姜春濤

　　（四川大學 計算機學院，四川 成都 610000）

       摘要：利用霍夫變換進行橢圓檢測，需要尋找橢圓的參數。使用橢圓主半軸的長度，可以快速地尋找橢圓的參數。這種方法需要將橢圓的短半軸長度求解出來，然后僅使用一維的聚集數組收集橢圓短半軸的長度信息。該方法不需要計算橢圓的邊的切線或者曲率，因此不易受到噪聲的影響。該方法的實現不需要大量的內存。合成的圖像和真實的圖像測試表明，這種方法是有效的。

　　關鍵詞：圖像處理；霍夫變換；橢圓檢測

　　中圖分類號：TP751文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.04.013

　　引用格式：姜春濤.利用長軸檢測橢圓［J］.微型機與應用，2017,36（4）：43-46.

0引言

　　橢圓檢測是圖像處理中的一個重要的問題，已經有很多種橢圓檢測的方法［110］。完全定義一個橢圓需要五個參數，因此變化霍夫變換［11］進行橢圓檢測需要五維的參數空間。這需要很大的內存和時間，所以需要使用幾何上的限制以減少參數空間。為了減少橢圓檢測中時間和空間的需求，以前的技術大部分將 5 維的參數空間分為更少維數的子空間。參考文獻［1］介紹了一種基于幾何屬性的橢圓檢測方法。 參考文獻［2］通過在相同的水平和垂直位置上的邊緣點構造兩個中間點矩陣，然后，利用霍夫變換從這兩個矩陣中檢測出直線［1213］，這些直線的交提供了可能的橢圓中心。 文獻［3］提出了一種包含切線信息的用于橢圓提取的映射方法。文獻［4］提出了一種有效的從圖像的邊中檢測橢圓的方法，其思路是在霍夫變換基礎上從邊緣中檢測對稱軸，一個高維的問題轉化成兩個二維的問題。先從邊緣中找到對稱軸，然后從邊緣中找到橢圓。文獻［4］介紹了一種利用橢圓長軸進行橢圓檢測的方法。利用短半軸的長度獲取在同一橢圓上的點，然后橢圓的參數被計算出來。

　　本文的橢圓檢測方法基于文獻［9］介紹的方法。這種方法使用新的方式計算橢圓的短半軸，需要的運算量稍微少一些。對于給定的橢圓長軸的兩個端點，文中提供了一種用于減少計算短半軸長度的點數的方法。

1橢圓參數的尋找

　　一個橢圓具有五個參數，它們分別是橢圓的中心坐標O(x0,y0)、橢圓的長半軸a、橢圓的短半軸b、橢圓的長軸與x軸的夾角T。橢圓的五個參數如圖1所示。

　　圖2是與圖1相對應的橢圓，它是將原橢圓的中心平移到坐標原點，然后順時針旋轉角度T后得到的。對應于圖2的橢圓方程是:

　　其中a2－x2>0。(2)

　　從圖1到圖2的線性變換，先是將橢圓的中心平移到坐標原點，其對應的變換矩陣為P，然后將橢圓順時針旋轉角度T，其對應的變換矩陣為R。整個變換的復合矩陣為A［1415］。變換矩陣P，T ，R如下：

　　假設點B(x,y)是位于圖1橢圓上的一點，而點C(xt,yt)是位于圖2橢圓上由點B經過線性變換A后的對應點,則C的坐標為:

　　從式(8)和(9)中可以得到

　　a2>x2t(10)

　　x2t+y2t≤a2(11)

　　使用霍夫變換檢測橢圓的基本算法［9］為：首先查找圖像中的邊緣點，找到距離滿足給定條件的兩點，這兩點被看成是橢圓主軸上的兩個端點，然后對圖像邊緣上的每一個點根據式(6)將其轉化到圖2所對應的坐標系中，若得到的點的坐標滿足條件(10)和(11)，則由式(2)計算出橢圓的短半軸的長度，最后根據短半軸長度將短半軸聚集矩陣中對應項的值加1。如果最終聚集矩陣中的某一項的值大于給定的閾值，則該項對應的邊緣像素點在同一橢圓上。假設橢圓的主軸上的兩個端點分別為(x1,y1)和(x2,y2)，則橢圓的中心O(x0,y0)、長半軸a及橢圓長軸與x軸的夾角T如下:

　　獲取橢圓的短半軸的長度，需要先按照式(6)將邊緣點的坐標轉化到圖2所示的坐標系中，需要4次乘法，4次加法，然后求解x2t需要1次乘法，求解y2t需要1次乘法，接著檢查條件(11)需要1次加法，最后按照式(2)求解短半軸長度需要1次乘法，1次除法，1次減法和1次求平方根。因此求解短半軸的長度總共需要8次乘除法，6次加減法和1次求平方根。在文獻［9］介紹的方法中，求解短半軸的長度需要11次乘除法，8次加減法和2次求平方根。經過比較可以看出，本文提供的方法需要的運算量要小一些。

2減少用于計算短半軸長度的點數

　　在前面介紹的橢圓檢測算法中，需要將邊緣像素點轉化到圖2所示的坐標系后才能判斷該點是否在某一個橢圓上，然后計算該橢圓的短半軸的長度。明顯不在橢圓上的點不必要進行轉化，這樣可以減少計算量。在橢圓邊界盒子外的點明顯不在橢圓上，不必轉化而將其排出。使用與坐標軸平行的邊界盒子，圖3橢圓邊界示意圖如圖3所示，圖中最大的長方形即為邊界盒子。設橢圓邊界盒子的寬為W， 高為H。邊界盒子的寬和高的計算式如下：

　　H=2a|cosT|+2bsinT(17)

　　W=2asinT+2b|cosT|(18)

　　上式中，b為橢圓的短半軸的最大長度，其最大值為a。橢圓的中心為O(x0,y0)，若點的坐標滿足條件

　　則將其轉化到圖2所示的坐標系后求解短半軸的長度。

3橢圓檢測的步驟

　　算法的輸入是從圖像中取得的邊緣像素點的列表 L，輸出是找到的橢圓的中心O(x0,y0)，長半軸a，短半軸b，長軸與x軸的夾角T以及橢圓的邊上的點。

　　根據前面對橢圓檢測算法的描述，橢圓檢測的步驟如下：

　　(1)在L中尋找距離在給定范圍內的兩點A,B，如果存在這樣的兩點，則跳到第（2)步，否則結束。

　　（2)將A,B作為橢圓長軸的兩個端點，按照式(12)、(13)、(14)、(15)、(16)計算出橢圓的中心O(x0,y0)、長半軸a、橢圓長軸與x軸的夾角T。

　　（3)按照式(17)、(18)分別計算出橢圓邊界盒子的高H和寬W。

　　（4)將短半軸聚集累加器中的每一項清零。

　　（5)對于L中的每一個點，如果點的坐標滿足式(19)、(20)，則將其坐標由式(6)轉化到圖2所對應的坐標系中，然后判斷得到的坐標是否滿足式(10)和(11)，如果滿足，則按照式(2)計算出短半軸的長度及聚集累加器中的對應項加1。

　　（6)在短半軸聚集累加器中查找值大于給定閾值的項，輸出該項對應的橢圓的長半軸長度a、短半軸長度b、中心坐標(x0,y0)、長軸與x軸的夾角T以及該橢圓對應的邊上的點。將該橢圓邊上的點從L中刪除。跳到第（1)步。

4合成圖像和真實圖像測試結果

　　使用合成的圖像作為測試數據，先使用Sobel算子計算出圖像的梯度，然后使用簡單閾值算法找到圖像的邊緣像素點列表。使用從圖像中獲取的邊緣像素點列表，根據前面的橢圓檢測步驟檢測圖像中的橢圓。測試使用的圖像以及檢測到的橢圓和橢圓邊緣點如圖4所示。測試用的圖像大小為640×480。檢測到的圖像中的橢圓的參數如表1所示。按照測試圖像中橢圓從左到右，從上到下，同心橢圓 (圓) 從小到大的順序，橢圓的數據在表中以這個順序列出。表中的 “數據無效” 表示檢測對象是圓，其長軸與x軸的夾角無意義；夾角T的單位為弧度。

　　從檢測結果來看，測試圖像中的橢圓 (圓) 被全部檢測到，得到的橢圓 (圓) 的參數比較準確。從圖4中檢測到的橢圓圖像看，在長軸端點附近的點沒有被檢測到，這是由于當邊緣點靠近長軸端點時，由式(2)求得的橢圓的短半軸的長度誤差大。

　　使用真實的圖像進行測試。先對測試圖使用高斯低通慮波器除噪聲，然后使用Sobel算子求圖像的梯度，接著使用簡單閾值算法得到圖像的邊緣，再進行痩邊處理［8，16］，得到圖像的邊緣像素點列表，最后根據前面的橢圓檢測步驟檢測圖像中的橢圓。測試圖像的大小為 640×480。測試結果如圖5所示，從測試結果看，圖中的橢圓被全部檢測出。橢圓檢測算法所找到的橢圓 (圓) 的邊緣點在圖中使用實線標示出。

5結論

　　本文介紹的橢圓檢測算法使用一維的聚集累加器，需要的內存少，受噪聲的影響小，算法對橢圓的檢測比較準確。橢圓檢測算法需要橢圓長軸上的兩個端點，如果橢圓長軸上的兩個端點不存在，則橢圓不會被檢測到。算法需要先找橢圓長軸上的兩個端點，然后令一個點在以這兩個端點為長軸的橢圓上，計算出這個橢圓的短半軸的長度，圖像的邊緣點很多，算法的運算量很大。通過Sobel算子求解圖像中的邊緣點方向［8］，根據邊緣點的方向將邊緣點分成兩部分，方向相對的各為一部分，然后分別在這兩部分中查找橢圓的長軸端點，以減少可能的橢圓長軸的端點數目。由于圖像中的邊存在大量的直線，如果一個邊緣點不是可能的橢圓長軸端點，則其附近的點為橢圓的長軸上的端點的可能性比較小。如果一個點被作為橢圓的長軸上的點被檢測，則它附近的點可以不再作為長軸的端點進行檢測，利用Sobel算子求解出的邊緣點的方向信息，將圖像中臨近的邊緣點中方向很相近的點只保留一個進行可能的長軸端點檢測，因為如果邊緣點的方向相同，則認為在同一直線上，不大可能成為橢圓的邊，這種方法能減少大量的運算量，但是誤差較大。

　　參考文獻

　　［1］ YIN P Y, CHEN L H. New method for ellipse detection by means for symmetry［J］. Journal of Electronic Imaging, 1994, 3(1): 20-29.

　　［2］ HO C, CHEN L. A fast ellipse/circle detector using geometric symmetry［J］. Pattern Recognition, 1995, 28(1): 117-124.

　　［3］ AGUADO A S, MONTIEL M E, NIXON M S. On using directional information for parameter space decomposition in ellipse detection［J］. Pattern Recognition, 1996, 29(3): 369-381.

　　［4］ LEI Y, WONG C. Ellipse detection based on symmetry［J］. Pattern Recognition, 1999, 20: 41-47.［5］ DAVIES E R. Finding ellipses using the generalized Hough Transform［J］. Pattern Recognition, 1989,9（2）: 87-96.

　　［6］ TSUJI S, MATSUMOTO F. Detection of ellipses by modified Hough Transform［J］. IEEE Transaction On Computers, 1978, 27(8): 777-781.

　　［7］ YIP R K K, TAM P K S, LEUNG D N K. Modification of Hough Transform for circles and ellipses detection using a 2-dimensional array［J］. Pattern Recognition, 1992, 25(9): 10071022.

　　［8］ DAVIES E R. Computer & Machine Vision［M］. 北京：機械工業出版社, 2013.

　　［9］ Xie Yonghong, Ji Qiang. A new efficient ellipse detection method［C］. 16th International Conference Pattern Recgnition, Proceedings.  Quebec, Canada, 2002， IEEE, 2002: 957960.

　　［10］ Ji Qiang, HARALICK R M. A statistically efficient method for ellipse detection［C］. Proceedings of 1999 International Conference on Image Processing USA: IEEE Computer Society Press, 1999:730-734.

　　［11］ BALLARD D H. Generalizing the Hough transform to detect arbitrary shapes［J］. Pattern Recognition, 1981, 13(2): 111-122.

　　［12］ HART P E. How the Hough Transform was invented［C］. IEEE Signal Processing, 2009: 1822.

　　［13］ DUDA R O, HART P E. Use of the Hough Transform to detect lines and curves in pictures［J］. Communications of the ACM, 1972, 15(1): 1115.

　　［14］ HEARN D, BAKER M P. Computer graphics with OpenGL［M］. 北京：電子工業出版社, 2006.

　　［15］ LAY D C. Linear algebra and its applications［M］. 北京：電子工業出版社, 2010.

　　［16］ GONZALEZ R C, WOODS R E. Digital image processing［M］. 北京：電子工業出版社, 2007.