雙目立體視覺匹配算法的實現與分析

王 沁 費 強 石迪迪

（浙江省國土勘測規劃有限公司，浙江 杭州 310030）

0.引言

攝影測量是指利用相機或其他傳感器對地面或物體表面實施拍照，獲取包含紋理信息的影像數據，采用相應的處理手段，可以快速獲取大量的空間點位信息，是目前應用領域較為廣泛的技術方法[1]。攝影測量采用非接觸式測量方法，可有效兼顧精度與效率，測量周期短，已經在眾多領域得到了廣泛的應用[2]。采用非接觸測量方式對特定目標或場景進行精確測量，結合特定的技術恢復其三維信息一直是一個研究熱點[3]。雙目立體視覺測量利用組成立體像對的圖像進而實現三維重建。所謂立體像對，就是指具有一定重疊關系的兩張影像，可利用兩個相機或者一個相機在空間的不同位置實施拍攝獲得[4]。雙目立體視覺測量技術涉及影像獲取、預處理、影像匹配和三維重建等步驟，其中，影像匹配作為關鍵的技術環節，其優劣性直接影響到后續三維重建質量，而匹配質量又是由匹配效率、精確性和可靠性決定的。目前，影像匹配算法的發展一直是雙目立體視圖技術的瓶頸。

影像匹配是指在具有重疊關系的立體影像對上進行相似特征點搜索，在剔除誤匹配點后，獲取最佳的空間相似對應點，以此恢復影像間的空間變化關系[5]。影像匹配的關鍵是采取一種合適的匹配算法，以求高效性、準確性、穩健性以及時效性[6]。

1.立體匹配原理

結合立體像對的重疊區域，用投射理論表述多個投影點間的變換模型，利用投影點的特征因子計算視差。其最終目的就是根據圖像處理和參數優化獲取像素點間的視差值。歷經多年發展，不斷涌現出了多種優質匹配算法，包括局部算法和全局算法。其中，對于任何匹配算法均具備完整的計算流程。首先，根據場景要求確定匹配單元，選擇合理的特征提取算法，并對提取的特征進行描述；然后，選擇匹配算法，并以相似性度量函數和約束準則完成特征點匹配與提純；最后，完成視差計算。

各類特征匹配算法在完成視差圖獲取時，難免會受到影像噪聲、陰影遮擋、匱乏紋理、光照強度差異等多種因素的影響，導致匹配結果出現系列問題，因此，需要建立相關的立體匹配評判準則。一般把真實視差圖與計算所得的視差圖進行對比，將符合限差條件的視為正確結果，否則任務匹配失敗。以誤匹配率函數為例，設兩視差圖大小相等，則視差圖誤差比重如式（1）所示：

式（1）中，N為像素點總數；（i，j）為像素點坐標；dc為待評估視差值；dt為真實視差值；δd為閾值，一般取值為1。誤匹配率可以直接描述特征匹配的好壞，下面我們選擇三種當前比較流行的影像匹配方法進行相關的研究和分析。

2.三種影像匹配算法的原理

2.1 %半全局匹配算法

半全局匹配算法（Semi-Global Block Stereo Matching,SGBM）是計算機視覺領域的一種影像匹配算法，該算法是采取互信息來描述像點間對應關系的，主要原理是先以互信息為基礎，迭代計算像素值，然后以多維方向的約束來模擬二維約束。

SGBM匹配算法是以互信息MI1，2為基礎的，互信息MI1，2是通過兩張影像的信息閾H1、H2及其聯合信息閾H1，2來定義的，其定義如式（2）所示：

單張影像的信息閾H以直方圖統計概率分布情況，聯合影像的信息閾H1，2則用相互匹配影像的灰度聯合分布函數進行計算。經過逐像素匹配計算、用一維約束近似二維約束、視差計算、誤匹配剔除等步驟完成。

（1）逐像素匹配計算

采用函數d（xi，yi，IL，IR）判斷兩個像素點相似程度的大小，進而判斷是否為同名像點，如式（3）所示：

式中，xi和yi分別表示左右掃描線上對應的像點。若左掃描線上像點的灰度定義為IL（xi），則通過采樣點線性內插計算，可以得到右掃描線上對應的灰度值IR（yi）。

（2）用一維約束近似二維約束

在P的周圍，以45°為間隔設置了8個路徑。通過8個路徑計算最小代價路徑，以此來近似二維約束匹配計算。

（3）視差計算

一般采用迭代的方式計算視差，主要包括兩種方法：一是結合隨機視差影像對右影像進行糾正，而后實施特征匹配，并重新生產出視差影像；二是結合分等級計算方法，先利用半分辨率獲得初始視差影像，而后經遞歸計算得出新的視差影像。

（4）誤匹配的剔除

在完成影像匹配后，再次利用右影像對左影像上的點進行同名像點匹配。若兩次的匹配結果視差相同，則認為匹配成功，否則視為粗差，將其剔除。

2.2 BM匹配算法

BM（boyer-moore，BM）匹配算法是一種精確字符串匹配算法（區別于模糊匹配），在OpenCV中被用來對圖像灰度進行精確匹配，圖像灰度匹配也可以認為是字符串的匹配[9]。BM算法應用從右至左進行比較的匹配方法，并引入了壞字符算法和好后綴算法的不同啟發式跳轉方式，進而計算出模板右移的步長。

令待匹配圖像的灰度值為文本串T，匹配的圖像灰度值為文本串P，并定義為模式串。先將T左對齊于P，而后從右向左進行比較（如圖1所示）：

圖1 文本串T和模式串P

若采用上述方法，無法完成匹配時，BM匹配算法就會跳轉到好后綴算法和壞字符算法兩種啟發式規則，進而在匹配過程中，逐步計算出上述模式串P的移動步長（如圖2所示）：

圖2 壞字符與好后綴啟發式規則

可見，文本串P與T在進行匹配時，斜體E和B則表示首個不匹配的字符，為壞字符。加粗體CAB表示匹配好的字符，為好后綴。圖2中BM算法從右到左的匹配不一致情況，需要根據壞后綴算法，應用兩種情況來處理：

（1）假如文本串T中不匹配的字符E沒有出現在文本串P中，則可以理解為，從E開始的長度為m的字符串不能匹配P。此時，P可以直接跳到E，并開始接下來內容的匹配。

（2）如果E出現在與文本串P不匹配的字段中，則認為與字符E對齊。

歷經兩次調整后，再次從右到左執行匹配過程（如圖3所示）：

圖3 適用好后綴算法的情況

2.3 %GC匹配算法

基于圖切（graph-cut，GC）圖像分割的方法維持了這樣一個假設：場景可以被分割成很多部分，其中每一個部分深度的變化都是細微的，可以和深度大致相同。分割則是基于圖像的顏色信息。這種方法要么在匹配時將分割的小平面參數作為約束，要么在匹配時以小平面代替像素作為匹配單元。本文選擇基于mean-shift的雙目立體視圖圖像分割匹配算法，具體流程如下：

首先，使用分割算法對圖像實施分割后，采取基于窗口的方法計算概略的初始深度圖。

其次，使用穩健的最小二乘法解算每個分區的平面模型參數。

冬天，雪精靈歡快飛舞，將大地裝點成銀裝素裹。書包帶著我旋轉著、飛翔著，我與雪精靈歡快共舞，銀鈴般的笑聲引得地上的雪人也裂開了嘴。

再次，同一簇中的點形成一個深度平面，我們可以采取初始深度圖對深度平面的平面模型參數進行計算。在該算法中，深度分配的單位是提取的深度平面，而不是像素。

最后，根據深度圖將所有的深度平面轉換就得到了整幅轉換影像。這樣，我們就能定義匹配的代價，如式（4）所示：

其中，第一項表示的是轉換后的影像與真實影像之間的差別，定義如式（5）所示：

W（p）表示像素點p在轉換影像中的值，而R（p）表示p在真實影像中的值。不相似函數dis（pi，pj）表示顏色三通道絕對差的和。

式（4）右側的第二項則是對左右圖中遮擋區域的懲罰，定義如式（6）所示：

其中，OccR是在右圖中被遮擋的點，OccL是左圖中被遮擋的點，而λocc則是對于所有遮擋的一個懲罰常數。

3.實驗結果與分析

實驗計算機采用的是聯想公司Y470型筆記本，下面將選取Tsukuba和Satellite Model兩組立體像對進行實驗，分別運用上述三種算法進行匹配，并對實驗結果進行相應的分析。

3.1 Tsukuba立體像對匹配實驗

Tsukuba立體像對（如圖4所示），圖像像素尺寸為384px ×288px，格式為jpg，經過SGBM、BM、GC三種匹配算法處理所得深度圖（如圖5所示），影像匹配時間（如表1所示）：

圖4 Tsukuba立體像對

圖5 Tsukuba立體像對匹配結果

表1 Tsukuba立體像對匹配時間表

3.2 %Satellite Model立體像對匹配實驗

Satellite Model立體像對（如圖6所示），圖像像素尺寸為640px × 512px，格式為bmp，經過SGBM、BM、GC三種匹配算法所得深度圖（如圖7所示），影像匹配時間（如表2所示）：

圖6 Satellite Model立體像對

圖7 Satellite Model立體像對匹配結果

表2 Satellite Model立體像對匹配時間表

3.3 實驗分析

綜合比較以上兩組實驗結果，可以發現：

（1）在處理速度上，BM匹配算法最快；SGBM匹配算法次之，其耗時約是BM匹配算法的3—5倍；GC匹配算法最慢，耗時甚至會達到BM匹配算法的100倍以上。

（2）在處理效果上，BM匹配算法處理的深度圖中，場景物體輪廓模糊，表面清晰度差，變形嚴重，存在較多誤匹配區域，效果較差；SGBM匹配算法比BM匹配算法具有更好的處理效果；GC匹配算法成功恢復了場景中對象的形狀，尤其是在Satellite Model立體像對中對于衛星模型和火箭模型形狀的恢復很成功，場景層次清晰分明，對象輪廓清晰，表面光滑，匹配效果最好。

（3）在應用領域上，BM匹配算法適用于對處理效率期望高但對處理效果要求不嚴格的情況，可用于實時動態匹配，如移動視覺跟蹤和加工制造監控等；SGBM匹配算法適用于對處理效果和處理速度均要求較高的場合，如武器打擊系統、醫學影像分析、機械制造檢測等；GC匹配算法，適用于目標或場景的精細三維建模，如精密器件加工、高精度測繪、高精度仿真建模等。

4.結束語

本文介紹了雙目立體視覺測量領域的一些知識，著重研究了SGBM、BM、GC三種匹配算法的原理，通過算法的程序實現，分析了其匹配速度、匹配效果的差異，對其總體性能和應用領域進行了一定的總結和預測，在今后進行立體像對的匹配處理時，可以根據任務需求選擇最優的匹配算法。