朱曉林， 高誠(chéng)輝， 何炳蔚， 黃敏純， 陳 杰

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

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

朱曉林1,2， 高誠(chéng)輝1,2， 何炳蔚1,2， 黃敏純1， 陳 杰1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 中點(diǎn)畫圓算法

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

圖2 中點(diǎn)畫圓算法

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

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

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

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

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

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

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

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

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

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

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

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

4 具體實(shí)施步驟

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

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

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

（2） 分段檢測(cè)閾值生成

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

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

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

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

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

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

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

5 對(duì)比實(shí)驗(yàn)

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

表1 三種檢測(cè)圓方法的對(duì)比實(shí)驗(yàn)結(jié)果

圖5 對(duì)比實(shí)驗(yàn)的原始圖像

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

6 結(jié) 束 語(yǔ)

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

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

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

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

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

[9]朱曉林. 機(jī)械零件二維幾何特征檢測(cè)技術(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

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

朱曉林（1976-），男，福建福州人，高級(jí)程序員，實(shí)驗(yàn)師，碩士，主要研究方向?yàn)闄C(jī)器視覺。