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