[發明專利]一種柵格數字圖像快速矢量化方法

無效

• 申請號: 201210159393.1
• 申請日: 2012-05-22
• 公開（公告）號: CN102881028A
• 公開（公告）日: 2013-01-16
• 發明（設計）人: 章孝燦;蘇程;俞偉斌;倪廣翼;黃智才
• 申請（專利權）人: 浙江大學
• 主分類號: G06T9/00
• 分類號: G06T9/00
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 周烽

技術領域

本發明屬于遙感數字圖像處理和地理信息系統（GIS）中數據轉換技術領域，具體涉及一種提取柵格數字圖像中面狀圖斑信息的柵格數字圖像快速矢量化方法。?

技術背景

柵格數字圖像矢量化是對柵格數字圖像中的圖斑進行邊緣勾繪，以提取圖斑的面狀信息為目的，將其轉換為矢量區域信息的技術。柵格和矢量作為GIS兩種基本數據類型經常需要互相轉換，由于遙感數據不斷大量增加，GIS的應用不斷豐富，對柵格數字圖像矢量化的需求與日俱增，面對海量數據，迫切需要有新的方法提高矢量化效率。?

以提取柵格數字圖像中面狀信息為目的的矢量化過程主要有2個關鍵過程：（1）是勾繪柵格圖斑生成矢量區域邊界；（2）是描述多邊形拓撲包含關系形成完整區域信息。目前，在上述兩個處理過程中，針對勾繪柵格圖斑形成矢量邊界，前人提出了有向邊界法、游程編碼法和四叉樹壓縮編碼法等技術方法，這些技術方法雖然在一定程度上提高了追蹤柵格圖斑邊界的效率，但是其中仍然存在大量的冗余的弧段搜索和連接判斷，因此在處理大量甚至海量數據時效率仍比較低；針對描述多邊形拓撲包含關系形成完整區域信息，前人提出的矢量化方法都是通過構造完整的多邊形拓撲關系來解決，由于多邊形拓撲關系構建非常復雜，故效率較低，是目前柵格數字圖像矢量化方法中最主要的效率瓶頸。因而在對海量柵格數字圖像進行面狀柵格圖斑矢量化的過程中，由于轉換效率低下的問題，傳統方法已經越來越不能滿足相關領域生產與應用的需求。?

發明內容：

本發明的目的在于提出一種柵格數字圖像快速矢量化方法，該方法充分利用了計算機系統資源和柵格數字圖像中所蘊含的圖斑空間信息，能夠解決現有矢量化方法存在的效率不高的缺點。

本發明的目的是通過以下技術方案來實現的：一種柵格數字圖像快速矢量化方法，該方法首先根據單個像元與其四鄰域像元屬性（像元值）的異同，確定該像元的像元有向邊類型；然后通過記錄像元有向邊首尾結點矢量坐標及其兩側多邊形信息構造連接索引，再根據像元有向邊類型和連接索引從以下四種方式中選擇一種方式對像元進行處理，掃描完所有像元后，每一個內多邊形及歸屬于該內多邊形的所有外多邊形共同構成一個矢量區域：?

（1）構建內多邊形；

（2）構建外多邊形，利用隱含射線法判斷外多邊形歸屬；

（3）根據連接索引連接像元有向邊，動態構造多邊形邊界；?

（4）根據多邊形邊界連接關系進行多邊形歸并處理。

進一步地，所述像元有向邊具有方向，該方向與矢量化區域邊界拓撲正向一致。?

進一步地，所述連接索引是記錄像元有向邊首尾結點的出入信息。?

進一步地，所述隱含射線法判斷外多邊形歸屬具體為：在掃描過程中，通過記錄最新掃描的內多邊形實現隱含射線法，并以此判斷外多邊形的歸屬。?

進一步地，所述根據多邊形邊界連接關系進行多邊形歸并處理具體為：通過連接多邊形邊界、更新內多邊形孤島鏈表、更新區域列表和更新多邊形類型實現多邊形的歸并。?

本發明的有益效果是：?

（1）根據掃描順序和像元有向邊類型構建新的多邊形，使構造矢量區域簡單高效。使用掃描線方法遍歷柵格數據時是按照從上到下，從左到右的順序進行，因此對于任意一個圖斑來說，總是先遍歷到它的左上角像元，當掃描至“左上角像元”時就遇到了一個新的柵格圖斑，需要構建新的內多邊形，即一個新的區域。對于任意含有“洞”的圖斑來說，總是先遇到“洞”的頂邊，即具有“下”邊且不能插入至現有多邊形邊界的像元有向邊需要構建新的外多邊形。由于充分利用了柵格圖斑中所蘊含的鄰接關系，直接避免了構建矢量區域的起始搜索弧段過程。

（2）根據連接索引直接連接像元有向邊，使構造矢量區域邊界簡單高效。使用掃描線方法按照從左到右，從上到下的順序遍歷柵格數據時，像元有向邊只可能在所屬像元正上方左右兩個結點處發生連接。對每一個矢量坐標列記錄其像元有向邊首尾出入信息，就可以引導其它像元有向邊直接連接至相應多邊形的邊界，直接避免了組織多邊形邊界時復雜的判斷與追蹤過程，從而大幅提高構建柵格圖斑矢量邊界的效率。?