基于形状骨架图匹配的文物碎片自动重组方法

张雨禾; 耿国华; 魏潇然; 张靖; 周明全

doi:10.16383/j.aas.2017.c160336

基于形状骨架图匹配的文物碎片自动重组方法

doi: 10.16383/j.aas.2017.c160336

张雨禾^1,,
耿国华^1, ,,
魏潇然^2,,
张靖^1,,
周明全^3,

1.
西北大学信息科学与技术学院西安 710127
2.
西北大学新闻传播学院西安 710127
3.
北京师范大学信息科学与技术学院北京 100875

基金项目:

高等学校博士学科点专项科研基金 20136101110019

国家自然科学基金 61602380

陕西省教育厅科学研究项目 16JK2178

国家自然科学基金 61673319

国家自然科学基金 61373117

详细信息

作者简介:
张雨禾  西北大学信息科学与技术学院博士研究生.2012年获得西北大学软件工程专业学士学位.主要研究方向为图形几何处理, 可视化技术及3D打印技术.E-mail:zhangyuhe0601@126.com

魏潇然  博士，西北大学新闻传播学院讲师.2016年获得西北大学计算机应用技术专业博士学位.主要研究方向为图形几何处理, 3D打印技术.E-mail:wxran1987@163.com

张靖  西北大学信息科学与技术学院硕士研究生.主要研究方向为图像处理, 可视化技术.E-mail:zj18710812436@163.com

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

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

计量
- 文章访问数: 2313
- HTML全文浏览量: 367
- PDF下载量: 6486
- 被引次数: 0
出版历程
- 收稿日期: 2016-04-15
- 录用日期: 2016-08-02
- 刊出日期: 2017-04-01

Reassembly of Fractured Fragments Based on Skeleton Graphs Matching

1.
School of Information Science and Technology, Northwest University, Xi'an 710127
2.
School of Journalism and Communication, Northwest University, Xi'an 710127
3.
College of Information Science and Technology, Beijing Normal University, Beijing 100875

Funds:

Special Research Fund for the Doctoral Program of Higher Education 20136101110019

National Natural Science Foundation of China 61602380

Scientiflc Research Project of Shaanxi Provincial Department of Education 16JK2178

National Natural Science Foundation of China 61673319

National Natural Science Foundation of China 61373117

More Information

Author Bio:
Ph. D. candidate at the School of Information Science and Technology, Northwest University. She received her bachelor degree from Northwest University in 2012. Her research interest covers graphics geometry processing, visualization technology and 3D printing technology

Ph. D. and lecturer at the School of Journalism and Communication, Northwest University. He received his Ph. D. degree from Northwest University in 2016. His research interest covers graphics geometry processing and 3D printing technology

Master student at the School of Information Science and Technology, Northwestern University. Her research interest covers computer graphics and visualization

Professor at the School of Information Science and Technology, Beijing Normal University. His research interest covers virtual reality and visualization technology, intelligent information processing, database and knowledge base, graphics and image processing

Corresponding author: GENG Guo-Hua Professor at the School of Information Science and Technology, Northwest University. Her research interest covers graphics image processing and visualization technology. Corresponding author of this paper

摘要

摘要: 为了有效解决文物碎片自动重组中由于断裂部位受损造成几何信息丢失，采用传统几何驱动方法容易失效的问题，本文提出一种基于形状骨架图匹配的文物碎片自动重组方法，将碎片匹配问题转化为碎片表面纹饰中非完整纹元的互补匹配问题.首先，通过提取文物碎片表面特征线得到碎片表面的纹饰信息；然后根据完整纹元的特征确定非完整纹元互补匹配的约束条件，采用视觉骨架剪枝的方法提取完全位于断裂部位的非完整纹元的形状骨架图，基于形状骨架图语法及匹配约束条件判定非完整纹元是否互补匹配；接着，将碎片上非完整纹元的顺序作为上层约束条件，采用基于带剪枝深度优先的搜索方法搜索匹配碎片；最后，以邻接碎片上非完整纹元间公共弦的端点作为邻接约束点，采用最小二乘法计算刚体变换参数得到碎片的初始位置，并采用迭代最近点方法将邻接碎片精确对齐.实验结果表明，该方法能够有效解决断裂部位存在缺损文物碎片的自动重组问题.
- 碎片重组 /
- 特征线 /
- 表面邻接约束 /
- 形状匹配
Abstract: In order to effectively address the problem that traditional geometry-driven methods fail to reassemble the fragments with incompleteness in fracture surfaces or break-curves, an automatic reassembly method based on skeleton graph of shape matching is proposed, which transfers the matching of fragments into complementary matching of incomplete geometry texels. Firstly, the surface ornamentation information is obtained by extracting the feature lines of the fragments. Secondly, the constraints for matching texels are designed according to the features of complete texels, and a visual skeleton pruning method is utilized to generate the skeletons of the shapes of the incomplete texels and the grammar of skeleton graphs is introduced. Then, the sequence of the incomplete texels is used as the upper constraint and a depth-first searching method with pruning for adjacent fragments is presented. Finally, the endpoints of the common chords of the incomplete texels on the adjacent fragments are used as the initial matching points in order to calculate the initial position of the fragment. After that, the iterated closest point (ICP) method is employed to precisely align the adjacent fragments. Experimental results show that the proposed method can successfully solve the reassembly problem of the fragments with incompleteness in fractured surfaces and break-curves.
- Reassembly of fragments /
- feature lines /
- surface adjacency constraints /
- shape matching

HTML全文

图 1 G10-19号俑部分碎片表面纹饰特征线提取结果

Fig. 1 The results of feature lines extraction from fragments of Warriors G10-19

下载: 全尺寸图片幻灯片

图 2 4种纹元破碎情况

Fig. 2 Four styles of fractured texels

下载: 全尺寸图片幻灯片

图 3 形状骨架图语法规则

Fig. 3 Grammatical rules of skeleton graphs

下载: 全尺寸图片幻灯片

图 4 部分非完整纹元奇点图

Fig. 4 Skeleton graphs of some incomplete texels

下载: 全尺寸图片幻灯片

图 5 邻接碎片搜索流程

Fig. 5 Searching pipeline of adjacent fragments

下载: 全尺寸图片幻灯片

图 6 碎片纹元顺序示意图

Fig. 6 Illustration for the sequences of texels on fragments

下载: 全尺寸图片幻灯片

图 7 纹元顺序计算示意图

Fig. 7 Illustration for the computation of the texels sequences

下载: 全尺寸图片幻灯片

图 8 G10-19号俑部分邻接碎片拼接结果

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

下载: 全尺寸图片幻灯片

图 9 G10-13号俑部分邻接碎片拼接结果

Fig. 9 Reassembly results of some adjacent fragments of Warriors G10-13

下载: 全尺寸图片幻灯片

图 10 G10-52号俑部分邻接碎片拼接结果

Fig. 10 Reassembly results of some adjacent fragments of Warriors G10-52

下载: 全尺寸图片幻灯片

图 11 G10-54号俑部分邻接碎片拼接结果

Fig. 11 Reassembly results of some adjacent fragments of Warriors G10-54

下载: 全尺寸图片幻灯片

图 12 G10-39号俑部分邻接碎片拼接结果

Fig. 12 Reassembly results of some adjacent fragments of Warriors G10-39

下载: 全尺寸图片幻灯片

图 13 G10-36号俑部分邻接碎片拼接结果

Fig. 13 Reassembly results of some adjacent fragments of Warriors G10-36

下载: 全尺寸图片幻灯片

图 14 薄壁碎片模型特征线提取结果

Fig. 14 Feature lines extraction of a shell fragment model

下载: 全尺寸图片幻灯片

图 15 传统算法实验结果

Fig. 15 Experimental results of traditional methods

下载: 全尺寸图片幻灯片

表 1 兵马俑碎片模型数据

Table 1 Data of fragment models of warriors

编号	碎片数量	碎片点云数据总量	含非完整纹元数量
G10-54	4	140 764	22
G10-39	5	418 576	33
G10-36	7	301 783	23

下载: 导出CSV

表 2 本文算法运行时间 (s)

Table 2 Execute time of the proposed algorithm (s)

编号	Stage ${\rm{\# }} $1	Stage ${\rm{\# }} $2	Stage ${\rm{\# }} $3	总时间
G10-54	20.513	13.671	5.118	39.302
G10-39	70.732	20.889	7.142	98.763
G10-36	58.132	12.482	5.331	75.945

下载: 导出CSV

参考文献(22)

[1]	Üçoluk G, Toroslu I H. Automatic reconstruction of broken 3-D surface objects. Computers & Graphics, 1999, 23(4):573-582 http://www.academia.edu/7961995/Automatic_reconstruction_of_broken_3-D_surface_objects
[2]	Cooper D B, Willis A, Andrews S, Baker J, Cao Y, Han D J, Kang K B, Kong W X, Leymarie F F, Orriols X, Velipasalar S, Vote E L, Joukowsky M S, Kimia B B, Laidlaw D H, Mumford D. Bayesian pot-assembly from fragments as problems in perceptual-grouping and geometric-learning. In:Proceedings of the 16th International Conference on Pattern Recognition. Quebec City, Canada:IEEE, 2002. 297-302
[3]	樊少荣, 茹少峰, 周明全, 耿国华.破碎刚体三角网格曲面模型的特征轮廓线提取方法.计算机辅助设计与图形学学报, 2005, 17(9):2003-2009 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF200509017.htm Fan Shao-Rong, Ru Shao-Feng, Zhou Ming-Quan, Geng Guo-Hua. A method of extracting feature contour from triangular mesh surface model of fractured solid. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(9):2003-2009 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF200509017.htm
[4]	Oxholm G, Nishino K. Reassembling thin artifacts of unknown geometry. In:Proceedings of the 12th International Conference on Virtual Reality, Archaeology and Cultural Heritage. Aire-la-Ville, Switzerland:Eurographics Association Press, 2011. 49-56
[5]	李姬俊男, 耿国华, 周明全, 康馨月.文物碎块虚拟拼接中的表面特征优化.计算机辅助设计与图形学学报, 2014, 26(12):2149-2154 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201412007.htm 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 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201412007.htm
[6]	Winkelbach S, Rilk M, Schönfelder C, Wahl F M. Fast random sample matching of 3D fragments. In:Proceedings of the 26th DAGM Symposium on Pattern Recognition, Lecture Notes in Computer Science. Tübingen, Germany:Springer, 2004. 129-136
[7]	Huang Q X, Flöry S, 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
[8]	Chen H, Bhanu 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
[9]	王坚, 周来水.基于最大权团的曲面粗匹配算法.计算机辅助设计与图形学学报, 2008, 20(2):167-173 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF200802006.htm 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 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF200802006.htm
[10]	Mellado N, Reuter P, Schlick C. Semi-automatic geometry-driven reassembly of fractured archeological objects. In:Proceedings of the 11th International Conference on Virtual Reality, Archaeology and Cultural Heritage. Aire-la-Ville, Switzerland:Eurographics Association Press, 2010. 33-38
[11]	Palmas G, Pietroni N, Cignoni P, Scopigno R. A computer-assisted constraint-based system for assembling fragmented objects. In:Proceedings of the 2013 Digital Heritage International Congress. Marseille, France:IEEE, 2013. 529-536
[12]	Zhang Y H, Geng G H, Wei X R, Zhang S L, Li S S. A statistical approach for extraction of feature lines from point clouds. Computers & Graphics, 2016, 56(5):31-45 http://www.sciencedirect.com/science/article/pii/S0097849316300097
[13]	Hoppe H, DeRose T, Duchamp T, McDonald J, Stuetzle W. Surface reconstruction from unorganized points. ACM SIGGRAPH Computer Graphics, 1992, 26(2):71-78 doi: 10.1145/142920
[14]	樊少荣. 破碎刚体互补形状匹配与拼接方法研究[博士学位论文], 西北大学, 中国, 2005 Fan Shao-Rong. Research on Fractured Objects Complementary Shape Matching and Aligning[Ph.D. dissertation], Northwest University, China, 2005
[15]	Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(5):550-571 https://www.researchgate.net/publication/295256647_A_Statistical_Approach_for_Extraction_of_Feature_Lines_from_Point_Clouds
[16]	Siddiqi K, Shokoufandeh A, Dickenson S J, Zucker S W. Shock graphs and shape matching. In:Proceedings of the 6th International Conference on Computer Vision. Bombay, India:IEEE, 1998. 222-229
[17]	魏潇然. 三维文物模型边界特征提取[硕士学位论文], 西北大学, 中国, 2011 Wei Xiao-Ran. Extraction of Boundary from Relic Three-Dimensional Model[Master dissertation], Northwest University, China, 2011
[18]	Bai X, Latecki L J, Liu W Y. Skeleton pruning by contour partitioning with discrete curve evolution. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2007, 29(3):449-462 https://www.researchgate.net/publication/6576882_Skeleton_Pruning_by_Contour_Partitioning_with_Discrete_Curve_Evolution
[19]	Arun K S, Huang T S, Blostein S D. Least-squares fitting of two 3-D point sets. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1987, PAMT-9(5):698-700 https://www.researchgate.net/publication/224378053_Least-squares_fitting_of_two_3-D_point_sets_IEEE_T_Pattern_Anal
[20]	Huang T S, Blostein S D, Margerum E A. Least-squares estimation of motion parameters from 3-D point correspondences. In:Proceedings of the 1986 IEEE Conference Computer Vision and Pattern Recognition. Miami Beach, USA:IEEE, 1986. 112-115
[21]	Besl P J, McKay H D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis & Machine Intelligence, 1992, 14(2):239-256 https://www.researchgate.net/publication/220183320_A_Method_for_Registration_of_3-D_Shapes
[22]	李群辉. 基于断裂面匹配的破碎刚体复原研究[博士学位论文], 西北大学, 中国, 2013 Li Qun-Hui. Research on Fractured Slid Recovery Based on Bracture Surfaces Matching[Ph.D. dissertation], Northwest University, China, 2013