吳明珠WU Mingzhu

王曉蟬2WANG Xiaochan

李興民3LI Xingmin

利用八元數(shù)矢量積改進(jìn)三維區(qū)域生長算法

吳明珠1WU Mingzhu

王曉蟬2WANG Xiaochan

李興民3LI Xingmin

作者單位
1.廣州商學(xué)院計算機(jī)系 廣東廣州 511363
2.南方醫(yī)科大學(xué)圖書館 廣東廣州 510515
3. 華南師范大學(xué)計算機(jī)學(xué)院 廣東廣州510631

Department of Computer， Guangzhou College of Commerce， Guangzhou 511363， China

Address Correspondence to： WU Mingzhu

E-mail： wmz419@126.com

2016-02-23

中國醫(yī)學(xué)影像學(xué)雜志

2016年 第24卷 第7期：549-552，556

Chinese Journal of Medical Imaging

2016 Volume 24 （7）： 549-552， 556

針對傳統(tǒng)區(qū)域生長算法不能在有斷點的血管區(qū)域繼續(xù)生長的問題，本文提出一種新的基于八元數(shù)矢量積的三維區(qū)域生長算法，首先使用傳統(tǒng)的區(qū)域生長算法，分割出連續(xù)的血管，通過梯度計算，找到血管的邊緣，將其作為八元數(shù)區(qū)域生長的初始種子點，然后用種子點6個鄰域的灰度構(gòu)造八元數(shù)來表示種子點的特征，運(yùn)用八元數(shù)的矢量積運(yùn)算，進(jìn)一步對于噪聲等影響下的斷裂血管進(jìn)行有效的連接。對肝臟血管分割的結(jié)果表明，相對于傳統(tǒng)的區(qū)域生長算法，該算法能夠快速有效地分割出更多更精細(xì)的血管。

圖像處理，計算機(jī)輔助；算法；體層攝影術(shù)，X線計算機(jī)；肝靜脈；主動脈，腹

【Abstract】Because traditional regional growing algorithm can not continue to grow in the blood vessels which have breakpoints， we propose a new three-dimensional region growing algorithm based on octonion vector product. First， traditional regional growing algorithm is used to segment continuous blood vessels. The edges of the vessel are found by gradient calculation and used as initial seeds in the octonion growing regions. Then the six neighborhood of seeds' gray are used to construct octionions which represents the characteristics of seeds. The octonion vector product operation is used to connect the rupture vascular interfered by noise. Experimental results of the liver vessel segmentation show that the algorithm can quickly and efficiently segment more vessels compared with the traditional regional growing algorithm.

【Key words】Image processing， computer-assisted； Algorithms； Tomography， X-ray computed； Hepatic veins； Aorta， abdominal

準(zhǔn)確精細(xì)的血管分割是醫(yī)學(xué)圖像三維重建與可視化及疾病診斷和手術(shù)導(dǎo)航的關(guān)鍵技術(shù)［1］。目前常用的醫(yī)學(xué)圖像分割方法主要分為基于區(qū)域的方法［2］、基于邊緣的方法［3-7］、基于模糊連接的方法［8-10］、基于人工神經(jīng)網(wǎng)絡(luò)的方法［11-12］及基于活動輪廓的方法［13-14］。

其中基于區(qū)域的方法主要利用統(tǒng)一區(qū)域內(nèi)的相似性識別區(qū)域。Adams等［2］首先提出種子區(qū)域生長算法，該算法基于局部像素的相似性，分割出種子點鄰域中滿足某些條件的像素點，是分割連通區(qū)域的常用方法，其計算簡單，運(yùn)算速度快，在血管連續(xù)的區(qū)域能夠得到較好的分割結(jié)果。但是分割結(jié)果對種子點的選擇有很大的依賴性，而且區(qū)域生長算法在有很多斷點或者噪聲點的血管區(qū)域可能不能繼續(xù)生長，從而得不到好的分割效果。大量的研究人員致力于改進(jìn)區(qū)域生長算法［15-16］。程明等［15］根據(jù)區(qū)域生長的歷史數(shù)據(jù)以及血管方向信息，提出一種定向區(qū)域生長算法，用于肝臟血管的分割。由于醫(yī)學(xué)圖像的復(fù)雜性，單一的分割算法往往不能取得理想的分割結(jié)果。許修等［16］基于血管增強(qiáng)濾波聯(lián)合動態(tài)閾值分割和動態(tài)閾值區(qū)域生長的血管提取方法，取得了較好的分割效果。但此方法計算比較復(fù)雜，且對圖像質(zhì)量的要求較高。近年來，很多研究人員將區(qū)域生長與其他分割方法相結(jié)合取得不錯的結(jié)果［17-19］。Del Fresno等［17］首先采用區(qū)域生長分割出粗略的血管，然后使用粗略的血管模型作為構(gòu)造可形變模型的初始幾何形狀，得到較精細(xì)的分割結(jié)果。Palomera-Pérez等［18］基于醫(yī)學(xué)影像分割與配準(zhǔn)算法的研發(fā)平臺（ITK）的并行運(yùn)算，采用多尺度特征與區(qū)域生長相結(jié)合的方法，提取視網(wǎng)膜血管，在精度和速度上均有很大的改進(jìn)。Cseh［19］采用神經(jīng)網(wǎng)絡(luò)和區(qū)域生長結(jié)合的方法，在腫瘤分割中取得不錯的效果?，F(xiàn)有的區(qū)域生長算法大多未考慮醫(yī)學(xué)圖像的相鄰切片之間的相關(guān)性特點，致使算法的抗噪性較低。

由于醫(yī)學(xué)影像設(shè)備電子器件的噪聲、容積效應(yīng)、場偏移效應(yīng)等的影響，生成的醫(yī)學(xué)圖像往往含有噪聲污染，圖像信息缺失，尤其是半徑較小的血管在噪聲影響下容易出現(xiàn)斷裂。使用常規(guī)的區(qū)域生長算法，在血管斷裂的位置會停止生長，不能得到理想的分割結(jié)果。近年，高維代數(shù)理論八元數(shù)分析［20］在圖像處理中得到了重要的應(yīng)用［21-22］。劉偉［21］提出了一種基于八元數(shù)乘法幾何意義的邊緣檢測濾波器，該方法能夠提取出豐富的彩色圖像的邊緣以及特定的顏色區(qū)域，在色彩較鮮艷的彩色圖像中，取得非常好的效果。黃國恒等［22］提出一種基于八元數(shù)的彩色掌紋特征提取與識別算法，對圖像進(jìn)行二維小波分解后，在頻率域中利用八元數(shù)構(gòu)造七維向量，在掌紋提取與識別方面獲得良好的效果。本文綜合考慮CT序列中相鄰切片圖像的相關(guān)性，在空間域中利用八元數(shù)構(gòu)造種子點的六維特征向量，使用八元數(shù)的矢量積性質(zhì)，結(jié)合區(qū)域生長算法的思想，提出一種新的基于八元數(shù)矢量積的三維區(qū)域生長算法。

1　基于八元數(shù)矢量積的三維區(qū)域生長算法

本文提出的基于八元數(shù)矢量積的三維區(qū)域生長算法流程見圖1。

1.1 區(qū)域生長 區(qū)域生長的基本方法是：從一組“種子點”開始，對其鄰域進(jìn)行搜索，將其中具有與種子點性質(zhì)相似的像素合并成生長區(qū)域，直到所有鄰域點都不符合生長規(guī)則［23］。區(qū)域生長的研究重點，一方面是初始種子點的選取，另一方面是區(qū)域合并規(guī)則的設(shè)計。在醫(yī)學(xué)圖像的分割中，區(qū)域生長的常用合并準(zhǔn)則是基于種子點的灰度值，用來判斷其鄰域像素值是否在設(shè)定的波動范圍內(nèi)。如果是，則將其添加到生長區(qū)域中；否則不添加?；叶炔▌臃秶ㄟ^上下閾值設(shè)定，在CT圖像中，血管的灰度值一般在180～450。區(qū)域生長算法計算簡單，運(yùn)算速度較快，通?？梢詫⑦B通的血管樹從CT圖像中分割出來。

1.2 八元數(shù)乘法的矢量積表示定理 實數(shù)域上交錯的有限維可除代數(shù)只有4種：實數(shù)R、復(fù)數(shù)C、四元數(shù)H、八元數(shù)O。八元數(shù)O是由Graves和Cayley于1844—1845年發(fā)現(xiàn)的，是一種非交換、非結(jié)合的八維代數(shù)［20］。八元數(shù)又稱Cayley數(shù)。八元數(shù)形如：x=x0e0+x1e1+x2e2+ x3e3+x4e4+x5e5+x6e6+x7e7，其中e0、e1、e2、e3、e4、e5、e6、e7是八元數(shù)的一組基，滿足：=－1， i=1，2，...7。令W=｛（1，2，3），（1，4，5），（2，4，6），（3，4，7），（2，5，7），（6，1，7），（5，3，6）｝。則對，有：

圖1　基于八元數(shù)矢量積的三維區(qū)域生長算法

1.3 基于八元數(shù)矢量積的三維區(qū)域生長算法 傳統(tǒng)的區(qū)域生長算法一般只考慮種子點本身的灰度信息。算法運(yùn)行過程中，根據(jù)相似性準(zhǔn)則對種子點周邊的像素進(jìn)行相似性判斷，如果相似就加入到分割區(qū)域中，最終的算法結(jié)果是一個或多個由相似像素組成的連通區(qū)域。因此，對于因噪聲而斷裂的血管不能合并進(jìn)來，導(dǎo)致分割的精細(xì)程度不夠高。另外，生長過程本身也未考慮到血管結(jié)構(gòu)及走向，因此有一定的弊端。而將八元數(shù)與區(qū)域生長的思想結(jié)合起來能克服上述缺點，并能分割出更細(xì)小的、不連續(xù)的血管。本文針對血管可能不連續(xù)的區(qū)域，使用種子點鄰域的灰度信息表示種子點的特征，運(yùn)用八元數(shù)的矢量積表示定理，判斷該點是否為血管上的點。具體做法是：選擇種子點的上、下、左、右、前、后6個鄰域的像素值，構(gòu)造一個純八元數(shù)，并將其單位化，作為該種子點的特征向量。即一個點對應(yīng)于一個六維的特征向量。6個鄰域定義見圖2，對于第N張切片中的點P，取與其相鄰切片中的上、下2個點和當(dāng)前切片中的前、后、左、右4個點的灰度值，構(gòu)成純八元數(shù)，每一分量除以八元數(shù)自身的模，得到單位純八元數(shù)。

圖2　種子點6個鄰域

設(shè)當(dāng)前點的坐標(biāo)值為為（x，y，z），其像素值用f （x，y，z）表示。構(gòu)造的純八元數(shù)Oseed如下所示：

Oseed= f （x，y， z-1）e1+ f （x， y， z+1）e2+ f （x-1，y， z）e3+ f （x+1，y， z）e4+ f （x， y-1， z）e5+ f （x， y+1， z）e6

對其進(jìn)行單位化得到種子點的特征向量O如下，用f1， f2，…，f6 表示Oseed的每一分量。

選擇初始種子點后，對種子點的鄰域進(jìn)行搜索，如果搜索點的6個鄰域組成的單位純八元數(shù)特征向量與當(dāng)前種子點特征向量的內(nèi)積等于或接近1，則將該點添加到種子點區(qū)域，直到所有的點都不滿足條件。

由上述描述可知，對于每個點的判斷，都需要計算其6個鄰域的像素值，并構(gòu)造八元數(shù)，進(jìn)行八元數(shù)的單位化。另外由于醫(yī)學(xué)圖像本身就有很大的數(shù)據(jù)量，算法的運(yùn)算時間會很長，不能滿足實際的應(yīng)用需要，尤其是實時的手術(shù)導(dǎo)航。考慮到常規(guī)區(qū)域生長法在血管連續(xù)區(qū)域的分割效果較好，基于八元數(shù)矢量積的區(qū)域生長在血管斷裂的位置能夠發(fā)揮較大功效，所以本文首先使用1.1節(jié)介紹的常規(guī)區(qū)域生長算法，分割出連續(xù)的血管，通過梯度計算，找到血管的邊緣，即有可能存在血管斷裂的位置，作為八元數(shù)矢量積區(qū)域生長的初始種子點，進(jìn)一步分割可能斷裂的血管。具體算法流程如下：

記L（seeds）為區(qū)域生長算法的種子點列表，L （octseeds）為基于八元數(shù)矢量積表示的區(qū)域生長算法的種子點列表，R（output）為分割區(qū)域。首先初始化L（seeds），L（octseeds）和R（output）為空。①輸入DICOM格式的K張M×N的CT序列圖像，體數(shù)據(jù)大小為 M×N×K；在血管區(qū)域交互式選擇一個種子點，并添加到L（seeds）中。②從L（seeds）中取出一個種子點作為當(dāng)前種子點，搜索當(dāng)前種子點的26鄰域，判斷像素值是否在血管的灰度值范圍內(nèi)。如果在，則將其添加到L（seeds）中，并將分割區(qū)域R（output）中的相應(yīng)位置的像素值置為255。③循環(huán)執(zhí)行②，直到L（seeds）為空。④通過梯度計算，找出當(dāng)前分割區(qū)域R（output）中的血管邊緣，添加到L（octseeds）中。⑤從L（octseeds）中取出一個種子點作為當(dāng)前種子點，取當(dāng)前種子點的6個鄰域像素值，構(gòu)造單位純八元數(shù)。搜索當(dāng)前種子點的26鄰域作為當(dāng)前分割點，計算當(dāng)前分割點的八元數(shù)特征向量，并與種子點的特征向量做內(nèi)積。判斷內(nèi)積值與1的差值是否在給定范圍內(nèi)。如果是，則將當(dāng)前分割點添加到L（octseeds）中，并將分割區(qū)域R（output）中的相應(yīng)位置的像素值置為255。⑥循環(huán)執(zhí)行⑤，直到L（octseeds）為空。輸出的R（output）則為最終的分割結(jié)果。

2　實驗結(jié)果與分析

本算法是在Windows7 操作系統(tǒng)上，使用Visual Studio編程工具來實現(xiàn)。為了分析算法對醫(yī)學(xué)圖像的分割效果，驗證是否能夠達(dá)到血管分割的目的，取南方醫(yī)科大學(xué)珠江醫(yī)院提供的2套腹部CT序列作為測試圖像。第一套數(shù)據(jù)S70是對肝靜脈的造影數(shù)據(jù)，大小為512×512×336。第二套數(shù)據(jù)S50是對主動脈的造影數(shù)據(jù)，大小為512×512×365。對于S70，在體數(shù)據(jù)的其中一張切片中選擇種子點，見圖3，紅色標(biāo)記點為種子點，其像素值為284，并設(shè)置血管的上下閾值為［180，380］。種子點特征向量與分割點特征向量的內(nèi)積與1的差的絕對值小于0.005。分別使用本文算法與區(qū)域生長算法分割后，取選擇種子點的切片結(jié)果見圖4，綠色部分為分割結(jié)果。

對分割結(jié)果進(jìn)行三維重建得到的血管模型見圖5。為了說明算法的優(yōu)勢，在相同的閾值條件，與文獻(xiàn)［3］中常規(guī)的區(qū)域生長算法進(jìn)行對比，區(qū)域生長的結(jié)果見圖6。

圖3　S70種子點選擇

圖4　S70二維切片的分割結(jié)果

圖5　本文算法對S70肝血管分割結(jié)果

圖6　區(qū)域生長算法對S70肝血管分割結(jié)果

以同樣的方法對S50數(shù)據(jù)進(jìn)行分割。在圖7所示的切片中選擇種子點，種子點的像素值為364：血管的閾值范圍設(shè)置為［180，450］。種子點所在切片的分割結(jié)果見圖8。對其進(jìn)行三維重建后如圖9所示，使用同樣的閾值進(jìn)行區(qū)域生長分割，三維重建后的模型見圖10。

圖7　S50種子點選擇

圖8　S50二維切片的分割結(jié)果

圖9　本文算法對S50肝血管的分割結(jié)果

圖10　區(qū)域生長算法對S50肝血管的分割結(jié)果

為了進(jìn)一步驗證本文所提出算法的分割效果，本研究將醫(yī)師手工分割結(jié)果作為評價的“金標(biāo)準(zhǔn)”［24］，將上面兩組實驗數(shù)據(jù)S70和S50運(yùn)用本文算法和傳統(tǒng)區(qū)域生長算法進(jìn)行血管分割的敏感度和特異度測試，結(jié)果見表1。

表1　兩種算法的分割效果評價

由上述實驗結(jié)果可見，本文提出的基于八元數(shù)矢量積的三維區(qū)域生長算法對CT序列圖像的分割敏感度和特異度均相對較高，說明有較好的效果，特別適用于肝臟中血管的分割，相對于區(qū)域生長算法，能夠分割出更多更精細(xì)的血管。而在運(yùn)算時間上，相同的機(jī)器配置環(huán)境下對于S70數(shù)據(jù)，區(qū)域生長算法的運(yùn)算時間為25 s，本文算法時間為40 s，時間消耗不大，能夠滿足實際應(yīng)用需求。故基于八元數(shù)矢量積的三維區(qū)域生長算法在CT圖像的肝臟血管分割中具有較大的優(yōu)勢。

本文使用八元數(shù)這一高維的數(shù)學(xué)工具，在計算過程中綜合考慮多個特性，與少量特性進(jìn)行處理的結(jié)果相比有明顯的優(yōu)勢，相對于傳統(tǒng)的血管分割算法，提高了三維重建圖像的精度，運(yùn)算時間也較短。種子點特征向量的構(gòu)造結(jié)合了血管的結(jié)構(gòu)特征，對于斷裂或噪聲污染的血管具有很好的適用性。

［1］ 林強(qiáng)， 董平， 林嘉宇. 圖割方法綜述. 微處理機(jī)， 2015，36（1）： 35-39.

［2］ Adams R， Bischof L. Seeded region growing. Pattern Analysis and Machine Intelligence， IEEE Transactions on Pattern Analysis and Machine Intelligence， 1994， 16（6）： 641-647.

［3］ Zanaty EA， Asaad A. Probabilistic region growing method for improving magnetic resonance image segmentation. Conn Sci，2013， 25（4）： 179-196.

［4］ 段先知， 丁亞軍， 錢盛友， 等. 改進(jìn)型快速ICA算法與數(shù)學(xué)形態(tài)學(xué)結(jié)合的圖像分割方法. 微電子學(xué)與計算機(jī)， 2015， （2）：80-83.

［5］ 夏菁， 張彩明， 張小峰， 等. 結(jié)合邊緣局部信息的FCM抗噪圖像分割算法. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2014，26（12）： 2203-2213.

［6］ 王斌， 李潔， 高新波. 一種基于邊緣與區(qū)域信息的先驗水平集圖像分割方法. 計算機(jī)學(xué)報， 2012， 35（5）： 1067-1072.

［7］ 呂曉琪， 范運(yùn)洲， 谷宇， 等. 基于人工交互分水嶺區(qū)域合并的醫(yī)學(xué)圖像分割研究. 中國醫(yī)學(xué)影像學(xué)雜志， 2010， 18（6）：516-520.

［8］ 杜艷新， 葛洪偉， 肖志勇. 基于模糊連接度的近鄰傳播聚類圖像分割方法. 計算機(jī)應(yīng)用， 2014， 34（11）： 3309-3313.

［9］ 周子又， 劉奇， 任靜. 基于MRI腦腫瘤的濾波方法與分割技術(shù)對比研究. 中國醫(yī)學(xué)影像學(xué)雜志， 2015， 23（7）： 553-556， 560.

［10］ 張玲. 基于模糊理論及其擴(kuò)展的圖像分割研究及應(yīng)用. 濟(jì)南： 山東大學(xué)， 2012.

［11］ 安琦， 李敏， 何玉杰， 等. 一種優(yōu)化脈沖耦合神經(jīng)網(wǎng)絡(luò)模型及在圖像分割中的應(yīng)用. 計算機(jī)科學(xué)， 2014， 41（S1）： 215-217.

［12］ 周東國， 高潮， 郭永彩. 一種參數(shù)自適應(yīng)的簡化 PCNN 圖像分割方法. 自動化學(xué)報， 2013， 40（6）： 1191-1197.

［13］ 孟紅波， 王昌明， 包建東. 用于圖像分割的魯棒的區(qū)域活動輪廓模型. 計算機(jī)科學(xué)， 2014， 41（6A）： 207-210.

［14］ 楊東亮， 鄧廷權(quán)， 戴家樹. 基于模糊連接度的交互式活動輪廓模型. 計算機(jī)應(yīng)用研究， 2014， 31（10）： 3181-3183， 3195.

［15］ 程明， 黃曉陽， 黃紹輝， 等. 定向區(qū)域生長算法及其在血管分割中的應(yīng)用. 中國圖象圖形學(xué)報， 2011， 16（1）： 44-49.

［16］ 許修， 鄭彩仙， 王成， 等. 基于血管增強(qiáng)濾波的腦部靜脈分割新方法. 中國醫(yī)療器械雜志， 2013， 37（4）： 240-243， 247.

［17］ Del Fresno M， Vénere M， Clausse A. A combined region growing and deformable model method for extraction of closed surfaces in 3D CT and MRI scans. Comput Med Imaging Graph， 2009， 33（5）： 369-376.

［18］ Palomera-Pérez MA， Martinez-Perez ME， Benítez-Pérez H， et al. Parallel multi-scale feature extraction and region growing：application in retinal blood vessel detection. IEEE Trans Inf Technol Biomed， 2010， 14（2）： 500-506.

［19］ Cseh Z. Neural networks combined with region growing techniques for tumor detection in ［18F］-fluorothymidine dynamic positron emission tomography breast cancer studie. SPIE， 2013： 8670.

［20］ 李興民. 八元數(shù)分析. 北京： 北京大學(xué)， 1998.

［21］ 劉偉. 八元數(shù)及Clifford 代數(shù)在數(shù)字圖像處理中的應(yīng)用. 廣州華南師范大學(xué)， 2010.

［22］ 黃國恒， 李興民. 基于八元數(shù)的彩色掌紋特征提取與識別算法. 計算機(jī)工程， 2012， 38（22）： 28-33.

［23］ 宋余慶， 陳健美， 朱峰， 等. 數(shù)字醫(yī)學(xué)圖像. 北京： 清華大學(xué)出版社， 2008： 99.

［24］ Hooshyar S， Khayati R. Retina vessel detection using fuzzy ant colony algorithm. Canadian Conference Computer and Robot Vison， 2010： 239-244.

（本文編輯 張建軍）

Improvement of Three-dimensional Region Growing Algorithm Using Octonion Vector Product

10.3969/j.issn.1005-5185.2016.07.020

吳明珠

2015-12-13

國家高技術(shù)研究發(fā)展計劃863計劃（2012AA 021105）；2016年廣東省創(chuàng)新強(qiáng)校工程教學(xué)改革項目（GDJG2016001）；廣州商學(xué)院應(yīng)用型人才培養(yǎng)示范基地（zlgc2015005）。

TP391.4；R816.2