遮挡线索增强的最大密度投影算法

罗月童， 朱会国， 韩 娟， 徐云云

（合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）

遮挡线索增强的最大密度投影算法

罗月童， 朱会国， 韩 娟， 徐云云

（合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）

遮挡线索增强的最大密度投影算法（OEMIP）旨在解决最大密度投影法（MIP）不能正确表达遮挡线索的问题，它包括两个步骤：首先使用 K-Means聚类算法从MIP结果图像中自动提取结构特征；然后根据结构特征自适应调节MIP绘制过程以正确表达遮挡线索。此外，引入绘制优先级以避免重要特征被次要特征严重遮挡，并给出绘制优先级的自动设置算法。多个体数据的测试结果表明OEMIP能显著增强遮挡线索，且能实现实时交互。

体数据可视化；最大密度投影；遮挡线索；结构特征

直接体绘制（direct volume rendering，DVR）是最有效的体数据可视化方法之一，在医学、地理、物理等众多领域有广泛应用。传递函数（transfer function，TF）负责将体数据属性（如密度值、梯度模等）映射为颜色、透明度等光学属性，其质量对DVR的效果有决定性影响。虽然人们提出了很多传递函数的设计方法，但直观快速地设计合适的传递函数仍是可视化领域面临的重大挑战[1]。作为一种特殊的 DVR方法，最大密度投影[2]（maximum intensity projection，MIP）将投射光线上的最大密度值投影到屏幕上，无需传递函数，具有简单实用等优点，在医学等领域获得广泛应用。

因MIP只投影投射光线上的最大密度值点，

导致结果图像中缺少深度线索，不利于用户感知体数据的结构特征，为此人们不断尝试改进MIP方法。Heidrich等[3]根据深度调节密度值从而使距离视点越远的点越暗，以增强结果图像的深度线索；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图像的同时生成深度图像，然后在片段程序中根据深度图像调节MIP结果图像，从而增强结果图像的深度线索。

遮挡是最常用的深度线索之一，但MIP及上述改进算法均不能正确表现遮挡线索。如图1中内脏位于后肋骨前方，但在(a)和(b)中却是后肋骨遮挡了内脏，造成混淆。遮挡能够表达结构特征之间的前后关系，而MIP、DEMIP等算法均没有显式考虑结构特征，难以表达遮挡关系。因此，遮挡线索增强的最大密度投影算法（occlusion enhanced maximum intensity projection，OEMIP）被提出。OEMIP首先自动提取结构特征，然后基于结构特征控制绘制过程，从而准确地表达结构特征之间的遮挡关系。

图1 各种绘制方法的结果对比

1 相关工作

1.1 最大密度投影法

最大密度投影法因具有简单实用等优点而获得广泛应用，但也存在缺少深度信息、图像真实感不强等缺点，因此人们不断尝试改进MIP算法。为提高绘制结果图像中结构特征的连续性，Sato等[6]提出局部最大密度投影算法（local manximum intensity projection，LMIP），LMIP将投射光线最先碰到的局部极大值（大于给定阈值），而非最大值投影到对应像素上；光照对表达结构特征细节形状有重要价值，Zhou等[7]通过添加光照效果实现形状感知增强的最大密度投影算法（shaped enhanced MIP，SEMIP），增强MIP对局部细节特征的表达能力。增强MIP的深度线索一直是重要研究方向，Ropinski等[8]通过边界增强、改变结构颜色等方法实现深度线索的增强，虽然与文献[5]采用的方法有差异，但基本思想都是通过改变像素的颜色或亮度来体现深度信息。OEMIP的目标也是增强深度线索，但和上述方法不同，OEMIP方法是通过正确表达结构特征间的遮挡关系来增强深度线索，这是OEMIP

的最大创新之处。

1.2 体数据特征提取

特征能用于改进人机交互和渲染效果，因此特征提取一直是体数据可视化领域的重点研究内容。Tzeng和Ma[9]使用ISODATA聚类算法对体数据进行分类，允许用户通过聚类结果（特征）调整可视化效果，使交互过程更简洁直观；Wang等[10]使用高斯混合模型（Gaussian mixed model，GMM）拟合体数据的2D直方图，并将高斯模型作为特征以实现传递函数的半自动设计。光线穿越体数据所形成的标量曲线能反映体数据的特征，对一般而言，每两个相邻波谷之间的曲线段对应一个特征，很多研究人员利用这个事实改进体绘制算法。Malik等[11]通过分析标量曲线实现特征剥离；周志光等[12]通过分析标量曲线特征改进MIDA算法以揭示隐藏特征；罗月童等[13]依据标量曲线的分析结果实现考虑结构特征的自适应光线投射算法。标量曲线分析技术也被OEMIP用于提取结构特征。

2 遮挡线索增强的最大密度投影法

缺少遮挡线索会妨碍用户感知结构特征的前后位置关系，所以对有多个结构特征的体数

据，用户使用MIP算法难以进行有效地观察分析。OEMIP算法的目标是增强遮挡线索，算法的整体流程如图2所示：首先提取结构特征，然后使用结构特征调整绘制过程，从而增强遮挡线索。此外，OEMIP还自动为结构特征设置绘制优先级，以避免重要特征被次要特征严重遮挡。

图2 OEMIP整体流程

2.1 提取结构特征

结构特征是指具有一定意义的体素集合，如医学体数据中的心脏、头颅等器官，是体数据可视化需要展示的重要对象。有研究表明很多结构特征的密度值服从正态分布，如文献[10，14]中分析的结构特征的密度值服从正态分布，OEMIP方法也假设结构特征的密度值服从正态分布，并用表示结构特征。

聚类算法常被用于自动/半自动提取结构特征，如Tzeng和Ma[9]使用ISODATA算法提取结构特征。OEMIP是基于K-Means算法提取结构特征，是将MIP结果图像作为聚类样本（参考图2所示流程），而不是体数据，选择这种方案有两个主要原因：

（1）提高效率和鲁棒性：和体数据相比，MIP结果图像的规模要小很多，因此对MIP结果图像进行聚类分析的效率和鲁棒性都会有很大提高；

（2）能满足OEMIP算法的要求：OEMIP的目标是增强MIP结果图像的遮挡线索，仅需考虑在MIP结果图像中可见的结构特征，因此可以基于MIP结果图像进行结构特征的提取。

2.1.1 MIP绘制

投射光线穿越体数据时会产生密度曲线（如图3），密度曲线能有效体现体数据的特征[11]，如相邻波谷间的曲线段一般属于同一结构特征。为使MIP结果图像更全面地包含体数据的结构特征，对最大值所在曲线段进行采样（采样方法如图3），并将采样点的均值μ和方差σ保存在结果图像中。

图3 密度曲线

2.1.2 K-Means聚类

聚类是实现无监督分类的最有效方法之一，现有聚类算法可分为层次化聚类方法、划分式聚类方法、基于密度和网格的聚类方法等[15]。K-Means聚类算法因具有便于实现、时间复杂度低等优点而被广泛使用。OEMIP使用 K-Means算法对MIP结果图像进行聚类分析，并将聚类结果作为结构特征。K-Means算法的基本步骤与应用无关，但其中两个问题和应用密切相关：

（1）计算距离：即如何计算聚类中心 fi和样本 pj之间的距离；

其中K由用户指定。

虽然通常式(1)只有数值近似解，但对于一维正态分布 pi和 fj，有研究已证明存在如式(2)所示解析解：

因为已知样本 pij和聚类中心 fi均服从正态分布，所以令将和式(2)代入式(3)可得：

2.2 考虑结构特征的MIP绘制

通过考虑结构特征可以增强结果图像中的遮挡线索，但遮挡线索在帮助用户理解结构特征之间位置关系的同时也可能导致重要特征被严重遮挡从而妨碍用户观察重要特征。因此，通过引入绘制优先级的概念以进一步调整OEMIP的绘制过程，恰当地设置结构特征的绘制优先级，使OEMIP在增强遮挡线索的同时，也能有效地展现重要结构特征。考虑结构特征的MIP绘制包括两部分：

（1）设置绘制优先级：根据结构特征的重要度和相互遮挡关系自动地设置结构特征的绘制优先级；

（2）绘制最终图像：根据结构特征及绘制优先级控制绘制过程，生成最终图像。

2.2.1 绘制优先级

绘制优先级是用于解决重要结构特征被严重遮挡的问题，所以设置绘制优先级时需要考虑两个要素：

（1）结构特征重要度：虽然重要度的定义和具体问题密切相关，但不失一般性，可将结构特征的均值 μf作为）的重要度，即（2）遮挡率：遮拦率 O（fi, fj）表示结构特征 fi对的 fj遮拦程度。

基于“次要结构特征不严重遮拦重要结构特征”的原则，按以下步骤设置结构特征的绘制优先级 prior（f）。不失一般性，这里假设

第二步：更新遮拦率，计算所有特征对比其更重要特征的遮挡率，即计算j =1,2 … ,N,i ＜j ；

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

其中 εO是用户给定的阈值，表示最大可接受次要结构特征对重要结构特征的遮挡率，实验表明 εO= 0.6效果较好，因此，后续实验也均令ε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个结构特征的绘制优先级最高；③投射光线穿过多个具有相同最高绘制优先级的结构特征。对于第1种情况，OEMIP将投射光线的最大值投影到相应像素，和标准MIP一致；第2种情况按绘制优先级最高的结构特征设置像素颜色；第3种情况在绘制优先级最高的结构特征中选取距离视点最近的结构特征，从而增强遮挡线索，整个绘制流程如图5所示。

图4 三类可能的投射光线

图5 绘制流水线

投射光线穿越体数据产生密度曲线，密度曲线的局部极大值点具有代表性，因此基于密度曲线的局部极大值，而非采样点值判断投射光线和结构特征之间的关系更有鲁棒性，所以可按式(7)确定密度值I所属结构特征：

其中k可由用户指定，根据3σ法则可令 k= 3。

3 实验结果与分析

实验的配置环境如下：2.93 GHz Intel I3 CPU，2.0G内存，NVIDIA GeForce GTS450 GPU，编程编程环境为Microsoft Visual Studio 2008，程序主框架采用 C++编写，渲染相关功能采用CUDA实现，采用了CUDA SDK 4.2与OpenGL 3.1等函数库。

选用了合成数据、医学CT数据等对OEMIP进行验证，实验所用数据如表1所示。

表1 实验体数据

3.1 绘制结果分析实不符，该问题在OEMIP中得以克服。脚部体数据的结构特征包括骨骼、皮肤肌肉，使用OEMIP虽然能正确表达遮挡关系，但更重要的结构特征骨骼却被皮肤完全遮挡。绘制优先级用于避免重要特征被严重遮挡现象，对于合成数据、胸腔数据，因为重要特征未被严重遮挡，所以考虑绘制优先级后没有对OEMIP结果产生影响，但脚数据考虑绘制优先级后，能有效展示骨骼，即使骨骼处于皮肤的后面。

图6 不同绘制方法效果对比

综上所述，和MIP方法相比，OEMIP能有效增强遮挡线索，且通过考虑绘制优先级，能避免重要特征被严重遮挡的现象出现。

3.2 时间性能分析

和MIP相比，OEMIP增加了特征提取、设置绘制优先级等步骤，而且光线投射步骤也更加复杂，因此需要更多的绘制时间，但利用 MRT和CUDA等技术，仍然获得了大于10 fps的绘制速度（如表2所示），能满足实时交互的要求。

表2 OEMIP的绘制效率

4 总结与展望

MIP算法具有简单、直接等优点，在医学等领域有广泛应用，但MIP算法难以正确表达多个特征之间的遮挡关系，影响用户感知数据的空间结构。OEMIP算法通过提取结构特征，显式增强MIP结果图像中的遮挡线索，从而帮助用户更好地理解体数据的结构特征。针对次要结构特征可能严重遮挡重要结构特征的现象，OEMIP进一步引入绘制优先级的概念，通过绘制优先级避免重要特征被严重遮挡。使用合成数据、医学体数据的测试结果都表明OEMIP能显著增强遮挡线索，且能保证重要结构特征总被有效展示。

使用 K-Means聚类算法提取结构特征需要用户指定结构特征的数目K，虽然对常用数据这种方法可以接受，但对陌生数据，用户难以确定合适的 K，如何自动选取 K或采用类似于ISODATA等自适应聚类算法是未来的努力方向；另外，目前用于提取结构特征的聚类算法在CPU上运行，效率不高，如何基于CUDA实现结构特征提取，更充分地发挥 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