基于改進移動立方體算法的三維重建

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

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

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

目前許多虛擬現實平臺采用改良MC算法進行組織器官圖像三維重建。Du等[3]采用多邊形等值面擴展算法來遍歷相鄰立方體，使渲染時間縮短，存儲空間減少。Mun等[4]采用基于二次誤差度量技術的三角面片抽取方法減少了MC算法生成的三角面片數量。高峰等[5]采用種子體元衍生等值面方法，以避免對無用體元的遍歷，減少渲染時間。但這些算法重建過程中的模型精確性和交互性相對較弱，對于后續虛擬康復訓練和醫學輔助診治的作用有待提高。Wijewickrema等[6]將改進的MC算法用于分段離散的體數據，生成了光滑的三維曲面。Chen[7]采用等間距閾值法代替傳統的等值面閾值法，使改進的MC算法更適用于材質移除的虛擬仿真平臺上。但這些相關MC算法需要生成大量的多邊形面片，拓撲結構復雜，計算量大。本研究提出一種基于區域增長法的通用樹結構和移動等值點法的自適應改進MC算法。

1 原理與方法

基于區域增長法的通用樹結構和移動等值點法的改進MC算法包括基于交互式區域增長算法的醫學圖像分割、建立通用樹結構、移動等值點合并三角面片法三部分，具體流程見圖1。

1.1 基于交互式區域增長算法的醫學圖像分割 在醫學圖像上選取1個或多個種子點，種子點自適應地向相鄰空間剖分，遍歷周邊體元，尋找并標記所有與指定閾值相交的體元，生成三角面片，完成相關組織器官的分割。

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

圖1 基于交互式區域增長法的通用樹結構和移動等值點結合的改進MC算法流程圖

1.2 建立通用樹結構 根據分割的相關組織器官的空間大小，確定所建通用樹結構的層數和子節點個數，制定體元頂點索引方式。將與閾值相交的體元全部插入到創建的通用樹結構中。

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

為更直觀、形象地說明通用樹結構的創建和頂點索引方式，以層數為8的通用樹結構舉例說明。子節點的編號順序采用按0～7的二進制位cba分配法，a=1表示沿x軸的正方向，a=0表示沿x軸的負方向；b=1表示沿y軸的正方向，b=0表示沿y軸的負方向；c=1表示沿z軸的正方向，c=0表示沿z軸的負方向。子節點的編號順序見圖3。

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

圖2 區域增長算法示意圖 A.體素灰度值圖，其中紅色區域為原始種子點； B.區域增長算法的生長軌跡圖，種子點區域沿黑色箭頭生長，當灰度值為32的種子點進行相鄰區域衍生時，灰度值為33的體素符合門限灰度值的界定，因此將灰度值為33的體素并入種子點區域。同理，灰度值為35和34的體素也成為種子區域 圖3 通用樹子節點的編號順序

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

1.3 移動等值點合并三角面片法 將體元棱邊上的等值點移動至最近的體元頂點，合并存儲在通用樹結構中體元內的共面三角面片，以減少三角面片個數。選擇頂點代替原等值點，頂點信息儲存在通用樹結構的子節點中，不需要計算等值點的坐標和法向量，大大提高了算法執行效率。連接新的三角面片，形成最終的三維組織模型。

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

2 結果

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

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

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

表1 傳統MC算法和改進MC算法性能對比

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

圖7 腎臟組織三維重建效果圖 A.傳統MC算法； B.改進MC算法 圖8 腎臟三維重建模型應用于虛擬手術平臺

3 討論

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

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

本研究結果顯示改進MC算法的三維重建效果較好，拓撲結構簡單，三角面片個數減少，算法執行效率有較大提高，能夠高精度地展示出腎臟細節，并成功應用于虛擬手術平臺，為基于醫學圖像的三維重建和虛擬手術研究提供更加有效的方法。本研究所用算法渲染效果好，真實性和精確性均達到虛擬手術平臺要求。改進MC算法減少了對空體元的遍歷和生成的三角面片數量，簡化等值面抽取過程，大大提高了算法執行效率。但上述研究僅改進了虛擬手術平臺中軟組織的幾何建模，今后將對軟組織的物理建模展開更深研究，為搭建更加符合真實手術情況的虛擬手術平臺提供幫助。