柵格圖像矢量化方法及其研究進展

摘要：該文分析了柵格圖像矢量化的常用方法存在的問題，介紹并簡單評價了多種主要的改進方法，方便技術人員根據具體需要快速的選擇合適的矢量化方法，最后，就柵格圖像矢量化的研究方向給出了一些建議。

關鍵詞：柵格圖像；矢量化；細化；非細化

中圖分類號：TP391.41 文獻標志碼：A 文章編號：1009-3044(2008)33-1478-02

The Progress of Vectorization Algorithm of Grid image

SHI Gui-xian，ZHANG Ping

(School of Information Science and Engineering，University of Jinan，Jinan 250022，China)

Abstract: The paper makes an analysis of several common vectorization methos and their problems.Then，some methods about the vectorization are introduced and the evaluation is discussed The purpose of the survey is to help researchers select a appropriate vectorization algorithm for a system.At last，some suggestions about the vectorization of grid image are proposed.

Keywords: grid image; vectorization; thinning; nonthinning

1 引言

計算機中圖像文件的格式主要有兩大類：一類是柵格圖像文件格式，另一類是矢量圖文件格式。在現代圖像處理技術中，矢量圖文件格式相對于柵格圖像文件格式具有明顯的優點。矢量化就是將柵格數據轉換為矢量數據。國內外矢量化的研究始于20世紀70年代，柵格圖像矢量化作為圖像處理的一個重要分支，已經成為地理信息系統（GIS）、計算機輔助設計和制造時代（CAD/CAM）領域的關鍵技術。柵格圖像矢量化方法的研究與改進具有非常重要的現實意義。

2 經典的矢量化算法

目前矢量化方法大致可分為兩類，基于細化的方法和基于非細化的方法。

1) 經典的基于細化的方法主要有：邊界重復細化法、距離交換法和適當骨架化方法。這些細化方法的優點是能夠保持線段的連續性，主要缺點是有很高的時間復雜度，丟失線寬信息，在交叉區域處以產生變形及錯誤的分支。

2) 在基于非細化的方法中，主要有：基于輪廓線的方法，基于游碼的方法，基于網格模式的方法以及基于稀疏像素的方法。① 由于基于輪廓線的方法在早期比較流行，但是此算法容易使連續矢量之間產生間隙。② 基于游碼的方法能夠保持線段的連續性并能保存線寬信息，但在游碼圖形顯示過程中，容易產生噪聲和引起交叉區域的變形。③ 基于網格模式的方法，由于只考慮網格邊框上的圖像信息，是研究問題得到相應的簡化，但是網格的尺寸很難控制。此方法是用于所含線段直并且少的線圖中。④ 基于稀疏像素的方法能夠保存線寬以及精確的中心軸和端點，矢量化速度快。其不足之處在于不能對所有的交叉區域提供正確的處理。

一個好的矢量化方法應該能保存線形信息例如線寬、區域交叉點、圖像的拓撲結構等信息，同時還要求矢量化的速度比較快。總的來說各種矢量化方法都各有自身的優缺點，從矢量化效果上來說不具有通用性。

3 基于細化的矢量化算法的改進

目前比較普及的矢量化方法是基于細化的方法，細化又叫中軸變換(medial axis transformation)或骨架化(skeletonization)，是指在圖像上對于寬度大于一個像素的粗線狀目標，刪除其輪廓像素，保留骨架像素的過程。

作為基于細化的柵格圖像矢量化過程中的一個重要技術環節，細化同樣影響工作效率和結果的精度。所以很多改進方法是圍繞著細化算法的改進展開的。本節將介紹幾種基于細化矢量化方法的改進方法。

3.1 保存節點拓撲的改進方法

利用現有的矢量化軟件，如：ArcGIS、ENVI、PCI等進行柵格圖像矢量化時所獲得的矢量圖會出現一些島和自交多邊形，或者是一些連接關系雜亂無章的矢量線，而不是多邊形。

一種改進方法是以拓撲關系原理為指導，同時提取柵格圖像中節點和坐標點以及所有的水平和垂直線段，目的是在提取骨架線的同時更好地從柵格數據獲取節點信息，依據節點和線段兩者信息共同來生成弧段，再由弧段生成多邊形[1]。

文獻[2]對細化后的圖像識別端點和節點信息，并用相同大小的參考圖像記錄節點信息，利用節點對應位置的像素值來表示節點類型，如值為1則表示端點，值為3則表示3鏈節點。在設計節點和骨架線的適量數據結構時，考慮到處理骨架線節點畸變和冗余的需要，記錄節點坐標的同時還記錄了相關的拓撲關系，如是否舍去，是否懸掛節點，節點連接線數，節點相關線的ID等。

上述兩種改進方法由于保存了節點的拓撲信息，在用于矢量面狀地物的骨架線提取時，能夠在一定程度上防止節點畸變并減少骨架線的冗余小分枝。

3.2 基于數學形態學的改進方法

數學形態學是一種新型的圖像處理工具，研究人員利用數學形態學的薄化運算作為細化的基本運算模式。這種算法相對與經典的基于細化的方法具有明顯的優點：可以實現并行運算，提高算法運算速度；可以較好的保持圖像各圖元間的拓撲結構特性。缺點是不能保持線段的連續性。這種基于細化的方法是近年來研究的一個熱點。

3.3 基于Freeman鏈碼的矢量化方法改進

基于細化的矢量化算法在對柵格圖像進行細化提取了骨架線后，多數采用了基于Freeman鏈碼的矢量化方法。文獻[3]對基于Freeman鏈碼的變步長矢量化方法進行改進，即要求初始步長（最小取樣間隔）是2的N(N是非負整數)次冪，每次步長的改變量是上一步長的一半，直到步長的改變量為1并且鏈碼中兩點間任意像素點到這兩點間弦線垂距滿足大于等于最大允許垂線偏差的條件為止。這種改進算法減少了算法迭代次數，提高運算效率。

4 基于非細化的矢量化算法的改進

由于基于細化的矢量化方法普遍存在丟失線寬信息，在交叉區域處容易產生變形及錯誤的分支等缺點。部分學者仍在為設計具有良好自適應性的基于非細化的柵格圖像矢量化算法而努力。本節將介紹近幾年針對這類算法的一些主要改進發法。

4.1 基于游程編碼的矢量化方法改進

解決規模大、復雜度高的柵格圖像高效矢量化問題的有效途徑是找到一種完全基于內存數據處理的弧段提取技術。吳華意等[4]提出了一種無邊界游程編碼及其矢柵互轉換算法，標記矢量化時的追蹤，對游程進行了擴充。但是這種算法額外的內存開銷降低了游程的壓縮效率，限制了處理圖像的規模和復雜度。文獻[5]在此基礎上提出了一種基于游程編碼的矢量化改進方法。利用最簡的游程編碼形式并與區位表和折半查找技術相結合，實現對柵格圖斑邊界的追蹤和矢量化提取，直接由游程編碼提取含有拓撲關系的圖斑邊界弧段，其效率較以往方法有一定幅度的提高。

4.2 基于圓跟蹤的矢量化方法

這種方法針對地形等高線的特性提出的。算法的具體方法是：首先查找等高線的起始點A，并記錄該點，然后以A點為圓心，以指定的長度為半徑畫圓，并記錄該圓與等高線的交點B，然后以B點為圓心，再以同樣的半徑畫圓，以此類推，每一次畫一個圓都記錄一個交點（忽略落在前一個圓內部的那個交點），直至所畫的圓和等高線沒有交點為止，把這個過程叫做跟蹤等高線，這一系列的圓叫做跟蹤圓。該方法可以從等高線的任意一個端點開始跟蹤，在遇到等高線較稠密或者等高線急拐彎的情況下，跟蹤圓和等高線按照一定的步長縮小跟蹤圓的半徑重新跟蹤，直到跟蹤圓和等高線重合的像素點在一個指定的閾值范圍內為止[6]。該矢量化算法具有一定的自適應性，但是得到的是等高線上一些距離間隔不等的離散的坐標點，為了還原等高線或者作為后續的插值求其它點的高程或者其它屬性，必須對這些離散的數據點進行曲線擬合。可以采用三次B-樣條進行擬合。

4.3 基于輪廓線的矢量化方法的改進

基于輪廓線的矢量化過程可以分為輪廓提取，跟蹤，輪廓特征點提取，輪廓矢量化。輪廓特征點的提取直接影響到矢量化的效果，即怎樣從輪廓跟蹤后得到的緊密排列的有序輪廓點中，提取出表示圖像輪廓關鍵特性的點。文獻[7]主要針對特征點提取提出了一種基于以“徑向增量同向段”和“徑向增量異向段”為基本元素構成位圖輪廓邊界的輪廓特征點提取算法，并對特征點進行插值；得到最終的圖像輪廓特征點。由這些特征點可以表征原圖像的形體特征，且算法具有計算簡單和工作量少的特點。

5 其他方面的改進

近年來也有學者嘗試將計算智能中的遺傳算法，神經網絡等引入到圖像矢量化方法的某些環節如：圖像分類、分層、細化、曲線特征點提取等，從而對算法進行適當的改進。

6 結束語

本文概述了柵格圖像矢量化的常用方法和存在的問題，并介紹了多種主要的改進方法。其中，仍有一些方法需要得到進一步的改進，在實際應用中，我們可以根據矢量化對象的特點和各改進方法的優點將不同的算法進行結合和運用。國際上商品化的矢量化軟件有德國Softelec公司的VPStudio、挪威RxSpotlight、美國GTX公司的GTXRasterCAD PLUS，Able公司的R2v等等，國內的有MapGIS、中科院的VWAN、清華山維的EPScan等，這些軟件都能對柵格圖像進行矢量編輯或進行一定程度上的自動矢量化，但是矢量化精度和速度上尚不能完全達到工程自動化的需要，普遍具有對噪音、缺損敏感等缺點。可見柵格圖像自動矢量化是一個非常困難而遠遠沒有被解決的問題，其難點主要在于圖像要素的復雜性和多樣性。預計柵格圖像自動矢量化技術還將在以下幾個方面得到進一步的研究和發展：

1) 基于細化的矢量化方法設計中，復雜的圖像要素的自動識別比較困難，有效的特征提取顯得尤為重要；

2) 提高矢量化算法的自適應性，提高矢量化軟件的自動化程度；

3) 柵格圖像的智能與自動矢量化涉及到計算機圖形學、圖像處理、模式識別、人工智能等多種技術，與各相關技術的新的高效的科研成果相結合也是柵格圖像矢量化改進的一種途徑；

4) 研制公共的數據轉換器實現不同軟件之間的數據交換，從而促進不同的矢量化軟件之間的相互兼容。

參考文獻：

[1] 扶卿華，倪紹祥，郭劍.柵格數據矢量化及其存在問題的解決[J].現代測繪，2004，27(3):8-11.

[2] 王輝連，武芳.利用數學形態學提取骨架線的改進算法[J]. 測繪科學，2006，31(1):29-33.

[3] 孫景榮，許錄平.一種改進的圖形矢量化方法[J].計算機工程與應用，2004，(1):88-90.

[4] WU Hua-yi，GONG Jian-ya，LI De-ren.Non-boundary Run-length Encoding System for Raster and Its Relevant Algorithms[J]. Acta Geodaetica et Cartographica Sinica，1998，27(1):63-64.

[5] 謝順平，都金康.基于游程編碼的GIS柵格數據矢量化方法[J].測繪學報，2004，33(4):323-327.

[6] 陳爭光，吳裕樹，王玉芳.一種新型的地形等高線矢量化方法[J].計算機工程與應用，2004，(3):84-86.

[7] 嚴素蓉，朱桂林，徐從富.一種位圖矢量化新方法[J].計算機工程與應用，2005，(14):85-87.