基于OTSU和輪廓追蹤的地圖線條識別方法

冉文靜 王加勝 饒 珣 趙 喆 陳鑫亞 徐春曉

(1.云南師范大學(xué)信息學(xué)院，云南 昆明 650500；2.云南師范大學(xué)地理學(xué)部，云南 昆明 650500)

1 引言

紙質(zhì)地圖是重要的地理數(shù)據(jù)來源之一。為了充分利用紙質(zhì)地圖數(shù)據(jù)，需要通過掃描成柵格地圖后，再將其轉(zhuǎn)化為計(jì)算機(jī)方便查詢和拓?fù)浞治龅氖噶繑?shù)據(jù)。地圖矢量化即為將柵格地圖轉(zhuǎn)換為矢量地圖的處理過程，是地理信息科學(xué)（Geographic Information Science，GIS）數(shù)據(jù)獲取的重要途徑。傳統(tǒng)的地圖矢量化方法采用人機(jī)交互方式完成，需要用鼠標(biāo)對照柵格地圖新建圖層，描繪點(diǎn)、線、面，添加屬性。當(dāng)需矢量化的地圖數(shù)量較大時(shí)，這種方式需要花費(fèi)大量的人力物力。如何改進(jìn)自動化程度，提高矢量化速度成為目前快速獲取地理空間數(shù)據(jù)亟需解決的問題。線條識別是地圖自動矢量化的關(guān)鍵步驟，線條識別后可通過柵格轉(zhuǎn)矢量方法方便地轉(zhuǎn)化為線和面。

現(xiàn)有的地圖線條識別算法主要分為三類：一是基于邊界特征的線條算法[1]。該算法由Capson提出[3]，利用多邊形邊界的連貫性研究的一種掃描柵格圖多邊形邊界鏈接序列化算法，但是該算法需要占用大量的內(nèi)存資源。二是基于邊界搜索的線條查找算法[4-7]，該算法由Nichols[2]提出，該算法首先確定來自四個相鄰像素交點(diǎn)的類型，然后用連接信息跟蹤弧，用弧線構(gòu)造多邊形，但是該算法也仍然存在占用大量內(nèi)存資源的缺點(diǎn)。三是基于邊界跟蹤的線條查找算法[8-13]。在目前線要素提取的研究中：趙雪松[14]將地圖進(jìn)行二值化后，結(jié)合Arcscan的DRG進(jìn)行自動的矢量化。但經(jīng)過此方法提取線要素的過程中還需要進(jìn)行人工修測、刪減、增補(bǔ)等處理，才能得到較好的結(jié)果。董敏等[15]用ArcGIS自動矢量化提取線要素，薛濱瑞[16]用CorelDraw和ArcGIS制作地形等高線，但這兩種方案易導(dǎo)致矢量化線條變形。Naccache等[17]提出細(xì)化算法來提取等高線，雖然速度快、效果好，但算法對于掃描地形圖的質(zhì)量要求較高，且實(shí)現(xiàn)方式成本較大，不利于普及。鄧凱、朱世權(quán)等[18]在地圖線條質(zhì)量優(yōu)化過程中，閾值的調(diào)整可能額外生成雜點(diǎn)。在這些方法中存在需要人工修改，或?qū)崿F(xiàn)效果不好等缺陷。

本文提出了一種基于最大類間方差法（OTSU）和邊界追蹤的地圖線條自動識別方法。該方法根據(jù)光柵圖像的連通性提取多邊形邊界，從上到下和從左到右掃描圖像，將地圖中線條所形成的輪廓全部檢測提取。相比較于其它的矢量化算法，該算法記錄了所有輪廓之間的聯(lián)系信息，并運(yùn)用這些信息有效解決了地圖的圖文分離問題。

2 地圖線條識別方法

基本思路為：首先，對圖像進(jìn)行預(yù)處理，對于含噪聲比較高的地圖圖像，進(jìn)行去噪、濾波等處理；然后，基于OTSU閾值分割算法對處理好的圖像進(jìn)行二值化處理；然后，運(yùn)用邊界追蹤算法識別輪廓；最后，通過計(jì)算所有輪廓的面積將面積小的進(jìn)行剔除，實(shí)現(xiàn)地圖的圖文分離，即將線條和文字分離出來。

2.1 地圖灰度化與二值化

（1）地圖的灰度化。就是將每個像素點(diǎn)的RGB值轉(zhuǎn)換為一個灰度值。首先，讀取彩色的柵格地圖，用矩陣存儲其數(shù)值。參考文獻(xiàn)[19]運(yùn)用公式（1）將RGB圖像轉(zhuǎn)換為灰度圖像。

其中，R、G、B分別代表彩色圖像中的紅色、綠色、藍(lán)色三個通道的對應(yīng)像素值，Gray為最終計(jì)算出的灰度值。

（2）圖像的二值化。二值化的目的是排除干擾，區(qū)分出地圖中的目標(biāo)（線條）和背景（其它）。通過設(shè)定閾值，將大于閾值的像素灰度值設(shè)為1，把小于這個值的像素灰度值設(shè)為0。在圖像二值化的過程中，閾值對線條識別結(jié)果有很大的影響。傳統(tǒng)的二值化方法主要根據(jù)人工的經(jīng)驗(yàn)設(shè)定一個閾值。本文運(yùn)用OTSU算法實(shí)現(xiàn)灰度圖像自動二值化。OTSU算法由日本學(xué)者大津在1979年提出，是一種圖像灰度自適應(yīng)的閾值分割算法，其在圖像亮度和對比度較低的情況下也能較好地選取合適的分割閾值。OTSU要求選擇最佳閾值，使圖像前景和背景間的灰度值差距較大，衡量灰度差異的標(biāo)準(zhǔn)定義為類間方差，即當(dāng)前景和背景間的類間方差取最大值時(shí)，獲取最佳閾值。假設(shè)圖像的像素總數(shù)為N，L個灰度級[1,2,…,L]，灰度值為i的像素總數(shù)為ni出現(xiàn)概率：

設(shè)圖像的初始閾值為t，若像素的灰度值小于t，則屬于C0，否則屬于C1，C0、C1別代表圖像的背景類和前景類。圖像背景類和前景類像素出現(xiàn)的概率和灰度均值分別用ω0、ω1、u0、u1表示，有：

其中，σ2表示類間方差，當(dāng)σ2取得最大值時(shí)，獲取最佳閾值。

2.2 線條輪廓追蹤

線條輪廓追蹤主要是基于邊界追蹤對二值圖像進(jìn)行拓?fù)浣Y(jié)構(gòu)分析。把一個二值圖像轉(zhuǎn)換成邊界表示，以此來實(shí)現(xiàn)地圖的線條識別。邊界追蹤是數(shù)字化二值圖像處理的基本技術(shù)之一，它從1像素的連接分量和0像素的連接分量之間的邊界導(dǎo)出坐標(biāo)或鏈碼序列[20]。因?yàn)槎M(jìn)制圖像在外邊界和1分量以及孔邊界和0分量之間存在一一對應(yīng)，所以可以確定給定二進(jìn)制圖像的拓?fù)浣Y(jié)構(gòu)。要提取的信息是兩種邊界：外邊界和孔邊界。

如果像素點(diǎn)（i,j）滿足外邊界和孔邊界的起始條件時(shí)，則像素點(diǎn)（i，j）被視為外邊界或孔邊界的起點(diǎn)。算法從左到右掃描像素點(diǎn)直到找到目標(biāo)像素點(diǎn)，圖1顯示了判斷是外邊界還是孔邊界的標(biāo)準(zhǔn)。其中圖1a表示外邊界，圖1b表示孔邊界。在掃描時(shí)，首先分辨一個像元是外部邊界還是孔邊界；然后，為發(fā)現(xiàn)的邊框分配一個可識別的數(shù)字，即邊界序號，用NBD來表示。初始時(shí)NBD=1，每次發(fā)現(xiàn)一個新的邊界NBD+1。在這個過程中，遇到（i,j）=1，(i,j+1)=0時(shí)，則將像素（i,j）的值更改為-NBD。否則，將像素（i,j）的值設(shè)為NBD。除非（i,j）在已經(jīng)跟隨的邊界上跟隨并標(biāo)記整個邊界，否則繼續(xù)掃描圖片，當(dāng)掃描到圖片右下角時(shí)，算法停止。

圖1 外邊界和孔邊界判斷標(biāo)準(zhǔn)

2.3 文字的去除

由于運(yùn)用目標(biāo)追蹤的矢量化算法，會將地圖上的文字的輪廓一并查找，因此在繪制輪廓時(shí)，選擇繪制所有的輪廓，會將地圖上的文字也進(jìn)行繪制出來，這樣就對地圖線條的提取造成了干擾，對于這個問題，本文利用輪廓的面積實(shí)現(xiàn)圖文分離。由于文字的輪廓面積較小，因此，可設(shè)定面積閾值篩選出字體的輪廓。其中輪廓面積的計(jì)算原理是計(jì)算整個或者部分輪廓的面積，計(jì)算部分輪廓面積時(shí)，由輪廓弧線和連接兩端點(diǎn)的弦圍成的區(qū)域總面積計(jì)算。

3 實(shí)驗(yàn)和結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文所用的數(shù)據(jù)是從天地圖以及百度網(wǎng)頁下載的RGB的彩色電子地圖圖像。為對比分析本文提出方法的效果，選取四類較為典型的電子地圖圖像進(jìn)行實(shí)驗(yàn)：一是線條較少文字較少的地圖，為最簡單的地圖圖像，如圖2a所示；二是線條較多文字較少的地圖圖像，如圖2b所示；三是線條少文字較多的地圖圖像，如圖2c所示，四是線條多文字也多的地圖圖像，也是最為復(fù)雜的地圖，如圖2d所示。

圖2 原始彩色地圖

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)的結(jié)果如圖3所示，第一步為將圖像二值化的結(jié)果。在將地圖進(jìn)行二值化的過程中，發(fā)現(xiàn)會有少量的地圖線條和文字有孔洞的效果，因此少量的圖像信息有所損失。在經(jīng)過輪廓追蹤后進(jìn)行文字和線條的分離過程中，由于在進(jìn)行輪廓追蹤算法時(shí)，對于有些文字本身就在地圖的線條上，查找輪廓時(shí)，將文字與線條計(jì)算在同一輪廓內(nèi)，因此通過輪廓面積方法進(jìn)行圖文分離的時(shí)候，會存在部分的文字沒有辦法進(jìn)行去除。從最后的實(shí)驗(yàn)結(jié)果中可以看到：在第一幅最為簡單的地圖中通過計(jì)算輪廓面積的方法能夠?qū)⒌貓D線條和文字進(jìn)行很好的分離，線條提取的結(jié)果幾乎沒有損失；在第二幅地圖中，結(jié)果有少量的線條和文字未進(jìn)行分離，如圖中用紅色框標(biāo)識的部分；在第三幅地圖中圖文分離的效果相較于第二幅地圖來說更多一點(diǎn)；在第四幅地圖中的實(shí)驗(yàn)結(jié)果較差，不僅有線條的損失，而且線條中夾雜文字的地方也最多。

圖3 實(shí)驗(yàn)結(jié)果

4 結(jié)語

針對地圖線條自動識別問題，本文提出了一種基于OTSU和輪廓追蹤的地圖線條識別方法。通過不同復(fù)雜程度的電子地圖實(shí)驗(yàn)，結(jié)果表明，本文方法實(shí)現(xiàn)了地圖線條自動識別，為地圖自動矢量化提供了重要支撐。然而，通過實(shí)驗(yàn)發(fā)現(xiàn)，本文的方法對于線條少，文字少且未附著于線條上的地圖來說有很好的適用性，但對于線條多，文字與線條混雜的復(fù)雜地圖來說，實(shí)驗(yàn)的結(jié)果仍有提升的空間。尤其是對于文字附著在線條上，與線條混在一起的情況，通過輪廓追蹤的算法會將文字與線條計(jì)算在同一輪廓內(nèi)，因此對于這樣的情況就不能將文字和線條進(jìn)行有效分離，在今后的工作中將進(jìn)一步研究優(yōu)化。