非規(guī)則正射影像鑲嵌多邊形網(wǎng)絡(luò)自動生成

項琳，岳貴杰，杜黎明

(1.中國測繪科學(xué)研究院,北京 100039;2.首都師范大學(xué)資源環(huán)境與旅游學(xué)院,北京 100048; 3.河南城建學(xué)院測繪工程學(xué)院,平頂山 467036)

1 引 言

在正射影像鑲嵌處理中待鑲嵌影像的有效范圍一般為矩形區(qū)域。此類影像鑲嵌網(wǎng)絡(luò)的生成相對簡單。通常采取手工或自動的方法提取重疊區(qū)域分割線，然后根據(jù)一定的規(guī)則生成整體的多邊形網(wǎng)絡(luò)[1]；當(dāng)正射影像的有效像素區(qū)域為非四邊形區(qū)域的，如何不對影像進行化簡情況下自動生成鑲嵌多邊形網(wǎng)絡(luò)顯得十分重要。常用的數(shù)字攝影測量系統(tǒng)或遙感影像處理軟件一般都采用人工方法進行兩兩影像鑲嵌處理，在海量數(shù)據(jù)處理時，勞動強度大。

本文提出了一種非規(guī)則邊緣正射影像的鑲嵌多邊形網(wǎng)絡(luò)自動生成方法，將正射影像鑲嵌多邊形網(wǎng)絡(luò)的生成細化為影像有效區(qū)域的提取、兩兩重疊區(qū)域的確定、重疊區(qū)域分割線的生成、初始鑲嵌多邊形網(wǎng)絡(luò)的生成及多邊形網(wǎng)絡(luò)的拓撲編輯等過程。該流程能全自動生成唯一的、且具有良好幾何特性的鑲嵌多邊形網(wǎng)絡(luò)，減少了人工處理的工作量，提高了正射影像鑲嵌的效率。

2 常用定義

影像有效范圍：用多邊形表示的影像有效像素范圍。如圖1中的紅色多邊形內(nèi)部像素，無效像素為背景色(黑)，白色矩形邊框為影像覆蓋范圍。

鑲嵌多邊形：在多幅影像的鑲嵌過程中，需要確定每幅影像對鑲嵌結(jié)果有貢獻的像素多邊形范圍，稱之為鑲嵌多邊形[1]。鑲嵌多邊形包含于影像有效范圍內(nèi)，如圖2中的兩個多邊形分別包含在圖1中的兩個多邊形內(nèi)。

鑲嵌多邊形網(wǎng)絡(luò)：在鑲嵌區(qū)域中，由每幅影像的有效鑲嵌多邊形組成的多邊形集合。在該多邊形集合中，兩兩多邊形沒有交集。如圖2中的兩個多邊形，圖7的三個多邊形。

拓撲孔洞：鑲嵌多邊形網(wǎng)絡(luò)中存在的未被覆蓋的部分。如圖8中的點4、7、8和9組成的多邊形(紅色部分)。

跨接邊：在多邊形的三角剖分結(jié)果中，位于多邊形內(nèi)部的三角形的邊稱為跨接邊。如圖4中的虛線邊。

邊界邊：鑲嵌多邊形組成的網(wǎng)絡(luò)中僅出現(xiàn)一次的邊，稱為邊界邊。如圖2中除去AB之間公共邊之外的其他邊。

非邊界邊：在多邊形網(wǎng)絡(luò)中出現(xiàn)兩次，即相鄰多邊形之間的重合邊(公共邊)。如圖2中的AB之間的公共邊，圖8中的點1和2,、點2和3，點3和4組成的邊等。

3 鑲嵌多邊形網(wǎng)絡(luò)生成步驟

本文中兩幅影像鑲嵌多邊形網(wǎng)絡(luò)自動生成流程為：①提取每一幅影像的有效像素范圍，用多邊形表示(圖1中的兩個紅色多邊形)；②求取兩幅影像的重疊區(qū)域(圖1中兩個多邊形的交集)；③計算重疊區(qū)域分割線(如圖1中AB兩點間的綠色線條)。分割線的起點和終點是兩幅影像有效區(qū)域多邊形的公共點(A點和B點)。若有多于兩個公共點時，分割線可以有多條，此時需要采用優(yōu)化算法得到滿足條件的最優(yōu)的一條分割線；④用求得的分割線分割兩幅影像，得到鑲嵌多邊形，如圖2中的兩個紅色多邊形。

多幅影像鑲嵌多邊形網(wǎng)絡(luò)的生成步驟類似于兩兩間的處理方法。對多幅影像處理時，將每一次分割后的結(jié)果作為下一次分割的輸入，直至處理完與一幅影像有關(guān)的所有分割線。分割后的多邊形構(gòu)成初始鑲嵌多邊形網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中，可能存在拓撲錯誤(孔洞)，需要進行孔洞檢測及消除。

圖1 兩幅重疊影像及其分割線

圖2 分割線分割影像多邊形

3.1 影像多邊形的自動提取

自動鑲嵌過程中，處理的是每一幅影像的有效像素，需要提取每一幅影像的有效像素范圍，并用多邊形表示。有效像素范圍提取實質(zhì)為輪廓跟蹤問題，即通過順序找出邊緣點跟蹤邊界。輪廓跟蹤常用的算法是基于4連通或8連通區(qū)域的方法。本文采用基于8連通區(qū)域的跟蹤算法，其主要步驟：

① 按從上到下，從左到右掃描圖像,尋找第一個邊界點。

② 按一定準(zhǔn)則逆時針?biāo)阉鳟?dāng)前3×3鄰域像素。

③ 直到得到閉合邊界，則跟蹤結(jié)束。

得到跟蹤結(jié)果后，對多邊形邊界數(shù)據(jù)采用Douglas-Peucker矢量數(shù)據(jù)壓縮方法進行壓縮。由于Douglas-Peucker矢量數(shù)據(jù)壓縮是針對曲線(首尾不相連)的壓縮方法，對多邊形處理時需要將多邊形分解為兩條曲線。分解時，選擇多邊形中距離最遠的兩個點將多邊形分為兩個曲線段。跟蹤的結(jié)果如圖1所示的兩個紅色多邊形。

3.2 兩兩影像重疊區(qū)域的計算

跟蹤所有影像的有效區(qū)域多邊形后，需要確定所有多邊形之間的重疊關(guān)系，即計算具有重疊關(guān)系的兩兩多邊形之間的交集，本質(zhì)為多邊形的剪裁(求交集)問題。

本文采用Weiler多邊形裁剪算法進行確定[2-3]交集多邊形。該方法中首先確定主多邊形和裁剪多邊形，然后根據(jù)邊的相交關(guān)系確定“出點”(主多邊形由此離開裁剪多邊形區(qū)域)和“入點”(主多邊形由此進入裁剪多邊形)，并把“出點”和“入點”坐標(biāo)插入到多邊形頂點表中，最后從多邊形的頂點中按照順時針或逆時針的順序確定多邊形的交集。

設(shè)多邊形(順時針)P1-P2-P3-P4為主多邊形，多邊形C1-C2-C3-C4-C5-C6為剪裁多邊形。J1、J2、J3、J4、J5、J6、J7和J8為被剪裁多邊形和剪裁多邊形的交點，則圖中的“入點”為J1、J3、J5和J7；“出點”為J2、J4、J6和J8。

圖3 Weiler多邊形交集計算原理

交集查找方法(順時針)：

① 從主多邊形的起點開始搜索“入點”，如果該點未被查找過(未被標(biāo)記)，則該“入點”作為交集多邊形的起始點，并沿主多邊形按順時針進行頂點的搜集、查找。

② 碰到“出點”，則轉(zhuǎn)入剪裁多邊形進行搜索；

③ 直到被剪裁多邊形中的所有“入點”均被查找；

該方法得到的兩個多邊形的交集J1-J8-J7-J6-C3-J5-J4-J3-J2-C6。

3.3 重疊區(qū)域分割線的生成

重疊區(qū)域分割線應(yīng)盡量平分重疊區(qū)域。文中采用一種基于四叉樹結(jié)構(gòu)原理的多邊形中任意兩點間路徑的提取算法進行分割線的提取，該算法的主要步驟：

① 首先對重疊區(qū)域多邊形采用割耳(Ear Clipping)的方法進行三角剖分；

多邊形的耳，是多邊形中凸點與兩個相鄰點組成的三角形，而且對角線不與其他邊相交。 Ear Clipping方法的主要原理為：逐次從多邊形中割去一個耳作為剖分的結(jié)果，直至剩余最后一個三角形。

② 得到重疊區(qū)域多邊形中的公共點(A點和B點)。

③ 采用四叉樹遍歷方法從剖分結(jié)果中提取指定起點和終點的分割線；

如圖4表示多邊形A～S的Ear Clipping三角形剖分結(jié)果(虛線)。假設(shè)B點和H點為指定的起點和終點(兩個多邊形的重疊區(qū)域中表示公共點)，采用四叉樹結(jié)構(gòu)遍歷B點和H點之間路徑的方法為：查找B點所在三角形的所有跨接邊的中點(0,1,2)，分別以0,1,2為節(jié)點(共有三棵四叉樹)遍歷所有的跨接邊的中點，直到查找到終點H所在三角形中的跨接邊。若以點1為節(jié)點遍歷，得到的路徑圖及四叉樹表示如圖4和圖5所示：

圖4 重疊多邊形兩點間路徑

圖5 兩點間路徑四叉樹結(jié)構(gòu)表示

指定起點和終點間的路徑也可能有多條，需采取一定的優(yōu)化方法提取最優(yōu)的一條，如路徑距離最短或分割多邊形為兩部分的面積差最小。

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

初始鑲嵌網(wǎng)絡(luò)的生成方法流程如圖6,圖7和圖8。圖6中A、B和C為三張正射影像有效區(qū)域，ab、ac及bc分別為AB、AC、和BC兩兩間重疊區(qū)域的分割線，則鑲嵌多邊形生成步驟如下：

① 得到多邊形相關(guān)的所有分割線,如圖6中A多邊形相關(guān)的分割線為ab,ac。

② 用每一條分割線分割多邊形，并把分割后的多邊形作為下一條分割線分割時的輸入多邊形，直到處理完所有的多邊形和分割線。用圖6中的ab和ac分別分割A(yù)多邊形得到A1多邊形(圖7)，生成的初始多邊形網(wǎng)絡(luò)如圖8所示。

圖6 影像多邊形及分割線

圖7 初始鑲嵌多邊形

圖8 初始鑲嵌多邊形網(wǎng)絡(luò)

3.5 初始鑲嵌多邊形網(wǎng)絡(luò)拓撲編輯

生成的初始鑲嵌多邊形可能含有孔洞(圖 8)，在鑲嵌過程中視之為拓撲錯誤。

(1) 鑲嵌多邊形網(wǎng)絡(luò)中孔洞產(chǎn)生原理

在圖6、圖7和圖8鑲嵌多邊形網(wǎng)絡(luò)生成過程中，用ab、ac和bc分割三個多邊形A、B和C時，由于三條分割線不相交于同一個點，分割時將可能產(chǎn)生孔洞。

(2) 孔洞的檢測與消除

由上述定義6、7可知，在圖8由A1，B1和C1組成的多邊形網(wǎng)絡(luò)中，點1、2邊、點2、3邊和點3、4邊組成A1多邊形和B1多邊形的公共邊。點5、6和7三邊組成A1多邊形和C1多邊形的公共邊，點9、10、11、12四邊組成B1多邊形和C1多邊形的公共邊?？锥炊噙呅?點4、7、8和9組成)的邊出現(xiàn)一次，為邊界邊。由孔洞多邊形產(chǎn)生原理又知，孔洞多邊形的邊是分割線的一部分。

基于孔洞多邊形邊的特點(屬于邊界邊，并且為分割線上的一段)。本文提出了初始鑲嵌多邊形網(wǎng)絡(luò)中，孔洞的自動檢測方法：首先對鑲嵌多邊形邊進行分類，并提取位于分割線之上的邊界邊(限制條件)，然后對得到的所有邊界邊進行首尾組合，生成封閉的多邊形，即孔洞。

得到鑲嵌多邊形網(wǎng)絡(luò)中孔洞后，可以采用多種方法消除孔洞。如以簡單多邊形內(nèi)的任意一點代替孔洞多邊形的各個頂點坐標(biāo)，并用該點對鑲嵌多邊形網(wǎng)絡(luò)中相應(yīng)頂點進行更新替換，得到經(jīng)過拓撲編輯的最終鑲嵌線多邊形網(wǎng)絡(luò)。

4 鑲嵌多邊形網(wǎng)絡(luò)生成與鑲嵌結(jié)果

為測試本文所提方法的有效性，分別利用兩個航帶的航空影像數(shù)據(jù)(圖9)和美國火星車影像數(shù)據(jù)(圖12)進行正射影像鑲嵌試驗。圖9中數(shù)據(jù)為兩個航帶共12幅影像,圖12中數(shù)據(jù)為美國火星車影像制作得到的正射影像,共10幅。

圖9、圖12紅色多邊形為采用8-鄰域方法跟蹤得到的正射影像有效多邊形范圍，綠線為所有重疊區(qū)域的分割線。圖10為得到的山區(qū)影像鑲嵌多邊形網(wǎng)絡(luò)。圖13為得到的火星影像初始鑲嵌多邊形網(wǎng)絡(luò)，圖13,圖14為兩個區(qū)域的鑲嵌結(jié)果。

圖9 山區(qū)影像多邊形范圍(紅線)及分割線(綠線)

圖10 山區(qū)影像鑲嵌多邊形網(wǎng)絡(luò)

圖11 山區(qū)影像鑲嵌結(jié)果圖

圖12 火星車影像多邊形范圍(紅)及分割線(綠)

圖13 火星車影像鑲嵌多邊形網(wǎng)絡(luò)

圖14 火星車影像鑲嵌結(jié)果圖

5 結(jié)束語

正射影像鑲嵌是攝影測量與遙感中數(shù)據(jù)生產(chǎn)的一項重要工作。本文采用自動化處理的流程替代手工鑲嵌處理，可以方便，快捷地進行鑲嵌處理，大大減輕了人工的工作量，且文中所述的鑲嵌方法同樣適用于規(guī)則邊緣正射影像鑲嵌處理，具有較好的應(yīng)用價值。

參考文獻：

[1] 潘俊,王密,李德仁.基于顧及重疊的面Voronoi圖的接縫線網(wǎng)絡(luò)生成方法[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2009,34(5):518-521.

[2] WEILER K.Polygon comparison using a graph representation[J].Computer Graphics,1980(14):10-18.

[3] WEILER K, ATHERTON P. Hidden surface removal using polygon area sorting[J].Computer Graphics,1977,1(11):214-222.

[4] 馬小虎,潘志庚,石教英.基于凹凸頂點判定的簡單多邊形Delaunay三角剖分[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,1999,(1):1-6.

[5] 周培德.計算幾何[M].北京:清華大學(xué)出版社,2001:212-235.

[6] 王中輝,閆浩文.多邊形主骨架線提取算法的設(shè)計與實現(xiàn)[J].地理與地理信息科學(xué),2011,27(1):43-48.

[7] 高福順,高占恒,梁學(xué)章.三角網(wǎng)絡(luò)中的孔洞修補算法[J].研究快報,2009,46(6).

[8] 鄧敏,李志林,李光強.簡單面目標(biāo)與孔洞面目標(biāo)間拓撲關(guān)系的層次表達方法[J].測繪學(xué)報.2008,37(3):330-337.

[9] 周曉光,陳軍,蔣捷等.地籍地塊間的空間拓撲關(guān)系[J].測繪學(xué)報,2003,32(4):356-361.

[10] 李根,陳志楊,張三元，等.網(wǎng)格曲面中復(fù)雜孔洞的自動修補算法[J].浙江大學(xué)學(xué)報(工學(xué)版),2007,41(3):407-411.