一种基于点集体素的多质物体分界面提取方法研究

宁小娟，刘 瑛，王怡轩，王映辉

(西安理工大学 计算机科学与工程学院，陕西 西安 710048)

多质物体的分界面提取是三维数据场可视化、逆向工程、三维重建领域的一个研究热点，也在医学、地质勘探等方面有着重要的应用。传统的等值面提取方法适用于标量场的可视化问题[1-2]。然而，在现实生活中几乎所有的物体都由三种或三种以上的材质组成，等值面提取方法很难支撑含有超过三种材质物体的重建工作。因此，提取多质物体分界面成为了当前研究工作的重点[3]。

目前，已有许多学者对多质物体分界面的提取展开了相关研究。Shamma等[4]提出一种提取多质物体等值面的方法。该方法首先将区域生长算法[5]和图割算法[6]相结合，对同一类材质的体素进行归类，然后使用移动立方体算法获取三角网格表示的各物质的分界面，但是当多质物体包含三种以上的不同介质时，由该算法提取的分界面变得不理想。Shamma等[7]又提出一种多图像分割方法提取体数据图像的边界表面。该方法首先确定一个初始种子区域，然后在边缘梯度小的地方使用限制的区域增长方法，最后使用速度函数进行轮廓扩张，直到给出整个图像的分割结果，从而获得边界表面。王明等[8-9]提出了对异质物体分界面提取与边界面重构的方法。该方法对已经标识材质的体数据分别提出了基于四面体和三棱柱的分界面提取方法，但是该算法不能一次性提取所需要的多个分界面。Wu等[10]提出一种能够处理多介质物体的移动立方体算法。Wang[11]提出了一个采用隐式的网格化形式表示多质物体分界面的方法，但是该算法无法保留分界面之间的边界信息。Wang等[12]提出一种从医学图像中检测具有连续变化的梯度幅度边界表面的方法。Zhang等[13]提出一种基于扩展加权最小二乘的体数据去噪方法，实现了多质物体的分界面提取，该方法在去除噪声的同时也能够保持清晰的特征。Ju等[14]提出一种扩展的移动立方体算法，将移动立方体算法和对偶算法相结合提取分界面，但是当介质数量超过三种时，该算法的效果明显下降。因此，本文通过给图像的每个像素点赋予相应的三维坐标，将其转为点集体素数据，在此基础上利用改进的球面收缩方法，一次提取出多质物体的所有分界面，然后对所有分界面进行分割与优化，从而确定各个分界面间的拓扑关系。

1 多质物体分界点标识

1.1 分界点的凸显

由于直接采用球面收缩方法对多质物体进行分界面提取时，会存在噪声点和局部分界面不清晰等问题。因此，本文在提取分界面之前先进行分界点的凸显。

1.1.1Gauss滤波去噪

在图像处理中，Gauss滤波方法[15]具有一定的去噪效果，可以通过调整Gauss分布参数σ改变平滑的程度。它的思想是对整幅图像的每个像素点加权平均，每个像素点的值都由其本身和邻域内的像素值通过加权平均得到。其具体实现过程是使用一个模板扫描图像中的每个像素，用模板确定的邻域内像素的加权平均值替代模板中心像素点的灰度值。该方法中使用的Gauss模板是通过离散化二维Gauss函数得到的，计算公式为：

(1)

式中：m和n表示图像的大小。

具体的去噪流程如下：

1) 计算Gauss模板。用式(1)计算Gauss模板M，M的大小为(2k+1)×(2k+1)，那么矩阵中的元素mi,j及矩阵M为:

(2)

(3)

2) Gauss滤波。滑动Gauss模板，使其中心位于图像I的(x,y)像素上，(x,y)位置的计算式为：

(4)

对整幅图像的每个像素运用式(4)即可得到Gauss滤波结果。本文给图像的每个像素点赋予了相应的三维坐标，对每个具体点迭代执行从而实现去噪。

1.1.2基于权重的分界点凸显

基于权重的分界点凸显是给邻域中心点及其邻域点赋予权重，以此来增大点的自身灰度值，减小其邻域点的灰度值，这样就可以增大邻域中心点与其邻域点灰度的差值，也更加合理地利用邻域对邻域中心的影响，从而凸显分界点。该方法的主要步骤为如下。

1) 计算权重矩阵。根据Gauss分布设定了一个权重矩阵，并将其归一化，得到一个3×3的权重矩阵W：

(5)

2) 计算任意一点P的灰度值结果。将点P的灰度值乘以权重矩阵中心元素值，P的邻域点的灰度值乘以权重矩阵中相应的权重值，然后用点P的计算结果和它的每一个邻域点的计算结果作差值，并对所有差值求和，该求和结果作为点P的灰度值。对于图像I(x,y)，被权重矩阵W覆盖的图像部分记为矩阵F：

(6)

F各位置对应的灰度值记为矩阵G：

(7)

式中：0≤gij≤255,1≤i≤3,1≤j≤3。

以图像的(0,0)位置作为起始位置，首先将权重矩阵W的中心元素与待处理点(0,0)重合，然后计算待处理点(0,0)的权重凸显结果。权重矩阵覆盖的图像的每个点加权结果记为resultij：

resultij=wij·gij

(8)

式中：1≤i≤3,1≤j≤3。记中心位置的结果为center，center=w22·g22那么待处理点(0,0)处的灰度值为(下式中对i,j同时求和)：

∑|resultij-center|

(9)

3) 对所有点迭代步骤2)，当所有点都计算结束时得到凸显分界点的结果。

以物体的一个截面为例，基于权重的分界点凸显方法见图1。图1(c)让权重矩阵中心(图1(a)红色框)与图像灰度示意图上的点(0,0)位置(图1(b)红色框)重合，计算权重矩阵每个元素和图像中对应位置灰度值的乘积，然后用权重中心处的结果和各个邻域点结果作差值，再对差值求和，该求和结果作为点(0,0)位置的灰度值。再次移动权重矩阵(如图1(d)所示)，使权重矩阵中心元素和处理点(0,1)重合，计算(0,1)位置的灰度值，依次按照该过程迭代处理所有点即可得到凸显分界点的结果。

图1 凸显分界点示意图

1.1.3基于球形邻域的分界点标识

通常描述某个点的局部特征时，需要借助其邻域点的信息。

邻域是一个特殊的区间，以点a为中心点的任何开区间称为点a的邻域，记作U(a)。对于任意一个点O，以O为圆心，定长r为半径作一个球，包含在该球内的点属于点O的球形邻域点[16]。

设以点O为球心的球形邻域中点的数量为n，点集为S，S={si∈S|0≤i≤n}，si表示第i个点，每个点对应的灰度值的集合为G，G={gi∈G|0≤i≤n,0≤gi≤255}，gi表示第i个点的灰度值，球心O的灰度值为go，则球心O的梯度grado为：

(10)

按照式(10)对每个点基于球形邻域进行转换计算，得到新的数据点集。材质相同的点集则灰度值都接近于0，而材质不同的点集则灰度值远大于0。按照此过程，本文完成一个个截面的分界点标识工作，将这些截面组合起来即可得到整个物体的分界点标识结果。

2 多质物体的分界面提取

2.1 改进的球面收缩方法

由于在球面收缩方法中，球面点遇到分界面就停止不再移动。因而，自遮挡部分的分界面上也就没有收缩后的球面点。针对此问题，本文对球面收缩方法进行改进，使得球面点在向球心移动的过程中，每遇到一次分界面就停止，并将球面点加入到提取分界面的结果中，直到球面点遇到球心，该球面点停止移动。同时由于分界面具有一定的厚度，因此，本文给所有的球面点设置一个标志位，标志位有0和1两个状态，0表示未遇到分界面，1表示遇到分界面。球面点的初始状态都为0，在移动的过程中检测到球面点遇到分界面时，设置球面点的标志位为1。接着让球面点继续向球心移动，移动过程中检测球面点的小球形邻域是否包含分界点，当检测到球面点的小球形邻域中没有分界点时，标记该球面点的状态为0，再继续向球心移动。通过这个方法可以使得球面点在同一个分界面上只停留一次，从而达到提取分界面的目的。

根据以上思路，改进后的球面收缩方法的具体过程分为以下四步。

1) 采用均值法[17]作物体的最小外接球，设球面点集的集合为P。

2) 对球面上任意一点pi，沿球心方向以一定的步长向球心O移动。在移动过程中检测点pi是否遇到球心O，如果遇到球心则点pi停止移动。反之，检测点pi是否遇到分界面，如果遇到分界面则点pi停止移动，并将点pi加入到提取分界面的结果中，同时将点pi的状态设置为1。

3) 点pi继续向球心移动，移动过程中检测点pi的小球形邻域是否有分界点，如果没有就设置点pi的状态为0，然后pi执行步骤2)。

4) 球面上所有的点都执行步骤2)和步骤3)操作，直到所有球面点全部移动到球心为止。

2.2 多质分界面的分割

在球面收缩方法中，球面点向球心移动的过程中遇到分界面是有先后顺序的,因此利用球面点遇到分界面的先后顺序进行分类，将同一顺序检测到分界面的球面点聚为一类，作为一个分界面，从而实现多分界面的基础分割。

该方法的具体实现过程是：在生成物体的最小外接球时，给球面点设置一个顺序属性type，并初始化所有球面点的type为0。在球面点向球心O移动的过程中，球面点每遇到一次分界面，球面点的顺序属性type就加1，当所有球面点都收缩结束时，将相同type的球面点聚为一类，表示一个分界面。

图2描述了基于球面点收缩顺序的分割方法。图中绿色点表示球面点，红色点表示第一次收缩到分界面上的球面点，蓝色点表示第二次收缩到分界面上的球面点。

图2 基于球面点收缩顺序的分割方法示意图

球面点在向球心O移动的过程中，第一次遇到分界面上的点是图中角α对应弧上的球面点，将这部分球面点的顺序属性type标记为1。然后球面点穿过分界面继续向球心移动，第二次遇到分界面上的点是图中角β对应弧上的球面点，将这部分球面点的顺序属性type标记为 2。球面收缩后，根据球面点的顺序属性type，把顺序属性相同的球面点聚类。将type为1的球面点聚为一类并标记为红色，type为2的球面点聚为一类并标记为蓝色，实现了采用球面点收缩顺序进行分类的方法。

2.3 优化分割结果

由图2可观察到，图中左下角红色点和蓝色点(右上角红色点和蓝色点)其实属于同一分界面，造成这一分割结果是由于在球面收缩方法中，球面点收缩顺序受分界面自身遮挡的影响，使得分割结果不准确。针对此问题，本文采用基于距离的聚类方法对多质分界面的结果进行进一步的优化。

首先，通过球面点收缩顺序的方法得到各个聚类，按照顺序属性值从小到大依次以每一个类为初始聚类中心，进行基于距离的聚类，将剩余类中满足距离条件的点加入到这个类中，直到没有点加入时停止，得到一个聚类结果。然后，选择剩余点中最小顺序值的那一类作为新的聚类中心进行迭代，直到没有剩余的点时优化结束。例如，图2中红色点的顺序属性type值为1，蓝色点的顺序属性type值为2。首先，以红色点为聚类中心，检测type值大于1的点，将其与红色点集中任意一点的距离小于一定阈值的点的顺序属性type设置为1，加入到红色点集中，直到没有点可以加入时结束。这样就可以通过基于距离的聚类方法将图2中左下角(或右上角)的蓝色点加入到左下角(或右上角)的红色点类中，表示一个分界面，从而实现多质分界面提取结果的优化。

3 实验结果与分析

3.1 实验环境与实验数据

本文实验的硬件平台为：CPU 为Intel Core i5-4460 3.2 GHz，内存为4GB，操作系统为Windows 7(64位)，编程平台为Visual Studio 2010。

本文的实验数据集包括两部分：一种是合成数据，一种是点集体素数据。本文中的Tomato数据主要是以PVM格式存储。对PVM格式的体数据，使用V3程序(来自：http://www.informatik.ni-erlangen.de)提供的PVM2RAW可执行程序将其转换为RAW格式，基于RAW格式进行进一步的处理。

3.2 分界点标识结果

为了验证本文方法的有效性，本文在相关的实验数据集上进行了实验。本文按照Gauss去噪、分界点标识、最后进行基于球形邻域的标识分界点，实验结果见图3。图3(a)和3(d)中红色框部分，可以看出红色框中该局部物质的灰度值和其周围邻域物质的灰度值过于相近，难以区分开来。然而，图3(d)红色框中该物质的灰度值和其周围邻域物质的灰度值已经有了很明显的差异，图3(c)是去噪后进行分界点标识，图3(d)可观察到在不丢失边界的前提下，可以将占整个物体体积比例很小的异质物体的边界清晰的表示出来。实验表明本文方法可以更加准确地标定出分界点，也较好地解决了受邻域信息影响导致的局部分界面不清晰的问题。

图3 Tomato模型截面的标识分界点结果

同时为了验证本文方法的效果，我们进行了对比实验，如图4所示。

图4 对比实验

图4(a)为原始数据直接进行标识分界点的结果，该结果对于整个物体体积比例很小的异质物体的边界描述不清晰。图4(b)为凸显边界点然后去噪再标识分界点的结果，可以看出其中的噪声点仍然较多。图4(c)为凸显边界点然后标识分界点再进行去噪的结果，此结果会导致边界缺失不清晰。图4(d)为本文方法，本文方法得到的效果相比较而言噪声少，边界较清晰。

3.3 分界面提取结果

本文分别针对由立方体和球体构成的多质物体以及Tomato模型进行多分界面提取实验。实验结果分别见图5和图6所示。

图5 多质物体分界面提取结果

图6 Tomato模型多质物体分界面提取结果

图5(a)是一个立方体里面包含两个相同的球体，图5(d)是球面收缩的结果，且收缩效果良好，球面收缩结果截面图5(e)也证实了这一点。从图中可以看出球面点(绿色点)很好地描述出了两个球体各自的形状，而其中有一部分球面点收缩到了球体的内分界面上(图5(e)红色框所示)，但两个球体的分界面很薄，对提取分界面的结果影响较小。图5(g)是在5(f)的基础上基于球面点收缩顺序的方法分割多分界面的结果。从图5(h)可以看出球面点收缩到球体的外分界面上和内分界面上表示出的结果不同。球面点收缩到球体外分界面上的结果如图5(h)中的红色点所示，球面点收缩到球体内分界面上的结果如图5(h)中的蓝色点所示，这个分割结果把收缩到两个球体分界面上的外侧点和内侧点各分为一类，该分割结果是不正确的。图5(i)是在5(g)的基础上采用基于距离的聚类方法对分割的分界面进行优化，因而得到了如图5(k)和5(l)所示正确的分割结果。

图6是对Tomato模型进行多分界面提取的实验结果。Tomato模型的球面收缩结果如图6(e)所示，可以观察到球面点(绿色点)都较好地贴合了Tomato模型中的各个分界面(黑色点)，收缩效果良好。对比图6(b)和6(f)可以观察到，提取的多分界面结果能良好的描述Tomato模型的外轮廓以及Tomato模型中的各个分界面，提取多分界面结果截面图6(g)也印证了这一点。其次，对提取到多分界面的结果(图6(f))采用基于球面点收缩顺序方法进行多分界面的分割。分割结果如图6(h)和6(i)所示，图中不同的颜色表示球面点不同的收缩顺序，图6(i)为其分割结果截面图，从图中可以观察到从边缘到中心，球面点的顺序值逐渐增大。最后，对多分界面的分割结果(图6(h))采用基于距离的聚类方法进行优化，其优化结果如图6(g)～6(n)所示。其中，图6(j)是优化后的多分界面分割结果图，图6(k)和6(l)是优化分割结果截面图，图6(m)和6(n)是最终得到的分割结果。

4 结 论

本文提出了一种基于点集体素的多质物体分界面提取方法，该方法可以正确有效地一次性提取多质物体的所有分界面，多个实验表明本文的提取效果良好。但是采用本文方法解决分界面自身遮挡问题时，有部分球面点会停留在分界面的内边界，虽然不影响对整个分界面的外形描述，但是结果不够准确。因此，在今后的研究工作中仍需进行深入的探索。