羅月童， 朱會國， 韓 娟， 徐云云

（合肥工業(yè)大學計算機與信息學院VCC研究室，安徽 合肥 230009）

遮擋線索增強的最大密度投影算法

羅月童， 朱會國， 韓 娟， 徐云云

（合肥工業(yè)大學計算機與信息學院VCC研究室，安徽 合肥 230009）

遮擋線索增強的最大密度投影算法（OEMIP）旨在解決最大密度投影法（MIP）不能正確表達遮擋線索的問題，它包括兩個步驟：首先使用 K-Means聚類算法從MIP結果圖像中自動提取結構特征；然后根據結構特征自適應調節(jié)MIP繪制過程以正確表達遮擋線索。此外，引入繪制優(yōu)先級以避免重要特征被次要特征嚴重遮擋，并給出繪制優(yōu)先級的自動設置算法。多個體數據的測試結果表明OEMIP能顯著增強遮擋線索，且能實現實時交互。

體數據可視化；最大密度投影；遮擋線索；結構特征

直接體繪制（direct volume rendering，DVR）是最有效的體數據可視化方法之一，在醫(yī)學、地理、物理等眾多領域有廣泛應用。傳遞函數（transfer function，TF）負責將體數據屬性（如密度值、梯度模等）映射為顏色、透明度等光學屬性，其質量對DVR的效果有決定性影響。雖然人們提出了很多傳遞函數的設計方法，但直觀快速地設計合適的傳遞函數仍是可視化領域面臨的重大挑戰(zhàn)[1]。作為一種特殊的 DVR方法，最大密度投影[2]（maximum intensity projection，MIP）將投射光線上的最大密度值投影到屏幕上，無需傳遞函數，具有簡單實用等優(yōu)點，在醫(yī)學等領域獲得廣泛應用。

因MIP只投影投射光線上的最大密度值點，

導致結果圖像中缺少深度線索，不利于用戶感知體數據的結構特征，為此人們不斷嘗試改進MIP方法。Heidrich等[3]根據深度調節(jié)密度值從而使距離視點越遠的點越暗，以增強結果圖像的深度線索；Bruckner和Gr?ller[4]結合DVR和MIP的思想提出最大標量差累積法(maximum intensity difference accumulation，MIDA)，MIDA利用DVR增強MIP的深度信息，但仍需要簡單的傳遞函數；Díaz和Vázquez[5]提出深度感知增強的最大密度投影算法（depth-enhanced maximum intensity projection，DEMIP）在生成MIP圖像的同時生成深度圖像，然后在片段程序中根據深度圖像調節(jié)MIP結果圖像，從而增強結果圖像的深度線索。

遮擋是最常用的深度線索之一，但MIP及上述改進算法均不能正確表現遮擋線索。如圖1中內臟位于后肋骨前方，但在(a)和(b)中卻是后肋骨遮擋了內臟，造成混淆。遮擋能夠表達結構特征之間的前后關系，而MIP、DEMIP等算法均沒有顯式考慮結構特征，難以表達遮擋關系。因此，遮擋線索增強的最大密度投影算法（occlusion enhanced maximum intensity projection，OEMIP）被提出。OEMIP首先自動提取結構特征，然后基于結構特征控制繪制過程，從而準確地表達結構特征之間的遮擋關系。

圖1 各種繪制方法的結果對比

1 相關工作

1.1 最大密度投影法

最大密度投影法因具有簡單實用等優(yōu)點而獲得廣泛應用，但也存在缺少深度信息、圖像真實感不強等缺點，因此人們不斷嘗試改進MIP算法。為提高繪制結果圖像中結構特征的連續(xù)性，Sato等[6]提出局部最大密度投影算法（local manximum intensity projection，LMIP），LMIP將投射光線最先碰到的局部極大值（大于給定閾值），而非最大值投影到對應像素上；光照對表達結構特征細節(jié)形狀有重要價值，Zhou等[7]通過添加光照效果實現形狀感知增強的最大密度投影算法（shaped enhanced MIP，SEMIP），增強MIP對局部細節(jié)特征的表達能力。增強MIP的深度線索一直是重要研究方向，Ropinski等[8]通過邊界增強、改變結構顏色等方法實現深度線索的增強，雖然與文獻[5]采用的方法有差異，但基本思想都是通過改變像素的顏色或亮度來體現深度信息。OEMIP的目標也是增強深度線索，但和上述方法不同，OEMIP方法是通過正確表達結構特征間的遮擋關系來增強深度線索，這是OEMIP

的最大創(chuàng)新之處。

1.2 體數據特征提取

特征能用于改進人機交互和渲染效果，因此特征提取一直是體數據可視化領域的重點研究內容。Tzeng和Ma[9]使用ISODATA聚類算法對體數據進行分類，允許用戶通過聚類結果（特征）調整可視化效果，使交互過程更簡潔直觀；Wang等[10]使用高斯混合模型（Gaussian mixed model，GMM）擬合體數據的2D直方圖，并將高斯模型作為特征以實現傳遞函數的半自動設計。光線穿越體數據所形成的標量曲線能反映體數據的特征，對一般而言，每兩個相鄰波谷之間的曲線段對應一個特征，很多研究人員利用這個事實改進體繪制算法。Malik等[11]通過分析標量曲線實現特征剝離；周志光等[12]通過分析標量曲線特征改進MIDA算法以揭示隱藏特征；羅月童等[13]依據標量曲線的分析結果實現考慮結構特征的自適應光線投射算法。標量曲線分析技術也被OEMIP用于提取結構特征。

2 遮擋線索增強的最大密度投影法

缺少遮擋線索會妨礙用戶感知結構特征的前后位置關系，所以對有多個結構特征的體數

據，用戶使用MIP算法難以進行有效地觀察分析。OEMIP算法的目標是增強遮擋線索，算法的整體流程如圖2所示：首先提取結構特征，然后使用結構特征調整繪制過程，從而增強遮擋線索。此外，OEMIP還自動為結構特征設置繪制優(yōu)先級，以避免重要特征被次要特征嚴重遮擋。

圖2 OEMIP整體流程

2.1 提取結構特征

結構特征是指具有一定意義的體素集合，如醫(yī)學體數據中的心臟、頭顱等器官，是體數據可視化需要展示的重要對象。有研究表明很多結構特征的密度值服從正態(tài)分布，如文獻[10，14]中分析的結構特征的密度值服從正態(tài)分布，OEMIP方法也假設結構特征的密度值服從正態(tài)分布，并用表示結構特征。

聚類算法常被用于自動/半自動提取結構特征，如Tzeng和Ma[9]使用ISODATA算法提取結構特征。OEMIP是基于K-Means算法提取結構特征，是將MIP結果圖像作為聚類樣本（參考圖2所示流程），而不是體數據，選擇這種方案有兩個主要原因：

（1）提高效率和魯棒性：和體數據相比，MIP結果圖像的規(guī)模要小很多，因此對MIP結果圖像進行聚類分析的效率和魯棒性都會有很大提高；

（2）能滿足OEMIP算法的要求：OEMIP的目標是增強MIP結果圖像的遮擋線索，僅需考慮在MIP結果圖像中可見的結構特征，因此可以基于MIP結果圖像進行結構特征的提取。

2.1.1 MIP繪制

投射光線穿越體數據時會產生密度曲線（如圖3），密度曲線能有效體現體數據的特征[11]，如相鄰波谷間的曲線段一般屬于同一結構特征。為使MIP結果圖像更全面地包含體數據的結構特征，對最大值所在曲線段進行采樣（采樣方法如圖3），并將采樣點的均值μ和方差σ保存在結果圖像中。

圖3 密度曲線

2.1.2 K-Means聚類

聚類是實現無監(jiān)督分類的最有效方法之一，現有聚類算法可分為層次化聚類方法、劃分式聚類方法、基于密度和網格的聚類方法等[15]。K-Means聚類算法因具有便于實現、時間復雜度低等優(yōu)點而被廣泛使用。OEMIP使用 K-Means算法對MIP結果圖像進行聚類分析，并將聚類結果作為結構特征。K-Means算法的基本步驟與應用無關，但其中兩個問題和應用密切相關：

（1）計算距離：即如何計算聚類中心 fi和樣本 pj之間的距離；

其中K由用戶指定。

雖然通常式(1)只有數值近似解，但對于一維正態(tài)分布 pi和 fj，有研究已證明存在如式(2)所示解析解：

因為已知樣本 pij和聚類中心 fi均服從正態(tài)分布，所以令將和式(2)代入式(3)可得：

2.2 考慮結構特征的MIP繪制

通過考慮結構特征可以增強結果圖像中的遮擋線索，但遮擋線索在幫助用戶理解結構特征之間位置關系的同時也可能導致重要特征被嚴重遮擋從而妨礙用戶觀察重要特征。因此，通過引入繪制優(yōu)先級的概念以進一步調整OEMIP的繪制過程，恰當地設置結構特征的繪制優(yōu)先級，使OEMIP在增強遮擋線索的同時，也能有效地展現重要結構特征?？紤]結構特征的MIP繪制包括兩部分：

（1）設置繪制優(yōu)先級：根據結構特征的重要度和相互遮擋關系自動地設置結構特征的繪制優(yōu)先級；

（2）繪制最終圖像：根據結構特征及繪制優(yōu)先級控制繪制過程，生成最終圖像。

2.2.1 繪制優(yōu)先級

繪制優(yōu)先級是用于解決重要結構特征被嚴重遮擋的問題，所以設置繪制優(yōu)先級時需要考慮兩個要素：

（1）結構特征重要度：雖然重要度的定義和具體問題密切相關，但不失一般性，可將結構特征的均值 μf作為）的重要度，即（2）遮擋率：遮攔率 O（fi, fj）表示結構特征 fi對的 fj遮攔程度。

基于“次要結構特征不嚴重遮攔重要結構特征”的原則，按以下步驟設置結構特征的繪制優(yōu)先級 prior（f）。不失一般性，這里假設

第二步：更新遮攔率，計算所有特征對比其更重要特征的遮擋率，即計算j =1,2 … ,N,i ＜j ；

第五步：結束，結束返回。

其中 εO是用戶給定的閾值，表示最大可接受次要結構特征對重要結構特征的遮擋率，實驗表明 εO= 0.6效果較好，因此，后續(xù)實驗也均令εO= 0.6。遮擋率的計算方法如下：

其中，p ixel（f, F ）表示僅考慮特征集F進行繪制時，特征f在結果圖像中所占像素的個數。對有n個結構特征的體數據，為更新遮擋率需要繪制幅圖像（在第二步中），但可利用多目標渲染技術（multi-rendering target，MRT）可同步渲染多幅圖像。目前主流GPU支持8個以上繪制對象，且每個繪制對象包含R、G、B、A四個通道，因此一遍繪制能生成 32幅圖像，滿足結構特征數 n≤ 7的問題。事實上，有研究表明人類最多能同時處理5～6個特征，因此7個結構特征能滿足絕大多數情況。如果有超過7個結構特征，可以進行多遍渲染。

2.2.2 繪制

在OEMIP中，存在3種可能投射光線（如圖4）：①投射光線不穿過任何結構特征；②投射光線穿過1個或多個結構特征，其中1個結構特征的繪制優(yōu)先級最高；③投射光線穿過多個具有相同最高繪制優(yōu)先級的結構特征。對于第1種情況，OEMIP將投射光線的最大值投影到相應像素，和標準MIP一致；第2種情況按繪制優(yōu)先級最高的結構特征設置像素顏色；第3種情況在繪制優(yōu)先級最高的結構特征中選取距離視點最近的結構特征，從而增強遮擋線索，整個繪制流程如圖5所示。

圖4 三類可能的投射光線

圖5 繪制流水線

投射光線穿越體數據產生密度曲線，密度曲線的局部極大值點具有代表性，因此基于密度曲線的局部極大值，而非采樣點值判斷投射光線和結構特征之間的關系更有魯棒性，所以可按式(7)確定密度值I所屬結構特征：

其中k可由用戶指定，根據3σ法則可令 k= 3。

3 實驗結果與分析

實驗的配置環(huán)境如下：2.93 GHz Intel I3 CPU，2.0G內存，NVIDIA GeForce GTS450 GPU，編程編程環(huán)境為Microsoft Visual Studio 2008，程序主框架采用 C++編寫，渲染相關功能采用CUDA實現，采用了CUDA SDK 4.2與OpenGL 3.1等函數庫。

選用了合成數據、醫(yī)學CT數據等對OEMIP進行驗證，實驗所用數據如表1所示。

表1 實驗體數據

3.1 繪制結果分析實不符，該問題在OEMIP中得以克服。腳部體數據的結構特征包括骨骼、皮膚肌肉，使用OEMIP雖然能正確表達遮擋關系，但更重要的結構特征骨骼卻被皮膚完全遮擋。繪制優(yōu)先級用于避免重要特征被嚴重遮擋現象，對于合成數據、胸腔數據，因為重要特征未被嚴重遮擋，所以考慮繪制優(yōu)先級后沒有對OEMIP結果產生影響，但腳數據考慮繪制優(yōu)先級后，能有效展示骨骼，即使骨骼處于皮膚的后面。

圖6 不同繪制方法效果對比

綜上所述，和MIP方法相比，OEMIP能有效增強遮擋線索，且通過考慮繪制優(yōu)先級，能避免重要特征被嚴重遮擋的現象出現。

3.2 時間性能分析

和MIP相比，OEMIP增加了特征提取、設置繪制優(yōu)先級等步驟，而且光線投射步驟也更加復雜，因此需要更多的繪制時間，但利用 MRT和CUDA等技術，仍然獲得了大于10 fps的繪制速度（如表2所示），能滿足實時交互的要求。

表2 OEMIP的繪制效率

4 總結與展望

MIP算法具有簡單、直接等優(yōu)點，在醫(yī)學等領域有廣泛應用，但MIP算法難以正確表達多個特征之間的遮擋關系，影響用戶感知數據的空間結構。OEMIP算法通過提取結構特征，顯式增強MIP結果圖像中的遮擋線索，從而幫助用戶更好地理解體數據的結構特征。針對次要結構特征可能嚴重遮擋重要結構特征的現象，OEMIP進一步引入繪制優(yōu)先級的概念，通過繪制優(yōu)先級避免重要特征被嚴重遮擋。使用合成數據、醫(yī)學體數據的測試結果都表明OEMIP能顯著增強遮擋線索，且能保證重要結構特征總被有效展示。

使用 K-Means聚類算法提取結構特征需要用戶指定結構特征的數目K，雖然對常用數據這種方法可以接受，但對陌生數據，用戶難以確定合適的 K，如何自動選取 K或采用類似于ISODATA等自適應聚類算法是未來的努力方向；另外，目前用于提取結構特征的聚類算法在CPU上運行，效率不高，如何基于CUDA實現結構特征提取，更充分地發(fā)揮 GPU強大的計算能力也需要進一步深入研究。

[1] 周芳芳, 樊曉平, 楊 斌. 體繪制中傳遞函數設計的研究現狀與展望[J]. 中國圖象圖形學報, 2008, 13(6): 1034-1047.

[2] Wallis J W, Miller T R, Lerner C A, Kleerup E C. Three-dimensional display in nuclear medicine [J]. IEEE Transactions on Medical Imaging, 1989, 8(4): 297-230.

[3] Heidrich W, McCool M, Stevens J. Interactive maximum projection volume rendering [C]// Proceedings of the 6th Conference on Visualization'95. IEEE Computer Society, 1995: 11.

[4] Bruckner S, Gr?ller M E. Instant volume visualization using maximum intensity difference accumulation [J]. Computer Graphics Forum, 2009, 28(3): 775-782.

[5] Díaz J, Vázquez P. Depth-enhanced maximum intensity projection [C]//Proceedings of the 8th IEEE/EG international conference on Volume Graphics. Eurographics Association, 2010: 93-100.

[6] Sato Y, Shiraga N, Nakajima S, Tamura S, Kikinis R. Local maximum intensity projection (LMIP): a new rendering method for vascular visualization [J]. Journal of Computer Assisted Tomography, 1998, 22(6): 912-917.

[7] Zhou Zhiguang, Tao Yubo, Lin Hai, Dong Feng, Clapworthy G. Shape-enhanced maximum intensity projection [J]. The Visual Computer, 2011, 27(6-8): 677-686.

[8] Ropinski T, Steinicke F, Hinrichs K. Visually supportingdepth perception in angiography imaging[C]//SmartGraphics. Springer Berlin Heidelberg, 2006: 93-104.

[9] Tzeng F Y, Ma K L. A cluster-space visual interface for arbitrary dimensional classification of volume data[C]//Proceedings of the Sixth Joint Eurographics-IEEE TCVG Symposium on Visualization. Eurographics Association, 2004: 17-24.

[10] Wang Yunhai, Zhang Jian, Chen Wei, Zhang Huai,Chi Xuebin. Efficient opacity specification based on feature visibilities in direct volume rendering[J]. Computer Graphics Forum, 2011, 30(7): 2117-2126.

[11] Malik M M, M?ller T, Gr?ller M E. Feature peeling[C]//Proceedings of Graphics Interface 2007: 273-280.

[12] 周志光, 陶煜波, 林 海. 一種有效顯示隱藏特征的光線投射算法[J]. 計算機學報, 2011, 34(3): 517-525.

[13] 羅月童, 譚文敏, 韓 娟, 陳進生. 一種考慮結構特征的自適應光線投射算法[C]//第十七屆全國計算機輔助設計與圖形學學術會議（CAD/CG 2012）論文集, 2012: 186-190.

[14] Haidacher M, Patel D, Bruckner S, Kanitsar A, Groller M E. Volume visualization based on statistical transfer-function spaces[C]//Pacific Visualization Symposium (PacificVis), 2010 IEEE, 2010: 17-24.

[15] 孫吉貴, 劉 杰, 趙連宇. 聚類算法研究[J]. 軟件學報, 2008, 19(1): 48-61.

[16] Jiang Bin, Pei Jian, Tao Yufei, Lin Xuemin.Clustering uncertain data based on probability distribution similarity [J]. IEEE Transactions on Knowledge and Data Engineering, 2013: 751-763.

Occulusion Enhanced Maximum Intensity Projection Algorithm

LuoYuetong, Zhu Huiguo, Han Juan, Xu Yunyun
(VCC Division, School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China)

Occlusion enhanced maximum intensity projection is to solve the problem that maximum intensity projection can′t convey occlusion cue correctly. It consists of two steps: firstly, K-Means clusting algorithm is used to extract structure features from MIP result images automatically; and then it adjusts rendering process adaptively according to structure features. Furthermore, the concept of rendering priority is introduced to avoid important features being occluded badly by non-important features, and an algorithm is provided to set rendering priority of structure feature automatically. Test result of several volume data indicates that OEMIP can enhance occlusion cue significantly, and rendering speed is enough for real-time interaction.

volume visualization; maximum intensity projection; occlusion cue; structure feature

TP 391

A

2095-302X (2014)03-0343-07

2013-08-23；定稿日期：2013-12-12

國家自然科學基金資助項目（11005028），（61070124）；安徽省自然科學基金資助項目（090412066）

羅月童（1978-），男，安徽青陽縣人，副教授，工學博士。主要研究方向為科學計算可視化、虛擬現實及計算機技術在核能領域的應用。E-mail：ytluo@hfut.edu.cn