基于改进光线投射法的冠脉图像三维重建

王逸夫，王瑜，邢素霞，王怡宁，易妍

1.北京工商大学人工智能学院，北京100048；2.中国医学科学院北京协和医院，北京100730

前言

随着核磁共振成像（Magnetic Resonance Imaging,MRI）技术、计算机断层扫描（Computed Tomography,CT）、超声波以及电子内窥镜等医学设备的快速发展，使得传统的医学诊断方式有了巨大的改变，通过医学影像设备已经可以得到人体内部某一组织比较清晰的横截面二维数字图像，而连续二维数字图像序列包含了人体内各种器官的三维信息。在这种背景下，医学图像三维重建技术应运而生［1-3］。

光线投射算法是一种应用最广泛的图像三维重建算法，具有成像保真性高的优点，在医学可视化领域有着良好的前景［4-5］。然而光线投射算法重建图像的速度慢，难以满足实时交互性的需求。目前提高重建速度可以从硬件和软件两个方面考虑，但由于硬件成本相对较高，限制了应用范围，因此，从算法进行优化成了主要手段。何楠等［6］采用预积分分类方法满足奈奎斯特采样定律，消除光线投射算法产生的木纹效应，利用平行线切割投射光线的数学特性实现高效的插值方法，加速绘制速度。于水等［7］把体数据分成两部分，利用八叉树重构并剔除空块，使用图形处理器对顶点集合进行渲染并绘制图形，加速绘制速度。胡春红等［8］利用血管分支点和端点来优化几何变换矩阵中的平移向量，不仅能有效提高冠脉树的三维重建精度，而且可获得重建冠脉树在第三角度下的精确投影图像。徐超清等［9］利用自适应划分算法加强极值点区域的绘制，引入预积分光照算法，对预积分采样段进行体绘制积分，增强绘制的局部细节。徐冰［10］采用预积分光照算法，对预积分片段内的梯度进行插值重构，然后计算梯度中与射入光线夹角的最小梯度值，将该梯度值用于预积分光照渲染，加强了体数据中局部细节的光照效果。彭伟等［11］提出一种计算统一设备架构CUDA存储器的访存优化策略，给出了适用于CUDA存储器的空体素跳跃法，加快光线投射算法的绘制速度。李晓清［12］将每一条采样射线分为多个部分进行优化采样，再将各部分的结果进行融合，对算法进行两两分组并优化，降低了传统光线投射算法的计算复杂度。李航等［13］通过二维最大商阈值分割，包围盒划分，八叉树数据格式存储最大限度地滤去无效体素，提高算法绘制速度。Deakin等［14］计算近邻非空体素的切比雪夫距离，并将该距离存入距离图中，在采样数据合成时，将该距离值赋予空体素，能直接跳过连续的空体素，加快绘制速度。在上述算法的启发下，本文提出一种冠脉三维重建算法，通过改进重采样的三线性插值算法，并结合切比雪夫空体素跳跃法来优化和加速传统光线投射算法的运算速度，从而达到实时交互的目的。

1 研究方法

1.1 传统光线投射算法基本原理

光线投射法的基本原理首先对三维体数据场进行数据预处理，将得到的数据根据阈值进行分类，分类完成后根据传输函数得到每一个数据点的颜色值和不透明度值［15］。然后从屏幕上的每一个像素点发出一条射线，沿着射线按照预先设定的釆样步长进行重采样，对重采样点近邻的8个数据点进行三线性插值得到该重采样点的颜色值和不透明度值。最后对每条射线上所有采样点按一定规则进行合成，得到屏幕上这条射线的颜色，将屏幕上所有像素点的颜色值计算出来，最终得到一幅完整的三维图像。

该算法主要分为4 个步骤：数据值分类、赋颜色值和不透明度值、重采样插值计算和图像合成。其中占用时间比重最高的是重采样插值计算步骤［16］，所以优化并加快重采样中的插值运算，是提高光线投射算法运算速度的关键。

1.2 传统三线性插值方法

如上所述，插值运算是提高光线投射算法运算速度的关键，传统三线性插值方法的原理如下：投射的光线穿过三维数据场，在每条光线上进行等距采样［17］，新的采样点一般不在原始的数据点上，所以把新的采样点称作重采样点。重采样点的数据值通过对距离重采样点最近的8 个原始数据点的颜色值和不透明度值进行三线性插值［18-19］得到，传统的三线性插值算法示意图如图1所示。

图1 三线性插值示意图Fig.1 Diagram of trilinear interpolation

设dx、dy、dz分别为P点在x、y、z轴上相对于顶点V4的偏移值，重采样点P的坐标位置为P(x,y,z)，其他相邻的原始数据点为V0(i,j,k)、V1(i+1,j,k)、V2(i+1,j,k+1)、V3(i,j,k+1)、V4(i,j+1,k)、V5(i+1,j+1,k)、V6(i+1,j+1,k+1)、V7(i,j+1,k+1)。用Δx、Δy、Δz表示x、y、z方向重采样的间距，则。其中符号[ ].表示不大于括号中数值的最大整数。则三线性插值的运算过程分为以下3步。

（1）对x方向进行插值运算，求出P11、P12、P21、P224个点的值：

（2）对z方向进行插值运算，通过P11、P12、P21、P22求出P1、P2两点的值：

（3）对y方向进行插值运算，通过P1、P2求出P点的值：

将式（1）和式（2）带入到式（3），并展开如下：

其中，u=x/Δx-i,v=y/Δy-j,w=z/Δz-k。

1.3 改进的三线性插值方法

在传统三线性插值方法基础上，本文进行了如下改进。光线投射法中给数据点赋颜色值和不透明度值时会产生大量不透明度为0 的空体素，即图1 中的V0～V7的数据值可能为0，但却参与了三线性插值运算，会增加很多不必要的计算量。

本文根据V0～V7的数据值是否等于0，将式（4）分为28=256 种形式。例如V0的数据值为0，则最终P点的三线性插值为：

即最后进行运算时，少了4 次加减运算和3 次乘除运算。将公式用一个8 位的二进制数A 来表示，A的各位分别与V0～V7相对应，若Vn=0(n=0,1,2,3,4,5,6,7)，则与之相对应的二进制位数值为0。在重采样三线性插值运算时，首先对V0～V7的数据值进行检测，然后根据检测的结果得到的二进制数A来选择三线性插值公式的形式，以此来减少插值过程中的运算量。

在重采样前、后会生成大量的空体素，这些空体素会在后续的合成图像时参与运算，但由于是完全透明的，所以并不能被观察到。本文在重采样完成后，结合切比雪夫空体素跳跃法，使产生的空体素不参与最后合成图像的运算，进一步提高整个光线投射算法运算速度。图2是本文的改进光线投射算法的流程图。

图2 改进光线投射算法流程图Fig.2 Flow chart of improved ray-casting volume rendering algorithm

2 实验结果与分析

2.1 实验设备与数据库

本实验硬件与软件环境：CPU 为Intel Core i5-9300H 2.40 GHz，内存为8 GB，显卡为NVDIA GeForce GTX 1660 Ti，显存为6 GB，编程环境为Window10系统下的Visual Studio 2019。

数据库选用真实病人心脏CT 图像，来自北京协和医院，共215 张，每张图像大小为512×512 像素，层间距为0.5 mm。

2.2 客观评测方法

本文利用均方误差值和结构相似性对三维重建图像质量进行评测。均方误差值计算如式（6）所示：

其中，M为图像像素的列数，N为图像像素的行数，f1(x,y)和f2(x,y)分别为某一视角下原始三维图像与重建图像的3 个通道的像素值，数值越小，表示重建质量越好。

结构相似性计算如式（7）所示：

其中，μx和μy表示重建图像3个通道像素值的均值，σx和σy表示原始三维图像和重建图像的方差，σxy表示协方差，C1=(K1L)2和C2=(K2L)2是用来维持稳定的常数，通常情况下，K1=0.01，K2=0.03，L=255。SSIM范围为0～1，值越大，表示重建质量越好。

2.3 实验结果与分析

2.3.1 人工合成图像为了客观评测提出算法的有效性，笔者人工合成了三维圆锥图像，共20 张，每张图像大小为1 100×850 像素，层间距为0.75 mm，具体如图3a所示，Levoy 光线投射算法［5］和本文提出方法的三维重建结果分别如图3b和图3c所示。笔者重建了10 次圆锥图像，并对两种算法在时间上进行了比较，具体实验结果如表1所示。其中MSE 值和SSIM 值为重建10 次图像的算术平均值，平均绘制时间为重建10 次图像的平均时间，插值运算时间为重建10 次图像三线性插值运算的平均时间。

图3 圆锥重建图像比较结果Fig.3 Comparison of conic image reconstruction results

表1 两种算法重建圆锥图像的质量与速度对比Tab.1 Comparison of the quality of reconstructed conic image and reconstruction speed between two algorithms

由图3和表1可以得出，两种算法的MSE值与SSIM值大小接近，即重建出图像的质量相近，本文提出的算法对重建图像的质量没有产生较大影响。本文提出算法在运算速度上为Levoy光线投射算法的1.18倍，插值运算速度为Levoy光线投射算法1.41倍。

2.3.2 真实冠脉图像冠脉三维重建的实验结果如图4所示，Levoy 光线投射算法与本文改进的光线投射算法绘制结果是在同样的视角、大小比例下获得的。

图4 冠脉重建图像结果（右侧为左侧红框内局部放大图）Fig.4 Image reconstruction of coronary angiography(The right image is the local zoom-in of the red box in the left image)

笔者重建了20 次冠脉图像，并对两种算法在时间上进行了比较，具体实验结果如表2所示。

由表2 可知，本文提出算法的运算速度为Levoy光线投射算法的2.58倍，插值运算速度为Levoy光线投射算法的3.05 倍。上述实验结果表明，Levoy 的光线投射算法速度缓慢，而本文提出的改进三线性插值算法结合切比雪夫空体素跳跃法，能够在不影响最终绘制图像质量的情况下，有效地加快光线投射算法的运算速度。

表2 两种算法重建冠脉图像的速度对比Tab.2 Speed comparison between two algorithms for image reconstruction of coronary angiography

3 结论

本文提出了一种改进的三线性插值算法，并用于冠脉的三维重建，通过检测原数据点的数据值，简化传统三线性插值方法的复杂性，并结合切比雪夫空体素跳跃法，加快传统光线投射法的运算速度。实验结果表明，本文的方法能够在不降低成像质量的同时，有效地提高算法的运算速度。未来的工作是将提出的算法结合包围盒技术，并运用到图形处理器上运行，实现提出算法基于图形处理器的实时绘制。