教学视频


第5章〓3D景物表达
中册第6章讨论了对图像中分割出的2D区域的各种表达方法。实际的客观景物是3D的，对其进行表达可直接采用3D方法。这里需要指出，从2D空间到3D空间的变化不仅是量的丰富，还有质的飞跃(如在2D空间中，区域是由线封闭而成的，而在3D空间中，仅仅有线并不能包围体积)，对视觉信息的表达和加工在理论和方法上都提出了新的要求。

客观世界中存在多种3D结构，还可能对应不同的抽象层次。因此，需要使用不同的方法表达各种不同层次的3D结构，以满足不同应用中后续加工的要求。

根据上述讨论，本章各节将安排如下。

5．1节介绍曲线和曲面的一些局部特征，它们在3D目标表面的表达中起着重要的基础作用。

5．2节讨论3D表面的表达方法，它们是对3D目标进行表达的常用方法。

5．3节给出在用体素表达3D目标的情况下，对其等值表面进行构造的两种算法。

5．4节介绍从3D目标的并行轮廓出发，通过插值，借助网格面元集合表达目标表面、实现表面拼接的技术。

5．5节介绍直接对3D实体(包括表面和内部)进行表达的方法。

5．1曲线和曲面的局部特征

曲线和曲面是构成3D实体的重要组件，也是观察实体时最先观察到的部分。为表达和描述曲线和曲面，需要研究其局部特征［Forsyth 2003］。微分几何是研究曲线和曲面局部特征的重要工具，下面讨论几个基本的概念。

5．1．1曲线局部特征

对平面曲线和空间曲线分别进行讨论。

1． 平面曲线特殊点的分类

先考虑平面上的曲线。如图5．1．1所示，设一条曲线C通过空间一个点P。通过点P且与曲线C相切的直线T称为曲线C在点P的切线(切线是割线的极限)。与点P的切线T相垂直且通过点P的直线N，称为曲线C在点P的法线。



图5．1．1曲线在由切线和法线

定义的坐标系中

设点P为原点，沿切线T的方向和法线N的方向为坐标轴的方向，则可构建一个局部坐标系统，以研究曲线在点P附近的性质。如图5．1．2所示，考虑第一象限中的一个点Q沿曲线C向P点移动，当它到达P点后继续运动，则它的下一个位置会有4种可能，分别位于一、二、三、四象限，依次如图5．1．2(a)~图5．1．2(d)所示。这4种情况对应4种不同的曲线C，或者说描述了曲线C在点P附近的4种变化。



图5．1．24种曲线变化情况


曲线上的点Q通过P点后如果到达第二象限，则称点P为一个规则点，而在其他3种情况下，都称点P为奇异点。奇异点还可进一步细分： 点Q通过P点后如果到达第三象限，则称点P为拐点； 点Q通过P点后如果到达第四象限或第一象限，则称点P为第一类或第二类尖点。

过点P的切线T是对曲线C在点P的最佳线性近似。如果能在点P建立圆周近似，就可定义曲线C在点P的曲率。曲率是沿曲线切线方向对变化速率的测度，它比切线或斜率能更好地表达曲线的特性。曲线C在点P的曲率可借助曲线上的另一点Q沿曲线向点P逼近计算。首先，考虑曲线C在点P的法线N和曲线C在点Q的法线M，两条法线有一个交点S，当点Q沿曲线向点P逼近时，交点S会沿点P的法线N到达极限位置O，它就是曲线C在点P的曲率中心。当点Q与点P间的距离随点Q沿曲线向点P逼近而趋于零时，法线N与法线M的夹角也会趋于零，上述夹角与距离的比值会趋于极限K，K就是曲线C在点P的曲率。K在数值上等于O与P距离r的倒数，称r为曲率半径，而以O为圆心、以r为半径的圆称为点P的曲率圆。

2． 高斯图

可借助高斯图描述曲线C。如图5．1．3所示，选定一个方向，使点P沿该方向遍历曲线C并依次将曲线C上的各点P与单位圆周上的各点Q对应。为此要使过点P的单位法线矢量与从单位圆心出发的终点为Q的矢量对应。这个从曲线向单位圆周映射的结果就是与曲线对应的高斯图。



图5．1．3平面曲线的高斯图


前面讨论曲率时，借助了曲线上一点Q沿曲线向另一点P逼近的过程。因为曲线可被映射到高斯图，所以逼近过程也体现在高斯图中。当点P′逼近点P时，点P′对应高斯图上的点Q′也逼近点P对应高斯图上的点Q。点P′和点P处的法线N′和N间的夹角对应单位圆周上连接Q′和Q的弧长。曲率就是高斯图上对应弧长度和曲线长度的比值在两者趋于零时的极限。

现在考虑一个点沿曲线的运动及其高斯图上对应点的运动。在规则点和拐点处，该点沿曲线C的遍历方向不变； 但在两类尖点处，该点沿曲线C的遍历方向会发生反转变化(参见图5．1．2)。其高斯图上的点沿单位圆的遍历方向在规则点和第一类尖点处不发生变化，而在拐点和第二类尖点处发生反转变化(参见图5．1．3)。将两者结合，根据一个点沿曲线C的遍历方向及其高斯图上对应点沿单位圆运动时的方向变化，可对4类曲线点进行分类，如表5．1．1所示。


表5．1．1曲线点分类表



分类点沿曲线遍历方向不变点沿曲线遍历方向反转变化


高斯图上点沿单位圆运动方向不变规则点第1类尖点

高斯图上点沿单位圆运动方向反转变化拐点第2类尖点


在对曲线C选出一个方向后，曲线C上任意一点的曲率可定义为一个符号。例如，可令凸点的曲率为正，即该点的曲率中心与该点法线矢量的顶点将处于曲线C的同一侧。同理，凹点的曲率为负，即该点的曲率中心与该点法线矢量的顶点将处于曲线C的两侧，拐点的曲率符号将改变，如果曲线的方向反转，曲率的符号也将反转。



图5．1．4空间曲线的局部几何

3． 空间曲线

空间曲线的情况常比平面内曲线的情况复杂得多。例如，空间曲线C上一点P可有无穷多的直线与该点的切线垂直，它们共同组成空间曲线在该点的法平面。又如，空间曲线C上一点的邻域点并不一定处于同一平面，但确实存在一个唯一的平面与这些点最贴近，该平面称为密切平面，其包含点P及趋于P的曲线点。通过点P并与法平面和密切平面都垂直的平面称为校正平面。由法平面N、密切平面T和校正平面R可建立以点P为中心(原点)的坐标系统，称为移动三面体或Férnet框架，如图5．1．4所示。其中，坐标系的3个轴分别对应切线矢量t、主法线(法平面和密切平面的交线)矢量n和副法线(法平面和校正平面的交线)矢量b，曲线C在P点的曲率中心为O。


空间曲线与平面曲线也有类似的地方。例如，可将平面曲线中高斯图的概念推广到空间曲线，不过此时表示切线、主法线和副法线的矢量端点处于一个单位圆球(高斯球)体上。空间曲线与平面曲线还有不同的地方。例如，不可能将空间曲线定义为一个有意义的符号。一般来说，空间曲线不存在拐点，其曲率在各个位置都是正的。

下面考虑密切平面上沿空间曲线变化的速率(可看作对曲率的推广)。设曲线C上有两个相邻的点P和P′，计算与其对应的两个密切平面之间的夹角(或对应两个副法线之间的夹角)，并除以其间距。当P′趋于P时，上述夹角和距离都趋于0，而其比值存在一极限，该极限称为曲线C在点P的挠率。曲线C上两个相邻点P与P′之间的弧长s可以设为有向的。点P的切线矢量t为单位速率dP/ds(定义为P′趋于P且两者间的距离趋于0时，矢量ΔPP′/Δs的极限)。如果s反向，则t也反向。进一步，加速度d2P/ds2与曲率K和主法线n之间存在如下关系： 
d2ds2P=ddst=Kn(5．1．1)
注意，曲率K是加速度的幅度，K和主法线矢量n都与曲线方向无关。副法线矢量可定义为b=t×n。与t类似，b依赖于曲线的方向。可以证明： 
ddsn=-Kt+τb(5．1．2)
ddsb=τn(5．1．3)
其中，τ为曲线在点P的挠率。

与曲率不同，对于一般空间曲线而言，挠率可以为正、为负或为零。其符号取决于曲线的遍历方向，并具有几何意义： 一般来说，曲线会以一个非零的挠率通过密切平面的每一点。当挠率为正时，曲线出现在密切平面的正面(副法线那面)； 当挠率为负时，曲线出现在密切平面的反面； 当挠率为零时，则为平面曲线。

5．1．2曲面局部特征

景物的表面可以是平面，也可以是曲面，可将平面看作曲面的特例。下列讨论的均为一般性曲面。

1． 表面法截线

先考虑表面S上一点P附近的性质。可以证明，对于通过点P且处于表面S上的曲线C，其所有切线均位于同一平面U上，平面U是过表面S上点P的切平面。通过点P且与表面S垂直的直线N称为表面S在点P处的法线，如图5．1．5所示。可以取点P处法线矢量的方向为表面S在点P处的局部方向。可见，表面上的每一点有唯一的法线，但可以有无数条切线。



图5．1．5表面一点的法线N、切线T、

切面U和法截线Ct

虽然通过表面S的点P处的法线只有一条，但包含该法线的平面(同时包含一条切线)有无数个(可将任一包含法线的平面绕法线旋转得到)。这些平面与表面S的交线构成一个单参数平面曲线族，称为法截线族。图5．1．5还给出了一条与曲线C的切线对应的法截线Ct(完全位于表面S中，但可以与曲线C不同)。


一般情况下，表面S的法截线在点P处是规则的，有时也会为拐点。法截线在点P处的曲率称为表面S在点P处相应切线方向上的法曲率。如果法截线与指向内部的表面法线位于切平面的同一侧，称法曲率为正； 如果分处两侧，则称法曲率为负。如果点P为对应法截线的拐点，那么表面S在点P处相应切线方向上的法曲率为零。

2． 表面主法曲率

由于可能有无穷条曲线通过表面上的同一点，所以不能直接将前面平面曲线的曲率定义推广至表面。不过对于每个表面，其上至少可确定一个具有最大曲率K1的方向，还可确定一个具有最小曲率K2的方向(对于比较平坦的表面，可能有多个最大曲率和最小曲率的方向，此时可任选)。换句话说，法截线在表面上点P处的法曲率会在绕法线的某个方向上取得最大值K1，也会在某个方向上取得最小值K2。一般将这两个方向称为表面S在点P处的主方向，可以证明其是互相正交的(除非法曲率在所有方向都取同一值，此时对应平面)。图5．1．6给出了一个示例，T1和T2代表两个主方向。



图5．1．6主曲率方向

可根据表面S在点P处邻域中两个主法曲率符号的异同判断该邻域的3种不同形状。如果两个主法曲率的符号相同，则点P处邻域的表面是椭圆形的，不跨越切平面。当曲率的符号为正时，点P处是凸的； 当曲率的符号为负时，点P处是凹的。如果两个主法曲率的符号相反，则点P处邻域的表面是双曲形的，表面S呈局部马鞍形并沿两条曲线通过切平面。对应的法截线在点P处有一个拐点。它们的切线位于表面S在点P处的渐近方向，这些方向被主方向隔开。椭圆形的点和双曲形的点在表面上组成块状区域，这些区域一般被抛物形的点组成的曲线隔开，在这些曲线上，两个主曲率之一为零。与此相应的主方向也是渐近方向，表面与其切平面相交处沿该方向有一个尖点。

类似于定义平面曲线的高斯图，也可定义表面的高斯图，此时一般称高斯球(更多讨论见5．2．2小节)。高斯球是将表面上的每个点映射到单位法线矢量与单位球的交点上得到的。对于平面曲线，高斯球在规则点附近是一一对应的，但在奇异点附近其遍历方向会改变。类似地，对于表面的椭圆点和双曲点，高斯球也是一一对应的； 而对于表面的抛物点，任何小邻域都包含具有平行法线的点，所以高斯球会有折叠［Forsyth 2003］。

3． 平均曲率和高斯曲率

将前面介绍的主法曲率K1与K2结合，可构成平均曲率H和高斯曲率G［Lohmann 1998］： 
H=(K1+K2)/2=tr(K)/2(5．1．4)
G=K1K2=det(K)(5．1．5)
平均曲率确定表面是否局部凸(平均曲率为负)或凹(平均曲率为正)。如果表面局部是椭圆类型的，则高斯曲率为正； 如果表面局部是双曲线类型的，则高斯曲率为负。

结合对高斯曲率和平均曲率的符号分析，可获得对表面的分类描述，也称地形性描述，如表5．1．2所示(这些描述也可用于深度图像分割，常称表面分割)。


表5．1．2高斯曲率G和均值曲率H确定的8种表面类型



H<0H=0H>0


G<0鞍脊最小/迷向鞍谷

G=0山脊/脊面平面山谷/谷面

G>0峰/顶面凹坑


用数学语言表示［刘1998］，峰点的梯度为零，且所有的二次方向导数均为负值。坑点的梯度也为零，但所有的二次方向导数均为正值。脊可以分为脊点和脊线。脊点也是一种峰点，但其与孤立的峰点不同，只在某个方向的二次方向导数为负值。相邻的脊点连接构成脊线，脊线可以是水平的直线，也可以是曲线(包括不水平的直线)。沿水平脊线方向的梯度为零，且二次方向导数也为零，而与脊线相交方向的二次方向导数为负。沿与弯曲脊线相交的方向必有负的二次导数，而且在该方向的一次导数必为零。谷也称沟，其与孤立的坑点不同，只在某些方向二次导数为正值(将对脊线描述中二次方向导数为负改为二次方向导数为正，就得到对谷线的描述)。鞍点的梯度为零，其两个二次方向导数的极值(在某个方向有局部最大值，在与之垂直的方向有局部最小值)必有不同的符号。鞍脊和鞍谷分别对应两个极值取不同符号的情况。

例5．1．18种表面类型示例

由表5．1．2可知，高斯曲率和均值曲率可确定8种不同类型的表面。图5．1．7分别给出了这8种表面类型的示例。


图5.1.7中示例图的位置排列与表5.1.2中的名称排列相同，其中，图5．1．7(a)对应鞍脊，图5．1．7(b)对应最小/迷向，图5．1．7(c)对应鞍谷，图5．1．7(d)对应山脊/脊面，图5．1．7(e)对应平面，图5．1．7(f)对应山谷/谷面，图5．1．7(g)对应峰/顶面，图5．1．7(h)对应凹坑。



彩图




图5．1．78种表面类型的示例□


5．23D表面表达

当人们观察3D场景时，首先观察到的是景物的外表面。一般情况下，外表面是由一组曲面构成的。为表达3D景物的外表面并描述其形状，可利用景物的外轮廓线或外轮廓面。如果给定外轮廓线，也可通过插值或“贴面”方法进一步获得外轮廓面。这里主要使用表面模型。

5．2．1参数表达

参数表达是通用的解析表达。

1． 曲线的参数表达

景物外轮廓线是表达景物形状的重要线索。例如，常用的线框表达法就是借助一组外轮廓线表达3D景物的一种近似方法。有些景物的外轮廓线可直接从图像中得到。例如利用结构光法采集深度图像时，可以得到光平面与景物外表面相交各点的3D坐标。如果将同一平面上的点用光滑曲线连接并依次显示这一系列曲线，即可表示景物表面的形状。有些景物的外轮廓线需要根据图像计算。例如为了观察生物体标本的内部，要将标本切成一系列切片，对每个切片采集一幅图像。通过对每幅图像的分割可获得每片标本的边界，也就是生物体横切面的轮廓线［Zhang 1991a］。如果要恢复原标本的3D形状，还需将这些轮廓线校正对齐并结合起来。

景物外轮廓线一般情况下为3D曲线，常用参数样条表示，写成矩阵形式(用t表示沿曲线从某点开始的归一化长度)为
P(t)=［x(t)y(t)z(t)］T0≤t≤1(5．2．1)
曲线上的任一点都由3个参数t的函数描述，曲线从t=0开始，在t=1结束。为了表示通用的曲线，使参数样条的一阶和二阶导数连续，P(t)的阶数至少为3。三次多项式曲线可写为
P(t)=at3+bt2+ct+d(5．2．2)
其中
a=［axayaz］T(5．2．3)
b=［bxbybz］T(5．2．4)
c=［cxcycz］T(5．2．5)
d=［dxdydz］T(5．2．6)
而三次样条曲线可表示为
x(t)=axt3+bxt2+cxt+dx(5．2．7)
y(t)=ayt3+byt2+cyt+dy(5．2．8)
z(t)=azt3+bzt2+czt+dz(5．2．9)

三次多项式可表示通过具有特定切线点的曲线，也是表示非平面曲线的最低阶多项式。

另外，一条3D曲线可隐式地表示为满足下式的点(x，y，z)的集合： 
f(x,y,z)=0(5．2．10)
2． 曲面的参数表达

景物的外表面也是表达景物形状的重要线索。景物外表面可用多边形片的集合表示，每个多边形片可表示为
P(u,v)=［x(u,v)y(u,v)z(u,v)］T0≤u,v≤1(5．2．11)
如果计算P(u，v)沿两个方向的一阶导数，可得到Pu(u，v)和Pv(u，v)，其都在通过表面点(x，y，z)=P(u，v)的切平面上，该点的法线矢量N可由Pu(u，v)和Pv(u，v)计算得到： 
N(P)=Pu×Pv|Pu×Pv|(5．2．12)
一个3D表面也可隐式地表示为满足下式的点(x，y，z)的集合： 
f(x,y,z)=0(5．2．13)
例如，一个中心为(x0，y0，z0)的半径为r的球可表示为
f(x,y,z)=(x-x0)2+(y-y0)2+(z-z0)2-r2=0(5．2．14)

3D表面的一种显式表达形式为
z=f(x,y)(5．2．15)
表面面元可用不同阶的双变量多项式表示。最简单的双线性面元(任何平行于坐标轴的截面都是直线)可表示为
z=a0+a1x+a2y(5．2．16)
而曲面可用高阶多项式表达。例如，双二次面元
z=a0+a1x+a2y+a3x2+a4xy+a5y2(5．2．17)
和双三次面元
z=a0+a1x+a2y+a3x2+a4xy+a5y2+a6x3+a7x2y+a8xy2+a9y3
(5．2．18)
另外，借助面元的概念，可将对表面的表达转换为对曲线的表达。设每个面元由4条曲线包围和界定，那么确定各面元的4条曲线，也可完成对整个表面的表达。

5．2．2表面朝向表达

通过表达3D景物各表面的朝向可勾勒景物的外观形状，而要表达表面的朝向，可借助表面的法线。

1． 扩展高斯图

扩展高斯图是表达3D目标的一种模型，其具有近似和抽象两个特点。一个目标的扩展高斯图给出目标表面法线的分布，从而给出表面各点的朝向。如果目标是凸多锥体，则目标和其扩展高斯图是一对一的，但一个扩展高斯图可能对应无穷多个凹形目标［Shirai 1987］。

计算扩展高斯图，可借助高斯球的概念。高斯球是一个单位球，给定3D目标［图5．2．1(a)］表面的一个点，将该点对应到球面上具有相同表面法线的点，就可得到高斯球［图5．2．1(b)］。换句话说，将目标表面点的朝向矢量尾端放在球中心，矢量的顶端与球面在一个特定点相交，这个交点可用于标记原目标表面点的朝向。球面上交点在球上的位置可用两个变量(有两个自由度)表示，例如极角和方位角或者经度和纬度。如果在高斯球上各点都放置与对应表面面积数值相等的质量，就可得到扩展高斯图［图5．2．1(c)］。



图5．2．1高斯球和扩展高斯图


考虑目标为凸多面体的情况，其各表面均为平面。该凸多面体可完全由其各表面的面积和朝向确定。利用各表面平面的朝向(法线矢量的方向)，可得到凸多面体的高斯球，因为凸多面体不同表面上的点不会有相同的表面法线矢量，所以其高斯球上每个点对应一个特定的表面朝向。这样得到的扩展高斯图具有如下特性： 扩展高斯图上的总质量在数值上与多面体表面区域面积的总和相等； 如果多面体是闭合的，则从任何相对的方向投影都可得到相同的区域。

上述方法可推广至光滑的曲面。定义高斯球上一个区域δS与目标上对应区域δO的比值在δO趋于零时的极限为高斯曲率G，即
G=limδO→0δSδO=dSdO(5．2．19)
如果对目标上一个区域O进行积分，则得到积分曲率
OGdO=SdS=S(5．2．20)
其中，S是高斯球上的对应区域。上式可允许处理法线不连续的表面。

如果对高斯球上一个区域S进行积分，则得到
S1GdS=OdO=O(5．2．21)

其中，O是目标上的对应区域。

式(5．2．21)表明可用高斯曲率的倒数定义扩展高斯图，具体是将目标表面上一点高斯曲率的倒数映射到单位球上的对应点。如果用u和v表示目标表面上点的系数，用p 和q表示高斯球上点的系数，则扩展高斯图定义为
Ge(p,q)=1G(u,v)(5．2．22)
上述映射对凸形景物是唯一的。如果目标不是凸体，则可能出现下面3种情况［Horn 1986］。 

(1) 某些点的高斯曲率会变为负数。

(2) 目标上的多个点会对球上同一点有贡献。

(3) 目标的某些部分会被其他部分遮掩。

例5．2．1扩展高斯图计算示例

给定一个半径为R的圆球，其扩展高斯图Ge(p，q)=R2，如果从球的中心观察区域δO，则观察立体角w=δO/R2，而高斯球上区域的面积δS=w。

2． 球心投影和球极投影

景物的表面朝向有两个自由度。为指定面元的朝向，可使用梯度，也可使用单位法线，其中表面法线所指的方向可用前面的高斯球表达。高斯球本身具有曲面形状的外表面，一般可将其投影到一个平面以得到梯度空间，如图5．2．2(a)所示。



图5．2．2球心投影和球极投影


考虑通过球且平行于Z轴的轴，可将球的中心作为投影的中心，将北半球上的点投影到与北极相切的平面上，称为球心投影。可以证明梯度为(p，q)的点在此平面上的位置为(-p，-q)。利用此平面定义梯度空间有一个缺点，即为避免混淆只能将一个半球面投影到此平面。


球心投影是方位投影的一种特殊情况，投影结果等效于从一个球心发出的光束透过球面照射在与球面相切的平面上所成的像。球心投影除了具有方位投影的一般性质外，其最大特性是能保持直线特征的几何属性，即3D空间中的直线经过球心投影后仍然为直线。借助这一特性，［岳2017］设计了一种利用球心投影纠正成像形变并计算点云在目标区域的投影坐标初值，以实现点云与全景影像配准的方法。

很多情况下，只关心观察者可看到的表面，这正对应北半球上的点。但也有其他情况，例如对于一个由背面照明的场景，指向光源的方向需要由南半球的点表示。这样就遇到梯度空间的一个难题，即对应高斯球表面的赤道上的点会投影到梯度空间的无穷远处。

解决以上问题的一种方法是利用立体图投影(也称球极投影)。投影的目的地仍是与北极相切的平面，但投影的中心是南极［图5．2．2(b)］。这样除南极点外，所有球面上的点都可唯一地映射到平面上，赤道的投影将是一个半径为球直径的圆周。如果设球极投影中的坐标为s和t，则可以证明
s=2p1+1+p2+q2t=2q1+1+p2+q2(5．2．23)
反过来有
p=4s4-s2-t2q=4t4-s2-t2(5．2．24)
另外，球极投影是高斯球上的一个保角投影，即球面上的角投影到平面上仍是相同的角。球极投影的缺点是有些公式比在球心投影中更复杂。有关球极投影的定义、性质及应用的更多讨论可见［刘2001］、［郑2003］。

5．3等值面的构造和表达

3D图像中的基本单元是体素，如果一个3D目标的轮廓体素具有确定的灰度值，那么这些体素点将构成一个等值表面，即该目标与其他目标或背景的交界面。下面介绍两种对等值面进行构造和表达的算法［Lohmann 1998］，并对其进行比较。

5．3．1行进立方体算法

考虑由8个体素构成顶点的立方体，如图5．3．1(a)所示，其中黑色体素表示前景，白色体素表示背景。该立方体具有6个(上下左右前后)邻接的立方体。如果该立方体的8个体素全部属于前景或全部属于背景，则该立方体为内部立方体。如果该立方体的8个体素中有的属于前景，有的属于背景，则该立方体为边界立方体。等值面应在边界立方体中(穿过边界立方体)。如图5．3．1(a)所示的立方体，等值面可以是图5．3．1(b)中的阴影矩形。



图5．3．1由8个体素构成顶点的立方体

与目标表面相交

行进立方体(MC)算法(也称移动立方体算法)是确定等值面的一种基本方法［Lorensen 1987］。该算法先检查图像中各个立方体，再确定与目标表面相交的边界立方体，同时确定其交面。根据目标表面与立方体相交的情况，处于立方体内部的目标表面部分一般情况下是一个曲面，但可用多边形片近似。这样的片很容易被分解为一系列三角形，而三角形又很容易进一步组成目标表面的三角形网。

算法逐次检查每个体素，从一个立方体行进到其相邻的立方体。理论上讲，立方体的每个顶点体素均可能为黑色体素或白色体素，所以对于每个立方体，可能有28=256种不同的黑白体素布局/构型。不过，如果考虑立方体的对称性，则只有22种不同的黑白体素布局。在22种不同的布局中，又有8种是其他布局形式的反转(黑色体素转变为白色体素或白色体素转变为黑色体素)。这样，只剩下14种不同的黑白体素布局，即只有14种不同的目标表面片，如图5．3．2所示(其中第一图代表目标表面与立方体不相交的情况)。



图5．3．2行进立方体布局


可将这些情况列入一个查找表，每当检查一个立方体时，只需从查找表中搜索以确定对应的多边形表面片。算法执行如下： 先从左上角开始整幅扫描3D图像中的第1层，到达右下角； 再从第2层的左上角开始整幅扫描，依次进行，直到最后一层图像的右下角。每扫描一个前景体素，就去检查该体素所属的由8个体素构成顶点的立方体。只要目标表面与立方体相交，就属于图5．3．2中后14种布局情况之一，可利用上面的查找表，找出各个对应的多边形表面片并进一步分解为一系列三角形。实际应用中常将256种布局情况全部列入查找表，以避免采用耗时更长的对称性和反转性验证。



图5．3．3有歧义的行进立方体布局示例

虽然上述黑白体素的分布情况不同，容易区分，但有些情况下，仅从黑白体素的分布并不能确切地获得与立方体相交的目标表面在立方体内的部分。事实上，图5．3．2的后14种布局情况中，第3、6、7、10、12和13共6种布局(对角顶点多为同色体素)均对应不止一种表面分布，或者说存在(确定平面的)歧义性。图5．3．3给出了一对典型的例子，其对应同一布局(第10种布局)，但目标表面分布存在两种可能。

解决上述歧义问题的一种方法是对基本布局中的有歧义的布局，通过添加其互补布局进行扩展。可将图5．3．3右图看作左图的互补布局。其他5种对有歧义布局扩展的互补布局如图5．3．4所示(其中前3图中的多边形片都已三角剖分)。实际应用中，可对其分别建立一个子查找表。每个子查找表包含两种三角剖分方式。此外，还需存储一个表以记录三角剖分方式的相容性。



图5．3．4对有歧义布局添加的5种互补布局


另外，还有两种方法均将布局对应为拓扑流形，一种称为面平均值法，计算歧义面上4个顶点值的平均值，通过比较该平均值与事先确定的阈值的大小选择一种可能的拓扑流形； 另一种称为梯度一致性试探法，借助歧义面上4个角点的梯度平均估算歧义面中心点的梯度，并根据该梯度的方向确定歧义面的拓扑流形。

除上述歧义问题外，由于行进立方体算法对每个立方体分别检验，未考虑整体目标的拓扑情况，所以即便没有采用有歧义的布局，也不能保证总能得到封闭的目标表面。一个采用行进立方体算法但没有得到封闭目标表面的示例如图5．3．5所示。图中两个初始的布局都得到了没有歧义的正确分解，但将其组合并没有得到封闭的目标表面。



图5．3．5采用行进立方体算法没有得到封闭的目标表面


例5．3．1三角形面元的不同组合

用两个三角形连接4个顶点并构成目标的表面部分有两种方法，得到的表面积和表面朝向都不相同。例如图5．3．6中，对于同样处于正方形上的4个顶点(其中数字指示该点相对基准面的高度)，图5．3．6(a)和图5．3．6(b)分别给出两种方式。按图5．3．6(a)方式得到的表面积为13．66，而按图5．3．6(b)方式得到的表面积为14．14。两者之间存在约3．5%的差别。



图5．3．6两种三角形面元的组合


□

行进立方体算法需要遍历目标的全部体素，逐次检查每个体素以确定等值面。对于实际景物，其全部体素中包含等值面的只是一小部分，所以遍历全部体素会浪费大量时间。为此，可采取另一种无须遍历的策略［刘2019］，先确定包含等值面的种子体素，再利用区域生长技术，直接选出与选定的种子体素相邻的、包含等值面的体素。实验结果表明，采用这种方法所需检查的体素数量只有原方法的1/400，整个算法的耗时减少了一半多。考虑到实际景物具有的连通性，［范2019］采取了类似的策略，区别只是在确定种子体素后，利用中值法结合对等值面的追踪近似实现。实验结果表明，采用这种方法生成的三角面片个数少了近一半； 在目视效果没有明显差异的情况下，耗时也减少了近一半。

5．3．2覆盖算法

覆盖算法也称移动四面体(MT)算法，可用于解决上述行进立方体算法得不到封闭目标表面的问题，从而保证得到封闭和完整的目标表面的三角形表示［Guéziec 1994］。不过该算法的缺点是其一般会产生多达实际需要数量3倍的三角形，所以还需要后处理步骤以简化多边形网格，从而将三角形的数量减少到可接受程度。

在此算法中，每次考虑的也是如图5．3．1(a)所示的具有8个体素的立方体。算法第一步将体素网格分解为立方体集合，每个立方体都有6个(上下左右前后)邻接的立方体。算法第二步将每个立方体分解为5个四面体，如图5．3．7所示。其中左边的4个四面体有两组长度相同的边缘(各3个)，而第5个四面体具有4个相同尺寸的面(图5．3．7最右)。可将属于四面体的体素看作在目标内部，而不属于四面体的体素看作在目标外部。



图5．3．7每个立方体分解为5个四面体




图5．3．8将立方体分解为四面体的

两种方案

立方体的四面体分解有两种方案，如图5．3．8所示。其中，左图和右图的两种方案分别称为奇方案和偶方案。对体素网格的分解是按奇偶相间进行的，就像国际象棋棋盘那样黑白交替，保证相邻立方体中的四面体可以互相匹配，以便得到协调一致的表面。


算法的第三步是确定目标表面是否与四面体相交。注意每个四面体都包含4个体素。对于一个四面体来说，如果其4个体素都在目标内部或任一个体素都不在目标内部，那么目标表面与该四面体不相交，在后续处理中就无须考虑了。

算法的下一步是估计在与目标表面相交的四面体中，目标表面与四面体各面(多边形)相交的边界。对每对边界两端的顶点可进行线性插值，通过逼近获得在连接每对顶点的边上的交点。如果使用4个顶点进行双线性插值，可能得到更好的效果。对于6邻接的体素，双线性插值与线性插值等价。对于对角边缘，设4个顶点的灰度值分别为a、b、c、d，得到的插值结果为
I(u)=(a-b-c+d)u2+(-2a+b+c)u+a(5．3．1)
其中，参数u沿对角线从0变到1。通过计算u0值，并使I(u0)=0，即可计算出交点。

可根据交点确定表面拼接后的顶点，如图5．3．9所示，共分3种情况。其中，拼接表面的朝向用箭头表示。朝向有助于区分每个拼接表面的内部和外部。根据约定，当从外部观察时，朝向是逆时针的。为使目标的拓扑稳定，在整个表面网格中都要遵守上面的约定。



图5．3．9表面相交的3种情况


5．3．3两种算法比较

移动立方体算法与移动四面体算法都是在3D标量场数据可视化、隐函数曲面显示、3D曲面重建等应用中提取等值面的常用方法。两种算法的比较如表5．3．1所示。


表5．3．1两种算法比较



算法体 素 单 元主要操作步骤离 散 逼 近


移动立方体立方体遍历立方体网格中的所有体素，依次判断每个体素的8个顶点与等值面之间的位置关系； 将交点作为逼近等值面的三角形面片的顶点三线性

移动四面体四面体遍历四面体网格中的所有体素，依次判断每个四面体的4个顶点与等值面之间的位置关系； 将交点作为逼近等值面的三角形面片的顶点线性


两种算法在构建等值面时都会产生一定的偏差。偏差的主要来源有两个： 三线性或线性假设； 在体素单元内用三角形面片逼近等值面。

关于两种算法的实验比较如下［王2014b］。

(1) 实验分别测试了4种等值面提取算法： MCA、MCL、MTA、MTL，其中，上标“A”表示等值面与体素边交点通过数值方法精确计算得到，上标“L”表示交点通过线性插值得到。两种算法的输入体网格类型不同，下面仅考虑四面体网格中的采样点数目与立方体网格大致相同的情况。

(2) 实验分别使用豪斯道夫距离、平均偏差和偏差均方差描述所提取等值面与真实等值面之间的最大偏离程度、平均偏离程度及偏差波动幅度。

(3) 实验分别使用5种具有不同次数的代数曲面。下面仅给出其中3种曲面结果的比较。3种曲面分别是： ①球面(2次)： x2+y2+z2=4； ②圆环面(4次)： (x2+y2+z2+R2-r2)2-4R2(x2+y2)； ③心形表面(6次)： (2x2+2y2+z2-1)3-0．1x2z3-y2z3=0。

对4种等值面提取算法借助3种不同次数的代数曲面进行实验，得到的平均偏差和偏差均方差结果如图5．3．10和图5．3．11所示。



图5．3．10等值面的平均偏差





图5．3．11等值面的偏差均方差


由图5．3．10和图5．3．11可看出： 

(1) 基于数值求根计算交点的算法的平均偏差均小于基于线性插值计算交点的算法。

(2) MTA算法的平均偏差总是最小。

(3) 由高次曲面得到的平均偏差总大于由低次曲面得到的平均偏差。

5．4从并行轮廓插值3D表面

对于3D目标表面，一类常用的边界表达方法是利用多边形网格(mesh)。这里多边形由顶点、边缘和表面组成，每个网格可看作一个面元。给定一组立体数据，获得上述多边形网格并用面元集合表达目标表面的过程称为表面拼接。5．3节的两种方法是对任意3D网格进行表面拼接的一般方法，本节考虑一种特殊的情况。

1． 轮廓内插和拼接

许多3D成像方式(如CT、MRI等)都是先逐层获得2D图像，再叠加得到3D图像。如果从每幅2D图像中检测出目标的轮廓，根据这一系列并行轮廓就可重建3D目标表面。根据并行轮廓插值3D表面时，每个轮廓都是2D的，它是轮廓内(部分)与轮廓外(部分)的边界； 而3D表面实际上是3D实体内外(部分)的边界。这是一个从2D边界到3D边界的过程。填充2D轮廓并堆叠，就可得到3D实体。这是一个从2D区域到3D体积的过程。

实际上，3D打印很好地诠释了这种3D表达方式。3D打印流程如图5．4．1所示，主要通过计算机CAD软件对拟打印目标进行3D建模，再将3D模型划分为逐层的截面和切片，由计算机控制打印机逐层(2D)打印，最后打印出3D目标［孙2022］。



图5．4．13D打印流程


根据并行轮廓插值3D表面的一种常用方法是用(三角形)面元进行轮廓间的内插。实际常以多边形的形式给出轮廓线，以节省表达数据量(见中册6．1．5小节)。此时要解决的问题可描述为用一系列三角形平面拼接成相邻两个多边形之间的表面。如果一个三角形有一个顶点位于一个多边形上，则剩下的两个顶点要位于另一个多边形上，反之亦然。主要工作包括两步。第1步是如何从相邻的两个多边形上确定一个初始顶点对，这两个顶点的连线构成三角形的一条边。第2步是如何在已知一个顶点对的基础上选取下一个相邻的顶点［Shirai 1987］，以构成完整的三角形。不断重复第2步，即可将构造三角形的工作继续下去，从而组成封闭的轮廓(常称为线框)。此过程也称轮廓拼接。



图5．4．2由轮廓线到轮廓面中顶点的选取

先看第1步。直观地说，相邻两个多边形上对应的初始顶点应在各自的多边形上有一定的相似性，即在各自的多边形上具有相似的特征。可考虑的特征包括顶点的几何位置、连接相邻顶点边的方向、两相邻边的夹角及从重心到边缘点的方向等。当多边形重心到边缘点的距离较大时，从重心到边缘点的方向将是一个比较稳定的特征。如图5．4．2所示，设从一个多边形边缘点Pi到该多边形重心的矢量为Ui，从另一个多边形边缘点Qj到该多边形重心的矢量为Vj，那么初始顶点对可根据使矢量Ui和Vj内积最大的原则确定。内积最大是指两个矢量尽可能平行且边缘点到重心的距离尽量大的情况。如果两个多边形相似，那么选择最远的顶点对即可。

再看第2步。选定了第一对顶点后，再选取一个顶点，即可组成第一个三角形。选择规则有多种，例如可根据三角形的面积、与下一对顶点的距离、与重心连线的取向等。如果基于与下一对顶点的距离，可选取具有最短距离的顶点对。但有时仅基于一种规则是不够的，特别是当顶点的水平位置不同时。

下面用图5．4．3介绍一种用于第2步顶点选取的方法，它是将图5．4．2的轮廓线向XY平面投影得到的。设当前的顶点对为Pi和Qj，Pi的X轴坐标小于Qj的X轴坐标，Pi+1Qj可能比PiQj+1短。然而由于PiPi+1与Qj-1Qj的方向相差很多，从表面连续的角度考虑，还是应倾向于选取Qj+1作为下一个三角形的顶点。具体来说还要考虑方向差。设PiPi+1与Qj-1Qj的方向差为Ai，Pi-1Pi与QjQj+1的方向差为Bj，那么当Pi+1Qj<PiQj+1时对下一顶点的选取规则如下(T表示一个预先确定的阈值)。



图5．4．3将图5．4．2的轮廓线向XY平面投影的结果


(1) 如果cosAi>T，表明Ai较小，PiPi+1与Qj-1Qj更接近平行，此时下一个顶点应选Pi+1。

(2) 如果cosAi≤T，且cosBi>T，则表明Bj较小，Pi-1Pi与QjQj+1更接近平行，此时下一个顶点应选Qj+1。

(3) 如果上述两个条件均不满足，即cosAi≤T，且cosBi≤T，则仍考虑距离因素，下一个顶点应选Pi+1。

2． 可能遇到的问题

可将上述对轮廓进行插值以获取表面的方法看作从矢量表达的平面轮廓中提取表面拼接的网格。这项工作比从具有体素数据结构的栅格图像中提取表面网格困难得多。由平面轮廓建立3D表面常遇到3种问题，可借助图5．4．4解释。



图5．4．4由平面轮廓建立3D表面常遇到的3种问题


（1) 对应问题

对应包括两个层次的问题。如果两个平面中都只有一个轮廓，那么对应问题仅涉及在相邻平面轮廓中确定对应关系和对应点。当平面之间的距离较小时，轮廓之间形状的差别也会较小，容易找到轮廓点间的匹配。但当平面之间的距离较大，且轮廓形状比较复杂时，则很难确定对应性。如果两个平面中都有不止一个轮廓，问题将更复杂。若需确定不同平面中的对应轮廓，不仅要考虑轮廓的局部特征，还要考虑轮廓的全局特征(有些方法将在第11章讨论)。由于约束不足，目前缺乏可靠的解决对应问题的全自动方法，某些场合还是需要人工干预。

（2) 拼接问题

拼接是用三角形网格建立覆盖相邻平面的两个对应轮廓间的表面，其基本思路是根据某种准则产生一组优化的三角面片，将目标表面近似地表达出来。这里采用的准则根据要求而定，例如表面面积最小、总体积最大、轮廓点间连线最短、轮廓点间连线与轮廓重心间连线平行等。尽管准则很多，但中心问题都是优化问题。另外，拼接在一般意义上讲还可用曲面拟合对应轮廓间的表面(上述使用三角形平面的方法是一种特例)，此时常使用参数曲面的表达方式，可获得较高阶的连续性(见5．2．1小节)。

（3) 分支或分叉问题

当一个轮廓从一个平面到相邻平面而分成两个或多个轮廓时会出现分支或分叉问题。一般情况下，分叉发生时的轮廓对应关系并不能仅由分叉处的局部信息确定，常需利用轮廓整体的几何信息和拓扑关系。解决这一问题的常用方法是利用如下的Delaunay三角剖分方法，由一组给定的输入顶点产生三角形网格［Lohmann 1998］。

除以上问题外，如果要在三角形网格或多边形网格的基础上通过选用参数曲面拟合获得光滑的表面，还要解决曲面拟合问题。可将网格点作为控制点进行。

3． 德劳内三角剖分和邻域沃罗诺伊图

1934年，苏联数学家德劳内(Delaunay)指出： 对于平面域上N个点组成的点集合，存在且仅存在一种三角剖分，即德劳内三角剖分，使所有三角形的最小内角之和为最大。德劳内三角剖分可使得到的每个三角形尽可能接近等边三角形，不过该定义并不完备。

根据德劳内三角剖分的定义，可导出其满足的下列两条准则(构造三角剖分算法的基础)。

(1) 共圆准则： 任意三角形的外接圆将不包含其他任何数据点，此准则也常被称为空圆盘性质。

(2) 最大最小角准则： 对任意相邻的两个三角形构成的四边形来说，德劳内三角剖分要求按该四边形的一条对角线分成的两个三角形中6个内角中的最小值将大于另一条对角线分成的两个三角形中6个内角中的最小值。此准则使德劳内三角剖分尽可能避免产生狭长、具有尖锐内角的病态三角形。

沃罗诺伊(Voronoi)图和德劳内三角形互为对偶。一个像素的沃罗诺伊邻域提供该像素的一个直观的近似定义。一个给定像素的沃罗诺伊邻域对应一个与该像素最接近的欧氏平面区域，即一个有限独立点的集合P={p1，p2，…，pn}，其中n≥2。

下面先来定义沃罗诺伊区域和直属沃罗诺伊图［Kropatsch 2001］。

利用欧氏距离
d(p,q)=(px-qx)2+(py-qy)2(5．4．1)
可将点pi的沃罗诺伊邻域定义为
V(pi)={p∈R2|i≠j: d(p,pi)≤d(p,pj)}(5．4．2)
包含邻域的边界BV(pi)，该边界包含满足下式的等距离的点： 
BV(pi)={p∈R2|i≠j: d(p,pi)≤d(p,pj)}(5．4．3)
所有点的沃罗诺伊邻域的集合为
W(P)={V(p1),V(p2),…,V(pn)}(5．4．4)
称为点集P的直属沃罗诺伊图，简称沃罗诺伊图。沃罗诺伊图中的边表示边界BV(pi)的线段，图中的顶点为线段相交的点。

德劳内图的顶点都是P中的点。当且仅当V(pi)和V(pj)在沃罗诺伊图中相邻时，pi、pj两点构成德劳内图的一条边。

构建沃罗诺伊图时，可先从最简单的情况，即只有两个不同的平面点p1和p2开始，如图5．4．5(a)所示。式(5．4．2)表明，p1的沃罗诺伊邻域V(p1)包含所有或者离p1（比p2）更近的点，或者与两点等距离的点。由图5．4．6(a)可见，所有与p1、p2两点等距离的点都正好落在p1到p2线段的垂直二分线b12上。根据式(5．4．3)和垂直二分线的定义，p1的沃罗诺伊邻域的轮廓BV(p1)就是b12。所有在由b12限定的包含p1的半平面上的点离p1（比p2）更近，它们将组成p1的沃罗诺伊邻域V(p1)。



图5．4．5构建沃罗诺伊图的垂直二分线方法


如果构建沃罗诺伊图时加上第3个点p3，就可构建一个三角形Δ123，如图5．4．5(b)所示。再次对三角形的每条边作垂直二分线，就可构建n=3的沃罗诺伊图。

图5．4．6为沃罗诺伊图和德劳内三角形的对偶性示例。其中图5．4．6(a)是一些平面点的沃罗诺伊图，图5．4．6(b)是其对偶，即德劳内三角形，图5．4．6(c)给出了两者之间的联系。



彩图





图5．4．6沃罗诺伊图和德劳内三角形的对偶性示例


基于构建沃罗诺伊图的式(5．4．1)~式(5．4．4)，可进一步构建区域沃罗诺伊图。

一个图像单元ij的区域沃罗诺伊图可定义为
Va(ij)={p∈R2|j≠k: da(p,ij)≤da(p,ik)}(5．4．5)
其中，图像单元ij与点p间的距离为
da(p,ij)=minq∈ijd(p,q)(5．4．6)
上式给出点p与图像单元ij中任意点p间的最小欧氏距离。一个图像单元的沃罗诺伊邻域是一个点集，从该点集到ij的距离小于或等于其他任意图像单元到ij的距离。类似于沃罗诺伊图，区域沃罗诺伊图的边界BVa(ij)可由下式给出： 
BVa(ij)={p∈R2|j≠k: da(p,ij)=da(p,ik)}(5．4．7)
该边界包含与两个或多个图像单元等距离的点(并不与其中某一个图像单元更近)。在沃罗诺伊图中，两个邻接的沃罗诺伊邻域的共同边界总是线或线段； 而在区域沃罗诺伊图中，边界总是曲线。

一幅图像的区域沃罗诺伊图Wa是所有图像单元的区域沃罗诺伊图的集合，即
Wa(P)={Va(i1),Va(i2),…,Va(in)}(5．4．8)
沃罗诺伊图是计算几何学中一种重要的数据结构。生成沃罗诺伊图的方法较多，常用沃罗诺伊图生成方法分类如表5．4．1所示［王2022b］。


表5．4．1常用沃罗诺伊图生成方法分类


类别优缺点分类特点具 体 方 法参 考 文 献


矢量法精度高，仅适合离散空间点要素的图，对包含线、面全要素的图生成较为困难
直接法直接生成要素

间接法先生成其对偶——德劳内三角网
分治法［Shamos 1977］

并行法［屠2015］

增量法［司2020］

可靠高效法［Held 2001］

质心法［王2021c］

自适应法［吴2022］


栅格法精度高的时间效率较低，时间复杂度低的精度较低
基于均匀栅格结构基于距离变换

基于层次栅格结构利用层次数据结构，空间复杂度较小

距离变换法［Chen 1999］

确定归属法［王2003］

栅格扫描法［Shih 2004］

扩张法［Guo 2011］

层次法［Liang 1998］

细分法［寿2013］



5．53D实体表达

对于真实世界中的绝大部分目标来说，尽管通常只能看到表面，但实际上它们都是3D的实体。这些实体可根据具体应用情况采用多种方法表达。这里主要使用体积模型。

5．5．1基本表达方案

3D实体的表达方案较多，下面对几种最基本和常用的表达方案进行简单介绍。

1． 空间占有数组

与中册6．2．2小节介绍的表达2D区域的空间占有数组类似，人们常用3D的空间占有数组表示3D目标。


图5．5．1空间占有数组表达3D目标示例

具体来说，对于图像f(x，y，z)中任一点(x，y，z)，如果其在给定实体内，则取f(x，y，z)为1，否则为0。所有f(x，y，z)为1的点组成的集合就代表了要表达的目标。示例如图5．5．1所示，图像体素与数组元素是一一对应的。


因为3D数组的尺寸是图像分辨率的立方，所以空间占有数组法只有在图像分辨率较低(且目标形状不规则)时才有效和实用。3D数组表达目标的优点是容易从中获得通过目标的各个截层，从而显示目标内部的信息。

2． 单元分解

单元分解是指将目标逐步分解，直至分解为可统一表达的单元，从而进行表达的方法。可将前述的空间占有数组表达法看作单元分解的一种特例，其单元就是体素。在一般的单元分解中，分解具有不同的形式； 单元还可能具有复杂的形状，但仍具有准不连接性，即不同的单元不共享体积。对分解后3D实体单元的唯一组合操作是粘接。


八叉树法是一种常用的单元分解法，其结构如图5．5．2所示。



图5．5．2八叉树结构


八叉树是2D图像中的四叉树(见中册6．2．3小节)在3D图像中的直接推广，可由递归的体积分解产生。八叉树表达法将目标在图像中的位置转化为分层结构树中的位置。由类似对四叉树的证明，可知对于n级的八叉树，其节点总数N最多为(实际应用中一般要小于这个数)： 
N=∑nk=08k=8n+1-17≈878n(5．5．1)
单元分解的基本原理适用于各种形式的基元。一个典型的例子是表面分解，其中可将3D结构外观看作各个可见表面的组合。表面分解用代表各个面元、边缘(面元的交)和顶点(边缘的交)的结点及代表这些基本单元联系的指针集合表示目标表面。图5．5．3给出了三棱锥体的表面分解示例，3种单元分别用3种符号表示，指针用连线表示。



图5．5．3三棱锥体的表面分解示例


表面分解的结果是所有(基本)表面的集合，这些表面也可用区域邻接图(RAG，参见中册7．3．4小节)表示。区域邻接图只考虑表面及其邻接关系(隐含顶角和边缘两种单元)，所以比图5．5．3的表达简单。

3． 几何模型法

几何模型法常在基于计算机辅助设计(CAD)模型的系统中使用。它也称刚体模型法，因为可用于表示刚体(非刚体的表达目前仍是一个具有挑战性的问题，尚无统一的方法)。刚体模型系统可分为两类： 在边界表达系统中，刚体用其各个边界面的并集表示； 在结构刚体几何表达系统中，通过一组集合操作将刚体表示为另一些简单刚体的组合。最低级(最简单)的是基元体，一般可用解析函数F(x，y，z)表达，并限定在F(x，y，z)≥0定义的封闭半空间交集区域之内。

例5．5．1边界表达和结构表达示例

图5．5．4(a)给出了一个两个几何体组合成的目标，图5．5．4(b)给出了该目标边界表达的示例，图5．5．4(c)给出了该目标结构表达的示例。



图5．5．4边界表达和结构表达示例□


5．5．2广义圆柱体表达

许多实际的3D目标可用2D集合沿某条3D曲线运动形成。一般情况下，该集合在运动中还可能出现参数变化。基于这种方式的刚体表达法通常称为广义圆柱体法，也称广义圆锥法。这是因为其中的基元体常为任意尺寸的圆柱或圆锥体，也可以是任意尺寸的长方体或球体(圆柱或圆锥体的变形)等。

广义圆柱体法通常用一个带有一定轴线和一定截面(广义)圆柱体的组合表达3D目标。换句话说，它包括两个基本的单元： 一根穿轴线和一个沿穿轴线移动的具有一定形状的截面，如图5．5．5(a)所示。将多个基元组合，可以逐级表示目标从高到低的不同细节，图5．5．5(b)给出了一个示例(其中每个圆柱体用长方形表示)。



图5．5．5广义圆柱体法示例


如果将基元作为变量，即改变穿轴线和移动截面，可得到一系列广义圆柱体的变形。事实上穿轴线可分为以下两类。

(1) 穿轴线是一条直线。

(2) 穿轴线是一条曲线(可以封闭)。

移动截面的变化类型或形式较多，主要分为以下三类。

(1) 截面的边界可以是直线或曲线。

(2) 截面可以旋转对称或不对称、反射对称或不对称，仅旋转或仅反射对称。

(3) 截面移动时其形状可以变化或不变化，如果变化，可以变大、变小、先大后小、先小后大等。

图5．5．6给出了广义圆柱体的一些变形的情况。将这些变形作为体基元进行组合，可表达复杂的3D目标。理论上讲，任意一个3D目标都存在无穷多个穿轴线和截面对。

将基本的3D广义圆柱体投影到2D图像会产生两种不同的结果，即条带和椭圆。条带是沿圆柱体长度方向投影的结果，而椭圆是对圆柱体截面投影的结果。如果考虑各种广义圆柱体的变形，则可能产生任意的结果，表达任意形状的实体。



图5．5．6广义圆柱体的变形



总结和复习






随堂测试