【摘要】 光线投影算法是医学图像三维可视化中常用的体绘制技术，算法原理简单，具有较高的成像质量，但绘制速度较慢。我们改进算法，利用投射光线与平面簇求交，快速确定融合片段，减少插值计算量，采用基于片段的融合绘制技术，加快融合速度，并且利用包围盒技术减少对无效平面的求交，提高了光线投影的效率。实验结果表明，改进后的算法既能保证绘制质量，又能显著减少计算量，提高体绘制的速度。
【关键词】 体绘制;医学图像;光线投影算法;平面簇求交;片段融合
Ray Casting Volume Rendering of Medical
Images Using Segment CompositionXU Ling，QIAN Zhiyu，TAO Ling
(Department of Biomedical Engineering， College of Automation， Nanjing University of Aeronautics && Astronautics ，Nanjing 210016，China)
Abstract：We presented an improved fast algorithm of ray casting volume rendering. Our algorithm could figure out composition segment fleetly and reduce interpolation calculation by intersection computation of the ray and a family of planes. Taken advantage of segment composition method， the composition velocity was accelerated. And utilizing boundary box technique， the algorithm avoided intersection computation with useless planes and greatly improved the efficiency of ray casting. The experiment results show that the improved acceleration algorithm can produce the required quality images， at the same time reduces the total operations remarkably， and speeds up the volume rendering.
Key words：Volume rendering;Medical image;Ray casting algorithm;Intersection computation of planes;Segment composition
1 引 言
医学影像的体绘制技术在临床上已成为辅助诊断和辅助治疗的重要手段。体绘制技术可分为间接体绘制和直接体绘制两大类，与间接体绘制相比，直接体绘制不仅能观察组织的表面，还能够透过表面观察到组织的内部细节，有助于医生对病灶部位做出正确的判断，更适合于临床应用。光线投影算法[1]是直接体绘制中效果较好的方法，具有较高的成像质量，可以显示医学影像数据场中细微的特征信息，且算法原理简单、易实现，其技术已成为近年来医学信息可视化领域研究的热点。但由于其投影光线数量巨大，严重影响了成像速度，为此，本研究在深入研究和综合分析各种加速算法的基础上[2-6]，提出了一种光线投影体绘制的综合加速算法，在保证绘制质量的基础上，有效地缩短光线投影算法的绘制时间。
2 光线投影算法原理
光线投影算法原理可简单描述为：根据设定的观察方向，从屏幕上的每一个像素点发出一条射线，见图1。射线穿过三维数据场，沿着射线选择若干个采样点，并由距离采样点最近的8个数据点的颜色值和不透明度值作三次线性插值，求出该采样点的颜色值和不透明度值，最后将每条射线上各采样点的颜色值及不透明度值按从前向后或从后向前的顺序进行合成，得到屏幕上该象素点的最终颜色值。
光线投影算法能显示出非常丰富的信息，甚至连数据场中细微的特征都不会丢失。但是光线投影算法的致命缺陷也源于此。首先，光线投影算法就是重采样点的光学属性按顺序进行融合的一个过程。假设像平面上有M个像素点，那么要发射M条射线，如果每条射线上选取N个采样点，则需要对M×N个采样点进行空间定位，为了得到较好的绘制效果，所需投射光线数量M和采样点个数N巨大，所以计算量很大，极大地影响了成像速度;其次，定位后采样点光学属性的计算采用三次线性插值的方法，该方法可取得较高的成像质量，但效率很低，用简单的插值方法又不能保证绘制质量。
鉴于传统光线投影算法的上述缺陷，我们提出了一种综合的加速算法，在保证绘制质量和不增加复杂度的前提下，有效地提高了绘制速度。
3 改进的光线投影算法
3.1 新算法的提出
在医学图像重建过程中，通常认为两两相邻平面间的采样点具有相似的光学属性，这样两两相邻平面间所截取的光线线段上的采样点组成一个片段，则一条投影光线可以被分为多个片段，并选取片段上和平面相交采样点的光学属性作为片段的光学属性，减少三次线性插值的计算量。改进后算法的主要流程见图2。
基于此，我们主要从以下几个方面对算法进行改进：(1)计算体数据立方体在像平面上的投影多边形，避免发出与三维数据场不相交的投影光线。(2)利用包围盒技术减少对无效平面的求交。(3)利用平面簇求交的方法快速确定相邻平面间采样点的个数及交点的光学属性，简化了插值算法
段的融合技术，减少了融合操作的次数和时间。(5)利用VTK库函数，简化算法的编写。前面两种技术在本课题组前期的文献[7]中有比较详细的阐述，这里主要介绍融合片段及采样点的获取技术。
3.2 融合片段的确定及采样点获取技术
两两相邻平面间所截取的光线线段上的采样点组成一个片段，显然，快速确定射线与平面簇的交点是融合片段确定的前提。对于三维规则数据场，从物空间一点(x0，y0，z0)出发，沿视线方向(l，m，n)的射线参数方程可表示为：
x=x0+l·t
y=y0+m·t
z=z0+n·t(1)
设体元编号为(i，j，k)，δx、δy、δz分别为X、Y、Z三个方向上网格点间距。不失一般性，假设Z轴方向的平面簇与射线方向垂直程度最高，其平面簇方程可表示为：
z=kδz(2)
其中k为整数(其取值范围从0到Z轴方向的最大平面数)，对于向量(l，m，n)=0，不失一般性，假设n=0，根据公式(1)和(2)可计算出射线和平面簇第k个平面交点P的坐标为：
xk=x0+l·kδz-z0n
yk=y0+mkδz-z0n
zk=kδz(3)
根据相邻平面间距离相等，可推算出其他平面上的交点坐标。
同样，如果知道射线和平面簇交点坐标，也可以推导出k的取值：
k=Zkδz(4)
设z轴方向第k个平面上各顶点处的光学属性为Mk1，Mk2，Mk3，Mk4，则P点的光学属性Mkp为：
Mkp=Mk1xkyk+Mk2(1-xk)yk+Mk3xk(1-yk)+Mk4(1-xk)(1-yk)(5)
根据公式(3)和(5)可计算出各相交平面交点处的光学属性，简化了三次线性插值计算。
当作为包围盒的封闭多边形设定后，计算射线和多边形的交点坐标，根据公式(4)确定k的取值范围，设k的取值范围为[α，β]，则射线上包含的片段个数为(β-α)。从射线和(α+1)平面交点处按采样步长确定重采样点坐标，并和射线与(α+2)平面交点坐标进行比较，记录重采样点个数n，当重采样点坐标超出射线与(α+2)平面交点坐标时，停止计数。由于射线和投影平面簇近似垂直，可以认为两两相邻平面间所截取的光线线段长度都相等，即相邻平面间采样点的个数都为n。
由于片段内的像素点具有相似的光学属性，基于对体数据的数据一致性分析，由基于像素点的绘制方程，可推导得到基于片段的绘制方程[8]。设M=(β-α)是一条光线中片段的个数;Cm和αm是片段的起始交点ti-1的光学属性，Cout和αout是片段的最后一个交点ti的光学属性，Cnow和αnow是片段两个交点之间的重采样点的光学属性，ni=n为片段的长度。用迭代的方法，依照从前向后的顺序有：
Cout=Cnow(1-αin)∑ni-1k=0(1-αnow)k+Cin
αout=αnow(1-αin)∑ni-1k=0(1-αnow)k+αin(6)
传统的由前向后的图像合成[9]如下：
Cout=Cnow(1-αin)+Cin
αout=αnow(1-αin)+αin(7)
比较式(6)和(7)，基于片段的绘制方程和原绘制方程具有相似的形式和计算过程，只是多了一个起加权作用的因子∑ni-1k=0(1-αnow)k，这是因为两种绘制方法的光学模型都是作用于像素点的，区别在于片段的光学模型融合的对象是光线片段，因此每次融合时需要加权片段中所有采样点的光学属性。随着影像学仪器能采集到的影像断层间距的减小，直接将断层间距作为融合片段，可以在提高绘制速度的同时保证绘制质量。
4 算法的实现过程
算法数据来自人体头颅横向MRI切片，数据大小为256×256×124体素，每个体素代表的人体空间的大小为0.94mm×0.94mm×0.93mm，像素灰度值范围为[0，560]，扫描厚度和采样间隔都为1mm。算法在处理器Inter(R) Celeron(R) CPU2.66G Hz，显卡VIA/S3G UniChrome Pro IGP，内存256M的微机上，利用VTK提供的库函数采用VC作为开发平台进行编程实现。主要实验步骤如下：
(1)清除图像缓冲区，建立图像空间和物体空间坐标系，通过vtkDICOMImageReader函数将数据读入内存并将体数据场形成的立方体投影到观察坐标系中，得到各可见面在像平面上的投影多边形，通过vtkRenderWindow函数设置视窗口参数。
(2)利用矩阵变换计算像平面上多边形顶点在物体空间的坐标位置，根据矩阵变换性质确定像平面上其他像素点的物体空间坐标位置。
(3) 遍历数据场，找到其中的包围盒以避免无效平面的求交。平面方程可表示为ax+by+cz+d=0，用10个这样的平面产生一个包围物体的封闭的多面体(所用平面越多，多面体越接近球形包围盒)。
(4)计算射线参数方程(1)和包围盒的交点，确定交点范围[MINs，MAXs](s=x，y，z)，根据公式(4)确定k的范围，然后计算射线参数方程(1)与k值范围内某一方向平面簇的交点，利用公式(5)插值计算交点处光学属性。
(5)计算某一相邻平面间线段上采样点的个数n，代入公式(6)中进行片段融合计算，得到像素点颜色值并写入相应的图像缓冲区。
(6)判断投影多边形内发射的投影光线是否处理完毕，如果没有则转向步骤(4)，若多边形内所有像素处理完毕，则往下执行。
(7)显示最终的重建图像。
5 算法结果及分析
为了验证本文算法的有效性，采用多组实验从图像质量和成像速度两个方面进行比较分析，本研究提出的加速算法均取得了比较好的结果。
一方面将本文算法与传统光线投影算法从不同视线方向所成的图像进行了比较。图3(a)为采用传统的光线投影体绘制算法得到的不同视线方向绘制效果，(b)为本文加速算法的绘制结果。从图中可以看出，两种算法成像的质量基本相同，成像效果较好，与传统的光线投影体绘制算法相比，本文算法重建的图像沟纹较深，变化较明显，但并不影响图像的整体效果和对细节的反映，脑中灰质、白质和耳朵的轮廓等细节都很清楚。
另一方面，将本文算法与传统光线投影算法从不同角度在绘制速度上进行了比较，表1给出了图3中不同视线方向传统光线投影算法和本文算法体绘制所需要的时间及加速比。从表中数据可得，本表1 传统光线投影算法和本文算法的绘制速度比较文算法比传统算法速度快近3倍，速度确实有了很大的提高。
从本文算法和传统算法的比较结果可知：本文算法在成像质量变化不大，效果较好的前提下，大幅度地提高了绘制速度。
6 小结
本研究针对标准光线投影算法计算量大、速度慢的特点，在原有算法的基础上，提出了一种新的光线投影体绘制综合加速算法。该算法利用光线与某一方向平面簇求交的方法快速确定融合片段，减少插值计算。采用基于片段的融合方法进行融合，提高融合速度，并利用包围盒减少光线与无效平面的求交。通过实验对比，本文算法成像效果较好，在保证成像质量的前提下，有效地提高了体绘制速度。
参考文献
[1]Tiede U， Hohne K， Bomans M， et al. Investigation of medical 3D-rendering algorithms[J]. IEEE Computer Graphics and Applications， 1990， 10(2): 41-53.
[2]NIU Cui-xia， FAN Hui， DU Hui-qiu. Accelerated algorithm of ray casting in medical volume rendering[J]. Journal of System Simulation， 2006， 18(1): 343-346.
[3]Jae Jeong Choi， Byeong-Seok Shin， Yeong Gil Shin， et al. Efficient volumetric ray casting for isosurface rendering[J]. Computers and Graphics， 2000， 24(5): 661-670.
[4]Freud N，Duvauchelle P，Le’tang J M， et al. Fast and robust ray casting algorithms for virtual X-ray imaging[J]. Nuclear Instruments and Methods in Physics Research， 2006， 248(1): 175-180.
[5]Markus Hadwiger， Christian Sigg， Henning Scharsach， et al. Real-time ray-casting and advanced shading of discrete isosurfaces[J]. Computer Graphics Forum， 2005， 24(3): 303-312.
[6]陈欣波. 医学图像三维重建算法研究及其实现[D].电子科技大学， 2007.
[7]TAO Ling， WANG Hui-nan， TIan Zhi-liang. Study on speed-up algorithm of re-sampled in ray casting volume rendering of medical images[J]. Transactions of Nanjing University of Aeronautics && Astronautics， 2005， 22(1): 20-26.
[8]张怡.实时光线投射算法加速技术研究[D].天津大学， 2006.