基于改進輪廓提取的Hough變換橢圓檢測方法

翟永立 丁雷 裴浩東

關鍵詞： 橢圓目標; 邊緣點分類; 檢測方法; 輪廓提取; 隨機Hough變換; 采樣次數

中圖分類號： TN911.23?34; TP391.9 ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? 文章編號： 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 ?引 ?言

橢圓形物體在現實生活中大量存在，隨著計算機視覺技術的發展，人們需要計算機從圖像中確定橢圓的位置和形狀大小，如自動化生產線上圓形物體的檢測、目標上面的圓形或者橢圓特征的識別等。并且橢圓檢測是圖像處理研究中的一項基礎任務，它在模式識別和機器視覺等領域內有著廣泛的應用。

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

本文采用基于隨機Hough變換的橢圓擬合方法，首先改進常規的輪廓提取方法，然后采用隨機Hough變換進行橢圓檢測，并對Hough變換進行一定的優化，降低計算量。該方法的時間空間消耗都較小，有一定的實用價值。

2.1 ?改進的輪廓提取方法

常用的輪廓提取方法是根據輪廓點間8?鄰接性質對細化圖像中的輪廓像素點進行跟蹤提取，跟蹤采用逐行掃描的方法。但是該方法會把交叉輪廓認為是同一個輪廓。

針對這一點，本文對此方法進行改進，首先進行邊緣點的分類，如圖3所示，去除孤立點和交叉點;然后再次去除因為交叉點造成的孤立點，并提取端點坐標;最后先根據端點坐標提取非封閉的輪廓邊緣，根據輪廓的長度，去除較短的輪廓，再掃描整幅圖像，提取封閉的輪廓邊緣并置零。至此，圖像中的輪廓提取完畢，避免了交叉輪廓分類為同一個輪廓。

2.2 ?改進的隨機Hough變換檢測方法

隨機Hough變換檢測橢圓的基本思想是采用多對一的映射關系，主要通過隨機采樣和動態鏈表存儲，隨機選取5個點計算橢圓的參數，對計算所得的參數進行累加，減少了使用傳統Hough變換所需要的計算量和占用的內存。但是，RHT的無目標采樣會引入大量的無效累積，浪費大量的計算時間和存儲空間。

2.2.1 ?隨機采樣總次數[Ncy]的確定

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

2.2.2 ?循環內部采樣次數的確定

隨機Hough變換在計算每個輪廓的參數時，需要進行固定次數的采樣計算，然后對參數存儲數組進行統計次數的比較，數組中統計次數最大的參數對應的橢圓就是該輪廓的橢圓表達式參數。

在對每一個輪廓進行參數計算的循環內部，本文設計一個閾值[Tc]，當統計數值不小于該閾值時，就認為該統計值對應的橢圓參數就是輪廓的橢圓參數保存橢圓參數，并跳出該循環。根據輪廓的長短，[Tc]可取8～30。通過此方法可以大大減少橢圓檢測所占用的時間與內存。

3 ?實驗結果分析

為了驗證本文算法的有效性，在PC上對圖像進行處理，該算法利用Matlab 2016平臺編程實現。首先采用人工合成圖像，對普通輪廓提取算法和本文所用輪廓算法的效果進行對比，如圖4所示。

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

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

檢測算法運行時間對比如表1所示。

對比圖5的4張圖和表1可以看出，三種方法都可以檢測出硬幣的輪廓。最小二乘法會檢測出虛假的橢圓，這是因為最小二乘法的抗噪聲能力較弱，容易受到其他點的影響。本文算法與隨機Hough變換的檢測效果在直觀上看均能準確地檢測出所有輪廓，但是從運行時間上看，隨機Hough變換的運行時間要多于本文算法，這是由于隨機Hough在計算每條輪廓時都要進行固定次數的采樣，進行大量的冗余計算。而本文算法首先根據每條輪廓的長度來確定該條輪廓的采樣次數，然后在每個循環內部，對每個參數出現的次數進行統計，大于一定閾值時就認為找到該輪廓橢圓參數，結束該循環，因此減少了許多的冗余計算和內存占用。

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

4 ?結 ?論

為了實現對光電圖像中的橢圓形目標的快速檢測，本文研究了Hough變換、最小二乘法等橢圓檢測方法。為了提高檢測速度，本文提出一種基于改進輪廓提取的隨機Hough檢測算法。先對常規輪廓提取算法進行改進，能夠實現交叉輪廓的分離，避免把交叉輪廓提取為同一個輪廓;然后改進隨機Hough變換，減少計算過程中的冗余采樣，縮減運行時間和內存空間。采集圖像數據對算法進行驗證，結果表明，此方法可以很大程度上降低計算量，可實現對圖像中橢圓的快速檢測。

參考文獻

[1] 熊風光，李希，韓燮.基于整體最小二乘的橢圓擬合方法[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] 何志強，曹彪，張立新.基于改進最小二乘的缺陷橢圓定位方法[J].計算機與數字工程，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變換的醫學顯微細胞檢測技術研究[D].湘潭：湘潭大學，2015.

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

[5] 陳余根，楊艷.基于霍夫變換橢圓檢測的兩種改進算法[J].半導體光電，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].測控技術，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] 李艷荻，徐熙平，鐘巖.特征弦約束隨機Hough變換在橢圓檢測中的應用[J].儀器儀表學報，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] 高煜妤，王春芳.基于歐氏距離圖的隨機Hough變換橢圓檢測方法[J].現代電子技術，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] 宦海，黃凌霄，張雨，等.基于最大內切圓的橢圓孔組檢測[J].計算機應用，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.