基于GPU加速的改進的光線投射算法研究

摘 要： 傳統的醫學圖像體繪制算法大多通過CPU端實現，為解決傳統算法存在繪制時間較長，交互不夠流暢，且使用平臺單一等問題，提出了一種基于圖形處理器（GPU）的醫學序列影像的實時體繪制技術。通過對不透明度值設置閾值，提前終止光線計算，并在光線遍歷體數據時，調整采樣間距，改進了光線投射算法。實驗結果表明，對其中一組最大數據（931張切片）的繪制時間為1.3 s左右，交互時的繪制幀數在20～40之間。在繪制時間方面，不僅比傳統的基于CPU的算法有大幅度提高，相比于前人的基于GPU的算法也有明顯改進，加速比可以達到1.5左右。

關鍵詞： GPU； 光線投射算法； 體繪制； 采樣間距； 不透明度值

中圖分類號： TN911.73?34； TP391.9 文獻標識碼： A 文章編號： 1004?373X（2016）21?0056?05

Study on improved ray casting algorithm based on GPU acceleration

TANG Zhenyu， Lü Xiaoqi， REN Guoyin

（School of Information Engineering， Inner Mongolia University of Science and Technology， Baotou 014010， China）

Abstract： The traditional volume rendering algorithms of medical image are mostly realized with CPU. In order to solve the problems of long rendering time， poor interaction and single platform existing in traditional algorithms， a real?time volume rendering technology of medical sequence image based on graphics process unit （GPU） is put forward. With the technology， the threshold of opacity value is set to terminate the light ray early， and the sampling interval is adjusted while the light ray traversing the volume data to improve the ray casting algorithm. The experimental results show that the volume rendering time of a group biggest data including 931 slices is about 1.3 s， and the rending frame is among 20～40 while interacting. The rendering time is faster than that of the traditional algorithm based on CPU， and the speed?up ratio can reach to about 1.5.

Keywords： GPU； ray casting algorithm； volume rendering； sampling interval； opacity value

0 引 言

近年來，計算機斷層技術（CT）、磁共振（MRI）和超聲（US）[1]等醫學影像技術快速發展。通過這些成像技術，醫生能夠獲得病人病變組織的二維切片圖像，輔助醫生進行診斷和治療。但是，這些成像技術所提供的人體二維切片圖像只能表達人體病變組織的二維信息，病灶的大小和形狀只能憑醫生的經驗去估算，此方法缺乏準確性和直觀性。醫學圖像三維可視化技術的發展極大地改善了這種狀況，醫學圖像三維可視化就是利用計算機將人體組織和器官的二維數字斷層切片通過插值技術將其轉化為具有直觀立體效果的圖像。

醫學圖像的三維可視化技術主要包括面繪制和體繪制[2]。與面繪制相比，體繪制重建出的圖像效果渲染質量更高，更能清晰地展示體數據的內部細節。體繪制中最常用的算法為光線投射算法，其繪制質量高，繪制效果好，但計算量大，耗費時間長。在圖像質量和繪制速度之間尋找一個最佳的解決方案，是目前三維可視化技術的研究熱點。隨著現代計算機圖形處理器（GPU）的快速發展，其浮點運算速度已大大超過CPU，很多基于CPU實現的光線投射算法被加以改進，以便能在GPU上運行。文獻[3]提出了一種基于Pixel Shader 2.0 API的多步光線投射算法。文獻[4]實現了基于GPU的最大密度投影（MIP）繪制。盡管基于GPU的光線投射算法越來越成熟，繪制的效果也越來越好，但在繪制速度方面仍然有可提高的空間。本文基于GPU加速技術，實現了一種改進的光線投射算法，該算法不僅繪制效果好，而且在繪制速度上有明顯提高。

1 體繪制算法的主要內容

1.1 可編程GPU的繪制管線

GPU渲染流程主要由圖形繪制管線描述，即“給定視點、照明模式、三維物體、紋理和光源等元素，繪制一幅二維圖像”。圖形繪制管線的三個階段為：應用程序階段、幾何階段和光柵階段。

（1） 應用程序階段。使用高級編程語言進行開發，主要對內存、CPU進行操作，比如空間八叉樹、碰撞檢測、視錐裁剪、場景圖建立等經典算法都是在這個階段執行的。在該階段的末端，紋理坐標、頂點坐標、紋理、法向量等幾何體數據通過數據總線傳送到圖形硬件。

（2） 幾何階段。主要負責投影、裁剪、屏幕映射、光照以及頂點坐標的變換，該階段主要基于GPU運行。經過投影和變換之后的紋理坐標、顏色以及頂點坐標都是通過該階段得到。

（3） 光柵階段。根據幾何階段輸出的數據，為每一個像素進行配色，然后繪制得到完整圖像。光柵階段是對單個像素進行操作，顏色緩沖器用來存儲每個像素的信息。

1.2 光線投射算法

光線投射（Ray Casting，RC）方法是一種以空間圖像為序列的DVR算法，RC算法的基本原理是：首先從成像平面的每一個像素，沿著視線方向發射一條光線穿過體數據，然后在此過程中對圖像序列等間距的進行重采樣并獲得顏色值，對獲得的顏色值進行累加，當光線穿越完圖像序列，最后得到的累加值就是圖像最終的渲染顏色[5]。其主要流程如圖1所示。

RC算法的主要技術如下：

（1） 數據分類

三維數據場中的數據分類就是對多種不同的物質用不同的數值表示。在醫學圖像中，比如腎臟、骨骼、肌肉、皮膚等不同的組織器官具有不同的密度，因此其圖像的CT值也不一樣。對數據進行分類，是醫學圖像三維重建的一個十分重要的環節。只有分類準確，才能在后續的圖像處理中得到較好的效果。一般來說，一個組織器官的圖像中往往會有不同的CT值，而具有相同CT值的像素也會存在于不同組織器官的圖像中，所以有時會需要人工對數據進行分類。

本文采用閾值分界法對醫學圖像的三維體數據進行分類。其原理就是根據人體器官和組織，為醫學三維數據場中的數據點設置一些閾值分界點[dii=1，2，…，n]。假設數據點的像素值為[f（xi，yj，zk），]那么可以把滿足式（1）的數據點歸入到同一類中。

（2） 顏色賦值

一般來說，體繪制的結果顯示的圖像要具有一定的透明效果，以便更直觀地展示內部結構，所以要給體素賦予一定的不透明度值[a，]當[a=1]時表示圖像完全不透明，當[a=0]時表示圖像完全透明。如果一個體素包含了多種物質，可以利用各種物質所占的百分比來表示該體素的顏色值。假設第[i]種物質所占的比例為[pi，]那么第[i]種物質的顏色值可以表示為[Ci=（aiRi，aiGi，][aiBi，ai），]該體素的最終顏色值就可以表示為：

（3） 明暗計算

因為體繪制中沒有面的信息，因此體繪制中要求先算出法向量才能進行明暗計算。在體繪制中數據點的法向量用梯度值代替。假設三維數據場中某個數據點的函數值為[f（xi，yj，zk），]那么就可采用如式（3）所示的中心差分法求出此數據點處的梯度值。

[Grad_x=f（xi+1，yj，zk）-f（xi-1，yj，zk）2ΔxGrad_y=f（xi，yj+1，zk）-f（x，yj-1，zk）2ΔyGrad_z=f（xi，yj，zk+1）-f（xi，yj，zk-1）2Δz] （3）

各數據點的梯度值求出后，就可以利用光照模型計算出各個數據點的漫反射分量，也就更能夠突顯體數據中的邊界面。

（4） 圖像合成

圖像合成是RC算法的最后一步。其主要原理為：根據像素點所發出的射線，此射線穿過三維體數據并進行采樣，然后計算該采樣點的不透明度值和顏色值，最后通過相關公式合成該像素點的最終顏色值。要想形成最終的圖像，需要計算屏幕中所有的像素點的顏色值。體繪制中主要有兩種圖像的合成方法。

① 由前向后的圖像合成

該算法通過沿著射線把各采樣點的不透明度值和顏色值由前往后的合成在一起，得到最終的圖像。假設[aout]和[Cout]分別是經過第1個體素后的不透明度值和顏色值，[ain]和[Cin]分別是進入第[i]個體素的不透明度值和顏色值，[aout]和[Cnow]分別為第[i]個體素的不透明度值和顏色值，則有：

[Coutaout=Cinain+Cnowanow（1-ain）aout=ain+aout（1-ain）] （4）

② 由后向前的圖像合成

[Cout=Cin（1-anow）+Cnowanow] （5）

可以看出，這兩種圖像合成方法符合光學的吸收和反射模型，實質上是一致的。其中，由前向后圖像合成過程中阻光度是逐漸增大的。如果阻光度的值接近于1，就表明該像素點幾乎為不透明，那么就可以把后面的像素點忽略掉。所以，由前向后的圖像合成方法效率更高，速度較快。本文采用由前向后的圖像合成方法。

2 改進的光線投射算法

采用RC算法生成的圖像質量較高，繪制效果好，但計算量大，耗費時間長。即使采用高性能的GPU進行圖形硬件加速，有時依然達不到所要求繪制的時間。這時就需要在算法方面進行加速優化，以滿足實時性的要求。目前最常用的兩種方法為：無效體素剔除法（Empty Skipping and Occlusion Clipping）[3，6]和提前光線終止法（Early Ray Termination）[5?6]。本文實現的是提前光線終止法。

2.1 無效體素剔除法

一些體素值轉化為光學特性后，并不會顯示，也不會影響最終圖像的合成，這些體素稱為空體素。三維體數據中一般都存在一定數量的空體素。所以，通過剔除冗余體素，不讓其進入到GPU的渲染管線中，從而達到加速繪制的效果。

2.2 提前光線終止法

通過式（5）可以看出，在像素混合迭代求解的過程中，不透明度[a]的值是逐漸增大的，當[a]的值接近1時，表示該光線對像素值的計算結果趨近于飽和，即使繼續采樣，最終的像素值也幾乎不會受到影響。因此，可以采用提前終止光線計算的方法，這樣可以提高整體繪制的時間。可以設置一個閾值，只要[a]的值超過這個閾值，就終止光線，本文設置的閾值為0.95。同時，與自適應加速采樣法結合，即當光線遍歷體數據時，如果碰到無效的采樣點，就適當增加采樣的間距，降低重采樣的頻率，如果碰到有效采樣點，就恢復重采樣頻率。通過將提前光線終止法與自適應采樣加速法結合，可以進一步提高整體繪制的時間。流程圖如圖2所示。

（1） 通過投射光線對體數據進行重采樣，獲得體素的值并進行數據分類。

（2） 判斷體素值是否有效。如果無效，則增大采樣間距，并轉到（5）；如果有效，則采用原采樣間距，并進行下一步。

（3） 對采樣點進行顏色賦值和明暗計算，并進行圖像合成。

（4） 判斷不透明度值[a]是否大于閾值，如果沒有大于閾值，則繼續重采樣；如果大于閾值，則轉到（6）。

（5） 判斷光線是否穿出包圍體，如果沒有穿出，則繼續重采樣；如果穿出，則進行下一步。

（6） 根據累加的顏色值，合成最終圖像。

3 GPU加速光線投射算法

RC算法在GPU上實現的關鍵是能夠利用GPU完成對體數據的遍歷、采樣和計算，并將得到的采樣值進行混合，以產生最終的重建結果[7?9]。此部分通過Cg語言和OpenGL編寫的頂點程序和片段程序實現。Cg語言是為GPU編程設計的高級著色語言，而OpenGL擴展則提供了可操作GPU的編程接口。頂點程序主要負責射線發出的方向和設置頂點的位置以及變換頂點坐標、頂點顏色和紋理坐標。而片段程序主要負責核心算法，即改進的光線投射算法。通過可編程GPU編寫著色器，可以非常靈活方便地實現各種繪制效果。本文通過結合GPU加速技術和改進的光線投射算法實現了最大密度投影繪制（Maximum Intensity Projection，MIP）[10]以及合成體繪制（包括骨骼、皮膚、肌肉等）[11]。不同的繪制方法分別對應不同的組織結構。

3.1 最大密度投影繪制

最大密度投影就是通過計算每條射線所遇到的最大像素密度確定最終圖像的顏色值和不透明度值。圖像效果可以反映組織密度的差異，對比度高，常應用于密度相對較高的組織結構。用基于GPU的光線投射算法實現最大密度投影算法的原理為：計算發射光線與體數據相交時的最大密度值，并把值賦予該像素。如圖3所示。

MIP繪制的效果如圖4所示。

3.2 合成體繪制

合成體繪制是最常用的一種光線投射方法。其原理為：通過頂點程序把體數據值轉換成顏色值和不透明度值等光學屬性，并將這些屬性值合成到屏幕上的像素中形成最終圖像。如果改變顏色值和不透明度值的參數，就能實現不同的繪制效果，比如骨骼、肌肉等。

繪制顯示效果如圖5所示。

4 繪制速度對比

實驗數據采用Philips公司Brilliance iCT設備產生的人體數據。計算機配置為Intel[?] CoreTM i7?3770 CPU @3.40 GHz；顯卡為AMD HD 7470，1 GB顯存；內存為3.49 GB；Windows 7 32位操作系統；開發平臺為Eclipse Luna Service Release1（4.4.1）。繪制時間通過測量十次取平均值得到，繪制幀數采用第三方軟件Fraps測量得到。

耳部數據集的大小為828 MB，頭部數據集的大小為477 MB，腳踝數據集的大小為75 MB。通過表1可以看出，繪制時間上，基于GPU的算法明顯快于基于CPU的算法，而本文實現的基于GPU改進的光線投射算法要優于傳統的GPU算法，最大加速比達到1.79。同時可以看出，數據集越大，基于GPU的加速效果越明顯。

5 結 語

隨著現代醫學成像設備的發展，其所生成的醫學圖像數據越來越龐大，傳統的基于CPU的體繪制算法已不能滿足醫學臨床需求，基于GPU的醫學圖像處理算法逐漸成為目前研究的熱門領域。本文在Eclipse平臺下，基于GPU加速，結合改進的光線投射算法，實現了最大密度投影繪制以及合成體繪制。Eclipse是一個兼容Windows系統和Linux系統的平臺，基于Eclipse平臺開發的程序移植也比較方便。通過結論可以看出，繪制效果已能滿足醫學臨床實踐的需求，且繪制速度上比傳統的GPU算法有明顯的提升。下一步的研究工作主要為完善程序的功能，實現更多的優化算法，并對各種算法進行優缺點的比較。

參考文獻

[1] KUTTER O， SHAMS R， NAVAB N. Visualization and GPU?accelerated simulation of medical ultrasound from CT images [J]. Computer methods and programs in biomedicine， 2009， 94（3）： 250?266.

[2] 常旖旎，魯雯，聶生東.醫學圖像三維可視化技術及其應用[J].中國醫學物理學雜志，2012，29（2）：3254?3258.

[3] LI W， MUELLER K， KAUFMAN A. Empty space skipping and occlusion clipping for texture?based volume rendering [C]// Proceedings of 2003 the 14th IEEE Visualization Conference. Washington， D. C.： IEEE， 2003： 1?8.

[4] KRUGER J， WESTERMANN R. Acceleration techniques for GPU?based volume rendering [C]// Proceedings of 2003 the 14th IEEE Visualization Conference. Washington， D. C.： IEEE， 2003： 287?292.

[5] LEVOY M. Efficient ray tracing of volume data [J]. ACM tran?sactions on graphics， 1990， 9（3）： 245?261.

[6] HADWIGER M， LJUNG P， SALAMA C R， et al. Advanced illumination techniques for GPU volume raycasting [C]// Procee?dings of 2008 ACM Siggraph Asia Courses. [S.l.]： ACM， 2008： 163?166.

[7] 胡劍，王明泉，侯慧琳，等.使用 GPU 編程的工業CT斷層圖像三維可視化技術[J].應用科技，2011，38（5）：61?65.

[8] 康健超，康寶生，馮筠，等.一種改進的基于 GPU 編程的光線投射算法[J].計算機工程與應用，2012，48（1）：199?201.

[9] 林碧英，陳達峰.基于GPU的三維數據場等值面繪制[J].中國電力教育，2008（z3）：402?404.

[10] 諸葛斌，馮煥清，周荷琴.基于有序體數據的最大密度投影算法[J].中國科學技術大學學報，2003，33（4）：473?479.

[11] 呂曉琪，張傳亭，侯賀，等.基于圖形處理器加速光線投射算法的多功能體繪制技術[J].計算機應用，2014，34（1）：135?138.

[12] WANG X H， GOOD W F. Real?time stereographic rendering and display of medical images with programmable GPUs [J]. Computerized medical imaging and graphics， 2008， 32（2）： 118?123.