作者：沙洪俊, 袁修孝 來源：《武漢大學學報（信息科學版）》

自進入數字地球時代以來，智慧城市的建設工作一直是推動其發展的關鍵，而三維點云數據的快速獲取則是智慧城市建設的關鍵一環。

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

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

圖1Middlebury網站公布的2001—2022年密集匹配算法數量

1）雙目影像的密集匹配算法數量呈逐年上升趨勢。這表明雙目影像的密集匹配問題正在被越來越多的學者所關注，同時也說明雙目影像的密集匹配技術依然是一個熱點研究問題。

2）多視影像密集匹配算法的年度數量明顯偏少，自2014年開始逐年下降。多視密集匹配中的多角度影像可以有效改善遮擋區域的匹配效果，特別是近些年發展起來的傾斜攝影測量技術[13]，融合了傳統的航空攝影測量技術和近景攝影測量技術[14]。現有的多視密集匹配模型主要劃分為兩類：基于多視的匹配模型及基于多視立體融合的匹配模型[15]。前者同時考慮多條交會光線以獲得更為精確穩健的匹配結果，匹配模型較為復雜，且大部分方法匹配效率較低[16]，并不適合于大范圍的影像匹配，更多的此類匹配模型方法介紹可參見文獻[17-18]；后者則是將多視密集匹配視為以單個立體像對（雙目影像對）為匹配單元的多個立體像對的匹配結果融合問題，該類模型可以通過粗差剔除的方法更有效地改善遮擋區的匹配精度，效率更高、操作簡便、易于并行加速，適用于大范圍的影像匹配，其核心仍然是雙目密集匹配技術。因此，相比于多視影像密集匹配，雙目影像的密集匹配更為重要，是更為常用的密集匹配方法，這也是本文著重對雙目密集匹配進行綜合論述的初衷之一。

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

基于深度學習的方法雖然在常規區域可以獲得更優的匹配效果，但對于弱紋理、視差不連續以及遮擋區域的匹配效果仍然存在劣勢，多數的方法受限于訓練標簽，文獻[19]詳細分析了基于深度學習的影像密集匹配算法，此處不再贅述。

本文通過對現有的雙目影像密集匹配算法進行綜合分析，著重對傳統的密集匹配算法進行總結，以期能系統地闡述影像密集匹配技術的發展現狀。

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

01 雙目密集匹配

雙目密集匹配即從一個立體像對的二維影像數據信息中提取并恢復對應物體的三維空間信息。現有的雙目密集匹配算法依據同名點搜索空間的不同可分為基于像方空間的密集匹配算法和基于物方空間的密集匹配算法[20]。

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

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

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

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

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

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

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

1.1 局部密集匹配

利用各個像素的鄰域信息求解對應視差的局部密集匹配算法又被稱為基于窗口的密集匹配算法[33]，此類算法包含以上雙目密集匹配算法完整的步驟且在代價聚合階段隱式地使用了光滑假設約束。對于局部密集匹配算法而言，在匹配代價聚合時，選擇適當的匹配窗口是決定匹配精度的關鍵。 早期使用的單一固定窗口法因限制了窗口的尺寸大小，使其易在對象邊界處發生重疊，從而錯誤地聚合了不同區域的匹配代價，導致地物邊緣粗化模糊[34]，使其在深度不連續處、弱紋理區域以及重復紋理區域具有較高的誤匹配率。為此，基于窗口的密集匹配方法逐漸衍生為自適應窗口法、自適應權重法以及非前向平行算法等。

1.1.1 自適應窗口法

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

表1 自適應窗口法

總而言之，基于自適應窗口法可以總結如下：

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

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

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

1.1.2 自適應權重法

自適應權重法是推動局部密集匹配算法發展的關鍵。自2006年Yoon等[53]首次提出可以在匹配質量與全局匹配算法相媲美的局部匹配方法后，局部匹配算法再次被推向密集匹配研究的高潮。這種方法大多是依據局部區域的像素顏色、空間距離、甚至是梯度等屬性特征的相似度來分配匹配窗口內原始代價的權值，權值計算方式是實現該類方法的關鍵。基于不同的權重值主函數，表 2對其進行了歸類分析。

表2 自適應權重法

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

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

1.1.3 非前向平行法

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

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

1.2 全局密集匹配

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

1.2.1 動態規劃法

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

表3 基于SGM改進的算法

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

1.2.2 置信度傳播法

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

1.2.3 圖割法

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

02 攝影測量密集匹配

綜合攝影測量領域的密集匹配算法不難發現，基于像方空間的雙目密集匹配算法幾乎都是基于計算機視覺場景中的匹配算法，這就使得其無法獲得更為突出的匹配效果。因此，對于攝影測量場景而言，密集匹配問題除了要考慮密集匹配算法本身的特點外，還要考慮由于場景差異所帶來的影響。

2.1 計算機視覺場景與攝影測量場景的差異

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

圖4 影像數據的攝取場景 計算機視覺場景與攝影測量場景的差異包括：

1）在計算機視覺場景中，相機通常是置于場景的側前方，近距離地攝取極小圖幅影像，因而獲取的影像可以明顯地區分前景與背景。前景的物體輪廓也格外的清晰完整，地物間所存在的遮擋問題通常也可以通過人工干預盡量規避；而在攝影測量場景中，相機是通過自上而下的方式遠距離地攝取大圖幅影像，地物結構更為復雜，前景與背景會發生變化，地面上的所有地物即為前景，背景即為地面，地物間存在的遮擋問題是不可避免的。

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

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

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

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

2.2 遮擋處理

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

圖5 不同建筑物場景的遮擋可見性分析 圖5中，有5種不同的建筑物遮擋情況。情況1為單棟建筑物1被左右相機拍攝所呈現的可見性情況；情況2與情況3則表示對于建筑物1，具有不同相對位置關系的相鄰建筑物2被左右相機拍攝所呈現的兩種可見性情況；情況4與情況5則表示建筑物1的屋頂附屬建筑物2被左右相機拍攝所呈現的兩種可見性情況。從以上幾種遮擋情況不難發現：對于高層建筑物而言，由于自上而下的拍攝角度以及視點與建筑物之間的相對位置關系，建筑物的底部結構以及邊緣特征會因為遮擋而不可見，進而無法完成正確的匹配，最終會使得匹配結果中被建筑物遮擋的部分因為信息缺失而出現空洞。因此，遮擋處理也成為了提高密集匹配質量的關鍵。 遮擋處理包括遮擋檢測與遮擋填充。對于遮擋檢測，多數的方法都是選擇利用一定的約束條件去估計被遮擋像素的視差，進而實現遮擋區域的檢測。表4列出了幾種常見的約束條件。

表4 用于檢測遮擋像素的約束條件

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

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

不同于掃描線填充法的搜索策略，最近鄰插值法是選擇在不同的方向上搜索最近的有效像素，然后通過將有效視差傳播到相鄰的無效視差區域來執行插值[9, 66, 110, 114-118]。最近鄰插值法相比于掃描線填充法是更為常用的一類遮擋填充方法，但該類方法常常會因為像素的處理順序是基于幾何順序而具有無效的填充結果。 簡言之，借助條件約束檢測遮擋像素，并對檢測到的遮擋像素進行視差值填充，來完成遮擋處理工作，雖然可以在一定程度上提高密集匹配結果的質量，但也因為此過程需要大量的迭代計算，使得整個密集匹配算法的計算復雜度有所增加。而且就目前的遮擋填充效果而言，遮擋填充仍是一個具有挑戰性的任務。

2.3 匹配速度與精度

影像匹配的速度、精度和可靠性是評價密集匹配算法質量的3個重要指標[18]，尤其是當匹配算法已經確保具有相當的可靠性時，如何提高算法的匹配速度與匹配精度便成為更進一步提高或衡量算法質量的關鍵。 匹配速度的提升是滿足高效率匹配需求的關鍵，通常可以通過改變匹配算法本身的搜索策略和基于計算機硬件層面的并行優化策略來實現。

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

表5 精度評價指標

匹配精度的提升通常可從兩方面入手：一方面可以通過在基本的匹配算法的基礎上引入幾何約束的點、線、面以及尺度空間等特征約束條件來提升視差初值的可靠性以實現匹配精度的提升；另一方面可以通過后處理技術來實現視差的優化以實現匹配精度的提升。 通過引入特征約束條件來提高算法的匹配精度是提高深度不連續區域以及弱紋理區域匹配精度的重要手段，特別是具有豐富平面幾何結構特征的城市場景[120-124]，但其局限性在于幾何約束條件的適用范圍有限，多數方法僅適用于范圍較小，幾何特征相對豐富的區域，且約束條件也多為定制式，并不適用于其他的匹配算法[16, 106]；尺度空間特征約束條件是利用不同尺度的輸入圖像來檢測匹配關鍵點，也即尺度不變性，這種方法被更多地引入自適應窗口法[37, 125-127]、自適應權重法[128-132]以及SGM算法[133-135]中，然而這種方法卻會降低原算法的運算速度。 后處理技術即是對視差值的優化，視差優化通常包括誤匹配剔除、整像素精度精化與視差平滑。

誤匹配剔除是針對弱紋理、重復紋理以及遮擋等區域出現的孤立異常點等誤匹配結果進行左右一致性檢測、中值濾波、加權中值濾波[136]、異常值剔除濾波[116]的剔除；整像素精度[20]精化則是對視差結果的整像素精度進行子像素或亞像素的細化，常見的方法有基于拋物線函數插值法[137]、最小二乘匹配[20]、擬合拋物線[138]等；視差平滑則是對視差結果通過雙邊濾波、引導濾波等手段進行匹配結果的平滑操作。

03 結語

本文結合圖表對傳統雙目密集匹配算法進行了全面分析。 局部密集匹配的復雜度并不高，具有匹配效率高、實時性強的優勢，但缺點是匹配精度較低，特別是在模糊的弱紋理區域；全局密集匹配算法具有較高的匹配精度，特別是在深度不連續區域、遮擋區域、弱紋理等區域均具有較好的效果，但由于這類算法大都是通過迭代計算來實現的，算法的實時性與匹配效率都不太理想。 此外，針對遙感影像所具有的寬基線、大幅面的特點，本文對高層建筑物的遮擋情況進行了詳細的分析。

在航攝場景中，由于采用自上而下的拍攝方式，高層建筑物因為遮擋問題而隱藏掉了許多的紋理信息，如何處理遮擋問題是提高密集匹配質量的關鍵，自然會增加整個算法的計算復雜度。 就攝影測量而言，從上文所述的密集匹配整體算法來看，現有的雙目密集匹配主要存在匹配效率和匹配精度兩方面的問題。匹配效率問題指的是算法無法完全滿足實時獲取匹配結果的需求，需要進一步縮短算法的計算時間，提高匹配效率。匹配效率的提高，一方面需要降低算法的復雜度，分析算法是否必須迭代運算，在滿足大幅面的遙感影像匹配需求的同時考慮搜索策略的優化，另一方面也可以通過基于計算機硬件層面的并行優化策略來縮短計算時間。匹配精度問題則是指匹配結果所存在的邊緣毛刺與匹配空洞等問題，該部分數據的不精確與缺失大大降低了算法的整體匹配精度。

精度的提升方法一方面可以通過直接在算法中引入特征約束條件來提升視差初值的可靠性，另一方面可以通過后處理技術對視差結果更進一步處理以實現匹配精度的提升。 就密集匹配技術的迅猛發展而言，本文難以窮盡所有的密集匹配方法，但愿以上內容能夠給讀者帶來更進一步的認識。我們堅信，在不久的將來，影像密集匹配技術在算法的實時性以及匹配精度上一定會取得更大的進步。
審核編輯：黃飛