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

Stanisław SKULIMOWSKI

s.skulimowski@pollub.pl
Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science (Poland)

Jerzy MONTUSIEWICZ


Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science (Poland)
https://orcid.org/0000-0002-8571-3354

Marcin BADUROWICZ


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

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.



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   Google Scholar

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

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   Google Scholar

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   Google Scholar

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   Google Scholar

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   Google Scholar

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   Google Scholar

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   Google Scholar

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   Google Scholar

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.
  Google Scholar

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   Google Scholar

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   Google Scholar

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.
  Google Scholar

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   Google Scholar

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   Google Scholar

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   Google Scholar

Download


Published
2023-12-31

Cited by

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

Authors

Stanisław SKULIMOWSKI 
s.skulimowski@pollub.pl
Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science Poland

Authors

Jerzy MONTUSIEWICZ 

Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science Poland
https://orcid.org/0000-0002-8571-3354

Authors

Marcin BADUROWICZ 

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

Statistics

Abstract views: 148
PDF downloads: 72


License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

All articles published in Applied Computer Science are open-access and distributed under the terms of the Creative Commons Attribution 4.0 International License.