大數據量遙感分類圖像的動態矢量化算法

榮岳成

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

1 引 言

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

柵格轉矢量是GIS研究中的經典課題，積累了比較多的方法。如邊緣跟蹤法、散列線段聚合法［4］、有向邊界法［5］、基于柵格技術的矢量化方法［6］、基于拓撲原理的轉換方法［2，7］、基于游程編碼的追蹤方法［8，9］、雙臂鏈邊界跟蹤法［10］等。此外，學者們還從拓撲信息自動生成［11］、基于弧－弧的拓撲關系判斷［12］等方面對多邊形拓撲關系構建算法進行了研究。

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

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

2 矢量化基本概念

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

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

定義1 柵格數據矢量化時，只有圖斑信息。

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

定義3 弧段是圖斑與圖斑之間的連續的邊界分界線，弧段內部的點稱為坐標點，弧段的端點稱為結點。

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

定義5 每個矢量多邊形由一個外環和多個內環組成（或沒有內環），沒有內環的多邊形稱為簡單多邊形，含有內環的多邊形稱為復雜多邊形。

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

3 動態矢量化算法

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

3.1 圖斑頂點統計

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

每個環是由一系列首尾重合的頂點構成的封閉多邊形。簡單多邊形對應圖斑的頂點個數為外環的頂點個數；復雜多變形對應的圖斑的頂點個數為外環與所有內環的頂點個數之和。在圖2中，圖斑A與C對應簡單多邊形，頂點個數均為4，圖斑B對應復雜多邊形，頂點個數為10。

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

圖2 圖斑頂點個數統計Fig.2 Statistics of vertices in polygon

3.2 圖斑頂點提取

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

對于每個頂點，本文采用如下的結構體表示其信息［2］。

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

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

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

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

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

（4）判斷所有點是否都已經被處理完成，如果是，則算法結束，否則繼續執行（1）。

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

3.3 圖斑頂點矢量化

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

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

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

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

4 動態矢量化算法分析

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

4.1 時間復雜度

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

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

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

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

4.2 空間復雜度

運用傳統的矢量化方法進行矢量化處理時，會在內存中保存所有的頂點，空間復雜度為O（K）。

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

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

5 試驗結果

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

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

表2 動態化處理對算法運行內存峰值的影響Tab.2 The impact of dynamism process on memory peak of vectorization

圖3 柵格圖像Fig.3 Raster map

圖4 矢量結果圖Fig.4 Vector map

本文的矢量化結果保持了圖斑連通區域邊界的原始拓撲結構，矢量化結果無精度損失，如圖3與圖4所示。采用道格拉斯－撲克算法［18］對邊界進行壓縮，以提高存儲效率，可以作為動態矢量化算法下一步的改進方向。

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

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

6 結 論

與傳統方法不同，本文算法具有如下特點：

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

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

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

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

本文的矢量化算法已開發為成熟的軟件模塊，經檢驗，能快速高效地完成大數據量遙感圖像矢量化。

［1］ GONG Jianya.An Unified Data Structrue Based on Linear Quadtrees［J］.Acta Geodaetica et Cartographica Sinica，1992，21（4）：259－266.（龔健雅.GIS中矢量柵格一體化數據結構的研究［J］.測繪學報，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］.遙感學報，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.（焦明勇，蘇鴻根.柵格轉矢量的改進算法及應用［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.（黃波，陳勇.矢量、柵格相互轉換的新方法［J］.遙感技術與應用，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］.計算機應用軟件，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中基于“柵格技術”的柵格數據矢量化技術［J］.計算機輔助設計與圖形學學報，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.（沈掌泉，王人潮.基于拓撲關系原理的柵格轉換矢量方法的研究［J］.遙感學報，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.（吳華意，龔健雅，李德仁.無邊界游程編碼及其矢柵直接相互轉換算法［J］.測繪學報，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柵格數據矢量化方法［J］.測繪學報，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中多邊形圖拓撲信息生成的數學基礎［J］.測繪學報，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.（齊華.自動建立多邊形拓撲關系算法步驟的優化與改進［J］.測繪學報，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.（張星月，汪閩，蔣圣.一種新的柵格數據矢量化方法［J］.地球信息科學，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樹和四叉樹的移動對象空間數據庫混合索引結構［J］.計算機與數字工程，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.（王凈，江剛武.無拓撲矢量數據快速壓縮算法的研究與實現［J］.測繪學報，2003，32（2）：173－177.）