圖像匹配綜述

摘 要：主要從圖像匹配技術(shù)的概念、一般性描述及圖像匹配技術(shù)的技術(shù)分類對(duì)圖像匹配進(jìn)行描述，在圖像匹配技術(shù)的分類中，對(duì)各個(gè)方法的優(yōu)缺點(diǎn)進(jìn)行了詳細(xì)的說明。

關(guān)鍵詞：圖像匹配；一般性描述；分類

隨著科學(xué)的飛躍發(fā)展，近年來圖像匹配技術(shù)在許多方面有著非常重要的應(yīng)用，尤其是在醫(yī)學(xué)方面、運(yùn)動(dòng)物體的跟蹤、計(jì)算機(jī)視覺、天氣預(yù)報(bào)以及各種資源分析等方面運(yùn)用非常廣泛。本文對(duì)圖像匹配進(jìn)行綜述，以便讀者對(duì)其有個(gè)粗略的了解。

一、圖像匹配的概念

圖像匹配的概念：在兩幅圖像中，從一幅圖像中尋找與另一幅具有相同或相似的過程。

二、圖像匹配的一般性描述

圖像匹配可以描述為：假設(shè)給定大小分別為m×m和n×n像素圖像h1（x，y）及h2（x，y），它們的映射關(guān)系為：

h2（x，y）=g（h1（a（x，y）），（2-1）

式（2-1）中，符號(hào)a是二維或者多維的幾位變換（x′，y′）=a（x，y），符號(hào)g為一維或者多維圖像的亮度變換。匹配圖像問題的實(shí)質(zhì)是尋找兩幅圖像的最佳幾何變換a和亮度變換，最終的目的是使預(yù)先定義的那種測(cè)度為最小值或者達(dá)到最大值，以達(dá)到兩幅待匹配圖像的匹配。匹配圖像的關(guān)鍵主要是下列因素選擇的一個(gè)組合：待匹配圖像的特征空間、相似度、幾何變換類型和參數(shù)的搜索策略。

下表2-1給出了待匹配圖像的特征空間、相似度及搜索策略的幾個(gè)主要要素及它們對(duì)應(yīng)的內(nèi)容。

表2-1 待圖像匹配的三個(gè)關(guān)鍵因素

三、圖像匹配技術(shù)的分類

圖像匹配技術(shù)算法分類很多，但都遵守這樣的基本原則：（1）算法必須是有效的。（2）算法必須是穩(wěn)定的，當(dāng)待匹配的圖像發(fā)生旋轉(zhuǎn)、尺度伸縮及被遮擋時(shí)，此種算法仍能使用。（3）算法必須是快速的。

1.基于圖像灰度相關(guān)的匹配方法

基于圖像灰度匹配算法是利用整幅圖像的灰度信息進(jìn)行匹配的方法。

幾種常見的算法有平均絕對(duì)差算法、歸一化積相關(guān)算法、互信息匹配算法、傅立葉相關(guān)算法等。下面簡(jiǎn)要介紹以下這幾種算法：

（1）平均絕對(duì)差算法

平均絕對(duì)差算法是這樣定義的：

d（x，y）= s（i+x，j+y）-T（i，j）（3-1）

其中，0≤x≤M-m+1；0≤y≤N-n+1。d（x，y）為度量函數(shù)在偏移量（x，y）的度量值，當(dāng)d（x，y）為最小時(shí)是最佳的匹配位置。它的優(yōu)點(diǎn)為：計(jì)算比較簡(jiǎn)單；不足是：對(duì)噪聲比較敏感，噪聲越多正確匹配的幾率越小。

（2）歸一化積相關(guān)算法

歸一化積相關(guān)算法是一種經(jīng)典的基于灰度的相關(guān)匹配算法。它的定義如下：

d（x，y）= （3-2）

在（3-2）中，0≤x≤M-m+1；；0≤y≤N-n+1。d（x，y）為度量函數(shù)在偏移（x，y）的度量值，當(dāng)d（x，y）為最大時(shí)是最佳的匹配位置。它的優(yōu)點(diǎn)是：抗白噪聲非常強(qiáng)，且在幾何畸變和灰度變化不大時(shí)，圖像的匹配精度很高。

（3）互信息匹配算法

互信息匹配算法是近年來才提出的匹配方法，它是基于像素相似性的匹配算法，這種算法把像素灰度信息的統(tǒng)計(jì)特征直接作為匹配的依據(jù)，省去了對(duì)圖像進(jìn)行分割和特征提取過程，它的好處是不但避免了在圖像分割或特征提取中造成精度損失，而且便于進(jìn)行回溯式的研究。

把參考圖和輸入圖的灰度值分別看作是隨機(jī)的兩個(gè)變量A和B，它們對(duì)應(yīng)的概率密度分別是P（A）及P（B），那么隨機(jī)變量A和B的互信息可以用下式來表示：

MI（A，B）=H（B）-H（B/A）=H（A）+H（B）-H（A，B）（3-3）

其中，H（A）=-EA（log（P（A）））。

優(yōu)點(diǎn)是匹配算法對(duì)光照的改變不靈敏；缺點(diǎn)是計(jì)算量大，并且要求圖像間的重疊區(qū)域比較大。

（4）傅立葉相關(guān)算法

假設(shè)待匹配的參考圖像I1（x，y）和輸入圖像I2（x，y）的傅立葉變換是F1（U，V）與F2（U，V）。如果這兩幅圖像之間存在一個(gè)平移變量（m，n），它們之間的數(shù)學(xué)關(guān)系可以用下式表示：

I1（x，y）=I2（x-m，y-n）（3-4）

相應(yīng)的，它們對(duì)應(yīng)的傅立葉變換存在下列關(guān)系：

F1（U，V）=e-j （mu+nj）F2（U，V）（3-5）

從式（3-4）和式（3-5）可以看出：當(dāng)兩幅待匹配的圖像之間只存在平移關(guān)系時(shí)，它們對(duì)應(yīng)的傅立葉變換的幅值具有相同的值；當(dāng)待匹配的兩幅圖像只存在一個(gè)相位差時(shí)，相位差的功率譜可以表示為：

=ej （um+vn）（3-6）

式（3-6）中*是復(fù)共軛的運(yùn)算符號(hào)。再對(duì)式（3-6）作傅立葉反變換，同大多數(shù)頻域匹配算法一樣之處在于，由于涉及了空間域和頻域的相互轉(zhuǎn)換，因此這種情況相對(duì)復(fù)雜。雖然匹配也能達(dá)到比較高的精度，但它對(duì)兩幅待匹配圖像之間的幾何變形和輻射畸變都有比較高的要求，基于以上的分析可以看出，傅立葉變換應(yīng)用的范圍相對(duì)來說較窄。

2.基于圖像特征的匹配算法

鑒于上述圖像灰度相關(guān)匹配算法的不足之處，人們提出了一種新的算法，即基于特征的匹配算法。其算法是提取各類圖像中在各種情況下都能夠保持不變的特征。

圖像特征匹配可以理解為在提取的特征點(diǎn)之間用某種映射來建立某種對(duì)應(yīng)關(guān)系的過程。即設(shè)在圖像A中提取出來的特征點(diǎn)數(shù)為m個(gè)，在圖像B中提取出來的特征點(diǎn)數(shù)有n個(gè)，并且m不等于n。其中，k是待匹配圖像共同擁有的特征點(diǎn)個(gè)數(shù)，則特征匹配要解決的問題就是如何確定圖像A和圖像B中這k對(duì)對(duì)應(yīng)的點(diǎn)。

幾種常用的匹配方法，它們分別是關(guān)于圖像的Hausdorff距離匹配法、金字塔小波匹配方法、最小均方誤差法等。

（1）Hausdorff距離匹配算法

Hausdorff距離匹配算法反映的是兩個(gè)集合之間的關(guān)系，它的定義通常是指待匹配圖像的兩個(gè)點(diǎn)集之間的最小距離或者是兩個(gè)點(diǎn)集的最大距離。假設(shè)兩個(gè)有限點(diǎn)集為A={a1，a2，…ap}與B={b1，b2，…bp}。那么這兩個(gè)點(diǎn)集A、B之間的Hausdorff距離為：

H（A，B）=max（h（A，B），h（A，B））（3-7）

其中，h（A，B）= ||a-b||，|| ||稱為某種距離的范數(shù)。若h（A，B）=d，則在點(diǎn)集A中的每一個(gè)點(diǎn)到點(diǎn)集B中的距離至少存在有一個(gè)點(diǎn)的距離不大于d，并且點(diǎn)集A中至少有一個(gè)點(diǎn)，這個(gè)點(diǎn)的距離恰好等于d。那么這些點(diǎn)就稱為最不匹配的點(diǎn)，從而被舍去。由此可見，Hausdorff距離衡量的是兩幅待匹配圖像的兩個(gè)點(diǎn)集的不相似程度。當(dāng)然它也可以衡量?jī)蓚€(gè)點(diǎn)集的相似程度，當(dāng)它作為相似性度量時(shí)，它的最小值就為匹配的最好位置。圖像的Hausdorff距離算法與其他二值圖像匹配算法不同的是：它不要求待匹配圖像中的匹配點(diǎn)對(duì)是一一對(duì)應(yīng)的，點(diǎn)集A中可以有一個(gè)或者是多個(gè)點(diǎn)與點(diǎn)集B中的同一個(gè)點(diǎn)對(duì)應(yīng)。它的優(yōu)點(diǎn)是圖像匹配速度快、匹配精度高。其缺點(diǎn)是當(dāng)兩幅待匹配的圖像之間存在旋轉(zhuǎn)問題時(shí)，它的克服噪聲的能力就比較差了。尤其是當(dāng)兩幅待匹配圖像之間的旋轉(zhuǎn)角度大于3-5時(shí)，兩幅圖像的匹配準(zhǔn)確率就大大下降了，匹配出來的結(jié)果有時(shí)甚至是錯(cuò)誤的。此外，圖像的Hausdorff距離利用的是特征匹配算法，如果提取出來的特征點(diǎn)不是很明顯時(shí)，也無法很好地解決圖像的匹配問題。

（2）金字塔小波匹配算法

圖像的金字塔小波匹配算法的另一個(gè)名字叫做圖像的分層匹配算法，它是根據(jù)人們先粗后細(xì)搜索事情的習(xí)慣逐步形成的。它可以分為以下幾步：第一步，對(duì)待匹配的圖像要先進(jìn)行分層預(yù)處理，在尺寸最小的圖像處或者分辨率最低的圖像上進(jìn)行全局搜索，快速準(zhǔn)確地找到待匹配圖像的特征點(diǎn)；第二步，以第一步匹配的結(jié)果為出發(fā)點(diǎn)，在較大尺寸的圖像上對(duì)少數(shù)有可能匹配的位置上進(jìn)行匹配；以此類推，最后一步就找到了圖像之間真正要匹配的那些特征點(diǎn)。金字塔小波匹配算法的優(yōu)點(diǎn)是：計(jì)算量較少，計(jì)算的速度就會(huì)比較高。但有一個(gè)前提條件就是提取出來的特征點(diǎn)必須是穩(wěn)定的，即具有較好的魯棒性。但在實(shí)際提取的過程中，具有這樣特點(diǎn)的特征點(diǎn)集合很難被提取到。因此，金字塔小波匹配算法的應(yīng)用在一定程度上受到了限制。

（3）最小均方誤差匹配算法

最小均方誤差匹配算法是利用待匹配圖像之間相互對(duì)應(yīng)的特征點(diǎn)來進(jìn)行的，通過對(duì)應(yīng)特征點(diǎn)的變換方程求解過程來計(jì)算圖像間的變換參數(shù)。如果兩幅待匹配圖像之間存在這樣的仿射變換（x，y）→（x′，y′），則它們的變換方程為：

x′y′=sxycosx sinx-sinx cosx+txty

=x y 1 0y -x 0 1（ssinx s cosx tx ty）T（3-8）

其中，用向量β=（ssinx scosx tx ty）T來表示仿射變換參數(shù)，所以對(duì)于給定的n對(duì)對(duì)應(yīng)的特征點(diǎn)（n>3）構(gòu)造出相應(yīng)的點(diǎn)坐標(biāo)矩陣為：

Y=（x1y1… …xnyn）T

X=x1 y1 1 0y1 -x1 0 1… … … …xn yn 1 0yn -xn 0 1（3-9）

利用最小均方誤差的原理來求出ET=（Y-Xβ）T（Y-Xβ），從而得到相應(yīng)的參數(shù)向量，它的方程為β=（XTX）-1XTY。

總之，每種算法都有其優(yōu)點(diǎn)和不足之處，具體選擇哪種算法還需要根據(jù)具體情況而定。

參考文獻(xiàn)：

[1]郭雷，李暉暉.圖像融合[M].北京：電子工業(yè)出版社，2008.

[2]鄭志杉，葉中付.基于相位相關(guān)的圖像匹配算法[J].數(shù)據(jù)采集與處理，2006，vol21（4）.

[3]李小明，趙訓(xùn)坡.基于Fourier-Mellin變換的圖像配準(zhǔn)方法及應(yīng)用拓展[J].計(jì)算機(jī)學(xué)報(bào)，2006，vol23（9）.

[4]comaniciu D Ramesh V，meer P.Kerner-based object tracking.IEEE Transection on Fatter Analysis and Machine Intelligence，2003：337-340.

[5]Daubechies I.The wavelet transform time-frequency localization and signal analysis. IEEE Transaction on information treory，1990，vol36（5）：961-1004.

[6]D.Comaniciu and P.Meer，Meanshift：A Robust Approach Toward Feature space Anysiss. IEEE Trans.Pattern Analysis and Machine Intelligence，2002，vol（24）.

[7]F Schaffalitzky，A Zisserman.Viewpoint invariant texture matching and wide baseline stcreo.IEEE，200l.

[8]Raymond van Ee，CliRon M Schor.Unconstrained stereoscopic matching of lines.Vision Research，2000（40）：151-162.

[9]S J D Prince，R D Eagle.Weighted directional energy model for human stereo correspondence.Vision Research，2001（13）：41-52.

編輯 王夢(mèng)玉