引用本文

袁洁, 周明全, 耿国华, 张雨禾. 基于Morse-Smale拓扑特征的文物碎片拼接算法. 自动化学报, 2018, 44(8): 1486-1495. doi: 10.16383/j.aas.2017.c160778

YUAN Jie, ZHOU Ming-Quan, GENG Guo-Hua, ZHANG Yu-He. Automatic Reassembly of Fractured Fragments Using Morse Topological Features. ACTA AUTOMATICA SINICA, 2018, 44(8): 1486-1495. doi: 10.16383/j.aas.2017.c160778

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160778

关键词

Morse-Smale复形，刚体变换，特征描述符，四元数，穷举搜索 

摘要

针对计算机辅助文物虚拟复原中由于破损文物断裂部位边缘受损而引起的轮廓线不能充分表示断裂面几何特征的问题，提出了一种基于断裂面拓扑特征的破碎文物自动拼接算法.首先，定义碎片模型顶点显著度指标函数，提取断裂面特征点，依据Morse-Smale复形理论构建并简化断裂面的几何拓扑图；然后，通过定义基准点与0值面，从而计算目标点的对应高度差值，将拓扑图中四边形曲面构造成为能完整表示断裂面几何特征的特征描述符，并根据凹凸互补性计算初始特征四边形匹配集的误差，筛选出最优匹配集；最后，采用四元组方法计算旋转、平移矩阵，利用穷举搜索法实现碎片的精确拼接.实验结果表明，该方法针对断裂部位边缘受损的破碎文物模型可获得较满意的拼接效果.

文章导读

三维破碎物体的匹配与拼接是计算机图形学、模式识别、可视化技术等众多领域里一个颇具挑战的问题. 20世纪末, 随着计算机技术的快速发展, 将计算机技术引入到文物碎片的虚拟拼接过程中, 提高了文物复原的效率, 对文物保护和复原至今有着重要的意义.

文物数字化虚拟拼接技术, 根据复原过程中是否有专家参与可分为自动复原方法和交互式复原方法.其中, 现有的刚体匹配算法主要结合破损文物断裂区域的几何特征, 作为判断相邻碎片之间相似性的主要依据, 从而实现破损文物的完整拼合[1].

根据文物的厚度信息, 自动化虚拟复原技术可大致分为两类:薄壁类和非薄壁类文物碎片.早期薄壁类破损文物的虚拟拼接, 主要以提取断裂面轮廓线, 并将其映射成为二维平面曲线, 实现碎片拼合[1-6].例如Cooper等[1]通过结合碎片轮廓线及其法向, 以最大似然函数为基础进行自底向上的搜索, 完成碎片模型的自动拼合.樊少荣等[2]区分三角网格曲面模型的外表面与断裂面从而正确提取出内轮廓线和外轮廓线, 实现碎片的精确拼合. Oxholm等[3]将断裂面轮廓线上顶点的曲率、挠率以及颜色信息进行结合, 组成特征属性串, 采用最长公共子串的方法实现轮廓线间的匹配. Willi等[4]将贝叶斯分析应用在半自动拼合方法中, 该算法对断裂面光滑平整且轴对称的三维模型有很好的匹配效果, 其局限性是只能作用于有限形状的三维模型. Zhang等[5]基于模板匹配的思想确定颅骨碎片的位置关系, 再结合相邻碎片轮廓曲线实现碎片拼接. Huang等[6]通过计算模型表面顶点的积分不变量值提取碎块表面尖锐的边缘线, 基于向前搜索技术和表面一致性的约束方法实现碎片的两两拼合.空间轮廓曲线匹配方法在几何特征的数值化计算时具有简单高效的特点; 但由于其采样点数量有限, 因此这类方法对噪声较敏感并且易忽略厚度信息的部分文物碎片模型效果较差.

非薄壁类刚体匹配对文物重建、数字化遗产保护有着重要的意义[7]. Papaioannou等[8]采用Z缓冲方法, 获取三维模型断裂面投影, 计算当前位置断裂区域的"位置误差", 通过最小化误差获得最优匹配, 实现虚拟复原, 该方法适用于雕塑、纪念碑等大体积破碎模型的修复.李姬俊男等[9]基于相邻断裂面间的凹凸互补性, 通过提取约束性的特征簇完成碎片间的两两拼合. Sahner等[10]通过计算断裂区域顶点的坐标和法向, 采用层次聚类方法进行破损文物碎块之间的拼合.由于断裂面中包含了较多的特征信息, 能够准确地反映模型断裂区域的邻接关系, 因此, 针对非薄壁类文物碎片, 基于空间曲面的碎片拼合, 具有一定优势, 但针对断裂面部位受损较严重的碎块, 匹配的正确性无法保证.

因此针对破损文物断裂部位边缘受损而引起的轮廓线不能充分表示断裂面几何信息的问题, 本文基于文献[11]中的特征线提取方法, 提出一种基于Morse-Smale的断裂面拓扑几何特征的破碎刚体自动拼接方法.本文算法包括断裂面拓扑图的生成、四边形描述符的定义、匹配集的确定以及碎片拼合4个主要部分, 步骤如图 1所示.本文算法的核心思想是采用曲面四边形描述符表示断裂面几何特征信息.在传统的基于空间曲线的碎片拼合方法中, 针对断裂部位边缘受损而提取的轮廓线不精确, 错误的曲线匹配导致断裂面渗透; 传统的基于空间曲面的碎片拼合方法, 并没有考虑断裂面特征点之间的拓扑关系, 可能出现断裂面的错误配准.因此, 为了提高碎片拼合的效果, 基于Morse-Smale复形[12]本身的四边形性质及其可控性和鲁棒性, 本文借助能有效融合断裂面上凹凸信息的四边形曲面, 更好地反映空间曲面特征, 并且可精确地确定邻接碎片的匹配关系, 同时采用凹凸互补阈值方法筛选出最优匹配集, 将计算量较大的空间点对应关系转换成少数的四边形匹配, 有效地提高了刚体转换的效率, 最后采用穷举搜索的方法实现破损碎片精确拼接.

图 1  本文方法步骤

图 2  顶点邻域关系图

图 3  环状和孤立临界点

针对破损文物断裂部位边缘受损而引起的轮廓线不能充分表示断裂面几何特征的问题, 本文提出了一种基于Morse-Smale的断裂面拓扑特征的破损文物自动拼接算法.该算法将断裂面上特征点的曲度函数作为特征检测算法, 根据断裂面几何特征提取特征点; 采用最大角度法对特征点进行特征线构建, 并计算特征线重要度简化拓扑图, 得到断裂面的纯四边形拓扑图; 将拓扑图中四边形曲面构造成为能有效表示断裂面集合特征的描述符, 弥补了传统方法反映局部特征的不足, 提高了匹配的精度和效率, 同时扩展了匹配算法的使用范围.本文算法需要较为精确地识别出碎片的断裂面, 解决薄壁类破损碎片断裂面特征平滑, 无法取得精确地拼合结果的难题.

由于本文算法采用了拓扑图四边形为特征描述符, 因此在提取特征描述符时较耗时, 寻找一种更加鲁棒、高效地特征提取算法以减少计算量, 将是我们下一步工作的重点.

作者简介

袁洁

西北大学信息科学与技术学院硕士研究生.2015年获得西北大学计算机科学与技术学士学位.主要研究方向为图形几何处理, 可视化技术.E-mail:yuanjie4920@163.com

耿国华  

西北大学信息科学与技术学院教授.主要研究方向为计算机图形图像处理, 可视化技术.E-mail:ghgeng@nwu.edu.cn

张雨禾 

西北大学信息科学与技术学院博士研究生.2012年获得西北大学计算机科学与技术学士学位.主要研究方向为图形几何处理, 可视化技术及3D打印技术.E-mail:zhangyuhe0601@126.com

周明全  

北京师范大学信息科学与技术学院教授.主要研究方向为虚拟现实与可视化技术, 智能信息处理, 数据库与知识库, 图形图像处理.本文通信作者.E-mail:mqzhou@bnu.edu.cn