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

袁 理，葉 露，賈建祿，2

（1.中國科學(xué)院長春光學(xué)精密機(jī)械與物理研究所，吉林長春130033；

2.中國科學(xué)院研究生院，北京100039）

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

袁 理1，葉 露1，賈建祿1，2

（1.中國科學(xué)院長春光學(xué)精密機(jī)械與物理研究所，吉林長春130033；

2.中國科學(xué)院研究生院，北京100039）

為了實(shí)現(xiàn)光電儀器對(duì)橢圓形目標(biāo)的準(zhǔn)確識(shí)別與跟蹤，基于Hough變換提出了一種新的橢圓檢測算法。該算法隨機(jī)采樣2點(diǎn)，再利用橢圓極和極弦的性質(zhì)來搜索第3點(diǎn)并篩除大量無效采樣；然后，以這3點(diǎn)為中心作正方形窗口，用窗口內(nèi)的所有點(diǎn)來擬合橢圓方程。在驗(yàn)證候選橢圓時(shí)，提出了一種新方法來判斷邊緣點(diǎn)是否在橢圓上，并且給出了確定真實(shí)橢圓的自適應(yīng)閾值。實(shí)驗(yàn)顯示，該算法的平均長度誤差為0.5 pixel，平均角度誤差為0.6°，平均耗時(shí)為79 ms，表明該算法精度高，速度快，檢測性能較好。

橢圓檢測；隨機(jī)采樣；無效采樣；橢圓擬合

1 引 言

為了實(shí)現(xiàn)光電儀器對(duì)橢圓形目標(biāo)的識(shí)別與跟蹤，需要從光電儀器所采集的圖像中檢測出橢圓。Hough變換［1］是形狀檢測的一種基本方法，但是橢圓的參數(shù)較多，如果用Hough變換來檢測橢圓，消耗的時(shí)間和內(nèi)存是難以接受的。Xu［2］等人提出了隨機(jī)Hough變換（Random Hough Transfor，RHT），主要通過隨機(jī)采樣與動(dòng)態(tài)鏈表存儲(chǔ)來降低計(jì)算時(shí)間與內(nèi)存需求。但是，RHT無目標(biāo)的采樣會(huì)引入大量的無效累積，浪費(fèi)大量的計(jì)算時(shí)間和存儲(chǔ)空間。為此，一些文獻(xiàn)對(duì)RHT算法做了改進(jìn)來檢測橢圓。文獻(xiàn)［3］先搜索圖像中的連續(xù)曲線，然后在同一連續(xù)曲線上采樣5點(diǎn)來計(jì)算橢圓參數(shù)，這樣提高了5點(diǎn)在同一個(gè)橢圓上的概率，但是搜索連續(xù)曲線太費(fèi)時(shí)，而且對(duì)于邊緣不連續(xù)的橢圓，檢測效果不好。文獻(xiàn)［4］隨機(jī)采樣6個(gè)點(diǎn)，若6個(gè)點(diǎn)都在一個(gè)橢圓上，則該橢圓成為可能橢圓，但隨機(jī)采樣的6個(gè)點(diǎn)都在一個(gè)橢圓上的概率太小，因此無效采樣也很多。文獻(xiàn)［5］利用3個(gè)點(diǎn)和其中2個(gè)點(diǎn)的切線方向來求橢圓方程；文獻(xiàn)［6］利用2點(diǎn)及其切線方向來提取橢圓中心，但是由于切線方向的誤差較大，所以這兩種方法的精度都不高。為了進(jìn)一步減少橢圓檢測的時(shí)間，提高檢測準(zhǔn)確性，本文在RHT的基礎(chǔ)上設(shè)計(jì)了一種新的橢圓檢測算法。

2 橢圓檢測算法

2.1 隨機(jī)采樣2點(diǎn)

對(duì)采集到的圖像進(jìn)行去噪、邊緣提取和二值化后，得到目標(biāo)的邊緣圖像。在所有邊緣點(diǎn)中，本文只隨機(jī)采樣2點(diǎn)。與隨機(jī)采樣5點(diǎn)或者3點(diǎn)相比，只隨機(jī)采樣2點(diǎn)大大增加了采樣點(diǎn)全部落在同一個(gè)橢圓上的概率，減少了無效采樣。為了減小誤差，采樣的2點(diǎn)之間的距離不能太小，因此設(shè)置一個(gè)適當(dāng)?shù)拈撝礵，如果2點(diǎn)的距離＜d，則放棄該2點(diǎn)，重新采樣。

2.2 橢圓極和極弦性質(zhì)的利用

隨機(jī)采樣得到2點(diǎn)后，可利用橢圓極和極弦的性質(zhì)來搜索第3點(diǎn)并篩除無效采樣。橢圓的極和極弦性質(zhì)如下［7］：如圖1所示，P1，P2為橢圓上兩個(gè)點(diǎn)，P1T和P2T為橢圓的兩條切線，兩切線交于T，T稱為橢圓的極，弦P1P2稱為橢圓的極弦。設(shè)P1P2的中點(diǎn)為M，TM的中點(diǎn)為G，則有以下兩結(jié)論成立：1）線段TM與橢圓的交點(diǎn)P3必在線段GM上；2）P3處的切線l1和弦P1P2平行。

圖1 橢圓的極和極弦的性質(zhì)

設(shè)隨機(jī)采樣得到的2點(diǎn)為P1，P2，它們的梯度方向的斜率kt可用Sobel算子求出［8］，則切線方向的斜率kP＝-1/kt，然后，可以求出切線P1T和P2T的方程，進(jìn)而求出T、M和G點(diǎn)的坐標(biāo)。接著，在線段GM上搜索第3個(gè)橢圓點(diǎn)P3。假設(shè)邊緣點(diǎn)為Q，如果Q不在線段GM上，則必有|GQ|+|QM|＞|GM|；如果Q在GM上，則必有|GQ|+|QM|＝|GM|?？紤]圖像的離散性，這里設(shè)置正閾值ε，若Q點(diǎn)滿足|GQ|+|QM|＜|GM| +ε，則認(rèn)為Q點(diǎn)在GM上，即在GM上搜索到了一個(gè)橢圓點(diǎn)Q。本文中ε取1。遍歷所有邊緣點(diǎn)后，如果GM上沒有搜索到點(diǎn)，則說明P1，P2點(diǎn)不在同一個(gè)橢圓上，則放棄這2點(diǎn)；若搜索到了，說明P1、P2點(diǎn)可能在同一個(gè)橢圓上，則繼續(xù)計(jì)算。

在GM上搜索到的點(diǎn)往往不止一個(gè)，可以從中隨機(jī)取出一個(gè)，將它作為P3點(diǎn)。然后，檢驗(yàn)P3處的切線l1與弦P1P2是否平行?？紤]到切線方向的誤差，如果l1與P1P2的夾角＜10°，即認(rèn)為平行，則說明P1，P2，P3可能在同一個(gè)橢圓上，繼續(xù)后續(xù)計(jì)算；如果不平行則放棄該3點(diǎn)并重新采樣。在以上過程中，對(duì)切線方向誤差的影響分析如下：第一，如果P3在橢圓上，切線誤差會(huì)使l1與P1P2的夾角不為0，但絕大多數(shù)情況下仍＜10°，所以仍然判斷l(xiāng)1與P1P2平行，不會(huì)將P3漏判；即使在極少數(shù)誤差很大的情況下出現(xiàn)漏判，也僅僅是浪費(fèi)一次有效采樣而已，由于采樣的次數(shù)很多，對(duì)整個(gè)橢圓檢測的影響不大。第二，如果P3點(diǎn)不在橢圓上，在大多數(shù)情況下l1與P1P2的夾角遠(yuǎn)＞10°，即使有切線誤差的影響也不會(huì)變化到10°以內(nèi)，所以不會(huì)將P3誤判為橢圓點(diǎn)；即使在極少數(shù)的情況下出現(xiàn)誤判，由于后面還有投票的檢驗(yàn)和邊緣點(diǎn)數(shù)的檢驗(yàn)，該虛假橢圓也會(huì)被排除。

本文充分利用了橢圓極和極弦的性質(zhì)，不僅搜索到了第3個(gè)橢圓點(diǎn)，還篩除了大量不共橢圓的無效采樣，減少了無效累積。

2.3 用最小二乘法擬合橢圓

現(xiàn)在已經(jīng)得到了可能共橢圓的3點(diǎn)P1，P2，P3，但3點(diǎn)不足以確定橢圓方程?？紤]到當(dāng)一個(gè)點(diǎn)在橢圓上時(shí)，它附近的點(diǎn)在同一個(gè)橢圓上的概率很大。因此，分別以P1，P2，P3為中心作3個(gè)正方形的小窗口，對(duì)窗口內(nèi)的所有邊緣點(diǎn)作橢圓最小二乘擬合。在確保能夠得到5個(gè)以上邊緣點(diǎn)的情況下，窗口的邊長要盡量小，以防止將橢圓以外的噪聲點(diǎn)也包含進(jìn)來，一般可取3。設(shè)橢圓方程為：

由于橢圓只有5個(gè)獨(dú)立參數(shù)，所以可以把參數(shù)F定為一個(gè)固定的任意值，本文取F＝100。將窗口內(nèi)的點(diǎn)代入式（1），得到一個(gè)超定線性方程組，設(shè)為UX＝V，求解其法方程UTUX＝UTV，即可得到橢圓的最小二乘解，如果該解滿足橢圓判別式B2-4AC＜0，則把求出的橢圓參數(shù)加入動(dòng)態(tài)鏈表進(jìn)行投票累積。

本文沒有像文獻(xiàn)［5］那樣用切線方向來直接求解橢圓參數(shù)，避免了切線方向誤差對(duì)橢圓參數(shù)的影響，提高了橢圓的檢測精度。

2.4 判斷點(diǎn)是否在橢圓上的新方法

當(dāng)投票累積值達(dá)到閾值時(shí)，該橢圓成為候選橢圓，接著就需要驗(yàn)證該橢圓上的邊緣點(diǎn)的數(shù)目。由于圖像的離散性，邊緣點(diǎn)一般不會(huì)準(zhǔn)確地滿足式（1），因此需要找出判斷邊緣點(diǎn)是否在橢圓上的辦法。很多文獻(xiàn)［4］采用了如下傳統(tǒng)方法：若邊緣點(diǎn)滿足

則認(rèn)為該邊緣點(diǎn)在橢圓上；但是閾值Td卻難以確定，通過大量的實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)Td取一個(gè)固定值時(shí)，對(duì)于不同的橢圓，其寬嚴(yán)程度有很大的不同。圖2是當(dāng)Td取0.5時(shí)由式（2）畫出的不同橢圓的圖像，可見，不同橢圓的邊緣厚度相差很大，這種方法是不可取的。

圖2 傳統(tǒng)方法畫出的橢圓圖像

圖3 判斷邊緣點(diǎn)在橢圓上的新方法

經(jīng)過大量實(shí)驗(yàn)和研究，本文提出一種新方法來判斷邊緣點(diǎn)是否在橢圓上。如圖3所示，設(shè)任一邊緣點(diǎn)為H，過H點(diǎn)分別作平行于x軸和y軸的直線Lx和Ly，Lx和Ly與橢圓共有0到4個(gè)交點(diǎn)，如果這些交點(diǎn)中存在與H的距離＜η的交點(diǎn)，則判斷H點(diǎn)在橢圓上；如果沒有與H的距離＜η的交點(diǎn)，則判斷H點(diǎn)不在橢圓上。其中η為閾值，本文取0.5。圖4是當(dāng)η取0.5時(shí)由新方法畫出的不同橢圓的圖像，其中所有橢圓的邊緣都細(xì)而均勻，效果遠(yuǎn)遠(yuǎn)勝過圖2?？梢姡屡袛喾椒▽?duì)不同橢圓的寬嚴(yán)程度是完全一樣的。

圖4 新方法畫出的橢圓圖像

2.5 橢圓上邊緣點(diǎn)數(shù)閾值的確定

如果候選橢圓上的邊緣點(diǎn)數(shù)超過閾值Mmin，即可以確定為真實(shí)橢圓。對(duì)于不同的橢圓，應(yīng)該有不同的自適應(yīng)閾值Mmin。設(shè)實(shí)際橢圓弧長度與理論的橢圓周長之比為λ，則真實(shí)橢圓的閾值

Mmin＝λ×π［1.5（a+b） -，（3）其中a、b是橢圓的兩個(gè)半軸長，可由式（1）的系數(shù)來計(jì)算，π［1.5（a+b）-是橢圓周長的近似計(jì)算公式。

2.6 算法步驟

（1）計(jì)算圖像中各點(diǎn)的梯度斜率kt并存儲(chǔ)；

（2）對(duì)圖像進(jìn)行中值濾波去噪，然后用Canny算子提取邊緣并二值化；

（3）構(gòu)造邊緣點(diǎn)集D，初始化參數(shù)單元集P＝NULL，循環(huán)次數(shù)k＝0；

（4）從D中隨機(jī)選取2個(gè)點(diǎn)P1，P2，如果距離|P1P2|＞d，轉(zhuǎn)（5）。否則轉(zhuǎn)（11）；

（5）按圖1所示在GM上搜索橢圓點(diǎn)P3，如果搜索到了，轉(zhuǎn)（6）。否則轉(zhuǎn)（11）；

（6）檢驗(yàn)P3處的切線與弦P1P2是否平行，若是，轉(zhuǎn)（7）。否則轉(zhuǎn)（11）；

（7）以P1，P2，P3三點(diǎn)為中心作正方形窗口，將窗口內(nèi)的所有點(diǎn)做最小二乘擬合，得到橢圓參數(shù)p，如果p滿足判別式B2-4AC＜0，轉(zhuǎn)（8）。否則轉(zhuǎn)（11）；

（8）在P中找一個(gè)pc滿足|p-pc|≤δ，δ是容許誤差，若找到了則轉(zhuǎn)（10）。否則，轉(zhuǎn)（9）；

（9）將p插入P，令其value為1，轉(zhuǎn)（11）；

（10）將pc的value加1，若小于閾值Nt（取2或3），轉(zhuǎn)（11）。否則，轉(zhuǎn)（12）；

（11）k＝k+1，若k＞Kmax，結(jié)束。否則，轉(zhuǎn)（4）；

（12）pc為候選橢圓的參數(shù)，驗(yàn)證該參數(shù)對(duì)應(yīng)橢圓上的點(diǎn)數(shù)M，若M＞Mmin，轉(zhuǎn)（13）。否則，為虛假橢圓，從P中去除pc，轉(zhuǎn)（4）；

（13）檢測到參數(shù)為pc的真實(shí)橢圓，判斷已檢測到的橢圓是否達(dá)到規(guī)定的數(shù)目，若是，結(jié)束；否則，將落在參數(shù)pc對(duì)應(yīng)橢圓上的點(diǎn)從D中去掉，重置P＝NULL，k＝0，轉(zhuǎn)（4）。

3 實(shí)驗(yàn)結(jié)果

圖5 實(shí)驗(yàn)用圖

為了驗(yàn)證本算法的有效性，用VC編程進(jìn)行實(shí)驗(yàn)。如圖5是一幅400×300的圖像，其中的兩個(gè)碗呈現(xiàn)橢圓形。在配置為Intel酷睿雙核E4600的CPU（2.4 GHz）和1 G內(nèi)存的計(jì)算機(jī)上，用本文的算法和文獻(xiàn)［4］、［5］的算法分別對(duì)圖像中的兩個(gè)橢圓檢測了20次，并由式（1）的系數(shù)計(jì)算出了橢圓的幾何參數(shù)。表1是檢測的平均結(jié)果，其中橢圓參數(shù)的列出順序?yàn)椋褐行淖鴺?biāo)（pixel）；兩半軸長（pixel）；對(duì)稱軸傾角（°），耗時(shí)的單位為ms。進(jìn)一步可算出本文算法的平均長度誤差為0.5 pixel，平均角度誤差為0.6°，平均耗時(shí)為79 ms；而文獻(xiàn)［4］分別為1.2 pixel，0.9°，301 ms；文獻(xiàn)［5］分別為2.0 pixel，1.1°，114 ms，可見本算法檢測精度較高、速度較快。

表1 3種算法各檢測20次的平均結(jié)果Tab.1 Average results of detecting ellipses for 20 times using threemethods

4 結(jié) 論

為了實(shí)現(xiàn)光電儀器對(duì)橢圓形目標(biāo)的準(zhǔn)確識(shí)別與跟蹤，提出了一種新的橢圓檢測算法。該算法有如下優(yōu)點(diǎn)：（1）只隨機(jī)采樣2點(diǎn)，增加了采樣點(diǎn)全部落在同一個(gè)橢圓上的概率，減少了無效采樣；（2）利用橢圓極和極弦的性質(zhì)搜索到了橢圓上的第3點(diǎn)，并篩除了大量無效采樣，減少了無效累積；（3）用最小二乘法擬合橢圓方程，避免了用切線計(jì)算橢圓參數(shù)帶來的誤差；（4）提出一種新方法來判斷邊緣點(diǎn)是否在橢圓上，該方法對(duì)不同橢圓的寬嚴(yán)程度完全一樣，大大優(yōu)于傳統(tǒng)方法。實(shí)驗(yàn)表明，該算法精度高、速度快，是一種較好的橢圓檢測算法。

［1］HOUGH PV C.Methods and means for recognizing complex patterns：US，3069654［P］.1962-12-18.

［2］XU L，OJA E.A new curve detectionmethod：Randomized Hough Transform（RHT）［J］.Pattern Recognition Lett.，1990，11（5）：331-338.

［3］王成儒，胡正平，練秋生.一種高效的混合圓/橢圓檢測方法［J］.貴州工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，31（4）：100-103.

WANG CH R，HU ZH P，LIAN Q SH.A new efficienthybrid circle and ellipse fast detectionmethod［J］.J.Guizhou University Technol.（Natural Science Edition），2002，31（4）：100-103.（in Chinese）

［4］薛程，王士同.一種新的不基于Hough變換的隨機(jī)橢圓檢測算法［J］.微計(jì)算機(jī)信息，2006，22（1）：265-268.

XUE CH，WANG SH T.A new non-HT-based randomized algorithm for detecting ellipses［J］.Control＆Automation，2006，22（1）：265-268.（in Chinese）

［5］于莉娜，胡正平，練秋生.基于改進(jìn)隨機(jī)Hough變換的混合圓/橢圓快速檢測方法［J］.電子測量與儀器學(xué)報(bào)，2004，18（2）：92-97.

YU LN，HU ZH P，LIAN Q SH.Hybrid circle and ellipse fast detection using improved randomized Hough transform［J］.J.Electronic Measurement and Instrument，2004，18（2）：92-97.（in Chinese）

［6］于海濱，劉濟(jì)林.基于中心提取的RHT在橢圓檢測中的應(yīng)用［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2007，19（9）：1107-1113.

YU H B，LIU JL.Ellipse detection by the RHT based on center extraction［J］.J.Computer-Aided Design＆Computer Graphics，2007，19（9）：1107-1113.（in Chinese）

［7］陳燕新，戚飛虎.一種新的基于隨機(jī)Hough變換的橢圓檢測方法［J］.紅外與毫米波學(xué)報(bào)，2000，19（1）：43-47.

CHEN Y X，QIF H.A new ellipse detection method using randomized Hough transform［J］.J.Infrared Millim.Waves，2000，19（1）：43-47.（in Chinese）

［8］瞿鈞，甘嵐.梯度Hough變換在圓檢測中的應(yīng)用［J］.華東交通大學(xué)學(xué)報(bào)，2007，24（1）：101-104.QU J，GAN L.The application of grads Hough transformation in circle detection［J］.J.East China Jiaotong University，

2007，24（1）：101-104.（in Chinese）

Ellipse detection algorithm based on Hough transform

YUAN Li1，YE Lu1，JIA Jian-lu1，2
（1.Changchun Institute of Optics，F(xiàn)ine Mechanics and Physics，Chinese Academy of Sciences，Changchun 130033，China；
2.Graduate University of Chinese Academy of Sciences，Beijing 100039，China）

In order to ensure that photoelectric instruments can identify and track elliptical objects accurately，a new algorithm based on Hough transform is proposed.The new algorithm randomly samples two points，and then searches the third point using the characters of ellipse′s pole and pole chord，and eliminates lots of invalid samples.In the following，it uses the three points as the centers tomake three square windows，and then all the points in the windows are used to fit the ellipse.When a candidate ellipse is validated，a new method is proposed to judge if edge points are on the ellipse，and an adaptive threshold is supplied to confirm real ellipses.The experiment indicates that the algorithm′s average length error is 0.5 pixel，average angle error is 0.6°，and the average time needed is79 ms.In conclusion，the algorithm has high precision and high speed，and shows a good capability of detecting ellipses.

ellipse detecting；random ly sampling；invalid sample；ellipse fitting

2010-03-11；

2010-05-13

TP301.6

A

1674-2915（2010）04-0379-06

袁 理（1983—），男，四川瀘州人，研究實(shí)習(xí)員，碩士，主要從事光學(xué)檢測、圖像識(shí)別等方面的研究。

E-mail：yuanlideyoux8852＠yahoo.cn