基于Voronoi圖的正射影像鑲嵌網(wǎng)絡(luò)生成與優(yōu)化方法

陳 松，周 平，李顯巨，陳 剛

(中國地質(zhì)大學(xué)(武漢)，湖北 武漢 430074)

單幅影像通常無法覆蓋航攝測區(qū)范圍，因此大范圍DOM的生產(chǎn)需要對多幅影像進(jìn)行鑲嵌處理[1]。鑲嵌線的自動生成作為影像鑲嵌中的關(guān)鍵步驟，已經(jīng)成為計算機視覺、攝影測量與遙感領(lǐng)域的研究熱點之一[2-4]。現(xiàn)有的鑲嵌線自動提取方法大多只關(guān)注相鄰兩幅影像的拼接，處理多幅影像時，將當(dāng)前兩幅影像的鑲嵌結(jié)果與剩余影像中的下一幅影像進(jìn)行鑲嵌，依此類推直到所有影像鑲嵌完畢。這種處理模式嚴(yán)重依賴鑲嵌過程，處理效率較低[5-6]。隨著高精度、高重疊度與高分辨率遙感數(shù)據(jù)的不斷涌現(xiàn)，研究基于全局的鑲嵌網(wǎng)絡(luò)自動生成，確定每幅影像的有效鑲嵌區(qū)域成為提升大范圍、海量影像鑲嵌處理效率的關(guān)鍵[6-7]。

文獻(xiàn)[8]提出了將單獨鑲嵌線連接生成鑲嵌網(wǎng)絡(luò)的方法，該方法需要記錄測區(qū)航帶信息，適用性有限。文獻(xiàn)[9]研究了利用Voronoi圖生成鑲嵌網(wǎng)絡(luò)，但其不能保證生成的鑲嵌線一定在相鄰DOM影像的重疊區(qū)域內(nèi)，從而導(dǎo)致鑲嵌結(jié)果可能存在未被有效數(shù)據(jù)覆蓋的區(qū)域。文獻(xiàn)[7,10]提出了顧及重疊的面Voronoi圖初始鑲嵌線網(wǎng)絡(luò)生成方法，該方法具有與輸入影像順序無關(guān)、無中間結(jié)果等優(yōu)點，但是對處理單片糾正后有效范圍呈不規(guī)則多邊形的正射影像比較復(fù)雜。文獻(xiàn)[11]改進(jìn)了文獻(xiàn)[7]提出的顧及重疊的面Voronoi圖方法，通過局部搜索將鑲嵌網(wǎng)絡(luò)頂點調(diào)整到最優(yōu)位置，但受限于搜索范圍，頂點仍然可能位于建筑和樹木等障礙區(qū)域。

結(jié)合DOM實際鑲嵌生產(chǎn)需求，本文提出基于Voronoi圖的正射影像鑲嵌網(wǎng)絡(luò)生成及優(yōu)化方法。通過構(gòu)建Voronoi圖生成初始鑲嵌網(wǎng)絡(luò)，然后結(jié)合數(shù)字表面模型(digital surface model，DSM)數(shù)據(jù)對鑲嵌網(wǎng)絡(luò)頂點進(jìn)行動態(tài)調(diào)整以避免鑲嵌結(jié)果出現(xiàn)無數(shù)據(jù)區(qū)域，并使頂點避開建筑、樹木等區(qū)域，以便使用已有的各類鑲嵌線自動提取方法對鑲嵌網(wǎng)絡(luò)進(jìn)一步調(diào)整優(yōu)化。

1 基于Voronoi圖的初始鑲嵌網(wǎng)絡(luò)生成

1.1 Voronoi圖介紹

Voronoi圖是計算幾何領(lǐng)域關(guān)于空間劃分的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，它是一組由連接相鄰兩點直線的垂直平分線組成的連續(xù)多邊形。其數(shù)學(xué)定義如下：假設(shè)P={p1,p2,p3,…,pn}(3≤n<∞)是二維歐氏空間(平面)上n個互不相同的點，則可以把點pi的Voronoi多邊形V(pi)定義為

(1)

式中，i,j=1,2,3,…,n,i≠j，p為平面上的任意點；d(p,pi)與d(p,pj)分別為點p與pi和pj的歐氏距離；集合V={V(p1),V(p2),V(p3),…,V(pn)}所定義的圖形即為以點集P為種子點生成的Voronoi圖，如圖1所示。

1.2 初始鑲嵌網(wǎng)絡(luò)生成

原始影像基于DEM進(jìn)行數(shù)字微分糾正后得到DOM影像，由于影像正射糾正時通常會發(fā)生旋轉(zhuǎn)或DEM數(shù)據(jù)缺失，導(dǎo)致DOM影像出現(xiàn)無效值區(qū)域。

一般而言無效值區(qū)域分布于影像的四周，像素值被標(biāo)記為0或255，可以采用邊緣跟蹤的方法獲取影像有效多邊形邊界，此時的邊界由連續(xù)像素點連接構(gòu)成，節(jié)點數(shù)量過多，不利于后期進(jìn)行多邊形求交等操作。為了減少計算復(fù)雜度，可以使用Douglas-Peucker算法[12]進(jìn)行點集抽稀。由于影像有效區(qū)域邊界為閉合多邊形，因此可以在點集中選定某一起點及距離其最遠(yuǎn)的一個節(jié)點，將多邊形拆分為兩條曲線段進(jìn)行抽稀處理。圖2(a)和圖2(b)分別為單幅DOM邊緣跟蹤和點集抽稀結(jié)果。

實際鑲嵌處理時，首先獲取每幅DOM影像的有效多邊形范圍，然后以多邊形中心為種子點生成Voronoi圖，對每幅影像進(jìn)行劃分，從而確定單幅影像在最終鑲嵌結(jié)果影像上的有效區(qū)域，避免中間結(jié)果產(chǎn)生，以提高DOM生產(chǎn)效率與鑲嵌的靈活性。

航空數(shù)碼影像一般為中心投影成像方式，在投影中心區(qū)域幾何畸變與投影差較小、圖像質(zhì)量較高、數(shù)字微分糾正后的DOM也是如此[13-14]。Voronoi圖是基于散點最鄰近原則的空間劃分方法，因此生成初始鑲嵌網(wǎng)絡(luò)可以保留影像質(zhì)量較高的區(qū)域，提高影像鑲嵌和DOM生產(chǎn)精度。

2 鑲嵌網(wǎng)絡(luò)優(yōu)化

2.1 頂點調(diào)整原則

基于常規(guī)Voronoi圖生成的鑲嵌網(wǎng)絡(luò)是根據(jù)影像中心點集對區(qū)域進(jìn)行分割，沒有考慮Voronoi多邊形是否位于影像有效區(qū)域內(nèi)，從而可能會在最終鑲嵌影像上產(chǎn)生一些無數(shù)據(jù)的漏洞，尤其是當(dāng)影像分布不均或影像間重疊區(qū)域不足時。因此需要對鑲嵌多邊形的頂點進(jìn)行相應(yīng)調(diào)整以避免鑲嵌漏洞的產(chǎn)生。

Voronoi圖中的每個頂點與三條邊相連，并對應(yīng)與其相關(guān)的3幅DOM影像。因此只需Voronoi網(wǎng)絡(luò)中每一個頂點都位于與其相關(guān)的3幅影像有效多邊形的重疊區(qū)域內(nèi)，即可保證鑲嵌線落在影像的有效重疊區(qū)域，從而避免無數(shù)據(jù)漏洞的出現(xiàn)。如圖3所示，當(dāng)頂點位于V1處時，鑲嵌影像的部分區(qū)域無有效數(shù)據(jù)覆蓋(圖中黑色區(qū)域)，需將其調(diào)整至3張影像(P1,P2和P3)的重疊區(qū)域(圖中灰色區(qū)域)內(nèi)，即點V2，這樣即可避免空洞區(qū)域的產(chǎn)生，實現(xiàn)正射影像無縫鑲嵌。

對于以效率優(yōu)先的影像拼接處理，一般只需實現(xiàn)無漏洞的拼接即可滿足要求。而為了生產(chǎn)高質(zhì)量、高精度的大范圍DOM，需要使鑲嵌線避開建筑、樹木等存在投影差的地物區(qū)域。當(dāng)鑲嵌網(wǎng)絡(luò)中的頂點位于這些地物上時，鑲嵌線經(jīng)過優(yōu)化之后仍然會不可避免地穿越這些地物，產(chǎn)生幾何錯位與變形，因此頂點也應(yīng)避開存在投影差的地物區(qū)域。由于DSM數(shù)據(jù)能夠直接體現(xiàn)地物的高度信息與區(qū)域范圍，并且一般與DOM產(chǎn)品一同生產(chǎn)，容易獲取，因此本文結(jié)合DSM數(shù)據(jù)對鑲嵌網(wǎng)絡(luò)頂點位置進(jìn)行進(jìn)一步調(diào)整優(yōu)化。

2.2 頂點調(diào)整方法

對于多級別的DSM灰度影像，使用閾值分割將其分為障礙區(qū)域(建筑物、樹木等)與非障礙區(qū)域(地面)。由于影像投影差的存在，頂點在DSM上緊貼障礙區(qū)域邊緣時在原始DOM上可能表現(xiàn)為已穿越建筑物邊緣部分。因此需要對DSM二值圖像進(jìn)行形態(tài)學(xué)膨脹[15]處理，填充建筑物與樹木等障礙區(qū)域的空洞與凹陷，并使邊緣往外擴(kuò)展，最終使頂點偏離障礙區(qū)域，如圖4所示。

DSM處理完成后，基于處理影像對頂點進(jìn)行調(diào)整，具體方法如下：以初始頂點v為圓心，從0開始以指定長度的步距不斷增大半徑r，在生成圓弧所經(jīng)過的像素點集中，如果存在一點v′同時滿足：①點v′在處理后DSM影像上的像素值為0；②點v′在3幅影像有效多邊形重疊區(qū)域內(nèi)，則以v′為新的頂點取代初始頂點v。

實際進(jìn)行頂點調(diào)整時，為了保持鑲嵌網(wǎng)絡(luò)的拓?fù)湫约岸噙呅伟纪剐?，需要設(shè)置最大調(diào)整限制范圍。如圖5所示，灰色區(qū)域為影像有效多邊形重疊區(qū)域，記為VO；虛線區(qū)域為待調(diào)節(jié)頂點v相連接的3個Voronoi頂點構(gòu)成的三角形，記為VT。則頂點調(diào)整的范圍應(yīng)限于VO與VT的交集多邊形內(nèi)，如圖5中陰影區(qū)域所示。

2.3 鑲嵌網(wǎng)絡(luò)優(yōu)化

頂點調(diào)整后可以使用已有學(xué)者提出的各類鑲嵌線自動提取算法對初始鑲嵌線進(jìn)一步優(yōu)化，使其避開建筑、樹木和車輛等存在投影差的區(qū)域，避免產(chǎn)生幾何錯位與變形，形成高質(zhì)量的無縫鑲嵌影像。本文采用文獻(xiàn)[2]提出的方法對鑲嵌網(wǎng)絡(luò)進(jìn)行優(yōu)化，對于每一段鑲嵌線，在其最小外包矩形的基礎(chǔ)上向外擴(kuò)展一定范圍，對所形成區(qū)域內(nèi)的DSM數(shù)據(jù)進(jìn)行處理生成搜索代價圖，而后使用改進(jìn)的JPS算法進(jìn)行最優(yōu)鑲嵌線自動提取。

3 試驗與結(jié)果分析

3.1 試驗設(shè)計

為了驗證本文算法的可行性與有效性，基于C++(VC14)與OpenCV(3.2.0)實現(xiàn)了本文所提出的鑲嵌網(wǎng)絡(luò)生成方法。使用德國Vaihingen地區(qū)影像數(shù)據(jù)進(jìn)行鑲嵌網(wǎng)絡(luò)生成試驗，包括3個航帶共14幅影像，航向與旁向重疊度均為60%；影像大小約為7680像素×13 824像素，空間分辨率為8 cm，正射糾正后重采樣至0.2 m；影像對應(yīng)的DSM分辨率為0.14 m。

3.2 結(jié)果分析

試驗中初始鑲嵌網(wǎng)絡(luò)生成與頂點調(diào)整結(jié)果如圖6所示，其中(b)、(c)和(d)分別為(a)中白色框內(nèi)圖像的局部放大顯示。圖6(a)中黑色線條是以DOM影像有效區(qū)域中心點為種子點基于Voronoi圖生成的初始鑲嵌網(wǎng)絡(luò)，由于僅考慮了影像中心點幾何位置關(guān)系，生成的鑲嵌網(wǎng)絡(luò)中部分頂點位于房屋、樹木等存在高投影差的區(qū)域，不利于接下來對鑲嵌線進(jìn)行走向優(yōu)化。圖6(a)中白色線條為經(jīng)過頂點調(diào)整后的鑲嵌網(wǎng)絡(luò)，可以看出，位于房屋處的頂點均被移至地面區(qū)域，而且Voronoi圖的結(jié)構(gòu)特性得以較好地保留。頂點調(diào)整后鑲嵌網(wǎng)絡(luò)中各條線段均位于影像有效重疊區(qū)域內(nèi)，避免了拼接結(jié)果中影像數(shù)據(jù)丟失，形成無拼接漏洞的鑲嵌影像。

頂點調(diào)整完成后，采用文獻(xiàn)[2]提出的基于DSM與JPS算法的鑲嵌線自動提取方法對初始鑲嵌網(wǎng)絡(luò)進(jìn)行優(yōu)化，從而使鑲嵌線避開建筑和樹木等存在投影差的地表區(qū)域。鑲嵌網(wǎng)絡(luò)優(yōu)化結(jié)果如圖7所示，(b)、(c)和(d)分別為(a)中白色框內(nèi)圖像的局部放大顯示。

4 結(jié) 語

本文提出了一種基于Voronoi圖的正射影像鑲嵌網(wǎng)絡(luò)生成與優(yōu)化方法，首先基于Voronoi圖生成初始鑲嵌網(wǎng)絡(luò)；然后對鑲嵌網(wǎng)絡(luò)節(jié)點進(jìn)行優(yōu)化調(diào)整，確定每幅影像的有效多邊形并保證無拼接漏洞產(chǎn)生；最后對每一段鑲嵌線進(jìn)行走向優(yōu)化使其避開建筑、樹木等區(qū)域，避免產(chǎn)生幾何錯位與色彩差異，形成最終的無縫鑲嵌影像。本文方法與輸入影像順序無關(guān)，可以避免中間結(jié)果的產(chǎn)生，提高影像鑲嵌的效率，能夠滿足大范圍正射影像無縫拼接處理需求。值得注意的是，鑲嵌網(wǎng)絡(luò)頂點調(diào)整及鑲嵌線走向優(yōu)化效果主要取決于DSM的精度及閾值分割效果，后續(xù)將對DSM處理流程作進(jìn)一步優(yōu)化改進(jìn)。