基于模板匹配的多圓識別算法

陳令剛

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院，安徽淮南232001)

基于模板匹配的多圓識別算法

陳令剛

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院，安徽淮南232001)

圓形是基本的幾個圖形，對圓形的識別也是計算機視覺的基本任務(wù)之一。圓形檢測在工業(yè)制造、通檢測、虹膜識別、生物醫(yī)藥、武器制造等領(lǐng)域都有著廣泛的應(yīng)用。模板匹配是圖像識別的常用的方法之一，但是模板匹配僅能匹配圖片視場中匹配度最高的位置。該文通過改進匹配策略，提出了一種基于距離的識別算法，使得能夠匹配出視場中所有的圓形。合成圖片上實驗結(jié)果表明了該算法的有效性，精度為像素級。

圓形識別；模板匹配；計算機視覺

Abstract：Circle is one of the basic graphics.Circular recognition is also one of the basic tasks of computer vision.Circle detec?tion in the industrial manufacturing,traffic detection,iris recognition,bio-medicine,weapons manufacturing and other fields has a wide range of application.Template matching is one of the commonly used methods of image recognition,but which can only match the highest degree of location in the image field of view.In this paper,a new algorithm Based on distance is proposed by improving the match strategy,so that all the circles in the field of view can be matched.The experimental results on the synthetic image show that the algorithm is effective and the precision is pixel level.

Key words：Circle detection;Template matching;Computer vision

1 概述

圓形的識別是圖像測量中最基本和最重要的任務(wù)之一，圓檢測在工業(yè)制造、交通檢測、虹膜識別、生物醫(yī)藥、武器制造等領(lǐng)域都有著廣泛的應(yīng)用。霍夫變換是最常用的圓形檢測技術(shù)，但是該算法空間復(fù)雜度和時間復(fù)雜度的需求都比較高，且在噪聲比較大的圖片背景下識別效果并不理想[1]。模板匹配是一種重要的圖像識別技術(shù)，已經(jīng)在很多計算機視覺中得到了應(yīng)用。如OCR、衛(wèi)星遙感、PCB檢測、視覺跟蹤等?；镜哪０迤ヅ渌惴ㄍㄟ^在源圖像上滑動指定大小模板圖模板圖像，源圖像與模板圖像一一進行相似度的計算。源圖像的每一個像素點都與模板圖像計算之后就可以得到最佳匹配位置，也得到相應(yīng)位置對應(yīng)的相似值。最佳匹配位置的橫縱坐標(biāo)各加上模板的1/2高和寬，這樣我們就得到了源圖像中的一個圓形的圓心。通過計算其他各點相似度與最佳匹配點的距離判斷其是否為圓形，當(dāng)距離小于某一經(jīng)驗值時，則判斷匹配到圓形。這樣便能把圓形位置和非圓形位置區(qū)分開，也就匹配出了源圖中所有的圓形。在檢測圓形時，為了防止產(chǎn)生干擾，我們將匹配成功的像素點周圍的像素值都不參與距離計算。最后，為了檢驗匹配的精度，我們隨機選取圓形邊緣上的三個點，通過三點擬合求出的圓心與模板匹配成功的圓心進行比較，從而確定該算法的精度。

2 模板匹配及三點擬合圓

2.1 模板匹配

模板匹配就是將模板以滑動窗口的形式遍歷整幅源圖像(待檢測的圖像)，每次滑動都會產(chǎn)生一個和模板等大小的ROI圖像，基于某種度量方式，計算模板與當(dāng)前ROI圖像的相似性度量值。這樣遍歷完整幅圖像后就會形成一個圖像，找出最大值對應(yīng)的位置(x,y)，它就是我們要尋找的目標(biāo)的位置。已知源圖中有要找的目標(biāo)，且該目標(biāo)同模板有相同的尺寸、方向，通過一定的算法可以在圖中找到目標(biāo)，確定其坐標(biāo)位置。以8位圖像(其1個像素由1個字節(jié)描述)為例，模板T(M×N個像素)疊放在被搜索圖S(W×H個像素)上平移，模板覆蓋被搜索圖的那塊區(qū)域叫子圖Sij。i，j為子圖左上角在被搜索圖S上的坐標(biāo)。搜索范圍是：

1≤i≤W—M+1

1≤j≤H—N+1

通過比較T和Sij的相似性，完成模板匹配過程。衡量模板T和子圖Si,j的匹配程度,可用的誤差平方和算法(SSD)，這也是速度較快的一種方法。此外還有平均絕對差算法(MAD)、絕對誤差和算法(SAD)、誤差平方和算法(SSD)、平均誤差平方和算法(MSD)、歸一化積相關(guān)算法(NCC)、序貫相似性檢測算法(SS?DA)、hadamard變換算法(SATD)等。本文采用的是SSD算法，公式如下：

模板大小的確定往往是一個經(jīng)驗值，一般緊貼目標(biāo)輪廓的模板或者包含太多背景的模板都不好，本文使用的模板是用畫圖畫出的標(biāo)準(zhǔn)的圓形模板，大小和源圖中目標(biāo)的大小基本一致。

2.1 三點擬合圓

模板匹配檢測圓之后，為了驗證其精確度，我們使用三點擬合圓的方法。三點擬合圓顧名思義是在圓形邊緣上隨機選取非共線的三點以確定圓的位置。圓的方程如下：

假設(shè)選取的三點為(x1，y1)，(x2，y2)，(x3，y3)，將這三點帶入方程(2)，得到：

運用Cramer法則解此方程組，得到參數(shù)a、b、c.

其中：

于是方程(2)可以重新寫為：

于是可以得到圓心(x0，y0)和半徑 r分別為(-a,-b)、(a2+b2-c)1/2。

3 實驗仿真及分析

本文的模板匹配適用于源圖像視場中的圓形大小基本一致的情況，比如在生物學(xué)領(lǐng)域，自動準(zhǔn)確的確定細(xì)胞的位置；人臉識別方面，確定眼睛的位置等等。該實驗是在合成的圖像上進行的，圖片像素大小1392*1040，模板像素大小100*100。圖像1為源圖像，圖像2為模板，圖片3為識別出的結(jié)果。表1列出了模板匹配識別及手動三點擬合的圓心坐標(biāo)。圓形檢測的步驟如下：

step1：根據(jù)源圖片S(W×H個像素)中的圓形的形狀生成模板圖片T(M×N個像素)，源圖片(圖1)中的圓是空心圓,那么也生成空心圓的模板(圖2)。生成的模板圖像的半徑要和源圖像中圓形的半徑要基本一致.

圖1 源圖像

圖2 模板圖像

Step2：運用公式(1)進行模板匹配，遍歷完整幅圖像后就會形成一個方差結(jié)果圖像S，得到每一個源圖像的像素點對應(yīng)的方差值，找出圖像S中方差值最小的位置min_Loc(x1,y1)及方差最大的位置max_Loc(x2,y2)，其方差值分別記為min_Loc_Value、max_Loc_Value。而min_Loc即為匹配到的第一個圓形的位置。圓心坐標(biāo)為：Loc(x,y)=min_Loc(x1+M/2,y1+N/2)。

Step3：為防止產(chǎn)生干擾，方差結(jié)果圖像S中min_Loc點附近1/2倍模板寬度和高度附近的值都不參與計算，我們將其均設(shè)置max_Loc_Value。

Step4：取排名第二個方差值最小的點new_min_Loc，其方差值為new_minValue，計算此點的方差值與min_Loc_Value的距離。計算方式如下：

如果distance＞=C，(C為某一經(jīng)驗值)，則判斷此位置為匹配到的第二個圓形。為了防止產(chǎn)生干擾，依然將new_min_Loc點附近1/2倍模板寬度和高度方差值都設(shè)置max_Loc_Value。

Step5：重復(fù)Step4，直到distance＜=C。

Step6：畫出匹配到的圓形，結(jié)果如圖3，結(jié)果表明能夠檢測出源圖像中所有的圓形。

圖3 檢測結(jié)果

Step7：用三點擬合圓的方法手動計算圓心，每個圓形選取10組計算圓心，最后求其平均。擬合圓的結(jié)果見表1。

4 實驗結(jié)果與結(jié)論

實驗采用對合成的圖片進行模板匹配，整套算法在VS2010+opencv2.4.9的環(huán)境下編程實現(xiàn)[3]，我們手動選取圓形上的三點擬合圓心作為對比，實驗對比結(jié)果表1所示。由此可見本文模板匹配方法能夠識別源圖像中的圓形且滿足一定的精度要求。

表1 多圓圖像的識別結(jié)果

5 結(jié)束語

本文提出了基于距離的多圓模板匹配算法，該算法能夠檢測源圖像中有一定噪聲下的多個圓形，識別的精度和手動三點擬合的圓心誤差在1個像素之內(nèi)。但是由于模板匹配技術(shù)本身的局限，僅當(dāng)模板中的目標(biāo)物大小基本能一致的時候才具有很好地識別效果。當(dāng)源圖像中的圓形大小不一致，可采用多模板匹配的方式實現(xiàn)。實際應(yīng)用中，圖片的情況是復(fù)雜多變的，由于光線、圖像采集、遮擋等多種因素的影響，待檢測的目標(biāo)經(jīng)常出現(xiàn)變異的情況，比如橢圓、邊緣斷續(xù)、多圓粘連等，也就是說在復(fù)雜背景下的圓檢測依然是一件挑戰(zhàn)性的工作。

[1]Atherton,T.J.and Kerbyson,D.J‘Using phase to represent ra?dius in the coherent circle Hough transform’,Proc,IEE Collo?quium on the Hough Transform,IEE,London,1993.

[2]Erik Cuevas,‘Automatic multiple circle detection Based on artificial immune systems’Expert system with Applications,2012(39)：713-722.

[3]劉瑞禎,于仕琪.opencv教程—基礎(chǔ)篇[M].北京：北京航空航天大學(xué)出版社,2007.

[4]周麗莎.基于模板匹配的視覺定位技術(shù)研究與應(yīng)用[D].大連：大連理工大學(xué),2012.

[5]張顯全,蘇勤,蔣聯(lián)源,等.一種快速的隨機Hough變換圓檢測算法[J].計算機工程與應(yīng)用,2008,44(22)：62-64.

[6]梁路宏,艾海舟.基于多關(guān)聯(lián)模板匹配的人臉檢測[J].軟件學(xué)報,2001(9).

[7]高聰,王福龍.基于模板匹配和局部HOG特征的車牌識別算法[J].計算機系統(tǒng)應(yīng)用,2017(9).

A Algorithm for Multiple-Circle Detection on Images using Template Matching

CHEN Ling-gang
(The Academy of Computer Science and Engineering in Anhui University of Science and Technology,Huainan 232001,China)

TP311

A

1009-3044(2017)24-0173-02

2017-07-15