陸路+梁光明+丁建文

摘 要： 在背景復(fù)雜的圖像中，針對多橢圓檢測時橢圓中心定位不準(zhǔn)、虛假橢圓過多的缺點，提出一種基于Hough變換的改進(jìn)算法。該算法對參數(shù)空間和Hough變換計算的改進(jìn)提高了橢圓檢測的準(zhǔn)確度，并利用參數(shù)方程判斷候選橢圓的真假。實驗結(jié)果表明，該檢測方法具有較強(qiáng)地抗干擾能力，能夠在復(fù)雜的環(huán)境中準(zhǔn)確快速地檢測出多個橢圓。

關(guān)鍵詞： Hough變換； 橢圓檢測； 參數(shù)方程； 檢測方法

中圖分類號： TN911?34； TP391.41 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2015）16?0092?03

An improved algorithm of ellipse detection base on Hough transform

LU Lu1， LIANG Guangming2， DING Jianwen3

（1. College of information Engineering， Xiangtan University， Xiangtan 411105， China；

2. School of Electronic Science and Engineering， National University of Defense Technology， Changsha 410075， China；

3. R & D Center， AVE Technology Co.， Ltd， Changsha 410013， China）

Abstract： An improved algorithm based on Hough transform is proposed for detection of multi ellipses in image with complicated background to cope with the problems of inaccurate position of the ellipse center and overmuch pseudo ellipse. The accuracy of the ellipse detection is improved through the developed calculation of parameter space and Hough transform. The true ellipse is distinguished from the pseudo candidate ellipses by using the parameter equation. The experimental results show that the detection method can detect multiple ellipses in the complex environment quickly and accurately， and has strong anti?interference ability.

Keywords： Hough transform； ellipse detection； parameter equation； detection method

在復(fù)雜圖像中如何快速而準(zhǔn)確地檢測橢圓目標(biāo)一直是研究者們努力探索的一個重要問題。這在生物醫(yī)學(xué)顯微圖像、工業(yè)自動化檢測、機(jī)器人視覺、空間技術(shù)和軍事防御等領(lǐng)域有重要的應(yīng)用。Hough變換是曲線檢測最有效的方法之一，于1962年由Paul Hough提出，并在美國作為專利被發(fā)表[1]。標(biāo)準(zhǔn)Hough變換（SHT）的主要特點是：對于圖像中局部信息的缺損不敏感，對隨機(jī)噪聲的魯棒性；但由于計算量與存儲量隨著參數(shù)空間維數(shù)成指數(shù)關(guān)系增加而難以實用。大量研究致力于改善Hough變換的實用性，并取得了一定的成果。Xu等提出了隨機(jī)Hough變換（RHT）[2?3]。該方法是多到一的映射，避免了標(biāo)準(zhǔn)Hough變換一到多映射的巨大計算量。但是在處理干擾較多的復(fù)雜圖像時，RHT的隨機(jī)采樣會引入大量無效采樣，大大降低了算法的性能。文獻(xiàn)[4]提出了一種利用橢圓的極點、極弦中點與橢圓中心共線性質(zhì)的RHT改進(jìn)方法，但該方法對于多橢圓的檢測并不高效。陳燕新等利用梯度信息提出了一種較好地解決無效采樣的RHT改進(jìn)算法[5]，但對噪聲比較敏感。還有一些利用幾何特征降低參數(shù)空間維度的方法[6?10]，如屈穩(wěn)太提出了一種新的基于弦中點的Hough變換（CMHT）檢測方法[8]，利用橢圓上所有點的內(nèi)切橢圓必經(jīng)過橢圓中心的性質(zhì)，先對圖像邊緣點進(jìn)行累積求得橢圓中心，再利用橢圓方程計算橢圓另外3個參數(shù)；但此方法在處理背景復(fù)雜圖像時，會出現(xiàn)檢測出橢圓中心位置不準(zhǔn)、虛假橢圓較多的情況。本文在CMHT算法的基礎(chǔ)上，提出一種橢圓檢測改進(jìn)算法，用于真實大便鏡檢測圖像中的蟲卵細(xì)胞。本文算法對參數(shù)空間的計算以及橢圓參數(shù)的求解進(jìn)行了改進(jìn)，并結(jié)合參數(shù)方程進(jìn)行了虛假橢圓的判斷，從而提高復(fù)雜環(huán)境下橢圓的檢測精度，降低了誤檢率。

1 CMHT算法原理

橢圓一般性方程為：

[Ax2+2Bxy+Cy2+2Dx+2Ey+1=0] （1）

設(shè)橢圓中心為（x0，y0），則橢圓方程變?yōu)椋?/p>

[Ax-x02+2Bx-x0y-y0+Cy-y02+1=0] （2）

式（1）有5個自由參數(shù)，文獻(xiàn)[8]中CMHT算法采用2步檢測法：第1步利用弦中點的幾何特性投票統(tǒng)計得到關(guān)于橢圓中心的2個參數(shù)x0，y0；第2步結(jié)合橢圓方程式（2）計算出另外3個參數(shù)。

1.1 基于橢圓中心的投票

性質(zhì)1：在橢圓上任取一點與橢圓上其他點的連線構(gòu)成橢圓的一組弦，這組弦的中點構(gòu)成一個新的橢圓，該橢圓稱為原橢圓在該點的內(nèi)切橢圓，如圖1（a）所示。endprint

性質(zhì)2：橢圓上外法線方向相反的2個點稱為橢圓的一對對偶點，橢圓上所有對偶點連線的中點即為橢圓的中心，如圖1（b）所示。

圖1 橢圓的幾何性質(zhì)

由性質(zhì)1可知橢圓上非對偶點之間連線的中點散布于各處；由性質(zhì)2可知橢圓上所有對偶點連線的中點都集中落在橢圓中心處。另外其余非橢圓上的點即噪聲點與其他各點連線的中點也散布于各處，并且落在同一點的可能性很小。因此如果把原圖像邊緣二值圖中的每一個邊緣點都與其他點相連，并對連線的中點在參數(shù)空間進(jìn)行投票統(tǒng)計，則在每個橢圓中心處將出現(xiàn)統(tǒng)計值的峰值，這正是Hough變換的基本思想。CMHT算法會遍歷參數(shù)空間中每個點的統(tǒng)計值，當(dāng)某個點的值大于設(shè)定的閾值時則認(rèn)為該點是一個橢圓中心。

1.2 橢圓參數(shù)計算

對每個橢圓中心（x0，y0），尋找關(guān)于中心對稱的3組特征邊緣點，代入式（2）中求解未知參數(shù)A，B，C。

2 本文改進(jìn)方法

當(dāng)處理復(fù)雜圖像時，參數(shù)空間會出現(xiàn)多個大于設(shè)定閾值點的位置接近的情況，導(dǎo)致檢測出較多虛假橢圓中心；且由于干擾點較多，計算出橢圓的另外3個參數(shù)會出現(xiàn)較大誤差。因此根據(jù)出現(xiàn)的問題本文算法增加了以下3點改進(jìn)。

2.1 參數(shù)空間計算的改進(jìn)

檢測參數(shù)空間統(tǒng)計值的極大值點作為橢圓中心，并根據(jù)極大值附近多個較大值點對中心點坐標(biāo)進(jìn)行修正。設(shè)參數(shù)空間H，根據(jù)先驗知識取橢圓長半軸長為a，對參數(shù)空間任意點P，設(shè)以該點為中心，邊長為2a的方形塊為局部區(qū)域R。先假設(shè)P點統(tǒng)計值P（x，y）為區(qū)域R的極大值Rmax。遍歷區(qū)域R，若某點統(tǒng)計值[Qx，y>Rmax]，則令[Rmax=Qx，y]，[Px，y=0]；若某點統(tǒng)計值[Qx，y≤Rmax]，則令[Qx，y=0]。對處理完參數(shù)空間所有點之后，參數(shù)空間的非零點即是極大值點，每個極大值點對應(yīng)一個候選橢圓中心。設(shè)求出的n個候選橢圓中心為[Oi]（i=1，2，…，n），對原參數(shù)空間H中的每個點O，在其區(qū)域R中尋找統(tǒng)計值大于閾值的點組成點集S，S滿足：

[SjSj∈R且Sjx，y>λ?Ox，y， j=1，2，…，m] （3）

式中：比例系數(shù)λ=0.8，計算點集S的中心坐標(biāo)O′ 即為橢圓中心的修正值：

[O′=1mj=1mSj=1mj=1mxj，yj] （4）

2.2 Hough變換求解橢圓參數(shù)

為了更準(zhǔn)確地計算橢圓參數(shù)，可采用Hough變換結(jié)合橢圓參數(shù)方程求解。在中心點Oi附近尋找關(guān)于中心點對稱的邊緣點進(jìn)行采樣存入數(shù)組Vi中。對于任意橢圓，設(shè)中心坐標(biāo)為（x0，y0），橢圓長半軸長為a，橢圓短半軸長為b，橢圓傾斜角為θ。則參數(shù)方程為：

[x-x0cosθ+y-y0sinθ2a2+x-x0sinθ-y-y0cosθ2b2=1] （5）

將中心坐標(biāo)Oi（x0，y0）帶入橢圓方程式（5）中，從數(shù)組Vi中取出數(shù)據(jù)在三維空間中結(jié)合式（5）并采用Hough變換對a，b，θ進(jìn)行量化投票統(tǒng)計，求出參數(shù)空間最大值對應(yīng)的3個參數(shù)即為候選橢圓的a，b，θ。

2.3 虛假橢圓判斷

對于候選橢圓E（x0，y0，a，b，θ），任意點P（x，y）落在橢圓上的判斷公式如下：

[x-x0cosθ+y-y0sinθ2a2+x-x0sinθ-y-y0cosθ2b2-1

以點（x0，y0）為中心選取長方形區(qū)域D，[D=x，yx-x0≤a+2且y-y0≤b+2]。取T=0.1，若點[Px，y∈D]且滿足式（6），則認(rèn)為該點落在候選橢圓上。在區(qū)域D中計算原圖中落在候選橢圓上的實際邊緣點數(shù)目N1和組成候選橢圓的邊緣點數(shù)目N2，因為組成橢圓的點數(shù)是隨著a，b變化而變化的，所以應(yīng)該以N1，N2的比值是否大于閾值λ來判斷候選橢圓是否為真，即當(dāng)[N1N2>λ]時，候選橢圓為真。

3 實驗結(jié)果

為驗證本文算法檢測結(jié)果，采用2組圖片對本文算法與CMHT算法進(jìn)行了對比檢測實驗，重點對橢圓檢測的準(zhǔn)確度和速度進(jìn)行考察。用Matlab 7.6編程實現(xiàn)了本文算法。測試平臺為普通PC機(jī)，CPU為Pentium E5300，2 GB內(nèi)存，操作系統(tǒng)為Windows XP。本文的測試程序把檢測到的橢圓用紅色和綠色畫出，分別表示用CMHT算法和本文算法檢測得到的橢圓。第1組實驗采用簡單的合成圖像如圖2所示，圖像大小為248×180，所需檢測橢圓1個。第2組實驗為真實大便鏡檢圖像的一部分如圖3所示，圖像大小為448×350，所需檢測蟲卵3個。從圖2中可以看出，對于簡單的圖像，2種方法都能正確檢測得到橢圓，CMHT算法速度稍快一些（見表1）。但對于圖3中背景復(fù)雜的大便鏡檢圖像，特別是圖中處于右下方的橢圓有明顯遮蓋的情況，CMHT算法檢測的橢圓會出現(xiàn)中心位置不準(zhǔn)等較大誤差，并且在圖像右上方出現(xiàn)誤檢，而采用本文算法仍能較快地檢測出多個橢圓，并定位準(zhǔn)確（見表2）。由此可見，本文算法在檢測精度和誤檢率上都有很大改善。

圖2 簡單圖像的檢測

圖3 真實大便鏡檢圖像的檢測

表1 2種算法對圖2處理的結(jié)果對比

4 結(jié) 語

本文提出了一種基于Hough變換的橢圓檢測改進(jìn)算法。利用對參數(shù)空間、橢圓參數(shù)計算的改進(jìn)和虛假橢圓的判斷，提高了橢圓檢測準(zhǔn)確度。由實驗結(jié)果可以看出，即使在背景復(fù)雜的圖像中，本文的改進(jìn)算法也能準(zhǔn)確快速地檢測各個橢圓的參數(shù)，運(yùn)算速度快，檢測性能好，抗干擾性強(qiáng)，具有一定的實用性。

表2 2種算法對圖3處理的結(jié)果對比

參考文獻(xiàn)

[1] HOUGH V， PAUL C. Method and means for recognizing complex patterns： US， 3069654 [P]. 1962?12?18.

[2] XU L， OJ A E. Randomized Hough transform （RHT）： Basic mechanisms， algorithms and computational complexities [J]. Computer Vision Graphic Image Process ： Image Understanding， 1993， 57（2）： 131?154.

[3] XU L， KALVIA I H， HIRVON E P， et al. Probabilistic and non?probabilistic Hough transforms ： Overview and comparisons [J]. Image and Vision Computing， 1995， 13（4）： 239?252.

[4] MCLAUGHLIN R A. Randomized hough transform： Improved ellipse detection with comparison [J]. Pattern Recognition Letters， 1998， 19（3/4）： 299?305.

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

[6] KALVIAINEN H， HIRVONEN P. An extension to the randomized Hough transform exploiting connectivity [J]. Pattern Recognition Letters， 1997（18）： 77?85.

[7] 于海濱，劉濟(jì)林.基于中心提取的RHT在橢圓檢測中的應(yīng)用[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2007，19（9）：1107?1113.

[8] 屈穩(wěn)太.基于弦中點Hough變換的橢圓檢測方法[J].浙江大學(xué)學(xué)報：工學(xué)版，2005，39（8）：1132?1196.

[9] 黎自強(qiáng)，滕弘飛.基于局部搜索的多橢圓隨機(jī)檢測算法[J].計算機(jī)工程與應(yīng)用，2006（12）：9?12.

[10] 周祥，孔曉東，曾貴華.一種新的基于Hough變換的橢圓輪廓檢測方法[J].計算機(jī)工程，2007，33（16）：166?171.endprint