陸路+梁光明+丁建文

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

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

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

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

1.1 基于橢圓中心的投票

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

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

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

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

1.2 橢圓參數(shù)計(jì)算

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

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

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

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

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

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

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

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

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

為了更準(zhǔn)確地計(jì)算橢圓參數(shù)，可采用Hough變換結(jié)合橢圓參數(shù)方程求解。在中心點(diǎn)Oi附近尋找關(guān)于中心點(diǎn)對(duì)稱的邊緣點(diǎn)進(jìn)行采樣存入數(shù)組Vi中。對(duì)于任意橢圓，設(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變換對(duì)a，b，θ進(jìn)行量化投票統(tǒng)計(jì)，求出參數(shù)空間最大值對(duì)應(yīng)的3個(gè)參數(shù)即為候選橢圓的a，b，θ。

2.3 虛假橢圓判斷

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

圖2 簡單圖像的檢測(cè)

圖3 真實(shí)大便鏡檢圖像的檢測(cè)

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

4 結(jié) 語

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

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

參考文獻(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變換的橢圓檢測(cè)方法[J].紅外與毫米波學(xué)報(bào)，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在橢圓檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2007，19（9）：1107?1113.

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

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

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