Walaupun teka-teki jigsaw hanyalah semata-mata satu permainan kepada orang ramai, ia memberi tahap cabaran yang tinggi kepada bidang pemprosesan imej. Teka-teki jigsaw boleh dikategorikan kepada jenis asas bergambar dan jenis asas berbentuk. Teka-teki jigsaw jenis asas bergambar boleh diselesaikan dengan menggunakan penggambaran atas perbezaan dalam penampilan tetapi susun suai gambar jenis asas berbentuk hanya boleh diselesaikan dengan menggunakan maklumat mengenai bentuk. Susun suai gambar bentuk segi empat adalah lebih sukar daripada susun suai gambar tradisional kerana teka-teki jigsaw bentuk segi empat memberi hamir kosong maklumat tentang bentuk teka-teki jigsaw dan satu-satunya sumber yang boleh dipercayai adalah perbezaan dalam penampilan kepingan jigsaw teka-teki. Oleh itu, tujuan utama projek ini adalah untuk membina semula teka-teki jigsaw. Terdapat dua sumbangan dalam projek ini; matrik keserasian baru dan kaedah pemilihan benih baru. Matrik keserasian baru itu memilih L2-Norm bagi bahagian-bahagian bersebelahan yang mempunyai perbezaan kecil di sepanjang sempadan mereka . L1-Norm digunakan bagi kes yang sangat berbeza dalam warna sepanjang sempadan pada bahagian-bahagian yang bersebelahan. Sumbangan kedua adalah pendekatan baru dalam memilih benih permulaan teka-teki. Benih atau kepingan gambar teka-teki lebih banyak maklumat tentang penampilan ada adalah lebih mudah untuk dipadankan dengan kepingan teka-teki yang tinggal. Sebaliknya, jika permukaan benih mempunyai banyak warna sekata, ia adalah lebih sukar untuk dipadankan dengan kepingan teka-teki lain. Oleh itu , pilihan benih yang baik akan memberi potensi yang tinggi untuk penyelesai jigsaw teka-teki untuk membina semula balik semua kepingan teka-teki dalam masa yang lebih pendek. Akhirnya, dengan menggunakan metrik keserasian baru, penyelesai teka-teki jigsaw dapat membina balik teka-teki jigsaw sehingga 432 kepingan dengan tahap ketepatan setinggi 65%. Seterusnya, dengan menggunakan cara pemilihan benih, ketepatan daripada penyelesai teka-teki jigsaw telah meningkat kepada 100 % bagi penyelesaian teka-teki jigsaw sebanyak 108 keping.
_______________________________________________________________________________________________________
Though jigsaw puzzle is merely a game to the public, it provides high degree of challenges to the image processing field. Jigsaw puzzle itself can be categorized into pictorial and apictorial puzzle. Pictorial puzzle is the type of puzzle that can be solved by using visualization on the difference in the appearance but apictorial puzzle can only be solved using the information regarding to the shape. Square jigsaw puzzle is much tougher than traditional jigsaw puzzle as square jigsaw puzzle provides almost zero information regarding to the shape of the puzzle and the only reliable source is the differences in the appearance of puzzle pieces. Therefore, the main purpose of this project is to efficiently reconstruct back the puzzle pieces. There are two contributions of this project; a new compatibility metric and a new seed selection method. The new compatibility metric applies L2-Norm for adjacent parts that have small difference along their boundaries. For the case of very different in the colour along the boundaries of adjacent parts, L1-Norm is applied. The second contribution is the new approach in selecting the starting seed of the puzzle. A seed or a starting puzzle piece with more appearance information available is easier to be matched up with the remaining puzzle pieces. In contrast, if a seed with homogenous colour plane on its surface is selected, it is harder to match this seed with other puzzle pieces. Hence, a good selected seed will lead to a high potential for the puzzle solver to reconstruct back all the puzzle pieces in a shorter time. In the end, by using new compatibility metric, the solver reconstructed back puzzle pieces up to 432 pieces with a mean accuracy level of 65%. Next, by using seed selection approach, accuracy of the solver was increased to 100% constantly in solving puzzle of 108 pieces.
Jigsaw puzzle solver / Calvin Chen