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 ; end smallImage = im(selectedRows,selectedCols); if ~isempty(smallImage) p = AnalyzeHorizontalEdgeProbability(smallImage); edgeProbabilityMatrix(j,i) = p; end end end if DEBUG figure;imagesc(edgeProbabilityMatrix); end end

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; end

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.

A very big like!

How about actually solving the Pentomino automatically 🙂 ?

I bet you already thought about it…