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

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

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

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

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

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

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

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

1 傳統(tǒng)的隨機Hough變換圓檢測

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

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

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

2 本文的KR圓檢測算法

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

2.1 邊緣點聚類

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

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

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

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

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

2.2 ROI分區(qū)獨立采樣

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

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

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

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

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

2.3 真圓的判定

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

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

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

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

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

其中，Ne為統(tǒng)計得到的在候選圓上的邊緣點，NT為設定的數(shù)量閾值。

3 試驗驗證與結果分析

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

3.1 圓的ROI區(qū)域獲取

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

3.2 試驗結果對比

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

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

3.3 算法性能分析

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

4 結語

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

參 考 文 獻

[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]何奎.基于圖像處理技術的圓環(huán)零件檢測方法研究 [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.