基于特征融合的文物碎片模型检索

赵夫群，戴 翀，耿国华*

(1. 西安财经大学信息学院 西安 710100；2. 西北大学信息科学与技术学院 西安 710127)

随着三维激光扫描技术的出现，物体的三维模型展现和处理技术也得到了快速发展。这是由于三维模型具有较强的特征展现力，并且可以弥补其他多媒体资源在信息存储、共享和展示等方面的不足。模型检索是三维模型处理技术的一个重要研究内容，是指从大量三维模型中检索出与某一特定模型相似的所有模型的过程。目前，三维模型检索已经在数字图像处理、文物虚拟复原以及计算机辅助设计等领域[1-4]得到了较为广泛的应用。

根据提取对象的差异，通常可以将三维模型检索方法分为两种类型，即基于文本的检索方法和基于内容的检索方法。基于文本的检索方法需要人为地给三维模型添加相应的关键字，具有较强的主观性；而基于内容的检索方法则是通过提取三维模型的显著几何特征进行检索，可以有效减少人工干预，是目前使用较多的模型检索方法。近年来，国内外学者提出了很多基于内容的三维模型检索算法。文献[5]提出一种基于联合形状分布的三维模型检索算法，通过主面分析和群融合提高了模型检索的精度；文献[6]提出一种多模态视图的三维模型检索算法，通过构造多模态特征空间中图的超边实现模型检索；文献[7]提出一种基于多模态图学习的三维模型检索算法，通过度量模型的多个视图间的相似性实现检索；文献[8]提出一种基于非监督特征学习的三维模型检索算法，有效提高了模型检索的效率；文献[9]提出一种基于梯度描述子优化的支持三维物体检索的有效方法，该方法以稀疏编码为基础，通过实验验证了该方法的有效性。这些三维模型检索算法均具有较高的检索效率，但仍然存在局部特征有效性低、模型整体信息表达差以及检索效率低等缺点，因此不适合用于复杂陶质文物类碎片模型的检索。

兵马俑是一种较为复杂的文物模型，在出土挖掘过程中破损严重，碎片数量较多，并且存在碎片缺失、形状各异以及特征模糊等问题。在计算机辅助兵马俑虚拟复原时，直接将大量碎片进行拼接复原是一项NP 难题，因此有必要设计高效的碎片智能检索方法，将碎片按照一定规则划分为若干子集，降低碎片匹配时的穷举规模，为匹配拼接工作提供指导约束，提高虚拟修复效率。针对兵马俑碎片的三维模型复杂引起的检索困难问题，提出一种基于特征融合的碎片点云数据模型的快速检索算法。该算法通过融合碎片点云的曲率和法向夹角特征，并通过迭代对融合特征进行匹配来实现模型检索。算法不仅可以准确地描述碎片的表面几何特征，而且可以避免算法陷入局部极值，从而提高碎片检索的精度和速度。

1 融合特征计算

1.1 曲率特征

曲率可以有效反映点云表面的凹凸程度，越是特征明显的点云区域，其曲率也就越大，而特征不够明显的区域，其曲率也就越小。这里利用k-D tree(k-Dimension tree)算法[10]构造点云上点及其邻域点的切平面来计算曲率。

对于点云模型D={di}，i=1,2,···,ND， ND表示点云 D中所包含的点数，首先采用k-D tree 算法计算点 di的k近邻点。该算法需要查找在点 di周围的固定半径为r内的k个近邻点，通过判断两点之间的欧氏距离即可实现，具有较高的处理效率。这里，k 不是一个固定的整数值，需要在实验中设置k的上限，而r是一个固定半径，也需要在实验中给出。

k-D tree 邻域点查询算法的步骤如下：

1)确定点云 D的划分维度和划分点。通常从方差最大的维度开始划分，可确保良好的切分效果和平衡性。根据该维度上的点的数值进行排序，并取中值点作为点云的划分点。

2)确定点云 D的左、右子空间。分割超平面过划分点可以将点云 D划分为两部分，数值小于中值点的划为左子空间，剩下的一部分为右子空间。

3)对于左、右子空间，分别重复步骤1)和步骤2)，以相同的方式递归地进行分割，直到分割的子空间内点的个数满足条件为止，由此构建好k-D tree。

4)从k-D tree 的根结点开始，按照查询点与各个结点的比较结果向下访问k-D tree，直至达到叶子结点。计算查询点与叶子结点上保存的数据之间的距离，若距离小于r，则记录该点的索引和距离。

5)回溯搜索路径，并判断搜索路径上结点的其他子节点空间中是否有与查询点距离小于r的点。若有，则跳到该子节点空间中去搜索，执行步骤4)中相同的查找过程；否则，继续回溯过程直到搜索路径为空。

通过上述步骤即可查询出点云 D上任意一点di的k近邻点。假设x轴和y轴是点云 D上点 di及其k近邻点拟合切平面上的两个正交向量， z轴是点云D的法矢，那么x、 y和z轴就构成了笛卡尔坐标系。可以定义点 di的切平面S(x,y)为：

在式(1)中，存在一组数值a、 b、 c、 d、 e使其成立，采用线性方程组可表示为：

1.2 法向夹角

法向夹角是指数据点法线方向与其邻近点法线方向的夹角，可用于描述点云表面的弯曲程度[11]。对于点云 D上 任意一点 di，通过查询 di的k近邻点可计算其协方差矩阵 Ci为：

计算协方差矩阵 Ci的特征值，假设其特征值为λ1≤λ2≤λ3，那么点 di的法线就是协方差矩阵 Ci的最小特征值对应的特征向量的方向。假设特征值λ1≤λ2≤λ3对应的特征向量为分别为e1,e2,e3，那么特征值 λ1就表示点云表面沿法线方向的变化量，点di的法线方向就是ni=e1。

定义点 di的法线夹角参数ωa(di)为：

法线夹角参数ωa(di)反映了点 di的所有k近邻点对点云表面弯曲程度的影响。ωa(di)越大，点 di及其k近邻点的表面弯曲程度就越大，点 di的邻域成为特征区域的可能性就越大；反之，ωa(di)越小，点 di的k近邻点的表面就越光滑，点 di的邻域成为特征 区域的可能性就越小。

1.3 特征融合

基于以上对曲率和法向夹角参数的计算，定义点 di的融合特征参数ω(di)为：

式中， α和β表示曲率系数，均为正数。

由式(9)可见，主曲率Ri1、Ri2、法线夹角ωa(di)与融合特征参数ω(di)均成正比。 Ri1、 Ri2和ωa(di)越大，点 di成为特征点的几率就越高；反之， Ri1、Ri2和ωa(di)越小，点 di成为特征点的几率就越低。

2 基于融合特征匹配的检索

基于以上计算的融合特征参数ω(di)，通过将大量三维模型与一个已知模型进行融合特征匹配即可实现模型检索。假设已知点云模型为M={mj|mj∈R3,i=1,2,···,NM}，某一个待检索的目标点云模型为D={di|di∈R3,i=1,2,···,ND}，采用融合特征匹配算法将 M 与 D进行匹配检索的具体步骤描述如下：

指纹是指尖表面上交替分布的脊线和谷线图案。指纹图像有着许多不同于其它图像的特点，其纹理性和方向性比较强，而指纹图像的方向场代表了指纹的这种固有性质。通过原始指纹图像的纹理信息，求出每一个像素点的切线方向，就可以描绘出整幅指纹图像的方向场图，而方向场图又为后续指纹图像的滤波、特征提取奠定了基础，故该方向场估算十分重要[12-13]。

1)对于参考点云 M和目标点云 D，利用k-D tree 算法查询其上任意一点di∈D和 mj∈M的k近邻点，并利用式(3)～式(9)计算点的主曲率、法向夹角和融合特征参数；

式中， s 表示迭代次数，初始设置为s=0。

3)判断式(11)和式(12)，若成立，那么点 di即为点 mj的匹配点：

式中， Ri1和 Ri2表示邻域点的两个主曲率； ωα表示邻域点的法向夹角；τcurvature和τnormal分别表示曲率和法向夹角的阈值。

4)令s=s+1，利用式(13)计算旋转矩阵 Rs、平移矢量 ts和Ds=RsD+ts。

6)重复步骤4)到步骤5)，直到匹配误差RMSs小于预设阈值ε或达到最大迭代次数stepmax为止；

7)判断，若RMSs小于给定阈值ε，那么目标点云 D就可以和参考点云 M正确匹配，点云 D就是检索到的点云 M的相似模型。否则，点云 D就不是点云 M的相似模型，由此实现了模型检索。

在该检索算法中，寻找两个三维模型的匹配点时，不仅仅利用式(10)计算相应点的距离来实现，而且加入了约束条件式(11)和式(12)，通过融合曲率和法线夹角特征来进一步刻画模型上点的邻域曲面的弯曲程度，可以更加精确地描述模型特征，降低相关点的误匹配率，从而避免陷入局部极值，提高模型检索的精度。

3 实验结果与分析

实验采用西北大学可视化技术研究所提供的兵马俑碎片验证所提检索算法。以50 个已经拼合的兵俑为模板，共包含1 036 个碎片。由于碎片数量较大，这里仅展示部分碎片，如图1 所示，碎片均采用三维点云数据模型表示。按照俑的身体部位，将碎片按照5 种类别进行检索，即头部碎片(C1类)、躯干碎片(C2 类)、裙摆碎片(C3 类)、上肢碎片(C4 类)和下肢碎片(C5 类)。

图1 部分碎片

采用所提检索算法，以图2 所示的头部碎片、躯干碎片、裙摆碎片、上肢碎片和下肢碎片为检索的参考模型，首先计算碎片点云模型的曲率和法向夹角，并将其加权融合，然后通过对融合特征的匹配来实现碎片检索。所提算法的碎片检索结果如图3 所示。

图2 检索参考模型

通过对大量兵马俑碎片的点云数据模型进行检索分析，结果发现曲率系数 α 和 β对特征参数的计算结果有较大影响。同时由于邻域点的数量跟点云密度及其分布的均匀性有很大关系，因此当点云数据模型的密度较大时， α 和 β的取值较小，当点云数据模型的密度较小时， α和 β的取值较大。

通过实验验证，通常建议 α和 β的取值范围均在10～30 之间。本实验中， α和 β的取值均为20。

图3 碎片检索结果

为了验证所提检索算法的精度，对1 036 个兵马俑碎片再分别采用文献[12]算法、文献[13]算法，以及本文算法中无主曲率和融合特征参数约束的算法进行检索，检索结果的准确率如表1 所示。从表1 的检索结果可见，所提检索算法的准确率最高，检索效果最佳。

这是由于文献[12]算法是一种基于多层深度网络的三维模型检索算法，通过构建局部信息和全局信息的特征学习模型实现模型检索。虽然该算法在一定程度上提高了检索效率，但是采用的特征表示方法对兵马俑碎片模型的整体信息表达相对较差，因此检索的准确率依旧不够高。文献[13]算法是一种基于模糊C 均值和卷积神经网络的模型检索算法，该方法将直觉模糊集引入到模型特征中以实现碎片特征分离，并根据分离特征实现模型检索。但是该算法需要人为设置检索参数，检索时间复杂度较高，对交叉特征的检索效果较差，从而影响了检索的准确率。无约束算法是在所提算法中去除了主曲率和融合特征参数约束，通过直接计算模型特征点的距离实现相似特征的匹配，从而进行模型检索，因此准确率不高。而所提算法融合了兵马俑碎片的两个主曲率和法向夹角特征，并通过迭代地对融合特征进行匹配来实现模型检索，不仅可以准确地描述碎片的几何特征，而且可以避免算法陷入局部极值，从而提高检索精度和速度。由此可见，本文的基于融合特征的三维模型检索算法是一种有效的高精度兵马俑碎片检索方法。

表1 4 种检索算法的准确率%

4 结 束 语

在基于特征的三维模型检索方法中，选择合适的特征并对其进行表示和融合是模型检索要解决的关键问题。提出的三维模型检索算法融合了曲率和法向夹角特征，并通过对融合特征的相似性匹配实现了三维模型的精确检索。通过将该算法应用到兵马俑碎片检索中，可以实现碎片分类，降低后期碎片匹配的穷举规模，为碎片拼接提供指导和约束，提高兵马俑虚拟修复技术在文物数字化保护中的应用能力。但是，本文算法采用的是加权求和的特征融合方式，通用性不够高，因此后期研究中要考虑将视觉显著性应用到模型特征提取中，将多模态应用于特征融合中，进一步提高模型检索的精度。