2.624

2020影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

张雨禾, 耿国华, 魏潇然, 张靖, 周明全. 基于形状骨架图匹配的文物碎片自动重组方法. 自动化学报, 2017, 43(4): 622-633. doi: 10.16383/j.aas.2017.c160336
引用本文: 张雨禾, 耿国华, 魏潇然, 张靖, 周明全. 基于形状骨架图匹配的文物碎片自动重组方法. 自动化学报, 2017, 43(4): 622-633. doi: 10.16383/j.aas.2017.c160336
ZHANG Yu-He, GENG Guo-Hua, WEI Xiao-Ran, ZHANG Jing, ZHOU Ming-Quan. Reassembly of Fractured Fragments Based on Skeleton Graphs Matching. ACTA AUTOMATICA SINICA, 2017, 43(4): 622-633. doi: 10.16383/j.aas.2017.c160336
Citation: ZHANG Yu-He, GENG Guo-Hua, WEI Xiao-Ran, ZHANG Jing, ZHOU Ming-Quan. Reassembly of Fractured Fragments Based on Skeleton Graphs Matching. ACTA AUTOMATICA SINICA, 2017, 43(4): 622-633. doi: 10.16383/j.aas.2017.c160336

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

doi: 10.16383/j.aas.2017.c160336
基金项目: 

高等学校博士学科点专项科研基金 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

Reassembly of Fractured Fragments Based on Skeleton Graphs Matching

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
  • 摘要: 为了有效解决文物碎片自动重组中由于断裂部位受损造成几何信息丢失,采用传统几何驱动方法容易失效的问题,本文提出一种基于形状骨架图匹配的文物碎片自动重组方法,将碎片匹配问题转化为碎片表面纹饰中非完整纹元的互补匹配问题.首先,通过提取文物碎片表面特征线得到碎片表面的纹饰信息;然后根据完整纹元的特征确定非完整纹元互补匹配的约束条件,采用视觉骨架剪枝的方法提取完全位于断裂部位的非完整纹元的形状骨架图,基于形状骨架图语法及匹配约束条件判定非完整纹元是否互补匹配;接着,将碎片上非完整纹元的顺序作为上层约束条件,采用基于带剪枝深度优先的搜索方法搜索匹配碎片;最后,以邻接碎片上非完整纹元间公共弦的端点作为邻接约束点,采用最小二乘法计算刚体变换参数得到碎片的初始位置,并采用迭代最近点方法将邻接碎片精确对齐.实验结果表明,该方法能够有效解决断裂部位存在缺损文物碎片的自动重组问题.
  • 图  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
  • [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
  • 加载中
图(15) / 表(2)
计量
  • 文章访问数:  1864
  • HTML全文浏览量:  346
  • PDF下载量:  6451
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-04-15
  • 录用日期:  2016-08-02
  • 刊出日期:  2017-04-01

目录

    /

    返回文章
    返回