柵格地圖道路的快速矢量化方法研究與實(shí)現(xiàn)

寇曼曼，王勤忠，萬(wàn) 娜

(河南省地震局，河南 鄭州 450018)

0 引言

GIS數(shù)據(jù)主要有柵格地圖和矢量地圖2類。柵格電子地圖也就是通常所說(shuō)的Bitmap位圖。獲取柵格數(shù)據(jù)的成本低、速度快、自動(dòng)化程度高，但是數(shù)據(jù)量大，存儲(chǔ)不方便，縮放過(guò)程中會(huì)產(chǎn)生失真，數(shù)據(jù)不是很準(zhǔn)確。矢量電子地圖，數(shù)據(jù)結(jié)構(gòu)緊湊，數(shù)據(jù)量小，冗余度低，有利于網(wǎng)絡(luò)和檢索分析，精度高，圖形顯示質(zhì)量好，可以隨意縮放，縮放過(guò)程中不會(huì)失真。由于矢量電子地圖的這些特點(diǎn)，使它在地理信息系統(tǒng)中應(yīng)用很廣。因此如何將柵格數(shù)據(jù)轉(zhuǎn)換為矢量數(shù)據(jù)是GIS技術(shù)研究的重點(diǎn)之一［1-4］。

通常制作矢量圖要先用掃描儀把紙質(zhì)地圖掃描成數(shù)字柵格圖像，然后再轉(zhuǎn)換成所需要的矢量圖。目前，在實(shí)際生產(chǎn)中是借助現(xiàn)有的工具軟件(如國(guó)外的MapInfo及國(guó)內(nèi)的MapGIS等)進(jìn)行逐點(diǎn)矢量化，工作量大而且繁瑣。本文采用從互聯(lián)網(wǎng)獲取得數(shù)字柵格地圖為處理對(duì)象，通過(guò)識(shí)別地圖標(biāo)注的方法來(lái)實(shí)現(xiàn)道路提取，在此基礎(chǔ)上提出一種基于可變矩形跟蹤框技術(shù)實(shí)現(xiàn)柵格地圖道路快速矢量化的方法。

1 分類道路提取與細(xì)化

1.1 數(shù)據(jù)來(lái)源

通常制作矢量圖要先用掃描儀把紙質(zhì)地圖掃描成數(shù)字柵格圖像，然后再轉(zhuǎn)換成所需要的矢量圖。本文采用從互聯(lián)網(wǎng)獲取得數(shù)字柵格地圖為處理對(duì)象。

1.2 分類道路提取

Google Map是由分辨率大小為256×256的圖片無(wú)縫拼接而成的。每個(gè)地圖瓦片均由獨(dú)立的URL地址唯一確定，有了完整的 URL在 C#中利用 Http-WebRequest類可實(shí)現(xiàn)瓦片地圖的下載［5-7］。在獲取瓦片地圖的基礎(chǔ)上，應(yīng)用圖像拼接得到原始數(shù)字柵格地圖。通過(guò)基于視覺(jué)一致性的聚類分析，可以基本分離出所需要的道路，但存在分離出的要素被各種標(biāo)注覆蓋或中斷的現(xiàn)象。通過(guò)結(jié)合模式識(shí)別與基于視覺(jué)一致性的色彩聚類分析精確識(shí)別出各類標(biāo)注體。在成功提取標(biāo)注區(qū)和道路信息的基礎(chǔ)上，通過(guò)分析不同標(biāo)注對(duì)道路的覆蓋形式，實(shí)現(xiàn)間斷道路的自動(dòng)連接［8-10］。

1.3 道路細(xì)化

通過(guò)前面的標(biāo)注區(qū)識(shí)別及基于視覺(jué)效果的色彩聚類分析和中斷道路的連接，已經(jīng)提取出了道路信息，將道路的顏色置為黑色(取值為1)，其他為白色(取值為0)。設(shè)待細(xì)化的圖像有任意點(diǎn)P，如果等于0，即認(rèn)為此點(diǎn)是背景點(diǎn)，跳過(guò)不予處理，繼續(xù)下一點(diǎn)，如果等于1，認(rèn)為是道路上的點(diǎn)，接著判斷此點(diǎn)是否保留。通常使用3×3的結(jié)構(gòu)元素對(duì)點(diǎn)P的去留進(jìn)行判斷［11-12］，但是對(duì)于是否是連接點(diǎn)的判斷，需要進(jìn)一步向外延考察，所以本文采用5×5的結(jié)構(gòu)元素，選取點(diǎn)P周圍對(duì)稱的24個(gè)點(diǎn)，結(jié)構(gòu)如圖1所示。

圖1 5×5結(jié)構(gòu)元素

同時(shí)滿足以下4個(gè)條件的點(diǎn)P將被刪除:

1)2≤A(P)≤6;

2)B(P)=1;

3)P(1，2)*P(2，1)*P(2，3)=0 或者 P(1，2)*P(2，1)*P(2，3)=1＆＆B(P(1，2))≠1;

4)P(1，2)*P(2，1)*P(3，2)=0 或者 P(1，2)*P(2，1)*P(3，2)=1＆＆B(P(2，1))≠1。

其中A(P)表示點(diǎn)P八鄰域中值為1的點(diǎn)的個(gè)數(shù)，B(P)表示點(diǎn)P八鄰域中從0→1變化的個(gè)數(shù)。

2 柵格地圖道路矢量化規(guī)則

要矢量化的柵格數(shù)據(jù)主要有以下特點(diǎn):

1)從道路數(shù)據(jù)的空間特征上來(lái)看，道路分不同等級(jí)，道路之間有交點(diǎn)。

2)從單條道路的角度看，道路有一定的方向性，且具有分段特性。

依據(jù)GIS系統(tǒng)線性對(duì)象的一般性拓?fù)湟?guī)則，在跟蹤矢量化過(guò)程中，應(yīng)滿足以下2個(gè)條件:

1)在同一層要素類中，線與線不能相互重疊，相交處打斷，以弧段形式表達(dá)線狀要素;

2)2個(gè)線層不能相交。

3 矢量化追蹤方法

3.1 可變矩形追蹤框

正方形追蹤框數(shù)據(jù)為一柵格點(diǎn)集，左上角為起始點(diǎn)，順時(shí)針排列。以矢量化線要素上一點(diǎn)為中心，以2S+1為邊長(zhǎng)的正方形追蹤框(追蹤步長(zhǎng)S，S取正整數(shù))，記錄追蹤框與線要素的交點(diǎn)，并根據(jù)不同情況調(diào)節(jié)追蹤框大小來(lái)獲得唯一的追蹤目標(biāo)點(diǎn)。

Bresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域使用最廣泛的直線掃描轉(zhuǎn)換方法。其原理是:過(guò)各行、各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)最近的像素［13］。當(dāng)追蹤框與矢量化線要素有2個(gè)交點(diǎn)時(shí)，采用Bresenham算法返回由這2點(diǎn)所確定直線中的一系列點(diǎn)集M，假設(shè)點(diǎn)集中有S點(diǎn)在矢量化圖像上，點(diǎn)擬合比例為P=S/M，選取合適的閾值P1(0＜P1＜1)，若實(shí)際情況大于P1，認(rèn)為2交點(diǎn)之間的點(diǎn)近似在一條直線上，以末端點(diǎn)為下一追蹤點(diǎn)，若小于P1，則認(rèn)為2交點(diǎn)之間的點(diǎn)基本不在一條直線上，縮短追蹤步長(zhǎng)，縮小跟蹤框。

3.2 端點(diǎn)(交點(diǎn))判斷

3.2.1 追蹤框與被矢量化對(duì)象交點(diǎn)

根據(jù)矩形中點(diǎn)及邊框大小確定邊框上各點(diǎn)的坐標(biāo)，然后從追蹤框左上角開(kāi)始，逐點(diǎn)判斷是否存在與被矢量化對(duì)象顏色一致的點(diǎn)并記錄下這些交點(diǎn)。當(dāng)交點(diǎn)為連續(xù)點(diǎn)時(shí)，合并首尾點(diǎn)只記錄第一個(gè)點(diǎn)。

判斷追蹤框與被矢量化對(duì)象的交點(diǎn)數(shù)，如果只有一個(gè)交點(diǎn)，則縮小追蹤框找到末端點(diǎn);如果存在2個(gè)交點(diǎn)，則通過(guò)判斷追蹤框中點(diǎn)和追蹤框與被矢量化對(duì)象交點(diǎn)間是否為近似的直線確定追蹤步長(zhǎng)是否合適;如果存在多于2個(gè)交點(diǎn)，則跟蹤框內(nèi)可能存在多個(gè)線段的交匯點(diǎn)。

3.2.2 追蹤框內(nèi)矢量化線段交匯點(diǎn)

追蹤框與被矢量化對(duì)象存在多于2個(gè)交點(diǎn)時(shí)，采用逐點(diǎn)跟蹤確定可能的交匯點(diǎn)。從追蹤框中心點(diǎn)開(kāi)始，以1個(gè)像素寬為跟蹤步長(zhǎng)，在該點(diǎn)的八鄰域中搜索線要素上的點(diǎn)，并統(tǒng)計(jì)其個(gè)數(shù)n(相鄰的點(diǎn)合并為一個(gè)點(diǎn))，如圖2所示。若n=1，則該點(diǎn)為線條的端點(diǎn)，結(jié)束此線的跟蹤;若n=2，則該點(diǎn)為線條的中間點(diǎn)，根據(jù)追蹤方向選擇曲線上的點(diǎn)作為下一追蹤點(diǎn);若n＞2，則該點(diǎn)為曲線的交匯點(diǎn)，相鄰多點(diǎn)合并為一個(gè)點(diǎn)，歸并3交叉、4交叉后，具體形式如圖1所示，“0”為背景，著色部分為曲線上的點(diǎn)，7種形式分別旋轉(zhuǎn)90°、180°、270°，共計(jì)有 22 種情況。應(yīng)用 Bresenham算法判斷交匯點(diǎn)與上一矢量化點(diǎn)之間是否為近似的直線，如果是則記錄交匯點(diǎn)，然后選擇在道路慣性延伸方向的交點(diǎn)做為下一跟蹤點(diǎn)，在道路的慣性延伸方向上沒(méi)有交點(diǎn)，那么將曲線的交匯點(diǎn)做為端點(diǎn)，此條道路矢量化結(jié)束。

圖2 逐點(diǎn)追蹤確定交叉點(diǎn)

3.2.3 道路交點(diǎn)慣性延伸方向

在道路交匯點(diǎn)的位置會(huì)有多條道路相交，如何選擇下一步的跟蹤方向?qū)⑹抢^續(xù)矢量化的關(guān)鍵，用道路慣性延伸方向來(lái)幫助選擇。如圖3所示，追蹤框尺寸size=7，道路與追蹤框入方向的交點(diǎn)ap，相對(duì)于中心點(diǎn)P在追蹤框上的對(duì)稱點(diǎn)cp，左右移動(dòng)［size/2］向下取整即3個(gè)點(diǎn)，從lp到rp這個(gè)范圍內(nèi)都屬于道路的慣性延伸方向。落在lp到rp之間的交點(diǎn)將是一個(gè)跟蹤點(diǎn)。

圖3 道路的慣性延伸方向

4 矢量化實(shí)現(xiàn)

道路矢量化的算法流程如圖4所示，采用自適應(yīng)可變矩形跟蹤框，計(jì)算矢量化對(duì)象與跟蹤框交點(diǎn);判斷交點(diǎn)數(shù)，如果只有2個(gè)交點(diǎn)則采用逆Bresenham算法判斷交點(diǎn)之間的線段是否為近似直線，不滿足則縮小跟蹤框返回上一步，滿足近似直線條件則把追蹤方向的交點(diǎn)作為下一追蹤框中心點(diǎn)繼續(xù);如果只有一個(gè)交點(diǎn)則通過(guò)縮小追蹤框找到端點(diǎn);如果交匯點(diǎn)多于2個(gè)則采用逐點(diǎn)跟蹤方式判斷追蹤框內(nèi)有無(wú)交匯點(diǎn)，如果無(wú)交匯點(diǎn)則同存在2個(gè)交匯點(diǎn)一樣處理，如果存在交匯點(diǎn)則判斷交匯點(diǎn)與上一矢量化中間點(diǎn)之間是否滿足近似直線標(biāo)準(zhǔn)，不滿足則縮小跟蹤框，滿足則取交匯點(diǎn)為矢量化線段的交點(diǎn)，線段慣性延伸方向的交點(diǎn)為下一跟蹤框的中心點(diǎn)，若為丁字路口無(wú)慣性延伸方向交點(diǎn)，則結(jié)束追蹤。

圖4 單條道路矢量化算法流程

5 試驗(yàn)結(jié)果

圖5 柵格地圖道路矢量化效果

圖5展示了不同道路狀況下的矢量化效果。圖5(a)、圖5(b)這2個(gè)例子可以看出被矢量化對(duì)象以可變步長(zhǎng)沿道路自然延伸方向跟蹤，并終止于同類道路的丁字型交匯點(diǎn);圖5(c)、圖5(d)這2個(gè)例子顯示矢量化算法自動(dòng)在道路交匯處設(shè)置交點(diǎn)并沿道路慣性延伸方向延續(xù)矢量化;當(dāng)遇到立交點(diǎn)，系統(tǒng)默認(rèn)設(shè)置為采用交互式人工確定下一步跟蹤方向及交點(diǎn)性質(zhì)，如圖5(d)中顯示低等級(jí)公路被高等級(jí)公路中斷，停止矢量化等待交互處理。

6 結(jié)束語(yǔ)

本文以數(shù)字柵格地圖為處理對(duì)象，提出一種基于可變矩形跟蹤框技術(shù)快速矢量化線狀要素的方法。根據(jù)柵格地圖特征，采用自適應(yīng)跟蹤步長(zhǎng)的可變矩形跟蹤框技術(shù)，加快了矢量化的速度，同時(shí)又結(jié)合逐點(diǎn)跟蹤、端點(diǎn)判斷、道路慣性延伸點(diǎn)判斷方法，提高了矢量化的精準(zhǔn)度，最終達(dá)到對(duì)柵格地圖道路快速、精確地矢量化的目的。實(shí)驗(yàn)結(jié)果表明該方法的矢量化效果十分理想。

［1］錢靜，陳洋，王潤(rùn)生.彩色掃描地形圖中等高線提取方法的研究［J］.中國(guó)圖象圖形學(xué)報(bào)，2006，11(10):1443-1449.

［2］張玉芳，熊忠陽(yáng)，陳銘灝，等.彩色柵格地圖矢量化方法研究［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(10):85-87.

［3］王勇，李朝奎.線性要素柵格數(shù)據(jù)矢量化快速簡(jiǎn)便算法設(shè)計(jì)與實(shí)現(xiàn)［J］.測(cè)繪工程，2009，18(5):44-46，50.

［4］鄒修明，張?jiān)佬?柵格地圖矢量化關(guān)鍵技術(shù)研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39(19):102-103，138.

［5］張東輝，何政偉，楊斌.柵格圖像自動(dòng)矢量化系統(tǒng)的研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(10):171-174.

［6］李少梅，闞映紅，王穎，等.Google Earth影像變換與應(yīng)用研究［J］.測(cè)繪科學(xué)與工程，2010，30(2):11-14，43.

［7］寇曼曼，王勤忠，譚同德.Google Map數(shù)字柵格地圖算法及應(yīng)用［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2012，22(4):204-206.

［8］寇曼曼，王勤忠，譚同德.彩色數(shù)字柵格地圖中道路的識(shí)別與提?。跩］.計(jì)算機(jī)工程，2012，38(13):276-279.

［9］詹曦.彩色城市交通地圖的道路識(shí)別與提?。跩］.計(jì)算機(jī)仿真，2010，27(2):242-246.

［10］Hai T，Bao Y L.Road extraction based on image features of raster urban traffic map［C］//International Conference on Transportation Engineering 2007.2007:594-599.

［11］Chin R T，Wan H K，Stover D L，et al.A one-pass thinning algorithm and its parallel implementation［J］.Computer Vision Graphics Image Processing，1987，40(10):30-40.

［12］牟少敏，杜海洋，蘇平，等.一種改進(jìn)的快速并行細(xì)化算法［J］.微電子學(xué)與計(jì)算機(jī)，2013，30(1):53-55，60.

［13］Freeman H.Computer processing of line-drawing image［J］.Compute Surveys，1974，6(1):57-97.