李航;孙景文
【摘 要】Ray casting algorithm is widely used in medical field as a classical algorithm for image sequence rendering.Aiming at the problem that the ray casting algorithm is slow and can't meet the requirements of real-time interactive operation in the operation simulation,Combined with the advantages of the improved algorithm proposed by various scholars,it presents an accelerated volume rendering algorithm based on maximum entropy threshold segmentation and bounding box division,algorithm through 2D maximum entropy threshold segmentation,bounding box division,octree data storage format to maximize the filter to invalid voxel,so as to improve the ray casting algorithm rendering speed.Experimental results show,the improved algorithm proposed in it can improve the rendering speed by more than 3 times compared with the traditional ray casting algorithm,and can meet the requirements of real-time rendering.%光线投射算法作为经典的像序体绘制算法被广泛应用于医学领域.针对光线投射算法在手术模拟中绘制速度慢、不能满 足实时交互操作要求的问题,结合各学者提出的各种改进算法的优点,提出了一种基于最大熵阈值分割和包围盒划分的体绘制加速算法,算法通过二维最大熵阈值分割、包围盒划分、八叉树数据格式存储最大限度地滤去无效体素,从而提高了光线投射算法绘制速度.实验结果表明,提出的改进算法与传统光线投射算法相比在绘制速度上可以提高3倍以上,基本满足了实时绘制的要求.
虚劳病
高分一号分辨率【期刊名称】《机械设计与制造》
【年(卷),期】2017(000)012
【总页数】5页(P187-190,194)
【关键词】体绘制;最大熵;包围盒;光线投射算法
【作 者】李航;孙景文
【作者单位】河南科技大学机电工程学院,河南洛阳471003;河南科技大学机电工程学院,河南洛阳471003
【正文语种】中 文
【中图分类】TH16;TP391.41
s11306
利用计算机技术对CT（Computed Tomography）和MRI（Magnetic Resonance Imaging）设备采集到的二维图像进行三维可视化[1]，如对病变组织三维重建和显示等，便于医生从多角度、多层次进行观察和分析从而对病情做出正确的判断[2]。目前，医学图像的三维可视化方法主要分为面绘制和体绘制两类[3-4]。体绘制方法不仅能显示对象的表面结构，而且能够很好的显示对象的内部结构，有利于保留重构图像的细节和获得高品质的图像。光线投射算法作为一种经典的像序体绘制算法受到很多研究学者的青睐，对传统光线投射算法做出了很多改进研究，重点在提高绘制速度方面[5]。针对传统光线投射算法的改进方向主要分为数据的分类，数据采样以及图像合成三个方面，例如：光线提前终止法、减少对成像无贡献的体素的采样法等。文献[6]提出了一种基于自适应包围盒划分的体绘制加速算法，根据体数据的大小选择合适的Block维度，结合视窗与图像分割技术划分出自适应包围盒以减少光线投射中对空域的合成；文献[7]提出了一种基于二维最大熵阈值分割技术的体绘制算法，通过最大熵阈值分割技术滤去背景等无效体素以减少
对无效体素的重采样。文献[8]提出了一种基于OBB包围盒划分的空域跳跃光线投射算法，通过OBB包围盒划分出感兴趣区域降低需要采样的光线投射数量达到提高光线投射算法绘制速度的目的。这些算法虽然在提高光线投射算法绘制速度上都有一些效果，但是没有满足实时交互操作的要求，尤其在手术模拟时需要三维重构很大的体数据时更不能满足需求。针对以上问题，结合各学者提出的各种改进算法的优点，提出了一种基于最大熵阈值分割和包围盒划分的体绘制加速算法，简称为EBRC算法。
目前经典的体绘制算法主要有四种，这四种体绘制算法分别为光线投射算法（Ray Casting Algorithm简称RC算法）、足迹表法（Splatting Algorithm）、错切-变形算法（Shear-Warp Algorithm）、三维纹理映射算法（Texture Mapping Algorithm），其处理的数据对象都为规则的三维空间数据。目前体绘制算法根据其空间成像方式主要分为物序体绘制算法和像序体绘制算法两类，以图像空间为序的代表算法为光线投射算法，而以物体空间为序的代表算法为足迹表法[9]。以下为四种体绘制算法的详细比较。
Ray Casting算法对三位数剧场中每一个体素都进行光线合成，因此绘制图像质量高且有利于保存图像细节，特别有利于绘制边界特征模糊、灰度值相近的三维空间数据[10]。该算
法的不足之处在于处理数据量大时难以实现实时绘制且视线的方向或视点的参数改变会导致三维数据场的重新绘制；足迹表法也称为抛雪球算法，相对于传统Ray Casting算法对每个体素都进行光线合成操作来说，该算法只投射对成像有贡献的体素，大大的降低了时间复杂度，与传统RC算法相比，足迹表法绘制速度快而传统RC算法成像质量高；错切-变形算法通过把三维空间的重采样过程转换为二维平面的重采样过程，降低了计算复杂度，从而提高了绘制速度，该算法是目前公认最快的体绘制算法，其成像质量没有前两者高；三维纹理映射算法是为了解决体绘制算法不能利用图形硬件来提高绘制速度的缺点而产生的，该算法利用图形卡硬件通道来提高绘制速度，随着图形硬件技术的不断进步，该算法的绘制速度和质量会不断改善。在四种体绘制算法中，该算法的成像质量最差，绘制速度比较快。四种体绘制算法的性能评价，如表1所示。
十八和谐综合区3.1 改进算法原理
传统RC算法绘制速度慢的最主要原因是对三维数据场中每个体素都进行光线合成，实际上，在体绘制过程中有很多为空体素（即透明度为0的体素）或者对最终成像没有贡献的无效体素，这些体素在整体中的占比可以达到（70～95）%，称这些体素所在区域为空域或者无效区域，因此，在三维绘制过程中跳过空域可以提高绘制速度。
EBRC算法的主要思想：在整个光线投射算法中减少对空域的采样，尽量只对有效体素进行采样操作，从而降低时间复杂度。在执行Ray Casting算法之前，首先，对需要处理的体数据选择大小合适的OBB包围盒和二维最大熵阈值图像分割等预处理操作，设置合适的采样步长和视点位置，接着从屏幕上的每个像素点发出投射光线并在穿过规则的三维数据场时先判断射线是否与包围盒相交，若相交，则对包围盒内部的采样点进行累加合成操作，反之，在射线上的所有体素都不进行光照合成。采用图像分割和包围盒划分的方法保留感兴趣的区域，去除一些像空气、床板等无效区域以减少对空域的采样，由于OBB包围盒的形状为六面体，因此在包围盒内部还是会存在一定量的无效体素，通过线性八叉树编码的方法去除这一部分无效体素。EBRC算法主要包含三个方面：二维最大熵阈值图像分割；体包围盒的建立；线性八叉树编码。算法流程图，如图1所示。
药用辅料标准3.2 基于图像分割的空域跳过技术
空域跳过加速技术从基于空间种类上分为基于图像空间和基于物体空间两类的空域跳过技术[11]。采用窗技术结合传递函数的方式可以跳过空域，此外采用图像分割技术也可以实现，采用一种基于二维最大熵阈值分割技术实现基于图像空间的空域跳过。
单幅CT或MRI图像都可以定义为二维灰度函数，若一幅含有N（m×n）个体素的图像，设该图像上的每个像素点的灰度值及其邻域灰度平均值分别为f（x，y）和g（x，y），两者的灰度级数均为L，f（x，y）和g（x，y）对应的灰度级为i和j时的频度记为r（x，y）。g（x，y）定义为：
其邻域模板为：
其中，L最大值取255，m和n为大于1的奇数。
则二元组（i，j）对应的发生概率为 p（i，j）=r（i，j）/N，则得到该图的二维灰度直方图，如图2所示。
从图2可以看出二维直方图被阈值向量（s，t）分成4个区域，沿对角线分布的1区和2区分别代表目标和背景，远离对角线的3区和4区分别代表边界和噪声。因为1区和3区所包含的数据信息是我们感兴趣的区域，所以这两个区域是最重要的。通过确定最佳阈值可以把目标和背景区分开来。区分1区和2区的最佳阈值的公式如下：
定义离散二维熵为：
设1区和2区的总熵为φ（s，t），则判别定义式为：
依据最大熵原理，最佳熵阈值向量（s*，t*）满足公式为：
由于上面二维最大熵的判别定义式中没有考虑1区和2区所占比例的不同，所以引入权重系数α以调整1区和2区的灰度熵在判别定义式中所占的比重：
对人体膝盖部位CT扫描图像进行二维最大熵阈值分割，先求出整体图像的灰度均值，接着获取阈值向量（s，t），α取0.6。
3.3 建立体包围盒
包围盒技术已经在光线追踪、碰撞检测等计算机图形学领域得到深入的研究，在这里算法中主要用来把有效体素从整体中隔开，只需要对包围盒内的体素做光线合成，从而降低了时间复杂度。目前，应用在光线投射算法中的经典包围盒有轴对齐包围盒（AABB）、球体包围盒、轴向包围盒（OBB）和离散方向多边形包围盒（K-Dop）等[12]，如图 3 所示。
AABB包围盒虽然便于与投射光线进行求交计算，但是其紧密性不足且随着视点位置的改变需要更新包围盒，方向包围盒OBB相对于轴对齐包围盒AABB只能与坐标轴平行来说灵活性更高，OBB包围盒的最大优点是其方向任意性，所以其紧密性比AABB要好[13]。采用OBB包围盒进行光线投射算法运算时，首先判断投射光线与包围盒是否相交，若相交则对包围盒内的采样点进行光线合成，反之，不进行合成，接着进行下一条光线的判断，直至完成所有光线的判断与合成。
根据需要处理的体数据大小选择合适的包围盒，包围盒的维度大小关系着空域去除效率。在进行OBB包围盒的计算时，首先在三维空间内定义OBB包围盒的中心为O，以中心为O为坐标中心建立空间坐标系O-XYZ，XYZ轴的方向与包围盒边界平行，三个坐标轴相互正交的方向向量分别为v1、v2、v3，其相对应的边长分别为r1、r2、r3，则包围盒OBB所在的区域可表示为：
3.4 建立线性八叉树
线性八叉树结构存储是有效快速去除包围盒内无效体素的一种方法[14]。线性八叉树结构的构造步骤如下[15-16]：
