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

成浩　崔文超

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

關(guān)鍵詞：橢圓檢測；Hough變換；對比分析

DOIDOI：10.11907/rjdk.182095

中圖分類號：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號文章編號：16727800（2018）009011504

英文標(biāo)題Contrastive Study of Elliptical Detection Based on Hough Transform

——副標(biāo)題

英文作者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.

英文關(guān)鍵詞Key Words：ellipse detection； Hough transform； contrastive analysis

0引言

隨著計(jì)算機(jī)視覺技術(shù)發(fā)展，人們可用計(jì)算機(jī)從圖像中確定橢圓的位置和形狀大小，如在數(shù)字?jǐn)z影測量領(lǐng)域， 橢圓檢測可提高圖像匹配自動(dòng)化程度和匹配率[1]；在模式識(shí)別領(lǐng)域，人臉識(shí)別和行人頭部的輪廓提取均可采用橢圓檢測技術(shù)實(shí)現(xiàn)[2]。因此，橢圓檢測有良好的應(yīng)用前景，設(shè)計(jì)橢圓檢測對比分析系統(tǒng)對橢圓檢測算法的對比分析具有重要意義。

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

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

本文在上述研究基礎(chǔ)上，選取3種優(yōu)化算法，簡單闡述其基本檢測原理，然后利用MATLAB軟件對不同算法的檢測效果進(jìn)行分析比較，得出不同橢圓檢測算法的優(yōu)缺點(diǎn)和各自適用的對象。設(shè)計(jì)橢圓檢測對比分析系統(tǒng)，能更直觀方便地對圖像檢測效果進(jìn)行評價(jià)。

1橢圓檢測算法原理

1.1傳統(tǒng)橢圓檢測

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

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

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

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

1.2弦中點(diǎn)橢圓檢測法

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

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

1.3三點(diǎn)橢圓檢測法

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

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

1.4幾何特征橢圓檢測法

引入一條關(guān)于橢圓幾何特征的數(shù)學(xué)定理，該算法就是基于這個(gè)定理提出的：任取橢圓平面上的一點(diǎn)p，其距離橢圓邊緣點(diǎn)的最大距離一定大于橢圓的長軸，所以圓心是橢圓平面上距橢圓邊緣點(diǎn)最大距離最小的點(diǎn)，性質(zhì)證明參見文獻(xiàn)[4]。幾何特征橢圓檢測法就是通過查找距離橢圓邊緣點(diǎn)最大距離最小的點(diǎn)來確定圓心，同時(shí)這個(gè)最小的最大距離就是橢圓長軸，剩下的兩個(gè)參數(shù)就能在二維參數(shù)空間進(jìn)行統(tǒng)計(jì)。

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

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

假設(shè)在一個(gè)圖像中有N個(gè)特征點(diǎn)，其中有Ni個(gè)屬于橢圓邊緣點(diǎn)，Nf個(gè)噪聲點(diǎn)，由于橢圓有5個(gè)獨(dú)立參數(shù)，所以在傳統(tǒng)的Hough變換中需要采樣5個(gè)橢圓邊緣點(diǎn)，而在圖像中隨機(jī)采樣的5個(gè)點(diǎn)中全部落在橢圓上的概率為：

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

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

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

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

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

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

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

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

由表1可知，弦中點(diǎn)橢圓檢測法和三點(diǎn)橢圓檢測法都能大大提高有效采樣概率，幾何特征橢圓檢測法在低信噪比情況下有效性較高。由于確定中心點(diǎn)需要準(zhǔn)確的長軸信息，因此當(dāng)橢圓內(nèi)部的噪聲點(diǎn)過多時(shí)會(huì)嚴(yán)重影響算法性能，導(dǎo)致算法失效。

3檢測結(jié)果對比

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

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

4定量比較

在評價(jià)不同檢測算法性能時(shí)，本文采用相似度與逼近度兩種綜合測度對檢測結(jié)果進(jìn)行定量分析。

（1）相似度S定義為：

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

式（6）中dotR是區(qū)域內(nèi)總的邊緣點(diǎn)數(shù)目。

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

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

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

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

進(jìn)行仿真實(shí)驗(yàn)后檢測出的橢圓相似度與逼近度計(jì)算結(jié)果如表3所示。

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

5綜合分析

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

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

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

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

6結(jié)語

本文闡述了4種主要的橢圓檢測算法基本原理，并利用MATLAB軟件編程實(shí)現(xiàn)了不同算法對圖像的檢測。根據(jù)檢測結(jié)果對比，分析不同算法的優(yōu)缺點(diǎn)與各自適用的圖像，在實(shí)際中根據(jù)需要選擇合適的算法。

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

參考文獻(xiàn)參考文獻(xiàn)：

[1]齊曉娟，董明利，王君，等.數(shù)字?jǐn)z影測量中橢圓的高效檢測方法[J].北京機(jī)械工業(yè)學(xué)院學(xué)報(bào)，2005（4）：57.

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

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

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