基于歐氏距離圖的隨機Hough變換橢圓檢測方法

摘 要： 為了實現橢圓目標的有效檢測，克服橢圓檢測過程中對橢圓完整性和邊緣梯度精度要求過高的缺點，提出了一種改進的隨機Hough變換的橢圓檢測方法。首先充分利用橢圓的軸對稱特性和極點?極弦性質求取候選橢圓，有效解決了無效采樣和累積問題，然后采用歐氏距離圖計算橢圓邊緣點的歐氏距離之和來確定真實橢圓。實驗結果表明，該算法相對于RHT?3算法和CMHT算法具有檢測精度高、檢測速度快和抗橢圓缺失能力強的優點。

關鍵詞： 橢圓檢測； 隨機Hough變換； 無效采樣； 歐氏距離

中圖分類號： TN911.73?34； TP391.41 文獻標識碼： A 文章編號： 1004?373X（2016）21?0061?04

Ellipse detection method based on random Hough transform

and Euclidean distance graph

GAO Yuyu， WANG Chunfang

（Liren College of Yanshan University， Qinhuangdao 066004， China）

Abstract： To detect the elliptical object effectively， and overcome the high requirements of edge gradient accuracy and ellipse integrity in ellipse detection process， an improved ellipse detection method based on improved random Hough transform is proposed. The axisymmetric characteristic， and pole and polar line property are fully used to get the candidate ellipse to solve the invalid sampling and accumulation problems effectively. The Euclidean distance graph is used to calculate the sum of Eucli?dean distances of the ellipse peripheral point to determine the true ellipse. The experimental results show that， in comparison with RHT?3 algorithm and CMHT algorithm， the algorithm proposed in this paper has higher detection accuracy， faster detection speed， and stronger ability to resist the ellipse loss.

Keywords： ellipse detection； random Hough transform； invalid sampling； Euclidean distance

0 引 言

橢圓檢測是圖像處理研究中的一個熱點，它在醫學圖像分析和機器視覺等領域內有著廣泛的應用[1]。Hough變換是檢測橢圓的一種有效方法，有很好的準確性和魯棒性，而且具有較強的抗噪能力和對橢圓缺失不敏感的優點，但直接應用Hough變換檢測橢圓存在著參數空間內存需求大、計算復雜的缺陷[2]。

針對這些問題，文獻[3]提出了隨機Hough變換（RHT），通過隨機采樣5個邊緣點確定參數空間，采用參數空間多對一映射和動態鏈表，降低計算復雜度和內存空間需求，具有參數精度任意高參數空間無限大的優點，但是大量隨機采樣和累積問題嚴重影響了RHT的性能。陳燕新等對RHT算法進行了改進，提出了RHT?3橢圓檢測算法[4]，利用邊緣梯度方向有效地解決了無效采樣和累積問題，但此方法僅適用于梯度方向集中的圖像。屈穩太利用橢圓的對稱性，提出了一種基于弦中點Hough變換（CMHT）的橢圓檢測方法[5]，雖然該算法檢測速度快，但是缺乏抗橢圓缺失的能力，檢測精度有待提高。Chang則提出了基于矩形邊框的橢圓檢測方法[6]，它不使用Hough變換，而是利用矩形邊框定位橢圓中心，從而獲得橢圓中心，然后使用邊界跟蹤尋找橢圓長軸的一個頂點，最后定位短軸的方向，該方法計算簡單有效，但僅僅應用于完整橢圓。文獻[7]提出基于圓弧的橢圓評價和檢測方法，圓弧通過邊界跟蹤和分割獲取，用圓弧代替邊緣點減少了圖像中噪聲點和其他形狀點的影響，抑制虛假橢圓的檢測，但其檢測精度較差。李楠楠等則提出一種不利用Hough變換的邊界弧分割橢圓檢測方法[8]，首先利用圖像中邊緣的交點分割成多個弧段，將弧段分為長弧和短弧，并且按長度排序，然后利用最小二乘法擬合橢圓，該方法對部分缺失的橢圓有很好的檢測效果，缺點是運算時間較長。本文充分利用橢圓的軸對稱特性和極點?極弦性質，檢測出橢圓的旋轉角度和一個長軸端點，然后利用選定的三個邊緣點求解其他參數，最后以歐氏距離圖確定真實橢圓，該方法有效解決了邊緣梯度方向和橢圓完整性要求過高的問題，去除了大量的無效采樣和累積，提高了算法的準確度和實時性。

1 隨機Hough變換原理

對于任意位置和角度的橢圓來說，如圖1所示，其中[（xc，yc）]為橢圓中心坐標，[（x，y）]為圖像空間坐標，[a]和[b]分別為長軸和短軸的長度，[φ]為長軸[a]與[x]軸的夾角，即相對于坐標軸的旋轉角度。橢圓方程為：

[x-xccosφ+y-ycsinφ2a2+ x-xcsinφ-y-yccosφ2b2=1] （1）

隨機Hough變換檢測橢圓的基本思想是采用多對一的映射和動態鏈表，僅對參數分配單元進行累積，這樣避免了傳統Hough變換一到多映射的龐大計算量和內存空間，具有參數空間無限大、參數精度任意高的優點，但在檢測橢圓時，隨機采樣5個邊緣點確定橢圓參數，無效采樣成指數增加，而且對無效采樣也會進行累積運算，加大參數空間搜索時間，占用了大量的內存空間。

2 改進的Hough變換檢測橢圓

2.1 旋轉角度的檢測

由于橢圓是軸對稱圖形，假如能夠尋找到長軸的斜率，則橢圓的旋轉角度就能夠確定。根據橢圓的極點?極弦性質，設橢圓上任意兩點[P1]和[P2]兩點的連線中點為[M，]若它們的切線不平行，交于一點[T，]這時稱點[T]為弦[P1P2]的極點，弦[P1P2]為極點[T]對應的極弦，則橢圓圓心[xc，yc]、極點[T]和極弦[P1P2]的中點共線[9]，如圖2所示。因此，隨機采樣兩點，若這兩點的垂直平分線與直線[TM]的方程相同，則認為在直線[TM]為長軸[a]所在的直線，且兩點關于長軸對稱。這時考慮極坐標系中由[P1x1，y1]和[P2x2，y2]形成的直線，直線方程可以表示為[ρ=xcosθ+ysinθ，]式中[ρ]是原點到直線的距離，[θ]是[x]軸到直線法線的夾角。若邊緣點對的垂直平分線為長軸所在直線，那么[θ]即為橢圓的旋轉角度[φ。]邊緣點對的垂直平分線可以通過下式計算：

[θ=tan-1y2-y1x2-x1ρ=x1+x2cosθ+y1+y2sinθ2] （2）

而對于直線[TM]，由于橢圓曲線上的點的邊緣方向的切線方向為該點的邊緣梯度方向，因此，可以得到切線[l1]和[l2]的方程，若[l1]和[l2]不平行，可以得到[T]點坐標，根據橢圓的極點?極弦性質，且[P1]和[P2]中點[M]的坐標為[x1+x22，y1+y22]，因此直線[TM]的參數方程為[ρ″=xcosθ+ysinθ″]。給定一定誤差范圍[Eθ，][Eρ，]當[θ-θ″≤Eθ]且[ρ-ρ″≤Eρ]時，則認為極弦[P1P2]的垂直平分線和直線[TM]重合。

圖2 橢圓的極點、極弦和形狀控制點

在圖像中有多個橢圓的情況下，隨機采樣的點對有可能屬于不同橢圓，這樣會造成無效采樣，為了減少屬于不同橢圓的點配對，這里增加一個約束條件：設置一個閾值[dr]，若[OP1-OP2

2.2 其他參數的求取

為了尋找橢圓的中心，并有效地去除無效采樣和累積，首先提出形狀控制點約束，如圖2所示。橢圓上的一段弧[P1P2]與直線[TM]相交于點[P3]，點[P3]被稱為橢圓的形狀控制點，則點[P3]的切線[l3]與極弦[P1P2]平行，且點[P3]位于點[M]與線段[TM]的中點[N]之間。若兩個邊緣點是橢圓上的兩個點，那么這兩個點必然滿足形狀控制點約束條件，否則這兩個邊緣點必然不在同一橢圓上。

根據這一約束，在線段[MN]上尋找一點[P3，]若[P3]滿足[MP3+P3N≤MN+σ，]則認為點[P3]在線段[MN]上，然后判斷[P3]的切線[l3]是否與極弦[P1P2]平行，若平行，由于[TM]為長軸所在直線，直線[TM]垂直于極弦[P1P2，]所以點[P3]是長軸的一個端點，可以求得長軸[a=xc-x32+yc-y32，]旋轉角度[φ]已求得，將[P1，][P2]和[P3]三點代入式（1），解方程組可求得橢圓的四個參數，確定一個候選橢圓；若沒有搜索到點[P3，]那么點[P1]和[P2]不在同一個橢圓上，重新采樣。

需要指出的是，雖然選取邊緣點[P1，][P2]進行旋轉角度檢測和形狀控制點約束搜索[P3]點時，都利用了邊緣點的梯度方向，但是使用邊緣點梯度方向的方式與文獻[4]中的RHT?3算法不同，本文方法僅僅利用邊緣梯度方向輔助判斷[P1，][P2]和[P3]三點是否存在，從而降低無效采樣和累積，并沒有用于橢圓參數的計算和累積，因此并不要求過高的精度，允許邊緣梯度存在一定范圍的誤差，不僅僅適用于梯度方向集中的圖像。

2.3 利用歐氏距離圖確定真實橢圓

在許多圖像處理的應用中，如模糊效果、圖像繪制與匹配，歐氏距離圖都是必不可少的。歐氏距離圖用來測量圖像中邊緣像素點之間的距離大小，反映了兩個像素之間的相似程度，即數值越小，兩個像素之間的差異越小[10]。對于一個[N×N]大小的二維二值圖像，將黑色像素作為邊緣像素點，歐氏距離圖采用歐氏距離作為基本距離度量，分配給每個像素到黑色像素的最近距離。圖像中兩個像素點的歐氏距離為：

[d=vNi-vNj22] （3）

式中：[v]表示像素值，[Ni]表示以[i]為中心像素的小鄰域。

對于獲取的邊緣，歐氏距離圖可以看作是一個二維數組，數組中每個元素用來儲存歐氏距離最近的邊緣點，如圖3所示。在上面的步驟中，由五個參數確定一個橢圓候選者。為了確認候選橢圓是否為真實橢圓，利用生成的歐氏距離圖去評估。統計落在該橢圓上的邊緣點，這些邊緣點已經被繪制在歐氏距離圖上，如圖4所示。計算這些邊緣點的歐氏距離之和[dsum]。假如這個候選橢圓為真實橢圓，那么這個橢圓接近邊緣點，且歐氏距離之和是很小的。因此，設置一個閾值[de，]若滿足[dsum

2.4 算法步驟

算法的實現步驟如下：

（1） 用Canny算子進行邊緣檢測，得到圖像的邊緣和梯度斜率[ki]，并繪制邊緣點的歐氏距離圖。將圖像空間的邊緣點[Pixi，yi]全部存入邊緣點集[D]中，然后建立參數單元集[P，]并初始化，令[P=NULL，][k=0；]

（2） 隨機選取[D]中的兩個邊緣點[P1，][P2，]如果兩點滿足[OP1-OP2

（3） 在線段[MN]上搜索點[P3，]若搜索到了，判斷[P3]的切線[l3]是否與極弦[P1P2]平行，若平行轉到步驟（4），否則轉到步驟（9）；

（4） 計算極弦[P1P2]的垂直平分線和直線[TM]的參數方程，給定誤差范圍[Eθ，][Eρ，]若[θ-θ≤Eθ]且[ρ-ρ≤Eρ，]計算得到[φ，]則轉到步驟（5），否則轉到步驟（9）；

（5） 通過[P1，][P2]和[P3]三點求取橢圓中心坐標[xc，yc]、長軸[a]和短軸[b，]得到橢圓參數空間點[p，]轉到步驟（6）；

（6） 設置一個容忍度[δ]，并在數據集[P]中尋找一個元素[pc，]若[p-pc<δ，]則轉到步驟（8），否則轉到步驟（7）；

（7） 在[p]上附加一個累加單元，其計數值score為1，然后將[p]作為一個新的元素插入到[P]中；

（8） 設置一個閾值[nt]（[nt=2，3，]甚至更大），將[pc]累加單元的score值加1，若[scorepc

（9） [k=k+1；]設定檢測一個橢圓所允許的隨機采樣最大點數[kmax，]如果[k>kmax，]則結束，否則，轉到步驟（2）；

（10） 將[pc]作為候選橢圓的參數，統計落在該橢圓上的邊緣點，計算它們的歐拉距離之和[dsum，]若[dsum

（11） 一條參數為[pc]的橢圓被提取出來，重置[P=NULL]和[k=0，]轉到第（2）步，繼續檢測。

3 實驗結果分析

為了測試基于改進隨機Hough變換橢圓檢測算法的準確性和魯棒性，本文選取了兩種不同的圖像對算法進行測試。

首先利用計算機生成一幅[100×100]的圖像，如圖5（a）所示。圖中共有4個不同方向的橢圓，其中有一個橢圓存在嚴重缺失現象。在理想的情況下，分別用RHT?3法、CMHT方法和本文方法對其進行橢圓檢測，檢測結果如圖5所示。

由表1可以看出，本文方法的檢測精度最高。由于在計算候選橢圓參數時使用采樣點距離限制、橢圓對稱性和極點?極弦性質對采樣點進行判斷，降低了隨機Hough變換中的無效采樣和無效累積，因此本文算法的檢測時間低于RHT?3法。而與CMHT法相比較，雖然本文方法的檢測時間略高于CMHT法，但是檢測精度卻遠比CHMT法要高。由圖5可以看出，特別是對缺失嚴重的橢圓，由于CMHT法尋找橢圓中心依靠對所有邊緣點對的中心點進行投票，求取其他參數時也是利用關于橢圓中心對稱的3對對稱點獲得，因此圖中中心部分缺失的橢圓未能檢測出來，RHT?3法雖然檢測出此橢圓的存在，由于過于依賴邊緣梯度方向，造成橢圓參數誤差較大，而本文方法都準確地將此橢圓檢測出來。

為了進一步測試本文算法的實時性和準確性，本文使用攝像機拍攝的真實圖像進行了另一項實驗。測試圖像大小為[300×300]，如圖6（a）所示。由實驗結果可以看出，RHT?3法檢測結果中沒有漏檢現象，但是在邊緣點投票中并沒有充分利用橢圓的幾何性質，仍然存在大量的無效采樣和無效累積，而且在累積計算中使用了邊緣梯度方向，對梯度方向的精確度要求較高，因此RHT?3法檢測時間較長，為99.78 s，且圖像右下方的不完整橢圓產生了不合理檢測。對于CMHT法，盡管檢測時間最短，僅為5.6 s，但由于僅僅利用邊緣點對的中心進行投票，因此缺失較大的兩個橢圓未能檢測出來，而且還錯誤檢測到圖像中兩個非橢圓的輪廓，檢測精度較差。而本文算法充分利用了橢圓的幾何性質來降低無效采樣和累積次數，僅僅利用邊緣梯度方向選取邊緣點，而不是將梯度方向用于橢圓參數的計算和累積，檢測時間為8.2 s，雖然與CMHT法相比檢測時間略長，但是沒有產生誤檢和漏檢現象，橢圓輪廓檢測結果合理，因此，本文算法的性能明顯優于RHT?3法和CMHT法。

圖6 實際圖像實驗結果圖

4 結 語

本文在隨機Hough變換原理的基礎上，結合極點?極弦性質和歐氏距離圖研究了一種改進的隨機Hough變換橢圓檢測算法。充分利用橢圓的軸對稱特性和極點?極弦性質求取候選橢圓，有效解決了無效采樣和累積問題，且對邊緣梯度精度和橢圓完整性無過高要求；采用歐氏距離圖確定真實橢圓，提高了檢測的準確率，增強了算法的魯棒性。實驗證明本文算法能準確地檢測圖像中的橢圓，實時性和魯棒性強。橢圓檢測在一些圖像的實時應用領域中有一定的應用價值，如衛星導航，視頻監控、航天航空等。今后將在亞像素級橢圓檢測、高的橢圓檢測率等方面做進一步研究。

參考文獻

[1] 羅琳，王志武，韋紅雨，等.可樂瓶口缺陷快速檢測系統的研制[J].計算機測量與控制，2008，16（4）：449?451.

[2] 牛曉霞，胡正平，楊蘇.局部PCA參數約束的Hough多橢圓分層檢測算法[J].計算機應用，2009，29（5）：1365?1368.

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

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

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

[6] CHANG Chunming. Detecting ellipses via bounding boxes [J]. Asian journal of health and information sciences， 2006（1）： 73?84.

[7] YU Q， ONG S H. Arc?based evaluation and detection of ellipse [J]. Pattern recognition， 2007， 40（7）： 1990?2003.

[8] 李楠楠，盧榮勝，李帥，等.基于邊界曲線弧分割的多橢圓檢測[J].計算機應用，2011，31（7）：1853?1855.

[9] CHIA A Y S， LEUNG M K H， ENG H L， et al. Ellipse detection with Hough transform in one dimensional parametric space [C]// Proceedings of 2007 IEEE International Conference on Image Processing. San Antonio： IEEE， 2007： 333?336.

[10] 張闖，王婷婷，孫冬嬌，等.基于歐氏距離圖的圖像邊緣檢測[J].中國圖象圖形學報，2013，18（2）：176?183.