基于改進光線投射法的冠脈圖像三維重建

王逸夫，王瑜，邢素霞，王怡寧，易妍

1.北京工商大學人工智能學院，北京100048；2.中國醫學科學院北京協和醫院，北京100730

前言

隨著核磁共振成像（Magnetic Resonance Imaging,MRI）技術、計算機斷層掃描（Computed Tomography,CT）、超聲波以及電子內窺鏡等醫學設備的快速發展，使得傳統的醫學診斷方式有了巨大的改變，通過醫學影像設備已經可以得到人體內部某一組織比較清晰的橫截面二維數字圖像，而連續二維數字圖像序列包含了人體內各種器官的三維信息。在這種背景下，醫學圖像三維重建技術應運而生［1-3］。

光線投射算法是一種應用最廣泛的圖像三維重建算法，具有成像保真性高的優點，在醫學可視化領域有著良好的前景［4-5］。然而光線投射算法重建圖像的速度慢，難以滿足實時交互性的需求。目前提高重建速度可以從硬件和軟件兩個方面考慮，但由于硬件成本相對較高，限制了應用范圍，因此，從算法進行優化成了主要手段。何楠等［6］采用預積分分類方法滿足奈奎斯特采樣定律，消除光線投射算法產生的木紋效應，利用平行線切割投射光線的數學特性實現高效的插值方法，加速繪制速度。于水等［7］把體數據分成兩部分，利用八叉樹重構并剔除空塊，使用圖形處理器對頂點集合進行渲染并繪制圖形，加速繪制速度。胡春紅等［8］利用血管分支點和端點來優化幾何變換矩陣中的平移向量，不僅能有效提高冠脈樹的三維重建精度，而且可獲得重建冠脈樹在第三角度下的精確投影圖像。徐超清等［9］利用自適應劃分算法加強極值點區域的繪制，引入預積分光照算法，對預積分采樣段進行體繪制積分，增強繪制的局部細節。徐冰［10］采用預積分光照算法，對預積分片段內的梯度進行插值重構，然后計算梯度中與射入光線夾角的最小梯度值，將該梯度值用于預積分光照渲染，加強了體數據中局部細節的光照效果。彭偉等［11］提出一種計算統一設備架構CUDA存儲器的訪存優化策略，給出了適用于CUDA存儲器的空體素跳躍法，加快光線投射算法的繪制速度。李曉清［12］將每一條采樣射線分為多個部分進行優化采樣，再將各部分的結果進行融合，對算法進行兩兩分組并優化，降低了傳統光線投射算法的計算復雜度。李航等［13］通過二維最大商閾值分割，包圍盒劃分，八叉樹數據格式存儲最大限度地濾去無效體素，提高算法繪制速度。Deakin等［14］計算近鄰非空體素的切比雪夫距離，并將該距離存入距離圖中，在采樣數據合成時，將該距離值賦予空體素，能直接跳過連續的空體素，加快繪制速度。在上述算法的啟發下，本文提出一種冠脈三維重建算法，通過改進重采樣的三線性插值算法，并結合切比雪夫空體素跳躍法來優化和加速傳統光線投射算法的運算速度，從而達到實時交互的目的。

1 研究方法

1.1 傳統光線投射算法基本原理

光線投射法的基本原理首先對三維體數據場進行數據預處理，將得到的數據根據閾值進行分類，分類完成后根據傳輸函數得到每一個數據點的顏色值和不透明度值［15］。然后從屏幕上的每一個像素點發出一條射線，沿著射線按照預先設定的釆樣步長進行重采樣，對重采樣點近鄰的8個數據點進行三線性插值得到該重采樣點的顏色值和不透明度值。最后對每條射線上所有采樣點按一定規則進行合成，得到屏幕上這條射線的顏色，將屏幕上所有像素點的顏色值計算出來，最終得到一幅完整的三維圖像。

該算法主要分為4 個步驟：數據值分類、賦顏色值和不透明度值、重采樣插值計算和圖像合成。其中占用時間比重最高的是重采樣插值計算步驟［16］，所以優化并加快重采樣中的插值運算，是提高光線投射算法運算速度的關鍵。

1.2 傳統三線性插值方法

如上所述，插值運算是提高光線投射算法運算速度的關鍵，傳統三線性插值方法的原理如下：投射的光線穿過三維數據場，在每條光線上進行等距采樣［17］，新的采樣點一般不在原始的數據點上，所以把新的采樣點稱作重采樣點。重采樣點的數據值通過對距離重采樣點最近的8 個原始數據點的顏色值和不透明度值進行三線性插值［18-19］得到，傳統的三線性插值算法示意圖如圖1所示。

圖1 三線性插值示意圖Fig.1 Diagram of trilinear interpolation

設dx、dy、dz分別為P點在x、y、z軸上相對于頂點V4的偏移值，重采樣點P的坐標位置為P(x,y,z)，其他相鄰的原始數據點為V0(i,j,k)、V1(i+1,j,k)、V2(i+1,j,k+1)、V3(i,j,k+1)、V4(i,j+1,k)、V5(i+1,j+1,k)、V6(i+1,j+1,k+1)、V7(i,j+1,k+1)。用Δx、Δy、Δz表示x、y、z方向重采樣的間距，則。其中符號[ ].表示不大于括號中數值的最大整數。則三線性插值的運算過程分為以下3步。

（1）對x方向進行插值運算，求出P11、P12、P21、P224個點的值：

（2）對z方向進行插值運算，通過P11、P12、P21、P22求出P1、P2兩點的值：

（3）對y方向進行插值運算，通過P1、P2求出P點的值：

將式（1）和式（2）帶入到式（3），并展開如下：

其中，u=x/Δx-i,v=y/Δy-j,w=z/Δz-k。

1.3 改進的三線性插值方法

在傳統三線性插值方法基礎上，本文進行了如下改進。光線投射法中給數據點賦顏色值和不透明度值時會產生大量不透明度為0 的空體素，即圖1 中的V0～V7的數據值可能為0，但卻參與了三線性插值運算，會增加很多不必要的計算量。

本文根據V0～V7的數據值是否等于0，將式（4）分為28=256 種形式。例如V0的數據值為0，則最終P點的三線性插值為：

即最后進行運算時，少了4 次加減運算和3 次乘除運算。將公式用一個8 位的二進制數A 來表示，A的各位分別與V0～V7相對應，若Vn=0(n=0,1,2,3,4,5,6,7)，則與之相對應的二進制位數值為0。在重采樣三線性插值運算時，首先對V0～V7的數據值進行檢測，然后根據檢測的結果得到的二進制數A來選擇三線性插值公式的形式，以此來減少插值過程中的運算量。

在重采樣前、后會生成大量的空體素，這些空體素會在后續的合成圖像時參與運算，但由于是完全透明的，所以并不能被觀察到。本文在重采樣完成后，結合切比雪夫空體素跳躍法，使產生的空體素不參與最后合成圖像的運算，進一步提高整個光線投射算法運算速度。圖2是本文的改進光線投射算法的流程圖。

圖2 改進光線投射算法流程圖Fig.2 Flow chart of improved ray-casting volume rendering algorithm

2 實驗結果與分析

2.1 實驗設備與數據庫

本實驗硬件與軟件環境：CPU 為Intel Core i5-9300H 2.40 GHz，內存為8 GB，顯卡為NVDIA GeForce GTX 1660 Ti，顯存為6 GB，編程環境為Window10系統下的Visual Studio 2019。

數據庫選用真實病人心臟CT 圖像，來自北京協和醫院，共215 張，每張圖像大小為512×512 像素，層間距為0.5 mm。

2.2 客觀評測方法

本文利用均方誤差值和結構相似性對三維重建圖像質量進行評測。均方誤差值計算如式（6）所示：

其中，M為圖像像素的列數，N為圖像像素的行數，f1(x,y)和f2(x,y)分別為某一視角下原始三維圖像與重建圖像的3 個通道的像素值，數值越小，表示重建質量越好。

結構相似性計算如式（7）所示：

其中，μx和μy表示重建圖像3個通道像素值的均值，σx和σy表示原始三維圖像和重建圖像的方差，σxy表示協方差，C1=(K1L)2和C2=(K2L)2是用來維持穩定的常數，通常情況下，K1=0.01，K2=0.03，L=255。SSIM范圍為0～1，值越大，表示重建質量越好。

2.3 實驗結果與分析

2.3.1 人工合成圖像為了客觀評測提出算法的有效性，筆者人工合成了三維圓錐圖像，共20 張，每張圖像大小為1 100×850 像素，層間距為0.75 mm，具體如圖3a所示，Levoy 光線投射算法［5］和本文提出方法的三維重建結果分別如圖3b和圖3c所示。筆者重建了10 次圓錐圖像，并對兩種算法在時間上進行了比較，具體實驗結果如表1所示。其中MSE 值和SSIM 值為重建10 次圖像的算術平均值，平均繪制時間為重建10 次圖像的平均時間，插值運算時間為重建10 次圖像三線性插值運算的平均時間。

圖3 圓錐重建圖像比較結果Fig.3 Comparison of conic image reconstruction results

表1 兩種算法重建圓錐圖像的質量與速度對比Tab.1 Comparison of the quality of reconstructed conic image and reconstruction speed between two algorithms

由圖3和表1可以得出，兩種算法的MSE值與SSIM值大小接近，即重建出圖像的質量相近，本文提出的算法對重建圖像的質量沒有產生較大影響。本文提出算法在運算速度上為Levoy光線投射算法的1.18倍，插值運算速度為Levoy光線投射算法1.41倍。

2.3.2 真實冠脈圖像冠脈三維重建的實驗結果如圖4所示，Levoy 光線投射算法與本文改進的光線投射算法繪制結果是在同樣的視角、大小比例下獲得的。

圖4 冠脈重建圖像結果（右側為左側紅框內局部放大圖）Fig.4 Image reconstruction of coronary angiography(The right image is the local zoom-in of the red box in the left image)

筆者重建了20 次冠脈圖像，并對兩種算法在時間上進行了比較，具體實驗結果如表2所示。

由表2 可知，本文提出算法的運算速度為Levoy光線投射算法的2.58倍，插值運算速度為Levoy光線投射算法的3.05 倍。上述實驗結果表明，Levoy 的光線投射算法速度緩慢，而本文提出的改進三線性插值算法結合切比雪夫空體素跳躍法，能夠在不影響最終繪制圖像質量的情況下，有效地加快光線投射算法的運算速度。

表2 兩種算法重建冠脈圖像的速度對比Tab.2 Speed comparison between two algorithms for image reconstruction of coronary angiography

3 結論

本文提出了一種改進的三線性插值算法，并用于冠脈的三維重建，通過檢測原數據點的數據值，簡化傳統三線性插值方法的復雜性，并結合切比雪夫空體素跳躍法，加快傳統光線投射法的運算速度。實驗結果表明，本文的方法能夠在不降低成像質量的同時，有效地提高算法的運算速度。未來的工作是將提出的算法結合包圍盒技術，并運用到圖形處理器上運行，實現提出算法基于圖形處理器的實時繪制。