一種基于重疊區指數化互相關和優化Dijkstra算法的航攝影像鑲嵌線選取方法

劉瀚陽，王博帥，王鳳艷，牛雪峰

吉林大學地球探測科學與技術學院，長春 130026

0 引言

航攝影像因包含大量語義和位置信息且相對容易獲取而成為廣泛使用的可視化產品，在環境監測和管理等方面均有所應用[1-6]。目前受分辨率的制約，單張航攝影像通常不能覆蓋整個研究區域，因此需要用多張航攝影像組成一張大范圍航攝影像[7-8]。然而因正射影像拍攝位置、照明條件和曝光參數等不同，同一地物在不同正射影像上會有顏色、紋理、形狀和位置的差異[9-10]。因此需顏色校正、平滑處理和鑲嵌線選取等步驟校正扭曲。以上步驟均需在鑲嵌線附近處理，因此鑲嵌線選取是航攝影像鑲嵌中的重要步驟。

航攝影像鑲嵌線即相鄰影像拼接時的分界線，航攝影像的重疊區被分為兩部分，每張航攝影像選取鑲嵌線一側組成一張大范圍影像。一條理想的航攝影像鑲嵌線應盡量避免穿過獨立地物，尤其是盡量避免穿越在相鄰影像上幾何形狀差異較大的獨立地物(相對地表較高的地物，如建筑物等)。本研究專注于選取最優鑲嵌線，實現航攝影像高質量鑲嵌。

航攝影像鑲嵌線選取的方法按照候選區域范圍不同分為基于全區域的鑲嵌線選取方法和基于限制區域的鑲嵌線選取方法。基于全區域的鑲嵌線選取方法在整個相鄰航攝影像重疊區中逐像素搜索匹配差異最小的路徑作為鑲嵌線。此類方法可以在重疊區找到最優鑲嵌線，但其耗時較長。目前存在的基于全區域的鑲嵌線選取方法如下：Kerschner[1]提出“兩蛇”方法，在重疊區根據對應像素顏色和紋理差異選取鑲嵌線。Chon等[11]最先提出一個理念，即一條較長的視覺差異較小的鑲嵌線比一條較短的誤匹配較大的鑲嵌線更好；其使用分水嶺瓶頸算法限制重疊區對應像素錯位差異的最大值，再逐層用Dijkstra算法尋找最優鑲嵌線。Li等[12]及Dong等[13]使用圖割算法，并聯合考慮各區域色彩、梯度和紋理的差異來選取鑲嵌線。Pan等[14]使用平均轉換算法(MS)獲取明顯地物的位置，進而從非明顯地物區域選取鑲嵌線。

另一類鑲嵌線選取方法是基于限制區域的方法，其通過人為制定策略在相鄰影像重疊區的部分子區域選取鑲嵌線。使用此類方法獲取的鑲嵌線不一定是整個重疊區中的最優解，但用時較少。目前已有的基于限制區域的鑲嵌線選取方法如下：Pan等[15-16]在重疊區構造泰森多邊形，再制定有效鑲嵌多邊形(EMP)策略沿著候選多邊形邊線形成鑲嵌線，并進一步優化以適應不同形狀的重疊區域。Yuan等[17]使用D-LinkNet神經網絡獲取影像中的道路區域，并在道路區域選取鑲嵌線，此方法只適用城市道路覆蓋密集的區域。Wang等[4]用矢量建筑物位置圖識別重疊區中的建筑物，并沿建筑物間空地的中線選取鑲嵌線以避免鑲嵌線穿越明顯建筑物。Wan等[18]根據矢量道路圖聯合重疊區中線的骨架選取鑲嵌線。然而用額外矢量信息的方法有一定限制性。首先有時矢量信息圖不易獲取，其次矢量信息圖有實效性，新的地物不會包含在舊矢量信息圖中，從而可能影響后續鑲嵌線選取操作。

基于全區域的鑲嵌線選取方法可以在重疊區獲取最優鑲嵌線，因此本文提出一種基于全區域的航攝影像鑲嵌線選取方法。首先構造一種指數化互相關方法高質量地表達航攝影像重疊對應區域的錯位程度，再提出一種優化Dijkstra算法高效尋找匹配差異最小的路徑來作為最優鑲嵌線。

1 原理與方法

1.1 重疊區損失函數構建

在相鄰正射影像重疊區域，一條最優鑲嵌線應穿越對應像素匹配較好的點。一條可能較長的高匹配鑲嵌線比一條較短的低匹配鑲嵌線的鑲嵌質量要高[11]。因此獲取重疊區對應像素間的錯位程度是一個關鍵問題。Chon等[11]使用5×5歸一化互相關(NCC)來評價重疊區匹配情況。Yuan等[17]在此基礎上用5×5快速歸一化互相關(QNCC)加快計算過程。然而這兩種方法獲取的重疊區對應像素的匹配程度范圍為(0, 1)，越靠近0匹配效果越好，越靠近1匹配越差，無法充分表達不同點間錯位程度的差異。例如，匹配結果為0.3表示匹配結果較好，匹配結果為0.6表示匹配結果較差，而在用上述方法選取鑲嵌線時，鑲嵌線經過兩個匹配結果為0.3的點的代價和經過一個匹配結果為0.6的點的代價相同，這顯然是不合理的。

本文基于經過一個高不匹配點的代價應遠高于經過多個低不匹配點的代價的理念，提出一種基于指數化互相關的方法充分擴大高不匹配點和低不匹配點間的錯位表達差異。

首先，優化QNCC，提出平均快速歸一化互相關。QNCC如式(1)所示：

(1)

式中：RQNCC(x,y)為點(x,y)處的QNCC值；Il(i,j)和Ir(i,j)分別是左影像和右影像在點(i,j)處的灰度值。然而，對應點灰度值相近不代表它們在紅綠藍(RGB)3個波段值都相近，只有RGB 3個波段值均相近才代表對應像素匹配程度較高。因此，本文提出平均快速歸一化互相關(mQNCC)，分別從RGB 3個波段計算對應像素匹配程度：

(2)

式中：RmQNCC(x,y)為點(x,y)處的mQNCC值，RRQNCC(x,y)、RGQNCC(x,y)和RBQNCC(x,y)分別為點(i,j)的RGB 3個波段QNCC值。

接著，提出一種指數化互相關函數，以充分表達對應像素匹配程度的差異：

(3)

式中，ω是常數。使用此函數可將線性變化的歸一化互相關函數進行指數化放大，從而成倍擴大低匹配精度像素與高匹配精度像素的結果差異，使鑲嵌線經過低匹配像素點的代價遠高于經過高匹配點的代價。

1.2 優化Dijkstra算法

Dijkstra算法是一種全局動態最優路徑選取方法。它使用有向圖處理非負權重區域的單源最短路徑問題[11, 19-20]。一些方法[11, 14]基于Dijkstra算法決定鑲嵌線。其在決定鑲嵌線前進方向時會不斷更新當前點鄰域內8個點的全局損失值，以確定從起始點到每個點的最小損失值和最優路徑。此類方法對重疊區中大部分點進行8次損失值計算和路徑更新，計算量較大，對含有千萬級像素的航攝影像而言處理時間較長。

本文提出一種優化Dijkstra算法，使鑲嵌線不斷沿最小全局損失點方向前進，且在重疊區每個像素點位置只運算一次便可求得由起始點到該點的最小損失值和最優路徑，從而大幅減少計算時間。優化Dijkstra算法為

(4)

式中：點(k,l)表示當前重疊區中到起始點全局損失值最小的點，且需要其鄰域內還有一個或多個點尚未計算全局損失值；S(k,l)表示點(k,l)鄰域內8個點中尚未計算全局損失值的點集合；IDijk(k,l)表示從起始點到點(k,l)的全局損失值。本方法通過一次運算便能得到從起始點到點(x,y)的全局損失值和最優路徑，高質高效實現最優鑲嵌線選取。

2 實驗

2.1 實驗環境

本文算法基于Python3.7編寫，使用OpenCV庫和NumPy庫進行圖像處理操作。本文算法在64位Win10操作系統下測試，硬件包括Intel i5-8400 2.8 GHz處理器、Nvidia 3090顯卡、56 GB內存和2 TB硬盤。

用于測試本文算法的兩組圖像分別來自城市和城鎮區域。城市區域航空影像包含商業區、居民區和公園區域。其分辨率為0.05 m，單張影像寬10 000 pt，高7 800 pt。相鄰影像航向重疊率75%,旁向重疊率45%。城鎮區域航空影像包含一個小村莊和部分耕地及道路。其分辨率為0.07 m，單張影像寬8 000 pt,高5 300 pt。相鄰影像航向重疊率77%,旁向重疊率50%。

2.2 實驗參數

在八位無符號航攝影像中，圖像像素值范圍為[0, 255]。在提出式(3)時，本文希望匹配較高的像素有接近0的較小損失值而匹配較低的像素有接近255的較高損失值，從而使低匹配像素損失值遠大于高匹配像素損失值，進而易于后續使用優化Dijsktra算法尋找最優鑲嵌線。

在式(3)中，將RmQNCC(x,y)經過線性反轉和歸一化操作后結果范圍為(0, 1)，其結果越接近0像素匹配越好，越接近1像素匹配越差。因此本文將常數ω的值定為5.5，從而使匹配最差像素的損失值達到244.7，即一個較高的損失值。

2.3 重疊區損失表達圖

通過式(3)獲得的重疊區對應像素匹配情況如圖1所示。由圖1e、f可見，本文算法檢測到重疊區中匹配較差的建筑、車輛和樹木等區域(圖中越亮像素具有越大損失值，即匹配效果較差)，與匹配較好的道路區域有明顯區別，從而為后續選取最優鑲嵌線提供了便利條件。

2.4 實驗結果與對比

本文使用兩組分別來自城市和城鎮區域的航攝影像，與同樣基于全區域Dijkstra類方法尋找最優鑲嵌線的Chon等[11]的方法進行對比，證明本文提出方法的可行性與優勢。

城市區域航攝影像鑲嵌結果如圖2所示。使用本文方法獲取的鑲嵌線為沿建筑物的邊緣、道路中的無車區域及林地區中樹木的間隙，避免了穿越明顯建筑物(圖2a、c)；使用Chon等方法獲取的鑲嵌線穿越了5棟建筑物，破壞了鑲嵌線附近地物的連續性(圖2b、d)。

a. 重疊區左影像；c. 重疊區右影像；e. 損失表達圖；b、d、f分別為a、c、e同一位置子區域。在圖e和f中，越亮的像素匹配精度越低。

城鎮區域航攝影像鑲嵌結果如圖3所示。使用本文方法獲取的鑲嵌線沿著道路的紋理和耕地的邊界，沒有破壞地物的連續性(圖3a、c)；由Chon等方法獲取的鑲嵌線同樣沿著道路區域鑲嵌，但其穿越了8棟房屋，產生可見鑲嵌錯位(圖3b、d)。

a. 本文方法；b. Chon等[11]方法；c、d分別為a、b同一位置子區域。

a. 本文方法；b. Chon等[11]方法；c、d分別為a、b同一位置子區域。

在效率方面，本文使用優化Dijsktra算法在重疊區中對每個像素位置只進行一次計算便可求出該點最小損失值，而Chon等的方法需在每個點位多次運算，因此本文方法運算時間更短(表1)。使用本文方法鑲嵌重疊區尺寸為6 000 pt×10 000 pt和3 000 pt×7 500 pt圖像分別用時64.83 s和35.51 s，均比Chon等的方法具有明顯優勢。

表1 本文方法和Chon等[11]方法鑲嵌兩幅航攝影像用時比較

3 結論與討論

本文提出一種基于指數化互相關和優化Dijkstra算法的航攝影像最優鑲嵌線選取方法。

1)本文構造的指數化互相關函數，相比已有方法可以更充分地表達重疊區高匹配像素和低匹配像素間的差異，從而為在匹配較好的區域選取最優鑲嵌線提供便利條件。

2)本文提出的優化Dijkstra算法在重疊區沿最小匹配損失方向選取鑲嵌線，相比已有方法，只需在重疊區每點位計算一次便可獲得從起始點到該點的最小損失值和最優路徑，從而減少鑲嵌線選取時間。

3)將本文方法與同樣基于全區域Dijsktra類方法選取鑲嵌線的Chon等的方法對比，結果表明使用本文方法選取航攝影像鑲嵌線效果更好，速度更快。

本文方法仍有改進空間。本文方法在單線程環境下操作，若通過多線程操作可進一步減少鑲嵌線選取時間。另外，使用本文方法選取的鑲嵌線起止點為兩幅影像邊緣的交點，當交點落在建筑物等獨立地物上時不可避免地使鑲嵌線穿越該地物，通過動態改變鑲嵌線起止點可提高鑲嵌線質量。以上不足將在后續研究中優化。