簡易檢索 / 詳目顯示

研究生: 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
論文種類: 學術論文
相關次數: 點閱:103下載: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.

    Acknowledgements i Abstract iii Contents iv List of Figures vii List of Tables x CHAPTER 1: INTRODUCTION 1 1.1 Some Related Research 2 1.2 Research Purpose 3 CHAPTER 2: LITERATURE REVIEW 4 2.1 Pattern Recognition in Puzzle Solving 4 2.2 Human Visual Perception and Color Quantification 7 CHAPTER 3: METHODS AND PARAMETERS 10 3.1 Human Strategy’s on Puzzle Solving 10 3.2 Computer simulation algorithm 11 3.3 Some Parameters 13 3.3.1 Number of sections and level of resemblance 13 3.3.2 Resemblance threshold, Alpha, and q 14 3.3.3 Percentage of ABC 15 3.4 Measurement of Simulation Performance 17 3.4.1 Pearson’s Correlation Coefficient (r) and R-squared value (r2) 17 3.4.2 Spearman’s Correlation (ρ) 18 CHAPTER 4: RESULTS AND DISSCUSSION 20 4.1 Measurement I 20 4.1.1 Various number of sections (Nos) 20 4.1.2 Different pattern of number of sections 23 4.1.3 Various resemblance threshold 25 4.1.4 Various alpha 28 4.1.5 Various q values 30 4.1.6 Various Percentage of ABC 33 4.2 Histogram of Percentage of Similar Edge and Color Entropy 34 4.3 Principal Trails of Puzzle Solving Process 35 4.4 Measurement II 43 4.4.1 Various resemblance threshold 43 4.4.2 Various alpha 46 4.4.3 Various q values 49 4.4.4 Various Percentage of ABC 53 4.5 Distribution of R-Squared, Gradient, and Spearman’s Correlation 58 CHAPTER 5: CONCLUSION 62 BIBLIOGRAPHY 64 Appendix: Average puzzle solving time as a function of N and its performance comparing to empirical data (λ’) 70

    [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].

    下載圖示
    QR CODE