自適應連續多級分區和初始閾值估計的快速模板匹配

孫靜晶　馬占欣　張　鵬　汪魯才

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

自適應連續多級分區和初始閾值估計的快速模板匹配

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

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

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

關鍵詞自適應連續多級分區; 歸一化互相關; 部分邊界相關; 增強邊界相關

Class NumberTP391

1引言

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

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

2自適應連續多級分區的快速模板匹配算法

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

(1)

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

圖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中的自相關ψ(x,y)的計算,本文采用自適應多級連續分區算法實現快速運算。如圖2所示,將模板圖像進行自適應連續多級分區,根據分區順序計算各層的上界,進行初始閾值估計后,采取多級連續淘汰獲得最優匹配區域。

2.1自適應連續多級分區策略

圖2　自適應連續多級分區和初始閾值估計的快速模板匹配算法框圖

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

通過柯西-施瓦茲不等式,文獻[10]中已經證明:

如果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自適應多級連續分區策略

圖3　自適應多級連續分區策略

2.2利用分區策略計算上界

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

1) 取得各層模塊的標記

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

Repeat:

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

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

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

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

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

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

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

(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層互相關的上界

(5)

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

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

(6)

其中NCC為歸一化互相關值。如果閾值T設置為0,則λmaxL=NCC。

2.3初始閾值估計

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

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

2.4利用自適應連續多級分區進行連續多級淘汰

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

圖5　連續多級淘汰方法流程圖

3實驗結果

為驗證所提出算法的有效性,本文將提出的算法和全搜索算法(FS),相關率Cr=50%的BPC算法,基于SAD的WUS算法,FFT算法,以及EBC算法進行了比較。實驗在intel P4 2.1G CPU,2G內存的個人電腦上進行,采用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圖作為原始圖,選取不同的模板圖的匹配結果。從表中可以看出,本文提出的算法在采用模板2,4時仍能保證匹配的精度,即不受光照變化的影響。而算法的執行時間比FS快了近30倍,比FFT算法快了近2倍,比EBC算法也要快。而WUS(SAD)算法雖然匹配速度較快,但在模板圖象的亮度變化時,匹配位置出錯。

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

圖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個模板后,各個算法的執行時間,單位為ms。

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

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

4結語

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

參 考 文 獻

[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].電子技術應用,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] 溫兆麟,陳新,鄭德濤.用快速歸一化互相關進行缺陷檢測[J].廣州航海高等專科學校學報,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] 蔡新建,鮮勇,張大巧.基于多線程的巡航導彈景象匹配技術研究[J].彈箭與制導學報,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算法的一種快速實現方法[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].傳感器與微系統,2007(9):104-106.

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

[10] 楊兵,于秋則,劉永才,等.基于新的加權互相關的圖像匹配[J].彈箭與制導學報,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].光子學報,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] 范新南,朱佳媛.基于小波變換的快速圖像匹配算法與實現[J].計算機工程與設計,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的歸一化互相關快速算法[J].現代電子技術,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日

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

中圖分類號TP391

DOI:10.3969/j.issn.1672-9722.2016.06.014