基于体数据的建模和绘制的发展现状综述

基于体数据的建模综述现实世界中有许多物体、自然现象以及一些计算模型都可以用体数据描述。体数据可以看作是在有限空间中对一种或多种物理属性的一组离散采样。广义的体数据表示形式为：(X,f),其中｛X｝表示n维空间的采样点集合，f表示该点的物理属性，可以是标量值，如颜色、密度或向量值，如速度。图1中给出了三维体数据的示意。widthwidthSi体数据的定义Fig.1Thedefinitionof^-olumedata在图1中，体数据集合包含了widthXheightXdepth个体素。原点的体素位置是(0,0,0)，下一个体素的位置是(1,0,0)。X坐标继续增加直到达到第一行末，此时的体素位置是(width-1,0,0)；紧接这个点上面的点在第二行末，其位置是(width-1,1,0)；第一个薄片的最后一个点的位置是(width-1‘height-1,0)；这个序列将随着体数据集合的薄片的增加而继续着.对体数据的操作包括了投影变换、三维坐标变换、三维滤波和体数据合成等，这些操作的时间复杂度是O(widthXheightXdepth)，即与体素的规模成正比。关于体数据的表示、处理分析、建模和绘制方面的研究已经形成以们独立的学科体视化。其任务就是要揭示物体内部的复杂结构并已经广泛应用于从医学成像、造型设计、地质分析到工业检测、计算流体力学、有限元分析等领域。基于体数据的建模就是根据离散采样值构建物体对象的几何表达。当前，基于体数据的物体建模方法分为表面重建和体素重建两大类，其中表面重建主要是按照给定的阈值从体数据中抽取等值面，然后利用传统的表面绘制方法绘制此等值面。表面重建主要有以下几种：基于断层轮廓线的表面重构、基于体素的表面重构、几何变形法和造型法。1.表面重建1.1.基于断层轮廓线的表面重构其数学表达为：已知N层断层平面上的一组闭合曲线{Bk,k=1,2，…N},重建表面S(x,y)，其中：Bk={(x,y)IS(x,y)=ZJ。它必须解决如下四个问题：轮廓对应(CorrespondenceProblem)、轮廓拼接(TillingProblem)、分叉问题(BranchingProblem)和曲面拟和(Surface-fittingProblem)。其中轮廓对应，后三个属于几何重建的问题。1.1.1.轮廓对应在三维重建成像中，如果成像深度的分辨率大于成像区域内物体之间的最小距离，则无论采用那种方式，都很难正确确定轮廓的对应关系。深度分辨率一般应比物体之间的最小距离大得多，例如大10倍以上.在这种情况下，采用简单的重叠方法就能容易地确定轮廓的对应关系。这是因为在相邻的两个图像平面中，两个分离的物体的二维切片不会重叠。但是如果深度分辨率不是很高，即使采用比较好的轮廓对应方法，有时也不容易正确确定轮廓的对应关系。特别对于激光扫描共焦显微生物医学三维图像，由于该图像上有的物体是弯曲的，有的是分叉的，有的是有孔的等等。在这种情况下，若采用轮廓的椭圆拟合和柱体生长，则很难正确确定轮廓的对应关系。在［dl］中采用如下一种间隙跟踪的方法来解决轮廓的对应问题。下面介绍这种方法的基本步骤：首先,采用递进门限［p1］图像分割技术把图像分割成物体区域和背景区域，然后依次处理两个相邻图像平面对；⑵在z和z+1两个相邻图像平面中，采用双边界法区域标号［p2］技术来组建每个二维物体，并获得每个二维物体的轮廓和方向链码；对z和z+1两个相邻图像平面做OR运算和AND运算；如果OR运算结果集SOR中只含有一种元素(如图1(a)所示)，且二维物体在z+1平面上，则轮廓对应是一对零或零对一。在这种情况下，相应的二维物体或者是底面(底面在z平面上)，或者是顶面(顶面在z+1平面上)。如果OR运算结果集SOR中只含有两种元素，且参加AND运算的两个相交边界之间的最大距离d大于事先设定的常数门限T1，即d>T1,或者AND运算的结果集SANd的元素数与参加AND运算的最小集合的元素数的比值R大于事先设定的常数门限阈值T2，即R>T2，如图1(b)所示，则轮廓对应是一对一。否则，无对应关系，如图1(c)所示。如果OR运算结果集SOR中含有多种元素，如图1(d)所示，则轮廓对应可能是多对多或复合对应。在这种情况下，如果d>T1，或者R>T2,则相应的轮廓是对应的，否则是无对应的。无对应的轮廓按步骤4处理；如果对应的轮廓是一对一，则按步骤5处理；如果对应轮廓是一对多，则按曲面分叉处理。如果对应轮廓是多对多，再按最大距离的大小进行分组。若组内距离大，组间距离小，则每组是一种对应，如在图1(d)中，A'和A间的d大，而和B间的d小,故A和A，对应。同理，B和B，对应，C和C，对应。又因D和E与C，的R大，故D，E和C'对应，且C，D，E和C'是曲面分叉对应。

⑹无对应(h)诃一对应w)无对应图1轮廓对应示意图(二维物体A,B,C,D,E在z平面上，而A',B‘，C'在z+1平面上)1.1.2.轮廓拼接轮廓拼接就是把相邻两个图像平面中的两个相对应的轮廓，用三角面片连接起来，以构成一个封闭的曲面(如图2所示)。图2中，假设平面I和平面II是相邻的两个图像平面，且在平面I中有物体切片A和B；在平面II中有物体切片A'和B'；又假设物体切片A和A'同属一个物体，B和B'同属另一个物体，贝UA和A'的轮廓相对应，B和B'的轮廓相对应，而轮廓拼接就是把A的轮廓(..abcde..)和A，的轮廓(..a'bzc‘ez..),用三角面片(..，aazbz,abzb,bbc,bccz,cCd,Cddz,dd'e,d'eez,..)链接起来，构成封闭的曲面，且这个封闭的曲面是一个没有重叠，没有悬浮，没有交叉的三角面片。三角面片链接的方式可能是多种多样的，例如轮廓边be和b，c‘也可能用三角面片b，be，和be，e来拼接。到底采用哪种链接方式，需依赖于采用哪种链接准贝。由此可见，若链接准贝不同，其链接方式也就不同，贝生成的封闭曲面也就不同，这也就是说，拼接生成的封闭曲面不是唯一的。因为每一种曲面对应一种链接方式和一种优化准贝，所以很难说那种方式、那种优化准贝最好，最符合实际。轮廓拼接比较常用的一种方法是环行轮廓拼接方法86］，该方法拼接的优化准则是表面积最小，或者体积最大，或者两轮廓之间的跨接边(如图2中的虚线所示)之和最短；另一种方法是弹性匹配轮廓拼接方法［pll,P12］。这两种基本方法的优点是它们都是优化的轮廓拼接方法，虽然一般拼接效果都很好，但是由于其优化运算增加了运算量，即降低了运算速度，因此在本文的虚拟物体三维重建中，为了减少运算量和数据量，以提高显示速度，采用了轮廓的多边形简化和环行轮廓拼接方法。其中，轮廓多边形简化的基本方法是:在轮廓检测时，首先建立轮廓的方向链码；然后依次搜索方向链码，其方向改变的点就是多边形的角点，而方向没有改变的点就是多边形边上的点；最后保留角点，去掉边上的点；于是，这样就把轮廓简化成了多边形，并去掉了轮廓直线边上的冗余点。这样处理，既减少了轮廓拼接的三角形面片的数量，又不改变表面的拼接形状。环行轮廓拼接就是从一个轮廓(例如图2中的A)的某个点(例如A中的a点)和与其对应轮廓(例如图2中的Az)的对应点(例如A'中的a‘点)开始，沿着轮廓线依次用三角面片把轮廓上的点链接起来，以构成一个封闭曲面。在环行轮廓拼接中，本文采用跨接边长度最短，而不是采用跨接边长度之和最短来作为优化准则。这样由于就避免了轮廓拼接的迭代运算，从而不仅提高了运算速度，而且不影响总体的轮廓拼接形状。1.1.3.分叉问题进行处理曲面分叉时，文献［p8］提出的方法是通过插入中间临界状态轮廓，把一对多的轮廓对应分解成一对二的轮廓对应。但笔者认为，这种方法有如下两个问题：第1个问题是一对二的分解有时可能不成功，分解的结果仍然是一对多；第2个问题是一对二的问题，本质上仍然是一对多的问题。所以本文提出一种把一对多或多对一的轮廓对应，分解成一对一的轮廓对应的方法。这种方法是先采用数学形态学的方法来确定多轮廓的分界线，再用这些分界线把单轮廓分割成相对应的多轮廓，结果得到一对一的轮廓对应。下面介绍这种方法的基本步骤。在单一轮廓A'的区域内，对多轮廓A,B,C做8邻域的膨胀运算；在膨胀运算中，任何两个轮廓膨胀的公共点就是轮廓之间分界线上的点；多轮廓分界线与单轮廓A'的交点1,2,3就是单轮廓A'的分割点；重复多轮廓的膨胀运算，直到在单轮廓A'区域内，没有任何一点可以膨胀为止；在单轮廓分割点1,2,3处，把单轮廓A'分割成轮廓段12,23和31,再把相应的分界线201,302,103分别加到相应的单轮廓段12,23和31中，即构成封闭的新轮廓1201,2302和3103。这种新轮廓和多轮廓就形成一对一的轮廓对应：A和1201对应,B和3103对应，C和2302对应。图3基于数学形态学方法的分叉曲面分解图3中，多轮廓A,B,C和单轮廓A'是多对一的轮廓对应。深灰色表示多轮廓的8邻域膨胀运算结果。黑色线条01,02,03是由膨胀运算所得到的多轮廓的分界线。1.2.基于体素的表面重建基于体素的表面重建方法是在物体表面通过的每一个体素内构造小面片，由这些小面片重建物体表面，即通过构造体数据中的等值面来重建物体表面。一般这些小面片都是三角片。这种方法主要适用于密集体数据，并且由于这种方法假定全局拓扑结构由局部拓扑结构所确定，就不必考虑分叉的问题。它主要有：Cuberille算法、MarchingCube算法、DividingCube算法等。Cuberille算法Cuberille算法适用于正交密集数据场的表示，主要用于医学图像和无损探伤等三维图像的物体表面重建。该方法将三维图像中的每个像素看成是空间中的一个六面体单元，即体素。在体素内数据场具有相同的值，用边界体素的六个面拟合物体表面。这种方法的特点是简单易行，便于并行处理，但会产生严重的走样，显示图像给人一种“块状”的感觉，尤其在物体边界处锯齿状走样特别醒目。MarchingCube算法Lorenson和Cline于1987年提出的MarchingCube算法是一个被广泛使用的体数据等值面抽取算法，已被视为三维规则数据场等值面生成的经典算法，其基本思想是把三维图像相邻层上的各四个像素组成立方体的八个顶点，逐个处理三维图像中的中的立方体，分类出与等值面相交的立方体，采用插值计算出等值面与立方体边的交点。根据立法体每个顶点与等值面的相对位置，将等值面与立方体的边的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近表示。MarchingCube算法存在连接方式上的二义性，目前主要采用以下两类方法解决：采用双曲线渐近线交点来判断二义性面和采用四面体剖分。该算法的优点是生成的物体表面显示十分细腻，可生成的面片数目十分庞大，不利于实时操作。对于医学图像这类较复杂的图像一般都要生成几十万个面片,以至于用户无法对用面片绘制出来的图像进行旋转、平移、缩放等实时交互。DividingCubes算法在密集数据场处理时，包含物体表面的体素数量很多，每个三角面片很小，使得每个体素的投影接近像素大小，因此往往是显示精度而不是体素大小限制了图像的精度。一种更有效的的方法是直接在显示图像上显示像素点，这就是DividingCubes算法的基本思想。DividingCubes算法逐个扫描每个体素，当体素的八个顶点越过等值面时，将该体素投影到显示图像上。如果投影面积大于一个像素，则该体素被分割为更小的子体素，如此直至每个子体素在显示图像上的投影不大于一个像素大小，每个子体素在图像空间被绘制成一表面点。每一表面点由对应子体素的值、对象空间中的位置和梯度三部分表示，可采用传统的消隐技术如Z_Buffer算法，将表面点绘制到图像空间。该法是MarchingCube算法的一种很好的近似，它采用绘制表面点而非绘制体素内的物体表面面片，从而节省了大量的计算时间。几何变形法几何变形法是从采样体元数据集中抽取封闭等值面的方法。传统技术抽取的等值面几何表示缺少一种连通性的拓扑信息，是一种离散点插值的方法，而几何变形法是对原始数据的一种逼近表示。整个几何变形法过程描述如下：•定义一个拓扑封闭的简单模型；•基于一定的约束并保持拓扑简单性，对该模型进行几何变形、放大或缩小•模型上的每个顶点都有一个代价函数，用以评价其变形和拓扑结构的性质，噪声和特征之间的关系，在变形中维持代价最小。三维几何变形模型的约束函数的基本形式可表示为：Ci(x,y,z)=a0D(x,y,z)+a1I(x,y,z)+a2Ti其中：D(x,y,z)定义为三维空间中的势能场；I(x,y,z)定义为三维空间中的边界判定算子；造型法造型法是从数据集(x,y,z,F.)中构造一三变量插值函数F(x,y,z)来近似逼近原始数据集。造型过程可看作是一个将数据集(x‘,y.,z.,F.)映射到三变量函数M(x,y,z)的操作。可假定造型函数是一些基函数的线性组合，因此造型法的问题在于选择合适的三变量基函数。目前广泛使用的基函数是三次样条函数如：距离函数和分段Hermite函数。2.体素重建体素重建也称直接体绘制法。体素模型是以体素(Wxel)集合来表达物体，一般体素是三维正交网格的一个单元，是用于医学图像等生成的规则体数据的建模与可视化。与传统的表面重建相比，体素模型不仅具有物体的外部形状信息，还包含物体的内部信息。以体绘制方法来对体素模型进行绘制，可表现物体的内部细节和外部形状。体素模型可方便地进行模型间的布尔集合运算(并、交、差)。体素模型的建模也可用阈值分割法来区别出物体体素和背景体素。传统的表面几何模型也可通过体素化过程转化成体素模型来表达。对以体素表达的物体或对象进行操作和显示的研究已经发展成为一门新兴的学科---体图形学。体图形学是计算机图形学中新崛起的一个非常引人注目的研究分支，它在许多方面都优于传统的面图形学。利用体图形学的三维成像就是体素成像(volumerendering)，能够描述物体的内部是体素成像的最大优势，它为计算机图形学带来了生机并开拓了更加广泛的应用领域；并且，体素成像目前牢牢地控制了医学、细胞生物学、分子生物学和工业无损检测等方面的主要应用。所以，很多人预言“正如70年代光栅图形取代矢量图形一样，体图形学将要取代面图形学”。这个预言是否正确，还需要时间来验证，但确定无疑的是体图形学必将发挥越来越重要的作用。体素成像技术在美国等一些发达国家发展得极为迅速,而在我们国家才刚刚起步。[d1]何小海,罗代升等.三维虚拟物体表面重建的研究,中国图像图形学报,2002,11(7):1192~1197[p1]LuoD,DalyC,MacGrathJC.Iterativem