大數(shù)據(jù)量遙感分類圖像的動態(tài)矢量化算法

榮岳成

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

1 引 言

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

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

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

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

2 矢量化基本概念

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

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

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

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

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

定義4 坐標點只有兩個方向存在邊界，而對結(jié)點，至少在3個方向上存在邊界（如圖1）。

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

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

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

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

3.1 圖斑頂點統(tǒng)計

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

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

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

圖2 圖斑頂點個數(shù)統(tǒng)計Fig.2 Statistics of vertices in polygon

3.2 圖斑頂點提取

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

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

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

在頂點提取的過程中，每個圖斑的頂點用一個動態(tài)容器來存儲，頂點提取算法如下：

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

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

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

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

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

3.3 圖斑頂點矢量化

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

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

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

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

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

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

4.1 時間復(fù)雜度

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

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

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

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

4.2 空間復(fù)雜度

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

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

Vmax的實際計算非常復(fù)雜，與圖像大小及圖斑的復(fù)雜程度都有關(guān)。為了對Vmax進行近似的估計，作如下兩個假設(shè)：①每個拓撲多邊形的頂點個數(shù)相等，且最小外接矩形的高相同；②拓撲多邊形在圖像空間中均勻分布。設(shè)每個拓撲多邊形最小外接矩形的高都為h，當動態(tài)矢量化算法處理到第t行時，只需要存儲第t－h(huán)行到第t行區(qū)域內(nèi)的多邊形頂點，其頂點個數(shù)為

5 試驗結(jié)果

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

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

表2 動態(tài)化處理對算法運行內(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ū)域邊界的原始拓撲結(jié)構(gòu)，矢量化結(jié)果無精度損失，如圖3與圖4所示。采用道格拉斯－撲克算法［18］對邊界進行壓縮，以提高存儲效率，可以作為動態(tài)矢量化算法下一步的改進方向。

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

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

6 結(jié) 論

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

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

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

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

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

本文的矢量化算法已開發(fā)為成熟的軟件模塊，經(jīng)檢驗，能快速高效地完成大數(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］.測繪學(xué)報，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é)報，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)矢量的改進算法及應(yīng)用［J］.計算機工程與設(shè)計，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.（李占才，劉春燕.點陣圖形矢量化的高效方法——有向邊界法［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］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，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.（沈掌泉，王人潮.基于拓撲關(guān)系原理的柵格轉(zhuǎn)換矢量方法的研究［J］.遙感學(xué)報，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.（吳華意，龔健雅，李德仁.無邊界游程編碼及其矢柵直接相互轉(zhuǎn)換算法［J］.測繪學(xué)報，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］.測繪學(xué)報，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中多邊形圖拓撲信息生成的數(shù)學(xué)基礎(chǔ)［J］.測繪學(xué)報，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.（齊華.自動建立多邊形拓撲關(guān)系算法步驟的優(yōu)化與改進［J］.測繪學(xué)報，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樹和四叉樹的移動對象空間數(shù)據(jù)庫混合索引結(jié)構(gòu)［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.（王凈，江剛武.無拓撲矢量數(shù)據(jù)快速壓縮算法的研究與實現(xiàn)［J］.測繪學(xué)報，2003，32（2）：173－177.）