王 璇，朱 映，王 瑋

(1.中山市基礎(chǔ)地理信息中心，廣東中山528400;2.江蘇省基礎(chǔ)地理信息中心，江蘇南京210013)

一、引 言

隨著地理信息系統(tǒng)、遙感、虛擬地理環(huán)境等技術(shù)的發(fā)展，數(shù)字高程模型(DEM)得到了廣泛的應(yīng)用。DEM數(shù)據(jù)處理、傳輸速度與用戶需求之間的矛盾日益突出，DEM數(shù)據(jù)壓縮技術(shù)便順應(yīng)時(shí)勢(shì)成為當(dāng)今研究的熱點(diǎn)。DEM有許多種表示方法，其中不規(guī)則三角網(wǎng)模型(即TIN模型)相對(duì)于DEM中的其他模型有著不可替代的優(yōu)點(diǎn)［1］。地理信息數(shù)據(jù)量的增大，對(duì)空間數(shù)據(jù)的存儲(chǔ)和傳輸提出了很高的要求，除了提高硬件設(shè)備，開發(fā)DEM的壓縮算法也成為一種迫切的需求。因此，研究TIN的建立和壓縮是非常有意義的［2］。

二、頂點(diǎn)聚合法和基于中心點(diǎn)的頂點(diǎn)消去算法介紹

1.頂點(diǎn)聚合法

頂點(diǎn)聚合的方法是由 Rossignac和Borrel［3］最先提出的。其基本思想是將輸入模型的頂點(diǎn)坐標(biāo)量化成整數(shù)，這相當(dāng)于在幾何上建立了一個(gè)方格坐標(biāo)，而將所有落在一個(gè)方格內(nèi)的頂點(diǎn)合并(聚合)為一個(gè)代表該方格的頂點(diǎn)，被完整地包含在一個(gè)方格中的所有三角形和邊也都被合并為一個(gè)點(diǎn)，從而簡(jiǎn)略掉這些三角形和邊。

閾值為10的頂點(diǎn)聚合如圖1所示。

圖中，點(diǎn)A、B、C將被聚合到點(diǎn)D的位置，也就是虛擬網(wǎng)格的交點(diǎn)，從而簡(jiǎn)化三角網(wǎng)。此時(shí)，需要對(duì)點(diǎn)D進(jìn)行高程預(yù)測(cè)。本文采用反距離加權(quán)的方法，公式如下

式中，Zi是i點(diǎn)的高程;Si是i點(diǎn)到網(wǎng)格交點(diǎn)的距離。

圖1 閾值為10的頂點(diǎn)聚合

2.基于中心的頂點(diǎn)消去算法

介于上面的方法要進(jìn)行高程的插值，筆者提出一種無(wú)需插值、可以直接快速壓縮三角網(wǎng)的方法，過(guò)程類似于頂點(diǎn)消去法，基于某中心點(diǎn)為基礎(chǔ)進(jìn)行點(diǎn)的消去。

該方法原理簡(jiǎn)單，以某個(gè)點(diǎn)為中心，基于某種消去條件，刪除周圍該條件下指標(biāo)小于該閾值的點(diǎn)。一般最簡(jiǎn)單的情況是以距離作為消去條件，即離目標(biāo)點(diǎn)小于某閾值的點(diǎn)刪除。

閾值為R的基于中心的頂點(diǎn)消去算法如圖2所示，離中心點(diǎn)A的距離小于R的點(diǎn)B、C、D將被消去。

圖2 閾值為R的基于中心的頂點(diǎn)消去算法原理

三、系統(tǒng)的總體框架設(shè)計(jì)與主要功能實(shí)現(xiàn)

系統(tǒng)的總體框架設(shè)計(jì)如圖3所示。

圖3 系統(tǒng)總體框架設(shè)計(jì)

軟件主要實(shí)現(xiàn)以下功能:

1)數(shù)據(jù)錄入:通過(guò)兩種方式錄入數(shù)據(jù)，第一種是以類似數(shù)字化的方式從屏幕直接通過(guò)鼠標(biāo)點(diǎn)擊錄入數(shù)據(jù)點(diǎn);第二種是通過(guò)外部文件(*.txt)直接載入文件。

2)TIN建立:該軟件的TIN建立方法為靜態(tài)三角網(wǎng)生長(zhǎng)算法［4］，內(nèi)部算法結(jié)構(gòu)采用隊(duì)列法。

3)TIN壓縮:該軟件實(shí)現(xiàn)了兩種TIN壓縮方法，即頂點(diǎn)聚合法和基于中心點(diǎn)的頂點(diǎn)消去法。

4)結(jié)果評(píng)估:該軟件可以對(duì)壓縮前后的頂點(diǎn)數(shù)和三角形數(shù)進(jìn)行統(tǒng)計(jì)，用于壓縮評(píng)價(jià)指標(biāo);另外，通過(guò)從外部錄入的校正點(diǎn)，可以計(jì)算高程誤差和高程中誤差。

5)數(shù)據(jù)點(diǎn)管理與操作:軟件對(duì)于數(shù)據(jù)點(diǎn)的管理與操作通過(guò)內(nèi)置的頂點(diǎn)數(shù)組來(lái)實(shí)現(xiàn)，通過(guò)在數(shù)組中添加刪除點(diǎn)，然后進(jìn)行三角網(wǎng)的實(shí)時(shí)重繪，來(lái)實(shí)現(xiàn)數(shù)據(jù)點(diǎn)的管理。

四、不同算法各閾值下壓縮結(jié)果分析

選取南京紫金山試驗(yàn)區(qū)的1∶5萬(wàn)地形圖等高線數(shù)據(jù)。通過(guò)軟件的即時(shí)輸入方法(數(shù)字化)構(gòu)網(wǎng)后，節(jié)點(diǎn)個(gè)數(shù)為52，三角形個(gè)數(shù)為82。原始數(shù)據(jù)生成的TIN如圖4所示。

圖4 原始數(shù)據(jù)生成的TIN

1.基于中心點(diǎn)的頂點(diǎn)消去法

對(duì)建立的TIN采用基于中心點(diǎn)的頂點(diǎn)消去法進(jìn)行壓縮，分別取閾值為10、20、30、40個(gè)像素，壓縮結(jié)果(即重新構(gòu)網(wǎng)的結(jié)果)如圖5所示。其中，(a)、(b)、(c)、(d)分別為閾值10、20、30、40 壓縮后的三角構(gòu)網(wǎng)。從圖中可以看出，隨著閾值的增大，壓縮后TIN的三角網(wǎng)密度在減小，精度在降低。

圖5 基于中心點(diǎn)的頂點(diǎn)消去法壓縮結(jié)果圖

在10、20、30、40個(gè)像素的閾值下的TIN數(shù)據(jù)壓縮后，各閾值下的壓縮結(jié)果統(tǒng)計(jì)見表1，各閾值下的高程誤差統(tǒng)計(jì)見表2。從表1可以看出，隨著閾值的增大，數(shù)據(jù)量、節(jié)點(diǎn)數(shù)、三角形個(gè)數(shù)都在減少，數(shù)據(jù)量壓縮比、點(diǎn)壓縮比和三角形壓縮比迅速增大，但三角網(wǎng)產(chǎn)生的特征形變不大。

表1 各閾值下的壓縮結(jié)果統(tǒng)計(jì)表

表2 各閾值下的高程誤差統(tǒng)計(jì)表

2.頂點(diǎn)聚合法

對(duì)建立的TIN采用基頂點(diǎn)聚合壓縮方法進(jìn)行壓縮，分別取閾值為10、20、30、40個(gè)像素。壓縮結(jié)果(即重新構(gòu)網(wǎng)的結(jié)果)如圖6所示。其中，(a)、(b)、(c)、(d)分別為閾值 10、20、30、40 壓縮后的三角構(gòu)網(wǎng)。從圖中可以看出，隨著閾值的增大，壓縮后TIN的三角網(wǎng)密度在減小，精度在降低，同時(shí)，產(chǎn)生了很大的變形。

圖6 頂點(diǎn)聚合法壓縮結(jié)果圖

利用頂點(diǎn)聚合法，可以看出，隨著閾值的增大，高程中誤差增大較快，三角網(wǎng)的形狀變化非常大，但三角形數(shù)量的減少并不顯著。各閾值下的壓縮結(jié)果統(tǒng)計(jì)見表3，各閾值下的高程誤差統(tǒng)計(jì)見表4。

表3 各閾值下的壓縮結(jié)果統(tǒng)計(jì)表

表4 最大高程誤差和中誤差差值表

五、兩種方法的比較及結(jié)論

通過(guò)上面的比較可以看出，頂點(diǎn)消去法的壓縮比率非常大，三角網(wǎng)的變形不大;頂點(diǎn)聚合法的壓縮比增大并不多，但三角網(wǎng)產(chǎn)生的特征形變卻很大。基于給定數(shù)據(jù)點(diǎn)的特征，得出以下結(jié)論:

從壓縮結(jié)果來(lái)看，頂點(diǎn)消去法更能適合試驗(yàn)區(qū)域。它產(chǎn)生的三角網(wǎng)形狀變化和高程誤差比頂點(diǎn)聚合法都要小一些。由于高程點(diǎn)比較稀疏，隨著閾值的增大，頂點(diǎn)聚合法的網(wǎng)格效應(yīng)非常明顯，可見此方法不適用于采集點(diǎn)過(guò)于稀疏的情況。雖然頂點(diǎn)消去法的高程中誤差較小，但并不能完全說(shuō)明它的絕對(duì)優(yōu)越性。該方法的壓縮過(guò)程不經(jīng)過(guò)插值，也沒(méi)有點(diǎn)的移動(dòng)，因此在誤差計(jì)算時(shí)可能會(huì)出現(xiàn)一些與校正點(diǎn)重合的高程點(diǎn)，這些點(diǎn)的高程誤差是0，從而使整個(gè)三角網(wǎng)的誤差偏低。頂點(diǎn)消去法不經(jīng)過(guò)插值，所以使一些不該刪去的點(diǎn)被刪去，可能會(huì)丟失一些重要的高程點(diǎn)，且一些重要的地形特征被當(dāng)作冗余信息被壓縮，故仍需要在程序中加以控制，強(qiáng)制保留重要高程點(diǎn)。

對(duì)于頂點(diǎn)聚合法，考慮到采集點(diǎn)的密度不大，在進(jìn)行強(qiáng)制性的網(wǎng)格轉(zhuǎn)換時(shí)每個(gè)點(diǎn)移位都比較大，從而產(chǎn)生了較大的誤差。另外，大量的插值導(dǎo)致誤差的累積，也是該方法產(chǎn)生較大誤差的原因。頂點(diǎn)聚合法的優(yōu)點(diǎn)在于，壓縮后三角網(wǎng)中的每一個(gè)點(diǎn)都保留了原始三角網(wǎng)中相鄰數(shù)據(jù)點(diǎn)的信息，從而在反映特殊地貌上不存在丟失重要高程點(diǎn)的缺點(diǎn)，但仍然需要提高插值的精度，以降低高程誤差。

六、結(jié)束語(yǔ)

本次試驗(yàn)通過(guò)對(duì)比基于中心點(diǎn)的頂點(diǎn)消去法和頂點(diǎn)聚合法對(duì)同一地區(qū)TIN的壓縮，分析二者產(chǎn)生誤差的不同原因及優(yōu)缺點(diǎn)，并提出相應(yīng)的解決方案如下:

對(duì)于基于中心點(diǎn)的頂點(diǎn)消去法，由于該方法不經(jīng)過(guò)插值，其精確度很大程度取決于各中心點(diǎn)的選取。在實(shí)際操作中，應(yīng)該對(duì)高程點(diǎn)進(jìn)行預(yù)處理，找出對(duì)地形影響較大的高程點(diǎn)和一些重要的、標(biāo)志性的高程點(diǎn)，強(qiáng)制使其成為中心點(diǎn)，從而在壓縮過(guò)程中不被刪去。這樣將顯著提高該方法的誤差。

對(duì)于頂點(diǎn)聚合法，由于在實(shí)際工作和研究中，高程采集點(diǎn)的密度會(huì)比本文的試驗(yàn)中大很多，因此，該方法的主要誤差來(lái)源是插值方法。從便于研究的方便出發(fā)，本文選擇了簡(jiǎn)單易行的反距離加權(quán)插值。在實(shí)際應(yīng)用中，則應(yīng)該針對(duì)不同的地形特征，研究更加精確、更加適合于試驗(yàn)區(qū)地形的插值方式。

［1］李志林，朱慶.數(shù)字高程模型［M］.武漢:武漢大學(xué)出版社，2001.

［2］蔡先華，鄭天棟.數(shù)字高程模型數(shù)據(jù)壓縮及算法研究［J］.測(cè)繪通報(bào)，2003(12):16-18.

［3］ROSSIGNAC J，BORREL P.Multi-Resolution 3D Approximations for Rendering Complex Scenes［C］∥Geometric Modeling in Computer Graphics.［S.l.］:Springer Berlin Heidelberg 1993:455-465.

［4］林報(bào)嘉，葉燕林，趙建偉.三角網(wǎng)的生成與簡(jiǎn)化算法［J］.地理學(xué)與國(guó)土研究，2001，17(1):69-71.