基于生成树代价和和几何约束的文物碎片自动重组方法

胡佳贝; 周蓬勃; 耿国华; 陈小雪; 杨稳; 王飘

doi:10.16383/j.aas.c180614

基于生成树代价和和几何约束的文物碎片自动重组方法

doi: 10.16383/j.aas.c180614

胡佳贝^1,,
周蓬勃^2,,
耿国华^1,,
陈小雪^1,,
杨稳^1,,
王飘^1,

1.
西北大学信息科学与技术学院西安 710127 中国
2.
北京师范大学艺术与传媒学院北京 100875 中国

基金项目: 国家自然科学基金(61802311, 61731015, 61673319, 61602380), 国家重点研发项目(2017YFB1402103), 陕西省重点研发计划(2019SF-272), 陕西省教育厅自然科学专项(18JK0795), 陕西省产业创新链项目(2016TZC-G-3-5), 青岛市自主创新重大专项项目(2017-4-3-2-xcl), 陕西省自然科学基金(2018JM6029)资助

详细信息

作者简介:
胡佳贝：西北大学信息科学与技术学院硕士研究生. 主要研究方向计算机图形学, 可视化技术. 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

计量
- 文章访问数: 1761
- HTML全文浏览量: 193
- PDF下载量: 125
- 被引次数: 0
出版历程
- 收稿日期: 2018-09-14
- 录用日期: 2019-07-30
- 网络出版日期: 2020-06-01
- 刊出日期: 2020-06-01

Reassembly of Fractured Fragments Based on Spanning Tree Cost and Geometric Constraints

1.
College of Information Science and Technology, Northwest University, Xi’an 710127, China
2.
College of Arts and media, Beijing Normal University, Beijing 100875, China

Funds: Supported by National Science Foundation of China (61802311, 61731015, 61673319, 61602380), National key research and development projects(2017YFB1402103), Shaanxi Provincial Key Research and Development Program(2019SF-272), Shaanxi Provincial Department of Education Natural Science Special Project(18JK0795), Shaanxi Industrial Innovation Chain Project(2016TZC-G-3-5), Qingdao Municipality's Independent Innovation Major Project(2017-4-3-2-xcl), Shaanxi Natural Science Foundation(2018JM6029),

摘要

摘要: 在文物碎片自动重组过程中, 针对传统基于几何驱动重组的方法容易受噪声影响会产生误匹配等问题, 本文提出一种基于生成树代价和和几何约束的文物碎片自动重组方法. 首先, 采用曲度函数提取碎片断裂面上凹凸性显著的n个特征点; 进而, 对其进行拓扑重构, 以特征点空间位置之间的欧氏距离为权值, 构造n阶带权无向完全图及其最小、最大生成树, 以生成树的代价和为邻接约束, 快速筛选潜在匹配碎片; 然后, 再以特征点的主曲率构造特征串, 引入Hausdorff距离来衡量两个特征串之间的相似程度, 可以有效找出配对碎片; 最后, 采用四元数法估算旋转平移矩阵将碎片粗对齐, 再采用迭代最近点算法实现精确对齐. 实验结果表明, 重组误差小于1 mm, 与传统方法相比, 该方法特征点数量较少, 计算量小, 有效提高了碎片重组的效率和准确性.
- 碎片重组 /
- 带权无向完全图 /
- 最小(大)代价和 /
- Hausdorff距离
Abstract: In the process of automatic reassembly of fractured fragments, the traditional methods based on geometric feature matching are sensitive to noises, which leads to mismatching points/fragments. An automatic reassembly method based on spanning tree cost and geometric constraints is proposed. Firstly, n features with significant concavity or convexity on the fracture surfaces of the fragments are extracted using the curvature function. Then, the topologies of the features are reconstructed, therefore, the n-th order weighted undirected complete graph and its minimum and maximum spanning trees can be constructed by setting the Euclidean distance between the feature points as the weights; thus the cost of spanning trees are utilized as the adjacency constraint in order to quickly screens the potential matching fragments. Furthermore, the feature strings are formed by aggregating the main curvatures of the feature points, and the Hausdorff distance is used to measure the similarities between the two feature strings. Consequently, the matching pieces of fragments can be effectively detected. Finally, the quaternion method is performed to complete the coarse alignment of adjacent fragments, and then the iterative closest point algorithm (ICP) is used to achieve precise alignment. The experimental results demonstrate that the reassembly error is less than 1mm, and compared to the traditional method, the number of feature points used in the proposed method is relatively small, and the computational complexity is reduced, which effectively improves the efficiency and accuracy of fragments reassembly.
- Reassembly of fragments /
- weighted undirected complete graph /
- minimum (maximum) cost sum /
- Hausdorff distance

HTML全文

图 1 顶点$v$的邻域点

Fig. 1 Neighborhood point of vertex v

下载: 全尺寸图片幻灯片

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

Fig. 2 Two arbitrary 4-order weighted undirected complete graphs

下载: 全尺寸图片幻灯片

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

Fig. 3 Different minimum spanning trees of the same connected net

下载: 全尺寸图片幻灯片

图 4 断裂面A、B的最小、最大生成树

Fig. 4 Minimum and maximum spanning trees for fracture surfaces A and B

下载: 全尺寸图片幻灯片

图 5 断裂面上特征点对应关系

Fig. 5 Correspondence of feature points on the fracture surfaces

下载: 全尺寸图片幻灯片

图 6 G10-57号俑左手臂部分邻接碎片重组结果

Fig. 6 Reassembly results of some left arm adjacent fragments of Warriors of G10-57

下载: 全尺寸图片幻灯片

图 9 G3-2号俑部分邻接碎片重组结果

Fig. 9 Reassembly results of some adjacent fragments of Warriors of G3-2

下载: 全尺寸图片幻灯片

图 7 G10-57号俑右手臂部分邻接碎片重组结果

Fig. 7 Reassembly results of some right arm adjacent fragments of Warriors of G10-57

下载: 全尺寸图片幻灯片

图 8 G10-57号俑部分邻接碎片重组结果

Fig. 8 Reassembly results of some adjacent fragments of Warriors of G10-57

下载: 全尺寸图片幻灯片

图 10 不同文献方法结果对比

Fig. 10 Comparison of results from different literature methods

下载: 全尺寸图片幻灯片

表 1 原始碎片数据表

Table 1 Raw fragment data table

Experimental data	Number of fragment	Fragment number	Triangular grid number	Number of fracture faces
G10-57	4	brick1#	403122	7
		brick2#	31270	1
		brick3#	31030	2
		brick4#	45840	1
G3-2	2	brick5#	86266	3
G3-2	2	brick6#	94538	4
G10-6	3	brick7#	62230	4
		brick8#	47595	4
		brick9#	35932	4

下载: 导出CSV

表 2 不同算法性能对比

Table 2 Performance comparison of different algorithms

Experimental data	Running time (s)		Recombination error (mm)		Initial match rate
Experimental data	Reference [17] method	Our method	Reference [17] method	Our method	Our method
brick1#-2#	23.596	14.748	1.2235	0.8842	0.04
brick3#-4#	19.236	13.472	1.4596	0.9151	0.06
brick1#-2#-3#-4#	28.197	20.643	1.2788	0.8962	0.02
brick5#-6#	41.259	37.941	1.2824	0.8027	0.08
brick7#-8#	25.845	19.739	1.3205	0.8425	0.04
brick7#-8#-9#	46.347	40.675	1.4752	0.9304	0.02

下载: 导出CSV

参考文献(18)

[1]	Zheng S Y, Huang R Y, Li J, Wang Z. Reassembling 3D thin fragments of unknown geometry in cultural heritage. Photogrammetrie Fernerkundung Geoinformation, 2015, 2015(3): 215−230 doi: 10.1127/pfg/2015/0267
[2]	Winkelbach S, Wahl F M. Pairwise matching of 3D fragments using cluster trees. International Journal of Computer Vision, 2008, 78(1): 1−13 doi: 10.1007/s11263-007-0121-5
[3]	Altantsetseg E, Matsuyama K, Konno K. Pairwise matching of 3D fragments using fast fourier transform. The Visual Computer, 2014, 30(6−8): 929−938 doi: 10.1007/s00371-014-0959-9
[4]	Huang Q X, Simon Flöry, Gelfand N, Hofer M, Pottmann H. Reassembling fractured objects by geometric matching. ACM Transactions on Graphics, 2006, 25(3): 569−578 doi: 10.1145/1141911.1141925
[5]	Papaioannou G, Karabassi E A, Theoharis T. Virtual archaeologist: assembling the past. IEEE Computer Graphics and Applications, 2001, 21(2): 53−59 doi: 10.1109/38.909015
[6]	Chen H C H, Bhanu B B B. 3D free-form object recognition in range images using local surface patches. Pattern Recognition Letters, 2007, 28(10): 1252−1262 doi: 10.1016/j.patrec.2007.02.009
[7]	王坚, 周来水. 基于最大权团的曲面粗匹配算法. 计算机辅助设计与图形学学报, 2008, 20(2): 167−173 Wang Jian, Zhou Lai-Shui. Surface rough matching algorithm based on maximum weight clique. Journal of Computer-Aided Design & Computer Graphics, 2008, 20(2): 167−173
[8]	李姬俊男, 耿国华, 周明全, 康馨月. 文物碎块虚拟拼接中的表面特征优化. 计算机辅助设计与图形学学报, 2014, 26(12): 2149−2154 Li Ji-Jun-Nan, Geng Guo-Hua, Zhou Ming-Quan, Kang Xin-Yue. Surface feature optimization for virtual matching of relic fragments. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(12): 2149−2154
[9]	李群辉. 基于断裂面匹配的破碎刚体复原研究[博士学位论文]. 西北大学, 中国, 2013 Li Qun-Hui. Research on Fractured Slid Recovery Based on Bracture Surfaces Matching [Ph. D. dissertation], Northwest University, China, 2013
[10]	袁洁, 周明全, 耿国华, 张雨禾. 基于Morse-Smale拓扑特征的文物碎片拼接算法. 自动化学报, 2018, 44(8): 1486−1495 Yuan Jie, Zhou Ming-Quan, Geng Guo-Hua, Zhang Yu-He. Automatic reassembly of fractured fragments based on Morse topological features. Acta Automatica Sinica, 2018, 44(8): 1486−1495
[11]	严蔚敏. 数据结构, 第二版. 北京: 清华大学出版社, 1992. Yan Wei-Min. Data Structure, Second Edition. Beijing: Tsinghua University Press, 1992.
[12]	Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms, Third Edition. US: The MIT Press, 2009
[13]	Jesorsky O, Kirchberg K J, Firschholz R W. Robust face detection using the Hausdorff distance. International Conference on Audio-& Video-based Biometric Person Authentication. Springer-Verlag, 2001. 90−95
[14]	Horn B K P, Hilden H M, Negahdaripour S. Closed-form solution of absolute orientation using orthonormal matrices. Journal of the Optical Society of America A, 1988, 5(7): 1127−1135 doi: 10.1364/JOSAA.5.001127
[15]	江刚武. 空间目标相对位置和姿态的抗差四元数估计[博士学位论文]. 解放军信息工程大学, 中国, 2009 Jiang Gang-Wu. A robust estimation using quaternions for relative pose of space object [Ph. D. dissertation]. The PLA Information Engineering University, China, 2009
[16]	Besl P J, Mckay H D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239−256 doi: 10.1109/34.121791
[17]	李群辉, 张俊祖, 耿国华, 周明全. 以轮廓曲线为特征的断裂面匹配. 西安交通大学学报, 2016, 50(9): 105−110 doi: 10.7652/xjtuxb201609017 Li Qun-Hui, Zhang Jun-Zu, Geng Guo-Hua, Zhou Ming-Quan. Fracture surfaces matching based on contour curve. Journal of Xi'an Jiao Tong University, 2016, 50(9): 105−110 doi: 10.7652/xjtuxb201609017
[18]	Wang Z, Bovik A C. Mean squared error: Love it or leave it? A new look at signal fidelity measures. IEEE Signal Processing Magazine, 2009, 26(1): 98−117 doi: 10.1109/MSP.2008.930649