基于Haar小波和形狀模板的圖像快速匹配算法*

白冰峰，溫秀蘭，張中輝

(南京工程學(xué)院 自動(dòng)化學(xué)院，南京 211167)

基于Haar小波和形狀模板的圖像快速匹配算法*

白冰峰，溫秀蘭，張中輝

(南京工程學(xué)院 自動(dòng)化學(xué)院，南京 211167)

針對(duì)傳統(tǒng)的模板匹配方法在低對(duì)比度的圖像中匹配不到目標(biāo)物體和匹配計(jì)算量大等問(wèn)題，提出一種基于離散Haar小波變換和形狀模板的圖像快速匹配算法。首先，使用Haar小波對(duì)圖像進(jìn)行分解操作，將分解的低頻信號(hào)重構(gòu)得到壓縮圖像，以減少匹配計(jì)算量；其次，使用形狀模板對(duì)壓縮圖像進(jìn)行匹配，設(shè)計(jì)出Haar小波圖像壓縮和形狀模板匹配相結(jié)合的算法及程序。最后，經(jīng)大量實(shí)驗(yàn)結(jié)果證實(shí)：所提出的算法不僅匹配速度快，精度高，而且匹配結(jié)果不受遮蔽、混亂和非線性光照變化等情況的影響，適宜于在復(fù)雜環(huán)境中進(jìn)行圖像提取、工件識(shí)別等。

小波變換；形狀模板；圖像匹配

0 引言

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展和廣泛應(yīng)用，計(jì)算機(jī)視覺(jué)在工業(yè)機(jī)器人控制、自主汽車或移動(dòng)機(jī)器人導(dǎo)航、醫(yī)學(xué)圖像分析、制造業(yè)自動(dòng)檢測(cè)等領(lǐng)域得到眾多應(yīng)用。其中模板匹配是計(jì)算機(jī)視覺(jué)需要解決的關(guān)鍵問(wèn)題，如何在干擾和遮蔽情況下進(jìn)行模板匹配一直是模板匹配的關(guān)鍵。多年來(lái)，研究者們提出了多種圖像模板匹配算法。Borgefors G提出了計(jì)算模板邊緣點(diǎn)與離它最近的圖像邊緣點(diǎn)之間的均方差最小的方法，這種通過(guò)計(jì)算圖像距離的方法提高了匹配效率，而且不受光照變化和混亂影響，但對(duì)遮擋很敏感[1]。Rucklidge提出了一種改進(jìn)的Hausdorff算法，這種算法對(duì)小面積的遮擋有很好的適應(yīng)性，但是計(jì)算量很大[2]。這些算法都存在一個(gè)缺點(diǎn)，都需要在圖像中提取邊緣，導(dǎo)致目標(biāo)匹配算法只能適用于光照變化很小的情況。

本文提出了基于離散Haar小波變換和形狀模板的圖像快速匹配算法。首先采用Haar小波變換對(duì)圖像進(jìn)行壓縮，然后利用canny算子獲取模板圖像和待搜索圖像邊緣信息，并計(jì)算其方向向量[3]，根據(jù)定義的相似度量[4]進(jìn)行匹配。其中采用Haar小波壓縮圖像，匹配算法速度快，且不受遮擋、混亂和非線性光照的影響。實(shí)驗(yàn)表明，基于離散Haar小波變換和形狀模板的圖像快速匹配算法的視覺(jué)系統(tǒng)可以快速匹配到目標(biāo)物體，并且利用相似度量進(jìn)行匹配，確保了匹配的準(zhǔn)確性。

1 小波變換和Haar小波

在整個(gè)高分辨率圖像中計(jì)算相似度量也是一個(gè)計(jì)算量龐大的工程，所以提出基于Haar小波的圖像壓縮策略，以減少計(jì)算量，提高匹配速度。小波變換[5]的含義：將基本小波函數(shù)ψ(t)做位移τ后，再在不同尺度α下，與待分析信號(hào)X(t)做內(nèi)積：

(1)

等效頻域表示為：

(2)

式中X(t),ψ(w)分別是x(t),ψ(t)的傅立葉變量，α和τ分別為伸縮因子和平移因子[6]。

Haar小波在時(shí)域上是不連續(xù)的，但在圖像處理中，具有圖像壓縮比高，處理速度快和圖像分解簡(jiǎn)單等優(yōu)點(diǎn)。通過(guò)Haar小波變換后得到低頻和高頻圖像，因?yàn)閳D像特征是由低頻部分決定的，所以保留低頻部分，去除高頻部分。此外，本文采用閾值的設(shè)置，對(duì)圖像進(jìn)行量化處理。然后設(shè)置不同閾值得到分解圖像含“0”數(shù)目以及圖像文件的大小。原始圖像cameaman.tif在閾值25、85情況下1和3級(jí)分解的低頻信號(hào)重構(gòu)得到的圖像如圖1所示。

圖1 Haar小波分解重構(gòu)圖像示例

原始圖像(圖1a)在閾值T=25的Haar小波1級(jí)和3級(jí)分解低頻信號(hào)重構(gòu)得到的圖像分別為圖1b和圖1c，在閾值T=85的Haar小波1級(jí)和3級(jí)分解低頻信號(hào)重構(gòu)得到的圖像分別為圖1d和圖1e。從圖1d和圖1e可以明顯看出圖像模糊了，使用低頻信號(hào)重構(gòu)圖像，去除了高頻信號(hào)和高頻中含有噪聲的部分，不僅提高了匹配效率，而且減少了噪聲干擾。

2 基于形狀模板的圖像快速匹配

2.1 相似度量

(3)

如果圖像模板中一個(gè)特征值丟失，噪聲將隨機(jī)生成一個(gè)方向向量，這些方向向量平均起來(lái)將不會(huì)對(duì)總和產(chǎn)生影響，所以相似度量不會(huì)受到遮擋和混亂的影響。

公式(1)中提供的相似度量算法并不真正能夠不受光照變化的影響，因?yàn)楫?dāng)使用邊緣提取算法計(jì)算方向向量時(shí)，方向向量的長(zhǎng)短取決于圖像的亮度，所以需要一個(gè)已經(jīng)定義合適范圍的相似度量指定一個(gè)閾值確定模板是否出現(xiàn)在圖像中。下式中的相似度量可以實(shí)現(xiàn)這個(gè)要求：

(4)

因?yàn)閷⒎较蛳蛄窟M(jìn)行歸一化，所有的向量長(zhǎng)度都變?yōu)?，所以相似度量不受任意光照變化的影響。又因?yàn)槿绻麍D像中某個(gè)特征丟失，噪聲將導(dǎo)致一個(gè)隨機(jī)的方向向量，這些方向向量平均起來(lái)不會(huì)對(duì)總和造成影響，所以此相似度量不受遮擋和混亂的影響。綜上所述，所求的相似度量不受遮擋、混亂以及光照變換的影響。

2.2 快速匹配原理

公式(4)和公式(5)中歸一化相似度量將返回一個(gè)小于1的數(shù)作為潛在匹配對(duì)象的分值。匹配分值提供了判斷數(shù)據(jù)，如果分值為1則表示模板與圖像之間完美一致，如果物體有30%被遮擋，平均匹配分值不會(huì)超過(guò)0.7。在匹配圖像過(guò)程，對(duì)圖像中每個(gè)點(diǎn)進(jìn)行一次全面歸一化計(jì)算，計(jì)算量大，并且大量的點(diǎn)是無(wú)用的。所以設(shè)置用戶定義的閾值smin，僅僅求出潛在匹配位置的達(dá)到用戶定義閾值smin的相似度量。使用sj表示累計(jì)到模板的第j個(gè)元素時(shí)點(diǎn)積的總和，然后進(jìn)行歸一化計(jì)算，其公式如下：

(5)

2.3 圖像匹配過(guò)程

從參考圖像選取含目標(biāo)物體的感興趣區(qū)域生成其模板，使用Canny濾波器處理模板搜索圖像,并計(jì)算出邊緣上點(diǎn)的方向向量，構(gòu)建模板并使用2×2均值濾波器平滑。對(duì)壓縮處理的圖像搜索進(jìn)行相似性度量匹配,并返回潛在匹配點(diǎn)、匹配分值及其變換參數(shù),并將模板進(jìn)行相應(yīng)的變換?？梢酝ㄟ^(guò)設(shè)置匹配閾值smin，并且根據(jù)上述搜索停止標(biāo)準(zhǔn)，匹配到目標(biāo)物體并終止搜索。

3 算法及程序設(shè)計(jì)

圖2 算法程序流程圖

4 實(shí)驗(yàn)與分析

根據(jù)上述原理和流程，在VC++平臺(tái)下設(shè)計(jì)相應(yīng)的算法程序。本次實(shí)驗(yàn)采用德國(guó)的basler像素為500萬(wàn)的工業(yè)相機(jī)進(jìn)行圖像采集，為了保證采集圖像的清晰和完整，通過(guò)實(shí)驗(yàn)找到合適閾值。實(shí)驗(yàn)的圖像大小為4922KB,閾值為5、25、45和85的1～3級(jí)Haar小波分解和不同閾值和級(jí)數(shù)分解下圖像中系數(shù)含“0”數(shù)目和文件大小曲線圖如圖3所示。

由圖3可以清楚地看出，在固定閾值時(shí)，Haar小波分解級(jí)數(shù)越大，低頻信號(hào)重構(gòu)得到的圖像被壓縮的越??；在Haar小波分解級(jí)數(shù)固定時(shí)，閾值越大，圖像被壓縮的越小。圖像被壓縮的越小，越有利于圖像的傳輸和處理，但是隨著閾值不斷增大，圖像中矩陣“0”的區(qū)域面積也將擴(kuò)大，圖像越來(lái)越模糊，可能造成圖像壓縮后失真。為了保證圖像壓縮后不失真，又盡可能地使得圖像被壓縮的小，需要選擇合適的閾值。本文通過(guò)實(shí)驗(yàn)，對(duì)閾值5～40之間的值分別做了測(cè)試，閾值為5～20時(shí)，在相同的Haar小波分解級(jí)數(shù)下，圖像壓縮效果不明顯；閾值達(dá)到35之后，圖像的壓縮會(huì)出現(xiàn)失真現(xiàn)象。所以本實(shí)驗(yàn)選擇閾值為25，在固定閾值下，對(duì)圖像進(jìn)行Haar小波的一級(jí)、二級(jí)和三級(jí)分解。對(duì)重構(gòu)得到的圖像的圖像進(jìn)行基于形狀模板的匹配，匹配結(jié)果如圖4所示。

圖3 Haar小波變換實(shí)驗(yàn)結(jié)果

(a)原圖 (b)模板

(c)原圖匹配 (d)一級(jí)分解重構(gòu)圖像匹配

(e)二級(jí)分解重構(gòu)圖像匹配 (f)三級(jí)分解重構(gòu)圖像匹配圖4 匹配結(jié)果

從圖4可以看出通過(guò)形狀模板匹配，原圖和在閾值T=25時(shí)的Haar小波分級(jí)得到的圖像都可以識(shí)別出來(lái)，但是匹配所用時(shí)間相差很大，沒(méi)有經(jīng)過(guò)Haar小波壓縮的原圖匹配時(shí)間為94.3ms，接近經(jīng)過(guò)Haar小波三級(jí)分解得到圖像匹配所用時(shí)間的3倍。但是從圖5f中明顯可以看出，Haar小波三級(jí)分解重構(gòu)得到的圖像匹配中有些特征缺失，可能會(huì)影響匹配效果。所以本文對(duì)上述四種類型的圖像做了50次匹配實(shí)驗(yàn)，比較它們的匹配成功率和平均匹配時(shí)間，比較結(jié)果見(jiàn)表1。

表1 不同類型圖像的匹配結(jié)果

從表1可以看出Haar小波三級(jí)分解重構(gòu)得到的圖像匹配時(shí)間最短，而且原圖匹配所用時(shí)間幾乎為Haar小波三級(jí)分解重構(gòu)得到圖像匹配的3倍。但是經(jīng)過(guò)Haar小波三級(jí)分解重構(gòu)得到圖像有些特征缺失，影響了匹配結(jié)果。所以本文為了保證匹配結(jié)果準(zhǔn)確性，又滿足快速匹配的系統(tǒng)要求，選擇閾值T為25，分解級(jí)數(shù)為二的Haar小波變換進(jìn)行壓縮圖像。

采集200幅圖像，進(jìn)行Haar小波圖像壓縮后，先提取標(biāo)準(zhǔn)圖像的模板，然后在光照不均勻、混亂和遮蔽的情況下各做50次實(shí)驗(yàn)，匹配的結(jié)果如圖5所示。運(yùn)算結(jié)果見(jiàn)表2。

(a)標(biāo)準(zhǔn)圖像 (b)標(biāo)準(zhǔn)圖像截取的模板

(c)光照不均勻

(d)混亂 (e)遮擋

圖像類型圖像大小(KB)匹配次數(shù)匹配成功次數(shù)成功率(%)平均匹配時(shí)間(ms)正常505010034．3(c)50499835．6(d)50489634．5(e)505010033．6

從不同環(huán)境中匹配的結(jié)果來(lái)看，對(duì)閾值T為25，分解級(jí)數(shù)為二的Haar小波變換的壓縮圖像進(jìn)行匹配，所用時(shí)間比沒(méi)有壓縮的圖像匹配減少了接近3倍，而且在光照不均勻、混亂和遮蔽的情況下，圖像都能被成功的匹配出來(lái)，匹配的準(zhǔn)確度很高。

5 結(jié)論

本文針對(duì)傳統(tǒng)模板匹配計(jì)算量大和在低對(duì)比度情況下匹配不到目標(biāo)物體問(wèn)題，利用Haar小波變換對(duì)圖像進(jìn)行壓縮處理，把高分辨率的圖像壓縮成分辨率較低的圖像，減少了匹配特征點(diǎn)的計(jì)算，大大提高了匹配速度。通過(guò)計(jì)算相似度量，得到匹配分值，確保匹配不受遮擋、混亂以及光照變化的影響，確保了匹配的準(zhǔn)確性。需要指出的是，合適的閾值是通過(guò)大量的實(shí)驗(yàn)得到的，還需要尋找更好的方法獲得合適的閾值，這將是下一步的研究方向。

[1] 張代林,陳文廣,謝經(jīng)明,等. 基于形狀模板匹配的印刷品缺陷檢測(cè)[J]. 機(jī)械與電子,2013(12): 40-43.

[2] 楊少榮,吳迪靖,段德山.機(jī)器視覺(jué)算法與應(yīng)用[M]. 北京:清華大學(xué)出版社,2009.

[3] ELMUNIM H A, FARAG A A. Shape representation and registration using vector distance functions [C]//CVPRp07: Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2007: 1-8.

[4] 趙振民,彭國(guó)華,符立梅. 基于形狀模板的快速高精度可靠圖像匹配[J]. 計(jì)算機(jī)應(yīng)用,2010,30(2): 441-444.

[5] 劉佳嘉,何小海,陳為龍. 一種結(jié)合小波變換的SIFT特征圖像匹配算法[J]. 計(jì)算機(jī)仿真,2011,28(1):257-260,335.

[6] 梁忠偉,葉邦彥,劉曉初,等. 基于矩陣二階矩和小波分解的紊流圖像融合灰色關(guān)聯(lián)度評(píng)價(jià)[J]. 組合機(jī)床與自動(dòng)化加工技術(shù),2011(8):1-4,8.

[7] DELMASP, FARBGG, SHORINA, et al. Robust leas-t squares image matching in the presence of outliers [C]//CAIP 2007: Proceedings of the12th International Conference on Computer Analysis of Images and Patterns, LNCS 4673. Berlin: Springer, 2007: 776-783.

(編輯 李秀敏)

Fast Image Matching Algorithm Based on Wavelet and Shape Template

BAI Bing-feng, WEN Xiu-lan, ZHANG Zhong-hui

(School of Automation，Nanjing Institute of Technology，Nanjing 211167,China)

According to these problems that the target object is not matched in low-contrast images and large matching calculation is needed in the method of traditional template matching, a fast image matching algorithm based on discrete Haar wavelet transform and shape template is proposed. Firstly, the image is decomposed by Haar wavelet, then the compressed image is reconstructed through the low frequency signal of decomposition to reduce computation cost of image matching and the compressed image is matched by shape template, the algorithm and program of Haar wavelet image compression and shape template match are designed. Finally, a large number of experimental results show that the proposed matching algorithm not only has fast speed and high accuracy, but also the matching results are not influenced by shelter, chaos, the changes of nonlinear illumination and so on. And it is applied to image matting and workpiece recognition in the complex environment.

wavelet transform; template match; image matching

1001-2265(2017)02-0037-04

10.13462/j.cnki.mmtamt.2017.02.010

2016-03-06；

2016-04-10

國(guó)家自然科學(xué)基金項(xiàng)目(51675259)；江蘇省“333人才工程”項(xiàng)目資助：江蘇省普通高校專業(yè)學(xué)位研究生創(chuàng)新計(jì)劃項(xiàng)目(SJLx16_066)

白冰峰(1991—)，男，江蘇徐州人，南京工程學(xué)院碩士研究生，研究方向?yàn)閳D像處理，(E-mail)842344646@qq.com；通信作者：溫秀蘭(1966—)，女，內(nèi)蒙古豐鎮(zhèn)人，南京工程學(xué)院教授，博士，研究方向?yàn)橛?jì)量與測(cè)試技術(shù)、智能計(jì)算、機(jī)器視覺(jué)及其應(yīng)用，(E-mail)zdhxwxl@njit.edu.cn。

TH161;TG506

A