雙目立體視覺匹配算法的實(shí)現(xiàn)與分析

王 沁 費(fèi) 強(qiáng) 石迪迪

（浙江省國(guó)土勘測(cè)規(guī)劃有限公司，浙江 杭州 310030）

0.引言

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

影像匹配是指在具有重疊關(guān)系的立體影像對(duì)上進(jìn)行相似特征點(diǎn)搜索，在剔除誤匹配點(diǎn)后，獲取最佳的空間相似對(duì)應(yīng)點(diǎn)，以此恢復(fù)影像間的空間變化關(guān)系[5]。影像匹配的關(guān)鍵是采取一種合適的匹配算法，以求高效性、準(zhǔn)確性、穩(wěn)健性以及時(shí)效性[6]。

1.立體匹配原理

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

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

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

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

2.1 %半全局匹配算法

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

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

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

（1）逐像素匹配計(jì)算

采用函數(shù)d（xi，yi，IL，IR）判斷兩個(gè)像素點(diǎn)相似程度的大小，進(jìn)而判斷是否為同名像點(diǎn)，如式（3）所示：

式中，xi和yi分別表示左右掃描線上對(duì)應(yīng)的像點(diǎn)。若左掃描線上像點(diǎn)的灰度定義為IL（xi），則通過采樣點(diǎn)線性內(nèi)插計(jì)算，可以得到右掃描線上對(duì)應(yīng)的灰度值IR（yi）。

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

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

（3）視差計(jì)算

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

（4）誤匹配的剔除

在完成影像匹配后，再次利用右影像對(duì)左影像上的點(diǎn)進(jìn)行同名像點(diǎn)匹配。若兩次的匹配結(jié)果視差相同，則認(rèn)為匹配成功，否則視為粗差，將其剔除。

2.2 BM匹配算法

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

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

圖1 文本串T和模式串P

若采用上述方法，無法完成匹配時(shí)，BM匹配算法就會(huì)跳轉(zhuǎn)到好后綴算法和壞字符算法兩種啟發(fā)式規(guī)則，進(jìn)而在匹配過程中，逐步計(jì)算出上述模式串P的移動(dòng)步長(zhǎng)（如圖2所示）：

圖2 壞字符與好后綴啟發(fā)式規(guī)則

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

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

（2）如果E出現(xiàn)在與文本串P不匹配的字段中，則認(rèn)為與字符E對(duì)齊。

歷經(jīng)兩次調(diào)整后，再次從右到左執(zhí)行匹配過程（如圖3所示）：

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

2.3 %GC匹配算法

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

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

其次，使用穩(wěn)健的最小二乘法解算每個(gè)分區(qū)的平面模型參數(shù)。

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

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

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

其中，第一項(xiàng)表示的是轉(zhuǎn)換后的影像與真實(shí)影像之間的差別，定義如式（5）所示：

W（p）表示像素點(diǎn)p在轉(zhuǎn)換影像中的值，而R（p）表示p在真實(shí)影像中的值。不相似函數(shù)dis（pi，pj）表示顏色三通道絕對(duì)差的和。

式（4）右側(cè)的第二項(xiàng)則是對(duì)左右圖中遮擋區(qū)域的懲罰，定義如式（6）所示：

其中，OccR是在右圖中被遮擋的點(diǎn)，OccL是左圖中被遮擋的點(diǎn)，而λocc則是對(duì)于所有遮擋的一個(gè)懲罰常數(shù)。

3.實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)計(jì)算機(jī)采用的是聯(lián)想公司Y470型筆記本，下面將選取Tsukuba和Satellite Model兩組立體像對(duì)進(jìn)行實(shí)驗(yàn)，分別運(yùn)用上述三種算法進(jìn)行匹配，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行相應(yīng)的分析。

3.1 Tsukuba立體像對(duì)匹配實(shí)驗(yàn)

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

圖4 Tsukuba立體像對(duì)

圖5 Tsukuba立體像對(duì)匹配結(jié)果

表1 Tsukuba立體像對(duì)匹配時(shí)間表

3.2 %Satellite Model立體像對(duì)匹配實(shí)驗(yàn)

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

圖6 Satellite Model立體像對(duì)

圖7 Satellite Model立體像對(duì)匹配結(jié)果

表2 Satellite Model立體像對(duì)匹配時(shí)間表

3.3 實(shí)驗(yàn)分析

綜合比較以上兩組實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)：

（1）在處理速度上，BM匹配算法最快；SGBM匹配算法次之，其耗時(shí)約是BM匹配算法的3—5倍；GC匹配算法最慢，耗時(shí)甚至?xí)_(dá)到BM匹配算法的100倍以上。

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

（3）在應(yīng)用領(lǐng)域上，BM匹配算法適用于對(duì)處理效率期望高但對(duì)處理效果要求不嚴(yán)格的情況，可用于實(shí)時(shí)動(dòng)態(tài)匹配，如移動(dòng)視覺跟蹤和加工制造監(jiān)控等；SGBM匹配算法適用于對(duì)處理效果和處理速度均要求較高的場(chǎng)合，如武器打擊系統(tǒng)、醫(yī)學(xué)影像分析、機(jī)械制造檢測(cè)等；GC匹配算法，適用于目標(biāo)或場(chǎng)景的精細(xì)三維建模，如精密器件加工、高精度測(cè)繪、高精度仿真建模等。

4.結(jié)束語(yǔ)

本文介紹了雙目立體視覺測(cè)量領(lǐng)域的一些知識(shí)，著重研究了SGBM、BM、GC三種匹配算法的原理，通過算法的程序?qū)崿F(xiàn)，分析了其匹配速度、匹配效果的差異，對(duì)其總體性能和應(yīng)用領(lǐng)域進(jìn)行了一定的總結(jié)和預(yù)測(cè)，在今后進(jìn)行立體像對(duì)的匹配處理時(shí)，可以根據(jù)任務(wù)需求選擇最優(yōu)的匹配算法。