幾種經(jīng)典的雙目匹配的算法

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

【雙目匹配】

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

雙目立體視覺系統(tǒng)中，深度信息的獲得是分如下兩步進(jìn)行的:

(1) 在雙目立體圖象間建立點(diǎn)點(diǎn)對(duì)應(yīng),

(2) 根據(jù)對(duì)應(yīng)點(diǎn)的視差計(jì)算出深度。

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

【立體匹配算法介紹】

BM

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

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

SBGM

SGBM算法 Stereo Processing by Semiglobal Matching and Mutual Information

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

通過選取每個(gè)像素點(diǎn)的disparity，組成一個(gè)disparity map，設(shè)置一個(gè)和disparity map相關(guān)的全局能量函數(shù)，使這個(gè)能量函數(shù)最小化，以達(dá)到求解每個(gè)像素最優(yōu)disparity的目的。

能量函數(shù)形式如下：

D指disparity map。E(D)是該disparity map對(duì)應(yīng)的能量函數(shù)。

p, q代表圖像中的某個(gè)像素

Np 指像素p的相鄰像素點(diǎn)（一般認(rèn)為8連通）

C(p, Dp)指當(dāng)前像素點(diǎn)disparity為Dp時(shí)，該像素點(diǎn)的cost

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

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

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

利用上述函數(shù)在一個(gè)二維圖像中尋找最優(yōu)解是一個(gè)NP-complete問題，耗時(shí)過于巨大，因此該問題被近似分解為多個(gè)一維問題，即線性問題。而且每個(gè)一維問題都可以用動(dòng)態(tài)規(guī)劃來解決。因?yàn)?個(gè)像素有8個(gè)相鄰像素，因此一般分解為8個(gè)一維問題。

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

GC

GC算法 算法文獻(xiàn)：Realistic CG Stereo Image Dataset with Ground Truth Disparity Maps

SAD

SAD(Sum of absolute differences)是一種圖像匹配算法?；舅枷耄翰畹慕^對(duì)值之和。此算法常用于圖像塊匹配，將每個(gè)像素對(duì)應(yīng)數(shù)值之差的絕對(duì)值求和，據(jù)此評(píng)估兩個(gè)圖像塊的相似度。該算法快速、但并不精確，通常用于多級(jí)處理的初步篩選。

基本流程

輸入：兩幅圖像，一幅Left-Image，一幅Right-Image 對(duì)左圖，依次掃描，選定一個(gè)錨點(diǎn)：

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

【匹配陷阱】

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

（1） 光學(xué)失真和噪聲（亮度、色調(diào)、飽和度等失衡）

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

高光處無細(xì)節(jié)，無特征點(diǎn)。

（3） 投影縮減（Foreshortening）

攝影測(cè)量學(xué)中的一個(gè)概念，指物體近大遠(yuǎn)小。由于相對(duì)左右照相機(jī)距離的不同，看到的同一個(gè)物體在左右視圖中的投影尺寸也會(huì)不同，造成匹配障礙。

（4） 透視失真（Perspective distortions）

由于鏡頭畸變?cè)斐傻谋粩z物體失真。譬如畫面中的鼻子被拉長(zhǎng)。

（5） 低紋理（Low texture）

無細(xì)節(jié)。主動(dòng)紋理光可以解決這一問題。

（6） 重復(fù)紋理（Repetitive/ambiguous patterns）

高度相似的特征點(diǎn)描述向量接近，行掃描時(shí)難以判斷哪一個(gè)是對(duì)應(yīng)的特征點(diǎn)。

（7） 透明物體

同低紋理。

（8） 重疊和非連續(xù)

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