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

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

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

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

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

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

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

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

2 基于圓對稱性的改進Hough變換算法

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

2.2 求解圓的半徑r

2.3 改進Hough算法檢測單個圓檢測仿真

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

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

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

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

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

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

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

2.4 MATLAB檢測成果

3 結(jié)論

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

參考文獻：

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

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

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

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

[5]葉峰，陳燦杰，賴乙宗，等.基于有序Hough變換的快速圓檢測算法[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].中國電子學(xué)會.ICEMI'2005第七屆國際電子測量與儀器學(xué)術(shù)會議論文集[C].中國電子學(xué)會，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].光電子快報：英文版，2009，5（5）：397-400.

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

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