利用八元數矢量積改進三維區域生長算法

吳明珠WU Mingzhu

王曉蟬2WANG Xiaochan

李興民3LI Xingmin

利用八元數矢量積改進三維區域生長算法

吳明珠1WU Mingzhu

王曉蟬2WANG Xiaochan

李興民3LI Xingmin

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

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

Address Correspondence to： WU Mingzhu

E-mail： wmz419@126.com

2016-02-23

中國醫學影像學雜志

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

Chinese Journal of Medical Imaging

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

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

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

【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

準確精細的血管分割是醫學圖像三維重建與可視化及疾病診斷和手術導航的關鍵技術［1］。目前常用的醫學圖像分割方法主要分為基于區域的方法［2］、基于邊緣的方法［3-7］、基于模糊連接的方法［8-10］、基于人工神經網絡的方法［11-12］及基于活動輪廓的方法［13-14］。

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

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

1　基于八元數矢量積的三維區域生長算法

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

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

1.2 八元數乘法的矢量積表示定理 實數域上交錯的有限維可除代數只有4種：實數R、復數C、四元數H、八元數O。八元數O是由Graves和Cayley于1844—1845年發現的，是一種非交換、非結合的八維代數［20］。八元數又稱Cayley數。八元數形如：x=x0e0+x1e1+x2e2+ x3e3+x4e4+x5e5+x6e6+x7e7，其中e0、e1、e2、e3、e4、e5、e6、e7是八元數的一組基，滿足：=－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　基于八元數矢量積的三維區域生長算法

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

圖2　種子點6個鄰域

設當前點的坐標值為為（x，y，z），其像素值用f （x，y，z）表示。構造的純八元數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

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

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

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

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

2　實驗結果與分析

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

對分割結果進行三維重建得到的血管模型見圖5。為了說明算法的優勢，在相同的閾值條件，與文獻［3］中常規的區域生長算法進行對比，區域生長的結果見圖6。

圖3　S70種子點選擇

圖4　S70二維切片的分割結果

圖5　本文算法對S70肝血管分割結果

圖6　區域生長算法對S70肝血管分割結果

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

圖7　S50種子點選擇

圖8　S50二維切片的分割結果

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

圖10　區域生長算法對S50肝血管的分割結果

為了進一步驗證本文所提出算法的分割效果，本研究將醫師手工分割結果作為評價的“金標準”［24］，將上面兩組實驗數據S70和S50運用本文算法和傳統區域生長算法進行血管分割的敏感度和特異度測試，結果見表1。

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

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

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

［1］ 林強， 董平， 林嘉宇. 圖割方法綜述. 微處理機， 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］ 段先知， 丁亞軍， 錢盛友， 等. 改進型快速ICA算法與數學形態學結合的圖像分割方法. 微電子學與計算機， 2015， （2）：80-83.

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

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

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

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

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

［10］ 張玲. 基于模糊理論及其擴展的圖像分割研究及應用. 濟南： 山東大學， 2012.

［11］ 安琦， 李敏， 何玉杰， 等. 一種優化脈沖耦合神經網絡模型及在圖像分割中的應用. 計算機科學， 2014， 41（S1）： 215-217.

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

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

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

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

［16］ 許修， 鄭彩仙， 王成， 等. 基于血管增強濾波的腦部靜脈分割新方法. 中國醫療器械雜志， 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］ 李興民. 八元數分析. 北京： 北京大學， 1998.

［21］ 劉偉. 八元數及Clifford 代數在數字圖像處理中的應用. 廣州華南師范大學， 2010.

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

［23］ 宋余慶， 陳健美， 朱峰， 等. 數字醫學圖像. 北京： 清華大學出版社， 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

國家高技術研究發展計劃863計劃（2012AA 021105）；2016年廣東省創新強校工程教學改革項目（GDJG2016001）；廣州商學院應用型人才培養示范基地（zlgc2015005）。

TP391.4；R816.2