The Use of Fuzzy Evaluation and Radical Cut-Off Strategy to Improve Apictorial Puzzle Assembly with Exhaustive Search Algorithm Performance

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

Identyfikatory

DOI

10.12913/22998624/147024

• Języki publikacji: EN

Abstrakty

EN

The paper presents an approach to solving the problem of assembling broken, flat elements using a letter notation of the elements’ contours and checking their matching using linguistic methods. Previous studies with the use of exhaustive search have shown effectiveness in finding possible connections, but they are burdened with a large number of calculations and the time needed to carry them out. In order to accelerate the process of searching for solutions, the possibility of using a fail-fast method of fuzzy assessment of potential combinations of elements was checked, as well as the method of cutting off potential, but not effective connections. The numerical experiment carried out showed a significant reduction in the number of trials and total computation time while maintaining the quality of the potential solutions found.

Słowa kluczowe

EN

fuzzy logic; exhaustive search; reassembling; linguistic methods; puzzle; contour description; fail-fast design; cut-off strategy

• Wydawca: Lublin University of Technology ; Polish Society of Ecological Engineering (PTIE), Branch of PTIE in Lublin
• Czasopismo: Advances in Science and Technology. Research Journal
• Rocznik: 2022
• Tom: Vol. 16, no 2
• Strony: 179--187
• Opis fizyczny: Bibliogr. 23 poz., fig., tab.

Twórcy

autor

Skulimowski Stanisław

• Department of Computer Science, Faculty of Electrical Engineering and Computer Science, Lublin University of Technology, Nadbystrzycka 36B, 20-618 Lublin, Poland

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

autor

Montusiewicz Jerzy

• Department of Computer Science, Faculty of Electrical Engineering and Computer Science, Lublin University of Technology, Nadbystrzycka 36B, 20-618 Lublin, Poland

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

autor

Badurowicz Marcin

• Department of Computer Science, Faculty of Electrical Engineering and Computer Science, Lublin University of Technology, Nadbystrzycka 36B, 20-618 Lublin, Poland

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

Bibliografia

• 1. Demaine E.D., Demaine M.L. Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs Comb. 2007; 23(S1): 195–208. http://dx.doi.org/10.1007/s00373-007-0713-4.
• 2. Freeman H., Garder L. Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE trans electron comput. 1964; EC-13(2): 118–127. http://dx.doi.org/10.1109/pgec.1964.263781.
• 3. Rasheed N.A., Nordin M.J. A survey of classification and reconstruction methods for the 2D archaeological objects. 2015 International Symposium on Technology Management and Emerging Technologies (ISTMET), 2015, 142–147. http://dx.doi.org/10.1109/ISTMET.2015.7359018.
• 4. Kong W., Kimia B.B. On solving 2D and 3D puzzles using curve matching. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition CVPR 2001. IEEE Comput. Soc; 2005.
• 5. Willis A.R. Computational Analysis of Archaeological Ceramic Vessels and Their Fragments. In: Lukac R, editor. Digital Imaging for Cultural Heritage Preservation. Boca Raton, FL: CRC Press; 2011, 323–252.
• 6. Zhou M., Geng G., Wu Z., Zheng X., Shui W., et al. A System for Reassembly of fragment Objects and Computer Aided Restoration of Cultural Relics. Virtual Retrospect 2007, Robert Vergnieux, Pessac, France 2007, 21-27.
• 7. Andreadis A., Papaioannou G., Mavridis P. Generalized digital reassembly using geometric registration. In: 2015 Digital Heritage. IEEE 2015.
• 8. Eureka!, 3 compass games that teach kids to use a compass [Internet]. Eurekacamping.com. [cited 2022 Jan 22]. https://www.eurekacamping.com/blog/article/3-compass-games-teach-kids-use-compass.
• 9. Freeman D. A corner-finding algorithm for chain-coded curves. IEEE Trans Comput. 1977; C26(3): 297–303. http://dx.doi.org/10.1109/tc.1977.1674825.
• 10. Montusiewicz J., Skulimowski S. A search method for reassembling the elements of a broken 2D object. Adv Sci Technol Res J. 2020; 14(3): 49–56. http://dx.doi.org/10.12913/22998624/122570.
• 11. Grabowik C., Kalinowski K., Ćwikła G., Gwiazda A., Monica Z. The use of chain codes to describe the structure and identify structural elementary objects. In: Innovations in management and production engineering. Opole, Poland: Publishing House of the Polish Production Management Society. 2017; 180–90.
• 12. Karczmarek P., Kiersztyn A., Pedrycz W., Dolecki M. An application of chain code-based local descriptor and its extension to face recognition. Pattern Recognit, 2017; 65: 26–34. http://dx.doi.org/10.1016/j.patcog.2016.12.008.
• 13. Buschmann T., Bystrykh L.V. Levenshtein error-correcting barcodes for multiplexed DNA sequencing. BMC Bioinformatics. 2013; 14(1): 272. http://dx.doi.org/10.1186/1471-2105-14-272.
• 14. Skulimowski S., Montusiewicz J. Optimization methods of searching algorithms for 2D elements matching. In: Katarzyna Falkowicz MS, editor. Modern Computational Methods and their Applications in Engineering Science. Lublin, Publishing house of the Lublin University of Technology; 2020; 35–47.
• 15. Bai Y., Wang D. Fundamentals of fuzzy logic control — fuzzy sets, fuzzy rules and defuzzifications. In: Advances in Industrial Control. London: Springer London; 2007; 17–36.
• 16. Korytkowski M., Scherer R., Szajerman D., Polap D., Wozniak M. Efficient visual classification by fuzzy rules. In: 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). IEEE 2020.
• 17. Czerwinski D., Kiersztyn A., Lopucki R., Karczmarek P., Kitowski I., Zbyryt A. An application of fuzzy C-means, fuzzy cognitive maps, and fuzzy rules to forecasting first arrival date of avian spring migrants. In: 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). IEEE 2020.
• 18. Chakrabarti T., Saha S., Sinha D. DNA multiple sequence alignment by a hidden Markov model and fuzzy Levenshtein distance based genetic algorithm. Int J Comput Appl. 2013; 73(16): 26–30. http://dx.doi.org/10.5120/12826-0206.
• 19. Mamdani E.H., Assilian S. An experiment in linguistic synthesis with a fuzzy logic controller. Int J Man Mach Stud. 1975; 7(1): 1–13. http://dx.doi.org/10.1016/s0020-7373(75)80002-2.
• 20. Zhang Y., Ishibuchi H., Wang S. Deep Takagi–Sugeno–Kang fuzzy classifier with shared linguistic fuzzy rules. IEEE Trans Fuzzy Syst. 2018; 26(3): 1535–49. http://dx.doi.org/10.1109/tfuzz.2017.2729507.
• 21. Ekuse Eborn S.L. Fail-fast in the Design Process of an Interactive Voice Response System. Lund, Swedish: The Department of Design Sciences Faculty of Engineering, Lund University Box. 118, 221 00 Lund; 2019.
• 22. Naina Gupta D.C. A fail-fast mechanism for authenticated encryption schemas. New Delhi: Indraprastha Institute of Information Technology; 2016.
• 23. Jin F., Cao M., Liu J., Martínez L., Chen H. Consistency and trust relationship-driven social network group decision-making method with probabilistic linguistic information. Appl Soft Comput [Internet]. 2021; 103(107170): 107170. http://dx.doi.org/10.1016/j.asoc.2021.107170.