Recognizing Pentomino from scanned paper – Part 1

[This is my first post! Please leave a comment, I would love to hear your feedback.]

A few monthes ago, when I visited my parents house, I noticed that my dad had solved a lot of Pentomino puzzles. Also, he had wrote them down in a notebook.
Pentomino is a puzzle game, in which you have to tile a 2D shape from pieces. The pieces resemble Tetris pieces, however, they have 5 squares instead of 4. There are 12 unique pieces, excluding rotations and flips:

A typical tiling puzzle solution looks like in the following way:

Here is a typical page from his notebook, after I scanned it:

As someone who is excited about image processing, I immediately thought about writing a program that will scan the page, and recognize the puzzle solutions. In this post, and the next ones, I will show the steps  that I used in order to accomplish this task. Also, I will try to share my thoughts about development in general.

Here is an overview of the algorithm:

  1. Rotate the image to be orthogonal to x-y axis
  2. Find the grid
  3. For each edge on the grid, decide whether it is “black edge” or “no edge”
  4. Break the grid into several parts, and process each one individually.
  5. Somehow, by using the prior knowledge on the 12 pentomino pieces, find where they are.

Let’s discuss each step individually. First, the rotation. Why do we need to rotate? When I scanned the notebook, I was kind of sloppy, and did not align it precisely on the scanner.

Thus, some compensation for the angle is needed. It is probably possible to solve the entire problem only by knowing the angle, and not rotating the actual image. While it is possible, the fact that all of the edges become either perfectly horizontal or vertical makes the coding easier. Even more than that, the debugging (which usually takes more time than writing the code itself) becomes significantly easier. The actual rotation re-samples the image, which can cause a degradation of quality. Nevertheless, as long as I will be able to extract the relevant information, it will be good enough.

How to find the angle of rotation? Several options popped into my head. Hough transform to recognize the lines sounds like a reasonable choice. I can find two dominant angles in Hough space, and use them. I decided to use Radon transform, which is conceptually very close.  Radon transform scans the image in every angle and sums up the pixels to a 1D array. You can see in the next image a conceptual  explanation of the transform:

I expect to have the highest contrast while scanning the angle of the grid. Why? Because every other angle will be more blurred. Think about it, if we hit the exact grid location, we expect to see something like a wave of peaks. Every time that we hit the grid line, the array value will be very large, and when we don’t it will be small. I don’t need to scan all of the possible angles, I need a small range around 0 and 90 degrees, and fairly good quantization of these small ranges. In order to detect the angle with the maximum contrast, I can calculate standard deviation to approximate the contrast.

There is one inherent flaw in Radon transform. Different orientations result in different 1D array length. Thus, the transform is biased towards some angles, it gives them more weight. In order to overcome this problem, I divide by a Radon transform of array of ones.

Here is the result of the transform, on the image above. You can see that one of the columns has a high contrast – that is the angle! It is close to zero, but not exactly.

Here is the Matlab code that detects the angle:

function angle = DetectAngle(greenIm)
    edgeIm = edge(greenIm,'canny');

    EXPECTED_ANGLE = 0;
    ORTHOGONAL_ANGLE = EXPECTED_ANGLE + 90;
    ANGLE_RAD = 5;
    STEP = (ANGLE_RAD*2) / 40;

    theta1 = EXPECTED_ANGLE - ANGLE_RAD : STEP : EXPECTED_ANGLE + ANGLE_RAD;
    theta2 = ORTHOGONAL_ANGLE - ANGLE_RAD : STEP : ORTHOGONAL_ANGLE + ANGLE_RAD;

    In = ones(size(edgeIm));
    %     theta =
    R = radon(edgeIm,theta1)./radon( In,theta1);
    Ro = radon(edgeIm,theta2)./radon( In,theta2);
    %     figure;imagesc(theta1,1:size(R,1),R+Ro);
    Rt = R + Ro;
    Rt(isnan(Rt)) = 0;
    nContrastProfile = std(Rt);
%     figure;plot(theta1,nContrastProfile);
    [~,nMaxContrastLocation] = max(nContrastProfile);
    angle = theta2(nMaxContrastLocation);

end

In the next post, I will show the next steps, so stay tuned.

[This is my first post! Please leave a comment, I would love to hear your feedback.]

Advertisements

4 thoughts on “Recognizing Pentomino from scanned paper – Part 1

  1. Hye there.. i would like to try out this code.. but unfortunately i got some error at line 21: [~,nMaxContrastLocation] = max(nContrastProfile); Expression or statement is incorrect–possibly unbalanced (, {, or [. Any help would be appreciate.

    • I think that you got an older Matlab version, which does not recognize the “~” syntax.
      Instead, simply change it to:

      [dummy,nMaxContrastLocation] = max(nContrastProfile);

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