[發明專利]一種基于Delaunay三角網的柵格地圖矢量化方法

有效

• 申請號: 201210401900.8
• 申請日: 2012-10-22
• 公開（公告）號: CN102930561A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 王結臣;倪浩晨;程亮;崔璨;謝順平
• 申請（專利權）人: 南京大學
• 主分類號: G06T9/00
• 分類號: G06T9/00;G06T7/00
• 代理公司: 南京同澤專利事務所(特殊普通合伙) 32245
• 代理人: 石敏

技術領域

本發明涉及一種單要素的柵格地圖矢量化方法，屬于柵格地圖矢量化技術領域。

背景技術

隨著社會信息化的不斷深入和地理信息產業的不斷發展，人們對基礎地理信息數據的需求，尤其對可進行大量空間分析的數字矢量地理信息數據的需求逐年增大。以當今遙感和測繪技術生成的數字矢量地理信息數據，遠遠不能滿足社會的龐大需求。因此通過對傳統紙質地圖的掃描數字矢量化，成為一種有效并可靠地獲取矢量地理信息數據的方法。

目前對傳統紙質地圖的掃描矢量化方法，按自動化程度可分為：手動矢量化、半自動矢量化、自動矢量化。手動矢量化主要指，早期利用平板數字化儀手撫跟蹤數字化或后期紙質地圖掃描屏幕數字化；半自動矢量化指，借助人工輔助利用計算機圖形圖像學算法，自動的識別出點、線、面、注記等地圖要素；自動矢量化指，完全不需要人工干預，由計算機自己通過算法完成自動地圖矢量化工作。顯而易見，上述三種矢量化方法中，完全脫離人工作業的自動矢量化是人工作業量最小、作業速度最快的。

對掃描地圖的自動矢量化是以柵格圖為依據，通過計算機輔助標繪等手段生成，是一個綜合了計算機視覺、計算機圖像處理、計算機圖形學和人工智能等各個學科的交叉課題。多年來的理論及實踐為此課題的研究奠定了良好的基礎，但由于其應用背景的復雜性及需求的多樣性，目前的研究結果普遍存在處理速度慢、智能程度低以及適應性差等特點。

在柵格圖形的矢量化過程中，提取目標圖形骨架線是實現柵格轉化成矢量的核心內容。骨架線能夠準確地反映空間對像的幾何結構特征，利用骨架線來表示圖像中已經提取的線狀目標，可以在保證目標重要拓撲特征的前提下，最大限度地減少目標存貯記錄中的冗余信息。迄今為止，已經有大量的骨架線提取算法，但大多存在運算復雜、矢量化時間長等缺陷。

發明內容

本發明解決的技術問題是：提出一種處理速度快、效果好的基于Delaunay三角網的柵格地圖矢量化方法。

為了解決上述技術問題，本發明提出的技術方案是：一種基于Delaunay三角網的柵格地圖矢量化方法，包括以下步驟：

第一步、對單要素柵格圖進行黑白二值化；

第二步、尋找所述單要素柵格圖中的線劃要素；

第三步、提取各線劃要素對應的柵格圖的邊界柵格，從而獲得各線劃要素對應的邊界柵格圖；

第四步、基于各邊界柵格圖的邊界柵格中心點分別生成Delaunay三角網；

第五步、剔除不在所述線劃要素范圍內的干擾三角形；

第六步、利用Delaunay三角網三角形間的拓撲關系提取線劃要素骨架線，即得到單要素柵格圖的矢量化結果。

本發明的創新點在于，獨創性地采用獲取線劃要素輪廓范圍內Delaunay三角形，并通過找到三角網首節點，跟蹤拓撲鄰接三角形的方式，提取線劃要素骨架線，達到矢量化的目的。

本發明首先對柵格圖進行分組找出線劃要素，再對線劃要素的邊緣點進行Delaunay三角網劃分，各分組的算法實現不受其它分組影響，運算量小、耗時短，而且又易于進行算法的并行化實現。這種提取骨架線的方法，錯誤率低，基本上不需要再進行人工修正。

對于為多要素彩色待矢量化柵格地圖，則首先通過分色，得到多個單色的單要素柵格圖，再分別對單要素柵格圖執行第一步到第六步。

本發明還提供一種使用像元鄰域分析的標記算法對所述單要素柵格圖中的像元進行分組的方法。在本發明第二步中，使用像元鄰域分析的標記算法尋找所述單要素柵格圖中的線劃要素，具體方法如下：

1)順序遍歷單要素柵格圖中的像元，對所有不為0的像元根據其掃描順序依次賦值；

2)再次順序遍歷重新賦值后的單要素柵格圖中的像元，對所有不為0的像素與其八鄰域中不為0的像素進行比較，若其八鄰域范圍內所有標記值的最小值小于其本身的標記值，則修改其標記值為撰述最小值；

3)反向遍歷步驟2)處理后的單要素柵格圖中的像元，處理過程同步驟2)；

4)再次順序遍歷單要素柵格圖中的像元，統計具有不同標記的像元種類數；

5)重復步驟2)-4)直到統計的像元種類數與上一次統計的像元種類數一致，即完成像元的分組，具有相同值的像元屬于同一線劃要素。

本發明還提供了一種使用基于數學形態學的腐蝕算法提取柵格圖中的邊界柵格的算法。因為本發明僅提取1個像元寬的邊界柵格，所以采用3*3的腐蝕算子。

在本發明第三步中，對分組后的柵格圖用3*3的腐蝕算子進行腐蝕運算，得到腐蝕后的柵格集合；用所述柵格圖減去腐蝕后得到的柵格集合就得到了柵格圖中的邊界柵格。