王 沁 費 強 石迪迪

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

0.引言

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

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

1.立體匹配原理

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

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

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

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

2.1 %半全局匹配算法

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

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

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

（1）逐像素匹配計算

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

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

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

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

（3）視差計算

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

（4）誤匹配的剔除

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

2.2 BM匹配算法

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

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

圖1 文本串T和模式串P

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

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

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

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

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

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

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

2.3 %GC匹配算法

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

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

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

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

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

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

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

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

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

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

3.實驗結(jié)果與分析

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

3.1 Tsukuba立體像對匹配實驗

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

圖4 Tsukuba立體像對

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

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

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

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

圖6 Satellite Model立體像對

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

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

3.3 實驗分析

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

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

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

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

4.結(jié)束語

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