TIN壓縮技術(shù)方法研究

王 璇，朱 映，王 瑋

(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)時勢成為當(dāng)今研究的熱點。DEM有許多種表示方法，其中不規(guī)則三角網(wǎng)模型(即TIN模型)相對于DEM中的其他模型有著不可替代的優(yōu)點［1］。地理信息數(shù)據(jù)量的增大，對空間數(shù)據(jù)的存儲和傳輸提出了很高的要求，除了提高硬件設(shè)備，開發(fā)DEM的壓縮算法也成為一種迫切的需求。因此，研究TIN的建立和壓縮是非常有意義的［2］。

二、頂點聚合法和基于中心點的頂點消去算法介紹

1.頂點聚合法

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

閾值為10的頂點聚合如圖1所示。

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

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

圖1 閾值為10的頂點聚合

2.基于中心的頂點消去算法

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

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

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

圖2 閾值為R的基于中心的頂點消去算法原理

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

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

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

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

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

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

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

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

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

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

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

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

1.基于中心點的頂點消去法

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

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

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

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

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

2.頂點聚合法

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

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

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

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

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

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

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

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

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

六、結(jié)束語

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

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

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

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

［2］蔡先華，鄭天棟.數(shù)字高程模型數(shù)據(jù)壓縮及算法研究［J］.測繪通報，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］林報嘉，葉燕林，趙建偉.三角網(wǎng)的生成與簡化算法［J］.地理學(xué)與國土研究，2001，17(1):69-71.