等值面抽取技术(Iso-surfaces Extraction Technique)

等值面的抽取技术(Iso-surfaces Extraction Technique)及其绘制是三维空间数据场(体数据)可视化的重要组成部分。所谓等值面是指空间中的一个曲面,在该曲面上函数F(x, y, z)的值等于某一给定值V,即由S = {(x, y, z):F(x, y, z) = V}组成的一个曲面。等值面可视化利用现有的、由硬件实现的画面绘制功能构作清晰的三维空间数据场中的表面图像,其图形生成及变换速度较快,因而被广泛地应用于科学及工程计算结果数据的显示中[6]。

在三维空间数据场中提取等值面的方法很多。早期的轮廓跟踪法(Contour Tracing)[2]是通过提取每个二维切片(Slice)的二维轮廓线后,用三角面片跟踪连接属于同一对象在相邻切片上的轮廓线进而得到相应的等值面。该方法可以根据特定的需求,只提取感兴趣区域的轮廓线序列,然后重构出三维等值面。其主要的问题是每一个切片上可能存在多个闭合轮廓线,相邻的两个切片上的轮廓线的差别也可能非常大,使得跟踪连接相邻切片上的轮廓线的工作十分困难,对于复杂结构的跟踪可能会产生大量连接错误。

立方块法(Cuberille)[1]是首先根据等值面数值将体数据二值化后,考虑处于边界上的每个立方块(体元),连接其所有的外向的边界面。如果只考虑绘制的效果,可以直接将边界体元以不透明六面体的形式渲染。该方法算法非常简单,和其他方法不同,在体元内没有插值计算,对于数据的处理高度独立,适于并行处理。其主要问题是提取得到的等值面是由相邻垂直的小平面组成块状表面,不够平滑。可以通过自适应细分的方法,每次将立方块细分为八个更小的立方体,使用三线性插值法持续到获得足够光滑的表面。

图1 移动立方体法中等值面和立方体相交的15种不同的情况

在各类等值面提取方法中最经典的是由W. E. Lorenson和H. E. Cline1987年提出的移动立方体法(Marching Cubes)[3]。这一方法首先假定函数值在三维空间中均匀地分布在由立方体组成的三维网络的顶点上,并假定函数值沿立方体棱边作线性变化。在求出等值面与立方体棱边的交点后将它们按一定规则连接起来,就可得到近似表示等值面的一系列的多边形或三角形。根据立方体数值的不同,一共有256种相交情况。通过对称性简化,可以合并成为15种处理情况(如图1)。再利用计算机图形学中传统的画面绘制技术,就可以得到待求等值面的真实感图形了。此算法实现容易,得到了广泛的应用。但该算法产生大量散乱的三角面片、对某些层间距离较大的医学图像数据会产生“台阶”样的中间层、构造等值面时存在二义性等缺点,对等值面显示速度、绘制效果及后继简化等影响很大。其中产生歧义的情况,可以通过渐近线决策(Asymptotic Decider)法[5]等解决。

W.E. Lorenson和H.E. Cline提出移动立方体法后不久,他们发现,当三维体数据的分辨率很高时,移动立方体法生成的三角面片通常很小,其投影可能小于屏幕上一个像素点的面积,因此不必要插值计算三角面片。因此1988年两人提出了剖分立方体(Dividing Cubes)[4]的方法。剖分立方体法逐个扫描每个体元,当体元的八个顶点跨越等值面阈值时,将该体元循环细分,直到其投影大小不大于显示图像像素,将其作为一个点到投影显示到输出图像上。

上述的方法适合于具有规则结构的三维空间数据场的等值面提取。对于不规则体数据,可以细化划分为四面体后通过移动四面体(Marching Tetrahedra, MT)的方法获得等值面。这个方法和移动立方体方法类似,但更为简单,顶点的取值只有两种不同的情况,即只有一个顶点函数值大于等值面数值(和三个顶点函数值大于等值面阈值情况对称)和两个顶点函数值大于等值面数值的情况,相应对于生成等值面上的一个或两个三角形。由于四面体是最简单的多面体,其它任何类型的多面体都可以剖分解析为四面体,可以广泛适用于各类体数据。此外,在四面体内提取等值面不存在移动立方体方法中存在的二义性问题。

对于大规模的体数据,已有各类加速算法提供高效的等值面提取方法[6]。在提高移动立方体方法的效率方面有基于八叉树的等值面提取方法,在建立的八叉树的每个节点上存储其所有子节点的最大值与最小值。遍历八叉树时,可以直接根据子节点数值范围,跳过不可能含有等值面的部分。和基于几何空间分解的加速方法不同,基于范围查询 (Range-query)的算法通过建立跨度空间(Span Space),在数值空间上对体数据进行分解,可以同时应用于规则或者不规则数据。此外通过视点相关的方法,只考虑可见部分的等值面提取也可以在一定程度上提高效率。光线跟踪的方法不需要提取中间曲面,可以直接获得等值面的绘制结果。最近快速光线跟踪方法的进步,使这类方法具有一定的吸引力。该方法还适用于同时绘制多个等值面。其他等值面提取的技术包括利用Level-Sets或者利用极值图(Extrema Graphs)的方法。

等值面的提取以及绘制是体数据可视化的重要组成部分,特别在早期的可视化研究工作中受到了极大的重视,得到了长足的发展。目前等值面方法的工作已经日趋成熟,在处理海量数据等方面还有一定的挑战存在。

参考文献

  1. G. T. Herman, H. K. Liu, “Three-dimensional display of human organs from Computed Tomograms”. Computer Graphics and Images Processing, 9(1):1-21, 1979.
  2. E. Keppel, “Approximating Complex Surfaces by Triangulation of Contour Lines”. IBM Journal of Research and Development, 19(1): 2-11, 1975.
  3. W. E. Lorensen, H. E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm”. Computer Graphics, 21(4): 163~169, 1987.
  4. H. E. Cline, W. E. Lorensen, S. Ludke, C. R. Crawford, and B. C. Teeter, “Two algorithms for the Three-Dimensional Construction of Tomograms”, Medical Physics, 15(3):320-327, 1988.
  5. G. M. Nielson, Bernd Hamann, “The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes”, in Proceedings of IEEE Visualization 1991, pp 83-91, 1991.
  6. The Visualization Handbook, Edited by C.D. Hansen and C.R. Johnson, Elsevier 2005.

*注: 本文为所撰写《计算机百科全书》第三版条目,请勿转载。

评论关闭。