Quadratic Matching Algorithm of Ancient Ceramic Fragments Based on Concavity-Convexity and Steering Angle

doi:10.19678/j.issn.1000-3428.0068313

Abstract

Abstract:

Fragment splicing is the key work in ancient ceramic repair. To address the problems of the random shapes, large number, weak surface textures, and local defects of ancient ceramic fragments (which result in a low accuracy and long matching time of the algorithm), this paper proposes a quadratic matching algorithm of ancient ceramic fragments based on concavity-convexity and steering angle. On the basis of extracting the contour curves of ancient ceramic fragments, the algorithm realizes the two-pair matching of fragments by combining coarse matching and fine matching. First coarse matching: The algorithm approximates the fragment profile curve through the polygon first to reduce the complexity of the profile. Then, it extracts the vertex concavity-convexity and vertex steering angle of the polygon to construct the first contour feature set. Finally, it uses the initial matching algorithm of the dual-modal features of concave-convex complementarity and traversal vertex alignment to determine the approximate matching segment, and the coarse matching point set is obtained. Quadratic fine matching: First, the algorithm selects any two adjacent points in the coarse matching points selected randomly to extract the fragment contour fragment. This reduces the number of contour points and improves the efficiency of the algorithm. Then, it calculates the contour steering angle of the contour fragment to extract the secondary profile feature set. Finally, it uses the quadratic matching based on Particle Swarm Optimization (PSO) to search for the exact matching segment and obtain the fine matching point set. The experimental results reveal that the algorithm displays a good stitching effect and strong robustness for the splicing of two-dimensional ancient ceramic fragments. The splicing error is less than 2%, and the running time efficiency is high(8%-20% higher than that of the existing algorithm).

Key words: fragment splicing, quadratic matching algorithm, contour extraction, concavity-convexity, steering angle, Particle Swarm Optimization(PSO)

摘要：

碎片拼接是古陶瓷修复的关键工作, 针对古陶瓷碎片形状随机、数量大、表面纹理弱且存在局部缺损而导致算法的精度较低、匹配时间较长等问题, 提出一种基于凹凸性和转向角的古陶瓷碎片二次配算法。在提取古陶瓷碎片轮廓曲线的基础上, 通过先后使用粗匹配和细匹配的二次匹配组合实现碎片的两两精确匹配。一次粗匹配先通过多边形逼近碎片轮廓曲线, 以降低轮廓的复杂性, 再提取多边形的顶点凹凸性和顶点转向角构建一次轮廓特征集合, 最后利用凹凸互补性和遍历顶点对齐的双模态特征初次匹配算法来寻找大致匹配段, 并得到粗匹配点集。二次细匹配先随机选取粗匹配点集中的任意相邻两点点对来提取碎片轮廓片段, 以减少轮廓点数量并提高算法效率, 再计算轮廓片段的轮廓转向角以提取二次轮廓特征集合, 最后利用基于粒子群优化的二次匹配来搜索精确匹配段, 并得到细匹配点集。实验结果表明, 该算法对二维古陶瓷碎片的拼接效果较好, 且具有较强的鲁棒性, 拼接误差不超过2%, 运行时间效率相比已有算法提高了8%~20%。

关键词: 碎片拼接, 二次匹配算法, 轮廓提取, 凹凸性, 转向角, 粒子群优化

LIU Penghuan, ZHOU Qiang, WANG Ying, ZHU Jianfeng, LUO Hongjie, WANG Lu, WANG Tian. Quadratic Matching Algorithm of Ancient Ceramic Fragments Based on Concavity-Convexity and Steering Angle[J]. Computer Engineering, 2024, 50(9): 356-366.

刘鹏欢, 周强, 王莹, 朱建锋, 罗宏杰, 王露, 王甜. 基于凹凸性和转向角的古陶瓷碎片二次匹配算法[J]. 计算机工程, 2024, 50(9): 356-366.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0068313

https://www.ecice06.com/EN/Y2024/V50/I9/356

Figures/Tables 17

Fig.1 Overall structure of the algorithm in this paper

Fig.2 The effect diagram of contour extraction and contour refinement after pretreatment

Fig.3 Once (coarse) matching algorithm procedure

Fig.4 Schematic diagram of vertex concavity-convexity and vertex steering angle

Fig.5 Schematic diagram of vertex concavity-convexity matching

Fig.6 Quadratic (fine) matching algorithm procedure

Fig.7 Procedure of ancient ceramic fragment quadratic matching algorithm based on PSO algorithm

Fig.8 Effect of fragment matching based on measurement

Fig.9 Image of ancient ceramic fragments used in pairwise splicing experiment

Fig.10 Image of damaged ancient ceramic fragments used in the robustness test experiment

Fig.11 Experimental results of rough matching algorithm

Fig.12 Experimental results of fine matching algorithm

Fig.13 Experimental results of pairwise splicing of fragments

Fig.14 Robustness test experimental results(Experiment 5)

Fig.15 Splicing effect of experiment 4

References 27

1	侯妙乐, 赵思仲, 杨溯, 等. 文物三维模型虚拟修复研究进展、挑战与发展趋势. 遗产与保护研究, 2018, 3 (10): 1- 10. URL
	HOU M L, ZHAO S Z, YANG S, et al. Research progress, challenges and development trends of virtual restoration of 3D model of cultural relics. Research on Heritages and Preservation, 2018, 3 (10): 1- 10. URL
2	ZHENG S Y, HUANG R Y, WANG G Z, et al. Reassembling 3D thin fragments of unknown geometry in cultural heritage. Photogrammetrie Fernerkundung Geoinformation, 2015, 3, 215- 230.
3	王飘, 耿国华, 张雨禾. 基于表面纹理特征定义的碎片拼接方法. 激光与光电子学进展, 2018, 55 (8): 081012. URL
	WANG P, GENG G H, ZHANG Y H. Fragment splicing method based on surface texture characteristic. Laser & Optoelectronics Progress, 2018, 55 (8): 081012. URL
4	王飘, 耿国华, 杨稳, 等. 结合表面纹理与断裂轮廓的碎片拼接方法. 计算机工程, 2019, 45 (2): 315- 320. URL
	WANG P, GENG G H, YANG W, et al. Fragment splicing method combined with surface texture and fracture contour. Computer Engineering, 2019, 45 (2): 315- 320. URL
5	袁洁, 周明全, 耿国华, 等. 基于轮廓线双向距离场的文物碎片拼接算法. 计算机工程, 2018, 44 (6): 207-212, 218. URL
	YUAN J, ZHOU M Q, GENG G H, et al. Heritage debris splicing algorithm based on contour line two-way distance field. Computer Engineering, 2018, 44 (6): 207-212, 218. URL
6	张雨禾, 耿国华, 魏潇然, 等. 基于形状骨架图匹配的文物碎片自动重组方法. 自动化学报, 2017, 43 (4): 622- 633. URL
	ZHANG Y H, GENG G H, WEI X R, et al. Reassembly of fractured fragments based on skeleton graphs matching. Acta Automatica Sinica, 2017, 43 (4): 622- 633. URL
7	李姗姗, 耿国华, 周明全, 等. 基于表面邻接约束的交互式文物碎片重组. 计算机辅助设计与图形学学报, 2016, 28 (6): 924- 931. URL
	LI S S, GENG G H, ZHOU M Q, et al. Interactive reassembly of fractured fragments based on surface adjacency constraint. Journal of Computer-Aided Design & Computer Graphics, 2016, 28 (6): 924- 931. URL
8	高宏娟, 耿国华, 王飘. 基于关键点特征描述子的三维文物碎片重组. 计算机辅助设计与图形学学报, 2019, 31 (3): 393- 399.
	GAO H J, GENG G H, WANG P. 3D archaeological fragment reassembly based on feature descriptors of key points. Journal of Computer-Aided Design & Computer Graphics, 2019, 31 (3): 393- 399.
9	赵夫群, 耿国华. 基于特征点的秦俑断裂面匹配方法. 激光与光电子学进展, 2018, 55 (4): 041005. URL
	ZHAO F Q, GENG G H. Fracture surface matching method for terracotta based on feature points. Laser & Optoelectronics Progress, 2018, 55 (4): 041005. URL
10	赵夫群, 耿国华. 基于特征区域划分的文物碎片自动匹配算法. 电子学报, 2022, 50 (6): 1436- 1443. URL
	ZHAO F Q, GENG G H. Automatic matching algorithm of cultural relic fragments based on feature region division. Acta Electronica Sinica, 2022, 50 (6): 1436- 1443. URL
11	耿国华, 张鹏飞, 刘雨萌, 等. 基于断裂面邻域特征的文物碎片拼接. 光学精密工程, 2021, 29 (5): 1169- 1179. URL
	GENG G H, ZHANG P F, LIU Y M, et al. Reassembly method of cultural relic fragments based on the neighborhood characteristics of fracture surface. Optics and Precision Engineering, 2021, 29 (5): 1169- 1179. URL
12	刘晓宁, 狄宏璋, 杨稳, 等. 基于SURF特征描述符和杰卡德距离的文物碎片拼接. 光学精密工程, 2020, 28 (4): 963- 972. URL
	LIU X N, DI H Z, YANG W, et al. Mosaic of cultural relics fragments based on SURF feature extraction descriptor and Jaccard distance. Optics and Precision Engineering, 2020, 28 (4): 963- 972. URL
13	袁洁, 周明全, 耿国华, 等. 基于Morse-Smale拓扑特征的文物碎片拼接算法. 自动化学报, 2018, 44 (8): 1486- 1495. URL
	YUAN J, ZHOU M Q, GENG G H, et al. Automatic reassembly of fractured fragments using morse topological features. Acta Automatica Sinica, 2018, 44 (8): 1486- 1495. URL
14	LI Q H, ZHOU M Q, GENG G H. Pairwise matching of 3D fragments[C]//Proceedings of International Conference on Information Management, Innovation Management and Industrial Engineering. Washington D. C., USA: IEEE Press, 2012: 479-482.
15	LI Q H, GENG G H, ZHOU M Q. Pairwise matching for 3D fragment reassembly based on boundary curves and concave-convex patches. IEEE Access, 2020, 8, 6153- 6161. doi: 10.1109/ACCESS.2019.2961391
16	王江辉, 吴小俊. 基于形状轮廓特征的金字塔匹配算法. 计算机工程与应用, 2019, 55 (1): 191- 195. URL
	WANG J H, WU X J. 2D shape matching based on pyramid matching with contour features. Computer Engineering and Applications, 2019, 55 (1): 191- 195. URL
17	ZHANG L G, SUN J G, SONG H T, et al. Normal direction local binary pattern for fragment reconstruction[C]//Proceedings of IEEE International Conference on Multimedia and Expo. Washington D. C., USA: IEEE Press, 2017: 481-486.
18	DERECH N, TAL A, SHIMSHONI I. Solving archaeological puzzles. Pattern Recognition, 2021, 119, 108065. doi: 10.1016/j.patcog.2021.108065
19	王晓辉, 王丽勇, 傅思勇. 基于轮廓特征的文物碎片自动拼接方法. 赤峰学院学报(自然科学版), 2021, 37 (10): 35- 41. URL
	WANG X H, WANG L Y, FU S Y. Automatic splicing method of cultural relics fragments based on contour features. Journal of Chifeng University (Natural Science Edition), 2021, 37 (10): 35- 41. URL
20	尚冲, 曹利钢, 冯浩, 等. 基于形状度量的陶瓷碎片二维拼接算法研究. 陶瓷学报, 2021, 42 (2): 320- 324. URL
	SHANG C, CAO L G, FENG H, et al. Two-dimensional stitching algorithm of potsherd based on shape constraint. Journal of Ceramics, 2021, 42 (2): 320- 324. URL
21	ZHANG T Y, SUEN C Y. A fast parallel algorithm for thinning digital patterns. Communications of the ACM, 1984, 27 (3): 236- 239. doi: 10.1145/357994.358023
22	DOUGLAS D H, PEUCKER T. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 1973, 10 (2): 112- 122. doi: 10.3138/FM57-6770-U75U-7727
23	陈亚婷, 严泰来, 朱德海. 基于辛普森面积的多边形凹凸性识别算法. 地理与地理信息科学, 2010, 26 (6): 28-30, 55. URL
	CHEN Y T, YAN T L, ZHU D H. An algorithm for identifying convex-concave vertices of polygon based on Simpson formula. Geography and Geo-Information Science, 2010, 26 (6): 28-30, 55. URL
24	ZHU L J, ZHOU Z T, HU D W. Globally consistent reconstruction of ripped-up documents. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30 (1): 1- 13. doi: 10.1109/TPAMI.2007.1163
25	SHAMI T M, EL-SALEH A A, ALSWAITTI M, et al. Particle swarm optimization: a comprehensive survey. IEEE Access, 2022, 10, 10031- 10061. doi: 10.1109/ACCESS.2022.3142859
26	KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of International Conference on Neural Networks. Washington D. C., USA: IEEE Press, 1995: 1942-1948.
27	王毅, 李晓梦, 耿国华, 等. 基于直觉模糊熵的混合粒子群优化算法. 电子学报, 2021, 49 (12): 2381- 2389. URL
	WANG Y, LI X M, GENG G H, et al. Hybrid particle swarm optimization algorithm based on intuitionistic fuzzy entropy. Acta Electronica Sinica, 2021, 49 (12): 2381- 2389. URL

[1]	WANG Jingyi, ZHU Yuhan, ZHOU Ruping, LIU Genggeng. X-Architecture Steiner Minimum Tree Algorithm Based on Dynamic Particle Swarm Optimization [J]. Computer Engineering, 2024, 50(9): 226-234.
[2]	ZHOU Chunlei, SONG Jimeng, SHEN Ziqi, YU Han, LEI Jie, LIN Bing. Identifier Data Layout Strategy in Identifier Resolution System of Internet of Data [J]. Computer Engineering, 2024, 50(6): 311-320.
[3]	GAO Jiahao, HU Chuangye, DING Nan, LIU Zhandong. Validity Analysis of Traffic-Flow Data for Combined Driving Style in Intelligent Connected Vehicle [J]. Computer Engineering, 2024, 50(6): 367-376.
[4]	HUANG Junze, WU Wenyuan, LI Yi, SHI Mingquan, WANG Zhengjiang. Discrete Hierarchical Memory Particle Swarm Optimization Algorithm for Dynamic Public Transport [J]. Computer Engineering, 2024, 50(4): 20-30.
[5]	Panfeng ZHANG, Danhua WU, Minggang DONG. Differential Privacy Deep Learning Model Based on Particle Swarm Optimization [J]. Computer Engineering, 2023, 49(9): 144-157.
[6]	SUN Yangwei, QI Yong. Intrusion Detection Method for In-Vehicle CAN Based on Cluster Mixed Sampling and PSO-Stacking [J]. Computer Engineering, 2023, 49(1): 138-145.
[7]	MIAO Yisheng, ZHAO Chunjiang, WU Huarui. Farmland WSN Routing Optimization Method Based on Improved Particle Swarm Optimization [J]. Computer Engineering, 2022, 48(10): 218-223.
[8]	WANG Gaiyun, LU Jiazhuo, JIAO Ao, GUO Zhichao, ZHANG Qi. RSSI Centroid Location Algorithm Optimized by Chaotic Particle Swarm and Chicken Swarm [J]. Computer Engineering, 2021, 47(6): 197-202.
[9]	GAO Hanghang, WANG Xiang, ZHAO Shanghong, PENG Cong. Controller Reliability Deployment Method for Aeronautical Information Network [J]. Computer Engineering, 2020, 46(6): 221-229.
[10]	ZHANG Rui, CHEN Hongwei. Intrusion Detection Based on Feature Optimization and SVPSO for Industrial Control System [J]. Computer Engineering, 2020, 46(4): 19-25.
[11]	DING Chengjun, LIU Qiang. Node Deployment Strategy Based on Spatial Weight and Fuzzy Perception [J]. Computer Engineering, 2019, 45(7): 140-146,153.
[12]	ZOU Maorong,FU Ming,XIONG Bing. Deployment Model of SDN Controllers Based on Time Delay and Load [J]. Computer Engineering, 2019, 45(4): 30-35.
[13]	LIN Yupei,CHEN Lanlan,ZOU Junzhong. Application of Hybrid Feature Selection Algorithm Based on Particle Swarm Optimization in Fatigue Driving [J]. Computer Engineering, 2019, 45(2): 278-283.
[14]	WANG Piao,GENG Guohua,YANG Wen,REN Jian. Fragment Splicing Method Combined with Surface Texture and Fracture Contour [J]. Computer Engineering, 2019, 45(2): 315-320.
[15]	YE Li, WU Chunming, QIANG Baohua, XIE Wu. Multi-Criteria Collaborative Filtering Based on Matrix Filling and Improved PSO Algorithm [J]. Computer Engineering, 2019, 45(12): 176-181,200.

Please choose a citation manager

Content to export