Recognizing Pentomino from scanned paper – Part 3

This it the 3rd part of the series on “How to recognize Pentomino from scanned paper“.

In the first part, I had discussed the steps to solve the problem of recognition.

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

In the second part, I had discussed about how to rotate the image and find the grid lines. The image below summarizes the steps so far, the grid is orthogonal to the image, and most of the lines are found. They are saved into two 1D arrays, “rows” and “cols”

There is also a slight problem, some lines are not detected. I will skip it for now, as it is quite easy to fill them in once you know the mean distance between the lines.

The next problem is to determine whether there is a drawn edge at some location. Just to make sure that I am clear, the following image shows what I call an edge. I marked the edges in green, and the non-edges in red.

The simplest approach I could think of is to find a small ROI around a possible edge, and collect some statistics. The simplest statistic is the mean value of the pixels. This makes sense, since edges should be black, and non-edges should be white. The following code section gets as input the processed image, and 2 arrays with row and column numbers of the lines on the grid. It runs in a loop through all rows and cols, and calls a procedure on a small ROI around the edge that attempts to measure the probability that it is an edge. The results are saved into an edge probability matrix.

function edgeProbabilityMatrix = ExtractHorizontalEdges(im,allCols,allRows)
	DEBUG = false;
	im = 255 - im;

	allRows = round(allRows);
	allCols = round(allCols);

	edgeProbabilityMatrix = zeros( numel(allRows),numel(allCols)-1);
	for i=1:numel(allCols)-1
		firstCol = allCols(i);
		secondCol = allCols(i+1);
		selectedCols = firstCol+2  : secondCol-2;
		selectedCols = putToLimits(selectedCols,1,size(im,2));
		for j = 1:numel(allRows)
			selectedRows = allRows(j)-4 : allRows(j)+4;
			selectedRows = putToLimits(selectedRows,1,size(im,1));
			if DEBUG
				x1 = selectedCols(1);
				x2 = selectedCols(end);
				y1 = selectedRows(1);
				y2 = selectedRows(end);
				plotc([x1 x2 x2 x1],[y1 y1 y2 y2],'k');
				hold on ;
			smallImage = im(selectedRows,selectedCols);
			if ~isempty(smallImage)
				p = AnalyzeHorizontalEdgeProbability(smallImage);
				edgeProbabilityMatrix(j,i) = p;

A few words about software engineering:

  • You might have noticed that I am using a custom function called plotc to debug the code. It draws a closed polygon. I have explained about it on stackoverflow.
  • I am also using another custom function, called putToLimits. It clips the input, so that it doesn’t go above or below some minimal and maximal value, i.e. get out of range. Its output is a clipped variant of the input.
  • I am using loops. There might be a vectorized solution, but in this case I prefer loops, due to the clarity of the code. A code that can be debugged is often worth a more than a bunch of smart-ass one-liners. That depends on the case, but in general there is a tendency to abuse vectorized solutions in Matlab community, as they are often considered to be smart, creative, etc. As Loren said once in her blog: “Vectorize, but sensibly“. I have touched here an issue that I will discuss more thoroughly in the next posts.
  • I wrote two functions – one for detection of vertical edges, and one for horizontal. This is not a good practice. A duplicated code causes maintenance problem in the long term. I should fix it in one of the next coding iterations.

Now, back to the algorithm. First, here is a visualization of the ROIs being taken for the horizontal edges:

Here is a histogram of the mean values in the ROIs, both for the horizontal and the vertical edges.

That looks very good!  You can spot two distributions mixed, with the mean values separated quite well. These kind of histograms are called Bi-Modal histograms. The good thing about them is that there are several solutions in computer vision to the problem of separating them and finding a threshold automatically. One of them is Otsu’s method, which is implemented in Matlab. The relevant function is graythresh. However, it assumes that the images are in the range of [0,1], so I did a scaling. The following function detects the range of the input, and scales it to [0,1]. Then it recalculates the threshold in terms of original input.

function threshold = PickThreshold(vals)
    vals = double(vals);
    a = min(vals);
    b = max(vals) - min(vals);
    vals = (vals - a ) / b;
    threshold = graythresh(vals);
    threshold = threshold * b + a;

Here is the result, after thresholding with Otsu’s method:
You can see that there are some non-edges detected as edges (false positives), and vice versa. This is not perfect, but it is a good start. I will explain in the next post how it can be improved.

How would you improve it? Leave a comment.


One thought on “Recognizing Pentomino from scanned paper – Part 3

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