翟永立 丁雷 裴浩東

關(guān)鍵詞： 橢圓目標(biāo); 邊緣點(diǎn)分類; 檢測方法; 輪廓提取; 隨機(jī)Hough變換; 采樣次數(shù)

中圖分類號(hào)： TN911.23?34; TP391.9 ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2019）06?0034?04

Abstract： The characteristic of the elliptical object on the imaging plane is analyzed， and a Hough transform ellipse detection method based on improved contour extraction is proposed， which can effectively extract the outline of the ellipse in the image. The edge points of images are classified after edge detection， so as to remove cross points and isolated points， and save endpoints. The non?closed contour in the image is extracted according to the endpoints. The remaining closed contour is extracted by scanning images. In allusion to the random Hough transform， the times of sampling and calculation are determined for the contour according to the length of each contour. A threshold value is set to judge the statistical value of each group of elliptic parameters inside each loop， so as to jump out of the loop. The experimental results show that the memory consumption and calculation amount of the algorithm are greatly reduced in comparison with the ordinary random Hough transform.

Keywords： elliptical object; edge point classification; detection method; contour extraction; random Hough transform; sampling times

0 ?引 ?言

橢圓形物體在現(xiàn)實(shí)生活中大量存在，隨著計(jì)算機(jī)視覺技術(shù)的發(fā)展，人們需要計(jì)算機(jī)從圖像中確定橢圓的位置和形狀大小，如自動(dòng)化生產(chǎn)線上圓形物體的檢測、目標(biāo)上面的圓形或者橢圓特征的識(shí)別等。并且橢圓檢測是圖像處理研究中的一項(xiàng)基礎(chǔ)任務(wù)，它在模式識(shí)別和機(jī)器視覺等領(lǐng)域內(nèi)有著廣泛的應(yīng)用。

近年來，研究人員提出了大量的橢圓檢測方法，如最小二乘擬合算法[1?3]、基于Hough變換擬合算法[4?6]、基于幾何特征的擬合方法[7?8]等。最小二乘擬合原理簡單，但是對(duì)噪聲和孤立點(diǎn)存在較差的魯棒性，擬合結(jié)果誤差較大。隨機(jī)Hough變換[9]采用參數(shù)空間多對(duì)一映射，降低了計(jì)算復(fù)雜度和內(nèi)存占用量，但大量隨機(jī)采樣和累計(jì)問題嚴(yán)重影響了RHT的性能?；趲缀翁卣鞯臄M合方法是利用橢圓本身的幾何特征，如弦中點(diǎn)、橢圓極和極弦性質(zhì)[10]和點(diǎn)與切線方向[11]等進(jìn)行橢圓擬合，但是由于噪聲等的影響，梯度的計(jì)算值與方向受到很大的影響，所以大大影響了計(jì)算的精度。

本文采用基于隨機(jī)Hough變換的橢圓擬合方法，首先改進(jìn)常規(guī)的輪廓提取方法，然后采用隨機(jī)Hough變換進(jìn)行橢圓檢測，并對(duì)Hough變換進(jìn)行一定的優(yōu)化，降低計(jì)算量。該方法的時(shí)間空間消耗都較小，有一定的實(shí)用價(jià)值。

2.1 ?改進(jìn)的輪廓提取方法

常用的輪廓提取方法是根據(jù)輪廓點(diǎn)間8?鄰接性質(zhì)對(duì)細(xì)化圖像中的輪廓像素點(diǎn)進(jìn)行跟蹤提取，跟蹤采用逐行掃描的方法。但是該方法會(huì)把交叉輪廓認(rèn)為是同一個(gè)輪廓。

針對(duì)這一點(diǎn)，本文對(duì)此方法進(jìn)行改進(jìn)，首先進(jìn)行邊緣點(diǎn)的分類，如圖3所示，去除孤立點(diǎn)和交叉點(diǎn);然后再次去除因?yàn)榻徊纥c(diǎn)造成的孤立點(diǎn)，并提取端點(diǎn)坐標(biāo);最后先根據(jù)端點(diǎn)坐標(biāo)提取非封閉的輪廓邊緣，根據(jù)輪廓的長度，去除較短的輪廓，再掃描整幅圖像，提取封閉的輪廓邊緣并置零。至此，圖像中的輪廓提取完畢，避免了交叉輪廓分類為同一個(gè)輪廓。

2.2 ?改進(jìn)的隨機(jī)Hough變換檢測方法

隨機(jī)Hough變換檢測橢圓的基本思想是采用多對(duì)一的映射關(guān)系，主要通過隨機(jī)采樣和動(dòng)態(tài)鏈表存儲(chǔ)，隨機(jī)選取5個(gè)點(diǎn)計(jì)算橢圓的參數(shù)，對(duì)計(jì)算所得的參數(shù)進(jìn)行累加，減少了使用傳統(tǒng)Hough變換所需要的計(jì)算量和占用的內(nèi)存。但是，RHT的無目標(biāo)采樣會(huì)引入大量的無效累積，浪費(fèi)大量的計(jì)算時(shí)間和存儲(chǔ)空間。

2.2.1 ?隨機(jī)采樣總次數(shù)[Ncy]的確定

傳統(tǒng)的隨機(jī)Hough變換的每個(gè)輪廓的采樣次數(shù)都是采用一個(gè)統(tǒng)一的固定值，這樣就造成不管輪廓的長短，都要進(jìn)行同樣的采樣次數(shù)，這就產(chǎn)生了大量的冗余計(jì)算。本文算法在循環(huán)外部控制每個(gè)輪廓上進(jìn)行隨機(jī)采樣的總次數(shù)，根據(jù)輪廓的長度進(jìn)行自適應(yīng)的調(diào)節(jié)采樣次數(shù)，設(shè)第i個(gè)輪廓長度為[Li]，取采樣次數(shù)為[Lin]，[n]為調(diào)節(jié)參數(shù)，根據(jù)輪廓的長短在1～4內(nèi)變化。通過該方法節(jié)省了程序的運(yùn)行時(shí)間。

2.2.2 ?循環(huán)內(nèi)部采樣次數(shù)的確定

隨機(jī)Hough變換在計(jì)算每個(gè)輪廓的參數(shù)時(shí)，需要進(jìn)行固定次數(shù)的采樣計(jì)算，然后對(duì)參數(shù)存儲(chǔ)數(shù)組進(jìn)行統(tǒng)計(jì)次數(shù)的比較，數(shù)組中統(tǒng)計(jì)次數(shù)最大的參數(shù)對(duì)應(yīng)的橢圓就是該輪廓的橢圓表達(dá)式參數(shù)。

在對(duì)每一個(gè)輪廓進(jìn)行參數(shù)計(jì)算的循環(huán)內(nèi)部，本文設(shè)計(jì)一個(gè)閾值[Tc]，當(dāng)統(tǒng)計(jì)數(shù)值不小于該閾值時(shí)，就認(rèn)為該統(tǒng)計(jì)值對(duì)應(yīng)的橢圓參數(shù)就是輪廓的橢圓參數(shù)保存橢圓參數(shù)，并跳出該循環(huán)。根據(jù)輪廓的長短，[Tc]可取8～30。通過此方法可以大大減少橢圓檢測所占用的時(shí)間與內(nèi)存。

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

為了驗(yàn)證本文算法的有效性，在PC上對(duì)圖像進(jìn)行處理，該算法利用Matlab 2016平臺(tái)編程實(shí)現(xiàn)。首先采用人工合成圖像，對(duì)普通輪廓提取算法和本文所用輪廓算法的效果進(jìn)行對(duì)比，如圖4所示。

由圖4a）、圖4b）對(duì)比可以看出，本文算法能準(zhǔn)確地區(qū)分出每一個(gè)物體的輪廓，而普通輪廓提取方法并不能很好地把重疊物體的輪廓分離開來。這是由于本文算法在提取輪廓時(shí)利用像素的鄰域信息，判斷出交叉點(diǎn)并進(jìn)行分離，這樣在提取時(shí)就可防止重疊物體輪廓被認(rèn)為是一個(gè)物體的輪廓。

為了對(duì)比算法檢測橢圓的效果，對(duì)一張246×300大小的硬幣圖，分別使用本文算法、基于輪廓的隨機(jī)Hough變換算法和最小二乘方法進(jìn)行橢圓檢測，效果如圖5所示。

檢測算法運(yùn)行時(shí)間對(duì)比如表1所示。

對(duì)比圖5的4張圖和表1可以看出，三種方法都可以檢測出硬幣的輪廓。最小二乘法會(huì)檢測出虛假的橢圓，這是因?yàn)樽钚《朔ǖ目乖肼暷芰^弱，容易受到其他點(diǎn)的影響。本文算法與隨機(jī)Hough變換的檢測效果在直觀上看均能準(zhǔn)確地檢測出所有輪廓，但是從運(yùn)行時(shí)間上看，隨機(jī)Hough變換的運(yùn)行時(shí)間要多于本文算法，這是由于隨機(jī)Hough在計(jì)算每條輪廓時(shí)都要進(jìn)行固定次數(shù)的采樣，進(jìn)行大量的冗余計(jì)算。而本文算法首先根據(jù)每條輪廓的長度來確定該條輪廓的采樣次數(shù)，然后在每個(gè)循環(huán)內(nèi)部，對(duì)每個(gè)參數(shù)出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，大于一定閾值時(shí)就認(rèn)為找到該輪廓橢圓參數(shù)，結(jié)束該循環(huán)，因此減少了許多的冗余計(jì)算和內(nèi)存占用。

使用人工合成的圖像來檢驗(yàn)前兩種方法的精確性，對(duì)同一個(gè)橢圓進(jìn)行檢測，對(duì)比連續(xù)20次橢圓中心的定位誤差。根據(jù)圖6可以看出兩種方法對(duì)于同一個(gè)橢圓定位的誤差，相差不大，都能夠較準(zhǔn)確地檢測出橢圓參數(shù)。

4 ?結(jié) ?論

為了實(shí)現(xiàn)對(duì)光電圖像中的橢圓形目標(biāo)的快速檢測，本文研究了Hough變換、最小二乘法等橢圓檢測方法。為了提高檢測速度，本文提出一種基于改進(jìn)輪廓提取的隨機(jī)Hough檢測算法。先對(duì)常規(guī)輪廓提取算法進(jìn)行改進(jìn)，能夠?qū)崿F(xiàn)交叉輪廓的分離，避免把交叉輪廓提取為同一個(gè)輪廓;然后改進(jìn)隨機(jī)Hough變換，減少計(jì)算過程中的冗余采樣，縮減運(yùn)行時(shí)間和內(nèi)存空間。采集圖像數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證，結(jié)果表明，此方法可以很大程度上降低計(jì)算量，可實(shí)現(xiàn)對(duì)圖像中橢圓的快速檢測。

參考文獻(xiàn)

[1] 熊風(fēng)光，李希，韓燮.基于整體最小二乘的橢圓擬合方法[J].微電子學(xué)與計(jì)算機(jī)，2017，34（1）：102?105.

XIONG Fengguang， LI Xi， HAN Xie. A method of ellipse fitting based on total least squares [J]. Microelectronics & computer， 2017， 34（1）： 102?105.

[2] BEKTAS S. Least squares fitting of ellipsoid using orthogonal distances [J]. Boletim de ciências geodésicas， 2015， 21（2）： 329?339.

[3] 何志強(qiáng)，曹彪，張立新.基于改進(jìn)最小二乘的缺陷橢圓定位方法[J].計(jì)算機(jī)與數(shù)字工程，2017，45（11）：2113?2117.

HE Zhiqiang， CAO Biao， ZHANG Lixin. A defect ellipse locating method based on least squares [J]. Computer and digital engineering， 2017， 45（11）： 2113?2117.

[4] 陸路.基于Hough變換的醫(yī)學(xué)顯微細(xì)胞檢測技術(shù)研究[D].湘潭：湘潭大學(xué)，2015.

LU Lu. Research on the detection technology of medical microscopic cell based on Hough transform [D]. Xiangtan： Xiangtan University， 2015.

[5] 陳余根，楊艷.基于霍夫變換橢圓檢測的兩種改進(jìn)算法[J].半導(dǎo)體光電，2017，38（5）：745?750.

CHEN Yugen， YANG Yan. Two improved algorithms for ellipse detection based on Hough transform [J]. Semiconductor optoelectronics， 2017， 38（5）： 745?750.

[6] 邵剛，屈保平，曹鵬，等.基于Hough變換的攝像機(jī)跟蹤系統(tǒng)設(shè)計(jì)[J].測控技術(shù)，2013，32（8）：32?35.

SHAO Gang， QU Baoping， CAO Peng， et al. Design of camera tracking system based on Hough transform [J]. Measurement & control technology， 2013， 32（8）： 32?35.

[7] 李艷荻，徐熙平，鐘巖.特征弦約束隨機(jī)Hough變換在橢圓檢測中的應(yīng)用[J].儀器儀表學(xué)報(bào)，2017，38（1）：50?56.

LI Yandi， XU Xiping， ZHONG Yan. Application of RHT based on character string constraint in ellipse detection [J]. Chinese journal of scientific instrument， 2017， 38（1）： 50?56.

[8] 高煜妤，王春芳.基于歐氏距離圖的隨機(jī)Hough變換橢圓檢測方法[J].現(xiàn)代電子技術(shù)，2016，39（21）：61?64.

GAO Yuyu， WANG Chunfang. Ellipse detection method based on random Hough transform and Euclidean distance graph [J]. Modern electronics technique， 2016， 39（21）： 61?64.

[9] MUKHOPADHYAY P， CHAUDHURI B B. A survey of Hough transform [J]. Pattern recognition， 2015， 48（3）： 993?1010.

[10] KWON B K， ZHU T， ROH T J. Fast ellipse detection based on three point algorithm with edge angle information [J]. International journal of control， automation and systems， 2016， 14（3）： 804?813.

[11] 宦海，黃凌霄，張雨，等.基于最大內(nèi)切圓的橢圓孔組檢測[J].計(jì)算機(jī)應(yīng)用，2015，35（4）：1101?1105.

HUAN Hai， HUANG Lingxiao， ZHANG Yu， et al. Detection of ellipse hole group based on maximum inscribed circle [J]. Journal of computer applications， 2015， 35（4）： 1101?1105.