基于圓對(duì)稱性和隨機(jī)選點(diǎn)改進(jìn)霍夫變換圓檢測(cè)算法

張汝祥 陳德林 季江偉 張偉昕

摘? 要：為了解決使用傳統(tǒng)Hough變換圓檢測(cè)算法存在計(jì)算量大、運(yùn)行效率低以及檢測(cè)精度不高等問題，文章提出了一種基于圓對(duì)稱性和隨機(jī)選點(diǎn)改進(jìn)Hough變換圓檢測(cè)算法。首先，根據(jù)圓對(duì)稱性特點(diǎn)，求解出圓心坐標(biāo);然后，將圓心坐標(biāo)回代入圓方程，求解出半徑。為了增強(qiáng)抗噪能力，隨機(jī)選取圓周上一定數(shù)量的邊緣點(diǎn)進(jìn)行求解，統(tǒng)計(jì)半徑值，選擇頻數(shù)最高的半徑值作為最終結(jié)果。在MATLAB環(huán)境中開展圓檢測(cè)仿真實(shí)驗(yàn)，結(jié)果表明，提出的方法可以有效地提高圓檢測(cè)精度。

關(guān)鍵詞：霍夫變換;圓檢測(cè);MATLAB

中圖分類號(hào)：TP391.4 文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號(hào)：2095-2945（2019）14-0041-03

Abstract： In order to solve the problems of large computational complexity， low running efficiency and low detection accuracy using the traditional Hough transform circle detection algorithm， an improved Hough transform circle detection algorithm based on circle symmetry and random point selection is proposed in this paper. Firstly， according to the characteristics of circle symmetry， the center coordinates are solved; then， the center coordinates are replaced into the circle equation， and the radius is solved. In order to enhance the anti-noise ability， a certain number of edge points on the circumference are randomly selected to solve， the radius value is counted， and the radius value with the highest frequency is selected as the final result. The simulation experiment of circle detection is carried out in MATLAB environment. the results show that the proposed method can effectively improve the accuracy of circle detection.

Keywords： Hough transform; circle detection; MATLAB

引言

Hough變換是圖形檢測(cè)處理中的方式之一，它通過圖像空間與參數(shù)空間的點(diǎn)-線的對(duì)偶性，從而可以將空間中的檢測(cè)問題轉(zhuǎn)換成參數(shù)空間的檢測(cè)問題。它可以有效的提取直線、曲線、圓甚至是其他任何形狀的邊緣。因?yàn)闄C(jī)器視覺有效率高、速度快、成本低可重復(fù)利用等優(yōu)點(diǎn)，廣泛應(yīng)用于各個(gè)領(lǐng)域。標(biāo)準(zhǔn)Hough變換算法及其優(yōu)化算法大量被應(yīng)用于機(jī)器視覺中。由于Hough算法的參數(shù)空間是三維空間，很多情況下運(yùn)算數(shù)據(jù)量大，占據(jù)內(nèi)存多，目前的一些改進(jìn)算法[1-5]主要是同對(duì)Hough變換進(jìn)行降維處理，但是對(duì)于小于8像素的圓很難檢測(cè)。因此本文用一種改進(jìn)的單圓檢測(cè)算法，提高了檢測(cè)效果的準(zhǔn)確率，使操作更加簡(jiǎn)單化易于實(shí)現(xiàn)。

1 標(biāo)準(zhǔn)Hough變換耗時(shí)分析

傳統(tǒng)的圓檢測(cè)算法一般是基于Hough變換[6-9]來求解的，所以標(biāo)準(zhǔn)的Hough變換算法中存在運(yùn)算量大、運(yùn)算速度慢等缺點(diǎn)，也會(huì)被引入到計(jì)算。圓的Hough變換中有圓心坐標(biāo)a、b和半徑r，存在3個(gè)未知參數(shù)，這就意味著需要對(duì)圓的所有邊緣點(diǎn)進(jìn)行三重積分，才能夠求解出一個(gè)標(biāo)準(zhǔn)的圓，Hough計(jì)算量大的問題成為制約這種算法發(fā)的瓶頸，導(dǎo)致在實(shí)際過程中Hough很難被實(shí)現(xiàn)和運(yùn)用起來[10-11]。

在笛卡爾坐標(biāo)系中，圓的方程是：對(duì)參數(shù)空間進(jìn)行量化，得到一個(gè)三維累積矩陣，用于記錄（a，b，r），當(dāng)我們?cè)跈z測(cè)圖像空間中的圓的時(shí)候，先用邊緣檢測(cè)算子，檢測(cè)出圓的邊緣信息，然后再計(jì)算邊出與邊緣上每個(gè)點(diǎn)距離是r的所有的點(diǎn)（a1，b1），然后記錄下（a1，b1，r）。改變r(jià)值的大小然后再重復(fù)進(jìn)行以上計(jì)算過程，當(dāng)計(jì)算完所有的邊緣點(diǎn)之后，對(duì)所有的數(shù)據(jù)值進(jìn)行累計(jì)排序，累計(jì)出數(shù)據(jù)最多的一組數(shù)值就認(rèn)為對(duì)應(yīng)的是圖像空間中圓的圓心。

假設(shè)有n個(gè)邊緣點(diǎn)，本文中提到的圖像n通常大于2000，所以總時(shí)間t的系數(shù)大于10到6次方。這么龐大的計(jì)算僅僅是其中的一個(gè)環(huán)節(jié)，它需要大量的運(yùn)行時(shí)間和存儲(chǔ)空間，因此需要改進(jìn)Hough轉(zhuǎn)換以提高效率。傳統(tǒng)的Hough變換是根據(jù)Hough變換的定義進(jìn)行的。雖然它有許多明顯的缺點(diǎn)，但它經(jīng)?？梢宰鳛楦倪M(jìn)算法的參考對(duì)象。

2 基于圓對(duì)稱性的改進(jìn)Hough變換算法

2.1 求取圓心坐標(biāo)

2.2 求解圓的半徑r

2.3 改進(jìn)Hough算法檢測(cè)單個(gè)圓檢測(cè)仿真

（1）圖像讀取與處理。實(shí)際中我們拍的照片是彩色的，而在運(yùn)算中需要的是二值圖像。所以我們先通過函數(shù)imfinfo（）讀取輸入的圖像，然后再通過函數(shù)edge（），將彩色圖像轉(zhuǎn)換成我們需要的二值圖像。

（2）計(jì)算中點(diǎn)值。先用水平直線從左到右進(jìn)行掃描，記錄下掃描后計(jì)算出來的中間點(diǎn)坐標(biāo)。同理，再用鉛直線從左到右進(jìn)行掃描，記錄中間值。

（3）數(shù)據(jù)處理。累積中值，找出現(xiàn)頻率最高的數(shù)據(jù)?？梢岳肕ATLAB中的tabulate（）函數(shù)，創(chuàng)建數(shù)據(jù)表記錄中間點(diǎn)，Rx=tabulate（X）;其中X表示計(jì)數(shù)器。[～，h]=max（Rx（：，2））;找出第二列中的最大值所在行（第二列是頻數(shù)）。A=Rx（h，1）;找出第一列的頻數(shù)值（表的第一列為原始數(shù)據(jù)）。

（4）記錄圓心坐標(biāo)。

（5）在圓周上隨機(jī)取一定數(shù)目點(diǎn)邊緣點(diǎn)，代會(huì)圓的方程，來求取圓的半徑值r，并進(jìn)行數(shù)據(jù)記錄。

（6）對(duì)記錄的半徑數(shù)值進(jìn)行統(tǒng)計(jì)處理，去除極值，然后求去半徑的平均值。

（7）可以使用參數(shù)法x=r·sinθ+cx;y=r·cosθ+cy;對(duì)圓進(jìn)行打印。

2.4 MATLAB檢測(cè)成果

3 結(jié)論

結(jié)合先前的研究知識(shí)，提出改進(jìn)的算法，本算法在一定程度上解決了傳統(tǒng)Hough變換存在的計(jì)算量大耗時(shí)多的缺點(diǎn)。通過MATLAB實(shí)驗(yàn)的驗(yàn)證，可以簡(jiǎn)單快捷的解決單個(gè)圓的檢測(cè)問題，雖然檢測(cè)條件比較局限，但是可以很高效的對(duì)圓進(jìn)行檢測(cè)提取，效率和精確度得到了很大的提高，在實(shí)際工業(yè)生產(chǎn)中有廣泛的應(yīng)用的價(jià)值。

參考文獻(xiàn)：

[1]王憲，趙前程，譚建平.應(yīng)用區(qū)域估計(jì)的復(fù)雜背景多圓快速定位方法[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，47（07）：2266-2272.

[2]陳珂，吳建平，李金祥，等.一維概率Hough變換的實(shí)時(shí)魯棒多圓檢測(cè)方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015，27（10）：1832-1841.

[3]蔡佳，黃攀峰，張彬.基于梯度的區(qū)域生長(zhǎng)和距離直方圖的快速圓檢測(cè)方法[J].光學(xué)學(xué)報(bào)，2015，35（03）：193-202.

[4]周勇亮，金燕，何萍，等.隨機(jī)Hough變換圓檢測(cè)累計(jì)加速算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，26（04）：574-580.

[5]葉峰，陳燦杰，賴乙宗，等.基于有序Hough變換的快速圓檢測(cè)算法[J].光學(xué)精密工程，2014，22（04）：1105-1111.

[6]Yi W， Marshall S. Circle detection using Fast Finding and Fitting（FFF）algorithm[J]. Geo-Spatial Information Science， 2000，3（1）：74-78.

[7]Ji Yu Shan Yuekang Zhang Zhi Pan Zisheng （China JiLiang University， Hangzhou 310018 China）. An Algorithm for Concentric Circles Detection Based on Least Squares and Cluster Analysis[A].中國(guó)電子學(xué)會(huì).ICEMI'2005第七屆國(guó)際電子測(cè)量與儀器學(xué)術(shù)會(huì)議論文集[C].中國(guó)電子學(xué)會(huì)，2005：4.

[8]Hanahara K， Hiyane M. A circle-detection algorithm simulating wave propagation[J]. Machine Vision and Applications， 1991，4（2）：97-111.

[9]蔣聯(lián)源.Fast detection of multi-circle with randomized Houghtransform[J].光電子快報(bào)：英文版，2009，5（5）：397-400.

[10]張翼，孫永榮，王艷，等.圓形目標(biāo)實(shí)時(shí)檢測(cè)的改進(jìn)算法研究[J].計(jì)算機(jī)與數(shù)字工程，2040（3）.

[11]浮紅霞，陳西平，毛慧珍，等.一種非Hough變換的快速圓檢測(cè)算法[J].河南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，29（4）.