細小器官分割的可回溯三維種子填充新算法

許苗村，蔣先剛，李 林

(華東交通大學基礎科學學院，江西南昌330013)

目前把二維種子填充推廣到三維來進行人體器官組織的填充分割是最常見的，這種方法不但容易實現而且速度較快，但由于算法本身存在一些缺陷，如填充時在z向會進行圖像層間的向前向后填充，即反復跳躍填充，而不是由前向后填充或由后向前填充，這就大大增加了不必要的回溯和像素的判讀，降低了填充效率，同時現有的改進方法對于提高算法速度不能起到有效作用。因此本文考慮從建立交叉堆棧入手，利用填充區域像素點之間的相關性來減少組織切片間層與層之間像素點的反復跳躍填充，從而大大提高了算法的填充速度[1-5]。

為驗證本文種子填充算法的可回溯性，將對人腦中較為細小的血管進行填充提取。如選取一頭部的二維數字圖像斷層序列(共137張切片)，從中提取出血管圖像以方便分析，提取后發現由于血管分支較多，每層切片上的血管數目不同，并且存在毛細血管等細小組織以及由灰度值定義血管區域存在的二義性問題，這些無疑為帶回溯的種子填充帶來了極大的困難。為解決這些問題，在對血管特性進行仔細研究后，采用圖1中(a)，(b)分別對第44，45號原始切片圖像進行分析，圖1中(c)，(d)第44，45號切片上的血管圖像。

圖1 不同切片層面上血管的數目

1 多堆棧種子填充技術思路

由三維血管組織的拓撲關系來看，血管存在向上及向下分支而分支上又有子分支的情況，按此特性把血管分為當前填充的血管區域和分支向上的血管區域和分支向下的血管區域這3類，與此對應決定建立3個作用互補的交叉堆棧，程序設計中選取紅色為填充色。

堆棧1用于單根血管的填充。問題在于僅用灰度值定義的填充區域存在二義性，即同一灰度值可能對應于多種物質，而同一物質也可能包含不同的灰度值。這就有可能在找種子點時找到的是雜質而并非真正的種子點，所以第一個種子點將由用戶對感興趣的區域來決定。鼠標點擊切片上的血管區域來給出，如果此點在前一和后一切片上仍然滿足填充要求就繼續作為種子點或填充點，否則考慮到同一種物質一般在空間上是互相連通的，認為連通的血管每層之間必有公共點，對相鄰兩張切片上的像素進行對比。如果上一張中點(x，y)為已填充的紅色點，而在下一切片中此點為滿足填充要求的點，則把此點置為下一張切片的種子點。這樣就既考慮了連通區域像素點的相關性，又消除了填充區域的二義性問題。

堆棧2將以堆棧1彈出的最后一個點作為新的種子點，對血管向下的分支進行填充。如圖1(c)中血管1與圖1(d)中血管2，3有公共重影點，因此是互相連通的;而堆棧1只能達到對血管1，2或1，3的填充，要使所有連通區域都能被完全填充就需要繼續判斷相鄰兩張切片像素點的相關性。如果前一張上的點(x，y)為已填充過的點，而在后一張切片中此點為滿足填充要求的點，則把此點置為后一張切片的種子點壓入堆棧。由此便可完成對血管2或3及類似血管分支的填充。

堆棧3適用于對血管向上分支的填充。將圖1(c)與(d)順序交換后正好體現了這種情況，即前一切片中包含血管的分支，而后一切片中是分支融合了的血管。它以前一堆棧彈出的最后一個點作為種子點，其余種子點的尋找方法與堆棧2中相反，即如果后一切片上的點(x，y)為已填充過的點，而在前一切片中此點為滿足填充要求的點，則把此點置為前一張切片的種子點壓入堆棧，這樣便能完成對此類分支的填充。

算法對堆棧1使用一次，對堆棧2，3將多次使用，由于新種子點的選取是通過判斷相鄰兩張切片上的像素分布情況來實現的。因此當同一位置像素點在相鄰兩張切片上都已填充過時，便可有效地跳過，減少了種子點的重復壓棧及不必要的回溯。

2 算法步驟

(1)鼠標點擊處為第一個切片上的種子點(seedpos.x，seedpos.y)。

(2)種子點壓入堆棧1，結合掃描線種子填充算法。以種子點的y坐標為分界線，把填充區域分為上、下兩部分，分別對這兩部分沿掃描線對種子點的左、右兩側進行填充，直到邊界為止，記錄填充下半區域時彈出的最后一個點(x1，y1)。

(3)(x1，y1)壓入堆棧2，堆棧為空時，彈出所記錄的最后一個種子點(x2i，y2i)。

(4)(x2i，y2i)壓入堆棧3，堆棧為空時，彈出所記錄的最后一個種子點(x3i，y3i)。

(5)轉到(3)運行，用(x3i，y3i)替換(x1，y1)壓入堆棧，直到所有連通區域均被填充為止。

其中:i=1，2，3…。

3 實驗結果與分析

為驗證本文算法在入棧次數和填充時間上所做的改進，在主機主頻為2.40GHz、內存為2.0 GHz的Windows XP操作系統中使用Delphi7軟件開發平臺編程實現了二維種子填充算法、傳統三維種子填充算法和本文算法。

由于頭部的骨頭和血管有著相同或相近的灰度值，因此在沒有考慮像素之間相關性及區域連通性的二維種子填充算法和傳統三維種子填充算法下，重構出的不但有血管還包括部分骨頭和其它雜質，如圖2、圖3所示?？梢钥吹蕉S種子填充算法由于沒有考慮垂直方向的種子填充問題，因此在z向上的連通性很差，圖像出現階梯狀斷裂，而傳統的串行向兩投影方向進行的二維種子填充算法是在水平方向填充的基礎上加入了垂直方向的填充，這又難免會造成填充區域某些點的‘膨脹'，因此雖然消除了部分雜質。在z向上也基本無斷流，但仍然造成了血管的失真顯示。圖4為使用本文算法填充后重構出的血管圖像?？梢钥吹酱朔ú坏谂懦袼攸c填充二義性和連通性上達到了非常好的效果，而且填充后的血管清晰飽滿，較為逼真。

圖2 二維種子填充算法的填充效果

圖3 串行向兩投影方向的二維種子填充的填充效果

圖4 本文算法的填充效果

表1 種子填充算法中效率對比

同時從表1所給的數據也可以看出，由于減少了不必要的回溯，本文算法在入棧次數上僅為二維種子填充算法的27.6%、傳統算法的33%，填充時間上還不到傳統算法的二分之一。此外重構時間也大大縮短了，這是因為排除了不相關的雜質而減少了重構三角面片數，從而節省了時間。因此本算法無論是在入棧次數、填充時間、重構時間還是重構質量上都有較大提高，并且達到了從一個種子點出發的空間連通域的血管回溯填充，填充效果、重構效率都比較高。

[1] 陸蓓，濮英，王小華.一種新的掃描線種子填充算法[J].中國水運，2008，8(2):152-154.

[2] 蔣先剛，涂曉斌.三維模型圖形接口程序設計[J].微計算機信息，2007，23(12-1):291-293.

[3] 陳多觀.一種無重復入棧的種子填充法[J].鐵道師院學報，2002，19(2):29-31.

[4] 孫燮華.掃描線種子填充算法的改進[J].計算機工程，2000，26(12):142-143.

[5] 余臘生，沈德耀.掃描線種子填充算法的改進[J].計算機工程，2003，29(10):70-72.