基于NCC的圖像匹配快速算法

摘 要: 在圖像匹配過程中，針對傳統歸一化積相關(NCC)算法計算量大的問題，提出一種對NCC進行改進的圖像匹配快速算法。該算法首先使用差分求和定理改造NCC相似度量函數，以降低匹配計算量。然后提出模板區域分割，設定閾值，進一步去除大量不必要的計算，優化匹配搜索過程，實現了快速匹配。實驗結果證明，與傳統的匹配算法相比，在保證精度的前提下，計算復雜度大大降低。關鍵詞:圖像匹配; 歸一化積相關; 相似度函數; 區域分割; 差分

中圖分類號:TN911-34; TP391 文獻標識碼:A

文章編號:1004-373X(2010)22-0107-03

Fast Algorithm for Image Matching Based onNCC

YANG Tong-yu， PENG Guo-hua

(School of Science，Northwestern Polytechnical University，Xi’an 710129， China)

Abstract: In the image matching process， the computational complexity was the major problem of the traditional NCC (normalized product correlation) algorithm. An image matching fast algorithm for improving the NCC is presented. First， it combined with the summation theorem of difference to improve the NCC for reducing the amount of calculation of matching. Second， it showed region segmentation for the template and then set threshold to get rid of some calculation to achieve rapid matching. The experimental results prove that the computational complexity is reduced greatly compared with the traditional matching algorithm by the premise of the precision，.

Keywords: image matching; normalized product correlation; similarity function; region segmentation; difference

0 引 言

圖像匹配問題是計算機視覺、圖像處理領域中的基本問題，有兩種對應的模型:一是兩幅(或者多幅)來自不同傳感器、不同視角或不同時間的圖像需找出對應關系，經過匹配步驟可得出兩幅圖像的差別所在，為下一步處理作基礎;二是根據已知的圖像模式在另一幅圖像中搜索類似模板的目標，即模板匹配。圖像匹配技術是數字圖像處理領域的一項重要研究，已在虛擬現實場景、航空航天遙感測量、醫學影像分析、光學和雷達跟蹤、景物制導等領域有著重要的應用價值。已有的圖像匹配算法可分為兩類:基于像素灰度值的匹配和基于圖像幾何特征的匹配。

所有的基于像素灰度值匹配算法的計算量等于模板運算量和搜索位置數之積。故提高匹配速度的角度有:

(1) 減少每個位置處模板相似度計算的運算量;

(2) 改變搜索策略，減少搜索像素點或在搜索圖像中的搜索位置數。模板匹配的傳統算法[1]有:MAD[2](平均絕對差)算法，歸一化積相關[3-5](NCC)算法，序貫相似性檢測法[6](SSDA)，圖像灰度值編碼[7](PFC)算法等。其中MAD算法計算過程非常簡單，無需復雜的乘除法運算，但是對噪聲比較敏感，在加噪聲的情況下，匹配準確率隨著信噪比的增加而減少; SSDA算法雖然相對MAD算法速度提高了很多，但是其精度低，匹配效果不好，而且易受噪聲影響，一旦進入信息貧乏的區域，會導致誤匹配率的上升;PFC算法無法適應圖像局部光照的非線性變化，匹配容易錯誤;NCC算法的優點是抗白噪聲干擾能力強，且在灰度變化及幾何畸變不大的情況下精度很高，它的這種優點非常突出，但該方法受局部光照變化的影響，且匹配速度較慢。針對該問題，本文在保證匹配精度的前提下，提高NCC匹配算法的速度，增強算法對實際應用的適應性。

文獻[8]提出的NCC快速模板匹配算法，結合文獻[9]的差分求和定理對每個位置處的模板計算進行改進，減少了計算量。本文在文獻[8]的基礎上，從上面所述的角度(2)，改變搜索策略，即提出模板分塊匹配策略，減少不必要的運算，進一步優化算法。該算法能適應一定光照的變化，適合任何形狀的匹配模型，相對于文獻[8]的匹配算法大大提高了速度。

1 NCC匹配

1.1 NCC原理

NCC匹配算法是一種經典的匹配算法。通過計算模板圖像和搜索圖像的互相關值確定匹配的程度。互相關值最大時的位置決定了模板圖像在搜索圖像中的位置。假設搜索圖像S的尺寸為M×M，模板T的尺寸為N×N，其中M>N，M，N代表圖像像素大小。

模板T在圖像S上平移，模板所覆蓋的子圖記作Si，j，(i，j)為子圖左上角頂點在搜索圖S中的坐標。在實際匹配應用中，搜索圖和模板的相似性通過度量函數來度量，則歸一化積相關匹配度量定義為:

R(i，j)=∑Mm=1∑Nn=1Si，j(m，n)T∑Mm=1∑Nn=1[Si，j(m，n)-Si，j]2×∑Mm=1∑Nn=1[T(m，n)-T]2(1)

NCC算法具有很高的準確性、適應性， 對圖像灰度值線性變換具有“免疫性”， 即所求的NCC值不受灰度值的線性變換的影響， 但計算耗費過于龐大，導致匹配效率低，所以需要一種新的快速的匹配算法。

1.2 改進NCC

1.2.1 差分求和定理

文獻[9]中提出差分求和定理，即設有兩個大小同為N的一維數組f(x) 和g(x)，x= 1，2，…，K，則這兩個數組的乘積等于將其中一個數組f(x)差分，另一個數組g(x)累進求和后的乘積，即:

∑Kx=1f(x)g(x)=∑Kx=1F(x)G(x)(2)

式中:

F(x)=f(x)-f(x+1)(3)

G(x)=G(x-1)-g(x+1)(4)

G(0)=0(5)

f(K+1)=0(6)

1.2.2 改進NCC算法

將上述差分求和定理用于式(1)。T(m，n)為模板上(m，n)位置點的像素值，其中0≤m≤N，0≤n≤N，將模板內的所有點保存為一維數組f(x)，子圖內對應模板的點保存為g(x)。令F(x)為對f(x)的差分數組，即F(x)=f(x)-f(x+1)，并根據式(5)對子圖g(x)累進求和得數組G(x)。

這樣就可以把模板T和子圖Si，j的乘積根據式(3)轉化為對F(x)和G(x)的乘積運算。由于在灰度變化不大的圖像中，相鄰像素的灰度值非常相近，這樣差分后的數組會產生大量的0，1或-1，而0，1，-1的乘法運算可以忽略。

在實際的模板匹配中，模板是固定的，故對其進行差分的運算只需進行1次，耗時很少。此外，在模板中相鄰像素間同樣存在大量的相同像素值，差分后可得到大量0，1和-1，從而大大地提高了匹配速度。

2 區域分割進一步改進

第1.2節為文獻[8]從引言中提到的角度(1)，即從減少每個位置處模板相似度計算的運算量對NCC算法進行改進，效率有了很大程度的提高;下面本文針對角度(2)，即通過改變搜索策略減少像素數量，來進一步提高匹配效率。本文提出區域分割的方法，也即模板分塊匹配，通過設定閾值，對分割后的小區域進行計算、比較，排除掉大量不符合要求的點，從而進一步提高匹配速度。區域分割法是用如圖1所示的分割圖來代替原來的模板，通過計算R1~R4四個小矩形的相關性來判斷匹配區域的位置。

圖1 分割模板

具體實現步驟如下:

(1)設定一個常數為最大相似性度量Max R=0.98，其中R為相關系數。

(2) 在搜索圖上，采用上述改進的NCC匹配算法，計算模板塊R1的相似度。如果R1的相似度小于Max R，完成本步驟后轉步驟(6);否則轉步驟(3)。

(3)計算模板塊R2的相似度。如果R2相似度小于Max R，完成本步驟后轉步驟(6);否則轉步驟(4)。

(4) 計算模板塊R3的相似度。如果R3相似度小于Max R，完成本步驟后轉步驟(6);否則轉步驟(5)。

(5)計算模板塊R4的相似度。如果R4相似度也大于Max R，即找到匹配目標。否則， 在完成本步驟后轉步驟(6)。

(6)結束。

實驗結果證明， 在保證圖像質量的前提下， 通過模板分塊， 減少了匹配時間， 準確地找到匹配的目標。該搜索策略能夠大大提高匹配速度， 同時不影響圖像質量， 較好地解決了匹配質量與運算量之間的矛盾。

3 實驗結果與分析

實驗運行環境為2.40 GHz Intel處理器，4 GB內存，Visual C++ 6.0。采用448×434的Lena圖像(如圖2(a)所示)做搜索圖，從搜索圖上任意位置取一塊子圖作為模板(如圖2(b)，(c)所示)，分別用傳統的NCC算法，本文改進的快速算法進行模板匹配，運算結果如表1所示。

圖2 匹配圖像

從表1數據分析可得到結論:本文算法在保證精度的前提下，時間遠遠小于傳統算法。如表2所示，在灰度模板的情況下，同樣一副圖像，模板尺寸越大，則進行模板匹配運算的量也越大。特別，當模板較大時更突顯本文算法的優勢。

表1 兩種算法的結果比較

算法模板圖像時間 /s 檢測位置

本文算法57×48448×4340.250(201，198)

傳統算法57×48448×43413.224(201，198)

當模板變小時，兩者的時間都在驟減，但即使是在模板為10×10時，本文算法時間仍然遠小于傳統算法。當搜索圖和模板圖皆為二值圖時，本文算法匹配速度更加快，傳統算法跟圖像類型無關，只和大小有關。故對于越簡單，灰度值變換范圍越小的圖像，本文算法越快，更能突顯其優勢。

4 結 語

本文通過采用模板分塊匹配策略對文獻[8]中經典的NCC算法進行了進一步改進，提出基于NCC的圖像匹配快速算法。在保持原有的高精度的前提下，相對于文獻[8]中的算法，速度上有了很大的提高;實時性強，可用于圖像實時處理。但由于文獻[8]的NCC算法局限于灰度變化不大的圖像，使適用范圍受到了一定的限制，在這方面可以做進一步的研究。另外，在圖像處理領域采用進行并行處理[10]是一個很好的切入點。

表2 不同類型圖像兩種算法的比較結果

模板類型模板大小本文算法 /s傳統算法 /s準確率

灰度模板

80×800.95421.235100%

57×480.25013.224100%

10×100.1079.621100%

二值模板

80×800.58721.554100%

57×480.13612.894100%

10×100.0759.541100%

參考文獻

[1]劉寶生.幾種經典相似性度量的比較研究[J].計算機應用研究，2006(11):1-3.

[2]李俊山，沈緒榜.圖像分塊平均絕對差匹配并行算法[J].小型微型計算機系統，2002，23(6):695-698.

[3]孫祖鑫，吳強.一種基于TS201的歸一化互相關快速算法[J].計算機應用技術，2010(11):125-127.

[4]韓冰，王永明，劉楊，等.一種基于積分圖像的快速歸一化積相關算法[J].彈箭與制導學報，2009，29(5):283-286.

[5]郭偉，趙亦工，謝振華. 一種改進的紅外圖像歸一化互相關匹配算法[J].光子學報，2009，38(1):189-193.

[6]王立新，劉彤宇，李陽.SSDA圖像匹配算法的研究及實現[J].光電技術應用，2005，20(3):53-55.

[7]李強，張鈸.一種基于圖像灰度的快速匹配算法[J].軟件學報，2006，17(2):217-222.

[8]劉錦峰.圖像模板匹配快速算法研究[D].長沙:中南大學，2007.

[9]王冰.基于差分矩因子的灰度圖像矩快速算法[J].計算機學報，2005，28(8):1367-1375.

[10]李俊山.歸一化積相關圖像匹配算法中的圖像分塊并行處理方法[J].小型微型計算統，2004，25(11):1986-1989.