基于Hough變換的橢圓檢測改進算法

陸路+梁光明+丁建文

摘 要： 在背景復雜的圖像中，針對多橢圓檢測時橢圓中心定位不準、虛假橢圓過多的缺點，提出一種基于Hough變換的改進算法。該算法對參數空間和Hough變換計算的改進提高了橢圓檢測的準確度，并利用參數方程判斷候選橢圓的真假。實驗結果表明，該檢測方法具有較強地抗干擾能力，能夠在復雜的環境中準確快速地檢測出多個橢圓。

關鍵詞： Hough變換； 橢圓檢測； 參數方程； 檢測方法

中圖分類號： TN911?34； TP391.41 文獻標識碼： A 文章編號： 1004?373X（2015）16?0092?03

An improved algorithm of ellipse detection base on Hough transform

LU Lu1， LIANG Guangming2， DING Jianwen3

（1. College of information Engineering， Xiangtan University， Xiangtan 411105， China；

2. School of Electronic Science and Engineering， National University of Defense Technology， Changsha 410075， China；

3. R & D Center， AVE Technology Co.， Ltd， Changsha 410013， China）

Abstract： An improved algorithm based on Hough transform is proposed for detection of multi ellipses in image with complicated background to cope with the problems of inaccurate position of the ellipse center and overmuch pseudo ellipse. The accuracy of the ellipse detection is improved through the developed calculation of parameter space and Hough transform. The true ellipse is distinguished from the pseudo candidate ellipses by using the parameter equation. The experimental results show that the detection method can detect multiple ellipses in the complex environment quickly and accurately， and has strong anti?interference ability.

Keywords： Hough transform； ellipse detection； parameter equation； detection method

在復雜圖像中如何快速而準確地檢測橢圓目標一直是研究者們努力探索的一個重要問題。這在生物醫學顯微圖像、工業自動化檢測、機器人視覺、空間技術和軍事防御等領域有重要的應用。Hough變換是曲線檢測最有效的方法之一，于1962年由Paul Hough提出，并在美國作為專利被發表[1]。標準Hough變換（SHT）的主要特點是：對于圖像中局部信息的缺損不敏感，對隨機噪聲的魯棒性；但由于計算量與存儲量隨著參數空間維數成指數關系增加而難以實用。大量研究致力于改善Hough變換的實用性，并取得了一定的成果。Xu等提出了隨機Hough變換（RHT）[2?3]。該方法是多到一的映射，避免了標準Hough變換一到多映射的巨大計算量。但是在處理干擾較多的復雜圖像時，RHT的隨機采樣會引入大量無效采樣，大大降低了算法的性能。文獻[4]提出了一種利用橢圓的極點、極弦中點與橢圓中心共線性質的RHT改進方法，但該方法對于多橢圓的檢測并不高效。陳燕新等利用梯度信息提出了一種較好地解決無效采樣的RHT改進算法[5]，但對噪聲比較敏感。還有一些利用幾何特征降低參數空間維度的方法[6?10]，如屈穩太提出了一種新的基于弦中點的Hough變換（CMHT）檢測方法[8]，利用橢圓上所有點的內切橢圓必經過橢圓中心的性質，先對圖像邊緣點進行累積求得橢圓中心，再利用橢圓方程計算橢圓另外3個參數；但此方法在處理背景復雜圖像時，會出現檢測出橢圓中心位置不準、虛假橢圓較多的情況。本文在CMHT算法的基礎上，提出一種橢圓檢測改進算法，用于真實大便鏡檢測圖像中的蟲卵細胞。本文算法對參數空間的計算以及橢圓參數的求解進行了改進，并結合參數方程進行了虛假橢圓的判斷，從而提高復雜環境下橢圓的檢測精度，降低了誤檢率。

1 CMHT算法原理

橢圓一般性方程為：

[Ax2+2Bxy+Cy2+2Dx+2Ey+1=0] （1）

設橢圓中心為（x0，y0），則橢圓方程變為：

[Ax-x02+2Bx-x0y-y0+Cy-y02+1=0] （2）

式（1）有5個自由參數，文獻[8]中CMHT算法采用2步檢測法：第1步利用弦中點的幾何特性投票統計得到關于橢圓中心的2個參數x0，y0；第2步結合橢圓方程式（2）計算出另外3個參數。

1.1 基于橢圓中心的投票

性質1：在橢圓上任取一點與橢圓上其他點的連線構成橢圓的一組弦，這組弦的中點構成一個新的橢圓，該橢圓稱為原橢圓在該點的內切橢圓，如圖1（a）所示。endprint

性質2：橢圓上外法線方向相反的2個點稱為橢圓的一對對偶點，橢圓上所有對偶點連線的中點即為橢圓的中心，如圖1（b）所示。

圖1 橢圓的幾何性質

由性質1可知橢圓上非對偶點之間連線的中點散布于各處；由性質2可知橢圓上所有對偶點連線的中點都集中落在橢圓中心處。另外其余非橢圓上的點即噪聲點與其他各點連線的中點也散布于各處，并且落在同一點的可能性很小。因此如果把原圖像邊緣二值圖中的每一個邊緣點都與其他點相連，并對連線的中點在參數空間進行投票統計，則在每個橢圓中心處將出現統計值的峰值，這正是Hough變換的基本思想。CMHT算法會遍歷參數空間中每個點的統計值，當某個點的值大于設定的閾值時則認為該點是一個橢圓中心。

1.2 橢圓參數計算

對每個橢圓中心（x0，y0），尋找關于中心對稱的3組特征邊緣點，代入式（2）中求解未知參數A，B，C。

2 本文改進方法

當處理復雜圖像時，參數空間會出現多個大于設定閾值點的位置接近的情況，導致檢測出較多虛假橢圓中心；且由于干擾點較多，計算出橢圓的另外3個參數會出現較大誤差。因此根據出現的問題本文算法增加了以下3點改進。

2.1 參數空間計算的改進

檢測參數空間統計值的極大值點作為橢圓中心，并根據極大值附近多個較大值點對中心點坐標進行修正。設參數空間H，根據先驗知識取橢圓長半軸長為a，對參數空間任意點P，設以該點為中心，邊長為2a的方形塊為局部區域R。先假設P點統計值P（x，y）為區域R的極大值Rmax。遍歷區域R，若某點統計值[Qx，y>Rmax]，則令[Rmax=Qx，y]，[Px，y=0]；若某點統計值[Qx，y≤Rmax]，則令[Qx，y=0]。對處理完參數空間所有點之后，參數空間的非零點即是極大值點，每個極大值點對應一個候選橢圓中心。設求出的n個候選橢圓中心為[Oi]（i=1，2，…，n），對原參數空間H中的每個點O，在其區域R中尋找統計值大于閾值的點組成點集S，S滿足：

[SjSj∈R且Sjx，y>λ?Ox，y， j=1，2，…，m] （3）

式中：比例系數λ=0.8，計算點集S的中心坐標O′ 即為橢圓中心的修正值：

[O′=1mj=1mSj=1mj=1mxj，yj] （4）

2.2 Hough變換求解橢圓參數

為了更準確地計算橢圓參數，可采用Hough變換結合橢圓參數方程求解。在中心點Oi附近尋找關于中心點對稱的邊緣點進行采樣存入數組Vi中。對于任意橢圓，設中心坐標為（x0，y0），橢圓長半軸長為a，橢圓短半軸長為b，橢圓傾斜角為θ。則參數方程為：

[x-x0cosθ+y-y0sinθ2a2+x-x0sinθ-y-y0cosθ2b2=1] （5）

將中心坐標Oi（x0，y0）帶入橢圓方程式（5）中，從數組Vi中取出數據在三維空間中結合式（5）并采用Hough變換對a，b，θ進行量化投票統計，求出參數空間最大值對應的3個參數即為候選橢圓的a，b，θ。

2.3 虛假橢圓判斷

對于候選橢圓E（x0，y0，a，b，θ），任意點P（x，y）落在橢圓上的判斷公式如下：

[x-x0cosθ+y-y0sinθ2a2+x-x0sinθ-y-y0cosθ2b2-1

以點（x0，y0）為中心選取長方形區域D，[D=x，yx-x0≤a+2且y-y0≤b+2]。取T=0.1，若點[Px，y∈D]且滿足式（6），則認為該點落在候選橢圓上。在區域D中計算原圖中落在候選橢圓上的實際邊緣點數目N1和組成候選橢圓的邊緣點數目N2，因為組成橢圓的點數是隨著a，b變化而變化的，所以應該以N1，N2的比值是否大于閾值λ來判斷候選橢圓是否為真，即當[N1N2>λ]時，候選橢圓為真。

3 實驗結果

為驗證本文算法檢測結果，采用2組圖片對本文算法與CMHT算法進行了對比檢測實驗，重點對橢圓檢測的準確度和速度進行考察。用Matlab 7.6編程實現了本文算法。測試平臺為普通PC機，CPU為Pentium E5300，2 GB內存，操作系統為Windows XP。本文的測試程序把檢測到的橢圓用紅色和綠色畫出，分別表示用CMHT算法和本文算法檢測得到的橢圓。第1組實驗采用簡單的合成圖像如圖2所示，圖像大小為248×180，所需檢測橢圓1個。第2組實驗為真實大便鏡檢圖像的一部分如圖3所示，圖像大小為448×350，所需檢測蟲卵3個。從圖2中可以看出，對于簡單的圖像，2種方法都能正確檢測得到橢圓，CMHT算法速度稍快一些（見表1）。但對于圖3中背景復雜的大便鏡檢圖像，特別是圖中處于右下方的橢圓有明顯遮蓋的情況，CMHT算法檢測的橢圓會出現中心位置不準等較大誤差，并且在圖像右上方出現誤檢，而采用本文算法仍能較快地檢測出多個橢圓，并定位準確（見表2）。由此可見，本文算法在檢測精度和誤檢率上都有很大改善。

圖2 簡單圖像的檢測

圖3 真實大便鏡檢圖像的檢測

表1 2種算法對圖2處理的結果對比

4 結 語

本文提出了一種基于Hough變換的橢圓檢測改進算法。利用對參數空間、橢圓參數計算的改進和虛假橢圓的判斷，提高了橢圓檢測準確度。由實驗結果可以看出，即使在背景復雜的圖像中，本文的改進算法也能準確快速地檢測各個橢圓的參數，運算速度快，檢測性能好，抗干擾性強，具有一定的實用性。

表2 2種算法對圖3處理的結果對比

參考文獻

[1] HOUGH V， PAUL C. Method and means for recognizing complex patterns： US， 3069654 [P]. 1962?12?18.

[2] XU L， OJ A E. Randomized Hough transform （RHT）： Basic mechanisms， algorithms and computational complexities [J]. Computer Vision Graphic Image Process ： Image Understanding， 1993， 57（2）： 131?154.

[3] XU L， KALVIA I H， HIRVON E P， et al. Probabilistic and non?probabilistic Hough transforms ： Overview and comparisons [J]. Image and Vision Computing， 1995， 13（4）： 239?252.

[4] MCLAUGHLIN R A. Randomized hough transform： Improved ellipse detection with comparison [J]. Pattern Recognition Letters， 1998， 19（3/4）： 299?305.

[5] 陳燕新，戚飛虎.一種新的基于隨機Hough變換的橢圓檢測方法[J].紅外與毫米波學報，2000，19（1）：43?47.

[6] KALVIAINEN H， HIRVONEN P. An extension to the randomized Hough transform exploiting connectivity [J]. Pattern Recognition Letters， 1997（18）： 77?85.

[7] 于海濱，劉濟林.基于中心提取的RHT在橢圓檢測中的應用[J].計算機輔助設計與圖形學學報，2007，19（9）：1107?1113.

[8] 屈穩太.基于弦中點Hough變換的橢圓檢測方法[J].浙江大學學報：工學版，2005，39（8）：1132?1196.

[9] 黎自強，滕弘飛.基于局部搜索的多橢圓隨機檢測算法[J].計算機工程與應用，2006（12）：9?12.

[10] 周祥，孔曉東，曾貴華.一種新的基于Hough變換的橢圓輪廓檢測方法[J].計算機工程，2007，33（16）：166?171.endprint