項(xiàng)琳，岳貴杰，杜黎明

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

1 引 言

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

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

2 常用定義

影像有效范圍：用多邊形表示的影像有效像素范圍。如圖1中的紅色多邊形內(nèi)部像素，無效像素為背景色(黑)，白色矩形邊框?yàn)橛跋窀采w范圍。

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

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

拓?fù)淇锥矗鸿偳抖噙呅尉W(wǎng)絡(luò)中存在的未被覆蓋的部分。如圖8中的點(diǎn)4、7、8和9組成的多邊形(紅色部分)。

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

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

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

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

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

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

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

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

3.1 影像多邊形的自動(dòng)提取

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

① 按從上到下，從左到右掃描圖像,尋找第一個(gè)邊界點(diǎn)。

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

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

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

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

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

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

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

圖3 Weiler多邊形交集計(jì)算原理

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

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

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

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

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

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

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

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

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

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

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

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

圖4 重疊多邊形兩點(diǎn)間路徑

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

指定起點(diǎn)和終點(diǎn)間的路徑也可能有多條，需采取一定的優(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。

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

圖6 影像多邊形及分割線

圖7 初始鑲嵌多邊形

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

3.5 初始鑲嵌多邊形網(wǎng)絡(luò)拓?fù)渚庉?/h3>

生成的初始鑲嵌多邊形可能含有孔洞(圖 8)，在鑲嵌過程中視之為拓?fù)溴e(cuò)誤。

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

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

(2) 孔洞的檢測(cè)與消除

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

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

得到鑲嵌多邊形網(wǎng)絡(luò)中孔洞后，可以采用多種方法消除孔洞。如以簡(jiǎn)單多邊形內(nèi)的任意一點(diǎn)代替孔洞多邊形的各個(gè)頂點(diǎn)坐標(biāo)，并用該點(diǎn)對(duì)鑲嵌多邊形網(wǎng)絡(luò)中相應(yīng)頂點(diǎn)進(jìn)行更新替換，得到經(jīng)過拓?fù)渚庉嫷淖罱K鑲嵌線多邊形網(wǎng)絡(luò)。

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 潘俊,王密,李德仁.基于顧及重疊的面Voronoi圖的接縫線網(wǎng)絡(luò)生成方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(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] 馬小虎,潘志庚,石教英.基于凹凸頂點(diǎn)判定的簡(jiǎn)單多邊形Delaunay三角剖分[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),1999,(1):1-6.

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

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

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

[8] 鄧敏,李志林,李光強(qiáng).簡(jiǎn)單面目標(biāo)與孔洞面目標(biāo)間拓?fù)潢P(guān)系的層次表達(dá)方法[J].測(cè)繪學(xué)報(bào).2008,37(3):330-337.

[9] 周曉光,陳軍,蔣捷等.地籍地塊間的空間拓?fù)潢P(guān)系[J].測(cè)繪學(xué)報(bào),2003,32(4):356-361.

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