基于Voronoi圖的正射影像鑲嵌網絡生成與優化方法

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

(中國地質大學(武漢)，湖北 武漢 430074)

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

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

結合DOM實際鑲嵌生產需求，本文提出基于Voronoi圖的正射影像鑲嵌網絡生成及優化方法。通過構建Voronoi圖生成初始鑲嵌網絡，然后結合數字表面模型(digital surface model，DSM)數據對鑲嵌網絡頂點進行動態調整以避免鑲嵌結果出現無數據區域，并使頂點避開建筑、樹木等區域，以便使用已有的各類鑲嵌線自動提取方法對鑲嵌網絡進一步調整優化。

1 基于Voronoi圖的初始鑲嵌網絡生成

1.1 Voronoi圖介紹

Voronoi圖是計算幾何領域關于空間劃分的基礎數據結構，它是一組由連接相鄰兩點直線的垂直平分線組成的連續多邊形。其數學定義如下：假設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 初始鑲嵌網絡生成

原始影像基于DEM進行數字微分糾正后得到DOM影像，由于影像正射糾正時通常會發生旋轉或DEM數據缺失，導致DOM影像出現無效值區域。

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

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

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

2 鑲嵌網絡優化

2.1 頂點調整原則

基于常規Voronoi圖生成的鑲嵌網絡是根據影像中心點集對區域進行分割，沒有考慮Voronoi多邊形是否位于影像有效區域內，從而可能會在最終鑲嵌影像上產生一些無數據的漏洞，尤其是當影像分布不均或影像間重疊區域不足時。因此需要對鑲嵌多邊形的頂點進行相應調整以避免鑲嵌漏洞的產生。

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

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

2.2 頂點調整方法

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

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

實際進行頂點調整時，為了保持鑲嵌網絡的拓撲性及多邊形凹凸性，需要設置最大調整限制范圍。如圖5所示，灰色區域為影像有效多邊形重疊區域，記為VO；虛線區域為待調節頂點v相連接的3個Voronoi頂點構成的三角形，記為VT。則頂點調整的范圍應限于VO與VT的交集多邊形內，如圖5中陰影區域所示。

2.3 鑲嵌網絡優化

頂點調整后可以使用已有學者提出的各類鑲嵌線自動提取算法對初始鑲嵌線進一步優化，使其避開建筑、樹木和車輛等存在投影差的區域，避免產生幾何錯位與變形，形成高質量的無縫鑲嵌影像。本文采用文獻[2]提出的方法對鑲嵌網絡進行優化，對于每一段鑲嵌線，在其最小外包矩形的基礎上向外擴展一定范圍，對所形成區域內的DSM數據進行處理生成搜索代價圖，而后使用改進的JPS算法進行最優鑲嵌線自動提取。

3 試驗與結果分析

3.1 試驗設計

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

3.2 結果分析

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

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

4 結 語

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