孫靜晶　馬占欣　張　鵬　汪魯才

(1.鶴壁汽車工程職業(yè)學(xué)院　鶴壁　458030)(2.漯河技師學(xué)院　漯河　462000)(3.湖南師范大學(xué)　長沙　410081)

自適應(yīng)連續(xù)多級分區(qū)和初始閾值估計的快速模板匹配

孫靜晶1馬占欣2張鵬1汪魯才3

(1.鶴壁汽車工程職業(yè)學(xué)院鶴壁458030)(2.漯河技師學(xué)院漯河462000)(3.湖南師范大學(xué)長沙410081)

摘要論文提出了一種基于歸一化互相關(guān)測度(NCC)的通過結(jié)合自適應(yīng)連續(xù)多級分區(qū)和初始閾值估計實現(xiàn)高效搜索的快速模板匹配算法。歸一化互相關(guān)測度在光照改變時,比采用絕對差之和測度(SAD)要穩(wěn)定,但是歸一化互相關(guān)測度的缺陷在于它的計算量非常大。為了解決這一問題,論文根據(jù)模板圖像中不同模塊的梯度值,將模板圖像進(jìn)行逐級分區(qū),通過分區(qū)順序?qū)⒒ハ嚓P(guān)之和分為不同的層,得到各層互相關(guān)的上界,運用柯西-施瓦茲不等式得到上界間的關(guān)系,形成自適應(yīng)連續(xù)多級分區(qū)淘汰方法。同時,為了進(jìn)一步加快匹配速度,論文利用初始閾值估計產(chǎn)生一個較大的邊界閾值,以淘汰初始搜索時的大量非匹配點,減少搜索點數(shù)目。實驗結(jié)果表明,論文提出的算法在不降低匹配精度的前提下,算法的執(zhí)行速度比FS算法快將近30倍,比FFT算法快將近2倍,優(yōu)于EBC算法。

關(guān)鍵詞自適應(yīng)連續(xù)多級分區(qū); 歸一化互相關(guān); 部分邊界相關(guān); 增強邊界相關(guān)

Class NumberTP391

1引言

模板匹配在目標(biāo)跟蹤,機器視覺和圖像編碼等圖像處理領(lǐng)域具有重要的作用。模板匹配快速算法主要有兩類:一類為非窮舉搜索算法,它通過減少搜索點的數(shù)目來實現(xiàn)快速運算。B. Zitova等提出通過減少搜索范圍[1]來節(jié)省計算時間,H. Schweitzer等通過分解模板或者圖像為多個矩形區(qū)域并將每個矩形區(qū)域近似為一個多項式[2]來達(dá)到快速運算的目的。但這些算法找到的匹配點可能是局部最優(yōu)點。另一類窮舉搜索算法主要通過降低每個搜索點上的計算量來實現(xiàn)快速運算。它的優(yōu)點在于找到的匹配點是全局最優(yōu)點。在基于相異性測度的搜索中,C. D. Bei等提出部分失真淘汰算法(PDE)[3],它的思想是如果當(dāng)前失真測度大于當(dāng)前最小值時,立刻停止評估。而后,一系列新的算法被提出:W.Li等提出連續(xù)淘汰算法(SEA)[4],C.Lee等提出模塊和金子塔算法(BSP)[5],X.Q.Gao等提出多級連續(xù)淘汰算法(MSEA)[6],C.Wang等提出贏墩領(lǐng)出算法(WUS)[7]。但這些算法是基于SAD測度的,所以對光照的變化都比較敏感。而基于相關(guān)性測度的歸一化互相關(guān)測度在光照變化時比絕對差值和(SAD)和平方差和(SSD)測度更穩(wěn)定,在目標(biāo)識別和工業(yè)檢測等領(lǐng)域應(yīng)用廣泛。J. P. Lewis等通過在頻域利用FFT算法來計算相關(guān)性[8～9]實現(xiàn)快速運算。S. Mattoccia等提出加強邊界相關(guān)算法EBC[10],雖然EBC的算法執(zhí)行速度比FFT快,但EBC算法將模板分為均等的子模塊,所以得到的邊界仍不足以抑制可觀的搜索點。

本文通過對MSEA算法進(jìn)行擴(kuò)展,將其應(yīng)用到NCC測度中,提出了一種基于NCC測度的快速模板匹配算法,算法主要由兩部分組成:自適應(yīng)連續(xù)多級分區(qū)及初始閾值估計。自適應(yīng)連續(xù)多級分區(qū)利用圖像的復(fù)雜度實現(xiàn)高效的子模塊的劃分,提供了一個比MSEA更嚴(yán)格的邊界,而且可以在較早階段跳過更多的非匹配點的搜索;初始閾值估計產(chǎn)生一個較大的邊界閾值,它有效地抑制了開始階段搜索點的數(shù)目。實驗表明,提出的算法不但能實現(xiàn)比FFT、EBC更快的匹配速度,而且能夠保證匹配的精度。

2自適應(yīng)連續(xù)多級分區(qū)的快速模板匹配算法

設(shè)T為一大小為n*n的模板,I為原始圖像,大小為M*N?；贜CC的模板匹配通過尋找NCC函數(shù)的最大值,將模板T定位到I中,如圖1所示。記當(dāng)前模板在圖像中的位置為(x,y),當(dāng)前候選子圖為Ic(x,y)。

(1)

其中,ψ(x,y)為原始圖中候選子圖和模板之間的互相關(guān)值,‖IC(x,y)‖和‖T‖分別代表原始圖中候選子圖和模板圖的自相關(guān)值。

圖1　模板匹配圖

IMssn(x,y)=IIss(x+n-1,y+n-1)

+IIss(x-1,y-1)-IIss(x+n-1,y-1)

-IIss(x-1,y+n-1)

(2)

TMssa(x,y)=ITss(x+a-1,y+a-1)

+ITss(x-1,y-1)-ITss(x+a-1,y-1)

-ITss(x-1,y+a-1)

(3)

對于NCC中的自相關(guān)ψ(x,y)的計算,本文采用自適應(yīng)多級連續(xù)分區(qū)算法實現(xiàn)快速運算。如圖2所示,將模板圖像進(jìn)行自適應(yīng)連續(xù)多級分區(qū),根據(jù)分區(qū)順序計算各層的上界,進(jìn)行初始閾值估計后,采取多級連續(xù)淘汰獲得最優(yōu)匹配區(qū)域。

2.1自適應(yīng)連續(xù)多級分區(qū)策略

圖2　自適應(yīng)連續(xù)多級分區(qū)和初始閾值估計的快速模板匹配算法框圖

2.1.1柯西-施瓦茲不等式的推廣

通過柯西-施瓦茲不等式,文獻(xiàn)[10]中已經(jīng)證明:

如果a,b∈Rp,A={1,2,…,p},則存在r∈{1,2,…,p}

A1∪A2…Ar=S

Ai∩Aj=?,?i≠j,(i,j∈{1,2,…,r})

則下面的不等式成立:

(4)

2.1.2自適應(yīng)多級連續(xù)分區(qū)策略

圖3　自適應(yīng)多級連續(xù)分區(qū)策略

2.2利用分區(qū)策略計算上界

本文將每個子模塊信息用模塊的起點坐標(biāo),模塊大小,模塊梯度幅度和,模塊分層層數(shù)以及模板起始位置來標(biāo)記。

1) 取得各層模塊的標(biāo)記

設(shè)模板圖像標(biāo)記為(x,y,n,sg,r,p),即模板的起點坐標(biāo)為(x,y),模板的大小為n*n,模板的梯度幅度和為sg,模板分層的層數(shù)r,模板存放的起始位置p。

Repeat:

(1)從所有的模塊標(biāo)記信息中選擇具有最大梯度幅度和的模塊設(shè)它的標(biāo)記為(x1,y1,n1,sg1,r,p1)。

(2)將標(biāo)記信息中層數(shù)信息為r的不具有最大梯度幅度和的所有模塊的標(biāo)記信息中的層數(shù)信息加一。

(3)將所選的具有最大梯度和的模塊分為四個子模塊,分別計算它們的梯度幅度和。

(4)檢查四個子模塊,如果子模塊的梯度幅度和大于一個給定閾值T,將模塊存入起始位置分別為

p1,p1+(n1/2*n1/2),p1+2*(n1/2)*(n1/2),p1+3*(n1/2)*(n1/2)的存儲區(qū)域。為簡便起見,這里將存儲區(qū)域的起始位置分別標(biāo)注為p11,p,p13,p14。

本文中T設(shè)置為0,以得到和全搜索(FS)NCC一樣的精度,找到全局最優(yōu)點。如果T設(shè)置得大些,可進(jìn)一步提高算法的運算時間,但匹配精度下降。

(5)將四個子模塊分別標(biāo)記為

(x1,y1,n1/2,sg11,r+1,p11),(x1+n1/2,y1,n1/2,sg12,r+1,p12),(x1,y1+n1/2,n1/2,sg13,r+1,p13),(x1+n1/2,y1+n1/2,n1/2,sg14,r+1,p14)。

Until:所有子模塊的梯度幅度和均小于閾值。

2) 計算NCC上界

第r層互相關(guān)的上界

(5)

在計算βr(x,y)時,先查找模塊標(biāo)記信息中層數(shù)信息為r的所有模塊標(biāo)記。通過標(biāo)記信息中的(x,y,n)即起點坐標(biāo),模塊大小,利用式(2)和式(3)完成上界的計算。

λ0≥λ1≥…λr≥…λmaxL≥NCC

(6)

其中NCC為歸一化互相關(guān)值。如果閾值T設(shè)置為0,則λmaxL=NCC。

2.3初始閾值估計

利用閾值NCCmax淘汰搜索點的模板匹配方法,通常設(shè)置一個可能出現(xiàn)的最小值,例如0,給NCCmax,這個值隨后被計算得到的當(dāng)前的NCCmax替代。這是一種降低計算量的有效方法。然而,最匹配點的坐標(biāo)通常不知道,如果最優(yōu)點在起始搜索點附近,那么快速搜索到目標(biāo);相反,如果最優(yōu)點遠(yuǎn)離起始點搜索,則需要較多的計算時間。如果我們在搜索開始之前估計一個較大的閾值,和在正確匹配點處NCCmax的值相同或者近似,那么更多的搜索點可以在搜索過程中淘汰,計算量將大大降低。當(dāng)然,利用估計閾值進(jìn)行窮舉搜索一般都能找到全局最優(yōu)匹配的點,而不會陷入局部最優(yōu)點。本文獲取初始閾值的方法如圖4所示。其中原始圖大小為M*N,模板大小為n*n。

圖4　初始閾值估計算法流程圖

2.4利用自適應(yīng)連續(xù)多級分區(qū)進(jìn)行連續(xù)多級淘汰

在獲得初始估計閾值后,便可進(jìn)行連續(xù)多級淘汰,如圖5所示,獲取最優(yōu)匹配位置。其中原始圖大小為M*N,模板大小為n*n。

圖5　連續(xù)多級淘汰方法流程圖

3實驗結(jié)果

為驗證所提出算法的有效性,本文將提出的算法和全搜索算法(FS),相關(guān)率Cr=50%的BPC算法,基于SAD的WUS算法,FFT算法,以及EBC算法進(jìn)行了比較。實驗在intel P4 2.1G CPU,2G內(nèi)存的個人電腦上進(jìn)行,采用C語言及Matlab編程。本文采用256*256的lena圖,如圖6(a)所示,以及加入σ=16的隨機高斯噪聲之后的lena圖作為原始圖,如圖6(b)所示。采用從原始圖中選取的大小分別為64*64,128*128的子圖,如圖7中,模板1及模板3所示,以及它們提高50%亮度之后的圖作為模板圖,如圖7中,模板2及模板4所示。

表1展示了采用256*256的lena圖作為原始圖,選取不同的模板圖的匹配結(jié)果。從表中可以看出,本文提出的算法在采用模板2,4時仍能保證匹配的精度,即不受光照變化的影響。而算法的執(zhí)行時間比FS快了近30倍,比FFT算法快了近2倍,比EBC算法也要快。而WUS(SAD)算法雖然匹配速度較快,但在模板圖象的亮度變化時,匹配位置出錯。

表2展示了在256*256的lena圖上疊加σ=16的隨機高斯噪聲之后的lena圖作為原始圖,選取不同的模板圖像的匹配結(jié)果,從表中可以看出,提出的算法在原始圖受噪聲污染時,仍能保證匹配位置的正確性,而且匹配速度幾乎不受噪聲影響。

圖6　原始圖

圖7　模板圖

算法原始圖類型T(1)T(2)T(3)T(4)全局搜索算法(FS)a3271314350314925(BPC)a1501142525162347WUS(SAD)a43*11772*165FFTa116139213232EBCa8691143161提出的算法a62799497

其中,T(i)(1≤i≤4)表示選擇第i個模板后,各個算法的執(zhí)行時間,單位為ms。

表2　對圖1(b),采用不同模板后,

其中,T(i)(1≤i≤4)表示選擇第i個模板后,各個算法的執(zhí)行時間,單位為ms.

4結(jié)語

本文提出了一種基于NCC測度的非常高效的模板匹配算法。將自適應(yīng)連續(xù)多級分區(qū)方法結(jié)合初始閾值估計實現(xiàn)高效計算。自適應(yīng)連續(xù)多級分區(qū)利用圖像的復(fù)雜度實現(xiàn)高效的子模塊的劃分,提供了一個比MSEA更嚴(yán)格的邊界。而且可以在較早階段跳過更多的非匹配點的搜索;初始閾值估計產(chǎn)生了一個較大的邊界閾值,它有效的抑制了開始階段搜索點的數(shù)目。實驗結(jié)果表明,提出的算法比FS快近30倍,比FFT快近2倍,優(yōu)于EBC算法;而且在光照變化和隨機噪聲的影響下,仍能保證匹配的精度。

參 考 文 獻(xiàn)

[1] B. Zitova, J. Flusser. Image registration methods: a survey[J]. Image Vis. Comput,2003,21(11):977-1000.

[2] H. Schweitzer, J. W. Bell, F. Wu. Very fast template matching[C]//Proc. Eur. Conf. Computer Vision,2002:358-372.

[3] C. D. Bei, R. M. Gray. An improvement of the minimum distortion encoding algorithm for vector quantization[J]. IEEE Trans. Commun.,1985,COM-33(10):1132-1133.

[4] 趙鵬,白振興,范文同.基于主成分分析的快速圖像匹配研究[J].電子技術(shù)應(yīng)用,2010(4):132-134.

ZHAO Peng. white rejuvenation; model; fast image matching based on principal component analysis[J]. Electronic Technology Application,2010(4):132-134.

[5] 溫兆麟,陳新,鄭德濤.用快速歸一化互相關(guān)進(jìn)行缺陷檢測[J].廣州航海高等?？茖W(xué)校學(xué)報,2006(2):29-31.

WEN Zhaolin, CHEN Xin, ZHENG Detao. Defect detection using fast normalized cross correlation[J]. Journal of Guangzhou Maritime College,2006(2):29-31.

[6] 蔡新建,鮮勇,張大巧.基于多線程的巡航導(dǎo)彈景象匹配技術(shù)研究[J].彈箭與制導(dǎo)學(xué)報,2010(2):32-34.

CAI Xinjian, XIAN Yong, ZHANG Daqiao. The research on the technique of multi thread based cruise missile scene matching[J].

[7] 黃真寶,陳陽.圖像匹配中NCC算法的一種快速實現(xiàn)方法[J].信息化研究,2011(2):48-52.

HUANG Zhenbao, CHEN Yang. NCC algorithm[J]. Information Research,2011(2):48-52.

[8] 孔凡芝,王以忠,李君蘭,等.引線鍵合匹配定位算法研究[J].微計算機信息,2008(30):232-233.

KONG Fanzhi, WANG Yizhong, LI Junlan, et al. Lead bonding matching localization algorithm research[J]. Micro Computer Information,2008(30):232-233.

[9] 孫卜郊,周東華.基于NCC的快速匹配算法[J].傳感器與微系統(tǒng),2007(9):104-106.

SUN Bujiao, ZHOU Donghua. Fast matching algorithm based on NCC[J]. Sensor,2007(9):104-106.

[10] 楊兵,于秋則,劉永才,等.基于新的加權(quán)互相關(guān)的圖像匹配[J].彈箭與制導(dǎo)學(xué)報,2008(4):199-202.

in the autumn, YANG Bing, LIU Yongcai, et al. New image correlation matching based on weighted[J]. Missiles and Guidance Journal,2008(4):199-202.

[11] 郭偉,趙亦工,謝振華.一種改進(jìn)的紅外圖像歸一化互相關(guān)匹配算法[J].光子學(xué)報,2009(1):189-193.

GUO Wei, ZHAO Yigong, XIE Zhenhua. One kind of improved infrared image normalized mutual correlation matching algorithm[J].:189-193

[12] 范新南,朱佳媛.基于小波變換的快速圖像匹配算法與實現(xiàn)[J].計算機工程與設(shè)計,2009(20):4674-4676.

FAN Xinnan, ZHU Jiayuan. fast image matching algorithm based on wavelet transform and[J]. Computer Engineering and Design,2009(20):4674-4676.

[13] 孫祖鑫,吳強.一種基于TS201的歸一化互相關(guān)快速算法[J].現(xiàn)代電子技術(shù),2010(10):125-127.

SUN Zuxin, WU Qiang. A fast algorithm for normalized cross correlation based on TS201[J]. Modern Electronic Technology,2010(10):125-127.

Adaptive Continuous Multistage Partition and the Initial Threshold Estimation Fast Template Matching

SUN JingjingMA ZhanxinZHANG PengWANG Lucai

(1. Hebi Automotive Engineering Vocational College Teachers of Department of Electronics, Hebi458030)(2. Luohe Institute of Technician Director, Luohe462000)(3. Hunan Nomal University, Changsha410081)

AbstractIn this paper, a fast template matching algorithm based on normalized mutual correlation measure(NCC) is proposed to achieve efficient search by combining adaptive continuous multilevel partitioning and initial threshold estimation. The normalized cross correlation measure is stable in the light of the change of illumination, but the defect of the normalized cross correlation measure is that it is very large. In order to solve this problem, this paper divides the template image into different layers according to the gradient values of different modules in the template image, and gets the upper bound of the correlation between the different layers. The upper bound is obtained by using the Schwartz Cauchy inequality. At the same time, in order to further speed up the matching speed, this paper uses the initial threshold estimation to generate a large number of non matching points, and reduce the number of search points. The experimental results show that the proposed algorithm is faster than the algorithm without reducing the matching accuracy. The algorithm is nearly 30 times faster than the FS algorithm. It is nearly 2 times faster than the FFT algorithm. It is better than the EBC algorithm.

Key Wordsadaptive continuous multilevel partitioning, normalized cross correlation, partial boundary correlation, enhanced boundary correlation

收稿日期:2015年12月1日,修回日期:2016年1月7日

作者簡介:孫靜晶,女,助教,研究方向:電子技術(shù)教育。馬占欣,男,高級實習(xí)指導(dǎo)教師,研究方向:自動化專業(yè)。張鵬,男,碩士研究生,研究方向:汽車維修。汪魯才,男,博士,教授,碩士生導(dǎo)師,研究方向:圖像處理與模式識別。

中圖分類號TP391

DOI:10.3969/j.issn.1672-9722.2016.06.014