基于改進蟻群算法的血管介入手術路徑規劃

高明柯, 陳一民, 張典華, 黃 晨, 李澤宇,3

(1.上海大學計算機工程與科學學院,上海200444;2.上海大學數碼藝術學院,上海201800;3.上海交通大學醫學院附屬瑞金醫院計算機中心,上海200025;4.中國電子科技集團公司第三十二研究所,上海201808)

血管介入手術是指醫生在病人皮膚上做極小切口,用微細導管等器械通過人體血管對病灶局部進行治療的方法,具有出血少、創傷小、恢復快的優點.目前,由于全國各地醫院硬件配置和人員手術水平不一,大部分的血管介入手術仍然依靠有經驗的外科醫生,通過徒手操作導管并借助X射線等醫學成像技術和虛擬現實等計算機輔助技術來完成.這類手術難度大,精度要求高,培訓周期長,并且手術過程中病人和醫生會受到X射線的輻射.在有限的技術條件下,綜合考慮醫生的操作水平、手術的危險性、術后并發癥等因素,醫生通常選用較粗的主動脈作為手術路徑,而不考慮其他可能的最優路徑.在密集分布的血管拓撲結構中,綜合考慮手術器械的粗細,血管的長度、口徑和迂曲程度等因素,必然存在一條從手術入口到病患之處的最優手術路徑.因此,為了縮短手術時間,減少術后并發癥,降低手術風險,提高手術成功率,在血管三維幾何空間中尋找一條全局最優或次優的手術路徑,對血管介入手術具有重要的理論指導和實際操作意義.

國內外對血管內路徑規劃的研究主要集中在虛擬內窺鏡[1]和血管內導航技術[2],其關鍵技術是血管中心線的提取和導航路徑的規劃.提取中心線的方法有拓撲細化法[3]、距離變換法[4]、勢能場法[5]、基于水平集法[6]和基于分割的方法[7-8]等.外科醫生利用虛擬內窺鏡技術,使用虛擬相機沿著血管中心線最大范圍地窺視血管內的情況,用以進行術前的路徑規劃,確定手術路徑.Wink等[9]采用Dijikstra算法和A星算法從預定義的代價圖像中確定最小代價路徑,并從醫學圖像數據中提取血管中心線.Belharet等[10]采用快速行進法在提取的血管中心線上搜索到兩點之間的最短路徑.但是,這些方法在搜索過程中并沒有考慮血管的其他特性.

蟻群算法是仿生學中的一種群體智能算法,是1996年Dorigo等[11]受到螞蟻覓食行為的啟發后提出的.蟻群算法在醫療方面被應用于視網膜視盤識別[12]、乳癌診斷[13]、手術安排分配[14]等.目前,國內外基于蟻群算法的三維路徑規劃主要集中在無人機[15-16]、潛水器[17]、三維管道[18-19]和機器人[20-21]等方面,而與血管介入手術相關的研究暫未見文獻報道.

針對上述問題,本工作提出在血管中心線提取的基礎上,綜合考慮導管直徑,血管長度、最小直徑、最大曲率和最大撓率等因素,引入端結點因子,改進蟻群算法中的啟發式函數和信息素更新機制,輔助外科醫生規劃手術的最優路徑.

1算法

1.1 蟻群算法

在螞蟻的覓食過程中,每一只螞蟻都會在走過的路徑上釋放一種可以與其他螞蟻進行信息交流的化學物質,稱之為信息素.隨著時間的推移,信息素會揮發,因此螞蟻爬行的路徑越短,留在路徑上的信息素濃度相對越高.螞蟻能夠發現這種信息素并感知它的濃度,并以較高的概率選中信息素濃度最高的路徑.因此,含有高濃度信息素的路徑會將更多的螞蟻吸引到這條路徑上,形成一種正反饋.基于上述原理,螞蟻便能快速地找到一條離食物源最短的路徑.

1.2 啟發式信息

啟發式函數對算法的收斂性和穩定性具有重要的影響.在蟻群算法中,啟發式信息η通常定義為兩點之間距離的倒數,即1/LI,J.基于手術的安全性和血管的特性,本工作中的路徑規劃不僅要考慮血管的長度L、血管路徑段上的最小直徑Dmin(大于導管直徑Dc,確保導管能夠穿過血管),還需要考慮血管的最大曲率Cmax和最大撓率Tmax,即血管彎曲程度和扭曲程度,啟發式地選擇較短且具有較好通過性的血管路徑.因此,本工作中啟發式信息定義為

式中:ηI,J(t)表示I(x,y,z)到J(i,j,k)的啟發信息;Dmin表示這條路徑上血管的最小直徑,Dc表示導管直徑,需滿足Dmin>Dc;LI,J表示當前路徑長度;Cmax表示當前路徑的最大曲率;Tmax表示當前路徑的最大撓率.

1.3 概率機制

1.4 信息素更新機制

初始時刻各路徑上的信息素量是相等的.螞蟻在完成一次循環后,會在相應路徑上留下信息素,但是信息素會隨著時間的推移逐漸揮發,因此要對信息素濃度進行更新.由于只針對病人手術范圍和具體手術部位進行計算機體層成像(computed tomography,CT)血管造影,因此得到的血管網絡拓撲結構不是一個完全圖,有的結點之間不存在回路,必然存在一些異常結點,即端結點VG(度數為1).若螞蟻在搜尋過程中訪問到一個端結點VG且該結點并非終點VE時,則結束搜索,定義搜索無效并刪除該結點.由于螞蟻在本次循環中不更新信息素,因此引入端結點因子γm以改進信息素更新機制.

基于上述分析,在螞蟻進入下一個循環之前,相應路徑上的信息素做如下更新:

式中:ρ(0<ρ<1)為信息素揮發系數,1?ρ為信息素殘留因子;(t,t+1)表示第m只螞蟻在第t次循環中在路徑(I,J)上留下的信息素量,(t,t+1)表示本次循環當中所有經過路徑(I,J)的螞蟻留下的信息素增量;γm為端結點因子,表示本次循環中螞蟻m在搜索過程中是否遇到端結點.考慮到全局最優的路徑情況,從手術安全和路徑最短的目的出發,本工作在螞蟻完成一次循環后再更新信息素.

1.5 信息素更新模型

信息素更新模型是蟻群算法的隨機搜索與快速收斂的重要環節.根據信息素更新模型的不同,Dorigo等[11]提出了3種蟻群系統:蟻密系統、蟻量系統和蟻周系統.由于蟻密模型不考慮路徑因素,且蟻量模型只在局部更新信息素,因此根據問題的實際情況,為了防止陷入局部最優,采用蟻周模型,即在螞蟻循環一次后更新信息素.考慮到血管直徑和導管直徑在手術中的影響,蟻周模型修改為

式中:Q為信息素強度常量,表示螞蟻在一個循環中在所經過的路徑上釋放的信息素的總量,在一定程度上影響算法的收斂速度;Lm表示第m只螞蟻在此次循環中所經過的路徑長度.

1.6 算法描述

血管介入手術路徑規劃算法的流程如圖1所示.

2實驗

實驗平臺:CPU為Intel(R)Core(TM)i5-520M,頻率2.4 GHz,內存6 GB;操作系統Windows 7旗艦版;軟件采用Visual Studio 2010,VTK,ITK,VMTK,Matlab 2012a.

2.1 血管建模及中心線提取

血管的三維建模方法主要有體繪制和面繪制兩種,而根據建模過程中是否存在模型假設,又可粗略分為基于模型和無模型兩類方法[22].由于基于模型的方法通常假設血管的剖面輪廓為圓形,而這種假設不能真實地表示任意剖面,例如,病變血管的剖面可能不是圓形.無模型的方法更忠實于初始數據,可以適用于疾病診斷等精度要求較高的場合.因此,本工作采用無模型的方法,并根據Antiga等[23]提出的通過基于水平集的方法進行分割建立血管三維模型,再用基于Voronoi圖和Eikonal方程的方法提取血管中心線,并求得最大內切球半徑.根據合作醫院放射科提供的腿部CTA數據進行建模并提取血管中心線,結果如圖2所示.

2.2 路徑規劃實驗

為了評估信息素啟發因子α,期望值啟發因子β,螞蟻數量M,信息素總量Q和信息素揮發系數ρ(0<ρ<1)對算法的影響,本工作設置7組不同的參數組合,每組做10次實驗,最后取平均,結果如表1所示.由表1可以看出:參數組合4所需的計算時間t最短,主要原因是ρ較大,即1?ρ較小,此時路徑上殘留的信息素較少,導致正反饋作用占主導地位,搜索隨機性減弱,因此收斂加快,陷入局部最優;參數組合5所需的計算時間最長,主要原因是螞蟻的數量增大,雖然加強了搜索隨機性,但是收斂減慢.通過比較,本工作最終選定α=5,β=10,M=40,Q=100,ρ=0.5,此時整個算法的平均計算時間為9.53 s.實驗設置迭代100次,起點為128,終點為53,導管直徑為0.2 mm.腿部血管網絡拓撲結構(76條路徑,131個端點)和最終得到的路徑規劃結果如圖3所示.

圖1 血管介入手術路徑規劃算法流程圖Fig.1 Flow chart of path planning algorithm for vascular access surgery

2.3 算法比較實驗

為了橫向比較算法的效率和可靠性,選取路徑規劃仿真實驗中的參數取值,導管直徑分別取值為0.5和0.2 mm.分別采用Dijkstra算法和本算法進行路徑規劃,結果如表2所示.

圖2 腿部血管中心線的提取效果示意圖Fig.2 Schematic diagram of vascular centerline extraction in legs

表1 血管介入手術路徑規劃的參數設置Table 1 Parameter setting of path planning for vascular access surgery

圖3 腿部血管的網絡拓撲結構和路徑規劃Fig.3 Network topology and path planning of vascular in legs

表2 兩種不同路徑規劃算法的比較Table 2 Comparison of two different path planning algorithms

由表2可以看出:從起點128到終點53,由于Dijkstra算法不考慮導管直徑以及血管的直徑、曲率和撓率,因此執行速度快;本算法在導管直徑為0.2 mm時,路徑規劃結果與Dijkstra算法一致,但執行時間較長;導管直徑為0.5 mm時,本算法得不到正確的路徑規劃結果,終止在點50位置.由于導管無法通過點50到點51,因此該路段的最小直徑為0.248 4 mm.實驗結果表明,Dijkstra算法雖然執行速度較快,但是實際規劃的路徑結果并不可靠,由于在導管直徑為0.5 mm時,點128到53之間不存在最優路徑,因此表明本算法比Dijkstra算法安全可靠.

3 結束語

本工作提出的基于改進蟻群的血管介入手術路徑規劃方法是一種可行的血管介入手術方案,該方法在蟻群算法的基礎上綜合考慮了導管直徑以及血管的長度、最小直徑、最大曲率和最大撓率等因素,通過引入端結點因子改進了蟻群算法的啟發式函數和信息素更新機制,最終得到了全局最優的規劃路徑.