点击显示 收起
【摘要】 本文在Shear-Warp投影算法的基础上，提出优化的RLE体数据编码算法。该算法充分地利用Shear-Warp算法中体数据断层内的相关性，具有编码速度快、数据量少的优点。结合本算法可以实现在RLE编码下动态等值面提取。在实际的应用中验证了该算法的有效性。
【关键词】 Shear-Warp算法；RLE编码；等值面提取
在体绘制的算法中，各种优化的快速算法层出不穷。基于人叉树、K-Tree等算法的快速体数据遍历编码，把体空间分割为一定大小的空间，对不同空间进行统一递归编码［1，2］；Law和Yagel提出了基于时间连贯性、用于绘制动态数据的加速算法［3］，利用三维纹理加速器的体绘制方法［4，5］，并行与分布式体绘制方法［6，7］。这些算法都是依赖于某种连贯性进行加速绘制编码的，如时间、物体空间、图像空间、立体图和光线采样空间的连贯性等。
基于Shear-Warp算法的体绘制技术是一种有效的体绘制算法。由Lacroute和Levoy提出的Shear-Warp绘制方法中，通过一种特殊的遍历模式，来发掘图像空间和物体空间的连贯性［8］。RLE编码是对这种连贯性的一种编码方法。使用该方法进行等值面的绘制，在没有任何硬件加速条件下，绘制速度也可以接近交互绘制的要求。在这里我们提出一种优化的基于Shear-Warp算法的RLE编码，具有编码速度快，数据量少的优点。
1 RLE编码的基本思想
体数据场经过分类算法分类后，根据不同的阈值条件fV可以将体数据分为物体数据和背景数据两种。体数据的属性值（例如灰度值）不变，分类后的体数据通过人为地分配不透明度值来分辨物体和背景数据。a(xi)=1 if f(xi)≥fv 0 if f(xi)＜fv
上述公式中α（xi）代表体空间中xi采样点上的不透明度值，f(xi)代表xi处的属性值。体绘制算法通过对不透明度的计算完成对体数据中物体数据的重新采样，并通过合成算法得到正确的三维立体图像。
经过分类后的体数据，在体绘制算法中的投射光线方向上，背景体数据由于没有阻光能力（不透明度为0），所以不予计算或者可以直接跳过。所以对于体绘制处理算法，分类后的体数据场中存在着大量连续的透明体数据区。在Shear-Warp算法中，体数据中的扫描顺序与图像空间中像平面的扫描顺序完全一致，经过RLE运行长度上的编码后，采样合成阶段可以直接跳过大块的透明体素区，达到快速扫描、绘制的目的。
2 优化的RLE编码
优化的RLE碥码以体数据的切片为基本的编码单位。原始体数据场可以不经过任何的处理就进行RLE编码处理。如果辅助以原始体数据场的断层内部的四叉树编码可以实现对体数据场的快速分类和快速的RLE编码的构造。
2.1 数据格式
使用动态内存数组来管理编码后的RLE数据。首先对原始的体数据场根据理想视轴（x，y，z）进行剖分，剖分后的每一个体素切片都单独作为一个数组来处理。切片内部的体素以固定的行扫描方式进行RLE编码。
2.2 编码格式
编码头说明字段+编码数据。编码头说明字段由两个部分组成：数据头+数据长度。数据头由两个字节的ASCII码组成：QE代表该切片全部为透明体素；LE代表该行全部为透明体素；LB代表该行为混合的体素行。数据长度是一个字节的BYTE型数据，如果在short型数组内，则只使用低8位。该字段说明编码后的体素行的实际长度。该字段只能够表示256个体素的行长度，在对体数据编码过程中，遇到行长度大于256时，对扫描行进行分割，分割为256个体素为基本长度的若干个区域。同时根据已知的体数据场的长、宽、高控制扫描行的编码。
2.3 RLE编码
RLE编码分作3个部分：数据长度+该数据的具体值+指向下一数据段的指针。数据长度也使用一个字节来表示，在体数据长度为16位时，只使用数据的低8位。数据段的数据值包括密度值和体素点的空间梯度矢量值，最后一个字节是指向下一个数据段的指针，如果为16位数据，则只使用低8位。扫描行的最后一组数据段的指针为零。所以在该压缩编码中只包含了前景数据（物体数据）的编码，而对于背景数据作为透明数据处理，通过数据段指针可以实现跳过或者索引。这种结构由于没有保留透明区域的编码，大大地减少了编码的数据量，减少了对内存的需求。RLE编码的结构示意图见图1。
3 实验结果
实际应用中，优化的RLE编码在体数据的预处理阶段进行，由于处理过程编码简单基本为线性运算，结合断层内的四叉树编码，编码速度比传统的编码速度快大约30%，数据量减少大约5%。
以往的体数据RLE编码无法实现在编码数据场中对等值面提取或者其他的计算。在我们的实验中，使用文献［9］中的等值面提取算法，实现了在RLE编码中的动态提取等值面。提取后的等值面数据场仍然保持着RLE编码的格式。在绘制中极大地提高了绘制的速度，达到了交互绘制的水平，平均21.2帧/s。比传统绘制速度提高了大约50%。
不同分类阈值条件下的绘制结果见图2（略）。上面一行是采用传统的绘制方式的结果；下面一行是经过本文的算法，进行等值面提取后的绘制结果。
4 结论
优化后的RLE编码算法，通过数据头的编码结构，实现了对透明断层的简化编码（只保留数据头部分）；对非透明体数据的紧凑压缩编码，达到了快速编码，缩减数据量的目的。同时，结合动态的等值面提取技术，达到了没有硬件加速条件下的快速等值面绘制的目的。缺点是：该算法只考虑了二维空间中体数据断层内部的相关性，只能够用于Shear-Warp算法中，对于其他的体绘制技术无法推广使用。
【参考文献】
1 Levoy M.Efficient ray tracing of volume data.ACM Transactions on Graphics，1990，9(3)：245-261.
2 Subramanian K，Fussell D.Applying space subdivision techniques to volume rendering.IEEE Visualization，1990，150-158.
3 Asish Law，Roni Yagel.Exploiting spatial，ray，and frame coherency for efficient parallel volume rendering.Proceedings of Graphi Con，1996，2：93-101.
4 Shiaofen Fang，Rajagopalan Srinivasan，Su Huang，et al.Deformable Volume Rendering by 3D texture mapping and octree encoding.IEEE Visualization，1996，73-80.
5 Todd Kulick.Building an OpenGL Volume Renderer.SIGGRAPH Course Notes，1996，1-8.
6 Philippe Lacroute.Real-Time Volume Rendering on Shared Memory Multiprocessors Using the Shear-Warp Factorization.Proceedings of the 1995 Parallel Rendering Symposium，1995，15-22.
7 KwanLiu Ma，James S.Painter.Parallel Volume Visualization on Workstations.Computers & Graphics，1993，17(1)：31-37.
8 Philippe Lacroute and Marc Levoy.Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation.SIGGRAPH′94，1994，451-458.
9 B Csebfalvi，A Konig，E Groller.Fast Surface Rendering of Volumetric Data.Vienna University of Technology，Technical Report TR-186-2-99-13，1999.
*基金项目：国家自然科学基金资助项目（编号：60372062）
作者单位： 1 710068 陕西西安，中国科学院西安光学精密机械研究所
2 北京，中国科学院研究生院
3 130031 吉林长春，中国科学院长春光学精密机械与物理研究所
(编辑：商 洁)