Recognizing Pentomino from scanned paper – Part 4

This is part 4 in the series of “Recognizing Pentomino from scanned paper”. To understand the context, I advice you to read previous parts (part 1, part 2part 3 ) before reading this one.

So far we’ve been able to:

  1. Rotate the image to be orthogonal to x-y axis in part 1
  2. Find the grid in part 2
  3. For each edge on the grid, decide whether it is “black edge” or “no edge” in part 3

The last step was far from perfect. When I developed the application, I decided that this is good enough to move on to the next steps. That is because often it is better to get a full working prototype as soon as possible, rather than get stuck at particular point. This approach has several advantages:

  • If you run out of time, you still got some kind of working solution.
  • Often, when you complete everything, you will see that there are other places, far more important than this one, to concentrate on them.
  • You might get really stuck in one of the next steps, in a way that you can’t advance at all. Obviously, it would be better to invest your time in that impossible step, rather than at one which is working, though not perfectly.

Development time is often your most precious resource!

Nevertheless, breaking the chronological order of things, I still want to describe how I improved this step at the end, after completing all of the steps. Just to remind you, the idea that I used at first was measuring the average of the pixels in the ROIs, marked as purple rectangles in the image below.

This kind of approach is not robust enough, because it does not consider any geometrical information. I can take the pixels of an black obvious edge, re-arrange their intensity among all pixels, and I still will get the same average intensity. Consider the two following images below (side-by-side). They have the same amount of intensity:

In order to differ the cases mentioned above, we could use correlation with perfect edge. The gray uniform patch would not give a high correlation. However, the edges can be curved, since they are drawn by human. Thus, I decided to perform a convolution with a column edge element. (For vertical edges, I use a convolution with row edge element.)  This should find the centers of the edge, per column. Since the edge is black on white background, the element should be in the following form : [+ + – – – – + +] . The negative part corresponds to the black edge. (This will handle better curved edges, since the maximal value is found per column, and can be in different row).

correlationImage = conv2(double(im),[1;1; -1;-1;-1;-1; 1;1;],'same');

I do this on the whole image, and then check in the relevant ROIs, on the convolution result. In each ROI, I can find the maximal response of the convolution per column (or row, if vertical edge), and then return the mean value.

function p = AnalyzeAnyEdgeProbability(edgeIm,dim)
    p = mean(val);

Here are two images, of an edge, and an image of correlation.  I find the maximal value in each column, and average. That is the probability that the ROI represents an edge.

The idea that we used last time of finding the threshold automatically is still valid. Otsu’s method of thresholding can be used on these new numbers.  Here is how the histogram of the new probability measure looks like now:

Otsu’s method will have an easy time with this one. The two distributions are separated very well.

After applying this new method here are the edges found after thresholding:

Now that is much better! It is not perfect, but now we can separate the problem into a set of smaller ones, and handle each individually. I will show in the next post how to:

  • Break the image into clusters by graph traversing technique
  • For each cluster
    • Each piece can be once and only once, so let’s use this information!

By the way, you can use the “follow” button above the post to subscribe by e-mail.


Leave a Reply

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

You are commenting using your 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