數(shù)字線劃圖的冗余點檢查方法比較研究

易俊華，許泉立

(1.昆明冶金高等?？茖W校測繪學院，云南 昆明 650033；2.云南師范大學地理學部，云南 昆明 650500)

0 引 言

數(shù)字線劃圖(Digital Line Graphic，DLG)，是運用矢量數(shù)據(jù)采集手段分層提取各地表要素并編輯、保存到計算機的矢量數(shù)據(jù)集[1-2].它保存了地理空間要素的空間關系信息和相關屬性信息，是GIS數(shù)據(jù)生產(chǎn)過程中最重要的矢量數(shù)據(jù)形式之一。數(shù)字線劃圖數(shù)據(jù)質(zhì)量的優(yōu)劣直接影響到GIS系統(tǒng)的運行和使用效率。但數(shù)字線劃圖的生產(chǎn)過程不可避免地會產(chǎn)生大量冗余數(shù)據(jù)，如空置圖層、重復屬性信息、線冗余點等。其中線劃冗余點是造成數(shù)據(jù)量大，傳輸和處理效率低的關鍵問題。

冗余數(shù)據(jù)一方面來源于數(shù)據(jù)采集過程，另一方面來源于數(shù)據(jù)的處理和應用過程[3-4]。很多學者或研究機構(gòu)針對數(shù)字線劃圖的冗余點問題進行了大量研究，無論是檢測算法還是檢查系統(tǒng)都取得了一些成果。比如：1971年，美國開發(fā)了具有地圖數(shù)據(jù)拓撲一致性及完整性檢測功能的獨立地圖編碼系統(tǒng)[5]，1973年，Douglas D等[6]提出經(jīng)典的道格拉斯-普克算法；1996年，烏迪內(nèi)大學開發(fā)了“GIS數(shù)據(jù)質(zhì)量控制軟件”[3，5]。相對于國外，我國對空間數(shù)據(jù)質(zhì)量檢查的研究相對較晚，但研究成果積累較快：2001年，解放軍信息工程大學研制了“航測數(shù)字化矢量數(shù)據(jù)檢查驗收系統(tǒng)”[5]；2004年，陜西測繪局開發(fā)了一款集4D功能于一個系統(tǒng)內(nèi)的數(shù)據(jù)質(zhì)量檢查軟件——“4D-Checker”[3]，該軟件檢查功能全面，但對硬件設備要求較高，檢查效率低；2007年，國家測繪產(chǎn)品質(zhì)檢中心研制了基于ArcEngine 9.2開發(fā)平臺的l∶5萬DLG質(zhì)量檢查系統(tǒng)[5]；2010年，浙大萬維科技有限公司開發(fā)了名為“Walk Check”的質(zhì)檢軟件；北京吉威時代軟件股份有限公司開發(fā)的針對3D數(shù)據(jù)的質(zhì)量檢查軟件，以工程項目作為驅(qū)動，可以自定義和組合檢查規(guī)則；2012年，龍勝春[7]提出基于面積閾值的曲線矢量數(shù)據(jù)壓縮方法；2014年，王飛提出了一種以累積偏移量為主要內(nèi)容的矢量數(shù)據(jù)實時壓縮算法。

綜上可述，冗余點檢測在理論上已有相對成熟的算法，各空間數(shù)據(jù)質(zhì)量檢查軟件中對冗余點檢測功能也進行了集成和封裝。但這些檢查軟件，特別是一些大型的質(zhì)量檢查軟件由于檢查功能多、檢查內(nèi)容豐富、檢查項設置復雜，對單一檢查項目設置不夠深，檢查算法不可見，導致對冗余點檢測的針對性不強、檢測方法不可選、靈活性不高，檢測結(jié)果不直觀等問題，從而降低了冗余點檢查效率。

因此，針對數(shù)字線劃圖冗余點檢測問題，本文選擇了間隔取點法、垂距法、角度限值法、道格拉斯—普克算法4種方法進行分析與對比，最終選取了垂距法和角度限值法，采用ArcEngine組件開發(fā)技術，設計并實現(xiàn)了針對數(shù)字線劃圖冗余點交互式檢查軟件；并通過運行軟件對實驗數(shù)據(jù)進行檢測，對比分析檢測結(jié)果，進而對上述算法的有效性和適用性進行檢驗與評價，研究出各檢測方法適宜的數(shù)據(jù)種類。

1 冗余點檢查算法比較

1.1 冗余點概念與檢查原則

在數(shù)字線劃圖生產(chǎn)過程中，由于線狀要素及面狀要素邊界常會出現(xiàn)線段上節(jié)點過多的情況，從而造成數(shù)據(jù)冗余，給地圖分析、地圖數(shù)據(jù)存儲和地圖數(shù)據(jù)傳輸使用造成了一定的困難，因此需要對冗余點進行檢查并刪除。數(shù)字線劃圖冗余點檢查在數(shù)據(jù)分析、處理、存儲、應用以及網(wǎng)絡傳輸?shù)确矫娑挤浅Ｖ匾?。根?jù)空間數(shù)據(jù)質(zhì)量檢查規(guī)范，冗余點檢查的原則是：在保留線狀要素必要特征點的前提下，對線狀要素進行冗余點檢測，所檢測到的冗余點應盡可能多，且對冗余點刪除后不改變圖形形狀特征。

1.2 冗余點檢查方法介紹

目前，冗余點檢查方法主要有：間隔取點法、垂距法、角度限制法、道格拉斯—普克法。

1)間隔取點法：間隔取點法是4種方法中操作最簡單的方法[8,16]?；舅枷胧牵簭木€段的起點開始，每隔n個點取1點為特征點保留，或每隔一段規(guī)定的距離取1點為特征點保留，但首末點必須保留，沒有被保留的點即為冗余點。

2)垂距法：垂距法檢查冗余點的原理如圖1所示，基本思想是：從一條線的起始節(jié)點開始，每次順序取線段上的3個節(jié)點，計算中間點與其前后相鄰兩點連線的垂直距離d，用d與預先設定的閾值D比較。若d

圖1 垂距法示意Fig.1 The explanation of vertical distance method

3)角度限值法：角度限值法的原理如圖2所示，基本思路是：首先設定一個角度閾值D，對于每一條線上的所有中間點，將其與前一點連接，再將其前后2點連接，然后通過判斷這2條線的夾角與閾值的大小關系判斷該中間點是否為冗余點。具體計算步驟：①連接點A、B與A、C，計算線段AB與線段AC的夾角，記為θ1，若θ1>D，則將點B保留；②連接點B、C與B、D，計算線段BC與線段BD的夾角，記為θ2，若θ2

4)道格拉斯—普克法：該方法是Douglas等[6,9-12]1973年提出的。其算法原理如圖3所示，基本思路是：將每一條曲線的首尾點虛連一條直線，計算其余點到該直線的垂直距離d。選出最大距離與規(guī)定的閾值D相比較，若小于閾值,則直線兩端點間所有點都為冗余點。否則保留最大距離對應的節(jié)點，并以該點為界，將曲線分成兩部分。重復以上過程，直至處理結(jié)束。

圖2 角度限制法示意 圖3 道格拉斯—普克算法原理Fig.2 The explanation of angle limitation method Fig.3 The explanation of Douglas-Peucker algorithm

1.3 檢查方法分析與選擇

圖4 冗余點檢查算法設計流程Fig.4 The flow of algorithm designing for redundancy point checking

下面對4種冗余點檢查方法進行分析與比較。

間隔取點法計算工作量小，可以檢查出大量的冗余點，但刪除這些冗余點后，曲線的形狀特征很大程度上會被破壞。垂距法與角度限值法原理相似，不同之處在于垂距法以垂直距離作為判斷依據(jù)，而角度限值法以角度作為判斷依據(jù)。2種方法都有易于實現(xiàn)、檢查速度快等優(yōu)點，但刪除冗余點后，曲線的形狀特征應與設置的閾值有關。道格拉斯—普克法是一個整體算法，通?？杀Ａ魪澢潭容^大的曲線上的特征點[13-16]。但局限性在于：1)在線狀目標起點不確定的情況下，用該方法檢查出的結(jié)果可能不一樣；2)在處理2個對象的公共邊時，可能會改變原始線狀目標之間的拓撲關系；3)算法比垂距法復雜，計算量較大，編程實現(xiàn)有一定難度。

基于上述方法的對比分析，本文最終選取垂距法與角度限值法進行基于ArcEngine的數(shù)字線劃圖冗余點算法設計和實現(xiàn)。

2 數(shù)字線劃圖冗余點檢查算法實現(xiàn)過程

2.1 算法流程圖(圖4)2.2 基于ArcEngine的算法實現(xiàn)

2.2.1 開發(fā)方法

本算法基于ArcEngine 10.0和Visual Studio2010開發(fā)平臺，使用C#語言進行設計。ArcEngine包含一系列GIS組件，提供多種開發(fā)接口，可用來構(gòu)建各種GIS應用程序。ArcEngine能實現(xiàn)的功能報告：

1)地理數(shù)據(jù)加載、地圖顯示、地圖編輯和地圖輸出功能；

2)地圖空間查詢與空間分析功能；

3)專題地圖制作等功能。

C#語言是Visual Studio.NET開發(fā)環(huán)境下多種常用編程語言之一，.NET環(huán)境為開發(fā)者提供了一個強大且方便的工具箱，包括所有窗體控件、通用控件、容器類控件、菜單和工具條控件、對話框控件和常用控件等基礎控件。本算法的設計需要在窗體界面中添加的控件有：License Control，Map Control，Toolbar Control，TOCControl，dataGridView等控件?？丶f明如下。

1)License Control：它能夠保證開發(fā)的產(chǎn)品在其他平臺上正常運行，是所有基于ArcEngine開發(fā)的軟件必須添加的控件。

2)Map Control：提供一種數(shù)據(jù)可視化窗口，通過此控件可以完成地圖顯示、地圖縮放、地圖空間查詢、地圖要素選擇等功能。

3)Toolbar Control：此控件包含了各種能實現(xiàn)地圖基本操作的命令工具，可以根據(jù)系統(tǒng)設計需要，從此控件添加所需工具條目。

4)TOCControl：主要負責對各地圖圖層的管理和操作，通常與Map Control控件關聯(lián)在一起。

5)dataGridView：提供一種可自定義屬性的表格，可將不同類型的數(shù)據(jù)添加到此表格顯示并對其編輯。

2.2.2 程序界面設計

設計了數(shù)據(jù)加載、數(shù)據(jù)保存、全圖顯示、地圖平移、地圖縮放、地圖要素選擇等常用操作功能，界面如圖5所示。

圖5 冗余點檢查軟件主界面Fig.5 The main interface of redundancy point checking software

3 試驗結(jié)果與對比分析

3.1 2種方法檢查的冗余點位置比較

使用同一數(shù)據(jù)進行試驗，分別對2種方法設置依次遞增的閾值，篩選冗余點數(shù)量相近或相同的檢查結(jié)果，試驗結(jié)果如圖6所示，圖中圓圈標注的位置表示2種方法都同時檢測到的冗余點。

通過分析2種方法檢查結(jié)果發(fā)現(xiàn)：當檢查結(jié)果中的冗余點數(shù)量相近或相同時，2種算法對應的冗余點位置分布有一定的差異。從檢查結(jié)果圖中可以看到，2種方法檢查得到的冗余點大部分為共同點。通過整體對比發(fā)現(xiàn)：角度限值法檢查出的冗余點在位置上比垂距法分布廣；用垂距法能檢查到的大部分冗余點位置，用角度限值法也同樣能檢查到。通過局部對比發(fā)現(xiàn)：在曲率變化較大且長度較長的線條上，角度限值法檢查到的冗余點比垂距法的多；在較平緩的線條上，垂距法檢查到的冗余點比角度限值法的多。因此，可以得出這樣的結(jié)論：垂距法對較平緩的線條檢查效果更好，而角度限值法對長度較長且彎曲程度較大的線條檢查效果更好。

(a) 基于垂距法檢查出6個冗余點 (b)基于角度限值法檢查出5個冗余點 (c) 基于垂距法檢查出17個冗余點 (d) 基于角度限值法檢查出17個冗余點

(e) 基于垂距法檢查出28個冗余點 (f) 基于角度限值法檢查出27個冗余點 (g) 基于垂距法檢查出45個冗余點 (h) 基于角度限值法檢查出45個冗余點圖6 基于2種不同檢查方法檢測到的冗余點位置分布Fig.6 The locations distribution of redundant points detected by two different checking methods

3.2 2種方法檢查的冗余點數(shù)量比較

使用同一實驗數(shù)據(jù)，分別對垂距法和角度限值法設置從小依次遞增的閾值，依次進行冗余點檢查，并記錄冗余點數(shù)量。檢查完成后，分別對2種方法的檢查結(jié)果(冗余點數(shù)量)進行統(tǒng)計，統(tǒng)計結(jié)果見表1、2。

表1 利用垂距法檢測的冗余點數(shù)量統(tǒng)計Tab.1 The statistics of the number of redundant points detected by vertical distance method

表2 利用角度限值法檢測的冗余點數(shù)量統(tǒng)計Tab.2 The statistics of the number of redundant points detected by angle limitation method

通過統(tǒng)計分析2種方法的檢查結(jié)果發(fā)現(xiàn)：當輸入的閾值較小時，冗余點的數(shù)量都較少；當閾值在某個值范圍內(nèi)遞增時，冗余點數(shù)量隨閾值遞增的速度較緩慢。本實驗中，使用垂距法，當閾值<0.01 m 時，冗余點的數(shù)量在20以內(nèi)緩慢增加；使用角度限值法，當閾值<0.1° 時，冗余點的數(shù)量同樣在20以內(nèi)緩慢增加。在一定的閾值范圍內(nèi)，冗余點的數(shù)量都保持在合理區(qū)間內(nèi)。當閾值超過質(zhì)量要求的極大值時，檢查結(jié)果對數(shù)字線劃圖圖形特征影響較大，此時檢查結(jié)果無實用意義。對本實驗數(shù)據(jù)而言，垂距法閾值不應>0.02 m；角度限值法閾值不應>0.5°。

4 結(jié)論與討論

4.1 結(jié) 論

本文主要對數(shù)字線劃圖中冗余點檢查問題進行了研究，介紹了4種矢量數(shù)據(jù)冗余點檢查方法，并進行了分析。在垂距法和角度限值法的理論指導下，基于ArcEngine組件GIS庫和Visual Studio 2010開發(fā)平臺，實現(xiàn)了數(shù)字線劃圖冗余點檢查算法，完成了2種方法對某區(qū)域?qū)嶒灁?shù)據(jù)檢查結(jié)果的對比分析。通過總結(jié)可得出以下結(jié)論：

1)通過實驗，發(fā)現(xiàn)2種方法設置的閾值對檢查結(jié)果影響很大。

2)對2種檢查方法的檢查結(jié)果分析得出，垂距法對較平緩的線條檢查效果更好，角度限值法對彎曲程度較大且長度較長的線條檢查效果更好。

4.2 討 論

數(shù)字線劃圖冗余點檢查結(jié)果的優(yōu)劣直接影響數(shù)據(jù)質(zhì)量，而檢查方法的選擇則是導致不同檢查結(jié)果的直接原因。因此，對于需進行冗余點檢查的數(shù)字線劃圖，應先對數(shù)據(jù)進行一定評估，針對數(shù)據(jù)特點，選擇最適宜的檢查方法，最大限度地降低數(shù)據(jù)冗余度。同時，對于不同用途的數(shù)字線劃圖，其精度要求也不一致，在冗余點檢查閾值設置時，應根據(jù)數(shù)據(jù)精度要求進行相應設置。當然，針對不同數(shù)字線劃圖精度要求，具體設置怎樣的檢查閾值，這是需要進一步研究的內(nèi)容。最后，針對數(shù)據(jù)冗余點檢查的方法還有很多，本文僅提及了4種，且只對其中2種算法進行了對比分析，更多算法的實驗對比，有待進一步研究。