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

楊喜東

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

0 引 言

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

1 算法的提出

1.1 基于頻域的抗旋轉圖像匹配算法

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

設圖像旋轉變化角θ范圍為［θmin，θmax］，根據旋轉校正精度的具體要求，確定θ角改變的步長為△θ，則有θ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）相對于其中心旋轉θ角后得到的新的功率譜，則滿足D（φ）＝ min｛D（θ）｝的角即為所求的旋轉角。但是此方法無法正確估計旋轉角并且信噪比無法達到最大，所以增加帶通濾波器，同時對圖像作加權、選擇候選校正角及圖像濾波處理。實際在運用時一般將匹配分成兩個步驟：粗匹配和精匹配。其具體流程圖分別如圖1、圖2所示。

1.2 相關函數傅里葉變換的匹配算法

利用二維傅里葉變換進行圖像匹配，圖像匹配的互相關函數定義如下：

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

成立。該變換對說明了兩個函數的空域相關可以由X＊（u，v）Y（u，v）的傅里葉反變換得到，則頻域的相關簡化也可以簡化為空域的相乘。則

圖1 抗旋轉粗匹配流程圖

對x補零使其為2 M×2 N矩陣，則上式可以變換為：

圖3 互相關匹配流程圖

圖2 抗旋轉精匹配流程圖

1.3 MATLAB實驗仿真與分析

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

表1 匹配定位比較表

2 算法的優化

針對傳統相關匹配計算復雜度大的缺點，基于快速傅里葉變換（FFT）和積分圖提出了一種快速相關匹配算法，大大降低了傳統相關匹配的計算復雜度。同時，該算法在任意搜索位置提供了與傳統相關匹配完全一致的計算結果，天然地繼承了傳統相關匹配抗干擾能力強、定位準確度高的優點。

2.1 優化過程

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

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

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

式中，cii（x，y）表示點（x，y）所在列縱坐標不大于y的所有像素灰度值的積分，即

則優化后的快速相關匹配算法流程圖如圖4所示。

2.2 優化后的特點

（1）計算復雜度降低

傳統相關匹配的計算量主要取決于占主導地位的乘法運算次數。對任意搜索位置（x，y），基準圖像遍歷搜索共需計算（M－m＋1）（N－n＋1）個搜索位置，從而傳統相關匹配所需乘法運算次數為

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

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

本文算法的計算復雜度與模板圖像大小無關，其計算量與傳統相關匹配的計算量之比為

從上式可以看出，隨模板圖像大小m的增大，本文算法與傳統相關匹配計算量之比快速降低，即模板圖像和基準圖像尺寸越大，本文算法相對傳統相關匹配的優勢越大。

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

為了驗證優化后算法的有效性，采用MATLAB對優化后算法進行了編程實現，并將結果與前面的傳統匹配算法進了對比。圖5是直接對待匹配圖進行匹配，并在待匹配圖中用紅色矩形框將定位圖像標示出來。

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

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

3 結 論

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

［1］ 王小睿，吳信才.遙感多圖像的自動匹配技術［J］.中國圖形圖像學報，1997，10（2）：735－738.

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

［3］ 李曉明，張福繼.一種基于學習的自動圖像匹配檢驗方法［J］.自動化學報，2008，1：7－13.

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

［5］ 李 卓，邱慧娟.基于相關系數的快速圖像匹配研究［J］.北京理工大學學報，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.