作者：沙洪俊, 袁修孝 來源：《武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）》

自進(jìn)入數(shù)字地球時(shí)代以來，智慧城市的建設(shè)工作一直是推動(dòng)其發(fā)展的關(guān)鍵，而三維點(diǎn)云數(shù)據(jù)的快速獲取則是智慧城市建設(shè)的關(guān)鍵一環(huán)。

目前，三維點(diǎn)云數(shù)據(jù)主要通過激光雷達(dá)（light detection and ranging，LiDAR）技術(shù)和影像密集匹配技術(shù)來獲取。前者雖然可以在短時(shí)間內(nèi)快速獲取到數(shù)以百萬(wàn)計(jì)的地物點(diǎn)三維坐標(biāo)并得到相應(yīng)的三維點(diǎn)云模型[1-2]，但相對(duì)于獲取成本低、效率高、紋理信息豐富、空間分辨率高、測(cè)繪范圍大、人工交互少[3]的影像密集匹配技術(shù)，依然存在一些不足[4-6]，因而后者受到了攝影測(cè)量與遙感界的廣泛關(guān)注。

自20世紀(jì)50年代起，基于航攝影像的匹配算法被提出后，越來越多的學(xué)者開始致力于影像的稀疏匹配方法研究。直到20世紀(jì)90年代，隨著具有生成數(shù)字表面模型和數(shù)字地形模型功能的攝影測(cè)量商業(yè)軟件的出現(xiàn)[1]，人們紛紛著手于密集匹配算法的研究。密集匹配技術(shù)在計(jì)算機(jī)視覺領(lǐng)域也被稱為立體匹配技術(shù)，在其數(shù)十年的發(fā)展中，已有許多文獻(xiàn)對(duì)其算法進(jìn)行了歸類對(duì)比分析[1, 7-11]，美國(guó)明德學(xué)院的Scharstein和Szeliski還創(chuàng)建了廣受關(guān)注的計(jì)算機(jī)視覺評(píng)測(cè)網(wǎng)站[12]，不僅提供了一系列權(quán)威的測(cè)試數(shù)據(jù)，還提供了量化誤差的算法測(cè)試平臺(tái)，只需要將匹配結(jié)果提交到平臺(tái)就可以獲得權(quán)威的性能分析并參與算法排名。該網(wǎng)站自2001年開放以來，已公布了430多種影像密集匹配算法，圖 1為Middlebury網(wǎng)站公布的各年度密集匹配算法數(shù)量（統(tǒng)計(jì)時(shí)間截至2022-11-20）。通過分析不難發(fā)現(xiàn)：

圖1Middlebury網(wǎng)站公布的2001—2022年密集匹配算法數(shù)量

1）雙目影像的密集匹配算法數(shù)量呈逐年上升趨勢(shì)。這表明雙目影像的密集匹配問題正在被越來越多的學(xué)者所關(guān)注，同時(shí)也說明雙目影像的密集匹配技術(shù)依然是一個(gè)熱點(diǎn)研究問題。

2）多視影像密集匹配算法的年度數(shù)量明顯偏少，自2014年開始逐年下降。多視密集匹配中的多角度影像可以有效改善遮擋區(qū)域的匹配效果，特別是近些年發(fā)展起來的傾斜攝影測(cè)量技術(shù)[13]，融合了傳統(tǒng)的航空攝影測(cè)量技術(shù)和近景攝影測(cè)量技術(shù)[14]?，F(xiàn)有的多視密集匹配模型主要?jiǎng)澐譃閮深悾夯诙嘁暤钠ヅ淠Ｐ图盎诙嘁暳Ⅲw融合的匹配模型[15]。前者同時(shí)考慮多條交會(huì)光線以獲得更為精確穩(wěn)健的匹配結(jié)果，匹配模型較為復(fù)雜，且大部分方法匹配效率較低[16]，并不適合于大范圍的影像匹配，更多的此類匹配模型方法介紹可參見文獻(xiàn)[17-18]；后者則是將多視密集匹配視為以單個(gè)立體像對(duì)（雙目影像對(duì)）為匹配單元的多個(gè)立體像對(duì)的匹配結(jié)果融合問題，該類模型可以通過粗差剔除的方法更有效地改善遮擋區(qū)的匹配精度，效率更高、操作簡(jiǎn)便、易于并行加速，適用于大范圍的影像匹配，其核心仍然是雙目密集匹配技術(shù)。因此，相比于多視影像密集匹配，雙目影像的密集匹配更為重要，是更為常用的密集匹配方法，這也是本文著重對(duì)雙目密集匹配進(jìn)行綜合論述的初衷之一。

近年來，具有相當(dāng)熱度的基于深度學(xué)習(xí)的密集匹配方法大體上可以分為分布式方法和端到端的方法[11]，后者為當(dāng)前主流算法。然而，分布式方法對(duì)于弱紋理、視差不連續(xù)區(qū)域以及遮擋區(qū)域的匹配效果并不理想，端到端方法則需要較高的計(jì)算機(jī)內(nèi)存消耗。

基于深度學(xué)習(xí)的方法雖然在常規(guī)區(qū)域可以獲得更優(yōu)的匹配效果，但對(duì)于弱紋理、視差不連續(xù)以及遮擋區(qū)域的匹配效果仍然存在劣勢(shì)，多數(shù)的方法受限于訓(xùn)練標(biāo)簽，文獻(xiàn)[19]詳細(xì)分析了基于深度學(xué)習(xí)的影像密集匹配算法，此處不再贅述。

本文通過對(duì)現(xiàn)有的雙目影像密集匹配算法進(jìn)行綜合分析，著重對(duì)傳統(tǒng)的密集匹配算法進(jìn)行總結(jié)，以期能系統(tǒng)地闡述影像密集匹配技術(shù)的發(fā)展現(xiàn)狀。

本文首先對(duì)密集匹配算法的匹配過程進(jìn)行了梳理，按照局部密集匹配與全局密集匹配對(duì)雙目密集匹配算法進(jìn)行了系統(tǒng)的分類概述，并指出各類算法的優(yōu)缺點(diǎn)；然后對(duì)攝影測(cè)量中的密集匹配技術(shù)進(jìn)行討論，對(duì)比分析了攝影測(cè)量場(chǎng)景與計(jì)算機(jī)視覺場(chǎng)景之間的差異，同時(shí)對(duì)影像遮擋機(jī)理進(jìn)行了剖析，詳細(xì)闡述了遮擋檢測(cè)與遮擋填充的處理方法，為解決密集匹配的空洞問題奠定了理論基礎(chǔ)；最后著重闡述了筆者對(duì)雙目密集匹配方法發(fā)展趨勢(shì)的展望。

01 雙目密集匹配

雙目密集匹配即從一個(gè)立體像對(duì)的二維影像數(shù)據(jù)信息中提取并恢復(fù)對(duì)應(yīng)物體的三維空間信息?，F(xiàn)有的雙目密集匹配算法依據(jù)同名點(diǎn)搜索空間的不同可分為基于像方空間的密集匹配算法和基于物方空間的密集匹配算法[20]。

基于像方空間的雙目密集匹配算法通常采用水平核線影像作為輸入影像，又稱為單基線密集匹配算法，是一種常用的匹配算法，其核線影像包括框幅式影像的核線影像和線陣推掃式影像的核線影像。

前者是從航空攝影測(cè)量和地面攝影測(cè)量中經(jīng)常使用的中心投影影像所獲得的核線影像，其核線模型基本分為兩種，基于數(shù)字影像的幾何糾正模型和基于共面條件的模型。其中，基于數(shù)字影像幾何糾正的核線糾正模型更為簡(jiǎn)單常用；線陣推掃式影像的核線影像多為從衛(wèi)星遙感影像所獲得的核線影像，其核線模型也分為兩種，基于多項(xiàng)式擬合的核線模型和基于投影軌跡法的核線模型[21]。基于投影軌跡法的核線模型因其具有更加嚴(yán)密的理論而被廣泛使用[22-23]。單基線密集匹配算法通過核線約束對(duì)左右影像進(jìn)行逐像素的匹配，并利用三角測(cè)量原理計(jì)算立體像對(duì)的視差值，最終將視差轉(zhuǎn)換為物方三維坐標(biāo)，即獲得2D影像點(diǎn)的3D地面坐標(biāo)（詳見圖 2）。

具體計(jì)算過程可以概括為4步：匹配代價(jià)計(jì)算、匹配代價(jià)聚合、視差計(jì)算與精化以及物方三維坐標(biāo)計(jì)算[7]。匹配代價(jià)計(jì)算是以左核線影像為參考影像、右核線影像為目標(biāo)影像，在指定的視差搜索范圍內(nèi)，計(jì)算待匹配像素與每個(gè)視差下的候選像素之間的視差值[24]，并將其存儲(chǔ)為階的視差矩陣，其中為影像寬度，為影像高度，從而獲得視差圖；匹配代價(jià)聚合是指對(duì)初始視差值在基于單個(gè)像素的支持窗口內(nèi)進(jìn)行濾波，剔除不合理的視差值；通過聚合而獲得的每個(gè)像素會(huì)對(duì)應(yīng)多個(gè)不同的視差值，視差計(jì)算與精化是為每個(gè)像素選取最佳的視差值[25]，一般采用勝者為王策略來優(yōu)選視差值，即在單個(gè)像素的所有初始視差值中，選擇最小的代價(jià)值作為最佳視差，剔除錯(cuò)誤視差，同時(shí)檢測(cè)并修復(fù)無(wú)效視差[26]；物方三維坐標(biāo)計(jì)算是在已知影像內(nèi)外方位元素的前提下，利用視差值求解目標(biāo)點(diǎn)坐標(biāo)，即首先根據(jù)已知的相機(jī)內(nèi)方位元素與視差值求出像素點(diǎn)的像方坐標(biāo)，然后結(jié)合已知的影像外方位元素將像方坐標(biāo)轉(zhuǎn)換為大地測(cè)量坐標(biāo)，從而求出目標(biāo)點(diǎn)的物方三維坐標(biāo)。

圖2基于像方空間的雙目密集匹配

基于物方空間的密集匹配是在基于像方空間密集匹配算法之后發(fā)展起來的算法，即將密集匹配算法從像方空間轉(zhuǎn)至物方空間。通常直接以地面高程方向或影像視線方向?yàn)橥c(diǎn)搜索方向，并將指定的物方面元反投影至影像中，以影像中投影面元之間的相似性來確定物方點(diǎn)。現(xiàn)有的基于物方空間密集匹配算法多是在鉛垂線軌跡法（vertical line locus，VLL）的基礎(chǔ)上發(fā)展起來的。本文以VLL算法為例對(duì)基于物方空間的雙目密集匹配過程進(jìn)行介紹。圖 3展示了VLL原理，假定在物方有一條鉛垂線軌跡，其對(duì)應(yīng)影像上的投影也是一條直線（圖 3中的紅色虛線），沿此鉛垂線方向搜索地面目標(biāo)點(diǎn)所對(duì)應(yīng)的左右影像中的像點(diǎn)與即可確定目標(biāo)點(diǎn)的高程。具體步驟如下：首先給定目標(biāo)點(diǎn)P的平面坐標(biāo)以及近似最低高程，并根據(jù)精度需求確定高程搜索步距；然后根據(jù)目標(biāo)點(diǎn)P的平面坐標(biāo)及候選高程值計(jì)算目標(biāo)點(diǎn)在左右影像上的像點(diǎn)坐標(biāo)，分別以這兩點(diǎn)為中心在各自影像上選取匹配窗口，計(jì)算匹配測(cè)度；令，重復(fù)前述步驟；最后根據(jù)匹配測(cè)度最大值確定目標(biāo)點(diǎn)的高程值，目標(biāo)點(diǎn)的物方三維坐標(biāo)為，詳細(xì)過程參見文獻(xiàn)[27]。

圖3基于物方空間的雙目密集匹配

基于物方的密集匹配算法實(shí)質(zhì)依然是基于影像的幾何定向參數(shù)對(duì)同名像點(diǎn)進(jìn)行反復(fù)前方交會(huì)，從而獲取物方點(diǎn)的過程[16]。由于基于物方空間的密集匹配算法可以同時(shí)處理多幅影像，這種方法多被用于多視影像的密集匹配中[28]，如常見的GC3（geometrically constrained cross-correlation）[29]及其改進(jìn)模型AMMGC（adaptive multi-image matching with geometric constraints）[30]、MVLL（modified vertical line locus）[31]、SGVLL（sem-global vertical line locus）[32]等。 雙目密集匹配當(dāng)前采用的多是基于像方空間的雙目密集匹配算法，依據(jù)其是否隱式地使用了光滑假設(shè)而被區(qū)分為局部密集匹配和全局密集匹配兩種[7]。具體說來，在匹配算法中使用了代價(jià)聚合和視差確定組合的為局部密集匹配方法，使用了能量函數(shù)優(yōu)化的為全局密集匹配方法。

1.1 局部密集匹配

利用各個(gè)像素的鄰域信息求解對(duì)應(yīng)視差的局部密集匹配算法又被稱為基于窗口的密集匹配算法[33]，此類算法包含以上雙目密集匹配算法完整的步驟且在代價(jià)聚合階段隱式地使用了光滑假設(shè)約束。對(duì)于局部密集匹配算法而言，在匹配代價(jià)聚合時(shí)，選擇適當(dāng)?shù)钠ヅ浯翱谑菦Q定匹配精度的關(guān)鍵。 早期使用的單一固定窗口法因限制了窗口的尺寸大小，使其易在對(duì)象邊界處發(fā)生重疊，從而錯(cuò)誤地聚合了不同區(qū)域的匹配代價(jià)，導(dǎo)致地物邊緣粗化模糊[34]，使其在深度不連續(xù)處、弱紋理區(qū)域以及重復(fù)紋理區(qū)域具有較高的誤匹配率。為此，基于窗口的密集匹配方法逐漸衍生為自適應(yīng)窗口法、自適應(yīng)權(quán)重法以及非前向平行算法等。

1.1.1 自適應(yīng)窗口法

局部密集匹配所選擇的窗口大小既要足夠大，以包括足夠的強(qiáng)度變化，又要足夠小，以避免因覆蓋對(duì)應(yīng)場(chǎng)景點(diǎn)深度（即視差）變化的整個(gè)區(qū)域而引起的失真問題[35]，因而演化出了可以根據(jù)局部強(qiáng)度和視差變化而自適應(yīng)地選擇窗口的自適應(yīng)窗口法。主要是依據(jù)局部區(qū)域的像素顏色、空間距離、紋理熵等屬性特征的相關(guān)性來改變聚合窗口的大小、形狀、位置和數(shù)量，從而提高視差圖的精度。將現(xiàn)今較為常用的具有代表性的自適應(yīng)窗口法概括為單窗口算法與多窗口算法，算法的簡(jiǎn)要描述和存在的優(yōu)缺點(diǎn)具體見表 1。

表1 自適應(yīng)窗口法

總而言之，基于自適應(yīng)窗口法可以總結(jié)如下：

1）最早興起的自適應(yīng)矩形單窗口法多是基于積分圖像與四象限掩模等技術(shù)通過改變矩形窗口的大小或長(zhǎng)寬比例來減少位于不正確深度區(qū)域的不良像素?cái)?shù)量，提高準(zhǔn)確率。相比于固定窗口法，其具有更高的匹配精度，但卻要高度依賴于初始視差的估計(jì)，并且矩形窗口并不適合于接近具有任意形狀的深度不連續(xù)區(qū)。因而該類方法在視差邊緣處具有相對(duì)較低的準(zhǔn)確度。

2）自適應(yīng)形狀單窗口算法多是基于各向異性局部多項(xiàng)式逼近技術(shù)或是通過局部屬性構(gòu)建直立交叉局部支持骨架等方式來構(gòu)建自適應(yīng)形狀窗口。相較于自適應(yīng)矩形單窗口法，這種方法的窗口形狀自適應(yīng)能力有了較大的提高，以至于在深度不連續(xù)區(qū)域的匹配準(zhǔn)確度得到了較大的提升，但窗口形狀或是模型的通用性仍然不高，很多算法需要特定的參數(shù)甚至是需要在特定的條件下才能得以實(shí)現(xiàn)。

3）自適應(yīng)多窗口算法通常是結(jié)合多個(gè)單窗口來匹配相對(duì)復(fù)雜的圖像區(qū)域，相比于自適應(yīng)單窗口法，這類方法在低紋理區(qū)域以及邊緣區(qū)域的匹配準(zhǔn)確度有了更大的提升，具有更廣泛的適用性。但因其較高的計(jì)算復(fù)雜度，需要很高的計(jì)算成本，匹配效率有所降低。 近年來，為提高自適應(yīng)窗口算法的運(yùn)算速率、加強(qiáng)匹配的時(shí)效性，很多基于現(xiàn)場(chǎng)可編程門陣列（field programmable gate array，FPGA）或圖形處理器（graphics processing unit，GPU）硬件加速的局部方法開始流行[51]。其中，F(xiàn)PGA開發(fā)的靈活性以及對(duì)高速信號(hào)處理的優(yōu)越性，使其成為了近些年數(shù)字系統(tǒng)開發(fā)的核心部件；GPU技術(shù)利用硬件的并行計(jì)算能力，將算法設(shè)計(jì)為高度并行，同時(shí)使用多個(gè)計(jì)算核心進(jìn)行算法運(yùn)算，具有明顯的加速效果[52]。

1.1.2 自適應(yīng)權(quán)重法

自適應(yīng)權(quán)重法是推動(dòng)局部密集匹配算法發(fā)展的關(guān)鍵。自2006年Yoon等[53]首次提出可以在匹配質(zhì)量與全局匹配算法相媲美的局部匹配方法后，局部匹配算法再次被推向密集匹配研究的高潮。這種方法大多是依據(jù)局部區(qū)域的像素顏色、空間距離、甚至是梯度等屬性特征的相似度來分配匹配窗口內(nèi)原始代價(jià)的權(quán)值，權(quán)值計(jì)算方式是實(shí)現(xiàn)該類方法的關(guān)鍵?；诓煌臋?quán)重值主函數(shù)，表 2對(duì)其進(jìn)行了歸類分析。

表2 自適應(yīng)權(quán)重法

根據(jù)自適應(yīng)權(quán)重法的權(quán)重確定方式可總結(jié)如下： 1）應(yīng)用最為廣泛的基于濾波的自適應(yīng)權(quán)重法多是根據(jù)顏色較為一致的區(qū)域視差值較為接近、連續(xù)區(qū)域具有更加相近的視差值或是梯度等原理來為匹配窗口內(nèi)的每個(gè)像素分配權(quán)重。該類方法中的雙邊濾波法[42, 53, 59]具有相對(duì)較好的匹配精度，特別是在深度或是視差斷裂區(qū)域，但計(jì)算效率并不高。

為了解決雙邊濾波的計(jì)算效率問題，人們引入了基于圖像的引導(dǎo)濾波算法[34, 45, 61, 65-67]，因其具有更高的匹配精度與計(jì)算效率而被更廣泛使用。總體而言，此類方法可以改善視差邊界的匹配效果，最終獲得一個(gè)較為滿意的匹配結(jié)果。 2）基于分割的自適應(yīng)權(quán)重法是基于假定分割塊的邊緣與深度不連續(xù)區(qū)域保持一致，且每個(gè)分割塊具有相同視差或滿足某種關(guān)系（如仿射變換）的前提下，以待匹配點(diǎn)是否落在分割塊內(nèi)作為定權(quán)的參考依據(jù)。這類方法在遮擋區(qū)域與無(wú)紋理區(qū)域會(huì)具有較好的匹配效果。 3）自適應(yīng)權(quán)重法可以被劃分為基于濾波的自適應(yīng)權(quán)重法與基于分割的自適應(yīng)權(quán)重法。相比于自適應(yīng)窗口法，這種方法具有更高的匹配精度和更小的計(jì)算代價(jià)。但這類方法需要對(duì)每個(gè)像素進(jìn)行獨(dú)立的加權(quán)計(jì)算，計(jì)算復(fù)雜度相對(duì)較高。

1.1.3 非前向平行法

自適應(yīng)窗口法和自適應(yīng)權(quán)重法是基于匹配窗口內(nèi)的像素具有相同視差的假設(shè)，即假設(shè)影像平面與影像的匹配窗口所對(duì)應(yīng)的實(shí)際場(chǎng)景表面相平行，稱之為前向平行。然而前向平行假設(shè)對(duì)于深度不連續(xù)區(qū)域以及表面傾斜區(qū)域的影像匹配并不適用。為此，針對(duì)具有傾斜結(jié)構(gòu)的場(chǎng)景，衍生出了非前向平行法。 相對(duì)于自適應(yīng)窗口法與自適應(yīng)權(quán)重法，非前向平行法的興起較晚，至今僅有十余年的發(fā)展歷史[68]。這種方法通過傾斜窗口來估計(jì)與具有傾斜結(jié)構(gòu)場(chǎng)景相符的支持區(qū)域。比較常見的方法當(dāng)屬PatchMatch算法，這種算法通過隨機(jī)采樣快速尋找影像面片之間的近似最近鄰匹配，再根據(jù)影像中的自然一致性將這些匹配信息快速傳播至周圍區(qū)域。但此方法對(duì)于病態(tài)輸入具有較差的收斂性，而且容易產(chǎn)生重影或羽狀偽影[68]。為此，基于PatchMatch算法衍生出了一系列常用的方法，包括PMBP[69]、PM-Huber[70]、PM-PM[71]、PMF[72]、PMSC[73]以及近兩年來較受歡迎的LocalExp算法[74]。 基于PatchMatch衍生出的非前向平行算法是目前較受歡迎的雙目密集匹配方法之一。

該系列算法主要是通過改變搜索策略和引入外來項(xiàng)策略實(shí)現(xiàn)對(duì)原有算法的改進(jìn)，具體表現(xiàn)為： 1）改進(jìn)搜索策略。將原算法擴(kuò)展到跨尺度搜索、基于核線的最近鄰搜索以及多個(gè)最近鄰匹配搜索等，可以更有效地顧及全局信息，獲得具有亞像素級(jí)精度的視差結(jié)果。 2）引入外來項(xiàng)。通過引入外來項(xiàng)，包括圖割以及置信度傳播等來建立PatchMatch與外來項(xiàng)之間的聯(lián)系，即將原有算法的最佳特征與外來項(xiàng)的最佳特征相結(jié)合以提高計(jì)算效率和準(zhǔn)確性。 使用3D標(biāo)簽的PatchMatch算法不僅避免了前向平行偏差，而且基于此算法改進(jìn)的很多方法目前已經(jīng)達(dá)到了亞像素級(jí)的匹配精度，但無(wú)論是改變搜索策略還是引入外來項(xiàng)的改進(jìn)算法都高度依賴于影像面片之間的初始匹配結(jié)果，均需要更長(zhǎng)的計(jì)算時(shí)間。 總之，非前向平行法解決了非平行表面的匹配歧義問題，填補(bǔ)了局部匹配方法關(guān)于非前向平行假設(shè)的空缺，但對(duì)于低紋理區(qū)域的匹配精度以及算法的整體匹配效率仍具有提升空間。

1.2 全局密集匹配

基于馬爾可夫隨機(jī)場(chǎng)（Markov random field，MRF）模型優(yōu)化的全局密集匹配方法不同于局部密集匹配方法會(huì)在代價(jià)聚合階段使用隱式光滑假設(shè)，這種方法通常不執(zhí)行聚合步驟，而是通過能量函數(shù)的平滑項(xiàng)來實(shí)現(xiàn)顯式光滑假設(shè)約束，并通過解算全局最優(yōu)能量函數(shù)來求解。全局能量函數(shù)包括表示像素自身相似度度量的數(shù)據(jù)項(xiàng)和表示相鄰像素間平滑程度的平滑項(xiàng)，該函數(shù)將密集匹配問題轉(zhuǎn)換為求取全局能量函數(shù)最小化問題[75]。因此，全局能量函數(shù)的優(yōu)化方式以及能量函數(shù)的最小化求解是全局密集匹配方法的研究重點(diǎn)。 全局密集匹配的能量?jī)?yōu)化算法中應(yīng)用較廣泛的方法包括動(dòng)態(tài)規(guī)劃法、置信度傳播法和圖割法。

1.2.1 動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法又稱為掃描線優(yōu)化法[76]，在20世紀(jì)90年代被引入到全局密集匹配算法中，是最早興起的一類用于解決密集匹配問題的全局優(yōu)化方法[77]。早期的動(dòng)態(tài)規(guī)劃算法僅是通過單獨(dú)對(duì)影像的每一條掃描線進(jìn)行優(yōu)化來完成一維動(dòng)態(tài)規(guī)劃，但僅考慮一維層面的優(yōu)化并不能夠?qū)崿F(xiàn)影像區(qū)域的整體最優(yōu)。因此，針對(duì)不同掃描線之間的斷層問題即條紋問題，又提出了諸如文獻(xiàn)[78]等解決方案，但這些方法也同時(shí)會(huì)產(chǎn)生豎直條紋的影響。 Hirschmuller[79]為避免在掃描線優(yōu)化算法中單一路徑產(chǎn)生的條紋效應(yīng)，首次提出了一種基于多路徑動(dòng)態(tài)規(guī)劃策略的半全局匹配（semi-global matching，SGM）算法。這種算法將多個(gè)不同的掃描線路徑以不同的角度運(yùn)行來逼近二維優(yōu)化，即對(duì)影像進(jìn)行多次一維能量?jī)?yōu)化。SGM算法因考慮了匹配目標(biāo)邊界的精確性、光照變化的魯棒性以及計(jì)算效率[80]而具有很好的應(yīng)用價(jià)值。因而后續(xù)涌現(xiàn)出了大量的基于SGM的改進(jìn)算法（見表 3）。

表3 基于SGM改進(jìn)的算法

基于SGM的改進(jìn)算法多數(shù)是出于降低計(jì)算復(fù)雜度和內(nèi)存空間以及提高計(jì)算性能的目的來對(duì)算法進(jìn)行改進(jìn)的，常見的較為有效的改進(jìn)策略包括由粗到精的分層策略、基于影像邊緣的懲罰策略以及與census相關(guān)性相結(jié)合等策略。這類算法不僅可以避免動(dòng)態(tài)規(guī)劃法產(chǎn)生的條紋效應(yīng)，而且在無(wú)需迭代的同時(shí)對(duì)參數(shù)的選擇也不具有敏感性，是近年來最受歡迎的一種密集匹配算法。但很多算法在提高算法準(zhǔn)確度的同時(shí)，無(wú)形中也增加了算法的復(fù)雜度及運(yùn)行時(shí)間。于是算法的硬件可實(shí)現(xiàn)性成為提高算法效率的關(guān)鍵，其中比較常用的硬件優(yōu)化策略為基于GPU的硬件并行優(yōu)化與基于FPGA的硬件并行優(yōu)化。

1.2.2 置信度傳播法

置信度傳播（belief propagation，BP）算法不同于需要單獨(dú)計(jì)算每條掃描線最優(yōu)解的動(dòng)態(tài)規(guī)劃法，該算法是通過多次迭代來計(jì)算整個(gè)影像的最優(yōu)解。BP算法將影像作為MRF來解釋，影像中的每個(gè)像素視為觀測(cè)節(jié)點(diǎn)，影像中的像素灰度值作為觀測(cè)值，視差是觀測(cè)的隱藏節(jié)點(diǎn)標(biāo)簽，相鄰節(jié)點(diǎn)通過每一次迭代來互相傳遞消息，最終的視差則是通過具有最大概率的標(biāo)簽來確定[93]。 自2003年Sun等[94]將BP算法引進(jìn)到密集匹配算法中后，越來越多的基于BP的改進(jìn)算法被提出，包括HBP[95]、CSB[96]、BP-M[97]、SBP[98]、LBP[99]以及SDT-BP[100]等算法。這些算法具有更好的匹配效果，但同時(shí)也會(huì)帶來復(fù)雜的計(jì)算問題，導(dǎo)致需要更長(zhǎng)的計(jì)算時(shí)間，實(shí)時(shí)性較差。這也是為什么近年來所提出的BP算法大都是出于降低算法的復(fù)雜度、提高算法速度以及內(nèi)存優(yōu)化的目的來對(duì)BP算法進(jìn)行改進(jìn)的。

1.2.3 圖割法

圖割法是除了BP算法以外的另一類基于二維層面的較為有效的全局密集匹配方法。這種方法將視差分配問題轉(zhuǎn)化為全局能量函數(shù)最小化問題。具體而言，圖割法將影像中的像素作為節(jié)點(diǎn)，將像素的視差值作為標(biāo)簽構(gòu)建成無(wú)向圖，采用最大流和最小割算法求解對(duì)應(yīng)能量最小的標(biāo)簽賦值方案，即最優(yōu)視差。不同的是，BP方法通過在MRF圖中迭代地將消息從當(dāng)前節(jié)點(diǎn)傳遞到鄰近節(jié)點(diǎn)，從而使能量函數(shù)最小化，圖割法是將最大流和最小割算法應(yīng)用于從MRF圖中提取的能量流結(jié)構(gòu)中，從而給出最小能量解[101]。 圖割法因構(gòu)建無(wú)向圖時(shí)會(huì)有大量節(jié)點(diǎn)且運(yùn)算過程需要進(jìn)行多次迭代而使整體算法的空間復(fù)雜度和時(shí)間復(fù)雜度相對(duì)較高。因此，基于圖割法的全局密集匹配方法多是通過減少搜索空間或是搜索路徑以及簡(jiǎn)化圖等方式來對(duì)算法進(jìn)行加速。雖然圖割法在最大流算法的效率方面已經(jīng)有了很大的提高，但當(dāng)視差搜索范圍較大時(shí)，仍無(wú)法滿足實(shí)時(shí)性應(yīng)用的需求。

02 攝影測(cè)量密集匹配

綜合攝影測(cè)量領(lǐng)域的密集匹配算法不難發(fā)現(xiàn)，基于像方空間的雙目密集匹配算法幾乎都是基于計(jì)算機(jī)視覺場(chǎng)景中的匹配算法，這就使得其無(wú)法獲得更為突出的匹配效果。因此，對(duì)于攝影測(cè)量場(chǎng)景而言，密集匹配問題除了要考慮密集匹配算法本身的特點(diǎn)外，還要考慮由于場(chǎng)景差異所帶來的影響。

2.1 計(jì)算機(jī)視覺場(chǎng)景與攝影測(cè)量場(chǎng)景的差異

攝影測(cè)量場(chǎng)景不同于計(jì)算機(jī)視覺場(chǎng)景，后者一般包括多數(shù)的室內(nèi)場(chǎng)景以及少數(shù)的街景（自動(dòng)識(shí)別）。這里主要討論計(jì)算機(jī)視覺的室內(nèi)場(chǎng)景與航空航天攝影測(cè)量的場(chǎng)景差異。根據(jù)大量的參考文獻(xiàn)以及公開的數(shù)據(jù)集，可將兩種場(chǎng)景的差異大致概括為相機(jī)位置、光源位置、光照特點(diǎn)、背景特點(diǎn)以及像幅大小等，詳見圖 4。

圖4 影像數(shù)據(jù)的攝取場(chǎng)景 計(jì)算機(jī)視覺場(chǎng)景與攝影測(cè)量場(chǎng)景的差異包括：

1）在計(jì)算機(jī)視覺場(chǎng)景中，相機(jī)通常是置于場(chǎng)景的側(cè)前方，近距離地?cái)z取極小圖幅影像，因而獲取的影像可以明顯地區(qū)分前景與背景。前景的物體輪廓也格外的清晰完整，地物間所存在的遮擋問題通常也可以通過人工干預(yù)盡量規(guī)避；而在攝影測(cè)量場(chǎng)景中，相機(jī)是通過自上而下的方式遠(yuǎn)距離地?cái)z取大圖幅影像，地物結(jié)構(gòu)更為復(fù)雜，前景與背景會(huì)發(fā)生變化，地面上的所有地物即為前景，背景即為地面，地物間存在的遮擋問題是不可避免的。

2）計(jì)算機(jī)視覺室內(nèi)場(chǎng)景中的人造點(diǎn)光源的位置、光線強(qiáng)度屬于人為可控因素，既可以盡量規(guī)避陰影的影響，也可以通過增強(qiáng)前景與背景的對(duì)比度來將前景與背景清晰區(qū)分，幾乎不存在陰影的干擾。雖然有少數(shù)影像數(shù)據(jù)中的背景存在陰影，但背景一般為平整的平面，即同一視差背景，因而對(duì)匹配結(jié)果并無(wú)明顯的影響；而攝影測(cè)量的室外場(chǎng)景的光源位置與強(qiáng)度是人為不可控的太陽(yáng)光，近乎平行光傳播。因而，影像質(zhì)量更容易受到地物陰影的影響，特別是城區(qū)內(nèi)的高層建筑物。陰影包括自影、本影以及半影，自影與本影則是影響影像質(zhì)量的主要因素。

3）計(jì)算機(jī)視覺室內(nèi)場(chǎng)景的環(huán)境特點(diǎn)較為單一可控且穩(wěn)定，而攝影測(cè)量室外場(chǎng)景具有更少的人為可控因素，環(huán)境更為復(fù)雜。攝影測(cè)量場(chǎng)景更易受天氣變化、輻射畸變等因素的影響，使得密集匹配影像對(duì)之間存在更多的差異，嚴(yán)重影響了影像對(duì)之間的相關(guān)性表達(dá)，特別是高分辨率衛(wèi)星遙感影像。對(duì)于高分辨率衛(wèi)星遙感影像而言，不論是同軌立體影像對(duì)間存在的幾分鐘時(shí)間差，還是異軌立體影像對(duì)間更長(zhǎng)的時(shí)間差，都會(huì)帶來不可忽視的輻射差異，致使影像對(duì)之間存在非線性輻射差異，影響影像對(duì)之間的相關(guān)性表達(dá)。

4）攝影測(cè)量場(chǎng)景的立體像對(duì)獲取要求更為嚴(yán)格，需要地理參考數(shù)據(jù)的同時(shí)又要考慮像對(duì)的基線長(zhǎng)短、重疊度、交會(huì)角大小等問題（包括衛(wèi)星遙感影像，影像的獲取和幾何分析通常被看作是航空攝影測(cè)量的直接擴(kuò)展）[16, 102]。在攝影測(cè)量影像密集匹配中，具有一定地面分辨率的近似平行的影像對(duì)需要具有一定的航向與旁向重疊度，同時(shí)需要精確地獲取相機(jī)的空間位置與姿態(tài)信息以及地面控制點(diǎn)的三維坐標(biāo)等定位參數(shù)信息。而對(duì)于立體視覺場(chǎng)景而言，三維信息的恢復(fù)通常以左右相機(jī)的相對(duì)位置為準(zhǔn)，并不需要地理參考，特別是計(jì)算機(jī)視覺領(lǐng)域的熱門研究SfM（structure from motion）技術(shù)以及SLAM（simultaneous localization and mapping）技術(shù)，它們并不需要預(yù)先知道相機(jī)的三維坐標(biāo)和姿態(tài)或是地面控制點(diǎn)的三維坐標(biāo)，即無(wú)需環(huán)境的先驗(yàn)信息，只需要已知相機(jī)的相對(duì)位置和場(chǎng)景幾何以及高度重疊的像片集，便可實(shí)現(xiàn)影像的獲取與計(jì)算工作，三維點(diǎn)云數(shù)據(jù)也可以用任意坐標(biāo)系統(tǒng)來表示[103-104]。

5）基于深度學(xué)習(xí)方法的不同在于應(yīng)用場(chǎng)景的差異。作為計(jì)算機(jī)視覺領(lǐng)域中的研究熱點(diǎn)，基于深度學(xué)習(xí)的密集匹配算法可以獲得更好的匹配效果。然而，對(duì)于大尺度的攝影測(cè)量場(chǎng)景影像而言，一方面，大量真實(shí)樣本的模型參數(shù)訓(xùn)練必然需要用極高的成本來獲取真值數(shù)據(jù)，更為復(fù)雜且不同的室外環(huán)境令預(yù)先訓(xùn)練好的模型的遷移學(xué)習(xí)能力受到影響[105-106]；另一方面，基于深度學(xué)習(xí)的方法很難直接應(yīng)用到完整的高分辨率影像數(shù)據(jù)中，即使是通過分塊處理來適應(yīng)GPU的計(jì)算能力，也會(huì)因?yàn)閱螇K像素信息太少而無(wú)法保證匹配結(jié)果的精度。

2.2 遮擋處理

對(duì)于攝影測(cè)量密集匹配中的大幅面城市影像而言，影響雙目密集匹配質(zhì)量的一個(gè)關(guān)鍵因素當(dāng)屬建筑物的遮擋問題。而不同的建筑物高度或是攝影中心（視點(diǎn)）相對(duì)建筑物的位置以及建筑物之間的位置關(guān)系都會(huì)帶來不同的遮擋效果，建筑物間存在的遮擋問題可被簡(jiǎn)要概括為5種情況，詳見圖5。

圖5 不同建筑物場(chǎng)景的遮擋可見性分析 圖5中，有5種不同的建筑物遮擋情況。情況1為單棟建筑物1被左右相機(jī)拍攝所呈現(xiàn)的可見性情況；情況2與情況3則表示對(duì)于建筑物1，具有不同相對(duì)位置關(guān)系的相鄰建筑物2被左右相機(jī)拍攝所呈現(xiàn)的兩種可見性情況；情況4與情況5則表示建筑物1的屋頂附屬建筑物2被左右相機(jī)拍攝所呈現(xiàn)的兩種可見性情況。從以上幾種遮擋情況不難發(fā)現(xiàn)：對(duì)于高層建筑物而言，由于自上而下的拍攝角度以及視點(diǎn)與建筑物之間的相對(duì)位置關(guān)系，建筑物的底部結(jié)構(gòu)以及邊緣特征會(huì)因?yàn)檎趽醵豢梢?，進(jìn)而無(wú)法完成正確的匹配，最終會(huì)使得匹配結(jié)果中被建筑物遮擋的部分因?yàn)樾畔⑷笔Ф霈F(xiàn)空洞。因此，遮擋處理也成為了提高密集匹配質(zhì)量的關(guān)鍵。 遮擋處理包括遮擋檢測(cè)與遮擋填充。對(duì)于遮擋檢測(cè)，多數(shù)的方法都是選擇利用一定的約束條件去估計(jì)被遮擋像素的視差，進(jìn)而實(shí)現(xiàn)遮擋區(qū)域的檢測(cè)。表4列出了幾種常見的約束條件。

表4 用于檢測(cè)遮擋像素的約束條件

除了這些常見的約束條件外，地面控制點(diǎn)約束[107]、對(duì)稱約束[108]、分割約束[109]、光度約束[110]、亮度差約束[111]等約束條件也被結(jié)合使用于遮擋檢測(cè)。 遮擋處理的另一個(gè)重要工作是對(duì)遮擋檢測(cè)到的異常值進(jìn)行遮擋填充處理。遮擋填充是指異常值在其鄰域中搜索具有最相似像素的視差值，并對(duì)其進(jìn)行迭代填充的過程。根據(jù)搜索策略的不同，將遮擋填充方法分為掃描線填充與最近鄰填充。 掃描線填充是指針對(duì)每個(gè)異常值像素所在的掃描線，向左側(cè)和右側(cè)搜索最近的有效像素的視差值來填充所有被遮擋的像素

。同時(shí)，由于被遮擋區(qū)域在通常情況下具有與背景對(duì)象相似的性質(zhì)，因而會(huì)將異常值分配給左右兩個(gè)有效視差值之間的最小值。然而，掃描線填充法因其是考慮在掃描線范圍內(nèi)進(jìn)行遮擋填充，所以這類方法會(huì)在視差圖結(jié)果中出現(xiàn)水平條紋，因而也有許多學(xué)者選擇使用中值濾波來對(duì)該種方法進(jìn)行改進(jìn)[34, 58, 112-113]。掃描線填充法雖然是一種簡(jiǎn)單有效的遮擋填充方法，但對(duì)于具有傾斜表面的場(chǎng)景并不具有可觀的填充效果。

不同于掃描線填充法的搜索策略，最近鄰插值法是選擇在不同的方向上搜索最近的有效像素，然后通過將有效視差傳播到相鄰的無(wú)效視差區(qū)域來執(zhí)行插值[9, 66, 110, 114-118]。最近鄰插值法相比于掃描線填充法是更為常用的一類遮擋填充方法，但該類方法常常會(huì)因?yàn)橄袼氐奶幚眄樞蚴腔趲缀雾樞蚨哂袩o(wú)效的填充結(jié)果。 簡(jiǎn)言之，借助條件約束檢測(cè)遮擋像素，并對(duì)檢測(cè)到的遮擋像素進(jìn)行視差值填充，來完成遮擋處理工作，雖然可以在一定程度上提高密集匹配結(jié)果的質(zhì)量，但也因?yàn)榇诉^程需要大量的迭代計(jì)算，使得整個(gè)密集匹配算法的計(jì)算復(fù)雜度有所增加。而且就目前的遮擋填充效果而言，遮擋填充仍是一個(gè)具有挑戰(zhàn)性的任務(wù)。

2.3 匹配速度與精度

影像匹配的速度、精度和可靠性是評(píng)價(jià)密集匹配算法質(zhì)量的3個(gè)重要指標(biāo)[18]，尤其是當(dāng)匹配算法已經(jīng)確保具有相當(dāng)?shù)目煽啃詴r(shí)，如何提高算法的匹配速度與匹配精度便成為更進(jìn)一步提高或衡量算法質(zhì)量的關(guān)鍵。 匹配速度的提升是滿足高效率匹配需求的關(guān)鍵，通常可以通過改變匹配算法本身的搜索策略和基于計(jì)算機(jī)硬件層面的并行優(yōu)化策略來實(shí)現(xiàn)。

常用的基于搜索策略的優(yōu)化算法包括上文所述的動(dòng)態(tài)規(guī)劃算法、松弛迭代算法、人工神經(jīng)元網(wǎng)絡(luò)以及遺傳算法[18]，其基本思想是通過改變搜索策略來盡可能多地避免遍歷搜索，提高匹配速度?；谟?jì)算機(jī)硬件層面的并行優(yōu)化策略包括基于中央處理器（central processing unit，CPU）的并行優(yōu)化、基于GPU的并行優(yōu)化以及基于FPGA的并行優(yōu)化，這種優(yōu)化策略是利用硬件的并行計(jì)算能力將算法設(shè)計(jì)為高度并行，同時(shí)使用多個(gè)計(jì)算核心進(jìn)行算法運(yùn)算，提高匹配速度[51]，而對(duì)于攝影測(cè)量場(chǎng)景中的高分辨率大幅面影像而言，顯然具有更為充裕的存儲(chǔ)空間的CPU更具優(yōu)勢(shì)。 匹配精度的提升是滿足高精度三維點(diǎn)云數(shù)據(jù)獲取的關(guān)鍵，除了目視判別外，現(xiàn)有的較為常見的精度評(píng)價(jià)指標(biāo)包括物方精度評(píng)定與像方精度評(píng)定兩種，常見的精度評(píng)價(jià)指標(biāo)及主要描述見表 5。

表5 精度評(píng)價(jià)指標(biāo)

匹配精度的提升通?？蓮膬煞矫嫒胧郑?/strong>一方面可以通過在基本的匹配算法的基礎(chǔ)上引入幾何約束的點(diǎn)、線、面以及尺度空間等特征約束條件來提升視差初值的可靠性以實(shí)現(xiàn)匹配精度的提升；另一方面可以通過后處理技術(shù)來實(shí)現(xiàn)視差的優(yōu)化以實(shí)現(xiàn)匹配精度的提升。 通過引入特征約束條件來提高算法的匹配精度是提高深度不連續(xù)區(qū)域以及弱紋理區(qū)域匹配精度的重要手段，特別是具有豐富平面幾何結(jié)構(gòu)特征的城市場(chǎng)景[120-124]，但其局限性在于幾何約束條件的適用范圍有限，多數(shù)方法僅適用于范圍較小，幾何特征相對(duì)豐富的區(qū)域，且約束條件也多為定制式，并不適用于其他的匹配算法[16, 106]；尺度空間特征約束條件是利用不同尺度的輸入圖像來檢測(cè)匹配關(guān)鍵點(diǎn)，也即尺度不變性，這種方法被更多地引入自適應(yīng)窗口法[37, 125-127]、自適應(yīng)權(quán)重法[128-132]以及SGM算法[133-135]中，然而這種方法卻會(huì)降低原算法的運(yùn)算速度。 后處理技術(shù)即是對(duì)視差值的優(yōu)化，視差優(yōu)化通常包括誤匹配剔除、整像素精度精化與視差平滑。