研究生: |
Syifa Fauzia Fauzia, Syifa |
---|---|
論文名稱: |
Biomimicry of Human Pattern Recognition by Puzzle Solving Simulation Biomimicry of Human Pattern Recognition by Puzzle Solving Simulation |
指導教授: |
陳啟明
Chen, Chi-Ming |
口試委員: |
曾宇鳳
Tseng, Yufeng Jane 王科植 Wang, Ko-Chih 陳啟明 Chen, Chi-Ming |
口試日期: | 2023/07/17 |
學位類別: |
碩士 Master |
系所名稱: |
物理學系 Department of Physics |
論文出版年: | 2023 |
畢業學年度: | 111 |
語文別: | 英文 |
論文頁數: | 70 |
英文關鍵詞: | Puzzle solving, Algorithm, Pattern recognition, R-squared, Spearman's correlation |
DOI URL: | http://doi.org/10.6345/NTNU202301388 |
論文種類: | 學術論文 |
相關次數: | 點閱:106 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
In this work, our purpose is to imitate human behavior in pattern recognition by puzzle solving simulation with an automatic algorithm based on statistic database of human solver. Based on the empirical database of puzzle solving of 972 human solvers, it has been observed that human solvers tend to pick a piece as the nucleation site and then enlarge the site by finding out corresponding piece of its edges with similar color pattern. In this study, an automated algorithm has been developed based on the empirical data from the previous research. The algorithm incorporates specific parameters that are crucial for puzzle solving, including the number of sections for each puzzle piece, the resemblance threshold, alpha, the percentage of ABC, and q values. The objective of the study is to evaluate the simulation performance by comparing it with the empirical data for different parameter settings. Our simulation shows that by setting the Number of sections into 6×6, Resemblance threshold 0.65, Alpha 0.55, q values 5, and Percentage of ABC {90,8,2}, our simulation that working based on color does mimics human solvers with strong effect size r^2 0.72 for 6 Pictures that dominates by colors. At the second measurement, we found that the simulation with number of sections 6×6, Resemblance threshold 0.65, Alpha 0.55, q values 1, and Percentage of ABC {94,4,2} showcased the best performance, with R-squared value of 0.82 and a Spearman's correlation coefficient of 0.85 for the set of 8 pictures. Similarly, for the set of 6 pictures, it exhibited an R-squared value of 0.87 and a Spearman's correlation coefficient of 0.94.
[1] T. . S. Cho, S. Avidan and W. T. Freeman, "A probabilistic image jigsaw puzzle solver," Conference on Computer Vision and Pattern Recognition (CVPR), pp. 183-190, 2010.
[2] D. Pomeranz, M. Shemesh and O. Ben-Shahar, "A fully automated greedy square jigsaw puzzle solver," in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2011.
[3] N. Alajlan, "Solving Square Jigsaw Puzzles Using Dynamic Programming and the Hungarian Procedure," American Journal of Applied Sciences, vol. 6, no. 11, pp. 1941-1947, 2009.
[4] B. . J. Brown, C. Toler-Franklin, D. Nehab, M. Burns, D. Dobkin, A. Vlachopoulos, C. Doumas, S. Rusinkiewicz and T. Weyrich, "A System for High-Volume Acquisition and Matching of Fresco Fragments: Reassembling Theran Wall Paintings," ACM Transactions on Graphics,, vol. 27, no. 3, pp. 1-9, 2008.
[5] H.-Y. Lin and W.-C. Fan-Chiang, "Reconstruction of shredded document based on image feature matching," Expert Systems with Applications, vol. 39, p. 3324–3332, 2012.
[6] W. Marande and G. Burger, "Mitochondrial DNA as a Genomic Jigsaw Puzzle," Science, vol. 318, no. 5849, pp. 415 - 415, 2007.
[7] N. Payal and R. K. Challa, "AJIGJAX: A Hybrid Image Based Model for Captcha/CaRP," in Uttar Pradesh Section International Conference on Electrical, Computer and Electronics Engineering (UPCON), Varanasi, India, 2016.
[8] S. Markaki and C. Panagiotakis, "Jigsaw puzzle solving techniques and applications: a survey," The Visual Computer, 2022.
[9] X. Yang, N. Adluru and L. J. Latecki, "Particle Filter with State Permutations for Solving Image Jigsaw Puzzles," in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2011.
[10] A. C. Gallagher, "Jigsaw Puzzles with Pieces of Unknown Orientation," in Conference on Computer Vision and Pattern Recognition, 2012.
[11] H. Freeman and L. Garder, "Apictorial Jigsaw Puzzles: The Computer Solution of a Problem in Pattern Recognition," IEEE Transactions on Electronic Computers, Vols. EC-13 , no. 2, pp. 118 - 127, 1964.
[12] W. Kong and B. B. Kimia, "On Solving 2D and 3D Puzzles Using Curve Matching," in Computer Society Conference on Computer Vision and Pattern Recognition, 2001.
[13] D. Goldberg, C. Malon and M. Bern, "A global approach to automatic solution of jigsaw puzzles," in symposium on Computational geometry, 2002.
[14] D. A. Kosiba, P. M. Devaux, S. Balasubramanian, T. L. Gandhi and R. Kasturi, "An Automatic Jigsaw Puzzle Solver," in International Conference on Pattern Recognition, Jerusalem, 1994.
[15] M. G. Chung, M. M. Fleck and D. A. Forsyth, "Jigsaw Puzzle Solver Using Shape and Color," in International Conference on Signal Processing Proceedings (ICSP), Beijing, 1998.
[16] R. Z. Hsu, Exploration of Brain's Information Processing Ability--Taking Puzzle Process as an Example (大腦處理資訊能力之探索--以拼圖歷程為例 ; a Thesis), Taipei: NTNU, 2005.
[17] Z. T. Hsu, Quantitative Measurements of Brain's Power in Processing Information Using an Online Puzzle Game (大腦處理資訊能力之定量測量-線上拼圖遊戲的應用 ; a Thesis), Taipei: NTNU, 2007.
[18] "Pattern Recognition: what is it and how to develop it," Creative Huddle , 18 February 2021. [Online]. Available: https://www.creativehuddle.co.uk/post/pattern-recognition-what-it-is-and-how-to-develop-it. [Accessed 26 June 2023].
[19] "Pattern Recognition (psycology)," Wikipedia, 23 June 2023. [Online]. Available: https://en.wikipedia.org/wiki/Pattern_recognition_(psychology). [Accessed 26 June 2023].
[20] M. Singh, "10 Real Life Example Of Pattern Recognition," 14 March 2023. [Online]. Available: https://numberdyslexia.com/pattern-recognition-real-life-examples. [Accessed 26 June 2023].
[21] A. Wirayasa, "Pattern Recognition in Computer Science," [Online]. Available: https://www.ketutrare.com/2023/03/pattern-recognition-in-computer-science.html. [Accessed 27 June 2023].
[22] M. Parasher, S. Sharma, A. K. Sharma and J. P. Gupta, "Anatomy On Pattern Recognition," Indian Journal Of Computer Science and Engineering, vol. 2, no. 3, pp. 371-378, 2011.
[23] P. Baheti, "Image Recognition: Definition, Algorithms & Uses," V7, 5 October 2022. [Online]. Available: https://www.v7labs.com/blog/image-recognition-guide#how-image-recognition-evolved-over-time. [Accessed 27 June 2023].
[24] K. Kpalma and J. Ronsin, "An Overview of Pattern Recognition in Computer Vision," Vision Systems: Segmentation and Pattern Recognition, pp. 169-194, June 2007.
[25] T. Hicklin, "New Color Vision Pathway Unveilied," National Institutes of Health, 26 April 2016. [Online]. Available: https://www.nih.gov/news-events/nih-research-matters/new-color-vision-pathway-unveiled. [Accessed 27 June 2023].
[26] "Academy : Theory," Cone, [Online]. Available: https://www.conecosmetics.com/Academy/Online/Theory/CONE-cells/. [Accessed 2 June 2023].
[27] "Cone Cell," Wikipedia, [Online]. Available: https://en.wikipedia.org/wiki/Cone_cell. [Accessed 27 June 2023].
[28] "Introduction to Color Spaces," Java T Point, [Online]. Available: https://www.javatpoint.com/introduction-to-color-spaces. [Accessed 27 June 2023].
[29] "Complete Dissertation by Statistic Solutions," [Online]. Available: https://www.statisticssolutions.com/free-resources/directory-of-statistical-analyses/correlation-pearson-kendall-spearman/. [Accessed 24 June 2023].
[30] "Academic Skills Kit," Newcastle University, [Online]. Available: https://www.ncl.ac.uk/webtemplate/ask-assets/external/maths-resources/statistics/regression-and-correlation/strength-of-correlation.html. [Accessed 6 June 2023].
[31] "Effect Size," Wikipedia, 9 June 2023. [Online]. Available: https://en.wikipedia.org/wiki/Effect_size#. [Accessed 25 June 2023].
[32] P. Srinivasan, "Analytics Vidhya," 30 November 2020. [Online]. Available: https://www.analyticsvidhya.com/blog/2020/11/interpreting-p-value-and-r-squared-score-on-real-time-data-statistical-data-exploration/. [Accessed 26 June 2023].
[33] "Spearman's_rank_correlation_coefficient," Wikipedia, 6 April 2023. [Online]. Available: https://en.wikipedia.org/wiki/Spearman's_rank_correlation_coefficient. [Accessed 6 June 2023].
[34] F. Anifowose, "The Basic Elements of Artificial Intelligence and Recipe for a Successful Career Kick Start," 7 December 2021. [Online]. Available: https://jpt.spe.org. [Accessed 20 March 2023].
[35] S. Cheusheva, "Linear regression analysis in Excel," 16 March 2023. [Online]. Available: https://www.ablebits.com/office-addins-blog/linear-regression-analysis-excel/. [Accessed 11 April 2023].
[36] S. D. Jost, "Steve Jost -- IT 223 -- Section 501 -- Loop," DePaul University, [Online]. Available: https://condor.depaul.edu/sjost/it223/documents/correlation.htm#:. [Accessed 25 6 2023].