基于Hough變換實(shí)現(xiàn)圓的快速檢測方法

0 引言

圖像處理中對圓進(jìn)行檢測及確定其參數(shù)是圖像特征檢測和模式識別中的一項重要任務(wù)，在生物信息識別、產(chǎn)品檢測、集成電路板在線質(zhì)量檢測等眾多領(lǐng)域中，通常需要對圖像中的圓形圖案進(jìn)行檢測，以便識別和定位目標(biāo)。常用的圓檢測方法有Hough變換檢測圓方法、形狀分析法、BP網(wǎng)絡(luò)分類器方法、基于圓度的計算方法等。目前，Hough變換圓檢測（HTCD）方法[1]在噪聲、曲線間斷，邊緣不完整地情況下，仍能夠可靠的提取出圓的特征信息，成為常用的圓檢測方法，Xu等提出了隨機(jī)Hough變換圓檢測方法（RHT）[2]，該方法在圖像空間中隨機(jī)選取不共線的三個特征點(diǎn)，映射成參數(shù)空間中一個點(diǎn)，是多到一的映射，大大減少了計算量，但是在處理帶有一定噪聲且復(fù)雜度較高圖像時，由于隨機(jī)采樣的無效點(diǎn)太多，造成了大量的無效累積。Chen等提出隨機(jī)圓檢測方法（RCD）[3]，RCD是針對圖像的所有邊緣點(diǎn)直接檢測，不涉及到空間參數(shù)的累積等，提高了計算檢測速度，減少了累積內(nèi)存空間，但是當(dāng)干擾像素點(diǎn)太多時，需要檢測的樣本數(shù)太多，計算量會大大增加，導(dǎo)致檢測速度下降，計算不穩(wěn)定。Shih-HsuanChiu提出了一種標(biāo)準(zhǔn)Hough變換圓檢測的投票方法，減少了計算量和存儲空間[4]。W.C.Y. Lam等提出了具有直角特性的點(diǎn)三元組檢測方案，方案基于Hough變換將計算空間由三維降到了二維，有一定的抗噪能力，但在二維空間計算復(fù)雜度仍然很高[5]。林金龍等提出了用點(diǎn)Hough變換檢測圓，根據(jù)同一圓上任意兩條弦的中垂線相交于圓心的性質(zhì)，將搜索空間由三維降到一維，降低了計算復(fù)雜度和對資源的需求[6]，但檢測精度仍然不高。

為了解決上述算法出現(xiàn)檢測精度不高，計算復(fù)雜，占用內(nèi)存多，不能滿足速度要求的缺陷，本文在Hough變換圓檢測的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種新的Hough變換圓檢測方法（FHCD），該方法首先對原始圖像進(jìn)行預(yù)處理，并通過Canny邊緣檢測方法進(jìn)行邊緣提取，在對提取的邊緣進(jìn)行形狀識別，排除非圓，之后利用圓是中心對稱圖形的幾何性質(zhì)，同時選取圓周上三點(diǎn)，計算出圓心和半徑，將搜索空間由三維降到一維，進(jìn)一步降低了計算復(fù)雜度，提高了計算速度，實(shí)驗表明，該方法同時具有較高的檢測精度和抗干擾性。

1 Hough變換圓檢測原理

Hough變換最早于1962年由Paul Hough提出，其基本思想是將檢測圖像的空間域映射到參數(shù)空間，用大多數(shù)邊界點(diǎn)滿足的某種參數(shù)形式來描述圖像中的邊緣曲線,通過投票和設(shè)置累加器的方法將圖像空間中的復(fù)雜問題轉(zhuǎn)換成簡單的局部峰值檢測問題[7]。

Hough變換是目前檢測圖像圓的主要方法，它實(shí)現(xiàn)了圖像空間的邊緣點(diǎn)映射到參量空間中一個投票過程，空間的峰值點(diǎn)對應(yīng)檢測圖像所需要的參數(shù)。傳統(tǒng)的Hough變換在參量空間中對三個自由參數(shù)圓心坐標(biāo)（a,b）和半徑r進(jìn)行累積，對存儲量和計算量要求很高。

Hough變換檢測圓的公式：

其中r0為半徑,（a0，b0）為圓心坐標(biāo)。

在參數(shù)空間中，半徑為r，圓心坐標(biāo)為（a,b）的圓表達(dá)式為：

式(2)表示圖像空間的圓對應(yīng)著參數(shù)空間中的一個點(diǎn)，圖像空間中的任意一個有效點(diǎn)（xi，yi）在參數(shù)空間中對應(yīng)著一個三維直立圓錐，如圖1所示，該點(diǎn)約束了通過該點(diǎn)的一族圓的參數(shù)。對于圖像空間中的一個圓，它的半徑是固定不變的，而圓周上各個點(diǎn)組成的集合在參數(shù)空間中表現(xiàn)為半徑相等，而圓心坐標(biāo)不等的各個圓錐的集合。圖像空間中圓上的點(diǎn)映射到參數(shù)空間中的一族圓錐的交點(diǎn)正好對應(yīng)于圓的圓心坐標(biāo)和圓的半徑，即是被檢測圓的三個參數(shù)，實(shí)現(xiàn)Hough變換檢測圓。

如圖2所示，圖像空間中4個邊緣點(diǎn)（A，B，C，D）映射到參數(shù)空間，在圓心坐標(biāo)（a，b，r）處相交，對應(yīng)著在點(diǎn)（a，b，r）的累加器投票值為峰值，從圖中可以看出，圖像空間到參數(shù)空間的映射，是一維到三維的映射，這需要大量的存儲空間且計算復(fù)雜度高，難以實(shí)際應(yīng)用中對實(shí)時性要求較高的圓檢測。

圖1 圖像空間點(diǎn)對應(yīng)參數(shù)空間直立圓錐

圖2 圖像空間圓上點(diǎn)在參數(shù)空間中的表示

2 改進(jìn)的Hough變換圓檢測方法

Hough變換需要將圖像空間轉(zhuǎn)換成3個參量空間，參量空間較大，而往往為了提高精度，量化值又較小，投票階段箱格數(shù)會很多，使得Hough變換圓檢測占用內(nèi)存空間和計算量特別多，運(yùn)算速度慢[8]，為此對Hough變換進(jìn)行了改進(jìn)，該方法在圓周上同時選取三點(diǎn)，以過圓心的直線x=a0，y=b0為對稱軸對圖像上的三點(diǎn)進(jìn)行對稱選取，選取的三點(diǎn)對應(yīng)于參量a-b-r空間中一點(diǎn)，運(yùn)用Hough變換對該點(diǎn)進(jìn)行累加計數(shù)，計數(shù)最大值對應(yīng)的參數(shù)坐標(biāo)即圓心坐標(biāo)和半徑的值，由此將搜索空間由三維降到了一維，降低了計算復(fù)雜度，提高了計算速度和精確性。

2.1 圓的識別

攝像機(jī)在獲取圖像的過程中，拍攝的目標(biāo)圖片中往往含有其他背景圖像，因此將獲取的彩色圖像轉(zhuǎn)換成灰度圖后，運(yùn)用Otsu圖像分割技術(shù)將Mark點(diǎn)圖像從背景圖像中精確地分割出來，閾值分割后運(yùn)用Canny邊緣檢測器對圖像進(jìn)行邊緣提取，得到一幅包含邊緣信息的圖像。

為了避免無效投票，減少無效累積，邊緣檢測后對圖像進(jìn)行圓形識別，圖3中點(diǎn)A1，A2，A3，A4為圓周上互不重合的四點(diǎn)，坐標(biāo)值分別為（x1，y1），（x2，y2），（x3，y3），（x4，y4）由圓的性質(zhì)可知，若四點(diǎn)在圓周上，則必滿足弦A1A2和弦A3A4在弦A2A3的異側(cè)。

構(gòu)造函數(shù)：

將（x1，y1）、（x4，y4）代入上式：

若f（x1，y1）. f（x4，y4）＞0，則弦MN和弦PQ一定在弦NP的同側(cè)；

若f（x1，y1）. f（x4，y4）＜0，則弦MN和弦PQ一定在弦NP的異側(cè)；

若f（x1，y1）. f（x4，y4）=0，則弦MN或弦PQ一定與弦NP共線。

對于f（x1，y1）. f（x4，y4）＞0的圖形可以初步認(rèn)為是圓，由此就可以在檢測過程中，排除明顯不可能為圓的輪廓，從而提高后續(xù)Hough變換檢測圓的效率。

圖3 圓性質(zhì)圖

2.2 圓參數(shù)確定

圖像上每一點(diǎn)的灰度值，如式(4)所示：

p（m,n）表示第m行第n列的像素點(diǎn)坐標(biāo)值。定義圖像中任意一點(diǎn)關(guān)于過圓心的直線x=a0，y=b0對稱的點(diǎn)組集合為|P|={（A1，B1，C1），（A2，B2，C2），…，（An，Bn，Cn）}，在圖4中圓上選取Ai，Bi，Ci三點(diǎn)，（Ai，Bi，Ci）∈|P|，Ai，Bi，Ci坐標(biāo)分別為（mi，ni）、（qi，ni）、（mi，zi），點(diǎn)Ai與點(diǎn)Bi關(guān)于圓心橫坐標(biāo)x=a0對稱，點(diǎn)Ai與Ci關(guān)于圓心縱坐標(biāo)y=b0對稱，Ai，Bi，Ci三點(diǎn)構(gòu)成一個以直徑為斜邊的直角三角形。

由于圖像二值化處理過程中圖像邊緣存在一定的偏移和誤差，因此存在對稱點(diǎn)為非邊緣點(diǎn)的情況，對此采用對稱點(diǎn)上下左右偏移一個像素來處理。

設(shè)：

當(dāng)f（mi，ni）×f（qi，ni）=1時Ai（mi，ni）與Bi（qi，ni）是關(guān)于圓心橫坐標(biāo)x=a0的對稱點(diǎn)，當(dāng)f（mi，ni）×f（mi，zi）=1時Ai（mi，ni）與Ci（mi，zi）是關(guān)于圓心縱坐標(biāo)y=b_0的對稱點(diǎn)。

利用圓是中心對稱的幾何性質(zhì)可以求出：

圓上的任意不共線三點(diǎn)Ai，Bi，Ci，對應(yīng)于參量空間中一個點(diǎn)（ai，bi，ri），參量空間中的點(diǎn)用向量表示圖像中圓（ai，bi，ri）上的點(diǎn)組（Ai，Bi，Ci）對應(yīng)參量空間中向量在圖像中選取N個點(diǎn)組，得到包括N個向量的向量組，在參量空間中運(yùn)用Hough變換圓檢測對向量值進(jìn)行累加計數(shù)，累計陣列中出現(xiàn)次數(shù)最多的向量值就是圖像中圓的參數(shù)。

圖4 獲取圓心和半徑

2.3 復(fù)雜度分析

假設(shè)圖像有N個待分析點(diǎn)，則共有個點(diǎn)組，從圖像空間到參數(shù)空間進(jìn)行投票時，對應(yīng)于在參數(shù)空間中進(jìn)行了次投票，復(fù)雜度函數(shù)為：f（N）=O（N3）。

在改進(jìn)的算法中，同樣假定圖像中有N個待分析點(diǎn)，點(diǎn)Ai選定后，由于圓是中心對稱圖形的幾何性質(zhì)，水平對稱點(diǎn)Bi，垂直對稱點(diǎn)Ci也被定下來，點(diǎn)（Ai，Bi，Ci）能夠達(dá)到遍歷所有有效邊緣，共有N個點(diǎn)組，對應(yīng)于參量空間中進(jìn)行了N次投票，復(fù)雜度函數(shù)為f（N）=O（N）。O（N3）遠(yuǎn)大于O（N），從而顯著減少了計算時間，提高了計算速度，達(dá)到精確檢測的目標(biāo)。

2.4 算法流程

本文的算法流程如圖5所示：先對圖像進(jìn)行預(yù)處理以消除攝像頭在獲取圖像時所產(chǎn)生的噪聲，閾值分割后運(yùn)用Canny算子進(jìn)行邊緣檢測，獲取圖像邊緣信息，然后通過計算f(x,y)來對輪廓進(jìn)行圓形識別，最后運(yùn)用新的Hough變換圓檢測方法獲取圓參數(shù)。

圖5 算法流程圖

3 實(shí)驗結(jié)果和分析

為驗證本文算法的檢測結(jié)果，采用PCB Mark圖片對改進(jìn)后Hough變換圓檢測方法與SHT和RHT算法進(jìn)行對比實(shí)驗，主要針對圓檢測準(zhǔn)確度和速度進(jìn)行考察。實(shí)驗采用的計算機(jī)為Intel 3.6GHz Core i7-7700，8G內(nèi)存，軟件環(huán)境為MATLAB2014a。

3.1 速度和精確性測試

圖6 新Hough變換檢測過程圖

測試圖片為PCB Mark圖，本文的測試程序?qū)z測到的圓用藍(lán)色線畫出，原始圖像在PCB中運(yùn)用3D顯示功能生成，對原始圖像進(jìn)行平滑處理，生成與實(shí)際情況盡可能相符的標(biāo)準(zhǔn)圖像，如圖6(a)所示，實(shí)驗重復(fù)100次。圖6(b)是邊緣檢測圖，圖6(c)是最終的檢測結(jié)果圖。

表1列出了不同方法的檢測結(jié)果，檢測結(jié)果表明，三種檢測方法都能檢測出圓，檢測誤差在一個像素以內(nèi)，執(zhí)行時間約為26ms，顯示了新Hough變換圓檢測方法具有檢測精度高，計算速度快的特性。

表1 速度和精確性性測試結(jié)果

3.2 魯棒性測試

在工業(yè)檢測環(huán)境下，由于光線照射不均勻，其他影像干擾等因素的影響，存在各種噪聲，因此模擬實(shí)際工作環(huán)境，給檢測圖像加上不同強(qiáng)度的椒鹽噪聲，比較不同圓檢測方法所花時間，進(jìn)行魯棒性測試。

圖7(a)Mark圖像噪聲強(qiáng)度為10%，圖7(b)是邊緣檢測圖，圖7(c)是算法在噪聲影響下的圓檢測結(jié)果圖。表2為不同噪聲圖像的檢測數(shù)據(jù)，從中可以看出本文算法檢測的精度和速度優(yōu)于標(biāo)準(zhǔn)Hough變換。

圖7 噪聲Mark圖像的圓檢測

4 結(jié)論

提出了一種改進(jìn)的Hough變換圓檢測方法，該方法運(yùn)用閾值分割技術(shù)將測試目標(biāo)與背景分離，對檢測圖形進(jìn)行Canny邊緣檢測后，對檢測圖像進(jìn)行形狀識別，之后運(yùn)用新Hough變換識別圓的參數(shù)，得到檢測結(jié)果。運(yùn)用PCB Mark圖片和PCB Mark噪聲圖進(jìn)行實(shí)驗，實(shí)驗結(jié)果表明本文方法與標(biāo)準(zhǔn)Hough變換圓檢測方法（SHT）和隨機(jī)Hough變換圓檢測方法（RHT）相比，降低了計算復(fù)雜度，提高了處理速度，同時降低了對存儲空間的需求，且該方法保留了標(biāo)準(zhǔn)Hough變換檢測精度高、抗噪能力強(qiáng)的優(yōu)點(diǎn)，圖像中存在干擾因素時，計算速度優(yōu)勢明顯，具有較強(qiáng)的抗干擾能力和檢查精度，可以滿足機(jī)器視覺，模式識別等領(lǐng)域檢測的要求。

表2 不同噪聲條件下三種圓檢測方法速度和精度比較

參考文獻(xiàn)：

[1]Smereka M, Duleba I. Circular object detection using a modified Hough transform[J].International Journal of Applied Mathematics and Computer Science,2008,18(1):85.

[2]Xu L,Oja E.Randomized Hough transform (RHT):basic mechanisms,algorithms, and computational complexities[J].CVGIP: Image understanding,1993,57(2):131-154.

[3]Chen T C,Chung K L.An efficient randomized algorithm for detecting circles[J].Computer Vision and Image Understanding,2001,83(2):172-191.

[4]Lam W C Y,Yuen S Y. Efficient technique for circle detection using hypothesis filtering and Hough transform[J].IEEEProceedings-Vision,Image and Signal Processing,1996,143(5):292-300.

[5]Che0w JJ.An effective voting method for circle detection[J].Pattern recognition letters,2005,26(2):121-133.

[6]林金龍,石青云.用點(diǎn)Hough變換實(shí)現(xiàn)圓檢測的方法[J].計算機(jī)工程,2003,29(11):17-18.

[7]周勇亮,金燕,何萍,等.隨機(jī)Hough變換圓檢測累計加速算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2014,26(4):574-580.

[8]Wang J, Zhu Q, Wang W, et al. Straight line extraction algorithm by Hough transform combining edge grouping[J].Journal of Remote Sensing,2014,1:186-192.

[9]何東海,鄭海鷹,馬曉玲.GIS中城市平面地圖的模糊矢量化算法及實(shí)現(xiàn)[J].測繪學(xué)院學(xué)報,2001,(03):213-216.