引用本文

胡佳贝, 周蓬勃, 耿国华, 陈小雪, 杨稳, 王飘. 基于生成树代价和和几何约束的文物碎片自动重组方法. 自动化学报, 2020, 46(5): 946−956 doi:  10.16383/j.aas.c180614

Hu Jia-Bei, Zhou Peng-Bo, Geng Guo-Hua, Chen Xiao-Xue, Yang Wen, Wang Piao. Reassembly of fractured fragments based on spanning tree cost and geometric constraints. Acta Automatica Sinica, 2020, 46(5): 946−956 doi:  10.16383/j.aas.c180614

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

关键词

碎片重组，带权无向完全图，最小(大)代价和，Hausdorff距离 

摘要

在文物碎片自动重组过程中, 针对传统基于几何驱动重组的方法容易受噪声影响会产生误匹配等问题, 本文提出一种基于生成树代价和和几何约束的文物碎片自动重组方法. 首先, 采用曲度函数提取碎片断裂面上凹凸性显著的n个特征点; 进而, 对其进行拓扑重构, 以特征点空间位置之间的欧氏距离为权值, 构造n阶带权无向完全图及其最小、最大生成树, 以生成树的代价和为邻接约束, 快速筛选潜在匹配碎片; 然后, 再以特征点的主曲率构造特征串, 引入Hausdorff距离来衡量两个特征串之间的相似程度, 可以有效找出配对碎片; 最后, 采用四元数法估算旋转平移矩阵将碎片粗对齐, 再采用迭代最近点算法实现精确对齐. 实验结果表明, 重组误差小于1 mm, 与传统方法相比, 该方法特征点数量较少, 计算量小, 有效提高了碎片重组的效率和准确性.

文章导读

文物是我国历史悠久的文化积淀和智慧结晶. 但由于自然及人为等因素的影响, 导致大多数文物呈现破碎或不完整状态. 传统的文物修复依靠考古学知识手工操作, 使得人工修复速度慢、准确性低、二次破坏等缺点. 近年来, 利用计算机辅助文物虚拟复原具有高速、便捷、无破坏等优势, 提高了文物修复的效率, 对文物保护和复原有着至关重要的意义.

根据文物的厚度信息, 自动化文物虚拟复原对象大致可分为两类: 薄壁类碎片和非薄壁类碎片两大类[1]. 不管是薄壁类文物碎片还是非薄壁类文物碎片, 其重组问题是一个大规模、非线性、多目标的组合优化NP难问题. 针对非薄壁类碎片的重组问题, 通常采用基于碎片断裂面几何特征搜索配对碎片, 实现碎片的重组. 该类方法的代表性研究有Winkelbach等[2]使用碎片断裂面上的所有顶点的法向与曲率等特征, 利用随机采样算法和分级二叉树实现碎片的配对. Altantsetseg等[3]基于傅里叶变换提取曲面上的特征曲线, 通过比较曲线的系数实现断裂面的匹配. Huang等[4]基于点云模型, 通过计算顶点的积分不变量来刻画断裂面的尖锐程度, 以此来分割断裂面, 然后通过基于向前搜索技术和表面一致性的约束方法进行碎片的成对重组. Papaioannou等[5]采用Z缓冲方法, 得到碎片的断裂面的投影, 然后计算当前位置断裂区域的“位置误差”, 最终实现碎片之间匹配. Chen等[6]利用曲面中心点、局部曲面的类型及二维直方图刻画特征点处的局部曲面描述子, 通过几何散列算法对碎片进行匹配. 王坚等[7]将曲面匹配问题转化为图论中的最大权团搜索问题并通过自旋图确定匹配关系. 李姬俊男等[8]提出一种基于空间曲面特征优化的匹配算法, 首先计算模型表面点体积积分不变量形成匹配约束簇, 然后定义3类空间几何一致性约束, 并采用最大独立集方法对非正确匹配对进行筛选.

然而, 上述方法在搜索匹配对时, 大多是采用断裂面轮廓线或凹凸区域上所有顶点的几何信息, 几何信息在估计时容易受噪声的影响; 其次, 基于单个点的几何特征匹配具有随机性, 忽略点与点之间的拓扑信息, 会造成误匹配等结果, 导致重组过程会出现错位、渗透等现象.

因此, 本文在传统基于几何特征匹配的基础上, 融入特征点之间隐含的拓扑信息, 提出一种基于生成树代价和和几何约束的文物碎片自动重组方法. 该方法采用两级匹配策略搜索配对碎片, 首先, 对碎片断裂面进行分割, 采用曲度函数获取碎片断裂面凹凸性显著的n个特征点, 进而, 以特征点空间位置之间的欧氏距离为权值, 构造n阶带权无向完全图, 利用Prime算法生成最小、最大生成树, 以其代价和为约束快速筛选潜在匹配碎片; 然后, 再以断裂面特征点的主曲率构造特征串, 通过Hausdorff距离衡量特征串之间的相似性, 找到最佳配对碎片. 最后, 采用四元数法计算刚体变换矩阵将碎片进行粗对齐, 再采用迭代最近点算法实现精确对齐, 有效提高了碎片重组的速度和准确率.

图 1  顶点v的邻域点

图 2  两个任意4阶带权无向完全图

图 3  同一连通网的不同最小生成树

在文物碎片自动重组过程中, 针对传统基于几何特征匹配的方法容易受噪声影响会产生误匹配等问题, 本文提出一种基于生成树代价和和几何约束的文物碎片自动重组方法. 该方法首先提取特征点, 对其进行拓扑重构及简化, 然后采用两级匹配策略, 从而有效搜索配对碎片. 最后, 采用四元数法计算刚体变换矩阵将碎片进行粗对齐, 再采用迭代最近点算法实现精确对齐. 本文算法不但克服传统基于几何驱动重组方法的缺点, 而且保证特征点数量较少, 计算量小, 有效提高了碎片重组的效率和准确性.

但由于碎片形状的多样性, 本文算法的局限性在于只能对断裂处信息基本完整的碎片适用, 对于断裂处有缺失的情况并不适用. 为了解决这类问题, 需要寻找更合适的特征描述符及匹配策略, 这将是下一步研究的内容.

作者简介

胡佳贝

西北大学信息科学与技术学院硕士研究生. 主要研究方向计算机图形学, 可视化技术. E-mail: jbhu@stumail.nwu.edu.cn

周蓬勃

北京师范大学艺术与传媒学院讲师. 主要研究方向为数字媒体, 虚拟现实. E-mail: zhoupengbo@bnu.edu.cn

耿国华

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

陈小雪

西北大学信息科学与技术学院硕士研究生. 主要研究方向为三维文物点云压缩及重建技术. E-mail: Chenxiaoxue@stumail.nwu.edu.cn

杨稳

西北大学信息科学与技术学院博士研究生. 主要研究方向为机器学习与模式识别. E-mail: yw@stumail.nwu.edu.cn

王飘

西北大学信息科学与技术学院硕士研究生. 主要研究方向为文化遗产数字化复原, 可视化技术. E-mail: wendywp@126.com