一種基于中點畫圓算法的改進(jìn)Hough變換檢測圓方法

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

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

一種基于中點畫圓算法的改進(jìn)Hough變換檢測圓方法

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

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

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

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

直線、圓（圓?。┘皺E圓等平面曲線是構(gòu)成機械零件圖像的主要元素。在機械零件二維幾何特征檢測工作中，首先要進(jìn)行機械零件圖像的邊緣檢測，在獲取圖像邊緣離散點信息后，再進(jìn)行直線、圓（圓?。?、橢圓或其它平面曲線等幾何特征的檢測。其中，圓形特征檢測無疑是機械零件二維幾何特征檢測的重要內(nèi)容。

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

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

1 標(biāo)準(zhǔn)Hough變換檢測圓方法

標(biāo)準(zhǔn)Hough變換檢測圓的基本原理是[7]：設(shè)半徑為r0，圓心坐標(biāo)為(a0, b0)的圓的表達(dá)式為

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

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

圖1 標(biāo)準(zhǔn)Hough變換檢測圓方法

在參數(shù)空間中，由公式（2）可推導(dǎo)出

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

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

2 中點畫圓算法

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

圖2 中點畫圓算法

3 基于中點畫圓算法的改進(jìn)Hough變換檢測圓方法

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

圖3 基于中點畫圓算法的改進(jìn)Hough變換檢測圓方法

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

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

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

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

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

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

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

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

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

4 具體實施步驟

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

（1） 經(jīng)驗知識設(shè)定

根據(jù)待檢測機械零件圖像的實際情況和經(jīng)驗知識，預(yù)先分段指定待測圓的半徑范圍，進(jìn)行經(jīng)驗知識設(shè)定。

（2） 分段檢測閾值生成

根據(jù)實際情況，分段設(shè)置調(diào)節(jié)系數(shù)，自適應(yīng)生成各段的檢測閾值[9]。

（3） 基于中點畫圓算法對累加器進(jìn)行投票

采用中點畫圓算法對 Hough變換參數(shù)空間中相應(yīng)的累加器進(jìn)行投票，然后統(tǒng)計各累加器的累加值。

（4） 檢測出圓的幾何參數(shù)

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

檢測圓新方法的檢測結(jié)果如圖4所示。

圖4 檢測圓新方法的檢測結(jié)果

5 對比實驗

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

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

圖5 對比實驗的原始圖像

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

6 結(jié) 束 語

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

[1]朱桂英, 張瑞林. 基于Hough變換的圓檢測方法[J].計算機工程與設(shè)計, 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]蔣聯(lián)源, 蘇 勤, 祝英俊. 快速隨機Hough變換多圓檢測算法[J]. 計算機工程與應(yīng)用, 2009, 45(17)：163-166.

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

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

[6]馮新崗, 周 詮. 數(shù)字圖像中基于多尺度幾何分析的圓檢測算法[J]. 中國圖象圖形學(xué)報, 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]孫家廣, 劉 強, 陸 薇, 等. 計算機圖形學(xué)(第3版)[M]. 北京：清華大學(xué)出版社, 1999. 167-173.

[9]朱曉林. 機械零件二維幾何特征檢測技術(shù)研究及系統(tǒng)開發(fā)[D]. 福州：福州大學(xué), 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

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

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