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

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

二值圖像中目標物體邊界跟蹤的一種快速算法及其應用

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

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

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

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

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

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

1 已有的典型算法

蟲隨法是一種常見方法，它的基本思路是：一只理想的小蟲從背景區(qū)域向目標區(qū)域前進，當由背景區(qū)域跨入目標區(qū)域時向左轉，當由目標區(qū)域跨入背景區(qū)域時向右轉，直到回到起點，便得到目標物體的輪廓結果(見圖1)。

圖1 蟲隨法跟蹤邊界

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

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

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

2 改進后的算法

2.1 算法說明

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

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

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

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

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

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

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

3)從上到下，從左到右依次搜尋“備份圖”，直到找到第一個值為1的柵格，如果沒有找到，則搜索結束，如果有，記錄下該柵格的左上角點P0，并判斷是否是島和洞，如果是，轉5)。定義向前搜索的方向為Rotation，其中，前進方向向右時，Rotation=0；前進方向向上時，Rotation=1；前進方向向左時，Rotation=2；前進方向向下時，Rotation=3，如圖3(b)所示。開始，置Rotation=0。

圖3 算法基礎定義及設定

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

a. Rotation=0

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

ii.如圖4(b)所示，當前柵格的右側柵格為1，右上側柵格為0，則將當前柵格置為0，當前節(jié)點向右前進一個柵格的距離，Rotation值不變，轉4)；

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

b. Rotation=1

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

c. Rotation=2

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

d. Rotation=3

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

圖4 確定下一邊界點時的各種判定情況

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

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

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

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

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

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

圖5 島和洞的處理

2.3 值得注意的細節(jié)問題

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

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

圖6 特殊情況的處理

3)本文提出的算法雖然能解決大部分的島洞問題，但是對于一些很特殊的情況(如圖6(a) 所示)，追蹤出來的邊界也不是很理想(如圖6(b)所示)，這是因為本算法是基于四鄰域的，所以這種情況并不視為島洞。這就需要在追蹤結束后進行一些操作，比如將自相交的點向多邊形外邊進行一點移位(如圖6(c)所示)。

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

3 實驗結果及算法應用

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

圖7 實驗對象及實驗結果

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

在實際生活中，經(jīng)常遇到選址問題，例如，已經(jīng)有某個地區(qū)的所有學校的位置數(shù)據(jù)，現(xiàn)在需要根據(jù)教育情況劃定幾個教育集中區(qū)域，以期落實教育改革情況或者建設基礎設施以改善教學質量?；诖?，本文提出一種應用模式。

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

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

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

4 結束語

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

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

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

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

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

[5]崔鳳魁,張豐收,白露,等.二值圖像目標鄰域點法邊界跟蹤算法[J].洛陽工學院學報,2001,22(1):28-34.

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

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

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

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

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

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

[責任編輯：劉文霞]

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；補充更新日期：2014-09-20

國家863計劃資助項目(2012AA12A402)；國家自然科學基金資助項目(41071289，41171350)

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

TP75

：A

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