袁 理，葉 露，賈建祿，2

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

2.中國科學院研究生院，北京100039）

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

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

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

2.中國科學院研究生院，北京100039）

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

橢圓檢測；隨機采樣；無效采樣；橢圓擬合

1 引 言

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

2 橢圓檢測算法

2.1 隨機采樣2點

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

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

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

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

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

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

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

2.3 用最小二乘法擬合橢圓

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

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

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

2.4 判斷點是否在橢圓上的新方法

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

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

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

圖3 判斷邊緣點在橢圓上的新方法

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

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

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

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

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

2.6 算法步驟

（1）計算圖像中各點的梯度斜率kt并存儲；

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

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

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

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

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

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

（8）在P中找一個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，結束。否則，轉(zhuǎn)（4）；

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

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

3 實驗結果

圖5 實驗用圖

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

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

4 結 論

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

［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è)大學學報（自然科學版），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］.微計算機信息，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］于莉娜，胡正平，練秋生.基于改進隨機Hough變換的混合圓/橢圓快速檢測方法［J］.電子測量與儀器學報，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］于海濱，劉濟林.基于中心提取的RHT在橢圓檢測中的應用［J］.計算機輔助設計與圖形學學報，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］陳燕新，戚飛虎.一種新的基于隨機Hough變換的橢圓檢測方法［J］.紅外與毫米波學報，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變換在圓檢測中的應用［J］.華東交通大學學報，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—），男，四川瀘州人，研究實習員，碩士，主要從事光學檢測、圖像識別等方面的研究。

E-mail：yuanlideyoux8852＠yahoo.cn