一種新的邊界跟蹤算法

石 爽，曲仕茹，何 力

?

一種新的邊界跟蹤算法

石 爽，曲仕茹，何 力

（西北工業大學自動化學院，陜西西安 710072）

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

區域生長；邊界跟蹤；爬蟲；八鄰域

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

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

1 問題提出

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

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

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

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

圖1 邊界點圖組

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

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

2.1 邊界跟蹤

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

步驟如下：

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

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

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

（4）若j

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

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

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

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

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

（10）否則，轉至步驟4；

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

（12）轉至步驟3。

2.2 初始點處理

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

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

2.3 補齊斷點

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

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

3 實驗及結論

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

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

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

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

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

[2] 劉相濱, 向堅持, 陽 波. 基于八鄰域邊界跟蹤的標號算法[J]. 計算機工程與應用, 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著. 數字圖像處理[M]. 朱志剛,等譯. 北京: 電子工業出版社, 1998. 70-72.

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

[6] 李西平, 王思賢. 基于邊緣檢測技術的字符輪廓線的提取和顯示[J]. 計算機工程與應用, 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] 胡學龍, 許開宇. 數字圖像處理[M]. 北京: 電子工業出版社, 2006. 145-146.

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

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

[15] 陳慶虎, 趙 云, 劉鴻翔.一種簡單高效的二值圖像并行細化算法PABIT[J]. 武漢理工大學學報, 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

陜西省工業攻關資助項目（2008KD7-14）

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