基于頻域分析的圖像匹配定位算法的研究

楊喜東

（西南科技大學(xué)信息工程學(xué)院，四川 綿陽621010）

0 引 言

圖像定位匹配比較一直是圖像檢測(cè)中的關(guān)鍵問題，經(jīng)常用于印刷、影印等行業(yè)的產(chǎn)品自動(dòng)化質(zhì)量檢測(cè)系統(tǒng)中。目前的質(zhì)量檢測(cè)系統(tǒng)一般將標(biāo)準(zhǔn)模板圖像與實(shí)際產(chǎn)品的采集圖像進(jìn)行匹配，通過檢測(cè)比較的結(jié)果來確定生產(chǎn)線上的產(chǎn)品是否符合質(zhì)量要求，但缺點(diǎn)在于定位精度有限，在提高精度的情況下速度又非常低。針對(duì)這些缺陷，本文提出了一種基于傅里葉變換和積分圖的圖像匹配定位算法，旨在解決以往圖像定位匹配精度和速度的問題，從而提高工業(yè)生產(chǎn)線上自動(dòng)化檢測(cè)的效率。

1 算法的提出

1.1 基于頻域的抗旋轉(zhuǎn)圖像匹配算法

該算法是采用頻域匹配的中間結(jié)果即圖像的功率譜求旋轉(zhuǎn)角。具體圖像旋轉(zhuǎn)校正方法如下：

設(shè)圖像旋轉(zhuǎn)變化角θ范圍為［θmin，θmax］，根據(jù)旋轉(zhuǎn)校正精度的具體要求，確定θ角改變的步長為△θ，則有θi＝θmin＋i△θ（i＝0，1，2，...，n）。其中：n＝（θmax－θmin）／△θ，則有：

式中，t（u，v）為模板圖T（x，y）的功率譜；sθi（u，v）為搜索圖S（x，y）的功率譜s（u，v）相對(duì)于其中心旋轉(zhuǎn)θ角后得到的新的功率譜，則滿足D（φ）＝ min｛D（θ）｝的角即為所求的旋轉(zhuǎn)角。但是此方法無法正確估計(jì)旋轉(zhuǎn)角并且信噪比無法達(dá)到最大，所以增加帶通濾波器，同時(shí)對(duì)圖像作加權(quán)、選擇候選校正角及圖像濾波處理。實(shí)際在運(yùn)用時(shí)一般將匹配分成兩個(gè)步驟：粗匹配和精匹配。其具體流程圖分別如圖1、圖2所示。

1.2 相關(guān)函數(shù)傅里葉變換的匹配算法

利用二維傅里葉變換進(jìn)行圖像匹配，圖像匹配的互相關(guān)函數(shù)定義如下：

式中，X＊（m，n）表示X（m，n）的復(fù)共軛，在圖像處理中，函數(shù)是實(shí)函數(shù)。所以X＊（m，n）＝X（m，n），卷積理論同樣適用。則傅里葉變換對(duì)

成立。該變換對(duì)說明了兩個(gè)函數(shù)的空域相關(guān)可以由X＊（u，v）Y（u，v）的傅里葉反變換得到，則頻域的相關(guān)簡(jiǎn)化也可以簡(jiǎn)化為空域的相乘。則

圖1 抗旋轉(zhuǎn)粗匹配流程圖

對(duì)x補(bǔ)零使其為2 M×2 N矩陣，則上式可以變換為：

圖3 互相關(guān)匹配流程圖

圖2 抗旋轉(zhuǎn)精匹配流程圖

1.3 MATLAB實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)選取的是大小為550×578，格式為b mp格式的一幅圖像，然后在該圖上截取一幅較小的圖片為模板圖片。匹配后用紅色的方框在待匹配的圖像中將模塊圖標(biāo)識(shí)出來。下面用三種方式進(jìn)行模板的匹配定位。通過MATLAB編程實(shí)現(xiàn)三種常見的圖像匹配算法，通過比較，分析各種算法的優(yōu)缺點(diǎn)如表1所示。

表1 匹配定位比較表

2 算法的優(yōu)化

針對(duì)傳統(tǒng)相關(guān)匹配計(jì)算復(fù)雜度大的缺點(diǎn)，基于快速傅里葉變換（FFT）和積分圖提出了一種快速相關(guān)匹配算法，大大降低了傳統(tǒng)相關(guān)匹配的計(jì)算復(fù)雜度。同時(shí)，該算法在任意搜索位置提供了與傳統(tǒng)相關(guān)匹配完全一致的計(jì)算結(jié)果，天然地繼承了傳統(tǒng)相關(guān)匹配抗干擾能力強(qiáng)、定位準(zhǔn)確度高的優(yōu)點(diǎn)。

2.1 優(yōu)化過程

設(shè)模板圖像為T，大小為m×n，基準(zhǔn)圖像（待搜索大圖）為S，大小為M×N，且m≤M，n≤N。設(shè)S中以（x，y）為左上角，點(diǎn)大小為m×n的子塊為Sxy，通過對(duì)相關(guān)系數(shù)矩陣ρ（x，y）的分析，判斷兩幅圖是否匹配。其中

其中R2（x，y）和R3（x，y）分別為子塊Sxy灰度值及其能量的積分，本算法利用積分圖對(duì)其進(jìn)行快速計(jì)算。對(duì)任意圖像g，其積分圖在（x，y）處的灰度值ii（x，y）為圖像g中該點(diǎn)左上方所有像素灰度值的積分，即：

該積分圖可以由下面兩個(gè)公式對(duì)原圖g一次掃描得到

式中，cii（x，y）表示點(diǎn)（x，y）所在列縱坐標(biāo)不大于y的所有像素灰度值的積分，即

則優(yōu)化后的快速相關(guān)匹配算法流程圖如圖4所示。

2.2 優(yōu)化后的特點(diǎn)

（1）計(jì)算復(fù)雜度降低

傳統(tǒng)相關(guān)匹配的計(jì)算量主要取決于占主導(dǎo)地位的乘法運(yùn)算次數(shù)。對(duì)任意搜索位置（x，y），基準(zhǔn)圖像遍歷搜索共需計(jì)算（M－m＋1）（N－n＋1）個(gè)搜索位置，從而傳統(tǒng)相關(guān)匹配所需乘法運(yùn)算次數(shù)為

圖4 利用積分圖匹配算法流程圖

其計(jì)算量近似與模板圖像大小和基準(zhǔn)圖像大小的乘積成正比，隨二者的增大而快速增加。而算法優(yōu)化后的快速相關(guān)匹配算法由于積分圖僅涉及有限次的加法運(yùn)算，因此算法復(fù)雜度主要由FFT及IFFT決定。典型的FFT及IFFT所需乘法運(yùn)算次數(shù)均約為2 MN l og2（M／N），R1（x，y）共需計(jì)算一次 FFT和一次IFFT，從而其所需乘法運(yùn)算次數(shù)為

本文算法的計(jì)算復(fù)雜度與模板圖像大小無關(guān)，其計(jì)算量與傳統(tǒng)相關(guān)匹配的計(jì)算量之比為

從上式可以看出，隨模板圖像大小m的增大，本文算法與傳統(tǒng)相關(guān)匹配計(jì)算量之比快速降低，即模板圖像和基準(zhǔn)圖像尺寸越大，本文算法相對(duì)傳統(tǒng)相關(guān)匹配的優(yōu)勢(shì)越大。

（2）高精度和抗干擾能力

為了驗(yàn)證優(yōu)化后算法的有效性，采用MATLAB對(duì)優(yōu)化后算法進(jìn)行了編程實(shí)現(xiàn)，并將結(jié)果與前面的傳統(tǒng)匹配算法進(jìn)了對(duì)比。圖5是直接對(duì)待匹配圖進(jìn)行匹配，并在待匹配圖中用紅色矩形框?qū)⒍ㄎ粓D像標(biāo)示出來。

圖5 利用積分圖匹配定位效果圖

從圖中可以看出匹配所用的時(shí)間在0.39 s左右，而且匹配的精度很高。由此可以得出基于傅里葉變換和積分圖的匹配定位算法具有很好效率，并且有很好的抗干擾能力。

3 結(jié) 論

如何準(zhǔn)確、快速的進(jìn)行圖像匹配是當(dāng)前許多領(lǐng)域關(guān)注的熱點(diǎn)。然而由于空域算法的復(fù)雜性，很多空域的匹配方法都很難在實(shí)際中應(yīng)用，因此本文闡述的基于頻域的圖像匹配方法體現(xiàn)出了一定的理論意義和實(shí)際價(jià)值。同時(shí)解決了傳統(tǒng)的圖像定位匹配中定位精度和速度不能兼顧的缺陷。當(dāng)然圖像匹配是一個(gè)復(fù)雜和不斷完善的過程，在今后的研究中，該算法還有一些值得改善和優(yōu)化的地方，如擴(kuò)大算法的適用范圍和通用性、提高抗干擾能力、減少圖像匹配時(shí)間等，但隨著社會(huì)經(jīng)濟(jì)發(fā)展的不斷進(jìn)步，圖像匹配技術(shù)必將擁有更廣闊的發(fā)展前景。

［1］ 王小睿，吳信才.遙感多圖像的自動(dòng)匹配技術(shù)［J］.中國圖形圖像學(xué)報(bào)，1997，10（2）：735－738.

［2］ 孫 瑾，顧宏斌，秦小麟.一種魯棒型 Hausdorff距離圖像匹配方法［J］.中國圖象圖形學(xué)報(bào)，2008，4：761－767.

［3］ 李曉明，張福繼.一種基于學(xué)習(xí)的自動(dòng)圖像匹配檢驗(yàn)方法［J］.自動(dòng)化學(xué)報(bào)，2008，1：7－13.

［4］ 鄧通軍.旋轉(zhuǎn)圖像匹配新算法［J］.測(cè)繪與空間地理信息，2007，8：104－108.

［5］ 李 卓，邱慧娟.基于相關(guān)系數(shù)的快速圖像匹配研究［J］.北京理工大學(xué)學(xué)報(bào)，2007，（27）11：998－1000.

［6］ VIOLAP，JONESM .Rapid object detection using a boosted cascade of simple features［C］.IEEE Conference on Co mputer Vision and Patter n Recognition，2001，511－518.