一種基于腦血管圖像特征的快速邊界跟蹤算法

（蘇州大學 智能信息處理及應用研究所， 江蘇 蘇州 215006）

摘 要：在處理復雜的腦血管圖像時，經典的邊界跟蹤算法暴露出邊界精度不高、邊界不夠平滑，且速度不盡人意等缺點。提出了一種新的快速邊界跟蹤算法，該算法在分析腦血管邊緣垂直細節遠多于水平細節的特征基礎上，結合方向記憶選擇搜索方向，并在不同的搜索方向上賦予不同的權值，最終得到下一個邊界點。實驗表明：該算法提取的腦血管邊界平滑、速度快，適合腦血管圖像的邊界提取，為下一步的腦血管形狀特征提取及表示提供了精確的數據準備。

關鍵詞：邊界跟蹤; 方向記憶; 八鄰域; 腦血管圖像

中圖分類號：TP391.41文獻標志碼：A

文章編號：1001-3695(2009)04-1569-03

Rapid boundary tracking algorithm based on cerebrovascular image feature

SUN Xiao-ping， WU Jian， ZHAI Hai-tao， CUI Zhi-ming

（ Institute of Intelligent Information Processing Application， Soochow University， Suzhou Jiangsu 215006， China）

Abstract:When dealing with complex brain vascular images， classic boundary tracking algorithm exposed some disadvantages such as boundary was not high enough smooth， accuracy was limited and its speed was unsatisfied. This paper proposed a new rapid boundary tracking algorithm to solve those problems. Analysed the feature of cerebral vascular image edge that vertical details were more than horizontal details. Based on this feature， determined next border point with memory direction of the search options and different weights to different search directions. Experimental results show the proposed algorithm can get smooth boundary and its performance is enhanced greatly. For the next phase of cerebral vascular shape and feature extraction， the new algorithm provides accurate data.

Key words： boundary tracking; direction memory; eight neighborhood; cerebrovascular image

在圖像識別領域中，為了獲得物體的周長和寬度、高度及輪廓的凹凸等形狀特征，必須借助邊界點序列或鏈碼。邊界跟蹤算法在圖像識別中能夠很好地提取邊界點序列和鏈碼，是模式識別領域的底層算法，其提取的邊界精度和速度對形狀特征描述及后續的識別和理解有著很大的影響[1]。

常見的邊界跟蹤算法如八鄰域邊界跟蹤算法，都是基于當前點的所有鄰域點按照某種方向準則搜索每個鄰域點，確定下一個邊界點[2]。在處理腦血管圖像時，由于腦血管的復雜性很難保證其性能，容易造成血管邊界粗糙、精度不高；且由于該算法搜索所有的鄰域點，計算量較大。

本文提出的基于腦血管圖像特征的快速邊界跟蹤算法從跟蹤算法的效率和精度出發，根據腦血管圖像的固有特征及當前點和上一個邊界點的位置信息選擇搜索方向，并賦予不同搜索方向上不同的權值，結合梯度信息選擇下一個邊界點，較好地解決了腦血管圖像的邊界提取問題，為腦血管識別及理解提供了基礎。

1 腦血管圖像信號分布特征

腦血管部位在整個圖像中呈垂直分布，如圖1所示。整幅圖像背景區域較大，主要細節集中在腦血管區域，而細節的主要方向為垂直方向。所以說腦血管圖像的主要信號表現為垂直方向，水平信號比較少。

腦血管的邊界實質上是腦血管區域的信號和背景信號在灰度值不連續的結果，而這種不連續可以利用導數檢測出來。本文利用不同方向的空域微分算子通過卷積計算導數，得到圖像的梯度圖，以此分析腦血管邊界的方向特征。

Sobel算子是效果比較好的一種算子，圖2是Sobel算子的兩個3×3模板。其中：水平Sobel算子對垂直邊緣有較強的響應；垂直Sobel算子圖對水平邊緣有較強的響應。

使用以上水平和垂直方向的梯度算子對腦血管圖像進行增強處理可以看出腦血管邊界信息的信號分布特征。圖3是對圖1分別使用水平Sobel算子和垂直Sobel算子的效果圖。

由圖3可以看出，腦血管邊界的垂直信號比較強，而水平信號比較弱，這就反映了腦血管邊界垂直細節遠多于水平細節。在腦血管邊界跟蹤準則中，下一個邊界點在當前點的垂直位置及斜角位置的幾率大于其水平位置。根據以上分析，在邊界提取中引入方向記憶，減少跟蹤方向的個數，然后根據當前點和跟蹤方向上各點的位置關系賦予垂直方向上點較大的權值，可以使得邊界更加逼近腦血管真實邊界，從而得到的腦血管邊界會更加精確，且時間復雜度降低、效率提高。

2 基于圖像特征的邊界跟蹤

邊界跟蹤的基本原理是：先根據某些嚴格的探測準則找出目標物體邊界上的一個像素，再根據這個像素的某些特征用一定的跟蹤準則找出目標物體的其他像素。因此其主要過程包括探測過程和跟蹤過程。不同算法的差異性主要體現在跟蹤過程，尤其是如何根據當前點判斷下一步的跟蹤方向，這是邊界跟蹤算法的核心[3]。

2.1 基于梯度算子的八鄰域邊界跟蹤算法

八鄰域邊界跟蹤算法是最常用的邊界跟蹤算法，其基本思路是：下一個邊界點必在當前點的八鄰域內。首先找到位圖區域左上角的一個邊界點作為搜索起點，按逆時針方向自上而下、從左到右搜索其八鄰域，按照某種依據找到下一個邊界點；然后以此邊界點為當前點繼續搜索。不斷重復上述過程，直到回到搜索起點[4]。

經典的八鄰域邊界跟蹤算法是以判斷鄰域點像素是否為目標像素作為跟蹤準則。該算法跟蹤準則簡單、易于實現，但在處理復雜的腦血管圖像時，容易受邊緣噪聲影響，跟蹤的邊緣不平滑、精度不高，容易陷入噪聲的陷阱中。

基于梯度算子的八鄰域邊界跟蹤算法在探測過程和跟蹤過程中均使用梯度方向作為準則[5]。首先找到圖像中梯度最大點作為邊界跟蹤的開始點，在其八鄰域內選擇梯度最大的點為下一個邊界點，同時將這個點作為下一個搜索的開始點一直搜索，直到梯度絕對值小于某個閾值，搜索停止。該算法抗噪聲能力強、邊界精度高。由于其梯度運算及尋找八鄰域梯度最大值的比較運算，使得該算法效率低。

2.2 帶有方向記憶的跟蹤準則

基于以上分析，在基于梯度算子的八鄰域邊界跟蹤算法中引入帶有方向記憶的跟蹤準則。在當前點的八鄰域跟蹤時，不僅考慮其八鄰域點的梯度大小，還要考慮上一個邊界點與當前點的位置關系。根據兩者的位置關系，選擇八鄰域中的某些點作為跟蹤方向，而不是搜索所有的八鄰域點。圖4即是當前點與其上一個邊界點的八種位置關系。其中：C為當前點；P為上一個邊界點；陰影部分則是跟蹤方向。

根據方向記憶，將基于梯度算子的八鄰域邊界跟蹤算法的跟蹤方向由原來的八個降為三個，減少了搜索的次數和梯度大小比較的次數，而且使得跟蹤的邊界平滑，在效率和精度上都有提高。

2.3 基于圖像特征及方向記憶的邊界跟蹤

基于腦血管圖像的信號分布特征及搜索方向記憶準則，結合下一個搜索邊界點與當前點的位置關系分配不同的權值，使得下一個邊界點更多地在垂直方向上選擇，符合腦血管圖像垂直信號較強的特征。

在實際處理過程中，根據當前點與其下一個點的位置不同賦予不同的權值。其基本思想是下一個點在當前點的垂直方向分配的權值最大，其次是斜角方向，水平方向最小。設P為上一個邊界點，C為當前邊界點，候選跟蹤方向的點的集合為A={x1，x2，x3}。如果C與候選跟蹤方向點的位置關系分別為垂直、斜角、水平，則賦予權值分別為Q1、Q2、Q3。本文考慮到腦血管圖像的特征，結合實驗效果將Q1、Q2、Q3分別取該點梯度值的1/2、1/3和1/4。例如C和P的方向關系如圖5所示，則其下一個邊界點的選擇依據為取max(G1×q1，G2×q2，G3×q3)的點。其中，G1、G2、G3分別為候選跟蹤點x1、x2、x3的梯度；q1=(1/3)×G1， q2=(1/4)×G2， q3=(1/3)×G3。

3 實驗結果及分析

在實驗中選擇基于像素跟蹤的邊界跟蹤算法、基于梯度跟蹤的邊界算法及本文中的算法作比較。設搜索八鄰域中一個點的時間為ts，計算梯度的時間為tg，一次比較的時間為tc。

首先分析基于當前點搜索下一個邊界點各個算法的耗時。基于像素跟蹤的邊界跟蹤算法按照一定方向搜索當前點的八鄰域，判斷像素是否為目標物體的點，從而使其搜索點的個數在1~8，其搜索下一個邊界點算法耗時為

Tp=[ts+tc，8×(ts+tc)](1)

基于梯度算子的八鄰域邊界跟蹤算法必須搜索當前點的八個鄰域點，并比較選擇梯度最大的值。該算法搜索下一個邊界點的耗時為

Tgrid=8×(ts+tg+tc)(2)

本文基于腦血管圖像特征的快速邊界跟蹤算法，由于引入方向記憶，減少了盲目搜索的次數，將鄰域點搜索的次數限定在三個，搜索下一個邊界點的耗時為

TF=3×(ts+tg+tc)(3)

由于梯度計算往往采用算子卷積運算，其計算量較大。綜上分析，在當前點搜索下一個邊界點過程中，本算法時間的復雜度介于兩者之間。

在實際使用中對圖像的梯度運算僅僅計算一次，然后儲存起來形成梯度圖像。假設最終形成邊界的點的個數為N，基于像素跟蹤的邊界跟蹤算法總的耗時為

T′p=[N(ts+tc)，8N×(ts+tc)](4)

基于梯度算子的八鄰域邊界跟蹤算法的總耗時為

T′grid=N×tg+8N(ts+tc)(5)

本文的總耗時為

T′F=N×tg+3N×(ts+tc)(6)

由以上分析可知，本文基于圖像特征的快速邊界提取算法總的時間復雜度降低，效率較高。

在算法提取邊緣的平滑度和精確度上，本文進行了兩組實驗，分別使用基于梯度的八鄰域邊界跟蹤算法和本文的邊界跟蹤算法。兩組實驗的效果如圖6、7所示。

對比兩組實驗效果圖可以看出，基于梯度的八鄰域跟蹤算法提取的邊界比較粗糙，特別是在原圖像的邊界存在噪聲的情況下，其提取的邊界有明顯的鋸齒，不夠平滑。本文算法提取的邊界比較平滑，抗噪聲的能力較基于梯度的八鄰域跟蹤算法強。表1是對兩組實驗提取邊界序列點總數的統計。

從表1可以看出，本文算法提取的邊界點序列總數少于基于梯度的八鄰域跟蹤算法，邊界精度比較高，相應的邊界序列點存儲空間減少，適合腦血管圖像的邊界跟蹤，為腦血管形狀特征的描述提供了精確的數據準備。

4 結束語

本文提出的基于腦血管圖像的快速邊界跟蹤算法使用了帶有方向記憶的跟蹤準則及基于梯度權值分配的方法。與傳統邊界跟蹤算法相比，新算法提取的腦血管邊界不僅精度高、邊界平滑，而且算法的時間復雜度大大降低，從而較好地解決了腦血管圖像的邊界跟蹤問題；同時該算法獲得邊界點序列及邊界鏈碼為腦血管形狀特征描述提供了數據準備，為腦血管識別和理解提供了基礎。

參考文獻：

［1］NIXON M S， AGUADO A S. Feature extraction and image proces-sing[M]. Burlington:Academic Press ，2002.

[2]GONZALEC R C，WOOD R E. Digital image processing [M].New Jersey:Prentice Hall，1996.

[3]史冊.對一種快速邊緣跟蹤算法的討論[J].小型微型計算機系統，2000，21(6):641-645.

[4]劉相濱，向堅持，陽波.基于八鄰域邊界跟蹤的標號算法[J].計算機工程與應用，2001， 37(23):126-127.

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

[6]任民宏.輪廓跟蹤算法的改進及在字符識別技術中的應用[J].計算機應用，2006，26(10):2378-2379.

[7]章毓晉.圖像工程(中冊):圖像分析[M].2版.北京:清華大學出版社，2005.

[8]許燕，胡書廣，商麗華，等.基于Hessian矩陣的冠狀動脈中心線的跟蹤算法[J].清華大學學報:自然科學版，2007，47(6):889-892.