[科普中國]-影像匹配

概念

最初的影像匹配是利用相關(guān)技術(shù)實(shí)現(xiàn)的，因而也有人稱影像匹配為影像相關(guān)。它是圖像融合、目標(biāo)識(shí)別、目標(biāo)變化檢測、計(jì)算機(jī)視覺等問題中的一個(gè)重要前期步驟，在遙感、數(shù)字?jǐn)z影測量、計(jì)算機(jī)視覺、地圖學(xué)以及軍事應(yīng)用等多個(gè)領(lǐng)域都有著廣泛的應(yīng)用。1

特征由于原始相片中的灰度信息可轉(zhuǎn)換為電子、光學(xué)或數(shù)字等形式的信號(hào)，因而可構(gòu)成電子相關(guān)、光學(xué)相關(guān)或數(shù)字相關(guān)等不同的相關(guān)方式；而由于可運(yùn)用于多個(gè)領(lǐng)域中，影像相關(guān)所匹配的對(duì)象也是多種多樣的，如衛(wèi)星遙感影像、航空攝影影像、近景攝影影像等，這些原始數(shù)據(jù)往往都不是理想的數(shù)據(jù)源，因此要針對(duì)各種特點(diǎn)選擇合適的算法進(jìn)行匹配。但一般來說，無論是光學(xué)相關(guān)、電子相關(guān)還是數(shù)字相關(guān)，所匹配的對(duì)象也有不同，但其理論基礎(chǔ)都是相同的。

影像相關(guān)是利用互相關(guān)函數(shù)，評(píng)價(jià)兩塊影像的相似性以確定同名點(diǎn)。即首先取出以待定點(diǎn)為中心的小區(qū)域中的影像信號(hào)，然后取出其在另一影像中相應(yīng)區(qū)域的影像信號(hào)，計(jì)算二者的相關(guān)函數(shù)，以相關(guān)函數(shù)最大值對(duì)應(yīng)的相應(yīng)區(qū)域中心點(diǎn)為同名點(diǎn)。即以影像信號(hào)分部最相似的區(qū)域?yàn)橥麉^(qū)域，同名區(qū)域的中心點(diǎn)為同名點(diǎn)。這也是自動(dòng)化立體量測的基本原理。

同名點(diǎn)的確定是以匹配測度為基礎(chǔ)的，因此定義匹配測度是影像匹配最首要的任務(wù)，基于不同的理論或不同的思想可以定義各種不同的匹配測度，因而形成了各種影像匹配方法及相應(yīng)的實(shí)現(xiàn)算法。常見的基于像方灰度的影像匹配算法有相關(guān)函數(shù)法、協(xié)方差函數(shù)法、相關(guān)系數(shù)法、差平方和法、差絕對(duì)值和法、最小二乘法等，基于物方的影像匹配算法有鉛垂線軌跡法（VLL，Vertical Line Locus），另外還有基于像方特征的跨接法影像匹配，金字塔多級(jí)影像匹配， SIFT等等。1

影像匹配算法按照影像中需要進(jìn)行匹配的像點(diǎn)的相對(duì)數(shù)目，影像匹配可分為稀疏匹配和稠密匹配兩類。稀疏匹配產(chǎn)生稀疏的視差矩陣，主要用于確定視點(diǎn)與影像以及影像之間的相對(duì)位置關(guān)系。稠密匹配通常要求獲得整個(gè)影像或者影像主要部分的深度圖。按照匹配元素選擇不同，影像匹配可以分為灰度區(qū)域匹配和特征匹配。灰度區(qū)域匹配按照像素灰度進(jìn)行匹配，特征匹配使用邊緣等影像特征進(jìn)行匹配。實(shí)際上，像素灰度也是一種影像特征，特征也不一定是某些可以解釋的幾何特征。具有可分辨性、不變性和穩(wěn)定性的屬性都可以作為匹配特征。

主要的匹配算法可以分為局部算法和全局算法兩大類。

局部算法局部算法主要有塊匹配算法、基于梯度的優(yōu)化算法和基于特征的匹配算法等。

認(rèn)為利用影像的局部信息足以實(shí)現(xiàn)影像匹配，不需要全局優(yōu)化。算法基于相似匹配元的選擇，定義適當(dāng)?shù)钠ヅ浯翱诤推ヅ湓瓌t是十分重要的。

典型的匹配代價(jià)函數(shù)有差平方和(SSD)，絕對(duì)差之和(SAD)以及標(biāo)準(zhǔn)化互相關(guān)(NCC)等。

1、塊匹配算法在局部小區(qū)域內(nèi)尋找最佳匹配使匹配誤差最小，通常使用規(guī)范化互相關(guān)方法，包括規(guī)范化互相關(guān)、平方差之和、規(guī)范化平方差之和、絕對(duì)差之和方法等。

2、基于梯度的優(yōu)化算法在局部區(qū)域內(nèi)通過最小化圖像間平方差的和來實(shí)現(xiàn)匹配。該算法假設(shè)場景中同一個(gè)點(diǎn)在兩個(gè)視圖內(nèi)的影像亮度不變。通過建立運(yùn)動(dòng)和影像亮度的微分方程來計(jì)算局部小區(qū)域內(nèi)的視差。

塊匹配算法和基于梯度的匹配算法對(duì)于圖像的局部不連續(xù)和一致性紋理問題敏感，無法得到滿意的解答，從而使基于特征匹配的算法得到發(fā)展，如基于分層的特征匹配和基于圖像分割的匹配算法等。

對(duì)于局部匹配算法，窗口的選擇非常重要。窗口必須足夠大以獲取可靠的匹配，同時(shí)又必須足夠小以避免投影變形的影響。而且，窗口的形狀必須保證具有足夠的可分辨性。

目前，已經(jīng)設(shè)計(jì)出了許多解決這個(gè)問題的窗口，例如可移動(dòng)式窗口、大小自適應(yīng)窗口、影像分割窗口、等視差鄰接窗口以及視差空間模型窗口等。2

全局算法全局算法使用全局約束解決由于遮擋和一致性紋理造成的局部匹配失敗問題。全局對(duì)應(yīng)算法包括動(dòng)態(tài)規(guī)劃算法、本征曲線算法、最大流量圖算法、最小割集算法、非線性擴(kuò)散算法、信心傳播算法等。

核心是：全局匹配需要首先定義一個(gè)先驗(yàn)?zāi)Ｐ?，通過最小化全局函數(shù)獲得問題的解。模型的選定決定了最后的解。

1、動(dòng)態(tài)規(guī)劃算法通過將優(yōu)化問題分解為更小、更簡單的子問題從而降低計(jì)算復(fù)雜度，通常使用外極線來實(shí)現(xiàn)次序約束。

2、本征曲線是對(duì)圖像按掃描線計(jì)算邊緣或點(diǎn)特征的描述矢量，算法將外極線映射到本征曲線空間從而將搜索問題轉(zhuǎn)化為最小鄰居查找問題，并通過動(dòng)態(tài)規(guī)劃解決二義性問題。本征曲線的主要優(yōu)點(diǎn)是它對(duì)視差的不變性。

3、最大流量圖劃分算法將視差表面作為最大流量圖中的最小割邊集進(jìn)行求解。

4、非線性擴(kuò)散算法通過局部擴(kuò)散處理提供聚類支持。

局部算法具有較高的效率，但是容易受到遮擋、紋理等問題的影響。與此相反，全局算法對(duì)上述問題不敏感，但計(jì)算效率較差。2

影像匹配算法性能評(píng)價(jià)指標(biāo)匹配算法的性能評(píng)價(jià)指標(biāo)主要有：匹配概率、匹配精度、匹配速度。

匹配概率，是正確匹配次數(shù)與總的匹配次數(shù)之比。

匹配精度，是正確匹配的匹配誤差均方差，描述了匹配的準(zhǔn)確性。由于噪聲和其他誤差因素的影響，圖像匹配時(shí)最終得出的匹配位置和真正的匹配位置是不同的，估計(jì)匹配點(diǎn)和真正匹配點(diǎn)之間存在一定的隨機(jī)偏差，該偏差稱為匹配誤差。顯然匹配誤差的方差越小，則定位精度越高。

匹配速度，是指匹配算法的快慢程度，說明了搜索的快速性。

一個(gè)好的匹配算法要求匹配概率盡可能高，匹配誤差小，算法計(jì)算快，能滿足應(yīng)用環(huán)境對(duì)實(shí)時(shí)性的要求2。