榮岳成

北京華迪宏圖信息技術(shù)有限公司，北京100195

1 引 言

遙感數(shù)據(jù)是GIS重要的信息源［1］，遙感數(shù)據(jù)專題信息也需要進(jìn)行矢量化表達(dá)［2］，柵格轉(zhuǎn)矢量是遙感和GIS一體化集成的一項(xiàng)關(guān)鍵技術(shù)。近年來，遙感圖像的空間分辨逐漸提高，矢量化對(duì)計(jì)算量和存儲(chǔ)的要求也成倍地增長(zhǎng)［3］，因此，研究適應(yīng)大數(shù)據(jù)量遙感圖像的高效矢量化算法具有非常重要的價(jià)值。

柵格轉(zhuǎn)矢量是GIS研究中的經(jīng)典課題，積累了比較多的方法。如邊緣跟蹤法、散列線段聚合法［4］、有向邊界法［5］、基于柵格技術(shù)的矢量化方法［6］、基于拓?fù)湓淼霓D(zhuǎn)換方法［2，7］、基于游程編碼的追蹤方法［8，9］、雙臂鏈邊界跟蹤法［10］等。此外，學(xué)者們還從拓?fù)湫畔⒆詣?dòng)生成［11］、基于弧－弧的拓?fù)潢P(guān)系判斷［12］等方面對(duì)多邊形拓?fù)潢P(guān)系構(gòu)建算法進(jìn)行了研究。

傳統(tǒng)的矢量化算法在大數(shù)據(jù)遙感圖像矢量化處理中，當(dāng)圖像規(guī)模大且內(nèi)容復(fù)雜時(shí)，內(nèi)存可能無(wú)法儲(chǔ)存所有的邊界點(diǎn)或者需要頻繁地與外存進(jìn)行交互，構(gòu)建多邊形時(shí)，弧段跟蹤耗時(shí)較多，拓?fù)潢P(guān)系判斷復(fù)雜度高，時(shí)間和空間效率低。

與傳統(tǒng)矢量化算法不同，本文從頂點(diǎn)提取與圖斑矢量化同時(shí)進(jìn)行即動(dòng)態(tài)矢量化的角度，來進(jìn)行柵格轉(zhuǎn)換矢量根據(jù)本文提出的方法，在圖斑頂點(diǎn)提取的過程中，檢測(cè)到能構(gòu)成封閉多邊形的圖斑立即將其矢量化，并釋放其所占內(nèi)存，圖斑矢量化時(shí)，直接將頂點(diǎn)構(gòu)建成多邊形，無(wú)須生成中間弧段，并即時(shí)形成拓?fù)潢P(guān)系。

2 矢量化基本概念

遙感中，柵格數(shù)據(jù)的每個(gè)像元（pixel）都表示一定的面積大小，它并不是數(shù)學(xué)意義上的點(diǎn)，因此，柵格數(shù)據(jù)矢量化后的矢量數(shù)據(jù)只有面狀（圖斑）信息，沒有點(diǎn)和線［6］。

在遙感柵格影像矢量化中，有如下約定和定義［2，6］：

定義1 柵格數(shù)據(jù)矢量化時(shí)，只有圖斑信息。

定義2 柵格數(shù)據(jù)中的每個(gè)像元都是有大小的，柵格數(shù)據(jù)矢量化時(shí)，最小圖斑是一個(gè)像元。

定義3 弧段是圖斑與圖斑之間的連續(xù)的邊界分界線，弧段內(nèi)部的點(diǎn)稱為坐標(biāo)點(diǎn)，弧段的端點(diǎn)稱為結(jié)點(diǎn)。

定義4 坐標(biāo)點(diǎn)只有兩個(gè)方向存在邊界，而對(duì)結(jié)點(diǎn)，至少在3個(gè)方向上存在邊界（如圖1）。

定義5 每個(gè)矢量多邊形由一個(gè)外環(huán)和多個(gè)內(nèi)環(huán)組成（或沒有內(nèi)環(huán)），沒有內(nèi)環(huán)的多邊形稱為簡(jiǎn)單多邊形，含有內(nèi)環(huán)的多邊形稱為復(fù)雜多邊形。

圖1 坐標(biāo)點(diǎn)（a）～（e）和結(jié)點(diǎn)（f）～（k）Fig.1 Nodes（a）～（e）and coordinate points（f）～（k）

3 動(dòng)態(tài)矢量化算法

矢量化算法主要分為3部分：①統(tǒng)計(jì)圖像各圖斑頂點(diǎn)個(gè)數(shù)；②提取圖斑頂點(diǎn)，并判斷各圖斑頂點(diǎn)，集合能否構(gòu)成封閉多邊形；③將能構(gòu)成封閉多邊形的圖斑頂點(diǎn)集合矢量化。在矢量化過程中②和③可以同時(shí)進(jìn)行，并且③執(zhí)行后，會(huì)釋放其所占內(nèi)存，因此，本文算法的矢量化過程是動(dòng)態(tài)的。

3.1 圖斑頂點(diǎn)統(tǒng)計(jì)

圖1中（a）～（e）屬于坐標(biāo)點(diǎn)，（f）～（k）屬于結(jié)點(diǎn)，只有坐標(biāo)點(diǎn)或結(jié)點(diǎn)能構(gòu)成圖斑邊界。其中圖1中的第a種坐標(biāo)點(diǎn)屬于冗余坐標(biāo)點(diǎn)，處理中可以剔除該類型坐標(biāo)點(diǎn)。在本文中，坐標(biāo)點(diǎn)和結(jié)點(diǎn)統(tǒng)稱頂點(diǎn)。柵格圖像中的一個(gè)圖斑是一個(gè)四連通區(qū)域，每個(gè)圖斑矢量化后，都對(duì)應(yīng)一個(gè)簡(jiǎn)單多邊形或一個(gè)復(fù)雜多邊形，對(duì)分類圖像中的圖斑進(jìn)行編號(hào)，每個(gè)圖斑將有唯一的編號(hào)。

每個(gè)環(huán)是由一系列首尾重合的頂點(diǎn)構(gòu)成的封閉多邊形。簡(jiǎn)單多邊形對(duì)應(yīng)圖斑的頂點(diǎn)個(gè)數(shù)為外環(huán)的頂點(diǎn)個(gè)數(shù)；復(fù)雜多變形對(duì)應(yīng)的圖斑的頂點(diǎn)個(gè)數(shù)為外環(huán)與所有內(nèi)環(huán)的頂點(diǎn)個(gè)數(shù)之和。在圖2中，圖斑A與C對(duì)應(yīng)簡(jiǎn)單多邊形，頂點(diǎn)個(gè)數(shù)均為4，圖斑B對(duì)應(yīng)復(fù)雜多邊形，頂點(diǎn)個(gè)數(shù)為10。

每個(gè)頂點(diǎn)的類型，由相鄰的4個(gè)像元決定，因此在對(duì)圖像進(jìn)行掃描時(shí)，不需要將整幅圖像讀入內(nèi)存，處理一行數(shù)據(jù)只需將相鄰兩行讀入內(nèi)存，依次判斷每個(gè)頂點(diǎn)類型，并將相應(yīng)的圖斑頂點(diǎn)個(gè)數(shù)計(jì)數(shù)器更新，處理完之后，下移一行。

圖2 圖斑頂點(diǎn)個(gè)數(shù)統(tǒng)計(jì)Fig.2 Statistics of vertices in polygon

3.2 圖斑頂點(diǎn)提取

圖斑頂點(diǎn)提取的流程與圖斑頂點(diǎn)個(gè)數(shù)統(tǒng)計(jì)的流程類似，每次讀入兩行柵格數(shù)據(jù)到內(nèi)存，從左至右逐點(diǎn)進(jìn)行處理，處理中，需要記錄每個(gè)頂點(diǎn)與其周圍4個(gè)像元的鄰接關(guān)系。

對(duì)于每個(gè)頂點(diǎn)，本文采用如下的結(jié)構(gòu)體表示其信息［2］。

其中，x、y為該點(diǎn)的行列坐標(biāo)；類型type＝2，3，…，11，對(duì)應(yīng)于上面的結(jié)點(diǎn)和坐標(biāo)點(diǎn)情況，表明該矢量點(diǎn)的類型；adj［4］分別記錄該點(diǎn)0、1、2、3這4個(gè)方向上（依次對(duì)應(yīng)為右、上、左、下）的連接信息。

在頂點(diǎn)提取的過程中，每個(gè)圖斑的頂點(diǎn)用一個(gè)動(dòng)態(tài)容器來存儲(chǔ)，頂點(diǎn)提取算法如下：

（1）從圖像中取出一個(gè)未處理的點(diǎn)，判斷該點(diǎn)的類型，如果是頂點(diǎn)，執(zhí)行（2），否則繼續(xù)執(zhí)行（1）；

（2）記錄該點(diǎn)的x與y方向坐標(biāo)及點(diǎn)類型，如果adj［4］某方向上有邊界，則將其對(duì)應(yīng)元素置為1，否則置為－1，根據(jù)頂點(diǎn)周圍相鄰4個(gè)像元的對(duì)應(yīng)的圖斑編號(hào)，將該頂點(diǎn)插入到包含該點(diǎn)的圖斑的多邊形頂點(diǎn)容器中；

（3）檢測(cè)新插入頂點(diǎn)的圖斑多邊形頂點(diǎn)容器當(dāng)前頂點(diǎn)數(shù)是否等于圖斑實(shí)際的頂點(diǎn)數(shù)，如果相等，則將該圖斑多邊形頂點(diǎn)容器（集合）進(jìn)行矢量化，并釋放其所占內(nèi)存；

（4）判斷所有點(diǎn)是否都已經(jīng)被處理完成，如果是，則算法結(jié)束，否則繼續(xù)執(zhí)行（1）。

從上述算法可以看出，在頂點(diǎn)提取的過程中，完成了圖斑矢量化，并且內(nèi)存中只駐留了已經(jīng)被掃描且尚未完成掃描的圖斑頂點(diǎn)，已經(jīng)完成掃描和未開始掃描的圖斑頂點(diǎn)不會(huì)被存儲(chǔ)，這樣大大降低了存儲(chǔ)頂點(diǎn)的內(nèi)存消耗，有利于提高算法的空間效率。

3.3 圖斑頂點(diǎn)矢量化

圖斑頂點(diǎn)矢量化首先進(jìn)行封閉弧段跟蹤，然后對(duì)封閉弧段進(jìn)行拓?fù)潢P(guān)系判斷。在封閉弧段跟蹤開始前，先通過對(duì)圖斑頂點(diǎn)容器內(nèi)所有頂點(diǎn)進(jìn)行一次掃描，在adj［4］中記錄每個(gè)頂點(diǎn)上、下、左、右4個(gè)方向上與其他頂點(diǎn)的連接信息［2］。封閉弧段的跟蹤可以從任意一個(gè)頂點(diǎn)開始，其跟蹤算法如下：

從圖斑頂點(diǎn)容器中選擇一個(gè)未被跟蹤過的頂點(diǎn)，對(duì)該頂點(diǎn)按0、1、2、3方向進(jìn)行遍歷，找出第一個(gè)具有連接點(diǎn)的方向，不妨設(shè)此方向?yàn)閗，adj［k］中的數(shù)值就是下一個(gè)頂點(diǎn)的序號(hào)，根據(jù)跟蹤到的該頂點(diǎn)的連接信息進(jìn)而可以跟蹤得到另一個(gè)新的頂點(diǎn)，如此下去，直到回到初始出發(fā)頂點(diǎn)為止，形成一個(gè)封閉多邊形。一個(gè)封閉多邊形跟蹤完畢后，應(yīng)該將其上所有頂點(diǎn)的跟蹤標(biāo)志設(shè)置為已跟蹤標(biāo)志，防止被重復(fù)跟蹤。一個(gè)圖斑一般會(huì)包含若干個(gè)封閉多邊形，因此，上述跟蹤步驟應(yīng)重復(fù)進(jìn)行，直到所有頂點(diǎn)都已被跟蹤過為止。

本文算法的多邊形拓?fù)潢P(guān)系判斷簡(jiǎn)單高效，能以線性時(shí)間復(fù)雜度完成。由于每個(gè)圖斑頂點(diǎn)容器中的頂點(diǎn)都屬于同一個(gè)圖斑，因此矢量化后的封閉多邊形也必然屬于同一個(gè)矢量多邊形，這樣拓?fù)潢P(guān)系判斷只需找出最外層的封閉多邊形，其余封閉多邊形均會(huì)被該多邊形包含。最外層多邊形的搜索算法如下：比較每個(gè)封閉多邊形最小外接矩形左上角頂點(diǎn)x方向坐標(biāo)值，最小坐標(biāo)值對(duì)應(yīng)的那個(gè)封閉多邊形即為最外層多邊形。

由于最小外接矩形可以在封閉弧段跟蹤過程中計(jì)算得出，因此，矢量多邊形拓?fù)潢P(guān)系判斷以線性時(shí)間復(fù)雜度完成。

4 動(dòng)態(tài)矢量化算法分析

為了便于后面的討論，先對(duì)符號(hào)進(jìn)行約定。設(shè)N和M分別為分類圖像的高與寬；矢量化文件共有K個(gè)頂點(diǎn)：v1，v2，…，vK，頂點(diǎn)集合V＝｛v1，v2，…，vK｝；矢量文件共有n個(gè)封閉弧段，每個(gè)封閉弧段對(duì)應(yīng)的頂點(diǎn)個(gè)數(shù)分別為：k1，k2，…，kn；矢量化文件共有m個(gè)拓?fù)涠噙呅危簊1，s2，…，sm組成，拓?fù)涠噙呅渭蟂＝｛s1，s2，…，sm｝；ysmin與ysmax分別表示多邊形s所有頂點(diǎn)中垂直方向坐標(biāo)的最小值與最大值；xv與yv分別表示頂點(diǎn)v在圖像水平與垂直方向的坐標(biāo)。

4.1 時(shí)間復(fù)雜度

與傳統(tǒng)的矢量化算法相似，動(dòng)態(tài)矢量化算法需要對(duì)圖像進(jìn)行遍歷，并且在弧段跟蹤時(shí)，需要對(duì)所有頂點(diǎn)進(jìn)行一次掃描。圖像遍歷與弧段跟蹤的復(fù)雜度分別為O（N×M）與O（K）。

封閉弧段間的拓?fù)潢P(guān)系判斷是矢量化算法中的一個(gè)難點(diǎn)。傳統(tǒng)的矢量化算法中，每個(gè)封閉弧段需要與其余所有封閉弧段進(jìn)行一次包含關(guān)系判斷，拓?fù)潢P(guān)系判斷的復(fù)雜度為O（n2）［13］。采用文獻(xiàn)［14—15］中的索引技術(shù)進(jìn)行優(yōu)化，理想情況下，復(fù)雜度接近O（nlogn），但這些算法實(shí)現(xiàn)起來較復(fù)雜。

動(dòng)態(tài)矢量化算法在拓?fù)潢P(guān)系判斷階段，屬于同一個(gè)復(fù)雜多邊形的封閉弧段劃分在一起，只需找出最外層的封閉弧段，拓?fù)潢P(guān)系判斷算法的復(fù)雜度為O（n）。

在實(shí)際的矢量化過程中，封閉弧段數(shù)量可能達(dá)到幾十萬(wàn)量級(jí)，以線性時(shí)間復(fù)雜度O（n）完成多邊形拓?fù)潢P(guān)系判斷，是動(dòng)態(tài)矢量化算法在時(shí)間效率上的顯著優(yōu)勢(shì)。

4.2 空間復(fù)雜度

運(yùn)用傳統(tǒng)的矢量化方法進(jìn)行矢量化處理時(shí)，會(huì)在內(nèi)存中保存所有的頂點(diǎn)，空間復(fù)雜度為O（K）。

當(dāng)動(dòng)態(tài)矢量化算法處理到圖像的第t行時(shí)，只需要存儲(chǔ)圖像第1行至第t行區(qū)域內(nèi)尚未完成矢量化的多邊形中的部分頂點(diǎn)，上述多邊形集合St＝｛s∈S｜ysmin≤t≤ysmax｝，需要存儲(chǔ)的頂點(diǎn)集合Vt＝｛v∈V｜存在s∈St，使得v∈s且yv≤t｝，易知Vt?V。設(shè)表示頂點(diǎn)集合Vt的頂點(diǎn)個(gè)數(shù)，則，只有當(dāng)對(duì)拓?fù)涠噙呅渭蟂中的任意一個(gè)多邊形都滿足ysmax＝N時(shí)，等號(hào)才成立?？梢?，在一般情況下，動(dòng)態(tài)矢量化算法空間復(fù)雜度O（Vmax）＜O（K）。

Vmax的實(shí)際計(jì)算非常復(fù)雜，與圖像大小及圖斑的復(fù)雜程度都有關(guān)。為了對(duì)Vmax進(jìn)行近似的估計(jì)，作如下兩個(gè)假設(shè)：①每個(gè)拓?fù)涠噙呅蔚捻旤c(diǎn)個(gè)數(shù)相等，且最小外接矩形的高相同；②拓?fù)涠噙呅卧趫D像空間中均勻分布。設(shè)每個(gè)拓?fù)涠噙呅巫钚⊥饨泳匦蔚母叨紴閔，當(dāng)動(dòng)態(tài)矢量化算法處理到第t行時(shí)，只需要存儲(chǔ)第t－h(huán)行到第t行區(qū)域內(nèi)的多邊形頂點(diǎn)，其頂點(diǎn)個(gè)數(shù)為

5 試驗(yàn)結(jié)果

為了驗(yàn)證本文算法的有效性，在Visual C＋＋環(huán)境下開發(fā)了相應(yīng)程序，進(jìn)行了兩組試驗(yàn)。第1組試驗(yàn)與遙感圖像處理主流商業(yè)軟件Arc－GIS10、ENVI4.8以及ERDAS2010的矢量化時(shí)間進(jìn)行了對(duì)比，測(cè)試的時(shí)間包含讀入柵格數(shù)據(jù)與生成矢量文件時(shí)間。第2組試驗(yàn)分析了動(dòng)態(tài)化處理對(duì)算法運(yùn)行內(nèi)存峰值的影響。本文選用不同規(guī)模和復(fù)雜度的北京一號(hào)衛(wèi)星遙感分類圖像，在AMD 2.3GHz CPU，2GB內(nèi)存的PC上進(jìn)行矢量化試驗(yàn)，試驗(yàn)結(jié)果見圖3、圖4、表1和表2。

表1 本文算法與ArcGIS、ERDAS以及ENVI矢量化時(shí)間的統(tǒng)計(jì)Tab.1 The process time of vectorization for different algorithms

表2 動(dòng)態(tài)化處理對(duì)算法運(yùn)行內(nèi)存峰值的影響Tab.2 The impact of dynamism process on memory peak of vectorization

圖3 柵格圖像Fig.3 Raster map

圖4 矢量結(jié)果圖Fig.4 Vector map

本文的矢量化結(jié)果保持了圖斑連通區(qū)域邊界的原始拓?fù)浣Y(jié)構(gòu)，矢量化結(jié)果無(wú)精度損失，如圖3與圖4所示。采用道格拉斯－撲克算法［18］對(duì)邊界進(jìn)行壓縮，以提高存儲(chǔ)效率，可以作為動(dòng)態(tài)矢量化算法下一步的改進(jìn)方向。

從表1可以看出，上述商業(yè)軟件中，ArcGIS矢量化算法效率最高，本文算法是其處理速度的2倍，具有明顯優(yōu)勢(shì)，并且隨著圖像規(guī)模及圖斑數(shù)量的增加，優(yōu)勢(shì)會(huì)更明顯，因此，本文算法處理大規(guī)模圖像具有很高的時(shí)間效率。

從表2可以看出，動(dòng)態(tài)矢量化算法所耗內(nèi)存僅為所有頂點(diǎn)加載到內(nèi)存進(jìn)行矢量化處理方法的16%～51%，這是因?yàn)檫M(jìn)行動(dòng)態(tài)化處理空間復(fù)雜度更低，因此，本文算法處理大規(guī)模圖像具有很高的空間效率。

6 結(jié) 論

與傳統(tǒng)方法不同，本文算法具有如下特點(diǎn)：

（1）將圖斑頂點(diǎn)個(gè)數(shù)作為判斷條件，使圖斑頂點(diǎn)的多邊形封閉性判斷能在常數(shù)時(shí)間內(nèi)完成，是本文動(dòng)態(tài)化算法得以高效實(shí)現(xiàn)的關(guān)鍵；

（2）在頂點(diǎn)提取過程中將滿足封閉性條件的圖斑矢量化并動(dòng)態(tài)釋放其內(nèi)存，大大降低了矢量化的內(nèi)存消耗，保證了空間的高效性；

（3）頂點(diǎn)提取時(shí)將各圖斑進(jìn)行分割，各圖斑矢量化獨(dú)立進(jìn)行直接生成封閉弧段無(wú)須產(chǎn)生中間數(shù)據(jù)，弧段跟蹤完成后，能以線性時(shí)間復(fù)雜度形成拓?fù)潢P(guān)系，時(shí)間效率高；

（4）各圖斑矢量化獨(dú)立進(jìn)行，非常適合將算法改造成并行化算法，能更充分地發(fā)揮多處理器或GPU的計(jì)算優(yōu)勢(shì)。

本文的矢量化算法已開發(fā)為成熟的軟件模塊，經(jīng)檢驗(yàn)，能快速高效地完成大數(shù)據(jù)量遙感圖像矢量化。

［1］ GONG Jianya.An Unified Data Structrue Based on Linear Quadtrees［J］.Acta Geodaetica et Cartographica Sinica，1992，21（4）：259－266.（龔健雅.GIS中矢量柵格一體化數(shù)據(jù)結(jié)構(gòu)的研究［J］.測(cè)繪學(xué)報(bào)，1992，21（4）：259－266.）

［2］ CHEN Renxi，ZHAO Zhongming，PAN Jing.A Fast Method of Vectorization for RS Classified Raster Map［J］.Journal of Remote Sensing，2006，10（3）：326－331.（陳仁喜，趙忠明，潘晶.遙感分類柵格圖的快速矢量化方法［J］.遙感學(xué)報(bào)，2006，10（3）：326－331.）

［3］ JIAO Mingyong，SU Honggen.Improved Algorithms for Raster to Vector and Specific Applications［J］.Computer Engineering and Design，2008，29（13）：3394－3398.（焦明勇，蘇鴻根.柵格轉(zhuǎn)矢量的改進(jìn)算法及應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（13）：3394－3398.）

［4］ HUANG Bo，CHEN Yong.New Approaches for Mutual Transferring of Vector and Raster［J］.Remote Sensing Technology and Application，1995，10（3）：61－65.（黃波，陳勇.矢量、柵格相互轉(zhuǎn)換的新方法［J］.遙感技術(shù)與應(yīng)用，1995，10（3）：61－65.）

［5］ LI Zhancai，LIU Chunyan.An Efficient Directed Boundary Method for Vectorization of Dot Matrix Image［J］.Computer Applications and Software，1997，14（3）：48－51.（李占才，劉春燕.點(diǎn)陣圖形矢量化的高效方法——有向邊界法［J］.計(jì)算機(jī)應(yīng)用軟件，1997，14（3）：48－51.）

［6］ ZHANG Xiaocan，PAN Yunhe.Vectorization Technique for GIS Grid Data Based on“Grid Technique”［J］.Journal of Computer－aided Design ＆ Computer Graphics，2001，13（10）：895－900.（章孝燦，潘云鶴.GIS中基于“柵格技術(shù)”的柵格數(shù)據(jù)矢量化技術(shù)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13（10）：895－900.）

［7］ SHEN Zhangquan，WANG Renchao.Study on a New Method for Transferring Grid to Vector Using the Topological Theory［J］.Journal of Remote Sensing，1999，3（1）：38－42.（沈掌泉，王人潮.基于拓?fù)潢P(guān)系原理的柵格轉(zhuǎn)換矢量方法的研究［J］.遙感學(xué)報(bào)，1999，3（1）：38－42.）

［8］ WU Huayi，GONG Jianya，LI Deren.Non－boundary Run－Length Encoding System for Raster and Its Relevant Algorithms［J］.Acta Geodaetica et Cartographica Sinica，1998，27（1）：63－68.（吳華意，龔健雅，李德仁.無(wú)邊界游程編碼及其矢柵直接相互轉(zhuǎn)換算法［J］.測(cè)繪學(xué)報(bào)，1998，27（1）：63－68.）

［9］ XIE Shunping，DU Jinkang，WANG Lachun，et al.Approach of Vectorization for GIS Raster Data Based on Runlength Encoding System ［J］.Acta Geodaetica et Cartographica Sinica，2004，33（4）：323－327.（謝順平，都金康，王臘春，等.基于游程編碼的GIS柵格數(shù)據(jù)矢量化方法［J］.測(cè)繪學(xué)報(bào)，2004，33（4）：323－327.）

［10］ TENG Junhua，WANG Fahui，LIU Yu.An Efficient Algorithm for Raster－to－vector Data Conversion ［J］.Annals of GIS.2008，14（11）：54－62.

［11］ CHEN Chun，ZHANG Shuwen，XU Guifen.The Basis for Generation of Topologic Information of Polygons in GIS［J］.Acta Geodaetica et Cartographica Sinica，1996，25（4）：266－271.（陳春，張樹文，徐桂芬.GIS中多邊形圖拓?fù)湫畔⑸傻臄?shù)學(xué)基礎(chǔ)［J］.測(cè)繪學(xué)報(bào)，1996，25（4）：266－271.）

［12］ QI Hua.The Optimization and Improvement for the Algorithm Steps on the Automatic Creation of Topological Relation of Polygons［J］.Acta Geodaetica et Cartographica Sinica，1997，26（3）：254－260.（齊華.自動(dòng)建立多邊形拓?fù)潢P(guān)系算法步驟的優(yōu)化與改進(jìn)［J］.測(cè)繪學(xué)報(bào)，1997，26（3）：254－260.）

［13］ ZHANG Xingyue，WANG Min，JIANG Sheng.A Novel Approach for Raster Data Vectorization ［J］. Geoinformation Science，2008，10（16）：730－735.（張星月，汪閩，蔣圣.一種新的柵格數(shù)據(jù)矢量化方法［J］.地球信息科學(xué)，2008，10（6）：730－735.）

［14］ GUTTMAN A.R－trees：A Dynamic Index Structure for Spatial Searching［C］∥ACM SIG－MOD Record.New York：ACM，1984：47－57.

［15］ XU Shaoping，WANG Minyan，WANG Weili.A New Index Structure for Moving Object Spatial Database Based on R Tree and Quan Tree［J］.Computer ＆ Digital Engineering，2006，34（3）：54－57.（徐少平，王命延，王煒立.一種基于R樹和四叉樹的移動(dòng)對(duì)象空間數(shù)據(jù)庫(kù)混合索引結(jié)構(gòu)［J］.計(jì)算機(jī)與數(shù)字工程，2006，34（3）：54－57.）

［16］ WANG Jing，JIANG Gangwu.Researching and Realization of the Quick Compression Method Aimed at the Non－Topology Vector Data ［J］.Acta Geodaetica et Cartographica Sinica，2003，32（2）：173－177.（王凈，江剛武.無(wú)拓?fù)涫噶繑?shù)據(jù)快速壓縮算法的研究與實(shí)現(xiàn)［J］.測(cè)繪學(xué)報(bào)，2003，32（2）：173－177.）