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

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

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

中圖分類號： TN911.73?34； TP391.41 文獻(xiàn)標(biāo)識碼： 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 引 言

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

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

1 隨機Hough變換原理

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

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

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

2 改進(jìn)的Hough變換檢測橢圓

2.1 旋轉(zhuǎn)角度的檢測

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

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

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

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

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

2.2 其他參數(shù)的求取

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

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

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

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

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

[d=vNi-vNj22] （3）

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

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

2.4 算法步驟

算法的實現(xiàn)步驟如下：

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

圖6 實際圖像實驗結(jié)果圖

4 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

[5] 屈穩(wěn)太.基于弦中點Hough變換的橢圓檢測方法[J].浙江大學(xué)學(xué)報（工學(xué)版），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].計算機應(yīng)用，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].中國圖象圖形學(xué)報，2013，18（2）：176?183.