基于Hough變換的橢圓檢測算法對比分析

成浩　崔文超

摘要：橢圓檢測在圖像識別與計算機視覺領域具有重要研究意義。為了對比分析出不同橢圓檢測算法的優缺點，提高檢測精確度和效率，針對基于Hough變換的橢圓檢測4種算法（傳統Hough變換方法、幾何特征橢圓檢測法、弦中點橢圓檢測法和三點橢圓檢測法）進行仿真，并對不同算法進行有效性分析。通過對檢測結果進行客觀評價，得出對比結論，并根據實驗結果分析不同算法適用的對象。設計了橢圓檢測對比分析軟件平臺，便于進行不同算法的對比分析。

關鍵詞：橢圓檢測；Hough變換；對比分析

DOIDOI：10.11907/rjdk.182095

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2018）009011504

英文標題Contrastive Study of Elliptical Detection Based on Hough Transform

——副標題

英文作者CHENG Hao， CUI Wenchao

英文作者單位（College of Computer and Information Technology， China Three Gorges University， Yichang 443000，China）

英文摘要Abstract：Ellipse detection is of great importance in image recognition and computer vision. In this paper， in order to compare and analyze the advantages and disadvantages of different ellipse detection methods and improve the accuracy and efficiency of detecting ellipse from images，four Hough transform based ellipse detection methods have been simulated， including traditional Hough transform method， geometric feature ellipse detection method， string midpoint ellipse detection method and threepoint ellipse detection method. The detection effectiveness regarding different algorithms has been analyzed and tested through the objective evaluation on the experimental results. Finally， the relevant contrastive conclusions are drawn， and the applicable objects of different methods are analyzed. At the same time， a software platform for ellipse detection and comparative analysis is designed to facilitate the comparative analysis of different algorithms.

英文關鍵詞Key Words：ellipse detection； Hough transform； contrastive analysis

0引言

隨著計算機視覺技術發展，人們可用計算機從圖像中確定橢圓的位置和形狀大小，如在數字攝影測量領域， 橢圓檢測可提高圖像匹配自動化程度和匹配率[1]；在模式識別領域，人臉識別和行人頭部的輪廓提取均可采用橢圓檢測技術實現[2]。因此，橢圓檢測有良好的應用前景，設計橢圓檢測對比分析系統對橢圓檢測算法的對比分析具有重要意義。

橢圓檢測算法主要分為投票（類聚）和最優化兩大類。最優化例如最小二乘法[35]，其通過最小誤差的平方和尋找符合樣本點的最佳函數，此類算法準確度高，但需要預先對數據進行分組處理，不能同時檢測多個橢圓。基于Hough變換的算法[69]，運用兩個坐標空間之間的變換，將樣本點映射到參數空間，然后采用統計投票或建立累加器的方法，在參數空間中尋找峰值確定橢圓。這類算法具有很好的魯棒性，對噪聲的靈敏度低于前述算法。本文對幾種基于Hough變換的改進算法進行對比分析。傳統Hough變換面對含有五維參數的橢圓檢測需要大量的內存空間和復雜的計算，因此降低Hough變換映射的參數維度是提高此類算法運算性能的關鍵。

大多數學者對橢圓檢測的研究集中在樣本點收集和降低參數維度方向。楊忠根等[10]詳細證明了橢圓的極點-極弦性質，并首次提出利用該性質提取橢圓，陳燕新[11]提出了三點橢圓檢測法，在橢圓上隨機采樣兩個點，然后利用極點極弦性質確定另一個采樣點，有效避免了無效采樣。于海濱等[12]充分利用橢圓的軸對稱特性，實現了參數空間累加列陣的降維，極大加快了橢圓檢測時間。屈穩太[13]將SHT和RHT結合，提出一種新的基于弦中點的Hough變換檢測算法。周祥[14]利用橢圓圓心的性質首先找到圓心，使參數維度降到二維，優化了傳統算法。

本文在上述研究基礎上，選取3種優化算法，簡單闡述其基本檢測原理，然后利用MATLAB軟件對不同算法的檢測效果進行分析比較，得出不同橢圓檢測算法的優缺點和各自適用的對象。設計橢圓檢測對比分析系統，能更直觀方便地對圖像檢測效果進行評價。

1橢圓檢測算法原理

1.1傳統橢圓檢測

平面上的橢圓用二次曲線方程表示為：

x2+Bxy+Cy2+Dx+Ey+F=0B2-4C<0（1+C）（4CF+BDE-D2C-B2F-E2）<0（1）

由于橢圓含有5個參數，直接采用Hough變換[15]中一對多的映射關系必然帶來龐大的計算量。為此Xu等[1617]提出了隨機Hough變換（RHT），采用多對一映射，主要思想如下：

假設要檢測的橢圓數學模型為f（α，z）=0，這里α=[B，C，D，E，F]，包含5個參數，RHT在圖像中隨機采樣5個點用來構造一個樣本，通過求解5個方程組將這個樣本映射到5維空間的一點上。若5個參數滿足式（1）中的兩個不等式，則該點對應的參數空間計數加1，重復上述過程，直至累加器中的計數超過設置的閾值，投票數最多的點對應的就是橢圓參數點。

1.2弦中點橢圓檢測法

橢圓的弦中點性質：在橢圓上任取一點，該點與橢圓其它邊緣點連接形成一組弦，該組弦的中點構成一個新橢圓，則稱新的橢圓是原橢圓在該點處的內切橢圓，如圖1所示。在同一個橢圓內，所有內切橢圓都相交橢圓圓心，如圖2所示。

由于非橢圓點相連的中點曲線只有很小的概率相交于橢圓圓心，因此在圓心處肯定會有較多的內切橢圓經過，這就是弦中點橢圓檢測法的基本思想。該算法步驟如下：先建立一個累加數組，用來存儲弦中點坐標，對于圖像中的每個邊緣點掃描，與其它邊緣點中點對應的數組便加一，跳過已經經過計算的邊緣點。設置閾值，累加數組的數值大于閾值便認為此處為一個橢圓圓心，確定了圓心后就能用傳統Hough變換檢測出其它3個參數。

1.3三點橢圓檢測法

包括橢圓在內的二次曲線可以利用極點、極弦來定義，以曲線上隨機兩點P1、P2為切點做兩條相交的切線，切線的交點T即為P1和P2的極點，過P1、P2的弦為二次曲線的極弦，根據極點-極弦性質，極點T、極弦的中點和橢圓中心C共線。如圖3所示，利用此性質可以在橢圓上隨機抽樣三點，確定兩條過圓心的直線，即可定位出橢圓圓心位置。另外，線段TM和橢圓的交點P3還具有一條性質：該交點處的切線l1平行極弦P1P2。

三點橢圓檢測法就是利用上述性質確定橢圓參數。隨機采樣兩個邊緣點，以當前邊緣點為中心，在一個小的鄰域內進行最小二乘擬合，所確定的直線就是該邊緣點的切線，若兩條切線不平行則可找到交點T，在P1P2中點M與T之間尋找與橢圓的交點P3（若未找到P3，則認為P1，P2不在同一橢圓上，需重新采樣），由交點P3處的切線與極弦P1P2平行的性質，確定得到的三點是否在同一橢圓上，這樣可避免大量不在同一橢圓上的三點組合，有效排除了傳統Hough變換中無效采樣問題，即使出現了極少數情況下的誤判，由于設置了多組獨立的采樣且后面還有投票的檢驗，該虛假點的影響也會被消除。若采樣到的三點組P、K、Q在橢圓上，則可利用對應的極弦確定橢圓圓心。

1.4幾何特征橢圓檢測法

引入一條關于橢圓幾何特征的數學定理，該算法就是基于這個定理提出的：任取橢圓平面上的一點p，其距離橢圓邊緣點的最大距離一定大于橢圓的長軸，所以圓心是橢圓平面上距橢圓邊緣點最大距離最小的點，性質證明參見文獻[4]。幾何特征橢圓檢測法就是通過查找距離橢圓邊緣點最大距離最小的點來確定圓心，同時這個最小的最大距離就是橢圓長軸，剩下的兩個參數就能在二維參數空間進行統計。

具體算法如下：將要處理的圖像進行邊緣檢測，將邊緣圖上的點存入數組A中，掃描二維圖像上的每個點，計算與數組A中的每個點的距離，所有點中最大距離最小的點便是橢圓圓心，該距離就是橢圓長軸a。然后在二維參數空間對短軸b和角度θ進行統計，得到峰值超過一定閾值的一組參數即為橢圓。

2橢圓檢測算法有效性分析

假設在一個圖像中有N個特征點，其中有Ni個屬于橢圓邊緣點，Nf個噪聲點，由于橢圓有5個獨立參數，所以在傳統的Hough變換中需要采樣5個橢圓邊緣點，而在圖像中隨機采樣的5個點中全部落在橢圓上的概率為：

pvalid=c5Nic5N=Ni（Ni-1）（Ni-2）（Ni-3）（Ni-4）N（N-1）（N-2）（N-3）（N-4）（2）

顯然，圖像中的噪聲點越多，采樣的5個點落在橢圓上的概率就越小，無效采樣越多，因此需要大量的內存空間和復雜計算。下面討論改進算法的有效性。

利用三點橢圓檢測法只需要2個有效采樣點，則2點落在橢圓上的概率為：

p1=c2Nic2N=Ni（Ni-1）N（N-1）（3）

同樣條件下，利用弦中點橢圓檢測法，圖像中有Nline=N（N-1）/2條線段，每條線段對應一個中點，但只有兩個橢圓點連接的線段才對應橢圓圓心，則有效采樣線段有Nvalid=Ni（Ni-1）/2線段，采樣到有效中點的概率為：

p2=NvalidNline=Ni（Ni-1）N（N-1）（4）

對于幾何特征橢圓檢測法，大小為m×n的圖像中每一個像素點與每一個特征點的距離計算次數為m×n×N，與橢圓邊緣點的距離計算次數為m×n×Ni，則有效計算的概率為：

p3=m×n×Nim×n×N=NiN（5）

由表1可知，弦中點橢圓檢測法和三點橢圓檢測法都能大大提高有效采樣概率，幾何特征橢圓檢測法在低信噪比情況下有效性較高。由于確定中心點需要準確的長軸信息，因此當橢圓內部的噪聲點過多時會嚴重影響算法性能，導致算法失效。

3檢測結果對比

為了測試3種橢圓檢測算法性能，采用一組相同圖片作為仿真圖像，其大小為450×320，運用MATLAB軟件編程實現檢測試驗，試驗環境為Window10操作系統，Intel Core-i5主頻為1.65 GHz處理器，內存為4 GB，不同的檢測效果如圖5所示。

僅從檢測結果參數難以分析出不同算法間的差異，因此有必要引入兩種綜合測度。

4定量比較

在評價不同檢測算法性能時，本文采用相似度與逼近度兩種綜合測度對檢測結果進行定量分析。

（1）相似度S定義為：

S=[∑（x，y）E（x+i，y+i）]/dotR（6）

式（6）中dotR是區域內總的邊緣點數目。

E（x+i，y+i）=1，點（x，y）在理想橢圓上有近似點0，點（x，y）在理想橢圓上無近似點 （7）

（2）逼近度D的定義為：

D=∑id（pi，c）/∑jd（pj，c）（8）

式（8）中：d（pi，c）是檢測到的輪廓點集合中點pi與橢圓圓心的距離，d（pj，c）是橢圓邊緣點集合中點pj與橢圓中心的距離。

進行仿真實驗后檢測出的橢圓相似度與逼近度計算結果如表3所示。

從表3數據可以看出，3種優化算法相比隨機Hough變換在擬合準確度與耗時上都有很大提高。不同算法擬合準確度從高到低依次為：弦中點橢圓檢測法、幾何特征橢圓檢測法、三點橢圓檢測法。3種算法在實驗中耗時也不相同，幾何特征橢圓檢測法耗時最少，弦中點橢圓檢測法其次，三點橢圓檢測法用時最長。

5綜合分析

弦中點橢圓檢測法更多考慮的是算法有效性問題，充分利用了橢圓內切圓必過中心點的性質，降低了傳統Hough變換中無效采樣概率，確保每次收斂映射結果一定是橢圓，從而在保證算法精度的前提下顯著提高了效率。

三點橢圓檢測法確保采樣的三點組一定在橢圓上，使RHT每次的收斂映射結果都為橢圓參數，另外該算法對邊緣數據集合的要求相當低，允許邊緣不連續且含有一定比例的假邊緣，所以此算法應用范圍很廣，對于一些較為復雜的圖像檢測效果優于其余兩種算法。但此算法要求在采樣點處有理想的邊緣梯度方向，對采樣點選擇較為嚴格，因此算法耗時較長。當橢圓形變較大時，其檢測效果下降。

幾何特征橢圓檢測法利用橢圓中心的幾何性質對圖像進行過濾，獲得可能的橢圓中心位置，將計算復雜度下降到了兩維，大大減少了運算時間和所需的參數空間，實現了橢圓特征的快速提取，且不受橢圓外部雜亂圖像的影響，在處理噪聲點較少的圖像時很有效。但該算法對橢圓內部噪聲敏感，因此適用于處理低信噪比下的簡單圖像。

為了更加方便地比較3種算法的優劣，設計了橢圓檢測對比分析系統幫助分析。該系統不僅便于對檢測效果進行對比，還能在參數區顯示檢測橢圓的參數及兩種綜合測度值。系統啟動界面設有標題區、顯示區、橢圓檢測參數精準度比較區、控制區和算法選擇區5大區域，界面簡潔明了，操作方便，具有實驗所需的基本功能。檢測出的橢圓用紅線圈出，與原圖像都顯示在顯示區，從而能客觀評價算法精確度。橢圓檢測對比分析系統初始界面如圖6所示。

6結語

本文闡述了4種主要的橢圓檢測算法基本原理，并利用MATLAB軟件編程實現了不同算法對圖像的檢測。根據檢測結果對比，分析不同算法的優缺點與各自適用的圖像，在實際中根據需要選擇合適的算法。

對基于Hough變換的橢圓檢測算法，大部分學者都在降低參數維度方面進行了深入研究，但都不可避免地出現計算量大、耗時長等問題。而在直線檢測方面，已有學者提出將Hough變換與最小二乘法相結合的直線擬合算法[1820]，充分利用Hough變換抗噪聲能力強和最小二乘法擬合精度高的特點，為橢圓檢測研究帶來了有益啟示。將Hough變換與最小二乘法相結合用于橢圓檢測是一個新的研究思路。

參考文獻參考文獻：

[1]齊曉娟，董明利，王君，等.數字攝影測量中橢圓的高效檢測方法[J].北京機械工業學院學報，2005（4）：57.

[2]薛源，李艷萍.人臉識別技術的探討和研究[J].機械管理開發，2010，25（5）：3941.

[3]別秀德，彭志勇.基于改進最小二乘法的一種橢圓檢測與定位方法[J].可編程控制器與工廠自動化，2015（7）：99102.

[4]呂洪赫，姚振杰，易衛東.基于對稱性的最小二乘擬合隨機橢圓檢測算法[J].電子測量技術，2011，34（5）：3741.