一種優化繪制順序的光線投射算法

趙文超　萬韜阮　武桐　朱耀麟

摘 要：針對光線投射算法難以滿足實時性需求的問題，提出一種光線投射改進算法。該算法把梯度估計、分類與著色、明暗計算過程放置體繪制預處理階段，減少繪制過程計算任務；簡化光照模型，從前向后進行融合運算提前終止融合，避免不必要的計算量。實驗結果表明該算法能有效提高光線投射算法的繪制速度。

關鍵詞：分類與著色；明暗計算；圖像融合

中圖分類號：TP3 文獻標識碼：A

Abstract：For real-time ray-casting algorithm can not meet the requirements of the problem，an improved algorithm ray casting.The algorithm of the gradient estimation，classification and coloring，shading calculations placed volume rendering preprocessing stage，a drawing process to reduce the computational tasks；simplified illumination model，from front to back early termination of integration of the fusion operation，avoid unnecessary computation.Experimental results show that the algorithm can effectively improve the rendering speed of light projection algorithm.

Keywords：classification and colored；shading calculation；image fusion

1 引言（Introduction）

可視化指利用計算機圖像處理技術，將海量的測量數據轉換為圖像的技術[1]。有效利用醫學圖像中的大數據進行三維重建，繪制出病灶的三維結構，幫助醫生作出的診斷。高質量的繪制效果與快速的繪制速度通常難以兼得。

相關的研究人員提出過改進方法，Lenoy提出自適應圖像超采樣技術來挖掘體素空間的一致性[2]。算法中僅從屏幕的一個像素子集發射光線，具有相同值的兩個像素中間采用插值的方法計算，對于圖像梯度較大的情況，算法再通過增加投射的光線密度來解決二義性。Walson提出利用體素空間的一致性。算法以較低的采樣頻率進行重采樣，如果兩個相鄰重采樣點間的數據值差別較大，將在該區域增加采樣頻率[3]。

2 算法原理（The basic method of the algorithm）

2.1 算法框圖

基于調整繪制流程的光線投影算法流程圖，如圖1所示。

2.2 計算量分析

假定三維空間網格為均勻網格，體數據分辨率為，視平面分辨率為，每條射線上采樣點數量為。假定代表一個重采樣點所花費時間，則進行一次體繪制所需時間為。由于采樣點數量和視平面分辨率在繪制過程中不變，故決定繪制速度的快慢。

梯度估計表征原始體數據分別沿坐標軸方向數值變化的大小。在光線投影算法中分類與明暗計算都會使用梯度估計。在明暗計算中需要梯度估計去近似法向量，分類階段梯度估計是其傳遞函數一個可選的自變量。若無需明暗計算，而且分類與著色過程無需梯度量，則梯度估計可刪減。把梯度估計放置在繪制過程開始之前進行，這將會提高繪制效率。而且，若體繪制算法使用高階梯度估計算法時，可大幅縮短繪制時間。

2.3 梯度估計算子選取

Sobel算子使用領域26個體素進行計算，屬于高階算子有54次乘除法運算與51次加減法運算。使用低階算子會導致大量的細節信息被丟失，無法完成高質量的體繪制渲染。梯度估計階段被放置在繪制準備階段，使用計算量大的高階梯度估計算子不會延長繪制時間。使用高階梯度估計算子來提高體繪制質量比重采樣階段使用高階插值來的效果更為明顯。

2.4 分類和著色

分類是為了給不同體素賦予不同透明度，著色是為了給不同體素賦予不同顏色值。可使用傳遞函數進行分類和著色過程，還可使用圖像分割劃分區域來分類，然后對不同類進行著色操作。雖然圖像分割可極大提高繪制效果，但分割技術人處于半自動階段，需要人工干預，且計算量較大。使用傳遞函數進行分類和著色，且放置在繪制過程開始之前，可有效縮短繪制時間。此時，值如式1所示。

2.5 明暗計算

其中，為表面對泛光的漫反射函數、為漫反射系數、為鏡面反射系數、為面法向、為入射方向、為反射方向、為視線方向、為表面的漫反射顏色、和為相應的光強。

在重采樣點處，通過三線性插值計算出法向量，然后在施加分類和著色以及進行光照計算求解該點的不透明度、顏色、亮度具有相同效果。

明暗計算過程可以在體繪制開始之前進行。此時，值如式4所示。

原來插值只需要進行體數據值的插值運算，現在提前著色和提前明暗計算會增加重采樣點的插值運算時間，需完成三個顏色分量和不透明度插值。

2.6 插值算法

對重采樣點進行三個顏色分量和不透明度的插值，故插值算法選擇很關鍵。雖然立方卷積和B樣條插值算法等高階插值算法更準確，但是其計算復雜度太高（都是52個乘除，39個加減運算），最近相鄰插值計算復雜度較低，只有3個加減運算，也能夠產生較高質量繪制圖像。但是由于新算法采用了提前分類著色、提前明暗計算的流程調整策略，所以新算法還是采用光線投射算法中使用最多的插值算法，即三線性插值算法。

2.7 融合計算

圖像融合是指沿像素點發出射線方向上的各采樣點進行顏色和不透明度的有序融合[4]。可以沿射線發出方向的前后進行依次融合，也可從后向前依次融合。在從前向后進行合成過程中，不透明度逐漸增大，當不透明度接近1時，體素變得不透明，其后的體素不在影響融合過程。因此，提前終止圖像融合，避免了不必要的計算量。

3 實驗結果與分析（Experimental results and analysis）

實驗信息與結果，如表1所示。

采用改進的光線投射法與改進前繪制效果比較接近，但繪制速度相對提高了10%左右。

4 結論（Conclusion）

針對光線投射算法難以滿足實時渲染需求的問題，提出一種光線投射改進算法。該算法把梯度估計、分類與著色、明暗計算過程放置體繪制預處理階段，減少繪制過程計算任務；使用高階梯度估計算子來保證體繪制效果；不考慮鏡面反射，簡化光照模型；使用計算量適中的三線性插值，對重采樣點進行三個顏色分量和不透明度插值；從前向后進行融合運算可提前終止融合過程，避免不必要的計算量。

參考文獻（References）

[1] 胡英.醫學圖像可視化關鍵技術研究[D].沈陽：東北大學，2004.

[2] 景孝凱.基于體繪制的圖像三維重建算法研究[D].西安：電子科技大學，2007.

[3] 劉尚平，陳驥，劉霞.基于醫學圖像的三維模擬手術[J].中國醫學影像技術，2010，26（1）：167-170.

[4] 王樹秀.醫學圖像分割與三維可視化技術研究[D].山東大學，2009.

作者簡介：

趙文超（1988-），男，碩士生.研究領域：數字圖像處理.

萬韜阮（1960-），男，博士，教授.研究領域：數字圖像處理.

武 桐（1982-），女，碩士，講師.研究領域：數字圖像處理.

朱耀麟（1977-），男，博士，副教授.研究領域：數字圖像處理.