Enhancing the efficiency of the Levenshtein distance-based heuristic method of arranging 2D apictorial elements for industrial applications

• Autorzy: Skulimowski Stanisław , Montusiewicz Jerzy , Badurowicz Marcin

Identyfikatory

DOI

10.35784/acs-2023-31

• Języki publikacji: EN

Abstrakty

EN

The article addresses the challenge of reconstructing 2D broken pictorial objects by automating the search for matching elements, which is particularly relevant in fields like archaeology and forensic science. The authors propose a method to match such elements and streamline the search process by detecting and filtering out low quality matches. The study delves into optimizing the search process in terms of duration and assembly quality. It examines factors like comparison window length, Levenshtein measure margin, and number of variants to check, using theoretical calculations and experiments on synthetic elements. The experimental results demonstrate enhanced method effectiveness, yielding more useful solutions and significantly reducing the complexity of element comparisons by up to 100 times in extreme cases.

Słowa kluczowe

EN

Levenshtein measure; apictorial; assembly; cut-off; fuzzy logic

• Wydawca: Polskie Towarzystwo Promocji Wiedzy ; Lublin University of Technology
• Czasopismo: Applied Computer Science
• Rocznik: 2023
• Tom: Vol. 19, no 4
• Strony: 1--13
• Opis fizyczny: Bibliogr. 16 poz., fig., tab.

Twórcy

autor

Skulimowski Stanisław

• Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science, Poland

• https://orcid.org/0000-0002-9049-9516

autor

Montusiewicz Jerzy

• Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science, Poland

• https://orcid.org/0000-0002-8571-3354

autor

Badurowicz Marcin

• Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science, Poland

• https://orcid.org/0000-0003-2249-4219

Bibliografia

• [1] Andreadis, A., Papaioannou, G., & Mavridis, P. (2015). Generalized digital reassembly using geometric registration. 2015 Digital Heritage International Congress (pp. 549–556). IEEE. https://doi.org/10.1109/DigitalHeritage.2015.7419572
• [2] Brown, B. J. (2008). Registration and matching of large geometric datasets for cultural heritage applications. Princeton University.
• [3] Chang, S. K., & Chow, C. K. (1973). The Reconstruction of three-dimensional objects from two orthogonal projections and its application to cardiac cineangiography. IEEE Transactions on Computers, C–22(1), 18–28. https://doi.org/10.1109/T-C.1973.223596
• [4] Demaine, E. D., & Demaine, M. L. (2007). Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs and Combinatorics, 23, 195–208. https://doi.org/10.1007/s00373-007-0713-4
• [5] Freeman, H., & Garder, L. (1964). Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE Transactions on Electronic Computers, EC-13(2), 118–127. https://doi.org/10.1109/PGEC.1964.263781
• [6] Montusiewicz, J., & Skulimowski, S. (2020). A search method for reassembling the elements of a broken 2D object. Advances in Science and Technology Research Journal, 14(3), 49–56. https://doi.org/10.12913/22998624/122570
• [7] Oxholm, G., & Nishino, K. (2013). A flexible approach to reassembling thin artifacts of unknown geometry. Journal of Cultural Heritage, 14(1), 51–61. https://doi.org/10.1016/j.culher.2012.02.017
• [8] Papaioannou, G., Karabassi, E. A., & Theoharis, T. (2001). Virtual Archaeologist: Assembling the past. IEEE Computer Graphics and Applications, 21(2), 53–59. https://doi.org/10.1109/38.909015
• [9] Rasheed, N. A., & Nordin, M. J. (2014). A polynomial function in the automatic reconstruction of fragmented objects. Journal of Computer Science, 10(11), 2339–2348. https://doi.org/10.3844/jcssp.2014.2339.2348
• [10] Rasheed, N. A., & Nordin, M. J. (2015a). A Survey of computer methods in reconstruction of 3D archaeological pottery objects. International Journal of Advanced Research, 3(3), 712-714.
• [11] Rasheed, N. A., & Nordin, M. J. (2015b). A survey of classification and reconstruction methods for the 2D archaeological objects. 2nd International Symposium on Technology Management and Emerging Technologies (ISTMET) (pp. 142–147). IEEE. https://doi.org/10.1109/ISTMET.2015.7359018
• [12] Rasheed, N. A., & Nordin, M. J. (2020). Classification and reconstruction algorithms for the archaeological fragments. Journal of King Saud University - Computer and Information Sciences, 32(8), 883–894. https://doi.org/10.1016/j.jksuci.2018.09.019
• [13] Skulimowski, S., & Montusiewicz, J. (2020). Optimization methods of searching algorithms for 2D elements matching. Modern Computational Methods and Their Applications in Engineering Science (pp. 35–47). Wydawnictwo Politechniki Lubelskiej.
• [14] Skulimowski, S., Montusiewicz, J., & Badurowicz, M. (2022). The use of fuzzy evaluation and radical cut-off strategy to improve apictorial puzzle assembly with exhaustive search algorithm performance. Advances in Science and Technology Research Journal, 16(2), 179–187. https://doi.org/10.12913/22998624/147024
• [15] Stanco, F., Battiato, S., & Gallo, G. (2018). Digital reconstruction and mosaicing of cultural artifacts. In F. Stanco, S. Battiato, & G. Gallo (Eds.), Digital Imaging for Cultural Heritage Preservation (pp. 353–384). CRC Press.
• [16] Vendrell-Vidal, E., & Sánchez-Belenguer, C. (2014). A discrete approach for pairwise matching of archaeological fragments. Journal on Computing and Cultural Heritage, 7(3), 15. https://doi.org/10.1145/2597178