交互式等值線圖紙矢量化方法

賈 雨， 王 瑩， 姚興苗

（1. 成都理工大學(xué)核技術(shù)與自動(dòng)化工程學(xué)院，四川 成都 610059；2.電子科技大學(xué)通信與信息工程學(xué)院，四川 成都 611731）

等值線圖紙矢量化是指將等值線圖紙掃描獲得相應(yīng)的圖像，通過(guò)計(jì)算機(jī)自動(dòng)識(shí)別圖像中的等值線，提取矢量的幾何屬性與拓?fù)潢P(guān)系，將處理對(duì)象由像素點(diǎn)陣圖像轉(zhuǎn)換為矢量圖形。該項(xiàng)工作是等值線圖紙數(shù)字化錄入的一種常用技術(shù)，在地質(zhì)、地球物理、地理信息系統(tǒng)等方面有廣泛的應(yīng)用，受到相關(guān)領(lǐng)域科技工作者的廣泛關(guān)注，提出了許多有用的算法[1-4]，促進(jìn)了該項(xiàng)技術(shù)的發(fā)展。

現(xiàn)有研究均在不同的方面促進(jìn)了等值線圖紙矢量化技術(shù)的發(fā)展，但尚沒(méi)有一種方法能解決等值線圖紙矢量化的所有問(wèn)題，在實(shí)際應(yīng)用中還存在不能完全采用計(jì)算機(jī)自動(dòng)識(shí)別的情況。為此，本文通過(guò)改進(jìn)基于圓跟蹤[3]的等值線矢量化算法，提出了一種交互式的等值線的矢量化方法——等值線間隔追蹤算法，通過(guò)人工干預(yù)彌補(bǔ)計(jì)算機(jī)自動(dòng)識(shí)別存在的缺陷，保證追蹤的正確性，適用于灰度等值線圖像的矢量化，具有實(shí)用性和高效性。

1 等值線間隔追蹤算法

1.1 算法原理

等值線間隔追蹤算法采用非細(xì)化的方法，對(duì)等值線圖紙直接進(jìn)行像素級(jí)的追蹤，以人工拾取的等值線上的某一點(diǎn)為起點(diǎn)，沿頭尾兩個(gè)方法進(jìn)行追蹤，若找不到符合條件的點(diǎn)，則暫停追蹤，等待人工干預(yù)后繼續(xù)追蹤，直到整條等值線追蹤完畢。等值線間隔追蹤算法有3個(gè)關(guān)鍵的門限參數(shù)作為追蹤的約束條件，RGB門限值對(duì)選取的點(diǎn)進(jìn)行初步判斷，通過(guò)顏色排除背景像素點(diǎn)；夾角門限利用等值線光滑的性質(zhì)，排除等值線以外的干擾點(diǎn)；最小搜索半徑門限控制搜索的范圍并且可以作為搜索結(jié)束的標(biāo)識(shí)。

對(duì)于實(shí)線上的某一點(diǎn)Pi開(kāi)始按照搜索半徑R進(jìn)行搜索，可能找到多個(gè)符合灰度門限的點(diǎn)，計(jì)算這些點(diǎn)與Pi點(diǎn)所確定的直線與點(diǎn)Pi和它前面的相鄰點(diǎn)Pi-1所構(gòu)成的直線的夾角，取夾角最小的點(diǎn)為搜索到的等值線上的點(diǎn)，如圖1(a)所示。

對(duì)于虛線上的某一點(diǎn)Pi開(kāi)始按照搜索半徑R進(jìn)行搜索，若沒(méi)有符合灰度門限和夾角門限的點(diǎn)，則縮小搜索半徑繼續(xù)搜索，直到找到符合條件的點(diǎn)。通過(guò)設(shè)置最小搜索半徑門限為VALUEr小于虛線段的半長(zhǎng)，可實(shí)現(xiàn)虛線繪制的等值線的追蹤。如圖1(b)所示。

圖1 等值線間隔追蹤算法原理示意圖

等值線間隔追蹤算法相較于基于圓跟蹤的等值線圖矢量化算法，主要進(jìn)行了以下兩個(gè)方面的改進(jìn)：

1）基于圓跟蹤的等值線圖矢量化算法只能處理黑白二值圖像，等值線間隔追蹤算法通過(guò)灰度門限的設(shè)置可以處理灰度圖像。

2）基于圓跟蹤的等值線圖矢量化算法適用于實(shí)線繪制的等值線的追蹤，而當(dāng)繪圖區(qū)域存在逆斷層（多值面）時(shí)，下盤的等值線是由虛線繪制的，本文提出的等值線間隔追蹤算法可以通過(guò)設(shè)置最小搜索半徑來(lái)實(shí)現(xiàn)虛線繪制的等值線圖像的追蹤。

1.2 算法描述

設(shè)Pi為等值線的控制點(diǎn)，則所有等值線控制點(diǎn)集合為為等值線的控制點(diǎn)個(gè)數(shù)。設(shè)追蹤算法的灰度門限為VALUErgb，最小搜索半徑門限為VALUEr，搜索半徑為R。

第1步：在圖像中的等值線上任取一點(diǎn)放入集合U，該點(diǎn)即作為頭點(diǎn)，又作為尾點(diǎn)，向兩個(gè)方向追蹤等值線。

第2步：以頭點(diǎn)為搜索起點(diǎn)搜索。

1）置集合V為空集，用于臨時(shí)存放追蹤找到的點(diǎn)。在頭點(diǎn)方向上，以頭點(diǎn)為圓心，R為半徑搜索圓上的像素點(diǎn)，逐個(gè)比較這些點(diǎn)與頭點(diǎn)的灰度差是否超過(guò)灰度門限VALUErgb。若灰度差小于灰度門限VALUErgb，則將該點(diǎn)放入集合V。

2）若集合V不為空，分2種情況考慮：

第1種情況，所有等值線控制點(diǎn)集合為U只有一個(gè)控制點(diǎn)P1，則取等臨時(shí)集合V中與控制點(diǎn)P1灰度差最小的一個(gè)點(diǎn)為第二個(gè)控制點(diǎn)P2，放入集合U。

第2種情況，所有等值線控制點(diǎn)集合為U有2個(gè)或2個(gè)以上的控制點(diǎn)，當(dāng)前頭點(diǎn)記為Pi，逐個(gè)判斷集合V中點(diǎn)與頭點(diǎn)Pi所確定的直線與頭點(diǎn)Pi和它前面的相鄰點(diǎn)Pi-1所構(gòu)成的直線的夾角，取夾角最小的點(diǎn)為控制點(diǎn)，將這個(gè)點(diǎn)放入集合U中，記此點(diǎn)為頭點(diǎn)，并將當(dāng)前搜索半徑置為R，重新執(zhí)行第2步。

3）若集合V為空，則跳至第4步。

第3步：以尾點(diǎn)為搜索起點(diǎn)搜索。以尾點(diǎn)為搜索起點(diǎn)搜索方法與第2步相同。若找到符合條件的點(diǎn)，放入集合U，并將該點(diǎn)設(shè)置為尾點(diǎn)，作為下次尾點(diǎn)方向追蹤的起點(diǎn)。若沒(méi)有找到符合條件的點(diǎn)，跳至第4步。

第4步：若R≥VALUEr，則縮小搜索半徑，以當(dāng)前的頭點(diǎn)或尾點(diǎn)按第2、3步進(jìn)行搜索。若R

等值線間隔追蹤算法步驟如圖2所示：

圖2 等值線間隔追蹤算法原理

1.3 等值線的光滑處理

在追蹤出所有的等值點(diǎn)后，如果僅僅將等值點(diǎn)依次連接起來(lái)，那么生成的等值線圖是由折線構(gòu)成，而等值線通常要求是一條光滑連續(xù)的曲線。因此，需要對(duì)等值線進(jìn)行光滑處理。常見(jiàn)的曲線光滑算法主要可分為插值算法和擬合算法兩類。常見(jiàn)的插值算法有拋物線加權(quán)算法、分段三次多項(xiàng)式插值的方法，三次樣條函數(shù)法等；常見(jiàn)的擬合算法有線形迭代法、Bezier曲線函數(shù)法等。

下面以正軸拋物線加權(quán)平均算法為例，介紹等值線的光滑算法。

正軸拋物線加權(quán)平均法的基本思想是根據(jù)給定的曲線特征點(diǎn)順序，每相鄰3點(diǎn)作1條拋物線，而每相鄰兩點(diǎn)之間前后兩條拋物線弧的重合部分用加權(quán)平均曲線作為最終的插值光滑曲線[6]。

正軸拋物線加權(quán)平均法的實(shí)現(xiàn)方法是：對(duì)給定的n個(gè)曲線特征點(diǎn)序列，從首點(diǎn)開(kāi)始，順序取4點(diǎn)，過(guò)4點(diǎn)中的前3點(diǎn)可作一正軸拋物線，過(guò)4點(diǎn)中的后3點(diǎn)又可作一正軸拋物線，對(duì)過(guò)中間2點(diǎn)的2條正軸拋物線取加權(quán)平均，作為過(guò)中間2點(diǎn)的最終曲線。由于權(quán)函數(shù)是一個(gè)三次多項(xiàng)式，所以最終的曲線方程是五次多項(xiàng)式。

正軸拋物線加權(quán)平均法在數(shù)學(xué)上是嚴(yán)密的，計(jì)算過(guò)程也較為簡(jiǎn)單，能保證光滑曲線嚴(yán)格通過(guò)每個(gè)特征點(diǎn)，并且在整條線上具有一階連續(xù)導(dǎo)數(shù)，其缺點(diǎn)是曲線的拐點(diǎn)不一定正好在特征點(diǎn)上，也即曲線的最大曲率點(diǎn)有可能偏離節(jié)點(diǎn)。

2 應(yīng)用實(shí)例

等值線間隔追蹤算法的核心思想是以像素點(diǎn)的灰度值和相鄰點(diǎn)連線的夾角為約束條件，在滿足最小搜索半徑的門限的前提下尋找合適的像素的點(diǎn)作為等值線的控制點(diǎn)。在算法實(shí)現(xiàn)過(guò)程中，可以通過(guò)調(diào)整各門限值來(lái)適應(yīng)不同等值線的追蹤，并且采用人工干預(yù)的交互式操作來(lái)保證追蹤結(jié)果的正確性。等值線間隔追蹤算法中門限參數(shù)的設(shè)置對(duì)于等值線的追蹤效果有明顯的影響，適用于不同情況下的等值線圖紙追蹤。

1）灰度門限

一般情況下，等值線圖紙中同一條等值線的顏色是相同的，可以通過(guò)設(shè)置灰度門限將等值線上的像素點(diǎn)和等值線上其他圖像信息區(qū)分開(kāi)來(lái)。當(dāng)圖紙上干擾信息與等值線灰度值相近時(shí)，可以設(shè)置較小的灰度門限，減少誤判的情況；當(dāng)圖紙上干擾信息與等值線灰度值相差較大時(shí)，可以設(shè)置較大的灰度門限，以保證追蹤過(guò)程中不因門限過(guò)小而丟失等值線上的點(diǎn)。

2）最小搜索半徑門限

通過(guò)設(shè)置最小搜索半徑的門限可以矢量化虛線繪制的等值線，并且在絕大多數(shù)情況下追蹤過(guò)程不會(huì)因?yàn)榈戎稻€的標(biāo)注而中斷。該算法采用頭尾點(diǎn)同時(shí)追蹤的方式，能夠克服掃描圖片上出現(xiàn)的線交叉的問(wèn)題，確保追蹤出的等值線分岔。

3）夾角門限

合理的設(shè)置算法中相鄰點(diǎn)連線的夾角門限，可實(shí)現(xiàn)不同情況下的等值線追蹤。對(duì)于等值線密集區(qū)域，設(shè)置較小的夾角門限，以確保不會(huì)追蹤到相鄰等值線上的點(diǎn)；對(duì)于曲率較大的等值線，則設(shè)置較大的的夾角門限，使追蹤過(guò)程不會(huì)出現(xiàn)過(guò)多的等待人機(jī)交互的中斷。

圖3為灰度化以后的等值線圖紙，圖4為對(duì)等值線圖紙中幾條等值線采用等值線間隔追蹤算法進(jìn)行追蹤的效果圖，圖中彩色等值線為追蹤所得等值線，當(dāng)?shù)戎稻€追蹤到逆斷層邊界時(shí)，由于夾角門限的限制，可以有效的選取等值線上的點(diǎn)，并且在上盤線或下盤線處停止追蹤。從實(shí)驗(yàn)結(jié)果中可以看出追蹤所得的等值線與等值線圖紙中等值線基本吻合。

圖3 預(yù)處理后的等值線圖紙

圖4 等值線間隔追蹤算法效果圖

3 結(jié) 論

本文在基于圓追蹤的非細(xì)化等值線矢量化基礎(chǔ)上，改進(jìn)并實(shí)現(xiàn)了等值線間隔追蹤算法。該算法基于稀疏輪廓跟蹤圖像矢量化識(shí)別模型，采用非細(xì)化的方法直接對(duì)等值線進(jìn)行追蹤，通過(guò)人工干預(yù)保證追蹤的正確性，適用于灰度等值線圖像的矢量化。實(shí)驗(yàn)結(jié)果表明，本文的算法適用于灰度圖像的等值線追蹤，可以直接追蹤粗細(xì)不同的等值線，且能適用于含有逆斷層的等值線圖的矢量化，最大優(yōu)點(diǎn)是追蹤出的線是沒(méi)有分岔的線，能夠克服掃描圖片上出現(xiàn)的線交叉的問(wèn)題，實(shí)現(xiàn)簡(jiǎn)單且具有高效性。

[1]劉修國(guó), 謝 忠. MAPGIS 中掃描矢量化及其相關(guān)技術(shù)[J]. 地球科學(xué), 1998, 23(7): 341.

[2]Khotanzad A, Zink E. Contour line and geographic feature extraction from USGS color topographical paper maps [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(1): 18-31.

[3]陳爭(zhēng)光, 吳裕樹(shù), 王玉芳.一種新型的地形等高線矢量化方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2004, 3: 84-86.

[4]趙國(guó)成, 孫 群, 安曉亞, 等. 一種從彩色掃描圖像上提取等高線的方法[J]. 測(cè)繪通報(bào), 2011, (4): 35-37.

[5]張志軍, 孫志輝. 基于VC 平臺(tái)的彩色圖像的灰度化技術(shù)[J]. 計(jì)算機(jī)應(yīng)用, 2005, 24(1): 61-67.

[6]艾自興, 龍 毅. 計(jì)算機(jī)地圖制圖[M]. 武漢: 武漢大學(xué)出版社, 2005, 85-87.

[7]張鵬強(qiáng), 翟 翊, 林群超. 大比例尺地形圖掃描數(shù)字化影像變形糾正方法與實(shí)踐[J]. 測(cè)繪學(xué)院學(xué)報(bào),2001, 18(4): 280-283.

[8]楊 云, 朱長(zhǎng)青, 孫 群. 彩色掃描地圖中線目標(biāo)的矢量化方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2009, 21(4): 533-541.

[9]黃本宇. 等值線圖繪制算法研究及實(shí)現(xiàn)[D]. 西安:西安石油大學(xué), 2007: 22-23.

[10]譚建榮, 彭群生. 基于圖形約束的工程圖紙掃描圖像直線整體識(shí)別方法[J]. 計(jì)算機(jī)學(xué)報(bào), 1994, 17(8):561-569.

[11]成 彬, 張樹(shù)生, 石云飛. 工程圖矢量化識(shí)別技術(shù)研究綜述[J]. 工程圖學(xué)學(xué)報(bào), 2008, 29(6): 7-12.