Jigsaw Puzzle and Image Processing (ジグソーパズルと画像処理)

Recently, I got a Little Busters! (リトルバスターズ!) jigsaw puzzle of 500 pieces. According to the description printed on the box, the size of the puzzle is 38 x 53 cm. The estimated time to complete the whole puzzle will be 15 hours. So, I decided to build a tool to help me complete the task by identifying the location of each piece of the jigsaw puzzle.

Little Busters! 500 Pieces Jigsaw Puzzle
Little Busters! (Rin and Komari) 500 Pieces Jigsaw Puzzle

The first thing I need is a webcam. Most of the modern laptops have a webcam, even Chromebook has one. So, the next problem will be capturing image using the webcam. Therefore, I built a simple project to do that using Silverlight because it is very easy to achieve simple webcam image capturing in Silverlight.

After that, since the Silverlight project is web based, I can embed it in another my Windows Form C# application with the WebBrowser control easily. So now what I have is a image capturing app without the saving function yet.

Successfully capture the image from webcam.
Successfully capture the image from webcam.

The main task of the C# application is to save the captured image and then compare it with a target image to identify the matching pieces in the jigsaw puzzle. The square with white border is the area where the image will be saved as an image for the use of image comparison later. The templates that the captured image will be compared with are the 500 squares from the original complete image. To save only the captured image inside the square (100×100 pixels), I do the following.

Rectangle bounds = this.Bounds;
int widthOfCaptureArea = 100;
int heightOfCaptureArea = 100;
int captureAreaX = 120;
int captureAreaY = 85;
Size captureArea = new Size(widthOfCaptureArea, heightOfCaptureArea);
Point webBrowserLocation = webBrowser1.PointToClient(new Point(bounds.Left, bounds.Top));
using (Bitmap bitmap = new Bitmap(widthOfCaptureArea, heightOfCaptureArea))
{
    using (Graphics g = Graphics.FromImage(bitmap))
    {
        g.CopyFromScreen(
        new Point(bounds.Left + captureAreaX + webBrowserLocation.X * -1, bounds.Top + captureAreaY + webBrowserLocation.Y * -1), Point.Empty, captureArea);
    }
    bitmap.Save("D://.../source.jpg", ImageFormat.Jpeg);
    bitmap.Dispose();
 }

With the help of AForge.NET framework, I can easily get the similarity of source and template images using its ExhaustiveTemplateMatching class to compare pixel-by-pixel between the source image and the template image.

private float CheckSimilarity(Bitmap sourceImage, Bitmap targetImage) 
{
   // create template matching algorithm's instance
   ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0.8f);
   // find all matchings with specified above similarity
   TemplateMatch[] matchings = tm.ProcessImage(sourceImage, targetImage);
   float similarity = 0;
   foreach (TemplateMatch m in matchings)
   {
       similarity = m.Similarity;
   }
   return similarity;
}

When comparing the images, I perform rotation three times because the direction of the piece is uncertain. So, I will just need to rotate the source image three times and compare the source and the template for each of the time to get the highest similarity value.

float similarity = CheckSimilarity(sourceImage, targetImage);
// Rotate the source image 90 degrees
for (int i = 1; i <= 3; i++)
{
    sourceImage.RotateFlip(RotateFlipType.Rotate90FlipNone);
    if (CheckSimilarity(sourceImage, targetImage) > similarity)
    {
        similarity = CheckSimilarity(sourceImage, targetImage);
    }
}
Similarity of 83%
Similarity of 83% between this particular piece with one of the template images from the original complete image

Yup, now it is done and I can thus use it to complete my 500-piece jigsaw puzzle. However, in the whole project, I actually assume each piece to be a perfect square. So the similarity value is not that accurate as well. This can be improved in the next version to take the pattern of each piece into consideration.

Advertisements

One thought on “Jigsaw Puzzle and Image Processing (ジグソーパズルと画像処理)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s