陳 旺，郭慶勝，范 偉，張 航，周賀杰

(武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430070)

二值圖像中目標(biāo)物體邊界跟蹤的一種快速算法及其應(yīng)用

陳 旺，郭慶勝，范 偉，張 航，周賀杰

(武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，湖北 武漢 430070)

對(duì)比分析傳統(tǒng)的二值圖像邊界跟蹤算法，并在此基礎(chǔ)上提出一種只根據(jù)鄰近兩個(gè)柵格的圖像狀態(tài)控制輪廓走向的新算法。實(shí)驗(yàn)結(jié)果表明，新算法搜索次數(shù)少，輪廓識(shí)別準(zhǔn)確，且很好地解決了島洞問(wèn)題，最后在應(yīng)用中驗(yàn)證了算法的有效性。

二值圖像；邊界追蹤；地理信息系統(tǒng)；柵格數(shù)據(jù)；模式識(shí)別

邊界跟蹤作為圖像處理和模式識(shí)別的基礎(chǔ)算法，一直是研究的熱點(diǎn)和難點(diǎn)。邊界輪廓的確定對(duì)于研究物體的形狀特征有著不言而喻的意義，在醫(yī)學(xué)圖像、工業(yè)斷層掃描圖像等二維圖像處理領(lǐng)域中應(yīng)用廣泛[1]，甚至可以說(shuō)是很多進(jìn)一步研究的前提。另外在地理信息系統(tǒng)(GIS)數(shù)據(jù)處理的柵格數(shù)據(jù)向矢量數(shù)據(jù)轉(zhuǎn)換的過(guò)程中，邊界追蹤也有著重要作用[2-3]。

邊界跟蹤算法的難點(diǎn)與關(guān)鍵就在于如何確定下一步的跟蹤方向[4]，經(jīng)典的算法有蟲隨法、光柵法等。而這些算法有可能反復(fù)跟蹤局部區(qū)域，使程序陷入死循環(huán)。另外，對(duì)于可能存在的島或者洞，并沒(méi)有提供一個(gè)解決方案。文獻(xiàn)[5]中的目標(biāo)鄰域跟蹤算法是在蟲隨法上改進(jìn)而來(lái)，一次循環(huán)就可得到結(jié)果，但搜索精度和速度上仍有待提高。文獻(xiàn)[6]采用的算法思想是基于文獻(xiàn)[5]的算法思想，并根據(jù)上一點(diǎn)的邊界位置判斷輪廓走向，減少了搜索次數(shù)，但精確度并不太高，也沒(méi)有解決島和洞的問(wèn)題。文獻(xiàn)[7]提出的基于動(dòng)態(tài)權(quán)值的邊界跟蹤法在搜索速度和準(zhǔn)確度上都有所提升，并較好地過(guò)濾掉二值化引起的邊界噪聲，但存儲(chǔ)空間開銷大，對(duì)于復(fù)雜的圖像，效率不高。本文提出的算法可以根據(jù)鄰近兩個(gè)柵格的圖像狀態(tài)控制輪廓走向，極大地減少了搜索次數(shù)，并較好地解決了島和洞存在的問(wèn)題，實(shí)際應(yīng)用價(jià)值較高。

1 已有的典型算法

蟲隨法是一種常見方法，它的基本思路是：一只理想的小蟲從背景區(qū)域向目標(biāo)區(qū)域前進(jìn)，當(dāng)由背景區(qū)域跨入目標(biāo)區(qū)域時(shí)向左轉(zhuǎn)，當(dāng)由目標(biāo)區(qū)域跨入背景區(qū)域時(shí)向右轉(zhuǎn)，直到回到起點(diǎn)，便得到目標(biāo)物體的輪廓結(jié)果(見圖1)。

圖1 蟲隨法跟蹤邊界

蟲隨法概念明確，算法簡(jiǎn)單，適合于四連通區(qū)域[8]，但卻存在小蟲易“迷路”而陷入死循環(huán)，最終回不到起點(diǎn)的問(wèn)題，而且該方法中邊界定義與出發(fā)點(diǎn)有關(guān)，受到了較大的限制。

光柵掃描法通過(guò)選定的閾值，按照固定的掃描線和規(guī)定的掃描順序進(jìn)行掃描。先從熒光屏左上角開始，向右掃一條水平線，然后迅速地回掃到下一行的位置，再掃第二條水平線，照此固定的路徑及順序掃下去，直到最后一條水平線，即完成了整個(gè)圖像的掃描，得到邊界輪廓。

但是光柵法需要不斷調(diào)整閾值，對(duì)掃描方向有很大依賴性，而且需要多次進(jìn)行行掃描和列掃描，工作量大，得到的輪廓也不太準(zhǔn)確[9]。

2 改進(jìn)后的算法

2.1 算法說(shuō)明

本文提出的算法結(jié)合了蟲隨法和光柵掃描法的優(yōu)點(diǎn)，并做了相應(yīng)的改進(jìn)，使得搜索的速度大大提高，并針對(duì)島和洞提出了解決方法。算法思路如下：首先對(duì)目標(biāo)圖像從左上角點(diǎn)開始進(jìn)行逐行逐列地搜索，直到搜索到像素值為1的柵格，將該柵格的左上角點(diǎn)定為邊界的起始點(diǎn)，邊界前進(jìn)方向向右，然后按照以下跟蹤規(guī)則進(jìn)行跟蹤，直到跟蹤的邊界回到起始點(diǎn)為止。

跟蹤規(guī)則：如圖2所示，P為當(dāng)前柵格，箭頭所指為當(dāng)前邊界前進(jìn)方向，P1、P2為共享沿著當(dāng)前前進(jìn)方向下一單位距離線段的兩個(gè)柵格。如果在前進(jìn)方向右側(cè)的P1為0，則前進(jìn)方向改為當(dāng)前前進(jìn)方向順時(shí)針旋轉(zhuǎn)90°所指的方向；如果P1為1，而在前進(jìn)方向左側(cè)的P2為0，則前進(jìn)方向不變；如果P1、P2都為1，則前進(jìn)方向改為當(dāng)前前進(jìn)方向逆時(shí)針旋轉(zhuǎn)90°所指的方向。

圖2 跟蹤規(guī)則判定

對(duì)于島和洞，則將它們歸類，然后對(duì)每種不同情況分別進(jìn)行跟蹤，具體跟蹤方法見算法實(shí)現(xiàn)部分。

2.2 算法編程實(shí)現(xiàn)

1)備份一個(gè)相同的二值圖像，接下來(lái)算法中所有對(duì)圖像的修改操作都將在“備份圖”上進(jìn)行，而原圖的作用僅僅是在確定下一個(gè)邊界點(diǎn)的過(guò)程中，用來(lái)比對(duì)，以明確搜索規(guī)則。

2)將“備份圖”中完全內(nèi)部的值為1的柵格(四鄰域中的內(nèi)部柵格)置為0，如圖3(a)所示。

3)從上到下，從左到右依次搜尋“備份圖”，直到找到第一個(gè)值為1的柵格，如果沒(méi)有找到，則搜索結(jié)束，如果有，記錄下該柵格的左上角點(diǎn)P0，并判斷是否是島和洞，如果是，轉(zhuǎn)5)。定義向前搜索的方向?yàn)镽otation，其中，前進(jìn)方向向右時(shí)，Rotation=0；前進(jìn)方向向上時(shí)，Rotation=1；前進(jìn)方向向左時(shí)，Rotation=2；前進(jìn)方向向下時(shí)，Rotation=3，如圖3(b)所示。開始，置Rotation=0。

圖3 算法基礎(chǔ)定義及設(shè)定

4)判斷是否回到P0點(diǎn)且搜索到的邊界點(diǎn)數(shù)目大于1，如果是，此邊界搜索完成，轉(zhuǎn)3)，開始下一邊界的搜索。如果否，此邊界繼續(xù)向前搜索。對(duì)于不同值的Rotation，有如下搜索規(guī)則：

a. Rotation=0

i.如圖4(a)所示，當(dāng)前柵格的右側(cè)柵格為0，則將當(dāng)前柵格置為0，當(dāng)前節(jié)點(diǎn)向右前進(jìn)一個(gè)柵格的距離，并將當(dāng)前節(jié)點(diǎn)添加到該邊界中，然后置Rotation=3，轉(zhuǎn)4)；

ii.如圖4(b)所示，當(dāng)前柵格的右側(cè)柵格為1，右上側(cè)柵格為0，則將當(dāng)前柵格置為0，當(dāng)前節(jié)點(diǎn)向右前進(jìn)一個(gè)柵格的距離，Rotation值不變，轉(zhuǎn)4)；

iii.如圖4(c)所示，當(dāng)前柵格的右側(cè)柵格為1，右上側(cè)柵格為1，則將當(dāng)前柵格置為0，當(dāng)前節(jié)點(diǎn)向右前進(jìn)一個(gè)柵格的距離，并將當(dāng)前節(jié)點(diǎn)添加到該邊界中，然后置Rotation=1，轉(zhuǎn)4)。

b. Rotation=1

將Rotation=0的各種情況分別逆時(shí)針旋轉(zhuǎn)90°即可得到對(duì)應(yīng)情況，如圖4(d)、圖4(e)、圖4(f)所示，此處不再贅述。

c. Rotation=2

將Rotation=0的各種情況分別逆時(shí)針旋轉(zhuǎn)180°即可得到對(duì)應(yīng)情況，如圖4(g)、圖4(h)、圖4(i)所示，此處不再贅述。

d. Rotation=3

將Rotation=0的各種情況分別逆時(shí)針旋轉(zhuǎn)270°即可得到對(duì)應(yīng)情況，如圖4(j)、圖4(k)、圖4(l)所示，此處不再贅述。

圖4 確定下一邊界點(diǎn)時(shí)的各種判定情況

5)對(duì)于島和洞，有如下搜索規(guī)則：

a.如圖5(a) 所示，島洞在當(dāng)前搜索柵格的右側(cè)，則將當(dāng)前節(jié)點(diǎn)向右前進(jìn)一個(gè)柵格的距離，并將當(dāng)前節(jié)點(diǎn)作為新的島洞邊界的起始節(jié)點(diǎn)，然后置Rotation=3，轉(zhuǎn)4)；

b.如圖5(b) 所示，島洞在當(dāng)前搜索柵格(P)的下側(cè)，則將當(dāng)前節(jié)點(diǎn)向下前進(jìn)一個(gè)柵格的距離，并將當(dāng)前節(jié)點(diǎn)作為新的島洞邊界的起始節(jié)點(diǎn)，然后置Rotation=3，轉(zhuǎn)4)；

c.如圖5(c) 所示，島洞在當(dāng)前搜索柵格的左側(cè)，則將當(dāng)前節(jié)點(diǎn)作為新的島洞邊界的起始節(jié)點(diǎn)，然后置Rotation=2，轉(zhuǎn)4)；

d.如圖5(d) 所示，島洞在當(dāng)前搜索柵格的上側(cè)，則將當(dāng)前節(jié)點(diǎn)作為新的島洞邊界的起始節(jié)點(diǎn)，然后置Rotation=0，轉(zhuǎn)4)；

e.如圖5(e) 所示，島洞的邊界寬度處為一個(gè)柵格，且在四鄰域上閉合(即該邊界的所有柵格在四鄰域上有且僅有2個(gè)為空)，則取邊界的起始柵格的右下角點(diǎn)為新邊界線的起始點(diǎn)，置Rotation=3，轉(zhuǎn)4)。

圖5 島和洞的處理

2.3 值得注意的細(xì)節(jié)問(wèn)題

1)當(dāng)追蹤到的邊界位于整幅二值圖像的邊緣時(shí)，就會(huì)發(fā)生數(shù)組越界的情況，導(dǎo)致追蹤的面閉合不了[10]。解決辦法：遇到這種情況，就需要擴(kuò)大二值圖像，使其向四周各延伸一個(gè)柵格，用0值填充。此時(shí)，二值圖像的行列數(shù)均增加2。

2)當(dāng)整幅二值圖像很大時(shí)，追蹤結(jié)束后，可以統(tǒng)計(jì)每個(gè)追蹤到的多邊形包含的柵格數(shù)目，如果數(shù)目小于一定的閾值(根據(jù)不同的研究需要制定)，可以將該多邊形視為小圖斑或者噪點(diǎn)，予以去除。

圖6 特殊情況的處理

3)本文提出的算法雖然能解決大部分的島洞問(wèn)題，但是對(duì)于一些很特殊的情況(如圖6(a) 所示)，追蹤出來(lái)的邊界也不是很理想(如圖6(b)所示)，這是因?yàn)楸舅惴ㄊ腔谒泥徲虻模赃@種情況并不視為島洞。這就需要在追蹤結(jié)束后進(jìn)行一些操作，比如將自相交的點(diǎn)向多邊形外邊進(jìn)行一點(diǎn)移位(如圖6(c)所示)。

4)本算法最后得到的邊界中，普通邊界和島的邊界是順時(shí)針構(gòu)造的，而洞的邊界則是逆時(shí)針構(gòu)造的。

3 實(shí)驗(yàn)結(jié)果及算法應(yīng)用

本文選用了經(jīng)過(guò)處理的某地區(qū)中學(xué)分布圖和酒店分布圖作為實(shí)驗(yàn)對(duì)象，將其二值化得到二值圖像(見圖7(a))，然后運(yùn)用本文的搜索算法搜索出其邊界(見圖7(b))。

圖7 實(shí)驗(yàn)對(duì)象及實(shí)驗(yàn)結(jié)果

從圖上可以看出，搜索出的邊界基本符合原來(lái)的輪廓。對(duì)于面積特別小的圖癍，視為噪點(diǎn)予以去除，且對(duì)搜索出的邊界進(jìn)行了光滑處理，可視化效果較好。另外，在搜索次數(shù)上與文獻(xiàn)[6]提出的算法進(jìn)行了對(duì)比。文獻(xiàn)[6]采用的算法共搜索了4 128和5 619次，而本文提出的算法僅搜索了2 548和3 604次，搜索效率提高了38.28%和35.86%，其中文獻(xiàn)[6]的搜索數(shù)據(jù)是通過(guò)統(tǒng)計(jì)其算法在各種邊界點(diǎn)情況下平均搜索次數(shù)后與其邊界點(diǎn)相乘得到，本文的搜索數(shù)據(jù)是直接統(tǒng)計(jì)搜索次數(shù)得到的。

在實(shí)際生活中，經(jīng)常遇到選址問(wèn)題，例如，已經(jīng)有某個(gè)地區(qū)的所有學(xué)校的位置數(shù)據(jù)，現(xiàn)在需要根據(jù)教育情況劃定幾個(gè)教育集中區(qū)域，以期落實(shí)教育改革情況或者建設(shè)基礎(chǔ)設(shè)施以改善教學(xué)質(zhì)量?；诖耍疚奶岢鲆环N應(yīng)用模式。

首先根據(jù)這些離散點(diǎn)的位置，計(jì)算出整個(gè)區(qū)域的核密度估計(jì)(核密度估計(jì)是在概率論中用來(lái)估計(jì)未知的密度函數(shù)，屬于非參數(shù)檢驗(yàn)方法之一[11]。由于核密度估計(jì)方法不利用有關(guān)數(shù)據(jù)分布的先驗(yàn)知識(shí), 對(duì)數(shù)據(jù)分布不附加任何假定, 是一種從數(shù)據(jù)樣本本身出發(fā)研究數(shù)據(jù)分布特征的方法, 因而, 在統(tǒng)計(jì)學(xué)理論和應(yīng)用領(lǐng)域均受到高度的重視)，如圖8所示。如果這些離散點(diǎn)有屬性上的重要與非重要之分，則賦予不同的權(quán)重再計(jì)算。之后根據(jù)核密度估計(jì)的不同，選定一定的閾值，將整個(gè)區(qū)域二值化，再根據(jù)本文提出的邊界追蹤算法提取所需的區(qū)域，最后進(jìn)行一定的后期處理，如平滑邊界，去除噪點(diǎn)等，就得到了最終的結(jié)果，如圖7所示。不難看出，篩選出的區(qū)域都是目標(biāo)點(diǎn)集中的區(qū)域(重點(diǎn)區(qū)域)，且算法追蹤出的區(qū)域邊界光滑，解決了島和洞的問(wèn)題，在實(shí)際應(yīng)用中效果較好。

圖8 原始點(diǎn)數(shù)據(jù)及核密度處理結(jié)果

這種應(yīng)用模式可以應(yīng)用到各個(gè)行業(yè)中，如搶險(xiǎn)救災(zāi)中確定重災(zāi)區(qū)，先行救援；工業(yè)生產(chǎn)中確定技術(shù)密集區(qū)，加大扶持投資；日常生活中劃定商業(yè)娛樂(lè)中心，完善基礎(chǔ)設(shè)施建設(shè)等。

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

邊界追蹤是數(shù)字圖像處理、模式識(shí)別的重要內(nèi)容，也是地理信息系統(tǒng)中柵格數(shù)據(jù)向矢量數(shù)據(jù)轉(zhuǎn)換的重要保證。本文提出的算法減少了搜索次數(shù)，加快了搜索速度，搜索效率有較大程度提高，同時(shí)針對(duì)島洞問(wèn)題提供了較好的解決方案，最后根據(jù)實(shí)際問(wèn)題，提出了自己的應(yīng)用方法。實(shí)驗(yàn)表明，該算法切實(shí)可行，同時(shí)希望該應(yīng)用方法能為政府部門、商業(yè)機(jī)構(gòu)在解決一些調(diào)控、選址問(wèn)題時(shí)提供一定的參考。

[1]何麗，李嘉，鄭德華，等.基于柵格的點(diǎn)云數(shù)據(jù)的邊界探測(cè)方法[J].測(cè)繪工程,2013,22(3):69-73.

[2]CASTLEMANKR. Digital Image Processing[M]. [S.1.]:Prentice Hall,1996:309- 312.

[3]張孝燦, 潘云鶴. GIS中基于“柵格技術(shù)”的柵格數(shù)據(jù)矢量化技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2001,13(10):895-900.

[4]周凌焱，劉成龍，張強(qiáng)，等.基于深度和廣度優(yōu)先算法相結(jié)合的閉合環(huán)自動(dòng)搜索方法研究[J].測(cè)繪工程,2014，23(5)：24-28.

[5]崔鳳魁,張豐收,白露,等.二值圖像目標(biāo)鄰域點(diǎn)法邊界跟蹤算法[J].洛陽(yáng)工學(xué)院學(xué)報(bào),2001,22(1):28-34.

[6]王福生,齊國(guó)清.二值圖像中目標(biāo)物體輪廓的邊界跟蹤算法[J].大連海事大學(xué)學(xué)報(bào),2006(1):62-64.

[7]周豐樂(lè)，徐向民，肖躍,等. 一種新的二值圖像目標(biāo)輪廓跟蹤算法[J].微計(jì)算機(jī)信息,2007(6):259-261.

[8] PRATTK.數(shù)字圖像處理[M].鄧魯華,張延恒,譯.北京:機(jī)械工業(yè)出版社,2005:397-398.

[9]柳稼航,楊建峰,單新建,等.一種基于優(yōu)先搜索方向的邊界跟蹤算法[J].遙感技術(shù)與應(yīng)用,2004(19):209-213.

[10]謝順平,都金康,王杰臣.實(shí)現(xiàn)柵格圖形和圖像數(shù)據(jù)矢量化提取的游程輪廓追蹤法[J].遙感學(xué)報(bào), 2004,8(5):465-470.

[11]李存華, 孫志揮, 陳耿, 等. 核密度估計(jì)及其在聚類算法構(gòu)造中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展2004,41(10):21-28.

[責(zé)任編輯：劉文霞]

A rapid algorithm on tracing edge of binary image and its application

CHEN Wang, GUO Qing-sheng, FAN Wei, ZHANG Hang, ZHOU He-jie

(School of Resource and Environmental Sciences, Wuhan University, Wuhan 430070 , China)

The traditional tracing edge algorithms of binary image are compared with and analysed, and a new algorithm which can control the direction of the image’s outline is proposed only based on two neighboring grids. The experimental results show that in the algorithm the number of searching is fewer, identification of contour is accurate, and the problem of ‘island and hole’ is solved well. Finally, its application verifies the effectiveness of the algorithm.

binary image; tracing edge; GIS; raster data; pattern recognition

2013-12-23；補(bǔ)充更新日期：2014-09-20

國(guó)家863計(jì)劃資助項(xiàng)目(2012AA12A402)；國(guó)家自然科學(xué)基金資助項(xiàng)目(41071289，41171350)

陳 旺(1991-)，男，碩士研究生.

TP75

：A

：1006-7949(2014)12-0063-04