ENHANCING THE EFFICIENCY OF THE LEVENSHTEIN DISTANCE BASED HEURISTIC METHOD OF ARRANGING 2D APICTORIAL ELEMENTS FOR INDUSTRIAL APPLICATIONS
Stanisław SKULIMOWSKI
s.skulimowski@pollub.plLublin 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.
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
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
Authors
Stanisław SKULIMOWSKIs.skulimowski@pollub.pl
Lublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science Poland
Authors
Jerzy MONTUSIEWICZLublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science Poland
https://orcid.org/0000-0002-8571-3354
Authors
Marcin BADUROWICZLublin University of Technology, Faculty of Electrical Engineering and Computer Science, Department of Computer Science Poland
Statistics
Abstract views: 154PDF downloads: 78
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.
Most read articles by the same author(s)
- Marcin Badurowicz, Sebastian Łagowski, USAGE OF IOT EDGE APPROACH FOR ROAD QUALITY ANALYSIS , Applied Computer Science: Vol. 19 No. 1 (2023)
- Marcin BADUROWICZ, DETECTION OF SOURCE CODE IN INTERNET TEXTS USING AUTOMATICALLY GENERATED MACHINE LEARNING MODELS , Applied Computer Science: Vol. 18 No. 1 (2022)
