KRA：一種雙階段精確圓檢測算法

代巍 沈云嘯 謝寧 何道聰 馬亞東

【摘 要】為解決現有隨機Hough變換（RHT）圓檢測算法存在的無效積累嚴重問題，提出一種基于k-means聚類算法和隨機Hough變換（RHT）圓檢測算法的雙階段圓檢測算法（KRA）。所提出的KRA由k-means聚類算法和RHT圓檢測算法兩部分組成。k-means聚類算法負責對邊緣點進行聚類，得到每一類邊緣點額范圍。在此基礎上，RHT圓檢測算法對區域內的點進行檢測，最終得到圓的參數。實驗表明，提出的KRA能檢測到所有圓，并且算法的聚類和檢測時間只占RHT圓檢測時間的25.2%～67.8%，即采樣積累減少25.2%～67.8%，從而證明了文章提出的算法在減少無效采樣方面的有效性。

【關鍵詞】圓檢測;感興趣區域（ROI）;k均值聚類;隨機Hough變換;小范圍隨機采樣

【中圖分類號】TP391.41 【文獻標識碼】A 【文章編號】1674-0688（2021）03-0040-03

圓檢測是計算機視覺領域的常見方向，被廣泛應用于工程實踐項目。Hough變換圓檢測 [1]是最基本的檢測方法，其原理是把曲線由圖像空間中映射到由圓的3個參數構成的參數空間，累加統計參數空間的點，最大累加值的參數即為所求圓的參數。但該算法存在很多不足之處，在參數量、計算量和內存占用方面有很大的改進空間。針對上述不足，Xu L等人 [2]提出使用隨機Hough變換做圓檢測，該方法在圖像空間中隨機選取不共線的3個特征點，映射成參數空間中的一個點，是多到一的映射，大大減少了計算量，但是在圖像復雜的情形下，由于噪聲較多，從而引入大量的無效采樣，增加迭代次數，降低檢測效率 [3]。隨后，有很多改進的算法被提出，周勇亮等人 [4]提出一種有效繼承的累計加速算法，每次成功檢測圓后不清空參數空間，在隨機Hough變換圓檢測算法上測試取得很好的速度提升，但是對于單圓和極端情況下加速效果并不明顯。Chen等人 [5]在隨機Hough變換的基礎上進行了改進，使用第4個隨機采樣點判斷是否在候選圓上，隨后再驗證圓的真偽，提高了圓的檢測速度。

除此之外，還有許多學者從不同的角度改進圓檢測算法，如在Hough變換的基礎上結合梯度信息 [6]，運用圓的幾何屬性做圓檢測 [7]及使用圖像的直方圖 [8]作為評判依據，這些措施都取得了不錯的提升。

文中提到的改進算法是基于隨機Hough變換（RHT）圓檢測算法進行，雖然大幅提高了算法檢測效率，但是仍存在漏檢及無效積累等嚴重問題。為了改善這一問題，本文提出了一種基于k-means聚類算法和隨機Hough變換圓檢測結合的新的圓檢測算法，通過結合兩種算法的優點，對采樣空間進行約束，大大減少了無效采樣并降低了圓的漏檢率。

1 傳統的隨機Hough變換圓檢測

在平面直角坐標系中，圓的標準方程如下：

其中，（a，b）為圓心坐標，r為圓的半徑，（a，b，r）為圓的3個參數，分別是圓心坐標和半徑。隨機Hough變換（RHT）圓檢測算法需要在邊緣點集合中隨機采樣3個點（x1，y1）、（x2，y2）、（x3，y3），再將隨機選取的3個點代入圓的方程中，可以得到如下方程組：

求解以上方程組可求得圓的3個參數（a，b，r），即圓心坐標和圓半徑。然后計算邊緣上的其他點到圓心的距離d，并與所得參數r進行比較，若滿足|d-r|≤δ，δ為設定的誤差閾值，則該圓為候選圓。否則，重新采樣。隨后將其他邊緣點執行相同的過程，并統計在預設誤差范圍內的邊緣點的個數，當邊緣點個數累積達到設定閾值時，確定該圓為真實圓;否則，重新采樣。重復上述步驟，直至所有的真實圓檢測完成，或者是重復次數達到最大迭代次數。

2 本文的KR圓檢測算法

本文的圓檢測算法主要分為兩個部分：一是通過k-means聚類算法對邊緣點進行聚類，得到每個圓的ROI;二是在每個圓的ROI基礎上采用隨機Hough變換算法檢測圓，從而得到多個圓的圓心和半徑。

2.1 邊緣點聚類

在工程實踐中，工程背景相對復雜，在復雜環境拍攝的圖像存在不同程度的噪聲，導致檢測過程中的計算量劇增。為了緩解上述復雜背景問題，首先對圓所在區域進行提取。通過對原始圖像進行一系列預處理，包括灰度化和中值濾波處理，減少了隨機噪聲對后期處理的影響;對濾波后的圖像進行Canny邊緣檢測，得到二值圖像，并收集所有邊緣點構造邊緣點集;對邊緣點的數據采用k-means聚類算法進行聚類，方法描述如下。

（1）在邊緣點集中隨機選取k個點作為初始聚類的簇心。

（2）分別計算每個樣本點到k個簇心的距離（本文取歐式距離），找到離該點最近的簇核心，將它歸屬到對應的簇。

（3）所有點都歸屬到簇后，邊緣點就被分為k類。之后重新計算每個簇的中心，將其定義為新的簇核心。

（4）反復迭代步驟（2）和（3），直到達到某個中止條件。

2.2 ROI分區獨立采樣

傳統的隨機Hough變換（RHT）圓檢測算法是在當前所有邊緣點中隨機采樣3個點，但是在多個圓的情況下會有大量無效采樣。為緩解以上無效采樣問題，本文提出分區采樣的方法。通過k-means聚類算法對邊緣點進行聚類，每個圓的邊緣點都有屬于本身的聚類中心，再以此聚類中心點為中心，做一個可以囊括該類所有中心點的正方形，作為該圓的ROI。采樣時，只在該類邊緣點所在的ROI區域內部采樣，大幅度提高采樣效率，減少無效采樣。具體步驟如下。

（1）以聚類算法得到的k個點作為中心，分別以該類中距離中心點最遠的點到該中心的距離為半邊長，得到該類邊緣的區域邊框，即該圓的ROI。

（2）在圓對應的ROI區域內分別隨機采樣3個邊緣點，并確保3點不共線。

（3）將采樣得到的邊緣點代入公式（5）、公式（6）、公式（7）計算圓的參數。

其中，（a，b，r）分別為圓的橫縱坐標及圓心。

2.3 真圓的判定

通過統計位于候選圓上的邊緣點數目，對候選圓進行判斷，即如果邊緣點位于該候選圓的圓心距離等于半徑，則認為邊緣點在候選圓上，否則，邊緣點不在候選圓上。

考慮到數字化誤差，應留有一個小余量，判斷邊緣點是否在候選圓上應滿足公式（8）。

其中，（xe，ye）是邊緣點坐標，（a，b）為候選圓圓心坐標。

將統計的位于候選圓上的邊緣點數目與判定為真圓的相關閾值進行對比，從而確定候選圓的真假性，若候選圓上的邊緣點數目大于等于判定閾值，則候選圓為真圓，否則，候選圓不是真圓。即

Ne≥NT 候選圓為真圓other? ?候選圓為假圓 （9）

其中，Ne為統計得到的在候選圓上的邊緣點，NT為設定的數量閾值。

3 試驗驗證與結果分析

為了驗證本文算法的檢測效果，我們采用多幅合成圖像進行測試，并與RHT圓檢測算法在檢測時間和檢測精確度上進行比較。實驗目的是通過圓檢測算法實現在對圖像中圓的精確檢測，實驗所用計算機處理器為Intel（R）Core（TM）i5-4210M CPU @2.6 GHz，8 GB RAM，運行環境為Python 3.6。

3.1 圓的ROI區域獲取

對原圖像1（a）進行灰度化和Canny邊緣檢測，得到如圖1（b）所示的邊緣圖像，采用k-means聚類算法對所有的邊緣點進行聚類處理，從而得出k個聚類中心，在此基礎上按照ROI分區獨立采樣方法獲得圓的ROI（如圖2所示）。

3.2 試驗結果對比

首先利用圓的ROI區域獲取方法獲取圓的ROI，在每個圓的ROI內分區獨立采樣，然后分別采用隨機Hough變換圓檢測算法對每個ROI進行圓檢測，使用的圖像如圖3所示，本文對圖像的檢測效果如圖4所示，算法各環節耗時見表1，與傳統的隨機Hough變換圓檢測算法對比，檢測時間見表2，算法運行時間與圓個數的關系如圖5所示。

本文算法與RHT算法在不同個數的合成標準圓的圖像上（如圖3所示）進行比較，從試驗結果可知，本文提出的KRA在總的檢測時間上比RHT略高（如圖5所示），經過實驗對比分析KRA算法的各個關鍵環節（見表1），其中前處理耗時最長，在4張測試圖像中占比分別為77.69%、69.50%、64.46%和56.27%。縱向比較前處理時間占比可以發現，隨著圓個數的增加，處理時間增加幅度很小的同時，在整個算法的占比不斷減小。從圖5可以看出，KRA的主要部分即聚類和圓檢測時間一直低于直接RHT算法的檢測時間，可以得知，KRA縮小了隨機采樣的像素空間，成功地緩解了RHT圓檢測無效積累嚴重的問題。

3.3 算法性能分析

通過以上實驗結果和實驗數據表明，本文提出的方法在多個圓同時存在的情況下具有優勢。通過對圓的ROI提取，很好地解決了由于邊緣點數量大帶來的無效采樣劇增的問題;ROI分區采樣是完全隨機采樣和約束采樣的一種折中方法，既能將所有的邊緣點分區，又能在ROI內實現局部隨機采樣，大大減少無效采樣積累，提高圓檢測速度。

4 結語

本文提出的多圓檢測算法結合了k-means和隨機Hough變換圓檢測算法的優點，既能將所有邊緣點進行ROI分區，又能在ROI內隨機采樣，提高了采樣的有效性。試驗結果證明，本文提出的方法在速度上比傳統的隨機Hough變換圓檢測算法更有優勢，尤其是在圓個數較多的情況下優勢非常明顯。但是本文算法仍然存在不足，在使用k-means聚類算法對邊緣點進行聚類時需要指定k值的大小，即圓的個數，從而一定程度上限制了算法的適應性。因此，后續還需要對算法進行改進和研究。

參 考 文 獻

[1]Smereka M，Duleba I.Circular object detection us-ing a modified Hough transform[J].International Journal of Applied Mathe matics and Computer Sc-ience，2008，18（1）：85.

[2]XU L，OJA E，KULTANEN P.A new curve detec-tion method：randomized Hough transform（RHT）[J].Pattern Recognition Letters，1990，11（5）：331-338.

[3]何奎.基于圖像處理技術的圓環零件檢測方法研究 [D].大連：大連理工大學，2017.

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

[5]Chen The-Chuan，Chung Kuo-Lian.An efficient ra-ndomized algorithm for detecting circles[J].Comp-uter Vision and Image Understanding，2001，83（2）：172-191.

[6]Kimme C，Ballard D，Sklansky J.Finding circles by an array of accumulator[J].Commun.ACM，1975，18（2）：120-122.

[7]Huang YH，Chuang KL，Yang WN，Chiu SH.Effi-cient symmetry-based screening strategy to speed up randomized circle-detection[J].Pattern Recog-nition Letters，2012，33（16）：2071-2076.

[8]Yuan B，Liu M.Power histogram for circle detect-ion on images[J].Pattern Recognition，2015，48（10）：3268-3280.