一種基于中點畫圓算法的改進Hough變換檢測圓方法

朱曉林， 高誠輝， 何炳蔚， 黃敏純， 陳 杰

（1. 福州大學機械工程及自動化學院，福建 福州 350108，2. 福建省制造業數字化設計工程研究中心，福建 福州 350002）

一種基于中點畫圓算法的改進Hough變換檢測圓方法

朱曉林1,2， 高誠輝1,2， 何炳蔚1,2， 黃敏純1， 陳 杰1

（1. 福州大學機械工程及自動化學院，福建 福州 350108，2. 福建省制造業數字化設計工程研究中心，福建 福州 350002）

為了對機械零件圖像中的圓形幾何特征進行視覺檢測，將中點畫圓算法與Hough變換相結合，提出一種基于中點畫圓算法的 Hough變換檢測圓的新方法，并對中點畫圓算法中的浮點運算等方面進行了改進。給出了該新方法的具體實施步驟和檢測結果，表明了該方法的可行性。最后，通過對比實驗驗證了該方法的有效性。

工程圖學；中點畫圓算法；Hough變換；圓檢測；累加器投票

直線、圓（圓弧）及橢圓等平面曲線是構成機械零件圖像的主要元素。在機械零件二維幾何特征檢測工作中，首先要進行機械零件圖像的邊緣檢測，在獲取圖像邊緣離散點信息后，再進行直線、圓（圓弧）、橢圓或其它平面曲線等幾何特征的檢測。其中，圓形特征檢測無疑是機械零件二維幾何特征檢測的重要內容。

Hough變換是目前應用較為廣泛的圓檢測方法，該方法最大特點是可靠性高，在噪聲、變形、甚至部分區域丟失的狀態下仍能取得理想的結果[1]，但直接采用Hough變換檢測圓，存在需要頻繁地進行開平方或三角運算等缺陷，計算量比較大。目前，Hough變換已發展出幾種改進方法，如隨機Hough變換、梯度Hough變換等，但仍存在會產生大量無效累積、數字化量化誤差大等問題[2-6]。

中點畫圓算法是一種高效的畫圓算法，但目前只用于畫圓方面的研究，尚未見到用于Hough變換檢測圓的研究。本文將中點畫圓算法與Hough變換相結合，提出一種基于中點畫圓算法的改進Hough變換檢測圓的新方法。該新方法具有運算速度快，占用內存小，檢測結果準確等特點，可用于對自動生產線上被加工機械零件的圓形幾何特征進行實時在線檢測，確保零件的加工質量。

1 標準Hough變換檢測圓方法

標準Hough變換檢測圓的基本原理是[7]：設半徑為r0，圓心坐標為(a0, b0)的圓的表達式為

對于原圖像中的每一點(xi, yi)，在參數空間中對應一個三維直立圓錐，其表達式為

其中 a、b、r為參數空間中的3個變量。對于圖像空間中的半徑為r0，圓心坐標為(a0, b0)的圓上的點集，在參數空間中對應一簇三維圓錐面，它們交于一點(a0, b0, r0)，如圖1所示。

圖1 標準Hough變換檢測圓方法

在參數空間中，由公式（2）可推導出

對給定的 r0，由公式（3）可確定出一組(ai0,bi0)值，將(ai0, bi0)值投票到r0層的累加器上；對給定的 r1，由公式（3）又可確定出另一組(ai1, bi1)值，將(ai1, bi1)值投票到r1層的累加器上；依此類推，可得到三維累加陣列(aij, bij, rj)。通過三維累加計算，得到最大累加值對應的坐標(a0, b0, r0)，即得到被檢測圓的3個參數，實現標準Hough變換檢測圓。

由于采用標準 Hough變換檢測圓需要頻繁地進行開平方運算，其計算量相當大，占用的存儲空間也非常大。因此，在實時在線檢測中用標準Hough變換檢測圓幾乎是不可能的。

2 中點畫圓算法

中點畫圓算法的基本思想是[8]：確定起始點P，根據中點M構造函數判別式，計算出下一像素點 P1（如圖 2(a)所示）；依次每步單位間隔取樣，順時針確定出最佳逼近于該圓弧的像素序列（如圖 2(b)所示）；考慮到圓的對稱性，只需計算 1/8圓弧的數據（如圖 2(c)所示），從而大大減少運算量。

圖2 中點畫圓算法

3 基于中點畫圓算法的改進Hough變換檢測圓方法

將中點畫圓算法與 Hough變換檢測圓方法相結合，提出一種基于中點畫圓算法的改進Hough變換檢測圓方法，其基本思想如下：設待測圓的半徑為r0，對于實時在線檢測獲得的機械零件圖像每一個邊緣點(xi, yi)（如圖3(a)所示），以(xi, yi)為圓心、r0為半徑，在Hough變換參數空間的累加器陣列中，采用中點畫圓算法對相應的累加器進行投票（如圖 3(b)所示），然后檢測各累加器的累加值，當某個累加器的值達到檢測閾值時（如圖 3(c)所示），即可確定出機械零件圖像上的一個以(ai, bi)為圓心，r0為半徑的圓。

圖3 基于中點畫圓算法的改進Hough變換檢測圓方法

對于給定的半徑R，在參數空間的累加器陣列中，設當前累加器為P(xp, yp)（如圖3(b)所示），為判別下一累加器為 P1還是P2，構造判別函數F(x, y)= x2+ y2- R2。對于參數空間中的圓上的點，F(x, y)= 0；對于圓外的點，F(x, y)> 0；而對于圓內的點，F(x, y)< 0。

假設M是P1和P2的中點，即M =(xp+ 1, yp-0.5)。構造M的判別式

若d1< 0，M在圓內，說明P1距離圓弧更近，應取 P1為下一累加器。再下一個累加器的判別式為

因此，在已知1P后，即可根據dΔ方便地確定出下一個累加器。

若10d≥ ，M在圓外（或圓上），說明2P距離圓弧更近，應取2P為下一個累加器。再下一個累加器的判別式為令右下方向的增量因此，在已知2P后，即可根據 d′Δ 方便地確定出下一個累加器。

對比公式（3）～公式（5）可以看出：公式（3）要進行開平方運算，其運算量大，而公式（4）、公式（5）只需進行簡單的加減運算，運算量小，運算速度快。

為了進一步提高檢測速度和準確性，使該方法能更好地適用于機械零件圓形幾何特征的實時在線檢測，對檢測圓的方法做以下改進。

如圖2(b)所示，要生成第二個8分圓，按順時針方向，起始點為(0,)R，判別式d的初始值為

因在計算判別式d的過程中會出現大量浮點運算，存在運算量大、計算結果精度低等缺點。為了克服浮點運算方法的不足之處，本文提出采用整數運算代替浮點運算，即將判別式d的初始值放大 4倍改為 5-4R，則下一個累加器的判別式增量dΔ變為8xp+12或8(xp-yp)+20，從而進一步提高檢測速度和精度。

4 具體實施步驟

基于中點畫圓算法的改進 Hough變換檢測圓方法的具體實施步驟如下：

（1） 經驗知識設定

根據待檢測機械零件圖像的實際情況和經驗知識，預先分段指定待測圓的半徑范圍，進行經驗知識設定。

（2） 分段檢測閾值生成

根據實際情況，分段設置調節系數，自適應生成各段的檢測閾值[9]。

（3） 基于中點畫圓算法對累加器進行投票

采用中點畫圓算法對 Hough變換參數空間中相應的累加器進行投票，然后統計各累加器的累加值。

（4） 檢測出圓的幾何參數

比較累加值與檢測閾值，確定出被測圓，然后得到圓心坐標、圓的半徑等幾何參數。

檢測圓新方法的檢測結果如圖4所示。

圖4 檢測圓新方法的檢測結果

5 對比實驗

在相同檢測閾值的情況下，分別采用本文提出的檢測圓的新方法、標準Hough變換檢測圓和隨機Hough變換檢測圓這三種方法，在給定的半徑范圍內，對圖5中的圓形特征進行檢測，獲取圓的幾何參數，并求得各自的平均運算時間。圖5中的圓形幾何特征的原始值分別為：圓心坐標(65, 150)、(60, 65)及(121, 97)，對應半徑 19、33及 47pixels。對比實驗采用的計算機配置為：Pentium? 4 CPU 2.80GHz，2GB內存，NVIDIA GeForce 4 MX 440圖形加速卡，64MB顯存。其對比實驗結果如表1所示。

表1 三種檢測圓方法的對比實驗結果

圖5 對比實驗的原始圖像

通過上述實驗可以看出，檢測圓的新方法能有效地檢測出目標圓，檢測結果準確，其檢測速度要比標準Hough變換檢測圓快一個數量級，也比隨機Hough變換檢測圓略勝一籌。

6 結 束 語

針對標準Hough變換計算復雜、運算量大，隨機 Hough變換會造成參數單元的大量無效累積等缺點，將中點畫圓算法與 Hough變換相結合，提出了一種基于中點畫圓算法改進的Hough變換檢測圓新方法，并避免了浮點運算。通過實驗表明，本文提出的檢測圓的新方法具有運算速度快，占用內存小，檢測結果準確等特點，適合于被加工機械零件的實時在線檢測。由于該方法在初始化設置時還需人工干預，影響了其自動化檢測水平，今后還需在提高通用性、智能化等方面進行進一步研究。

[1]朱桂英, 張瑞林. 基于Hough變換的圓檢測方法[J].計算機工程與設計, 2008, 29(6)：1462-1464.

[2]XU L, OJA E, Kultanen P. Randomized hough transform (RTH)：basic mechanisms, algorithms, and computational complexities [J]. Computer Vision Graphics Image Process：Image Understanding, 1993,57(2)：131-154.

[3]蔣聯源, 蘇 勤, 祝英俊. 快速隨機Hough變換多圓檢測算法[J]. 計算機工程與應用, 2009, 45(17)：163-166.

[4]趙桂霞, 黃 山. 一種基于隨機Hough變換圓檢測的改進算法[J]. 計算機技術與發展, 2008, 18(4)：77-79.

[5]瞿 鈞, 甘 嵐. 梯度Hough變換在圓檢測中的應用[J]. 華東交通大學學報, 2007, 24(1)：101-104.

[6]馮新崗, 周 詮. 數字圖像中基于多尺度幾何分析的圓檢測算法[J]. 中國圖象圖形學報, 2009, 14(5)：957-960.

[7]HOUGH P V C．A method and means of recognizing complex patterns [P]. U.S. ：3069645, 1962-12-18.

[8]孫家廣, 劉 強, 陸 薇, 等. 計算機圖形學(第3版)[M]. 北京：清華大學出版社, 1999. 167-173.

[9]朱曉林. 機械零件二維幾何特征檢測技術研究及系統開發[D]. 福州：福州大學, 2009.

An Improved Method of Hough Transform Circle Detection Based on the Midpoint Circle-Producing Algorithm

ZHU Xiao-lin1,2, GAO Cheng-hui1,2, HE Bing-wei1,2, HUANG Min-chun1, CHEN Jie1
( 1. College of Mechanical Engineering and Automation, Fuzhou University, Fuzhou Fujian 350108, China;2. Fujian Provincial Research Center of Digital Design for Manufacturing, Fuzhou Fujian 350002, China)

To conduct vision detection to the circle’s geometric feature of the machine parts’images, a new circle detection method is put forward by joining the midpoint circle-producing algorithm and Hough transform, which improves the floating calculating of the midpoint circle-producing algorithm and other. The detailed implementation steps are given and the detection results show that the new method is feasible. Finally, the experimental comparison indicates that the proposed method is effective.

engineering graphics; midpoint circle-producing algorithm; Hough transform;circle detection, accumulator voting

TH 164

A

1003-0158(2010)06-0029-05

2010-04-01

國家自然科學基金資助項目（50605007）；福州市科技計劃資助項目（2009-G-115）；福州大學資助項目（2009-8）

朱曉林（1976-），男，福建福州人，高級程序員，實驗師，碩士，主要研究方向為機器視覺。