在深度相機的主流技術方案Structure Light，ToF，Stereo Dual）中，主動雙目成像方案可以基于低成本的硬件，獲得高分辨率、高精度的深度圖像，但是立體匹配算法（stereo matching）復雜，對計算資源消耗很大。那我們介紹下幾種經典的雙目匹配的算法。

【雙目匹配】

雙目立體視覺理論建立在對人類視覺系統研究的基礎上，通過雙目立體圖象的處理，獲取場景的三維信息，其結果表現為深度圖，再經過進一步處理就可得到三維空間中的景物，實現二維圖象到三維空間的重構。Marr-Poggio-Grimson [1] 最早提出并實現了一種基于人類視覺系統的計算視覺模型及算法。雙目立體視覺系統中，獲取深度信息的方法比其它方式（如由影到形方法）較為直接，它是被動方式的，因而較主動方式（如程距法）適用面寬，這是它的突出特點。

雙目立體視覺系統中，深度信息的獲得是分如下兩步進行的:

(1) 在雙目立體圖象間建立點點對應,

(2) 根據對應點的視差計算出深度。

第一部分，也就是對應點問題，是雙目立體視覺的關鍵; 第二部分是攝像機模型問題。雙目立體視覺模型中，雙攝像機彼此參數一致，光軸平行且垂直于基線，構成一共極性 (epipolar) 結構，這樣做是為了縮小對應的搜索空間，只有水平方向的視差，簡化了對應過程

【立體匹配算法介紹】

BM

其中minDisparity是控制匹配搜索的第一個參數，代表了匹配搜蘇從哪里開始，numberOfDisparities表示最大搜索視差數uniquenessRatio表示匹配功能函數，這三個參數比較重要，可以根據實驗給予參數值。

該方法速度最快，一副320*240的灰度圖匹配時間為31ms

SBGM

SGBM算法 Stereo Processing by Semiglobal Matching and Mutual Information

作為一種全局匹配算法，立體匹配的效果明顯好于局部匹配算法，但是同時復雜度上也要遠遠大于局部匹配算法。算法主要是參考Stereo Processing by Semiglobal Matching and Mutual Information。

通過選取每個像素點的disparity，組成一個disparity map，設置一個和disparity map相關的全局能量函數，使這個能量函數最小化，以達到求解每個像素最優disparity的目的。

能量函數形式如下：

D指disparity map。E(D)是該disparity map對應的能量函數。

p, q代表圖像中的某個像素

Np 指像素p的相鄰像素點（一般認為8連通）

C(p, Dp)指當前像素點disparity為Dp時，該像素點的cost

P1 是一個懲罰系數，它適用于像素p相鄰像素中dsparity值與p的dsparity值相差1的那些像素。

P2 是一個懲罰系數，它適用于像素p相鄰像素中dsparity值與p的dsparity值相差大于1的那些像素。

I[.]函數返回1如果函數中的參數為真，否則返回0

利用上述函數在一個二維圖像中尋找最優解是一個NP-complete問題，耗時過于巨大，因此該問題被近似分解為多個一維問題，即線性問題。而且每個一維問題都可以用動態規劃來解決。因為1個像素有8個相鄰像素，因此一般分解為8個一維問題。

OpenCV中自帶了BM和SBGM，效果對比如下圖：

GC

GC算法 算法文獻：Realistic CG Stereo Image Dataset with Ground Truth Disparity Maps

SAD

SAD(Sum of absolute differences)是一種圖像匹配算法。基本思想：差的絕對值之和。此算法常用于圖像塊匹配，將每個像素對應數值之差的絕對值求和，據此評估兩個圖像塊的相似度。該算法快速、但并不精確，通常用于多級處理的初步篩選。

基本流程

輸入：兩幅圖像，一幅Left-Image，一幅Right-Image 對左圖，依次掃描，選定一個錨點：

（1）構造一個小窗口,類似于卷積核； （2）用窗口覆蓋左邊的圖像,選擇出窗口覆蓋區域內的所有像素點； （3）同樣用窗口覆蓋右邊的圖像并選擇出覆蓋區域的像素點； （4）左邊覆蓋區域減去右邊覆蓋區域，并求出所有像素點灰度差的絕對值之和； （5）移動右邊圖像的窗口，重復（3）-（4）的處理（這里有個搜索范圍,超過這個范圍跳出）； （6）找到這個范圍內SAD值最小的窗口,即找到了左圖錨點的最佳匹配的像素塊。

【匹配陷阱】

以下幾種情形生成的深度圖像可能會有缺陷：

（1） 光學失真和噪聲（亮度、色調、飽和度等失衡）

（2） 平滑表面的鏡面反射

高光處無細節，無特征點。

（3） 投影縮減（Foreshortening）

攝影測量學中的一個概念，指物體近大遠小。由于相對左右照相機距離的不同，看到的同一個物體在左右視圖中的投影尺寸也會不同，造成匹配障礙。

（4） 透視失真（Perspective distortions）

由于鏡頭畸變造成的被攝物體失真。譬如畫面中的鼻子被拉長。

（5） 低紋理（Low texture）

無細節。主動紋理光可以解決這一問題。

（6） 重復紋理（Repetitive/ambiguous patterns）

高度相似的特征點描述向量接近，行掃描時難以判斷哪一個是對應的特征點。

（7） 透明物體

同低紋理。

（8） 重疊和非連續

紋理中斷，不利于行查找。