The Research Of Jigsaw Puzzle And Application

Jigsaw puzzles can be widely used in the fields of archaeology,cryptography,AR and so on.In recent decades,the research of jigsaw puzzles has experienced from the period of the features of shapes to mixed features of shapes and color information,ignoring the shape of the pieces of information,which pieces are all square,completely solved by color information.In the process of square pieces' research,many algorithms need preset informations,such as the small image of target puzzle,pieces are always fixed in one direction,up to now without any preconditions,and pieces can rotate smoothly,they can be called fully automatic algorithm.The number of pieces has been raised from 100 to more than 20000.Algorithm of missing pieces has been introduced to solve jigsaw puzzle.Solving jigsaw puzzle has been proved to be a NP-complete problem,many approximation methods are introduced to solve the problem,such as genetic algorithm,greedy algorithm,dynamic programming,graph models,and so on.The development of the algorithm is very fast,and the latest algorithm for the reconstruction of most of the images has reached more than 95% accuracy.For smooth images' reconstruction,however,there is no good algorithm for a long time.In order to solve this problem,we did the research and made some improvements.First,to make some improvements on measurement,we introduced the Jaccard distance,and applied it between images,combined with existing MGC compatibility,during the stage of reconstruction we still use the algorithm based on spanning tree.The experiment showed that the performance on smooth images or puzzles with a lot of similar things was better,but the improvement was a little bit,still below the satisfaction of real life.Second,we imitate human's basic steps of solving the puzzle,screening the adjacent pieces at first,then choose a piece as the initial point,a method based on symbol matrixes to reconstruct the puzzle.Although the algorithm's computing speed increased a little bit,it also can be used to deal with the puzzle with missing pieces,in terms of accuracy,especially the reconstruction of smooth image,the algorithm can't work very well.In addition,we try to use machine learning algorithm to find the adjacent pieces,such as Logistic Regression,SVM,but the result is not satisfied.Convolutional neural networks can extract the features of image effectively,it can simulate the processing of human brain.Human brain can distinguish the subtle differences between the two pieces,judge whether they are adjacent.A good network can also do this work well in theory,but because of the constraints,our network can't classify accurately when testing.Although we did not completely solve the problems existing in the jigsaw puzzle problems,especially the processing of the smooth images.Our proposed algorithm has advantages on speed and accuracy,and it can be used in the situation with missing pieces.