赵夫群, 周明全



一种有效的秦俑碎块匹配算法①

赵夫群1,2, 周明全2

1(咸阳师范学院教育科学学院, 咸阳 712000)2(西北大学信息科学与技术学院, 西安 710127)

针对秦俑碎块的三维网格数据模型, 提出了一种基于特征轮廓线的碎块断裂面匹配算法. 首先, 对数据模型进行纹理贴图、去噪、补洞、简化数据模型等预处理, 然后提取碎块的主轮廓线和次轮廓线, 进而提取出碎块的特征轮廓线, 最后根据角点对特征轮廓线进行分段, 并采用计算最长公共子序列的方法对分段曲线进行匹配, 完成特征轮廓线的匹配, 从而实现碎块断裂面的匹配. 实验结果表明, 该算法是一种有效的、精确的秦俑碎块匹配方法.

秦俑; 碎块匹配; 特征轮廓线; 角点; 最长公共子序列; 曲率; 挠率

近年来, 图像配准技术发展迅速, 应用广泛[1-3], 三维破碎刚体的匹配拼接也成为了一个研究热点. 破碎刚体的匹配方法主要分为两大类: 基于轮廓线的匹配方法和基于断裂面的匹配方法. 对于薄壁类的文物碎片, 如陶器碎片、壁画等, 以轮廓线为特征的碎片匹配是目前运用的主要方法[4,5]. 而对于厚度不可忽略的碎块, 既可以根据轮廓曲线进行匹配, 也可以根据断裂面进行匹配. 若以轮廓线为特征进行匹配, 那断裂面轮廓线的提取就是其中关键的一步, 提取结果的好坏往往对匹配的结果影响特别大. 目前针对基于轮廓线的碎块匹配, 很多研究者提出了一些匹配算法[6-9], 这些算法都是运用断裂面面上的某些特征直接提取断裂面的轮廓曲线, 因而在匹配精度上还存在一定的不足, 而本文则是采用基于特征轮廓线的方法来进行秦俑碎块断裂面的匹配[10]. 这里的特征轮廓线与一般提到的轮廓线有所不同, 是指模型断裂面和外表面的交线, 是由主轮廓线和次轮廓线的片段共同形成的. 主轮廓线是指模型的边界线, 它是构成特征轮廓线的主要部分, 次轮廓线是指碎块的外表面与断裂面的交线. 由于秦俑碎块存在一定程度的磨损和损坏, 特征轮廓线能更好地描述碎块的轮廓特征.

由于通过三维激光扫描仪采集到的秦俑碎块的三角网格模型不仅数据量非常大, 含有大量噪声, 而且还存在孔洞, 因此不能直接用于碎块的匹配拼接, 需要进行预处理. 本文主要进行了以下几个方面的预处理: 采用基于OpenGL的新式OBJ文件纹理贴图方法进行了纹理贴图处理[11], 将纹理图像映射到数据模型的对应位置上, 使得数字化后的三维模型看起来更加逼真. 在确保数据模型的重要特征不会丢失的情况下, 采用三边滤波去噪算法对数据模型进行去噪处理[12]. 采用区域生长算法对三角网格模型的孔洞进行修补[13], 使得数据模型更加完整. 最后, 采用基于特征保持和三角形优化的方法对三角网格模型进行简化[14], 在保持原有模型的几何形状不变的基础上, 大幅地减少了模型中三角面片的数量, 有效地提高了算法的执行效率.

数据预处理完成后, 就可以进行碎块的匹配操作了. 本文首先采用边界提取算法提取碎块的主轮廓线, 再提取断裂面的次轮廓线, 并由主轮廓线和次轮廓线的片段共同形成特征轮廓线. 然后, 采用四次B样条曲线将特征轮廓线拟合成光滑的空间曲线, 并根据角点对该曲线进行分段, 提取分段曲线上顶点的曲率和挠率, 组成特征字符串. 最后, 通过特征字符串匹配的方式完成特征轮廓曲线的匹配, 从而实现断裂面的匹配.

1 提取特征轮廓线

本文通过改进文献[7]提出的特征轮廓线提取方法来提取秦俑碎块的特征轮廓线. 首先提取主轮廓线, 然后提取次轮廓线, 再由主轮廓线和次轮廓线的片段共同形成特征轮廓线. 碎块主轮廓线、次轮廓线和特征轮廓线的示意图如图1所示.

(a)主轮廓线 (b)次轮廓线 (c)特征轮廓线

1.1 提取主轮廓线

主轮廓线的提取采用基于边的重数判断的模型边界提取算法, 即根据边的重数的值判断该边是否为边界边. 设是三维模型的边集,表示模型中顶点的个数,表示模型中边的条数, 则边集定义为:

主轮廓线的具体提取步骤如下:

①设置两个堆栈Stack1和Stack2, 用于存储主轮廓线的点集, 初始将中的边都标记为False.

③取堆栈Stack1和Stack2的栈顶元素为当前两个顶点, 分别按照相反方向搜索模型的边集, 在当前点的邻接点集中搜索与其构成的边的重数为1的点, 且这条边标记为false, 并将该点加入当前堆栈.

④判断堆栈Stack1和Stack2的栈顶元素是否相同, 若相同则转步骤⑤, 表示两个搜索方向搜索的点已汇合, 构成了封闭的主轮廓线, 否则转步骤③, 继续搜索.

⑤将堆栈Stack1和Stack2中所有的顶点出栈, 由此构成了该三角网格模型的主轮廓线点集.

1.2提取次轮廓线

因为次轮廓线是碎块外表面和断裂面的交线, 所以构成次轮廓线的点位于碎片断裂面的边缘, 因此识别碎块的断裂面是提取次轮廓线的关键一步. 首先对三维网格模型进行曲面分割, 然后根据曲面特征区分出断裂面和原始面, 再对识别出的断裂面提取次轮廓线点集.

1.2.1曲面分割

秦俑碎块的曲面分割是一个将碎块的外表面以棱边为界限分割成多张曲面的过程. 通常断裂面与原始面的交界处存在突变, 在几何上表现为棱边两侧位于不同曲面的两个相邻三角面片的法矢夹角比较大. 本文采用区域生长算法[15]来完成曲面的分割, 具体步骤如下:

① 判断相邻三角面片法矢的夹角是否大于给定阈值, 若大于给定阈值则这两个三角面片被分割在两个不同的曲面上, 若小于给定阈值则这两个三角片属于同一曲面. 重复该过程, 直到所有三角面 片分割完成为止.

② 逐一检查分割曲面, 若曲面特别小, 则将其合并到相邻的曲面中; 若曲面较大, 则要判断该曲面与其相邻曲面的平均法矢夹角, 若小于给定阈值则进行合并, 否则不合并.

1.2.2提取断裂面

一般情况下, 断裂面和原始面的显著区别在于断裂面较原始面更为粗糙, 在几何特征的表现上就是断裂面上顶点的法向量变化较大, 因此可以根据断裂面上所有顶点的法向量的变化情况来区分断裂面和原始面.

1.2.3提取次轮廓线

次轮廓线位于断裂面的边界, 是特征值变化的极值点. 在曲面分割阶段提取的断裂面的边界可能会不完整, 所以要首先进行断裂面的二级邻接生长, 然后再对生长后的断裂面提取特征极值点, 进而提取次轮廓线.

②采用步骤①的方法, 对一阶邻接生长的曲面再进行一次邻接曲面生长, 就得到了二级邻接生长曲面.

1.3 提取特征轮廓线

在提取了秦俑碎块的三角网格模型的主轮廓线和次轮廓线后, 就可以提取模型的特征轮廓线了. 这里的特征轮廓线是指模型断裂面和外表面的交线, 是由主轮廓线的片段和次轮廓线的片段共同形成的. 特征轮廓线的具体提取方法是: 对于存在断裂面的部分只选取相应的次轮廓线, 否则就选取主轮廓线, 这些选取的线段就构成了三角网格曲面模型的最终特征轮廓线. 但是, 这里提取到的特征轮廓线是空间离散曲线, 需要采用四次B样条曲线将其拟合成光滑的空间曲线. B样条曲线的定义如下[17]:

2 基于特征轮廓线的断裂面匹配

本文的特征轮廓线的匹配思想是: 首先根据角点对特征轮廓线分段, 然后计算分段曲线上每个顶点的曲率和挠率, 由此得到了用曲率和挠率所描述的特征串, 最后通过对特征串的匹配来完成特征轮廓线的匹配, 进而实现了断裂面的匹配.

2.1 计算曲率和挠率

2.2 断裂面的匹配

3 实验结果与分析

为了验证本文算法的有效性, 这里选取了三组K9901坑出土的秦俑碎块, 如图2所示. 第1组数据是扫描的秦俑肩膀部位的碎块, 第2组和第3组数据是扫描的不同秦俑胸前部位的碎块.

(a) 第1组碎块

(b) 第2组碎块

(c) 第3组碎块

对这三组碎块, 首先根据本文算法提取其断裂面的主轮廓线、次轮廓线和特征轮廓线, 然后分别基于主轮廓线和特征轮廓线进行碎块的匹配, 匹配结果如图3所示, 这里的每组碎块的匹配结果中的图(a)是基于主轮廓线的匹配结果, 图(b)是基于特征轮廓线的匹配结果, 很明显, 第1组图(a)的匹配中出现了部分错位, 第2组图(a)的匹配结果不理想, 存在很大的断裂面拼接处的缝隙, 存在较大误差, 第3组图(a)的匹配结果同样存在较大孔洞. 而这三组碎块的图(b)的匹配结果较为理想, 基本做到了符合实际效果的匹配结果, 因此基于特征轮廓线的匹配是一种较为有效准确的碎块匹配方法.

(a)主轮廓线匹配结果 (b)特征轮廓线匹配结果

第1组碎块的匹配结果

(a)主轮廓线匹配结果 (b)特征轮廓线匹配结果

第2组碎块的匹配结果

(a)主轮廓线匹配结果 (b)特征轮廓线匹配结果

4 结语

通过对秦俑碎块的数据分析发现, 简单的特征轮廓线不能很好地描述其轮廓特点, 因此本文采用特征轮廓线特征来进行碎块的匹配. 首先通过纹理贴图、去噪、孔洞修补、简化网格数据模型等操作进行数据预处理, 然后提取碎块的主轮廓线和次轮廓线, 进而提取碎块的特征轮廓线, 再次采用四次B样条曲线将特征轮廓线拟合成光滑的空间曲线, 并对该曲线进行分段以完成特征轮廓曲线的匹配, 从而实现断裂面的匹配. 实验证明, 较一般的轮廓线匹配算法, 本文的特征轮廓线匹配算法在匹配精度上有了很大的提高, 是一种有效的秦俑碎块断裂面匹配算法. 但是由于历史原因, 秦俑的碎块可能存在缺失、风化、二次断裂、受潮和变形等各个方面的问题, 因此数据比较复杂, 今后的研究中要综合考虑各个方面的因素, 提出更加有效的秦俑碎块匹配算法.

1 赵静,赵小乐.基于Laplace的LSSIM图像配准算法.计算机系统应用,2015,24(9):160–165.

2 陈欲勐,马无锡.基于快速模板匹配的金标试纸条图像配准. 计算机系统应用,2015,24(5):19–25.

3 葛盼盼,陈强.基于SURF特征提取的遥感图像自动配准. 计算机系统应用,2014,23(3):16–24.

4 潘荣江,孟祥旭,屠长河.一种基于LCS 的物体碎片自动拼接方法.计算机学报,2005,28(3): 351–356.

5 Shin H, Doumas C, Funkhouser T, et al. Analyzing fracture patterns in Theran wall paintings. Proc. of the 11th International Conference on Virtual Reality, Archaeology and Cultural Heritage. Eurographics Association. 2010. 71–78.

6 李姬俊男,耿国华,周明全,等.一种基于邻接约束的交互式文物模型复原系统.西北大学学报(自然科学版),2016, 46(1):55–60.

7 杜建丽,茹少峰,樊少荣,等.基于B-样条表示的物体轮廓曲线匹配.西北大学学报(自然科学版),2005,35(5):527–530.

8 吕科,耿国华,周明全,等.基于傅立叶变换的三维轮廓线快速匹配算法.西北大学学报(自然科学版),2003,33(2): 151–154.

9 Cohen F, Taslidere E, Liu ZX, et al. Virtual reconstruction of archaeological vessels using expert priors & surface markings. Proc. of IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, USA. Computer Society. 2010. 7–14.

10 李康,李静,孙家泽.一种改进的薄壁文物碎片特征轮廓线提取技术.图学学报,2015,36(2):251–256.

11 王波,孙蔚.基于OpenGL的新式OBJ文件纹理贴图方法研究.计算机与数字工程,2015,310(8):1497–1500.

12 张鑫,王章野,范涵奇,等.保特征的三维模型的三边滤波去噪算法.计算机辅助设计与图形学学报,2009,21(7): 936–942.

13 刘云华,吕剑,朱林,等.基于区域生长的三角网格模型孔洞修补方法.计算机工程,2014,40(10):239–244.

14 张必强,邢渊,阮雪榆.基于特征保持和三角形优化的网格模型简化.上海交通大学学报,2004,38(8):1373–1377.

15 李群辉,周明全,耿国华.破碎刚体三角网格模型的断裂面分割.计算机应用,2011,31(8):2204–2205,2216.

16 Deschenes F, Ziou D. Detection of line junctions and line terminations using curvilinear features. Pattern Recognition Letters, 2000, 21(6): 637–649.

17 丁爱玲,周琳,李鹏.计算机图形学.西安:西安电子科技大学出版社,2005.

Effective Blocks Matching Algorithm of Terracotta Warrior

ZHAO Fu-Qun1,2, ZHOU Ming-Quan2

1(School of Education Science, Xianyang Normal University, Xianyang 712000, China)2(School of Information Science and Technology, Northwest University, Xi’an 710127, China)

Aiming at 3D mesh data model of Terracotta Warrior blocks, a block fracture surface matching algorithm based on feature contour is proposed in the paper. Firstly, the data model is pretreated, such as texture map, data denoising, hole filling, data model simplification and so on. Secondly, the primary contour and secondary contour are extracted, and then the feature contour is extracted too. Lastly, the feature contour is segmented according to the corner point in order to match the feature contour by the longest common subsequence method, then the contour feature matching is completed, and the fracture surface matching is achieved. The experimental results show that the algorithm proposed in the paper is an effective and accurate Terracotta Warrior blocks matching method.

Terracotta Warrior; blocks matching; feature contour; corner point; the longest common subsequence; curvature; torsion

国家自然科学基金(61373117)

2016-06-29;

2016-08-31

[10.15888/j.cnki.csa.005654]