阶层式三维形状环特征提取方法

左向梅，贾丽姣，韩鹏程

(1.中国飞行试验研究院试验机设计改装研究部，西安710089; 2.西北工业大学航空学院，西安710072)

(*通信作者电子邮箱88.zxm@163.com)

0 引言

随着信息技术的快速发展，三维模型因为其丰富的形状、颜色、纹理等信息，在多媒体、图形学、虚拟现实、设计、娱乐、工业制造等领域得到了越来越广泛的应用。大量的三维模型数据库可以从网络上轻松获得。除此之外，随着RGB-D设备的出现，用户可以更加方便快捷地获得相关三维模型数据，这也大大增加了三维模型的数量。因此，为了有效地对现有三维模型进行管理和再利用，需要高效准确的图形检索、分类的方法来处理这些海量三维数据。

对于三维图形的分类和检索，大部分的解决方案都是设计出优秀的具有高分类精度的三维形状特征。三维形状特征很好地描述了三维模型的相关属性包括颜色、纹理、形状特性等，用于有效地区分或者归类不同的三维模型。三维模型特征分为全局和局部特征，全局特征主要是通过对三维模型的整体形状进行分析研究，获取其形状表达;局部特征将着眼于三维模型的局部形状，利用局部网格来获取显著的局部特征。局部特征提取和检索是近些年来的研究热点，目前大量用于描述三维模型的局部特征被提出，例如:平均测地线距离(Average Geodesic Distance，AGD)［1］、尺度不变的热核描述子 (Scale-Invariant Heat Kernel Signature，SI-HKS)［2］、形状直径函数 (Shape Diameter Function，SDF)［3］等，尽管这些特征在三维模型检索匹配［4］、模型对齐［5］、对称性检测［6］中取得较好的应用效果，但是实际应用中还有待提升。主要原因有两点:第一，这些特征都是基于专业的设计人员通过复杂的数学模型构建出来的，需要相关领域很强的先验知识。例如尺度不变的热核描述子是利用Laplace-Beltrami算子在三维形状表面上通过热扩散方程导出的，对于非专业领域的特征设计人员很难利用相关特性设计出优秀的特征描述子。第二，人工设计的特征大部分只能抽象三维模型上某一方面的属性，例如平均测地线距离(AGD)只收集三维形状上顶点与顶点的距离，形状直径函数(SDF)只收集三维形状上不同部分的直径信息，而三维形状含有复杂的三维拓扑结构以及丰富的几何信息，很多信息在特征提取完之后严重丢失，从而影响了图形的检索效率。为了降低对设计人员的技术门槛需求，更充足地收集图形信息来提高特征表达能力，本文提出了一种融合三维形状拓扑连接信息的阶层式特征提取框架，让其自动学习提取三维模型的相关属性，其主要思想是以三维模型底层特征为基础，结合三维模型的拓扑结构以及机器学习方法进一步提取模型的中层特征以及高层特征。

1 阶层式环特征提取方法

本文方法主要分为三个步骤:首先，输入三维模型数据，根据平均测地线距离、尺度不变的热核描述符、形状直径函数等基础描述符构建三维形状的底层描述符。其次，结合三维形状的结构化信息建立等测地线的环区域模型来编码特征点的邻近区域，从而得到该点的中层特征表达。最后，结合稀疏编码的方法进一步探索各特征维度之间的信息，以及解决中层特征表达存在的相关问题，引入平移不变的编码方式和傅里叶变换操作，进一步求得三维模型的高层特征:平移不变的环特征(Shift Invariant Ring Feature，SI-RF)。该特征具有较强的分辨力和鲁棒性。本文方法流程如图1所示。

图1 提取平移不变的环特征的流程Fig.1 Flow chart of extracting shift invariant ring feature

1.1 图形底层特征提取

本文的研究中，主要将平均测地线距离(AGD)、尺度不变的热核描述子(SI-HKS)、形状直径函数(SDF)这些典型的局部特征进行组合，得到三维模型的底层特征，并以此为基础产生三维模型的中层特征。

平均测地线距离(AGD)被Hilaga等［1］提出用于三维模型的图形匹配。用g(xi，xj)描述在一个三维形状X上两顶点xi和xj之间的测地线距离，该值能保留有效的三维模型属性，在图形的检索和分类中应用广泛。该特征有以下三个特点:第一，该值描述了任意一点到模型上其他所有点的距离。第二，它的局部极大值与包含在模型中的几何特征的描述相一致。第三，它是尺度不变的，并且可以用来从区分不同的形状。

热核描述符(Heat Kernel Signature，HKS)是利用Laplace-Beltrami算子在三维形状表面上通过热扩散方程导出的，具有丰富的局部几何信息和多尺度特征。然而，HKS的局限性在于它对形状的尺度敏感，例如当形状变大时，HKS所描述的区域在同一时间范围内变小。为了解决这个问题，Bronstein等［2］提出了尺度不变的热核描述子(SI-HKS)，在图形检索匹配中取得了非常好的应用效果。

形状直径函数(SDF)是基于体积的标量函数，用来测量三维形状上不同部分的直径。SDF值是通过发射30条光线在30度的小圆锥内与相反的边界侧相交，并平均加权这些射线长度计算得到的。该值在同一模型的同一部分相邻区域保持相似，并且能够应对三维形状的铰接式变形。

考虑到这些特征既包含了三维形状的本质属性［7］也包含了三维形状的基本几何属性，本文将尺度不变的热核描述子(SIHKS)前6个频域分量和平均测地线距离(AGD)以及形状直径函数(SDF)拼接在一起形成三维形状的底层特征:

式(1)所求得的三维形状的底层特征维度fm=8。对于SI-HKS，时间尺度设为［1，20］，时间间隔设置为 0.2，本征函数的数量为100，对数时间基设为α=2。对于AGD描述子的参数n设为1。由于底层特征包含不同的基础三维形状特征，所以每种不同类型的特征模型构建方式不同，因此底层特征的每一个维度的值具有不同的值域和尺度，为了保证每一种基础特征所包含的信息不被忽视和过度重视，所有维度的值根据对应维度的最大最小值被线性归一化到［－1，1］，计算式定义如下:

式中i∈［1，2，…，8］，表示底层特征的每一个维度。

因为该底层三维特征由多个基础三维特征拼接而成，所以包含丰富的三维形状属性，可直接用于三维形状的相关应用。但是该特征在应用中并不能取得非常好的效果，原因有两点:首先，该底层特征由多种基础特征拼接，尽管这种方式尽可能地不丢失三维信息，但是冗余信息过多，对于一般的分类器来说，并不能得到较好的分类结果。其次，三维形状有着丰富而复杂的结构信息，比如坐标、纹理、颜色、拓扑结构信息等，该底层特征中包含的信息缺少显性的空间结构信息。为了进一步提高提取特征的分辨力，本文在该底层特征的基础上，结合特有的三维形状拓扑结构提取三维形状的中层特征。

1.2 图形中层特征提取

对于一个三维形状，仅靠顶点的特征描述值是不能提供足够的有区分度的信息，特别是对低级别描述符;而相邻的顶点及其邻域的拓扑连接属性却包含了更多的信息。因此，提取高区分度的形状特征最直接有效的方法就是编码顶点的局部周围区域。考虑到图形具有丰富的拓扑结构，本文基于图形的底层特征，提出了一种对三维形状局部拓扑连接关系进行建模的中层特征构建方案:基于环的中层特征编码。

1.2.1 三维图形预处理

三维形状通常由成千上万的顶点和拓扑结构组成;但是，任一个三维形状上顶点的特性类似于它的邻域顶点。另外，在构建局部中层特征时使用全部三维形状上的顶点会大大降低计算效率，浪费过多的计算机资源和时间。因此，在此工作中，选取三维网格上的部分点作为特征点用于模型的构建和训练。本文采用最远点采样(Farthest Point Sampling，FPS)［8］的策略对三维网格进行均匀采样。

本文利用最远距离采样的方法对数据库中所有的模型进行统一降采样预处理，得到三维形状顶点子集V={vi∈X，i=1，2，…，Ns}，式中:X为三维网格，Ns为用户设置的期望得到的采样点数。初始采样点v1∈X是随机选取的。图2是最远点采样的示意图:左侧为三维网格图，中间为点云图(顶点数5228)，右侧为最远点采样后的点云图(顶点数2000)。

图2 最远点采样的示意图Fig.2 Schematic diagram of farthest point sampling

1.2.2 基于环的中层特征编码

对三维形状进行局部编码最直接的方式是依据特征点邻域的拓扑连接结构创建该特征点邻域的n个环。然而，由于每个三角网格的边缘具有不同的长度，在该环上的顶点相对于中心特征点具有不同的测量距离。为了克服该缺点，利用基于测地线的方式创建等测地线的环。

1)等测地线环提取。

针对一个三角网格X上的特征点vi，本文通过快速修复方法(Fast Marching Method，FMM)［9］计算该特征点到三角网格上其他顶点之间的测地线距离。然后随着渐渐增加特征点vi到周边邻域的测地线距离d1＜d2＜… ＜dNr计算Nr个不同层次的测地线函数，Nr表示环的数量。由于每个环上的采样点数是不同的，在每个环上使用线性插值来生成相同数目的采样点数Ns，并且使这些采样点在环上等距隔开。每个环上的点具有一致的方向(顺时针或逆时针相同)，形式为Ri=［，…］∈ RNs×3(其中 i表示第几个测地线环，表示该测地线环上的采样点)。局部等测地线环被定义成R=［R1;R2;…;RNr］∈ RNs×Nr×3，该测地线环被用来表示特征点vi的局部区域。这种等测地线环具有两个好处:它们对于三维形状的等距变形很鲁棒，除此之外它们有相同的特征维度，有效地克服了受三维形状复杂多变的拓扑结构影响，导致特征点邻域顶点组成的环不具有相同维度的问题，因此可普遍应用于三维形状检索、对称检测等应用。一些三维模型的等测地线环的示意图如图3所示。在本文中，设置环的采样点数Ns=80，环的个数 Nr=4。

图3 部分三维模型的等测地线环示意图Fig.3 Schematic diagram of isometric geodesic rings of some three-dimensional models

2)三维形状的环特征描述符。

将1.1节计算的顶点底层特征代入到等测地线环上的顶点，形成等测地线环特征F(vi)∈RNs×Nr×fm，形式定义如下:

式中:vi是三角网格上的特征点;Ns是环上点的个数;Nr是环的个数。因为三角网格的顶点具有足够的密度，所以网格上一个面上的点的特征值差别不大。根据这样的事实，线性插值的方法被用来插值邻域顶点的特征值去形成等测地线环特征。用 Fl∈ RNs×Nr表示该中层特征的一个维度，l∈ {1，2，…，fm}是该中层特征的下标索引。

1.3 图形高层特征提取

1.2 节提出的这种编码局部区域信息的特征描述符:基于等测地线环的特征F(vi)，有效地融合了三维形状的结构化信息，大大增强了特征的区分力。但是这种特征依然存在以下问题:1)该特征由多个等测地线环上的点拼接而成，随着环的增加以及环上采样点的增加，该特征的维度将会非常大，信息冗余过多，不能高效地应用;特别是将该高维度的特征应用于分类器，很容易造成分类器失效，此时常常需要对高维度的特征进行降维操作，如使用主成分分析法对特征降维。2)因为本文是用圆环上采样得到的点来表示局部区域，所以没有办法确定环上哪个点是起始点，如图4所示。不同的点作为起始点会得到不同的结果，这显然不利于特征的统一使用。

为了解决以上问题，本文对这种融和局部拓扑连接关系的中层特征作进一步学习，提炼出三维形状的高层特征。

图4 环不同起始点示意图Fig.4 Schematic diagram of different start points on rings

1.3.1 稀疏编码

因为一个特征点的最初底层描述符被封装入一个固定维数的数组，所以关于中层特征表达的词典可以有效地通过稀疏编码方法获知。然而对于不同的特征点，很难统一等测地线环上的起点，这可能会降低基函数的表达能力。为解决这一问题，本文引入平移不变的稀疏编码(Shift-Invariant Sparse Coding，SISC)算法［10］来学习基于等测地线环的中层表达的基。SISC允许每个基函数在不同的测地线环上的不同位置被复制，因此学习的基对输入数据的位置偏移不敏感。SISC是传统稀疏编码的延伸扩展，其中，关于特征分解公式中的传统乘法运算被卷积运算代替，该特征的一个维度分解可以用如式(4)表示:

式中:aj∈Rq×Nr是关于等测地线环中层特征的基，它与中层特征Fl相比有较低的特征维度(q≤Ns)，因为环的个数要比环上采样点的数少得多。基于输入的中层特征Fl和基aj，基的不同圆形偏移量所对应的不同系数表达向量sj∈RNs－q+1。所以最优化问题是根据输入中层特征学习合适的基A={a1，a2，…，aNb} 和系数 sj，优化函数描述为:

式中:‖aj‖≤1，1≤j≤Nb。该目标优化函数是一个联合优化问题，即同时优化基A={a1，a2，…，aNb}和系数sj，并且通常是非凸函数。然而，当其中一个变量被固定，则该问题可以被视作一个凸优化问题。具体地说就是当A被固定，s能够被看作一个凸优化问题得到解决。反之亦然。两个子问题被反复交替并迭代求解，以获得最佳的A={A1，A2，…，Afm}。当目标函数收敛后，稀疏系数s可以通过学习得到的基A和输入的数据Fl得到，并且将其作为特征点的高层特征描述。

1.3.2 平移不变的环特征提取

高层特征是根据一系列不同形状的特征点学习得到的，每个特征维度的表达为sl。在产生等测地线环的过程中，每个环的起始点的方向是统一的;但是对于不同的特征点，它们是不连贯的，这将会导致转动歧义。为了使得该高层三维特征具有本质属性，本文引入傅里叶变换来实现高层特征的旋转不变性、这样可以有效解决等测地线环不同的排列顺序引起的不连贯问题。最后，底层特征f(xi)每个维度对应的三维高层特征可以描述成θl=|f{sl}|，则底层特征所有维度对应的高层平移不变的环特征描述为 θ = ［θ1，θ2，…，θfm］。

2 实验与结果分析

为了验证本文提出的平移不变的环特征(SI-RF)的有效性，以及对产生这种高层特征过程的重要参数进行讨论和说明，本文主要进行了形状对应和形状检索这两类实验。在形状对应实验中，主要采用Water tight dataset、TOSCA dataset和SCAPE dataset等三个数据库［11］，这些数据库含有丰富的三维形状，并且具有形状对应基准可用来计算SI-RF在三维模型上的对应准确率。在三维模型检索实验中，本文主要使用McGill shape benchmark［12］数据集进行验证，该数据集包含457个模型，其中铰链形式的模型含有10个类别，总共255个模型，每个类别有20～30个模型。

2.1 三维模型对应实验

2.1.1 最优参数设置

根据产生SI-RF高层三维特征的过程可以发现等测地线环的半径会影响特征的性能，所以，首先用Water tight dataset数据库模型来进行三维形状对应实验，找出最合适的测地线距离dNr(即圆形区域的最大半径)。本实验中，设置最大等测地线环的半径dNr的范围为三维形状上最大顶点之间距离的1% ～15%。本文采用两种形状对应方法:1)原始对应方法，即在两个三维模型上将最小的特征距离差所在的顶点作为对应点对。2)谱对应方法［13］，在考虑特征距离的基础上加上其他形式的约束，如能量等。所有模型的对应平均准确率用来作为实验的评估基准。随着选择不同大小的测地线距离，对应实验的结果如图5所示。

图5 不同测地线半径下的对应准确率Fig.5 Corresponding accuracy of different geodesic radius

图5 中，横轴代表的是最大等测地线半径dNr占三维模型上顶点之间最长测地线距离的比例;纵轴代表的是所有模型的平均对应准确率。从图5中可以看出，如果比例过小，即区域范围选择得过小，对应准确率较低;比例低于0.08时，对应准确率是呈上升趋势;但是，当比例高于0.08时，准确率呈下降趋势。因此，本文将三维模型上最长测地线距离的0.08倍作为特征点的最大等测地线半径，并将其应用于本文相关的实验。

其次，对应的准确率同样受到基的个数的影响，所以选择合适的基的个数Nb同样至关重要。第二个对应实验，本文分别将基的数目 Nb设置为 20、40、60、80、100、120、140、160，并根据其对应的准确率选择最佳的基个数，同样用两种对应方法进行对比实验，结果如图6所示。从图6中可以看出，随着基的个数增加，对应准确率呈现上升趋势，因为基的个数越多，其表达能力越丰富，所以能够产生有区分力的高层三维形状特征。虽然基个数越多越好，但是会导致计算效率降低，影响产生高层特征的效率。而且从图6中可以看出，当基的个数达到一定值后，其对应准确率增长得较为缓慢。因此，确定基个数为80，并将其用于后续的相关实验。

图6 不同基的个数的对应准确率Fig.6 Correspondence accuracy with different number of bases

2.1.2 对应实验验证

尺度不变的热核描述符(SI-HKS)和平移不变的环特征(SI-RF)在两种对应方法下的检测准确率结果如表1所示。本文选择了具有典型性的三组模型:人、蚂蚁、熊。从表1可以看出，本文提出的SI-RF特征具有更好的区分能力，能够获得更高的对应准确率。

表1 SI-HKS与SI-RF对应的检测准确率 %Tab.1 Corresponding detection accuracy of SI-HKS and SI-RF %

为了进一步验证平移不变的环特征(SI-RF)的性能，本文在TOSCA数据库上进行了对应实验。对于每个模型，通过最远点采样方法对模型进行降采样，设置每个模型采样后的点数为1000。将源物体上的顶点投射到目标物体上，在该实验中定义基准对应点到通过算法匹配得到的对应点之间的测地线距离为测地线误差，因为有些特征点在三维形状上很接近，特征具有极大的相似性，很难作出有效区分，所以，只要通过算法匹配得到的对应点与基准对应点之间的测地线范围小于一定值，即可认为该点对匹配成功。针对TOSCA数据库，本文得出不同测地线误差范围情况下模型对应实验的准确率如图7所示。

图7 SI-HKS与SI-RF在不同测地线误差范围下的匹配正确率Fig.7 Matching accuracy of SI-HKS and SI-RF under different geodesic error ranges

从图7中可以看出，SI-RF比SI-HKS具有更高的匹配正确率，当可以允许的测地线误差距离设置为三维形状上顶点之间最大测地线距离的0.15时，SI-RF可以达到90%的准确率，而SI-HKS只有64.5%。

2.2 三维模型检索实验

除了模型对应实验以外，本文进行模型检索实验来进一步验证该三维高层特征(SI-RF)能否适用于图形的相似性检测。借鉴Shape Google的思想［14］在Mcgill数据库上进行验证。首先，利用最远点采样的方法对数据库中每个模型进行降采样预处理，每个模型的采样点设置为1500。然后根据底层特征构建三维形状的中层特征:基于等测地线环的局部区域编码。接着利用稀疏编码进一步抽象提取每个特征点对应的高层特征:平移不变的环特征(SI-RF)。因为在模型检索实验中需要用模型的全局特征进行描述，借鉴Shape Google的思想将平移不变的环特征编码产生三维形状的全局特征(Global SI-RF)。对于SI-HKS，本文利用同样的思路产生相应的全局描述符(Global SI-HKS)。

本文采用6个标准评估指标［15］来评价提出的高层三维特征在模型检索应用中的表现，它们分别是:精密召回曲线(precision-recall curve)、最近邻(Nearest Neighbor，NN)、一阶(First Tier，FT)、二阶(Second Tier，ST)、E 测量(E-measure，E)和贴现累计收益(Discounted Cumulative Gain，DCG)。本文除了将全局SI-RF跟全局SI-HKS进行对比，还与其他先进的特征描述符包括形状谐波描述符(Shape Harmonic Descriptor，SHD)［16］、光 场 描 述 符 (Light-Field Descriptor，LFD)、关联矩阵特征值描述符(EigenValue Descriptor of affinity matric，EVD)［17］和测地线距离 －属性关系图(Earth Movers Distance-Attributed Relation Graph ，EMD-ARG)［18］进行比较。各特征描述符的检索精确率如图8所示。

图8 多种特征描述符检索精确率对比Fig.8 Recall-precision curve comparison of multiple feature descriptors

从图8中可以看出，本文设计的三维高层特征:平移不变的环特征(SI-RF)比其他特征取得了更高的检索准确率。除此之外，EMD-ARG、SI-HKS和SI-RF在不同评估指标下的值如表2所示。从表2中可以看出，本文提出的SI-RF各项评估指标都比另外两种特征描述符取得较高的数值，特别是在DCG指标上比SI-HKS提高了7.2个百分点，这充分表明了该设计框架的有效性，通过稀疏编码结合中层结构化编码能够进一步提高底层特征的区分能力。

表2 多种特征描述符关于标准检索评估指标的对比 %Tab.2 Comparison of multiple feature descriptors for standard retrieval and evaluation indicators %

3 结语

一个良好的特征应该是阶层式的，除了底层基础属性如纹理、角度、方向等，还应该具有三维形状拓扑结构信息，基于该思想本文提出了一种阶层式的三维形状环特征提取框架，其基本思路是从构建图形的底层特征开始，逐步根据三维形状局部拓扑连接关系构建三维形状的中层特征以及高层特征。首先，根据底层基本特征和三维形状的表面物理结构构建等测地线环，并用其作为特征点的中层表达;然后，利用平移不变的稀疏编码(SISC)进一步提取基于环的高层三维特征。该设计框架不仅将稀疏编码技术巧妙地应用于三维形状分析，还通过构建中层结构化特征的方法增强了稀疏编码的应用性能。本文将该特征应用于三维形状对应、检索等实验，相比其他相关的特征取得更高的检索准确率和更好的匹配效果。

虽然本文提出的三维形状局部特征具有更好的性能，但是仍然存在一些需改进的地方:首先，使用等测地线环来表示特征点的局部区域，这种方法的计算效率低。其次，在提取等测地线环的时候需要将三角网格展开，但是因为三角网格的复杂性，存在部分网格不能很好地被展开的问题。因此，在以后的研究中，我们将研究更好的局部区域提取技术来改善本文方法。