基于改進(jìn)移動(dòng)立方體算法的三維重建

胡凌燕，史康柏，徐少平，劉小平

(南昌大學(xué)信息工程學(xué)院，江西 南昌 330031)

醫(yī)學(xué)圖像三維重建技術(shù)已廣泛應(yīng)用于醫(yī)療診斷和構(gòu)建高精度虛擬三維模型等領(lǐng)域。隨著CT、MRI等醫(yī)學(xué)成像技術(shù)的飛速發(fā)展，空間數(shù)據(jù)采集量越來越大，高精度大數(shù)據(jù)的醫(yī)學(xué)影像三維繪制技術(shù)一直是研究熱點(diǎn)[1]。三維重建技術(shù)所用主要算法是三維面繪制中的移動(dòng)立方體(marching cubes， MC)算法[2]，其核心是從體數(shù)據(jù)中提取出由面片模擬的閾值面，再將所有閾值面按照一定拓?fù)潢P(guān)系組成等值面，因此也被稱為等值面提取算法。MC算法原理簡(jiǎn)單、應(yīng)用廣泛，但當(dāng)體數(shù)據(jù)密度較大時(shí)，體元產(chǎn)生的面片面積較小，導(dǎo)致面片運(yùn)算量過大，拓?fù)浣Y(jié)構(gòu)復(fù)雜，渲染時(shí)間較長(zhǎng)，影響生成組織三維模型的精確性和真實(shí)性。

目前許多虛擬現(xiàn)實(shí)平臺(tái)采用改良MC算法進(jìn)行組織器官圖像三維重建。Du等[3]采用多邊形等值面擴(kuò)展算法來遍歷相鄰立方體，使渲染時(shí)間縮短，存儲(chǔ)空間減少。Mun等[4]采用基于二次誤差度量技術(shù)的三角面片抽取方法減少了MC算法生成的三角面片數(shù)量。高峰等[5]采用種子體元衍生等值面方法，以避免對(duì)無用體元的遍歷，減少渲染時(shí)間。但這些算法重建過程中的模型精確性和交互性相對(duì)較弱，對(duì)于后續(xù)虛擬康復(fù)訓(xùn)練和醫(yī)學(xué)輔助診治的作用有待提高。Wijewickrema等[6]將改進(jìn)的MC算法用于分段離散的體數(shù)據(jù)，生成了光滑的三維曲面。Chen[7]采用等間距閾值法代替?zhèn)鹘y(tǒng)的等值面閾值法，使改進(jìn)的MC算法更適用于材質(zhì)移除的虛擬仿真平臺(tái)上。但這些相關(guān)MC算法需要生成大量的多邊形面片，拓?fù)浣Y(jié)構(gòu)復(fù)雜，計(jì)算量大。本研究提出一種基于區(qū)域增長(zhǎng)法的通用樹結(jié)構(gòu)和移動(dòng)等值點(diǎn)法的自適應(yīng)改進(jìn)MC算法。

1 原理與方法

基于區(qū)域增長(zhǎng)法的通用樹結(jié)構(gòu)和移動(dòng)等值點(diǎn)法的改進(jìn)MC算法包括基于交互式區(qū)域增長(zhǎng)算法的醫(yī)學(xué)圖像分割、建立通用樹結(jié)構(gòu)、移動(dòng)等值點(diǎn)合并三角面片法三部分，具體流程見圖1。

1.1 基于交互式區(qū)域增長(zhǎng)算法的醫(yī)學(xué)圖像分割 在醫(yī)學(xué)圖像上選取1個(gè)或多個(gè)種子點(diǎn)，種子點(diǎn)自適應(yīng)地向相鄰空間剖分，遍歷周邊體元，尋找并標(biāo)記所有與指定閾值相交的體元，生成三角面片，完成相關(guān)組織器官的分割。

選取種子點(diǎn)時(shí)，需要根據(jù)指定閾值選擇1個(gè)或多個(gè)體素。先找到需要三維建模組織輪廓的切片層，對(duì)切片層進(jìn)行邊沿輪廓提取，將邊沿點(diǎn)或相鄰切片層對(duì)應(yīng)的邊沿點(diǎn)設(shè)為種子點(diǎn)。在種子點(diǎn)處進(jìn)行相鄰8領(lǐng)域的擴(kuò)展，計(jì)算待加入像素點(diǎn)灰度值與所有種子點(diǎn)平均灰度值的差，當(dāng)其絕對(duì)值小于或等于設(shè)定的灰度值閾值時(shí)，將該像素點(diǎn)并入種子點(diǎn)區(qū)域(圖2)。當(dāng)不再有符合區(qū)域生長(zhǎng)條件的像素點(diǎn)時(shí)，終止區(qū)域增長(zhǎng)算法。至此，與閾值相交的所有體元標(biāo)記完成，三角面片全部生成，組織器官分割完畢。

圖1 基于交互式區(qū)域增長(zhǎng)法的通用樹結(jié)構(gòu)和移動(dòng)等值點(diǎn)結(jié)合的改進(jìn)MC算法流程圖

1.2 建立通用樹結(jié)構(gòu) 根據(jù)分割的相關(guān)組織器官的空間大小，確定所建通用樹結(jié)構(gòu)的層數(shù)和子節(jié)點(diǎn)個(gè)數(shù)，制定體元頂點(diǎn)索引方式。將與閾值相交的體元全部插入到創(chuàng)建的通用樹結(jié)構(gòu)中。

創(chuàng)建通用樹需要確定樹的層數(shù)和每一層的子節(jié)點(diǎn)個(gè)數(shù)。根據(jù)基于區(qū)域增長(zhǎng)算法分割好的組織器官的空間范圍，找到最小2的冪的包圍盒[8]。假設(shè)分割好的組織范圍是(200，220，240)，3個(gè)坐標(biāo)值中最大的數(shù)為240，而比240大的最小2的冪為28，通用樹算法可調(diào)用相關(guān)的庫(kù)函數(shù)來設(shè)定樹包圍盒為(256，256，256)，樹層數(shù)為8，每層子節(jié)點(diǎn)為8個(gè)。同理，若分割好的組織空間范圍為(400，300，200)，則樹包圍盒為(512，512，512)，樹層數(shù)為9，每層子節(jié)點(diǎn)數(shù)為9個(gè)。

為更直觀、形象地說明通用樹結(jié)構(gòu)的創(chuàng)建和頂點(diǎn)索引方式，以層數(shù)為8的通用樹結(jié)構(gòu)舉例說明。子節(jié)點(diǎn)的編號(hào)順序采用按0～7的二進(jìn)制位cba分配法，a=1表示沿x軸的正方向，a=0表示沿x軸的負(fù)方向；b=1表示沿y軸的正方向，b=0表示沿y軸的負(fù)方向；c=1表示沿z軸的正方向，c=0表示沿z軸的負(fù)方向。子節(jié)點(diǎn)的編號(hào)順序見圖3。

通過交互式區(qū)域增長(zhǎng)算法選定的體元中的角點(diǎn)(A，B，C)插入通用樹的步驟如下：①將A、B、C均按二進(jìn)制展開為8位(A1A2A3A4A5A6A7A8，B1B2B3B4B5B6B7B8，C1C2C3C4C5C6C7C8)；②將(A，B，C)插入n層的第An+2Bn+4Cn個(gè)子節(jié)點(diǎn)(n為0～7)。

圖2 區(qū)域增長(zhǎng)算法示意圖 A.體素灰度值圖，其中紅色區(qū)域?yàn)樵挤N子點(diǎn)； B.區(qū)域增長(zhǎng)算法的生長(zhǎng)軌跡圖，種子點(diǎn)區(qū)域沿黑色箭頭生長(zhǎng)，當(dāng)灰度值為32的種子點(diǎn)進(jìn)行相鄰區(qū)域衍生時(shí)，灰度值為33的體素符合門限灰度值的界定，因此將灰度值為33的體素并入種子點(diǎn)區(qū)域。同理，灰度值為35和34的體素也成為種子區(qū)域 圖3 通用樹子節(jié)點(diǎn)的編號(hào)順序

若這些子節(jié)點(diǎn)為空，則將(A，B，C)插入；若有些子節(jié)點(diǎn)不為空，表示子節(jié)點(diǎn)已經(jīng)有其他體素插入，則(A，B，C)跳過不為空的子節(jié)點(diǎn)，插入為空的子節(jié)點(diǎn)，以此避免多次插入遍歷，減少算法執(zhí)行時(shí)間[9]。將所選定體元的角點(diǎn)坐標(biāo)依次插入通用樹中，每個(gè)包含等值面的體元都處在樹的子節(jié)點(diǎn)上，通用樹結(jié)構(gòu)創(chuàng)建完成。

1.3 移動(dòng)等值點(diǎn)合并三角面片法 將體元棱邊上的等值點(diǎn)移動(dòng)至最近的體元頂點(diǎn)，合并存儲(chǔ)在通用樹結(jié)構(gòu)中體元內(nèi)的共面三角面片，以減少三角面片個(gè)數(shù)。選擇頂點(diǎn)代替原等值點(diǎn)，頂點(diǎn)信息儲(chǔ)存在通用樹結(jié)構(gòu)的子節(jié)點(diǎn)中，不需要計(jì)算等值點(diǎn)的坐標(biāo)和法向量，大大提高了算法執(zhí)行效率。連接新的三角面片，形成最終的三維組織模型。

每個(gè)體元對(duì)于體數(shù)據(jù)而言都是一個(gè)微小的空間，與閾值相交的體元最多含有4個(gè)三角面片，每個(gè)三角面片都很小，甚至可與顯示屏的像素點(diǎn)大小相似，因此，三角面片的頂點(diǎn)在體元插值邊上局部移動(dòng)對(duì)三維重建整體視覺化影響很小。本研究將等值點(diǎn)按照就近原則移動(dòng)到插值邊的相鄰端點(diǎn)，即體元的頂點(diǎn)；將相同平面上的小三角面片合并，形成大三角形面片，以減少共面三角面片數(shù)量和拓?fù)浣Y(jié)構(gòu)復(fù)雜性，部分三角面片合并示意圖見圖4。在傳統(tǒng)MC算法中，每次線性插值需要數(shù)次代數(shù)運(yùn)算，而本文選擇用體元頂點(diǎn)代替等值點(diǎn)，直接調(diào)用通用樹結(jié)構(gòu)中的子節(jié)點(diǎn)信息，避免了通過線性插值等算法計(jì)算等值點(diǎn)的法向量和坐標(biāo)點(diǎn)，可大大減少算法執(zhí)行時(shí)間。獲取三角面片的頂點(diǎn)的坐標(biāo)和法向量后，即可將所有新三角面片提取出來，連接成統(tǒng)一的等值面，完成基于醫(yī)學(xué)圖像的三維組織重建。

2 結(jié)果

本文算法實(shí)驗(yàn)仿真編譯采用Microsoft Visual Studio 2012和OpenGL庫(kù)，操作系統(tǒng)為64位win7系統(tǒng)，CPU為英特爾i7-6700，8.00GB內(nèi)存。數(shù)據(jù)來自1名29歲男性志愿者的腹部CT掃描圖像。采用Siemens Force雙源CT掃描儀，電壓120 kV，電流240 mA，圖像層厚1 mm，像素512×512，共361幅圖像。從該CT數(shù)據(jù)文件中提取腎臟數(shù)據(jù)(圖5)，并進(jìn)行三維重建，以便后續(xù)進(jìn)行虛擬手術(shù)。

基于CT數(shù)據(jù)，分別采用傳統(tǒng)MC算法和改進(jìn)MC算法構(gòu)建腎臟三維模型。基于傳統(tǒng)MC算法生成的腎臟三角面片拓?fù)浣Y(jié)構(gòu)復(fù)雜，三角面片數(shù)量較多；與之相比，基于改進(jìn)MC算法生成的腎臟三角面片拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單，三角面片較少(圖6)。基于傳統(tǒng)MC算法生成的腎臟三維模型表面存在許多凸凹，模型精確度較差；而基于改進(jìn)MC算法生成的腎臟模型渲染效果較好，三維模型表面平滑逼真，局部細(xì)節(jié)真實(shí)性較好(圖7)。對(duì)于同樣的CT掃描數(shù)據(jù)和相同的閾值分割提取，改進(jìn)MC算法遍歷體元個(gè)數(shù)明顯減少，生成三角面片個(gè)數(shù)減少39.20%，算法執(zhí)行效率提高37.59%(表1)。將基于改進(jìn)MC算法生成的腎臟組織三維模型應(yīng)用于虛擬手術(shù)平臺(tái)，操作者可以通過該模型進(jìn)行虛擬手術(shù)操作(圖8)。

圖4 三角面片合并示意圖 A、B.合并前的兩種共面三角面片； C、D.合并后的兩種共面三角面片

表1 傳統(tǒng)MC算法和改進(jìn)MC算法性能對(duì)比

圖5 志愿者CT圖像，白色輪廓是即將分割重建的腎臟組織 A.冠狀位； B.矢狀位； C.軸位 圖6 腎臟的同一區(qū)域的三角面片圖 A.傳統(tǒng)MC算法； B.改進(jìn)MC算法

圖7 腎臟組織三維重建效果圖 A.傳統(tǒng)MC算法； B.改進(jìn)MC算法 圖8 腎臟三維重建模型應(yīng)用于虛擬手術(shù)平臺(tái)

3 討論

本文提出了一種基于區(qū)域增長(zhǎng)法的通用樹結(jié)構(gòu)和移動(dòng)等值點(diǎn)的自適應(yīng)改進(jìn)MC算法，用于對(duì)組織器官構(gòu)建三維模型。傳統(tǒng)MC算法大多采用閾值分割方法對(duì)體數(shù)據(jù)進(jìn)行預(yù)處理，需要遍歷體數(shù)據(jù)中的所有體元，算法執(zhí)行時(shí)間較長(zhǎng)，效率較低，分割后數(shù)據(jù)細(xì)節(jié)處理不足、像素信息不全。本研究采用交互式區(qū)域增長(zhǎng)算法，依據(jù)數(shù)字圖像灰度值的相似性和連通性將圖像分割成相似的區(qū)域[10]。區(qū)域增長(zhǎng)算法設(shè)計(jì)有3點(diǎn)：生長(zhǎng)種子點(diǎn)的選取、區(qū)域生長(zhǎng)的條件和終止算法執(zhí)行的條件。該算法無需遍歷所有體元，執(zhí)行時(shí)間較短，分割后的像素信息較全，組織器官的細(xì)節(jié)處理較好。

通用樹結(jié)構(gòu)與傳統(tǒng)MC算法中直接在體數(shù)據(jù)上進(jìn)行操作運(yùn)算相比，具有以下優(yōu)勢(shì)：①通用樹的存儲(chǔ)方法利用了其結(jié)構(gòu)在空間的合理相關(guān)性，具有良好的空間利用率和查詢率，可以高效地對(duì)體元進(jìn)行并、交等集合運(yùn)算，提高了運(yùn)算和渲染效率；而傳統(tǒng)MC算法空間結(jié)構(gòu)性較差，體元之間的集合運(yùn)算時(shí)間相對(duì)較長(zhǎng)[11-12]。②體數(shù)據(jù)通用樹剖分的空間具有較好的層次性和有序性，有助于消除網(wǎng)格中多余的隱線和隱面，減少無效三角面片，提高網(wǎng)格顯示精度[13]。消隱方法的核心是排序，即將待三維重建組織的點(diǎn)、線、面按離觀察點(diǎn)的遠(yuǎn)近排序，近的三角面片遮擋較遠(yuǎn)的三角面片。通用樹結(jié)構(gòu)將與閾值相交的體元按順序排列，有助于消除隱線和隱面，從而提高三維模型的顯示精度。而傳統(tǒng)MC算法有序性較差，數(shù)據(jù)存儲(chǔ)相對(duì)散亂，網(wǎng)格顯示精度明顯弱于通用樹結(jié)構(gòu)。

本研究結(jié)果顯示改進(jìn)MC算法的三維重建效果較好，拓?fù)浣Y(jié)構(gòu)簡(jiǎn)單，三角面片個(gè)數(shù)減少，算法執(zhí)行效率有較大提高，能夠高精度地展示出腎臟細(xì)節(jié)，并成功應(yīng)用于虛擬手術(shù)平臺(tái)，為基于醫(yī)學(xué)圖像的三維重建和虛擬手術(shù)研究提供更加有效的方法。本研究所用算法渲染效果好，真實(shí)性和精確性均達(dá)到虛擬手術(shù)平臺(tái)要求。改進(jìn)MC算法減少了對(duì)空體元的遍歷和生成的三角面片數(shù)量，簡(jiǎn)化等值面抽取過程，大大提高了算法執(zhí)行效率。但上述研究?jī)H改進(jìn)了虛擬手術(shù)平臺(tái)中軟組織的幾何建模，今后將對(duì)軟組織的物理建模展開更深研究，為搭建更加符合真實(shí)手術(shù)情況的虛擬手術(shù)平臺(tái)提供幫助。