今日頭條
官方微信
官方抖音
案例頻道
關(guān)鍵詞: 霍夫變換；圖像識(shí)別；自動(dòng)報(bào)靶
顧筠（1963—）
女，陜西西安人．江蘇廣播電視大學(xué)信息工程系講師。
1 引言
在計(jì)算機(jī)視覺(jué)領(lǐng)域中，如何從當(dāng)前的圖像中提取所需要的特征信息是圖像識(shí)別的關(guān)鍵所在。在許多應(yīng)用場(chǎng)合中需要快速準(zhǔn)確地檢測(cè)出圓或橢圓，從而進(jìn)行更深一步的操作，例如在基于圖像處理的自動(dòng)報(bào)靶系統(tǒng)中，對(duì)靶環(huán)的識(shí)別就屬于這樣的一類(lèi)應(yīng)用。在這方面很多學(xué)者提出了各種方法，如文獻(xiàn)[1]中提出了采用規(guī)則三角形網(wǎng)格的控制點(diǎn)校正方法，文獻(xiàn)[2]中提出了加入方向圖濾波的方法，對(duì)低成本普通攝像頭的幾何失真（“桶形”、“枕形”或者其他不規(guī)則的變形）進(jìn)行校正，取得了一定的效果。在筆者研究的自動(dòng)報(bào)靶系統(tǒng)中，圖像采集部分用的是高精度的攝像頭，這樣，傳統(tǒng)意義上的幾何失真并不明顯。影響報(bào)靶精度的主要矛盾之一，是由于攝像頭與靶紙之間的不完全垂直而引起的線性變形。
攝像頭采集到的圖形是橢圓或者是圓，如果能夠得到橢圓/圓的各個(gè)參數(shù)再加上對(duì)彈孔的定位，就可以根據(jù)公式計(jì)算出環(huán)值。本文提出了利用橢圓的幾何特性和邊緣方向信息將參數(shù)空間分解，用多級(jí)低維的霍夫變換來(lái)實(shí)現(xiàn)橢圓的檢測(cè)，大大減小了計(jì)算量和內(nèi)存占用量，滿(mǎn)足了對(duì)靶環(huán)識(shí)別的應(yīng)用需求。
2 霍夫變換及橢圓/圓的幾何特性引理
2.1 霍夫變換原理
霍夫變換用于直線檢測(cè)的基本策略為：由圖像空間的邊緣點(diǎn)去計(jì)算參數(shù)空間中參考點(diǎn)的可能軌跡，在累加器中給計(jì)算出的參考點(diǎn)計(jì)數(shù), 最后選出峰值。 因?yàn)樗鼘⒅苯亲鴺?biāo)系中的線變?yōu)闃O坐標(biāo)中的點(diǎn)，故一般常將霍夫變換稱(chēng)為線、點(diǎn)變換。 如圖1中的直線可用參數(shù)表示為：
ρxcos (θ)+y sin (θ)
其中:λ為圖象空間中的某條直線；Ｐ為原點(diǎn)到λ的垂直距離；α為λ斜率角度；λ在ρ－θ平面上可表示為一點(diǎn)(Ｐ ,α)。
圖1 直線的霍夫變換
根據(jù)這個(gè)原理，可以用霍夫變換提取直線，通常將x－y平面稱(chēng)為圖像平面，ρ－θ平面稱(chēng)為參數(shù)平面。 將該思想推廣到檢測(cè)曲線，則稱(chēng)為廣義霍夫變換。
2.2 橢圓/圓的幾何特性引理
引理1：設(shè)E為一橢圓或圓，現(xiàn)對(duì)自左向右，自上而下掃描，假設(shè)每一水平掃描線λHi與相交于點(diǎn)XL i和XR i，XM i為XL i和XR i的中點(diǎn)，則所有XM i均處于同一條直線lV上，稱(chēng)其為縱軸，XL i（XR i）則稱(chēng)為XR i（XL i）對(duì)于lV的對(duì)稱(chēng)點(diǎn)（見(jiàn)圖2）。
引理2：設(shè)E為一橢圓或圓，現(xiàn)對(duì)E自上而下，自左向右掃描，假設(shè)每一垂直掃描線lV i與E相交于點(diǎn) YT i 和YR i，YM為YT i 和YR i的中點(diǎn)，則所有 YM均處于同一條直線lH上，稱(chēng)其為橫軸，YT i（YR i）則稱(chēng)為YR i（YT i）對(duì)于lH的對(duì)稱(chēng)點(diǎn)（見(jiàn)圖2）。
引理3：設(shè)為一橢圓或圓，lV和lH為E的兩條對(duì)稱(chēng)軸，則lV和lH的交點(diǎn)即為橢圓E的中心O（見(jiàn)圖3）。
以上引理的證明可參見(jiàn)文獻(xiàn)[6,7]。
圖2 縱軸lV 與 橫軸lH
圖3 獲得橢圓圓心
3 應(yīng)用實(shí)例
霍夫變換是檢測(cè)橢圓的有效方法，若將標(biāo)準(zhǔn)霍夫（SHT）或者廣義霍夫變換（GHT）直接用于橢圓檢測(cè)，由于橢圓有5個(gè)自由參數(shù)，需要在五維參數(shù)空間進(jìn)行累積，致使這種算法因計(jì)算量和內(nèi)存需求量過(guò)大而難以在實(shí)際中應(yīng)用。為了克服上述缺陷，Xu[3]等提出了隨機(jī)霍夫變換（RHT），在圖像空間隨機(jī)地選取不在一條直線上的幾個(gè)點(diǎn)映射成參數(shù)空間的一個(gè)點(diǎn)，是多到一的映射。從而避免了霍夫變換一到多映射的巨大計(jì)算量。但在處理復(fù)雜圖像時(shí)，由于無(wú)目標(biāo)的隨機(jī)采樣會(huì)引入大量的無(wú)效采樣與無(wú)效累積，使計(jì)算性能大大降低。筆者提出了利用橢圓的幾何特性和邊緣方向信息將參數(shù)空間分解，用多級(jí)低維的霍夫變換來(lái)實(shí)現(xiàn)橢圓的檢測(cè)，大大減小了計(jì)算量和內(nèi)存需求。
3.1 形心的提取
在靶環(huán)識(shí)別的過(guò)程中，最關(guān)鍵的一步就是對(duì)形心的提取，只有快速精確地得到形心才能更好的進(jìn)行后續(xù)的各項(xiàng)操作。在開(kāi)始提取橢圓形心前，首先對(duì)圖像進(jìn)行預(yù)處理，包括灰度化、二值化、低通濾波等，并將得到的圖像存在圖像C中。此時(shí)，圖像C中含有數(shù)個(gè)同心橢圓（包括一些噪聲點(diǎn)）。圖4（a）為原始圖像，圖4（b）為經(jīng)過(guò)預(yù)處理的。
（a）預(yù)處理前 （b）預(yù)處理后
圖4 預(yù)處理前后的圖像
形心坐標(biāo)的提取步驟如下：
(1) 從第一行開(kāi)始自左向右掃描圖像C，如果掃描到的數(shù)值是0（二值化后0表示黑色象素，1表示白色象素），則保存該點(diǎn)的坐標(biāo)，并且再自右向左掃描這一行尋找黑色象素，保存其坐標(biāo)。這樣掃描完整張圖就可以得到外圈的橢圓邊界。初始化一空白圖像D，對(duì)于每個(gè)邊界特征點(diǎn)，應(yīng)用引理1，求得所有的XM i，并將其存于D中。
假設(shè)XM i所在直線的方程在極坐標(biāo)內(nèi)可表示為：ρ=xcos(θ)+ysin(θ)。考慮一個(gè)以參數(shù)ρ和θ定義的二維空間，x-y平面的任意一直線對(duì)應(yīng)了該空間的一個(gè)點(diǎn)。因此，x-y平面的任意一直線的霍夫變換是ρ-θ空間的一個(gè)點(diǎn)。現(xiàn)在考慮x-y平面的一個(gè)特定的點(diǎn)XM i，坐標(biāo)為（x,y），過(guò)該點(diǎn)的直線可以有很多，每一條都對(duì)應(yīng)了ρ-θ空間中的一個(gè)點(diǎn)。然而這些點(diǎn)必須是滿(mǎn)足以x和y作為常量時(shí)的等式。因此在參數(shù)空間中與x-y空間中所有這些直線對(duì)應(yīng)點(diǎn)的軌跡是一條正弦曲線，而x-y平面上的一個(gè)點(diǎn)（圖5（a））對(duì)應(yīng)了ρ-θ空間的一條正弦曲線（圖5（b））。這一組XM i中絕大多數(shù)都是位于由參數(shù)ρ0和θ0決定的直線上的邊緣點(diǎn)，所以這些邊緣點(diǎn)對(duì)應(yīng)于ρ-θ 空間的正弦曲線中絕大多數(shù)都交于點(diǎn)（ρ0, θ0），因?yàn)檫@是它們共享的一條直線的參數(shù) 。
（a） x－y空間 （b） ρ－θ 空間
圖5 x－y空間與ρ－θ空間的對(duì)應(yīng)關(guān)系
為了找出這些點(diǎn)所構(gòu)成的直線段，我們可以將ρ,θ空間量化成許多網(wǎng)格。根據(jù)每一個(gè)XM i點(diǎn)的坐標(biāo)（x,y）代入θ的量化值，算出各個(gè)ρ ，所得值（經(jīng)量化）落在某個(gè)網(wǎng)格內(nèi)，便使該網(wǎng)格的計(jì)數(shù)累加器加1，等全部（x,y）點(diǎn)變換后，對(duì)網(wǎng)格進(jìn)行檢測(cè)。計(jì)數(shù)值大的網(wǎng)格對(duì)應(yīng)于共線點(diǎn)，其（ρ,θ）可用作直線擬合參數(shù)，據(jù)此得到lV（如圖6，為了能看得清楚，圖中的黑色區(qū)域已去除）。
圖 6 提取得到的lV
(2) 重新初始化D，自上向下掃描C，對(duì)于每個(gè)邊界點(diǎn)，應(yīng)用引理2，求得所有的YM i，并將其存于D中。對(duì)圖像D作如上所述的變換檢測(cè)直線，檢測(cè)到的結(jié)果即是lH。求lV和lH的交點(diǎn)，根據(jù)引理3，該交點(diǎn)即是圖像中外圈橢圓的形心。如圖7，兩直線的交點(diǎn)即是所要提取的靶心。所示位圖的大小為340×369像素，以左下角第一個(gè)像素點(diǎn)為坐標(biāo)原點(diǎn)（0，0），則辨識(shí)到的形心坐標(biāo)為（167，187）。
圖 7 提取到的lH，交點(diǎn)O為靶心
3.2 橢圓旋轉(zhuǎn)角的獲取
設(shè)P(xP,yP)為橢圓上某一點(diǎn)，P為P點(diǎn)梯度，a和b分別為橢圓的半長(zhǎng)軸和半短軸。對(duì)于圓心在(x0,y0)、旋轉(zhuǎn)角度為0的橢圓，P(xP,yP)滿(mǎn)足以下關(guān)系：
（1）
（2）
圖8 a、b和φ
3.3 橢圓長(zhǎng)短軸的確定
在h = a / b已知的條件下，橢圓上點(diǎn)P(xp,yp)滿(mǎn)足下式：
（3）
（4）如果在2.2中成功獲得了h = a / b的值，則橢圓的長(zhǎng)短軸值可由（3、4）式求得。上圖的運(yùn)算結(jié)果為a＝179.4，
b＝157.7。
4 實(shí)驗(yàn)結(jié)果
采用以上算法能夠快速準(zhǔn)確地的獲取得圖像中所需圖形的幾何參數(shù)。算法是用vc++語(yǔ)言[5]實(shí)現(xiàn)的 ，在Pentium 42.4GHz的機(jī)器上檢測(cè)形心的運(yùn)算時(shí)間小于0.1秒；對(duì)一幅340×369的位圖，形心的定位誤差小于2個(gè)像素點(diǎn)。這樣的運(yùn)算速度和檢測(cè)精度完全能夠適應(yīng)自動(dòng)報(bào)靶系統(tǒng)的實(shí)時(shí)性、準(zhǔn)確性要求。
5 結(jié)束語(yǔ)
本文討論了利用幾何特性提取圖像中圖形的幾何參數(shù)的方法，并根據(jù)對(duì)稱(chēng)性特點(diǎn)快速確定形心，濾除原圖中不必要的干擾信息，降低了霍夫變換參數(shù)空間的維數(shù)，達(dá)到了準(zhǔn)確、快速提取幾何參數(shù)的效果。在實(shí)際應(yīng)用過(guò)程中，參數(shù)空間中累加器的疊加及尋找局部最大值時(shí)的閾值的選取尤為重要。本文的實(shí)現(xiàn)過(guò)程中，參數(shù)空間閾值的選取仍依靠經(jīng)驗(yàn)來(lái)選取某一固定值，這有待今后進(jìn)一步研究。由于算法中采用霍夫變換的投票機(jī)制確定參數(shù)，使得圖像中圖形邊界即使不連續(xù)或者部分殘缺（<30%）的情況下，仍能達(dá)到較為滿(mǎn)意的結(jié)果。
參考文獻(xiàn)：
[1] 鹿洪旭，盧朝陽(yáng)，高西全等.用于射擊運(yùn)動(dòng)自動(dòng)判靶的圖像校正算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與科學(xué)，2001，23（3）：21～24.
[2] 張建波，高西全，丁玉美等.一種提高射擊運(yùn)動(dòng)自動(dòng)判靶系統(tǒng)精度的方法[J]. 計(jì)算機(jī)工程與科學(xué)，2002，29（3）：324～327、342.
[3] Xu L, O ja E . Randomized Hough transform (RHT) : basic mechanisms，algorithms and computational complexities[J],Computer Vision Graphic Image Process : Image understanding , 1993,57 (2) : 131-154.
[4]彭?yè)P(yáng)，胡福橋，李介谷.橢圓特征的快速提取，上海交通大學(xué)學(xué)報(bào)，1998， 32(9) ：61－63.
[5] 何斌，馬天予，王運(yùn)堅(jiān).《Visual C++ 數(shù)字圖像處理》，北京：人民郵電出版社,2001.
[6] Huang C L . Elliptical feature extraction via an improved hough transform . Pattern Recognition Letters , 1989,10 : 93-100.
[7] Ho Chun Ta , Chen Ling Hwei . A fast ellipse/circle detector using geometric symmetry . Pattern Recognition , 1995,28 : 117-124.
作者信息：
顧 筠（江蘇廣播電視大學(xué)信息工程學(xué)院，江蘇 南京 210036）
北京市公安局海淀分局備案號(hào)：11010802023656號(hào)