基于中轴点集分层螺旋信息的三维模型检索方法

具体实施方式

三维模型匹配的关键是提取一个能够有效匹配三维形状的描述符。该描述符应具有以下特性：(1)相似变换不变性；(2)快速计算；(3)具有简明的存储结构。

本发明使用中轴点集代替了中轴结构，且将中轴点集和它们的统计信息组合起来作为特征描述符。这样做的好处是：降低了计算复杂度，这是因为没有将中轴点集连接为骨架；保留了关键的骨架结构，因为通过基于势场方法提取的中轴点集是最重要的骨架信息；组合了模型的曲面信息；其中相似性度量方法减少了噪声的影响。

本发明提供一种基于中轴点集分层螺旋信息的三维模型检索方法，其流程如图1所示，包括以下步骤：

步骤一、对三维模型数据库中的每个三维模型进行坐标标准化预处理；

本实施例进行位姿标准化的方式是找到三维模型的唯一的包围盒，其采用一种法向量分布法来计算三维模型唯一的包围盒。该方法选取最大法向量分布作为一个主轴，首先计算出每个面片的面积，然后累加具有同样或相反法线方向的面片的面积。其中具有相同方向的法线被认为是具有相同的分布，具有最大面积的法线被定义为第一个主轴，剩余的法线分布中满足下列条件的法线方向被定义为第二个主轴：(1)具有最大的面积；(2)与第一个主轴正交。通过前面两个主轴的叉积运算得到最后一个主轴，本实施例采用通过面片的法线分布产生模型包围盒主轴方向的方法实现三维模型的位姿对准和标准化。

步骤二、对坐标标准化预处理后的除体元模型之外的三维模型进行体素化预处理；

位姿标准化后再将除体元模型之外的三维模型体素化为L×L×L的体元模型，其具体步骤为：首先将面片顶点体素化；再体素化面片的边，使用Bresenham算法解决平行于坐标平面的特殊边的体素化问题；然后体素化面片，体素化时分别将三角面片投影至XOZ、ZOY、YOX平面以得到面片的完整体素化，最后将三维模型内部体素化。

步骤三、对每个体素化的三维模型进行特征提取，得到每个三维模型的特征描述符，生成特征数据库；

对于体素化的三维模型，首先通过排斥力场函数提取三维模型的中轴点集，具体描述如下：

排斥力场方法的关键思想是给三维物体的边界充电以在物体内部产生排斥场。本步骤中，首先假设边界体元为点电荷，边界点被定义为一个物体体元距离坐标原点最近的立方体的角，内部点是在每个面上都邻接三维物体体元的模型体格中距离坐标原点最近的角，坐标原点被定义为三维模型包围盒的一个角。一个内部点的排斥力可以通过式(1)计算：

$F_P=\underset{i}{\Sigma }=(C_{i}P/R_i^m)---\left(1\right)$

其中，C_iP/R_i^m是点电荷C_i产生的力，F_P是在内部点P的排斥合力，C_iP是从C_i到P的标准化向量，它指明了力的方向，R是P和电荷C_i之间的距离，幂m称为该力函数的阶。

本步骤中，临界点是矢量力消失的点，只有一部分中轴点被当作临界点。矢量场中的临界点很难定位，尤其是因为它们不一定位于给定的采样位置，但是它们一般都位于采样点之间。如果力矢量(x，y，z)的三个分量都消失，矢量场就为零。也就是说，当某个区域中每一个矢量分量的符号都改变时，该区域就是包含临界点的候选区域。具体的说，首先假设体单元是最小的区域，并计算格子单元八个角的力场值，对于该单元所有的矢量分量(x，y，z)，如果即有正值又有负值，那么该单元就是潜在的候选单元，然后再将候选单元递归地分为八个子单元，并且对每个子单元重复做上述的候选性测试。其中，本实施例定义了下述规则：如果有两个或两个以上的候选子单元，则比较它们的力值并且选择具有最小力值的子单元替换原先的候选单元作为新的候选单元。处理过程终止的条件是：该单元未能通过候选性测试，或者该单元太小(用户指定大小的阈值)，此时该单元仍然作为候选单元保留。如果是后一种情况，临界点的坐标就被定义为该单元的坐标。但是如果所有的八个子单元都未能通过候选性测试，本实施例定义该单元的坐标为候选临界点。本实施例把从上述算法所提取的临界点和候选临界点称为中轴点。

接着，提取了三维模型的所有中轴点后，本实施例建立三维模型的中轴点集分层螺旋信息特征描述符，具体描述如下：

从三维模型提取的所有中轴点的集合被称为中轴点集。中轴点集描述的特征仅仅表示了物体中轴的大致轮廓，它不能评估两个拓扑相同但形状却不同的三维物体。总体来说，本实施例是将三维物体沿着X轴均匀的分层，并判断中轴点所在的层，然后从中轴点沿着平行于YOZ平面的方向均匀的发出射线，使从每个中轴点所发出的射线数量和两两相邻射线之间的夹角相等。这样，360度被均匀的分配到每一层，并保证任何不同层的中轴点具有不同的射线方向，任何同层的中轴点具有相同的射线方向。

首先本实施例做出以下几个定义：

定义1.分层螺旋射线集合

首先定义全局射线总数，全局射线总数是指从某中轴点的发射的射线数量与存在中轴点的层的数量的乘积。设全局射线总数为R，分层总数为N，且N可被R整除。则，每一层分布R/N条射线。以沿着三维模型的X轴分层为例，在YOZ平面上等角度(Δθ)发射R条射线，其中Δθ＝360/R。则第k层的射线与Y轴的夹角集合为θ_k＝{θ_k，j|0≤j＜R/N}，通过式(2)计算：

θ_k，j＝(k+j·N)·Δθ(2)

在这里，θ_k，j表示第k层中任一个中轴点的第j+1条射线与Y轴的夹角。则

θ_k＝{kΔθ，(k+N)Δθ，(k+2N)Δθ，...，(k+(R/N-1)gN)Δθ}，N层射线集合从全局上形成螺旋射线集合θ＝{θ_k|0≤k＜N}。

定义2.中轴点信息

第k层的第i个中轴点的信息定义为向量M_i＝(C_i，D_i)，其中，坐标信息C_i＝(X_i，Y_i，Z_i)代表中轴点的坐标位置；距离信息为D_i＝{D_ij| 0≤j＜R/N}，在这里，D_ij表示中轴点i的第j+1条射线。从中轴点i放射状地发射θ_k，j角度的射线R_ij，定义R_ij与模型表面首次相交的点为Inter_ij，则D_ij为中轴点i与Inter_ij之间的距离。

定义3中轴点集分层螺旋信息

组合所有中轴点信息M_i的集合就是中轴点集分层螺旋信息M＝[M₀，M₁，...，M_n-1]^-1，即模型的特征描述符。

提取中轴点集分层螺旋信息的步骤如下。首先，均匀地沿着X轴将一个三维物体分为N层，并构造分层螺旋射线集合。第二，判断中轴点i属于的层，并使点i沿着该层的射线方向放射状地等角度发出R/N条射线，在这里，R是分辨率参数和射线的分布总数(即全局射线总数)。第三，我们沿着第j+1条射线用射线跟踪算法计算Inter_ij的坐标值(与射线相交的最近的体格单元的坐标)。接着计算每个中轴点i和Inter_ij之间的距离D_ij，并结合坐标分量距离构造中轴点i的信息。最后，得到模型的特征描述符M＝[M₀，M₁，...，M_m-1]^-1，即该模型的中轴点集分层螺旋信息。

步骤四，将用户提交的三维模型首先进行预处理、然后体素化为体元模型，再进行特征提取得到该三维模型的特征描述符；

将用户提交的查询三维模型首先进行坐标标准化预处理、然后体素化为体元模型，再进行特征提取得到该三维模型的特征描述符，具体步骤如下：对用户提交的查询三维模型按照步骤一中的方法进行坐标标准化预处理，获取标准化后的三维模型；对坐标标准化后的除体元模型之外的三维模型按照步骤二中的方法进行体素化预处理，获取体素化的三维模型；对体素化的三维模型按照步骤三中的方法进行特征提取，得到用户提交的查询三维模型的特征描述符。

步骤五、将用户提交的三维模型特征描述符与特征数据库中的所有特征进行匹配，计算相似距离并排序，最终生成检索结果。

构建完用户提交的三维模型的中轴点集分层螺旋信息特征描述符之后，本实施例用一种匹配方法将该特征描述符与特征数据库中的特征进行匹配。有许多相似性匹配方法，如Euclidean距离、Manhattan距离、Hausdorff距离等。本实施例提出了一种基于Hausdorff距离的多级加权相似性匹配方法来进行三维模型之间的匹配。首先定义如下几个概念。

定义4中轴点加权信息

在中轴点信息的基础上，本实施例定义中轴点加权信息为：

其中，C_i⁺是坐标加权信息，D_i⁺是距离加权信息，ω₀是中轴点类型的权值。

定义5中轴点加权信息的距离

任意两个加权信息向量M_i⁺和M_i⁺的距离被定义为：

其中，$\mathrm{Length}(M_i^{+},M_j^{+})={\omega }_1·\left|\right|C_i^{+}-C_j^{+}\left|\right|+(1-{\omega }_1)·\left|\right|D_i^{+}-D_j^{+}\left|\right|,$ω是层的权值，

ω₁是点的坐标信息或距离信息的权值。

本实施例采用一种基于Hausdorff距离的匹配器匹配用户提交的三维模型A的特征描述符与特征数据库中的三维模型B的特征的步骤为：

第一步，根据中轴点的类型对其赋予不同的权值，如式(3)。若为临界点，权值为ω₀；若为候选临界点，权值为1-ω₀，亦为第1级加权。这样，A和B各自描述为加权的中轴点集分层螺旋信息A＝[a₀，...，a_m-1]^-1和B＝[b₀，...，b_n-1]^-1，其中，a_u和b_v是中轴点加权信息，u∈[1，m]，v∈[1，n]。

第二步，分别计算A和B的所有中轴点加权信息中C_i⁺和D_i⁺的加权Euclidean距离，权值ω₁调节坐标加权信息的Euclidean距离和距离加权信息的Euclidean距离所占的比重，亦为第2级加权。另外，根据式(4)计算两个中轴点的距离，判断两个中轴点是否同层，用对应的权值ω或1-ω加权这两个中轴点加权信息的距离，即第3级加权。A和B的任意两个中轴点加权信息a_u和b_v之间的距离为d(a_u，b_v)。

第三步，m可能不等于n，本实施例用Hausdorff距离度量模型A和模型B的差异值H(A，B)：

H(A，B)＝max{h(A，B)，h(B，A)}

其中，$h(A,B)=\underset{0\le u<m}{\max }\underset{o\le v<n}{\min }d(a_u,b_v).$

综上所述，将用户提交的查询模型和模型库中所有模型的特征按照上述匹配步骤计算，得出所有的特征匹配距离，然后将这些距离排序后按照相似度大小生成检索结果。

以下对本实施例提供的中轴点集分层螺旋信息相似性度量方法对三维模型的变换和干扰的健壮性进行相应测试。首先选择5个具有代表性的三维模型，并对所述模型进行五种变换。在此基础上，再建立了一个有30个模型的数据库，它包含每个模型的6个不同版本，其中包括1个原型及5个变换。所做变换如下：

·缩放：X、Y、Z每一维放大10倍；

·各相异性缩放：Y维放大5％，Z维放大10％；

·旋转：分别绕X维、Y维和Z维旋转45度；

·剪切：分别将Y维和Z维放大X维的5％和10％；

·插入：随机插入5％的多边形复件。

在所述数据库上，对本实施例方法区分不同类的能力进行测试，具体是计算30个模型描述符的差异性度量，结果证明了本实施例的方法具有很好的鉴别力，对刚体具有平移、旋转和缩放不变性。

此后再测试具有不同数量的多边形网格的相似三维物体的差异性。本实施例用简化封套(Simplification Envelopes)软件生成了Stanford Bunny的8个版本，其面片数量被剖分为600到70000不等。提取每个版本的中轴点集并计算它们之间的差异性度量值，实验结果可以明显地观察到每个化简模型版本得到的中轴点集大都非常相似，进一步从量化的数值来看，每个版本的平均差异性度量值都非常接近，说明它们之间的距离几乎相同。该部分实验证实了本实施例方法对改变网格、模型化简或模型退化具有良好的鲁棒性。

上述两个测试表明本实施例方法能够保证三维模型的变换不变性和健壮性。

接下来再测试本实施例的匹配方法能否在一个更大、更多样的数据库中表现出较好的效果。先从互联网上下载430个不同种类的模型，它们被分为35个类。在表2中列出了部分类的名称和所包含的模型数量。

该数据库具有一些显著的特点。首先，每个类包含任意数量的三维模型，即为随机的来自互联网；第二，类之间的相似性有很大差异；第三，每个类中模型的相似性也有差异。

为了对比测试本实施例的三维模型检索方法(EFS)与基于体素化和球面调和的三维模型检索方法(VOXSH)(Funkhouser，T.，Min，P.，Kazhdan，M.，Chen，J.，Halderman，A.，Dobkin，D.，Jacobs，D.：A searchengine for 3D models.ACM Transactions on Graphics 22(2003)83-105)对模型分类和检索的效果和效率，本实施例进行了分类和检索实验：比较数据库中每个模型的描述符，并根据归类与查询模型最相近的所有模型的原则进行分类。表1列出了反映总体分类性能的各项实验结果。另外，本实施例还在每个类上做了性能测试，随机抽取16个基本类，将这些基本类的分类实验结果在表2中列出。同时，本实施例通过生成部分典型模型的检索结果和全部数据库的查准-查全图来做测试。如图2和图3所示，方框曲线表示本实施例的EFS方法的查准-查全曲线，三角形曲线表示VOXSH方法的查准-查全曲线，图2是EFS、VOXSH的总体查准-查全曲线比较图，图3是EFS、VOXSH在部分类上的查准-查全曲线比较图。

表1 EFS和VOXSH的总体性能比较

表2 EFS和VOXSH在部分类上的性能比较

首先在数据库中检索到最相似的9个结果，所有的结果在大约17秒的时间返回。在该实验中，构造查询模型的特征描述符占用了绝大部分的检索时间，另外描述符的平均比较时间(2.38毫秒)比VOXSH方法的平均比较时间(4.06毫秒)快近1倍，如表1中匹配时间列所示，本实施例提出的EFS方法在各个类上的平均相似性度量时间绝大多数都比VOXSH方法更快。如此一来，当用户检索那些描述符已存在于特征库的模型时，速度将得到显著的加快(如从检索结果中进行二次检索)。

然后再对比VOXSH方法和本实施例提出的EFS方法在测试数据库中的分类性能指标、总体查准-查全曲线图和在部分类上的查准-查全曲线图。如表1所示，用于对比方法性能的折衷累积增益(DCG)指标表明，本实施例提出的EFS方法比VOXSH方法高出5.7个百分点，而且其余的各项指标都要优于VOXSH方法，其中最近邻(NearestNeighbor)高出了11个百分点。如图2所示，从总体查准-查全曲线比较图可以看出，代表本实施例EFS方法的方框曲线位于代表VOXSH方法的三角形曲线的上方。上述比较说明，本实施例方法的分类和检索效果优于VOXSH方法。其次，对各个类的分类和检索性能较好。为了分析方法对不同种类模型的适应性，表2列出了本实施例EFS方法和VOXSH方法在部分类上的性能统计，数据显示EFS方法各个类上的性能指标都明显优于VOXSH方法。另外，不同的方法对于不同类别的检索效果也有所不同，从图3可以看出，本实施例的EFS方法对于绝大多数类别的查准-查全率要高于VOXSH方法。从上述实验结果可以看出，本实施例提出的方法对于分类和检索该测试库中的三维模型，性能优于VOXSH方法。

以下再测试多级加权系数的影响，对两个模型采用基于Hausdorff距离的多级加权相似性匹配方法计算分层螺旋信息的相似度时，本实施例定义了三种权值，ω₀、ω₁和ω分别代表加权中轴点类型、中轴点的位置信息或距离信息以及是否同层。在此测试中，通过设定不同的权值进行了多次测试，测试实验结果表明，本发明方法的检索性能均优于VOXSH方法，并可以通过调整权值，满足对查准率或查全率的不同需要。

综上所述，本发明通过采用中轴点集分层螺旋信息作为三维形状的特征，并且提出一种基于Hausdorff距离的多级加权相似性匹配方法度量三维模型的相似性。本发明的关键是提供了一种框架，在该框架中，三维模型被转换为自然参数的函数，从而通过本发明提供的度量方法得到健壮高效和较好的三维模型相似性度量和检索结果。