矢量空間數據漸進傳輸研究進展

溫 永 寧，閭 囯 年，陳 旻

矢量空間數據漸進傳輸研究進展

溫 永 寧1，2，閭 囯 年1，陳 旻3

（1.南京師范大學虛擬地理環境教育部重點實驗室，江蘇 南京 210046;2.蘇州工業園區測繪有限公司，江蘇 蘇州 215021;3.香港中文大學太空與地球信息科學研究所，香港 沙田）

漸進傳輸被認為是解決目前海量空間數據傳輸與實時用戶體驗之間矛盾的有效方法。柵格數據漸進傳輸的相關研究比較成熟，但矢量數據的漸進傳輸理論和技術還存在問題。為了推進矢量數據漸進傳輸的相關研究，該文對與矢量數據漸進傳輸密切相關的二維矢量數據、三維表面模型兩種數據的多分辨率表達和漸進傳輸的研究現狀進行歸納與總結，指出相關研究的發展方向，為海量空間數據適用于分布式網絡傳輸提供參考依據。

空間數據;矢量數據;漸進傳輸

0 引言

傳統意義上，空間數據模型可分為矢量和柵格兩種;按照數據生產的目標，又可分為4D產品，即數字線畫圖（DLG）、數字正射影像（DOM）、數字高程模型（DEM）和數字柵格地圖（DRG）。如何協調計算機有限的內存、帶寬與海量空間數據傳輸之間的矛盾是當前GIS研究的重要課題。雖然空間數據的類型不同，但在解決海量數據的應用與傳輸問題上存在一些通用方法：1）對數據進行處理，建立數據的多分辨率表達，根據不同顯示需求所采用的比例尺或分辨率，傳遞相應分辨率的數據。2）采用數據漸進傳輸的方法，即如果高分辨率的數據可以通過低分辨率數據增加細節增量而得到，則傳輸時先傳遞低分辨率的數據，然后根據需要依次傳遞細節增量，最終得到合適分辨率的數據。

目前，柵格數據漸進傳輸研究比較成熟，相關國際標準和商業軟件已經出現，部分算法和產品也已經實用化。但矢量數據的漸進傳輸還不是很成熟，主要原因有以下方面：

（1）矢量數據本身存在復雜性。影像/柵格數據結構單一，可以認為是一種結構化數據。矢量數據則比較復雜，可分為要素和要素集合兩個層次。其中，要素又包括幾何和屬性兩部分，幾何部分包括點、線、面3種對象類型;幾何要素之間存在拓撲關系。

（2）矢量數據傳輸存在多目標與多層次特征。影像/柵格漸進傳輸的目標僅考慮可視化，以最終的視覺結果為判定標準。矢量數據的應用包含制圖輸出和空間分析兩種不同的功能，其漸進傳輸與制圖綜合問題相關聯，不僅涉及單個地理要素的多分辨率組織與漸進傳輸，還涉及多要素之間漸進傳輸結果可視化的邏輯一致性問題。

（3）缺乏堅實的理論基礎。傳統的矢量數據漸進傳輸通常被看做制圖綜合的逆向過程進行研究。目前，雖然制圖綜合算法和數據模型被大量引入到漸進傳輸與數據的多分辨率組織之中，但是制圖綜合本身尚有很多問題需要解決，如在拓撲一致性、化簡結構的適用性方面尚有難以克服的困難。

（4）缺乏集成性?，F有的矢量數據漸進傳輸算法較少考慮現代GIS體系結構，為達漸進傳輸目的而設計的獨立體系的數據結構與模型很難融入GIS主流體系中。此外，基于關系數據庫存儲是GIS工程中矢量數據的通用存儲方案;在制圖綜合領域雖然設計了一些多分辨率的矢量數據存儲結構，但以上結構仍難以方便地映射為GIS關系存儲模型。

1 二維矢量數據漸進傳輸的相關研究

Buttenfield等指出矢量數據漸進傳輸應該與制圖綜合緊密相連，是制圖綜合的逆過程［1－4］。因此，某些制圖綜合的算法、數據結構經過改造可以應用于矢量數據的漸進傳輸。

1.1 二維矢量數據漸進傳輸框架研究

Buttenfield針對線特征提出了GIS數據漸進傳輸的實現流程［1］，其思想是基于制圖綜合方法對原始數據進行預處理，生成矢量數據的多分辨率表達模型。該模型的建立步驟：1）根據專題建立圖層，圖層基于文件方式分離存儲;2）對圖層中的要素按照重要度排序;3）建立每個幾何要素的多分辨率模型。Buttenfield使用D-P算法對線要素進行化簡，并基于條帶樹進行線要素的多分辨率存儲，該方法的缺陷在于只能針對線要素保持拓撲關系，不能保持其他空間對象間的拓撲關系。如果要保持拓撲關系，則需附加算法對數據進行預處理。

Bertolotto等提出了基于胞腔復形矢量數據模型的漸進傳輸組織方案［2－4］，該方案定義了線收縮、面收縮、區域細化、線合并、區域合并、點抽取、線抽取等地圖化簡基本算子;通過上述算子，可以對地圖進行遞歸化簡，建立多分辨率模型。為了維護要素間的拓撲一致性，所有的矢量數據都保存在一個圖層中。該方法的效果相當于建立地圖級的離散LOD模型，但無法支持要素級別的漸進傳輸。

與Bertolotto的方案相似，楊必勝等［5］提出了一種基于頂點刪除模式的矢量數據漸進傳輸組織方案，該方案使用“面條模型”表達地圖，包含點、線和多邊形3種幾何對象，其中線和多邊形對象由頂點構成。為了建立頂點、線與多邊形之間的拓撲關系，將頂點分為3種基本類型：1）一個或兩個同層對象共享的頂點;2）兩個以上同層對象共享的頂點;3）一個以上多層對象共享的頂點?；陧旤c類型和原有拓撲關系，對頂點進行刪除操作。類似于Visvalingam-Whyat算法［6］，對刪除的頂點進行排序，并將刪除的頂點壓入堆棧結構中供后續漸進傳輸使用。該方法較之Bertolotto方法完整地實現了曲線的漸進傳輸，在刪除過程中保持拓撲關系不變，但是沒有考慮其它制圖綜合算子。由于算法需要對整個地圖進行漸進式化簡，所以最大的問題在于無法根據可視區域組織漸進數據流。

Ai等提出了一種基于變化累積模型的矢量數據漸進傳輸組織方案［7］，定義了“加”、“減”和“替換”3種基本的變化累積操作，通過這3種操作將客戶端的實時綜合與服務器端的離線綜合統一起來。對多邊形特征利用層次分解技術，化簡成一系列的凸殼和矩形，基于層次樹建立幾何對象的多分辨率表達。該算法適用于離散的多邊形對象（如湖泊、房屋等）的漸進傳輸。此外，Cecconi等提出了實現矢量數據漸進傳輸框架，并列出了3個核心研究點［8］：1）漸進傳輸相關的地圖綜合算法;2）在客戶服務器模型下的數據傳輸機制;3）客戶端矢量數據組合的問題。David等提出了面向服務的矢量數據漸進傳輸框架［9］，該框架融合了在線制圖綜合技術，不僅可以在服務器端生成客戶端需要顯示的SVG文檔，還可以為客戶端提供下載文檔服務，并在后續傳輸時，通過XML DOM更新客戶端的顯示。

1.2 矢量數據制圖綜合與幾何化簡

目前，制圖綜合算法被大量應用于矢量數據漸進傳輸研究中。綜合的目的是為了獲得特定分辨率的空間數據，由于矢量數據以要素集合的形式組織，所以多分辨率矢量數據被分為兩個級別：1）要素級的算法主要是針對曲線和多邊形邊界的化簡;2）要素集合級的算法則是要素之間制圖綜合過程，包括合并、移位、夸張等過程。

制圖綜合的基礎在于空間數據的化簡算法，其中最重要的是曲線的化簡。曲線的化簡算法類型較多，如點刪除算法（以 D-P算法和 Visvalingam－Whyat算法為代表）、重采樣算法（以Li-Openshaw算法為代表）、基于小波分析的算法、曲線層次結構方法、分形方法、組合優化方法、網格化方法等。

Douglas-Peucker算法（簡稱 D-P算法）是最常用的一種曲線數據壓縮算法。該算法基于點刪除原理，通過遞歸地刪除距離曲線兩個端點連線距離最近的點實現曲線壓縮。大量曲線壓縮和曲線化簡算法是基于對D-P算法的改進而實現的［10］。另外一種點刪除算法是Visvalingam-Whyat算法（簡稱VW算法），該算法的原理是利用曲線上相鄰的3個點構成三角形，如果該三角形是所有三角形中面積最小的，則可以將中間的點從三角形刪除，化簡過程迭代到曲線中剩下兩個點為止［11］。Wang等對V-W算法進行了擴展，稱為Bend Simplification算法;該算法通過分析幾何對象的特征，刪除時的判斷因子不再是三角形面積，而是邊界圍成的凸殼和凹陷部分，同時該算法還集成了刪除、膨脹和合并的制圖綜合算子［12］。Yang等的算法均是在V-W算法基礎上考慮要素間拓撲關系的改進版本［13－16］?；邳c刪除的算法與條帶樹、BLG樹、多尺度線性樹等多分辨率的數據結構聯系緊密，算法的迭代運行過程可以由這些結構記錄，并通過“回放”實現漸進傳輸。

Li-Openshaw算法［17］是一種基于自然規律的自適應線狀要素綜合算法，其原理是用與比例尺相關的圓在原有曲線上滑動，對曲線進行重采樣，獲得綜合結果。其過程是對于特定的顯示分辨率，隨著比例尺變小，一個大的多邊形會形成一個小多邊形;當該多邊形只能用一個點表示時，就達到了極限尺寸。朱鯤鵬等對算法做了進一步改進，主要考慮了曲線上極大值和采樣圓與曲線多點相交的問題［18］。

基于小波的算法是實現曲線化簡的另一條途徑。Saux將B－樣條與小波分析相結合，針對需要光滑和連續性的曲線，進行曲線化簡研究［19］。吳凡利用Mallat算法，研究了獲取整數尺度上曲線的綜合問題，通過建立多尺度表達的一致性約束模型，對細節信息進行增補和閾值調控，實現了介于任意兩個整數尺度之間的線狀特征空間數據近似表達［20］。Wang等基于小波分析理論，研究了基于小波多尺度分析的等高線數據壓縮模型和算法，利用D-P算法對小波變換的邊界進行預處理，提取特征點，并在小波壓縮之后恢復特征點，保持了等高線的拓撲一致性［21－23］。

構建曲線的層次結構并以此為化簡依據是矢量數據化簡的另一種策略。Guo提出了一種基于線對象結構的漸進式化簡算法，該算法基于線上的特征（極值點、凸點、拐點、單調區間）建立線結構及其層次關系，以此為約束對曲線進行化簡［24］。艾廷華等基于曲線彎曲層次的概念，通過將曲線自身作為約束，建立曲線的帶約束Delaunay三角網，并根據三角形與頂點、曲線的關系對其進行分類;在分類基礎上，對Delaunay三角網應用剝皮算法，記錄剝皮的過程，根據被剝皮的三角形類型，迭代構建曲線的二叉樹組織結構，再根據彎曲的層次結構，對曲線進行化簡［25］。王橋等利用分形原理對線狀要素化簡的步長選擇問題進行研究，所提出的方法顧及了制圖綜合的目的，強調圖形形狀結構特征，調整自動綜合的效果，并能與其它方法配合使用［26，27］。Poorten等提出的算法能夠同時對多條曲線進行綜合，通過三角形之間的聯通關系，維護曲線之間的拓撲一致性［28］。杜維等提出了一種基于組合優化策略的多邊形化簡算法，其基本思想是以多邊形輪廓為目標，依據曲線特征點將其分解為一系列的彎曲特征，并對此彎曲特征集實施組合優化;通過將入圍的彎曲首尾相連，該算法可被應用于多邊形的化簡［29］。

網格法是將地理坐標表示成一系列的網格單元，利用網格單元作為控制結構實現要素的化簡。在這一方面，Dutton提出了層次坐標系統（Hierarchical Coordinate System）的概念，同時基于地球表面的結構采用QTM（Quaternary Triangular Mesh）加以描述［30－32］。QTM是相互嵌套的層次性三角形網格，覆蓋全球;其網格單元按照一定規則編碼，一個網格單元可以代表一定分辨率下確定的地理位置。在某一分辨率下，一條曲線可以用一系列的頂點所經過的單元ID表示;低分辨率的幾何要素由高分辨率的要素綜合得到，綜合過程受到QTM層次結構的控制，通過將同屬于一個低分辨率網格單元的頂點進行合并實現線狀要素的化簡。Wang等提出了適應性網格模型（Adaptive Lattice Model），并基于此建立了線和多邊形的綜合算法［33－35］。適應性網格類似于一個CCD相機陣列，提供了一個固定分辨率控制機制，在該網格分辨率下，點的坐標可以被四舍五入到網格上，某些頂點可以被合并，多邊形可以被聚合或者轉換成線狀要素。

1.3 二維矢量數據的多分辨率組織

矢量數據的多分辨率包含要素集合和要素兩個層次。通常通過樹結構的層次性生成要素集合多分辨率，常采用反應樹及其變種實現要素集合的多分辨率組織;通過化簡綜合算法生成線要素的多分辨率組織，常采用基于D-P算法所產生的多分辨率曲線存儲模型，包括STRIP樹、BLG樹和多叉樹。

反應樹（Reactive Tree）采用空間數據庫中進行多分辨率空間對象管理和索引的結構［36－38］，它是一種多路樹，其入口可分為對象和子樹兩種。每個節點包含若干入口，非葉子節點可以同時包含兩種節點，而葉子節點只能包含對象入口;每種入口都包含一個重要值指標以反映節點的多分辨率特性。反應樹可基于R樹、球樹、KD樹實現。李愛勤［39］討論了一種基于四叉樹的多分辨率數據組織模型，被認為是反應樹的四叉樹變種。

GAP樹（Generalized Area Partitioning tree）是管理平面分割的多分辨率組織結構［40］。在GAP樹中，一個節點對應一個被綜合的多邊形區域，節點下還可以包含不重要的低級多邊形，追蹤葉子到根的過程反映了多邊形綜合的過程。C-Tree是基于GAP樹的一種實現［41］。

STRIP樹也稱條帶樹，是一種二叉樹［42］，它通過記錄低精度曲線到高精度曲線的增量來表示多分辨率數據，可存儲任意的曲線結構。該樹可應用于D-P算法，通過記錄條帶樹抽取結點過程實現多分辨率的表達。

BLG樹（Binary Line Generalization tree）作為反應樹的補充［43，44］，也是基于二叉樹結構，其主要思想在于將D-P算法執行的中間過程按尺度特征進行記錄，建立細節累加模型。

多尺度線性樹（Multi-Scale Line Tree，MSLT）借鑒了STRIP樹的思想［45］，但它是多路樹而非二叉樹，結構的每個層次對應一個隱含的最大條帶寬度。此外，MSLT是面向節點的，在每個層次存儲節點，這些節點是更高層次的細節的中間層次。

多叉樹常應用于多邊形的多分辨率組織［46］，將按D-P算法抽取的不同層次細節的節點存儲在多叉樹結構索引矩陣中，在矩陣同一行中描述的具有等值偏移量的節點屬于同一等級，從而實現數據的層次細節存儲?；诙嗖鏄浣Y構，任應超等提出了一種面向線的多尺度表達的數據結構，該結構使用VW算法生成多分辨率曲線模型，支持曲線數據的編輯，利用關系模型將不同分辨率的數據存儲于不同的關系表中，以提升數據庫的訪問效率［47］。

2 三維表面模型的化簡與漸進傳輸

不規則三角網（Triangulated Irregular Network，TIN）也稱為三角形網格（Triangle Mesh）或簡稱網格（Mesh）。因為任何三維表面都可以使用不規則三角網進行逼近，所以不規則三角網是最為常用的一種三維表面建模方法。TIN是三維虛擬場景對象建模的基本模型，也是除柵格之外另一種表示DEM的數據結構，所以TIN的多分辨率表達和漸進傳輸既包括空間數據領域的研究工作，也包括計算機圖形學及三維動畫、游戲方面的工作。

2.1 三維表面模型的化簡算法

TIN的化簡是生成多分辨率模型的關鍵，將化簡后的模型組成序列就是該模型的多分辨率表達。按照在生成過程中使用的算子，可以將TIN的化簡算法分為頂點刪除法、重新布點法、頂點聚合法、區域合并法、邊折疊法、三角形折疊法以及基于小波分析的算法等。

頂點刪除法基本思想是刪除滿足一定條件的頂點，并對由此產生的空洞重新三角化，從而達到簡化模型的目的［48］。該算法首先將網格中的頂點劃分為簡單頂點、復雜頂點、邊界頂點、拐點和內部邊界頂點，然后根據相鄰頂點擬合局部切平面，計算頂點到擬合切平面的距離。若距離小于指定閾值，則刪除該頂點，對刪除頂點后所遺留的空洞進行局部三角剖分，壓縮過程中不能改變模型的拓撲關系。此后，Schroeder對算法進行了改進，通過剪切、縫合等操作，使得算法在構建LOD模型的過程中可以實現拓撲關系的修改［49］。

重新布點法基本思想是首先確定簡化模型中的頂點個數，按照一定的規則將一些頂點插入原始模型中，形成新舊模型共存的模型，然后刪除原始模型中的點，對刪除頂點后的空洞進行三角化，得到新頂點構成的簡化模型［50］。該算法中新點的分布采用排斥力算法，即先隨機分布新點，然后計算新點間的排斥力，根據排斥力在網格上移動這些新點，使它們重新分布。排斥力的大小與新點間的距離、新點所在三角面片的曲率、面積等有關。

頂點聚合法的基本思想是通過空間劃分將模型中的頂點劃分為一系列頂點簇，然后把簇內的點集聚合為一個頂點。該操作不依賴于原始模型的拓撲關系，僅與其幾何信息有關。最早的頂點聚類方法是均勻頂點聚類方法，該算法根據頂點的重要性對模型的頂點進行分類，并將模型所在的空間按用戶定義的大小剖分為若干個規則格網，把構成模型的所有頂點劃分到相應的子格網單元中，遍歷劃分的格網單元，按照一定的規則（如距離單元內所有頂點的加權平均距離）選擇可以代表整個格網單元中所有頂點的聚合頂點，最終得到由代表性頂點構成的LOD模型［51］。Luebke等通過建立空間自適應八叉樹剖分對上述算法進行了改進［52，53］。Low等提出利用立方體、球等任意簡單的形狀作為空間剖分的基本單元，并將單元的中心定位于單元內重要度最高的頂點，對于同時被包含在多個單元內的頂點，根據其與各單元中心的距離遠近進行分配［54］。

區域合并算法通過合并表面模型中的相鄰面片以達到降低模型復雜度的目的。其中的超面算法是比較經典的區域合并算法，該算法基于共面準則把表面模型分割成連通區域，分別用多邊形面片代替各個區域，并對多邊形面片的邊界進行簡化，最后重新生成三角化多邊形面片［55，56］。

邊折疊法是一個迭代的化簡算法，它按照一定的準則刪除三角網中的邊并重構三角網，以達到化簡模型的目的。邊折疊可以在化簡過程中形成自然的層次結構，便于多分辨率模型的構建。Hoppe最先提出了邊折疊化簡方法，該方法綜合考慮了頂點數目、近似表達誤差以及網格結構優化，可以獲得非常好的結果，但運算效率較低，后續研究主要集中在如何提高邊折疊的效率［57］。Ronfard等相繼提出了新的邊折疊的判別標準［58－62］。

三角形折疊法也是一種迭代化簡方法。該方法先將滿足折疊條件的三角面片的三個頂點合并為一個頂點，然后刪除退化的三角面片。一次三角形折疊相當于兩次邊折疊，因此三角形折疊的效率要優于邊折疊。Hamann首先提出了基于三角形折疊的表面LOD模型構建算法，該算法是基于三角形三個頂點曲率和三角形的形狀確定三角形權值，權值最低的三角形最先被折疊為一個頂點［63］。Isler以頂點的重要度決定基本操作算子（邊折疊或三角形折疊），以三角形的視覺重要度確定三角形折疊順序［64］。周昆利用折疊后的新點與被折疊三角形相關的三角形集合中各三角形所在平面的距離最大值的倒數作為權值，確定三角形的折疊順序［65］。

小波方法利用小波的多分辨率分析特性（Multi-Resilution Analysis，MRA），將模型分解為擬合域（即化簡后的模型）和細節域。Lounsbery最早將小波方法應用于三維表面模型化簡，他將具有分割連通性的曲面進行了小波分解［66，67］。此后，Eck等提出了將任意曲面轉換為分割連通性的方法，使得MRA可以應用于任意形狀的三維模型［68］。

2.2 三維表面模型的調度與傳輸策略

雖然網格化簡方法可以有效降低三維表面模型的數據量，但在處理海量數據時依然不能滿足繪制效率和用戶交互的要求，需與LOD、漸進傳輸等優化策略相配合，實現三維表面模型的調度與傳輸。

視點相關的LOD通過區域視覺重要度來定義，可以根據需要對局部格網區域有選擇地進行加密或者簡化，使得視覺重要度比較高的區域利用較高的分辨率表示。Gross在地形渲染中提出了地形表面模型的自適應視相關LOD表示法，并定義了用于改變局部區域模型質量的小波空間濾波算子［69］。Lindstrom等針對大數據量的地形渲染也提出了類似的方法［70－72］。Wang等設計并實現了一種具有拓撲保持特性的自適應視相關LOD模型的動態構建及實時更新方法［73］。

漸進網格（Progressive Mesh，PM）技術通過記錄迭代TIN的化簡過程形成化簡模型和增量數據的形式，通過化簡的逆向過程逐步恢復網格，實現網格的漸進傳輸［74］。Pajarola等進一步提出了壓縮漸進網格算法，在傳輸之前對數據進行壓縮［75，76］;Southern等結合視點相關傳輸方法進一步提高了漸進傳輸 效 率［77，78］。漸 進 幾 何 壓 縮 （Progressive Geometry Compression，PGC）通過對規則或者半規則網格進行小波變換，并在各個子帶的小波系數間建立零樹結構，進行零樹編碼生成漸進壓縮碼流，在碼流的任意位置截斷，解碼后可以獲得原始模型的一個近似表示［79］。

由以上研究可以看出，三維表面模型的化簡與壓縮的核心是通過某種判別規則從模型中刪除頂點、邊或者三角形等幾何單元，并對刪除后模型進行空洞填補處理，最后通過迭代式的化簡及其逆向過程從而實現模型的漸進傳輸。漸進網格技術確立了三維表面模型漸進傳輸的基本方法，經過多年發展已成為三維數據壓縮與傳輸的經典算法。

3 結論

目前，漸進傳輸已經成為解決海量空間數據與網絡用戶交互、快速響應之間矛盾的基本方法。雖然影像/柵格的漸進傳輸已經得到比較好的解決，但矢量數據的漸進傳輸問題尚未得到真正的解決。通過與三維表面模型漸進傳輸的研究對比，矢量數據漸進傳輸研究需要克服如下問題：

（1）明確矢量地理數據漸進傳輸的目標與定位。當前大量研究將矢量地理數據的漸進傳輸與制圖綜合相聯系，試圖應用制圖綜合的相關技術解決漸進傳輸問題。但制圖綜合的首要目的是生產滿足制圖需求的多比例尺地圖，而矢量地理數據漸進傳輸的首要目標是在保證可視化結果正確的前提下，降低網絡負載，提升用戶的交互操作體驗效果。這兩種技術存在應用需求方面的差異，因此需要針對矢量數據漸進傳輸的目標需求，設計相關算法。

（2）平衡矢量數據化簡算法效率與拓撲關系保持之間的依賴性。矢量地理數據化簡是漸進傳輸的基礎，但是當前無論是多要素制圖綜合還是單要素幾何化簡都在純幾何層次考慮問題，算法需要大量的浮點運算，難以保證效率。僅對單個地理要素進行化簡，難以維持要素間的拓撲關系;但考慮要素間的拓撲關系保持問題，則又勢必極大地增加計算量。新的算法設計關鍵在于確定矢量數據化簡與拓撲關系保持的平衡點，尋找新的控制結構，解除兩者之間的依賴。

（3）設計新型的數據結構，降低數據冗余和存儲的復雜性。當前的相關算法都是基于樹的數據結構，需要指針維護層次關系，還需要額外的存儲空間，無法真正實現無冗余傳輸。同時樹結構與矢量地理數據的關系數據的存儲結構難融合，實際應用困難。因此需要尋找多分辨率之間的插入隱含關系，將增量數據的插入位置隱含在數據流中，實現增量數據的無冗余傳輸。

［1］BUTTENFIELD B P.Transmitting vector geospatial data across the Internet［EB/OL］.Proceeding GIScience′02.http：//www.springerlink.com/content/4kgffqdnmk962brv/fulltext.pdf.2011－09－27.

［2］BERTOLOTTO M，EGENHOFER M J.Progressive vector transmission［EB/OL］.7th ACM Symposium on Advances in Geographic Information Systems，1999.http：//delivery.acm.org/10.1145/330000/320172/p152-bertolotto.pdf ip＝137.189.162.186＆CFID＝44877011＆CFTOKEN＝80335071＆＿＿acm＿＿＝1317107472＿fcb8f0aa11cfa6c579111a684300ad9e.2011－09－27.

［3］BERTOLOTTO M，EGENHOFER M J.Progressive transmission of vector map data over the World Wide Web［J］.GeoInformatica，2001，5（5）：345－373.

［4］BERTOLOTTO M.Geometric Modeling of Spatial Entities at Multiple Levels of Resolution［D］.University of Genova，1998.

［5］楊必勝，李清泉.World Wide Web（WWW）上矢量地圖數據的多分辨率傳輸算法［J］.測繪學報，2005，34（4）：355－360.

［6］VISVALINGAM M，WHYATT J D.Line generalization by repeated elimination of points［J］.Cartographic，1993，30（1）：46－51.

［7］AI T H，LI Z L，LIU Y L.Progressive transmission of vector data based on changes accumulation model developments［EB/OL］.11th International Symposium on Spatial Data Handling 2005.http：//www.springerlink.com/content/u371gh8w85865mkm/fulltext.pdf.2011－09－27.

［8］CECCONI A，WEIBEL R.Map generalization for on-demand web mapping［EB/OL］.GIScience 2000.http：//citeseerx.ist.psu.edu/viewdoc/download;jsessionid＝ 85FD7EF9788A744D815 CFCE6A21BD8A7？doi＝10.1.1.90.9161＆rep＝rep1＆type＝pdf.2011－09－27.

［9］DAVID C C，MARIO M T，ANSELMO C，et al.Aservice-oriented architecture for progressive transmission of maps［EB/OL］.IX Brazilian Symposium on GeoInformatics.http：//www.geoinfo.info/geoinfo2007/papers/S5P2.pdf.2011－09－27.

［10］DOUGLAS D H，PEUKER T K.Algorithms for the reduction of the number of points required to represent aline or its caricature［J］.The Canadian Cartographer，1973，10（2）：112－122.

［11］VISVALINGAM M，WHYATT J D.Line generalization by repeated elimination of points［J］.Cartographic Journal，2003，30（1）：46－51.

［12］WANG Z，MULLER J C.Line generalization based on analysis of shape characteristics［J］.Cartography and Geographic Information Science，1998，25（1）：3－15.

［13］YANG B S，PURVES R S，WEIBEL R.Implementation of progressive transmission algorithms for vector map data in webbased visualization［A］.Proceedings XXth ISPRS Congress，Commission IV，2001.25－31.

［14］YANG B S.A multi-resolution model of vector map data for rapid transmission over the internet［J］.Computers ＆ Geosciences，2005，31（5）：569－578.

［15］YANG B S，PURVES R S，WEIBEL R.Efficient transmission of vector data over the internet［J］.International Journal of Geographical Information Science，2007，21（2）：215－237.

［16］任應超，李文雯，楊崇俊.一種用于漸進傳輸的多分辨率曲線模型［J］.計算機工程，2008，34（8）：25－28.

［17］LI Z L，OPENSHAW S.Linear feature′s self-adapted generalization algorithm based on impersonality generalized natural law［J］.Translation of Wuhan Technical University of Surveying and Mapping，1994（1）：49－58.

［18］朱鯤鵬，武芳，王輝連.Li-Openshaw算法的改進與評價［J］.測繪學報，2007，36（4）：450－456.

［19］SAUX E.B-spline functions and wavelets for cartographic line generalization［J］.Cartography and Geographic Information Science，2003，30（1）：33－50.

［20］吳凡.基于小波分析的線狀特征數據無級表達［J］.武漢大學學報（信息科學版），2004，29（6）：488－491.

［21］WANG Y H，ZHU C Q.The vector relief data compression based on the mulit-band wavelet［J］.Science of Surveying and Mapping，2003，28（3）：66－68.

［22］朱長青，王玉海，李清泉，等.基于小波分析的等高線數據壓縮模型［J］.中國圖象圖形學報（A輯），2004，9（7）：841－845.

［23］王玉海，朱長青.基于小波分析的線狀要素壓縮優化的綜合性研究［J］.武漢大學學報（信息科學版），2007，32（7）：630－632.

［24］GUO Q S.A progressive line simplification algorithm［J］.Wuhan Technical University of Surveying and Mapping，1998（1）：52－56.

［25］艾廷華，郭仁忠，劉耀林.曲線彎曲深度層次結構的二叉樹表達［J］.測繪學報，2001，30（4）：343－348.

［26］王橋，吳紀桃.制圖綜合方根規律模型的分形擴展［J］.測繪學報，1996，25（2）：104－109.

［27］王橋，吳紀桃.一種新分維估值方法作為工具的自動制圖綜合［J］.測繪學報，1996，25（1）：10－16.

［28］POORTEN V D，JONES C B.Customisable line generalization using Delauney triangulation［EB/OL］.Proceedings of the 19th ICA conference in Ottawa，1999.http：//www.comp.glam.ac.uk/pages/staff/pmvander/.2011－09－27.

［29］杜維，艾廷華，徐崢.一種組合優化的多邊形化簡方法［J］.武漢大學學報（信息科學版），2004，29（6）：548－550.

［30］DUTTON G，BUTTENFIELD B P.Scale change via hierarchical coarsening：Cartographic properties of quaternary triangular meshes［A］.Proc.16th Int.Cartographic Conference［C］.1993.847－862.

［31］DUTTON G.Digital map generalization using a hierarchical coordinate system［A］.Proc.Auto Carto 13.（Seattle，WA）Bethesda，MD：ACSM/ASPRS，1997.367－376.

［32］DUTTON G.Scale，sinuosity and point selection in digital line generalization［J］.Cartography and Geographic Information Science，1999，26（1）：33－53.

［33］WANG P T，DOIHARA T，LU W.Spatial generalization：An adaptive lattice model based on spatial resolution［EB/OL］.Symposium on Geospatial Theory，Processing and Applications，2002.http：//www.isprs.org/proceedings/XXXIV/part4/pdfpapers/291.pdf.2011－09－27.

［34］WANG P T，DOIHARA T，LU W，et al.A resolution-driven generalization approach for linear and areal object［EB/OL］.Geoscience and Remote Sensing Symposium.http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp＝＆arnumber＝1294431.2011－09－27.

［35］DOIHARA T，WANG P T，LU W.An adaptive lattice model and its applications to map simplification［EB/OL］.Symposium on Geospatial Theory，Processing and Applications，2002.http：//www.isprs.org/proceedings/XXXIV/part4/pdfpapers/301.pdf.2011－09－27.

［36］OOSTEROM P V.The reactive-tree：A storage structure for a seamless，scaleless geographic database［A］.Auto-Carto 10［C］.1991.393－407.

［37］OOSTEROM P V.A storage structure for a multi-scale database：The reactive-tree［J］.Computers，Environment and Urban Systems，1992，16（3）：239－247.

［38］OOSTEROM P V.Reactive Data Structure for Geographic In-formation Systems［M］.Oxford University Press，1994.

［39］李愛勤.無縫空間數據組織及其多比例尺表達與處理研究［D］.武漢大學，2001.

［40］OOSTEROM P V.The GAP-tree，an approach to on-the-fly map generalization of an area partitioning［A］.MULLER J C，LAGRANGE J P，WEIBEL R.GIS and Generalization：Methodology and Practice［C］.Taylor ＆ Francis，London，1995.120－133.

［41］田鵬，鄭扣根，張引，等.基于C-Tree的無級比例尺GIS多邊形綜合技術［J］.中國圖象圖形學報（A輯），2001，6（8）：765－770.

［42］BALLARD D H.Strip trees：A hierarchical representation for curves［J］.ACM Communications.1981，24（5）：310－321.

［43］OOSTEROM P V.A reactive data structure for geographic information systems［EB/OL］.Auto-Carto 9，1989.http：//www.mapcontext.com/autocarto/proceedings/auto-carto-9/pdf/a-reactive-data-structure-for-geographic-information-systems.pdf.2011－09－27.

［44］OOSTEROM P V.Reactive Data Structures for Geographic Information Systems［D］.Leiden University，1990.

［45］JONES C B，ABRAHAM I M.Line generalization in a global cartographic database［J］.Cartographica，1987，24（3）：32－45.

［46］毋河海.基于多叉樹結構的曲線綜合算法［J］.武漢大學學報（信息科學版），2004，29（6）：479－483.

［47］任應超，李文雯，楊崇俊.一種用于漸進傳輸的多分辨率曲線模型［J］.計算機工程，2008，34（8）：25－28.

［48］SCHROEDER W J，ZARGE J A，LORENSEN W E.Decimation of triangulation meshes［J］.Computer Graphics，1992，26（2）：65－70.

［49］SCHROEDER W J.A topology modifying progressive decimation algorithm［A］.Proceedings of Visualization′97［C］，IEEE Computer Society Press，1997.

［50］TURK G.Retiling polygonal surface［J］.Computer Graphics，1992，26（2）：55－64.

［51］ROSSIGUAC J，BORREL P.Multi-resolution 3D approximation for rendering complex scenes［A］.FALCIDIENO B，KUNII T.Geometric Modeling in Computer Graphics［C］.1993.455－465.

［52］LUEBKE D.Hierarchical structures for dynamic polygonal simplification［A］.SIGGRAPH′96［C］.1996.96－106.

［53］LUEBKE D，ERIKSON C.View-dependent simplification of arbitrary polygonal environments［A］.ACM Computer Graphics，31（Proc.of SIGGRAPH′97）［C］.1997.199－208.

［54］LOW K L，TAN T S.Model simplification using vertex-clustering［A］.COHEN M.Proceedings of 1997 Symposium on Interactive 3D Graphics［C］.1997.75－82.

［55］KALVIN A D，TAYLOR R H.Superfaces：Polyhedral approximation with bounded error［A］.Medical Imaging：Image Capture，Formatting and display，SPIE［C］.1994，2164：2－13.

［56］KALVIN A D，TAYLOR R H.Superfaces：Polyhedral mesh simplification with bounded error［J］.IEEECG＆A，1996，16（3）：64－77.

［57］HOPPE H，DEROSE T，DUCHAMP T，et a1.Mesh optimization［J］.Computer Graphics，1993，27（SIGGRAPH′93）：19－26.

［58］RONFARD R，ROSSIGNAC J.Full-range approximation of triangulated polyhedral［A］.Proceedings of EUROGRAPH′96［C］.1996.67－76.

［59］GARLAND M，HECKBERT P S.Surface simplification using quadric error metrics［A］.SIGGRAPH′97［C］.1997.209－216.

［60］LINDSTROM P，TURK G.Fast and memory efficient polygo-nal simplification［A］.ROBERT M.Proceedings of IEEE Visualization′98［C］.1998.279－286.

［61］陶志良，潘志庚.復雜場景中動態簡化層次的構造［J］.中國圖象圖形學報（A輯），1998，3（12）：1032－1036.

［62］盛業華，王永波，閭國年，等.一種基于邊收縮的3維表面模型數據壓縮算法［J］.中國圖象圖形學報，2007，12（1）：159－163.

［63］HAMANN B.A data reduction scheme for triangulated surface［J］.Computer Aided Geometric Design，1994，11（3）：197－214.

［64］ISLER V，LAU W H，GREEN M.Real-time multi-resolution modeling for complex virtual environments［EB/OL］.Proceedings of Virtual Reality Software and Technology′96.http：//www.cs.cityu.edu.hk/～rynson/papers/vrst96.pdf.2011－09－27.

［65］周昆，潘志庚，石教英.基于三角形折疊的網格簡化算法［J］.計算機學報，1998，21（6）：506－513.

［66］LOUNSBERY M.Multiresolution Analysis for Surfaces of Arbitrary Topological Type［D］.University of Washington，1994.

［67］LOUNSBERY M，DEROSE T D，WARREN J.Multiresolution analysis for surfaces of arbitrary topological type［J］.ACM Trans.on Graphics，1997，16（1）：34－73.

［68］ECK M，DEROSE T，DUCHAMP T，et a1.Multiresolution analysis of arbitrary meshes［A］.ACM Computer Graphics（Proc.of SIGGRAPH′95）［C］.1995.173－182.

［69］GROSS M H，GATTI R，STAADT O.Fast multiresolution surface meshing［A］.NIELSON G M，SILVER D.IEEE Visualization′95 Proceedings，1995.135－142.

［70］LINDSTROM P，KOLLER D，RIBARSKY W，et a1.Real-time，continuous level of detail rendering of height fields［A］.Proc.SIGGRAPH′96［C］.1996.109－118.

［71］LINDSTROM P，PASCUCCI V.Visualization of large terrains made easy［A］.Proc.IEEE Visualization 2001［C］.2001.363－370.

［72］DUCHAINEAU M，WOLINSKY M，SIGETI D E，et a1.Roaming terrain：Real-time optimally adapting meshes［A］.Proc.IEEE Visualization′97［C］.1997.81－88.

［73］WANG Y B，SHENG Y H，ZHANG K，et a1.Efficient implementation of adaptive view-dependent mesh simplification［A］.Proceeding of SPIE，Geoinformatics′2007.Cartographic Theory and Models［C］.2007，16751：1－13.

［74］HOPPE H.Progressive meshes［A］.Proceedings of SIGGRAPH′96［C］.1996.99－108.

［75］PAJAROLA R，ROSSIGNAC J.Compressed progressive mesh［J］.IEEE Transactions on Visualization and Computer Graphics，2000，6（1）：79－93.

［76］ALLIEA P，DESBRUN M.Progressive compression for lossless transmission of triangle meshes［A］.Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques［C］.2001.195－202.

［77］SOUTHERN R，PERKINS S，BARRY S，et a1.A stateless client for progressive view-dependent transmission［A］.Proceedings of the Sixth International Conference on 3D Web Technology［C］.2001.43－50.

［78］KIM J，LEE S，KOBBELT L.View-dependent streaming of progressive meshes［A］.Proceedings of the Shape Modeling International 2004［C］.2004.209－220.

［79］KHODAKOVSKY A，SCHRODER P，SWELDENS W.Progressive geometry compression［A］.Computer Graphics Proceeding，Annual Conference Series，ACM SIGGRAPH［C］.2000.85－94.

An Overview on Progressive Transmission of Vector Spatial Data

WEN Yong－ning1，2，LV Guo－nian1，CHEN Min3
（1.KeyLaboratoryofVirtualGeographicEnvironment（MinistryofEducation），NanjingNormalUniversity，Nanjing210046;2.SuzhouIndustrialParkSurveyCO.LTD，Suzhou215021;3.InstituteofSpaceandEarth InformationScience，TheChineseUniversityofHongKong，ShatinH.K.，China）

The progressive transmission strategy is considered to be an effective way to balance contradiction between scheduling the massive spatial data and the real time user experience.Research on the progressive transmission of raster data is fairly sophisticated and mature，while various problems of the theory and technology of vector data′s progressive transmission are still required to be tackled.Aiming at promoting the research of vector data′s progressive transmission，and providing references for research of the distributed network transmission of massive spatial data，this paper focuses on leveraging and summarizing the complementary past and ongoing research of the multi-resolution expression and the progressive transmission of 2D vector data and 3D surface model data which is closely related to the progressive transmission of vector data.

spatial data;vector data;progressive transmission

P208

A

1672－0504（2011）06－0006－07

2011－07- 28;

2011－10－27

國家“863”重點課題子課題項目“基于廣域網的虛擬月球環境構建研究”（2010AA122202）;國家自然科學基金項目“像素無損的矢量地理數據高效傳輸機制研究”（41001223）;江蘇高校優勢學科建設工程資助項目

溫永寧（1977－），男，博士，講師，主要研究方向為虛擬地理環境、3D GIS。E－mail：wenyn＠msn.com