一種新的邊界跟蹤算法

石 爽，曲仕茹，何 力

?

一種新的邊界跟蹤算法

石 爽，曲仕茹，何 力

（西北工業(yè)大學(xué)自動化學(xué)院，陜西西安 710072）

針對提取的圖像邊緣中存在非單像素和斷點的情況，提出了雙層邊界區(qū)域生長的邊界跟蹤算法。通過對中心點周圍里層點和外層點分別進(jìn)行搜索，然后把里層點和上一層中心點的外層點合并，并將并集中的點分別作為下一步搜索的中心點，循環(huán)向下搜索。同時充分考慮了起始中心點單向搜索的情況，并在一次搜索過程中完成了對斷點的補齊工作，從而彌補了“記憶爬蟲”法和八鄰域法在跟蹤分支、斷點和“厚”邊緣過程中存在的不足。實驗證明該方法效果較好。

區(qū)域生長；邊界跟蹤；爬蟲；八鄰域

區(qū)域的邊緣為圖像中灰度變化劇烈的地方，它含有豐富的信息。邊緣描述了圖像中所包含物體的輪廓，表達(dá)了物體之間的關(guān)系。邊緣在圖像高層處理中，如物體的識別、特征提取或者三維重建等都要用到邊界信息，邊緣處理的好壞直接影響圖像處理的結(jié)果。邊緣處理的前提是必須把邊緣組合成有意義的數(shù)據(jù)鏈，通過邊界跟蹤得到邊界點序列或邊界鏈碼才可以求得物體的周長、寬度、高度、輪廓的凹凸情況。

常用的邊界跟蹤方法是“爬蟲”法（輪廓跟蹤法）。文獻(xiàn)[5]對“爬蟲”法作了改進(jìn)，采用Freeman對鏈碼及方向的定義，將鏈碼以1、5為對角線分成上下兩個部分，這樣不必每次都搜索這8個像素點，算法時間復(fù)雜度有所降低。文獻(xiàn)[6]采用最近點關(guān)系準(zhǔn)則，即通過計算當(dāng)前點和其他點間的距離，選擇與當(dāng)前點距離最近的點連接。文獻(xiàn)[7]從中心點左上角開始，逆時針對八鄰域點進(jìn)行搜索，先搜索到的點作為下一搜索的中心點。文獻(xiàn)[8]為了消除輪廓跟蹤過程中斷點以及分支點的不利影響，采用遺傳算法對待定點進(jìn)行最優(yōu)搜索。

1 問題提出

常用的邊緣檢測算法中，Canny算法提取的邊緣效果較好，但其算法的時間復(fù)雜度較高，在實時圖像處理中很難接受。其它邊緣提取算子，例如Roberts算子、Sobel算子、Prewitt算子以及Laplace算子等，時間復(fù)雜度較低，但所得到的邊緣可能很“厚”，遠(yuǎn)非理想中的單像素寬，而且無論邊緣提取算法多么好，邊緣漏檢仍是不可避免的。斷邊和分支點會導(dǎo)致偽邊界的生成，噪聲和圖像灰度值差異也會產(chǎn)生的邊緣間斷。

文獻(xiàn)[9-11]的方法具有各自的局限，只能適用于某一類的圖像。光柵掃描跟蹤法通過掃描的方式將邊緣點連接起來，但很難構(gòu)成邊緣點鏈。“爬蟲”邊界跟蹤方法對于斷裂長度較大的邊緣跟蹤會失敗，“記憶爬蟲”能夠解決邊緣分支問題，但會落入“厚”邊緣和斷點的“陷阱”中。

在圖1(a)中，每個方格代表一個像素點，5、6、7、8點構(gòu)成“厚”邊緣，如果從點1開始搜索，從左上角開始，利用8鄰域逆時針?biāo)阉?，且搜索到一個8鄰域點后就更換搜索中心點，那么搜索中心點到達(dá)點5后，將會遺漏點6、7、9，搜索結(jié)果為1－2－3－4－5－8－10－11－12。如果采用每次都搜索完所有8鄰域點，那么以點5為中心點搜索時先搜索到8，接著是7，最后是6，這樣雖然不會產(chǎn)生遺漏點，但無法處理斷點的情況，如圖1(c)中，必須采用24鄰域搜索的辦法，而且每次必須搜索所有的鄰域點。

當(dāng)邊界出現(xiàn)小分支時，如圖1(b)所示，利用“爬蟲”，從點1開始，同樣按8鄰域搜索爬行，當(dāng)搜索到一個8鄰域點后就更換搜索中心點，那么搜索結(jié)果為1－2－3－4－5－6－7－9－10－11?！芭老x”落入“陷阱”中，遺失邊界點12到16。采用“記憶爬蟲”可以使其回到點7繼續(xù)向另一分支“爬行”，但它無法解決斷點的情況，如圖1(d)中，在8至13間出現(xiàn)斷點，“爬蟲”無法識別。

圖1 邊界點圖組

可見，以上提到的邊緣跟蹤算法均沒有充分考慮“厚”邊緣存在的情況下對分支和斷點等各種情況的處理。

2 邊界跟蹤、補齊斷點算法

2.1 邊界跟蹤

采用雙層邊界區(qū)域生長法可以有效地解決上面提出的問題。區(qū)域生長(region growing)的基本思想是將具有相似性質(zhì)的像素集合起來構(gòu)成區(qū)域。具體步驟是：先對每個需要分割的區(qū)域找一個種子像素作為生長的起點，然后將種子像素周圍鄰域中與種子像素具有相同或相似性質(zhì)的像素合并到這—區(qū)域中。將這些新像素當(dāng)作新的種子像素繼續(xù)進(jìn)行上面的過程，直到再沒有滿足條件的像素可被包括進(jìn)來。雙層指把搜索中心點的24個鄰域點按照里層和外層分開，把中心點的8鄰域點作為里層，剩下的16鄰域點作為外層。對于邊界，厚度一般不會超過3個像素，如果超過3個像素，必須經(jīng)過邊緣細(xì)化后才能繼續(xù)下面的工作。從左上角開始，按逆時針分別計算中心點的里層鄰域點和外層鄰域點，并把里層鄰域點和父中心點的外層鄰域點取并集，作為下一次搜索的中心點。這樣循環(huán)下去，直到所有的邊界點都被搜索完。

步驟如下：

（1）選擇初始中心點CenterPoint；

（2）如果CenterPoin是前3層點，在搜索其周圍點時，只要搜索到逆時針第一個點；

（3）否則CtClm＝本層中心點個數(shù)，j＝1；

（4）若j

（5）將搜索到的點從去除被搜索點集中去除；

（6）同深度中心點的里層點求并集a，同深度中心點的外層點求并集b；

（7）里層點集和上一深度中心點的外層點集求并集c；j++；

（8）如果某中心點的里層點和其父親節(jié)點外層點并集為空，但該中心點的外層點不為空，則調(diào)用補齊斷點程序；

（9）若a、b、c同時為空集，則搜索完畢，break；

（10）否則，轉(zhuǎn)至步驟4；

（11）按逆時針順序排列被搜索到點，計算新層中心點數(shù)目CtClm，j＝1；

（12）轉(zhuǎn)至步驟3。

2.2 初始點處理

通常任一邊界點的兩側(cè)都有點，當(dāng)設(shè)定第一個中心點，并只有按一測邊緣走向搜索才能得到順序邊界。而剛開始搜索時，除中心點外其它點均為未知點，利用里層和外層同時搜索會導(dǎo)致邊界順序同時向中心點兩側(cè)生長，所以必須對初始搜索方向進(jìn)行限制。

對初始點的里層點和外層點進(jìn)行搜索時，從中心點左上角開始，按逆時針，只分別搜索到一個點即可，然后更換中心點繼續(xù)向下搜索。這樣的搜索深度超過3時（此時新的中心點已經(jīng)超出第一個中心點的24鄰域），再按照4的步驟進(jìn)行搜索。

2.3 補齊斷點

在邊界序列中，如果不對斷點進(jìn)行修復(fù)，將給后續(xù)圖像分析帶來很多麻煩。為了降低時間復(fù)雜度，盡可能在對邊界點集合的一次排序中完成對斷點的修復(fù)。設(shè)左右和上下的相鄰像素間的距離均為1，在邊界跟蹤的搜索過程中，設(shè)同一中心點的里層點和外層點最小距離為，若>2，則認(rèn)為該處存在斷點；若里層點集為空，外層點集不為空，則同樣認(rèn)為該處存在斷點。

補其斷點采用求平均值法。在存在斷點的地方，計算中心點與外層點的坐標(biāo)算術(shù)平均值，再對該平均值取整，結(jié)果填入斷點處。

3 實驗及結(jié)論

圖2(a)中給出了一個存在斷點的物體紅外邊界圖，設(shè)網(wǎng)格的最左上角格坐標(biāo)為(1, 1)，最右下角格的坐標(biāo)為(20, 20)，以點1為初始中心點（坐標(biāo)為(5, 3)），使用八鄰域法和“記憶爬蟲”法進(jìn)行跟蹤，分別得到圖2(b)、圖2 (c)中的結(jié)果，可見，跟蹤過程被A處斷點終止。而使用雙層邊界區(qū)域生長法進(jìn)行跟蹤，只進(jìn)行一次搜索就得到圖2(d)中邊界圖像。共跟蹤了61個邊緣點，其中點4、11、15、19、21、25、42、49、51、55為修復(fù)點。

圖2 物體紅外邊界跟蹤對比

圖2(e)中給出了一個無斷點的物體紅外邊界圖。使用八鄰域法跟蹤結(jié)果如圖2(f)中所示，跟蹤掉入分支B處的“陷阱”中；使用“記憶爬蟲”法進(jìn)行跟蹤，雖然解決了分支問題，但需要跟蹤完一個分支后才能回到分支處進(jìn)行下一分支跟蹤，這樣，在“厚”邊緣C、D處的排序結(jié)果中變得雜亂無章，結(jié)果如圖2(g)中所示。而使用雙層邊界區(qū)域生長法進(jìn)行跟蹤，只進(jìn)行一次搜索就得到圖2(h)中邊界圖像，不僅解決了分支問題，而且對“厚”邊緣C、D處的點實現(xiàn)了合理排序。

綜上所述，雙層邊界區(qū)域生長法有效地對存在“厚”邊界和斷點的邊界進(jìn)行跟蹤，并在一次跟蹤中完成對邊界的修復(fù)。此外，該算法還可以擴(kuò)展到中心點的48鄰域，以適應(yīng)更大的斷點。但該方法也存在一些不足，例如它的時間復(fù)雜度要高于八鄰域法，而且在跟蹤的過程中不能完成邊緣細(xì)化的工作。這些問題將在今后的研究中致力解決。

[1] ZHANG Yujin. Image processing and analysis [M]. Beijing: Tsinghua University Press, 1999. 179-180.

[2] 劉相濱, 向堅持, 陽 波. 基于八鄰域邊界跟蹤的標(biāo)號算法[J]. 計算機(jī)工程與應(yīng)用, 2001, 37(23): 125-132.

[3] Sobel L. Neighborhood coding of binary images for fast contour following and general binary array processing [J]. Computer Graphics Image Process, 1978, 8(1): 127-135.

[4] [美]Castleman K R著. 數(shù)字圖像處理[M]. 朱志剛,等譯. 北京: 電子工業(yè)出版社, 1998. 70-72.

[5] 葛 澎. 一種快速邊緣跟蹤與提取的新算法[J]. 微電子學(xué)與計算機(jī), 2005, 22(8): 14-17.

[6] 李西平, 王思賢. 基于邊緣檢測技術(shù)的字符輪廓線的提取和顯示[J]. 計算機(jī)工程與應(yīng)用, 2001, 36(1): 52-53.

[7] Donoho D L. De-noising by soft thresholding [J]. IEEE TransInform Theory, 1995, 41(3): 613-626.

[8] 夏 濤, 陳海清, 黃士科. 基于局部灰度分析的紅外圖像輪廓跟蹤算法[J]. 紅外與激光工程, 2006, 35(2): 216-221.

[9] DEEMTER J H, DUBUF J M H. Simultaneous detection of lines and edges using compound Gabor filters [J]. International Journal of Pattern Recognition and Artificial Intelligence, 2000, 14(6): 757-777.

[10] 杜 奇, 向健勇, 袁勝春. 基于邊緣強度的紅外圖像閾值分割方法研究[J]. 紅外與激光工程, 2004, 33(3): 288-291.

[11] WANG Hongbo, ZHUANG Zhihong, ZHANG Qingtai. Infrared image segmentation algorithm in imaging guidance [J]. Infrared and Laser Engineering, 2003, 32(3): 234-238.

[12] 胡學(xué)龍, 許開宇. 數(shù)字圖像處理[M]. 北京: 電子工業(yè)出版社, 2006. 145-146.

[13] 林世毅, 蘇廣川, 陳 東, 等. 基于二步法的邊緣細(xì)化算法研究[J]. 儀器儀表學(xué)報, 2004, 25(4): 682-684.

[14] 劉明艷, 趙景秀, 孫 寧.用Prewitt算子細(xì)化邊緣[J]. 光電子技術(shù), 2006, 26(4): 259-263.

[15] 陳慶虎, 趙 云, 劉鴻翔.一種簡單高效的二值圖像并行細(xì)化算法PABIT[J]. 武漢理工大學(xué)學(xué)報, 2004, 28(2): 270-273.

A New Algorothm for Boundary Tracing

SHI Shuang, QU Shi-ru, HE Li

( Department of Automatic Control, Northwestern Polytechnical University, Xi’an Shaanxi 710072, China )

For the shortcoming of non-single pixels and broken points in the obtained image boundary, a new algorithm for boundary tracing of dual layer boundary region growing is proposed, to search inner-points and outer-points around center-points, to combine the inner-points with upper outer-points, to conduct continuous tracing with the combined points as the center-points in next search. The algorithm takes into account the one-way search from initial points, and can fill the broken points in one tracing process. Thus, it effectively makes up the defects of memory reptile method and eight neighborhood method in tracing embranchment, broken point and thick boundary. The experiments prove its effectiveness.

region growing; boundary tracing; reptile; eight neighborhood

TP 391

A

1003-0158(2011)03-0052-05

2009-03-03

陜西省工業(yè)攻關(guān)資助項目（2008KD7-14）

石 爽（1978-），男，安徽泗縣人，博士研究生，主要研究方向為交通運輸工程、圖像處理。