Computer Puzzle Shape Recognition Algorithm Research

The aim of Automatic puzzles solver is to automatically assemble an image of the pieces of a jigsaw puzzle by the shape,color and texture features of the pieces,Jigsaw puzzle problem endemic to machine vision,image analysis and pattern recognition.It contains a number of issues about machine vision,like shape description,partial boundary matching,feature extraction,etc.It can be applied to diverse areas such as restoration of archaeological findings, repair of broken objects,biological research,etc.Based on the version 1.0 of the JPT,this paper makes use of the scanner to get the pictures as the object to research.Automatic puzzles solver software integrates educational factor into a funny game and presents the basic principle of machine vision technology.It's easy to understand by students. The shape information is one of the most important information,which plays leading role in the Automatic Puzzles.This paper does a lot of research about the shape matching.The research starts from image scanning and goes along the process of an image change into curves to finish this paper.The research contents of the paper include:1.Discussing the methods reducing the noise caused by piece shadows,scanner noise, specks of color on the back sides of pieces,and so on.And a good result is gained.2.Introducing the image contour extraction.We obtain the Freeman chain code representation and the curvature representation of the boundary firstly.In order to find the easiest algorithm to calculate the curvature,we compare several methods in this filed.In the end,a kind of way named closed contour calculation is selected to complete our work.3.In order to find the boundary,this paper studies several conner detection algorithms and proposes two algorithms:conner detection based on chain code and conner detection based on curvature.Also detailed comparison and estimate about the two algorithms are discussed.4.After the chain code and curvature of the boundary obtained,we combine the dynamic programming algorithm with them separately and propose a dynamic programming algorithms based on chain code and curvature.And different similar-measurements of the two algorithms are given respectively.The experiments results indicate that,without the participating of color and texture and only using the characteristic of shape,the correct rate approaches exceed 90%.If we combine the shape characters with color and texture,a whole image will be assembled correctly.