影像匹配

最初的影像匹配是利用相關技術實現的，因而也有人稱影像匹配為影像相關。它是圖像融合、目標識別、目標變化檢測、計算機視覺等問題中的一個重要前期步驟，在遙感、數字攝影測量、計算機視覺、地圖學以及軍事應用等多個領域都有着廣泛的應用。 ^[2] 

由於原始相片中的灰度信息可轉換為電子、光學或數字等形式的信號，因而可構成電子相關、光學相關或數字相關等不同的相關方式；而由於可運用於多個領域中，影像相關所匹配的對象也是多種多樣的，如衞星遙感影像、航空攝影影像、近景攝影影像等，這些原始數據往往都不是理想的數據源，因此要針對各種特點選擇合適的算法進行匹配。但一般來説，無論是光學相關、電子相關還是數字相關，所匹配的對象也有不同，但其理論基礎都是相同的。

影像相關是利用互相關函數，評價兩塊影像的相似性以確定同名點。即首先取出以待定點為中心的小區域中的影像信號，然後取出其在另一影像中相應區域的影像信號，計算二者的相關函數，以相關函數最大值對應的相應區域中心點為同名點。即以影像信號分部最相似的區域為同名區域，同名區域的中心點為同名點。這也是自動化立體量測的基本原理。

同名點的確定是以匹配測度為基礎的，因此定義匹配測度是影像匹配最首要的任務，基於不同的理論或不同的思想可以定義各種不同的匹配測度，因而形成了各種影像匹配方法及相應的實現算法。常見的基於像方灰度的影像匹配算法有相關函數法、協方差函數法、相關係數法、差平方和法、差絕對值和法、最小二乘法等，基於物方的影像匹配算法有鉛垂線軌跡法（VLL，Vertical Line Locus），另外還有基於像方特徵的跨接法影像匹配，金字塔多級影像匹配， SIFT等等。 ^[2] 

按照影像中需要進行匹配的像點的相對數目，影像匹配可分為稀疏匹配和稠密匹配兩類。稀疏匹配產生稀疏的視差矩陣，主要用於確定視點與影像以及影像之間的相對位置關係。稠密匹配通常要求獲得整個影像或者影像主要部分的深度圖。按照匹配元素選擇不同，影像匹配可以分為灰度區域匹配和特徵匹配。灰度區域匹配按照像素灰度進行匹配，特徵匹配使用邊緣等影像特徵進行匹配。實際上，像素灰度也是一種影像特徵，特徵也不一定是某些可以解釋的幾何特徵。具有可分辨性、不變性和穩定性的屬性都可以作為匹配特徵。

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

局部算法主要有塊匹配算法、基於梯度的優化算法和基於特徵的匹配算法等。

認為利用影像的局部信息足以實現影像匹配，不需要全局優化。算法基於相似匹配元的選擇，定義適當的匹配窗口和匹配原則是十分重要的。

典型的匹配代價函數有差平方和(SSD)，絕對差之和(SAD)以及標準化互相關(NCC)等。

1、塊匹配算法在局部小區域內尋找最佳匹配使匹配誤差最小，通常使用規範化互相關方法，包括規範化互相關、平方差之和、規範化平方差之和、絕對差之和方法等。

2、基於梯度的優化算法在局部區域內通過最小化圖像間平方差的和來實現匹配。該算法假設場景中同一個點在兩個視圖內的影像亮度不變。通過建立運動和影像亮度的微分方程來計算局部小區域內的視差。

塊匹配算法和基於梯度的匹配算法對於圖像的局部不連續和一致性紋理問題敏感，無法得到滿意的解答，從而使基於特徵匹配的算法得到發展，如基於分層的特徵匹配和基於圖像分割的匹配算法等。

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

目前，已經設計出了許多解決這個問題的窗口，例如可移動式窗口、大小自適應窗口、影像分割窗口、等視差鄰接窗口以及視差空間模型窗口等。 ^[3] 

全局算法使用全局約束解決由於遮擋和一致性紋理造成的局部匹配失敗問題。全局對應算法包括動態規劃算法、本徵曲線算法、最大流量圖算法、最小割集算法、非線性擴散算法、信心傳播算法等。

核心是：全局匹配需要首先定義一個先驗模型，通過最小化全局函數獲得問題的解。模型的選定決定了最後的解。

1、動態規劃算法通過將優化問題分解為更小、更簡單的子問題從而降低計算複雜度，通常使用外極線來實現次序約束。

2、本徵曲線是對圖像按掃描線計算邊緣或點特徵的描述矢量，算法將外極線映射到本徵曲線空間從而將搜索問題轉化為最小鄰居查找問題，並通過動態規劃解決二義性問題。本徵曲線的主要優點是它對視差的不變性。

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

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

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

匹配算法的性能評價指標主要有：匹配概率、匹配精度、匹配速度。

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

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

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

一個好的匹配算法要求匹配概率儘可能高，匹配誤差小，算法計算快，能滿足應用環境對實時性的要求 ^[3]  。