一種基于重疊區(qū)指數(shù)化互相關(guān)和優(yōu)化Dijkstra算法的航攝影像鑲嵌線選取方法

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

吉林大學(xué)地球探測(cè)科學(xué)與技術(shù)學(xué)院，長春 130026

0 引言

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

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

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

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

基于全區(qū)域的鑲嵌線選取方法可以在重疊區(qū)獲取最優(yōu)鑲嵌線，因此本文提出一種基于全區(qū)域的航攝影像鑲嵌線選取方法。首先構(gòu)造一種指數(shù)化互相關(guān)方法高質(zhì)量地表達(dá)航攝影像重疊對(duì)應(yīng)區(qū)域的錯(cuò)位程度，再提出一種優(yōu)化Dijkstra算法高效尋找匹配差異最小的路徑來作為最優(yōu)鑲嵌線。

1 原理與方法

1.1 重疊區(qū)損失函數(shù)構(gòu)建

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

本文基于經(jīng)過一個(gè)高不匹配點(diǎn)的代價(jià)應(yīng)遠(yuǎn)高于經(jīng)過多個(gè)低不匹配點(diǎn)的代價(jià)的理念，提出一種基于指數(shù)化互相關(guān)的方法充分?jǐn)U大高不匹配點(diǎn)和低不匹配點(diǎn)間的錯(cuò)位表達(dá)差異。

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

(1)

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

(2)

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

接著，提出一種指數(shù)化互相關(guān)函數(shù)，以充分表達(dá)對(duì)應(yīng)像素匹配程度的差異：

(3)

式中，ω是常數(shù)。使用此函數(shù)可將線性變化的歸一化互相關(guān)函數(shù)進(jìn)行指數(shù)化放大，從而成倍擴(kuò)大低匹配精度像素與高匹配精度像素的結(jié)果差異，使鑲嵌線經(jīng)過低匹配像素點(diǎn)的代價(jià)遠(yuǎn)高于經(jīng)過高匹配點(diǎn)的代價(jià)。

1.2 優(yōu)化Dijkstra算法

Dijkstra算法是一種全局動(dòng)態(tài)最優(yōu)路徑選取方法。它使用有向圖處理非負(fù)權(quán)重區(qū)域的單源最短路徑問題[11, 19-20]。一些方法[11, 14]基于Dijkstra算法決定鑲嵌線。其在決定鑲嵌線前進(jìn)方向時(shí)會(huì)不斷更新當(dāng)前點(diǎn)鄰域內(nèi)8個(gè)點(diǎn)的全局損失值，以確定從起始點(diǎn)到每個(gè)點(diǎn)的最小損失值和最優(yōu)路徑。此類方法對(duì)重疊區(qū)中大部分點(diǎn)進(jìn)行8次損失值計(jì)算和路徑更新，計(jì)算量較大，對(duì)含有千萬級(jí)像素的航攝影像而言處理時(shí)間較長。

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

(4)

式中：點(diǎn)(k,l)表示當(dāng)前重疊區(qū)中到起始點(diǎn)全局損失值最小的點(diǎn)，且需要其鄰域內(nèi)還有一個(gè)或多個(gè)點(diǎn)尚未計(jì)算全局損失值；S(k,l)表示點(diǎn)(k,l)鄰域內(nèi)8個(gè)點(diǎn)中尚未計(jì)算全局損失值的點(diǎn)集合；IDijk(k,l)表示從起始點(diǎn)到點(diǎn)(k,l)的全局損失值。本方法通過一次運(yùn)算便能得到從起始點(diǎn)到點(diǎn)(x,y)的全局損失值和最優(yōu)路徑，高質(zhì)高效實(shí)現(xiàn)最優(yōu)鑲嵌線選取。

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)環(huán)境

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

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

2.2 實(shí)驗(yàn)參數(shù)

在八位無符號(hào)航攝影像中，圖像像素值范圍為[0, 255]。在提出式(3)時(shí)，本文希望匹配較高的像素有接近0的較小損失值而匹配較低的像素有接近255的較高損失值，從而使低匹配像素?fù)p失值遠(yuǎn)大于高匹配像素?fù)p失值，進(jìn)而易于后續(xù)使用優(yōu)化Dijsktra算法尋找最優(yōu)鑲嵌線。

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

2.3 重疊區(qū)損失表達(dá)圖

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

2.4 實(shí)驗(yàn)結(jié)果與對(duì)比

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

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

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

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

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

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

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

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

3 結(jié)論與討論

本文提出一種基于指數(shù)化互相關(guān)和優(yōu)化Dijkstra算法的航攝影像最優(yōu)鑲嵌線選取方法。

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

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

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

本文方法仍有改進(jìn)空間。本文方法在單線程環(huán)境下操作，若通過多線程操作可進(jìn)一步減少鑲嵌線選取時(shí)間。另外，使用本文方法選取的鑲嵌線起止點(diǎn)為兩幅影像邊緣的交點(diǎn)，當(dāng)交點(diǎn)落在建筑物等獨(dú)立地物上時(shí)不可避免地使鑲嵌線穿越該地物，通過動(dòng)態(tài)改變鑲嵌線起止點(diǎn)可提高鑲嵌線質(zhì)量。以上不足將在后續(xù)研究中優(yōu)化。