基于圓對稱性和隨機選點改進霍夫變換圓檢測算法

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

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

關鍵詞：霍夫變換;圓檢測;MATLAB

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

1 標準Hough變換耗時分析

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

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

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

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

2.1 求取圓心坐標

2.2 求解圓的半徑r

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

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

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

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

（4）記錄圓心坐標。

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

（6）對記錄的半徑數值進行統計處理，去除極值，然后求去半徑的平均值。

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

2.4 MATLAB檢測成果

3 結論

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

參考文獻：

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

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

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

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

[5]葉峰，陳燦杰，賴乙宗，等.基于有序Hough變換的快速圓檢測算法[J].光學精密工程，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].中國電子學會.ICEMI'2005第七屆國際電子測量與儀器學術會議論文集[C].中國電子學會，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]蔣聯源.Fast detection of multi-circle with randomized Houghtransform[J].光電子快報：英文版，2009，5（5）：397-400.

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

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