ENHANCING THE EFFICIENCY OF THE LEVENSHTEIN DISTANCE BASED HEURISTIC METHOD OF ARRANGING 2D APICTORIAL ELEMENTS FOR INDUSTRIAL APPLICATIONS

Stanisław SKULIMOWSKI; Jerzy MONTUSIEWICZ; Marcin BADUROWICZ

doi:10.35784/acs-2023-31

Open full text

PDF

Published: Dec 31, 2023

DOI: https://doi.org/10.35784/acs-2023-31

DOI

https://doi.org/10.35784/acs-2023-31

Authors

Stanisław SKULIMOWSKI

s.skulimowski@pollub.pl

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

Jerzy MONTUSIEWICZ

j.montusiewicz@pollub.pl

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

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

Marcin BADUROWICZ

m.badurowicz@pollub.pl

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

Abstract

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.

References

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 DOI: https://doi.org/10.1109/DigitalHeritage.2015.7419572

Brown, B. J. (2008). Registration and matching of large geometric datasets for cultural heritage applications. Princeton University.

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 DOI: https://doi.org/10.1109/T-C.1973.223596

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 DOI: https://doi.org/10.1007/s00373-007-0713-4

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 DOI: https://doi.org/10.1109/PGEC.1964.263781

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 DOI: https://doi.org/10.12913/22998624/122570

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 DOI: https://doi.org/10.1016/j.culher.2012.02.017

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 DOI: https://doi.org/10.1109/38.909015

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 DOI: https://doi.org/10.3844/jcssp.2014.2339.2348

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.

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 DOI: https://doi.org/10.1109/ISTMET.2015.7359018

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 DOI: https://doi.org/10.1016/j.jksuci.2018.09.019

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.

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 DOI: https://doi.org/10.12913/22998624/147024

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. DOI: https://doi.org/10.1201/b11049-13

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 DOI: https://doi.org/10.1145/2597178

SKULIMOWSKI, S., MONTUSIEWICZ, J., & BADUROWICZ, M. (2023). ENHANCING THE EFFICIENCY OF THE LEVENSHTEIN DISTANCE BASED HEURISTIC METHOD OF ARRANGING 2D APICTORIAL ELEMENTS FOR INDUSTRIAL APPLICATIONS. Applied Computer Science, 19(4), 1–13. https://doi.org/10.35784/acs-2023-31

Article Sidebar

Main Article Content

DOI

Authors

Abstract

References

Article Details

License