Detecting grid lines in a raster image

Motivation: Last October 7 there was a presidential election in Venezuela. Although the opposition saw an unprecedented increase in its votes, the government votes increased even more resulting in the current president being re-elected. The votes were counted by computers that are not trustworthy because of what they have done in the past. Each voting machine printed a voting certificate with the results. About 90% of such certificates where collected by the opposition and are available to anyone at http://hayuncamino.com/actas/

In each voting table there was a paper notebook were each voter put its signature and fingerprint. According to the law, the total number of votes from this notebook was supposed to be compared to the votes reported by the machine. The results certificate provided a space where this number must be hand written. Unfortunately it seems that in a very large number of voting tables the law was broken because the space for this verification is empty.

By using Mathematica image processing capabilities I intend to find out in which voting tables the verification was done and compare the results of this subset with its complement.

The original question:

I need to process a large number of images for a non-profit organization report. The images contain a grid with borders and cells. The cells B2 and C2 (spreadsheet coordinates) can be hand written or can be empty, and that is what needs to be detected.

Here is an example of a filled form:

And this is an example of an empty form:

My plan is to detect the coordinates of the following points:

and then compute to total amount o black pixels in the area defined by them.

So my question is: What strategy would you recommend to reliably detect the location of those points indicated in red?

I have already tried using ImageLines, Radon, and FindGeometricTransform without much success. I think that the best approach is not to look for independent lines but instead look for the grid as a whole.

This is what I am trying to do:

figWithoutSideBorders = 
  ColorNegate @
    ImageAdd[fig, 

             ColorNegate @ Erosion[#, 3] & @ MeanFilter[#, 1] & @ MaxDetect[fig, 0.95]
    ]

I careful crafted this matrix so that it has the same proportions as the target grid:

formMatrix = SparseArray[{Band[{ 1, 1 }, Automatic, {0,1}] -> 1,
                          Band[{15, 1 }, Automatic, {0,1}] -> 1,
                          Band[{29, 1 }, Automatic, {0,1}] -> 1,
                          Band[{52, 1 }, Automatic, {0,1}] -> 1,
                          Band[{66, 1 }, Automatic, {0,1}] -> 1,

                          Band[{ 1, 1 }, Automatic, {1,0}] -> 1,
                          Band[{ 1,105}, Automatic, {1,0}] -> 1,
                          Band[{ 1,146}, Automatic, {1,0}] -> 1,
                          Band[{ 1,265}, Automatic, {1,0}] -> 1},
                          {66,265}];
formFigure = ColorNegate @ ArrayPlot[formMatrix, AspectRatio -> Automatic, Frame -> False]

But when I try to use FindGeometricTransform, it fails. Maybe it does not work with hollow objects?

As I last resort, I am thinking about doing horizontal and vertical histograms and look for proportionally spaced peaks, but I want to ask the community before I over engineer a solution. Thanks in advance.

UPDATE 1: @nikie answer is certainly very useful and I am thankful for that. My only concern is that this method looks for any table instead of looking for a 4x3 table with row heights 21%, 21%, 36%, 21% and column widths 40%, 15% and 45%. The fragility of the method is exposed by using the other provided sample image where a vertical line, that is not part of the table is confused for an additional column:

UPDATE 2: As suggested by @belisarius I have added some context / motivation for this question.

UPDATE 3: I have now finished the processing. Only 5.7% on the voting certificates where not blank in the target total votes verification area. About 99% of the voting certificates were processed automatically. I have developed a set of functions that could be useful for other people doing similar tasks (and even in different areas), so I plan to write an answer to share that. Look also for a torrent file in the comments area.

Answer

The grid line detection from this answer works almost out of the box.

First, I adjust the brightness of the image for easier binarization:

src = ColorConvert[Import["http://i.stack.imgur.com/CmKLx.png"], 
   "Grayscale"];

white = Closing[src, DiskMatrix[5]];
srcAdjusted = Image[ImageData[src]/ImageData[white]]

Next I find the largest connected component (largest convex hull area), which should be the grid you're looking for:

components = 
  ComponentMeasurements[
    ColorNegate@Binarize[srcAdjusted], {"ConvexArea", "Mask"}][[All, 
    2]];
largestComponent = Image[SortBy[components, First][[-1, 2]]]

I create a filled mask from that, so I can ignore the background in the image:

mask = FillingTransform[Closing[largestComponent, 2]]

Next step: detect the grid lines. Since they are horizontal/vertical thin lines, I can just use a 2nd derivative filter

lY = ImageMultiply[
   MorphologicalBinarize[
    GaussianFilter[srcAdjusted, 3, {2, 0}], {0.02, 0.05}], mask];

lX = ImageMultiply[
   MorphologicalBinarize[
    GaussianFilter[srcAdjusted, 3, {0, 2}], {0.02, 0.05}], mask];  

The advantage of a 2nd derivative filter here is that it generates a peak at the center of the line and a negative response above and below the line. So it's very easy to binarize. The two result images look like this:

Now I can again use connected component analysis on these and select components with a caliper length > 100 pixels (the grid lines):

verticalGridLineMasks = 
  SortBy[ComponentMeasurements[
      lX, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All, 

      2]], #[[2, 1]] &][[All, 3]];
horizontalGridLineMasks = 
  SortBy[ComponentMeasurements[
      lY, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All, 
      2]], #[[2, 2]] &][[All, 3]];

The intersections between these lines are the grid locations:

centerOfGravity[l_] := 
 ComponentMeasurements[Image[l], "Centroid"][[1, 2]]
gridCenters = 

  Table[centerOfGravity[
    ImageData[Dilation[Image[h], DiskMatrix[2]]]*
     ImageData[Dilation[Image[v], DiskMatrix[2]]]], {h, 
    horizontalGridLineMasks}, {v, verticalGridLineMasks}];

Now I have the grid locations. The rest of the linked answer won't work here, because it assumes a 9x9 regular grid.

Show[src, 
 Graphics[{Red, 
   MapIndexed[{Point[#1], Text[#2, #1, {1, 1}]} &, 
    gridCenters, {2}]}]]

Note that (if all the grid lines were detected) the points are already in the right order. If you're interested in grid cell 3/3, you can just use gridCenters[[3,3]] - gridCenters[[4,4]]

tr = Last@
   FindGeometricTransform[
    Extract[gridCenters, {{3, 3}, {4, 3}, {3, 4}}], {{0, 0}, {0, 
      1}, {1, 0}}] ;
ImageTransformation[src, tr, {300, 50}, DataRange -> Full, 
 PlotRange -> {{0, 1}, {0, 1}}]

ADD: Response to updated question

UPDATE 1: @nikie answer is certainly very useful and I am thankful for that. My only concern is that this method looks for any table instead of looking for a 4x3 table with row heights ...

The algorithm I described above was meant as a proof-of-concept prototype, not an industrial strength, fully-polished solution (where would be the fun in that?). There are a few obvious way to improve it:

• instead of selecting the connected component with the largest convex area, you could add more filter criteria: caliper length, caliper with, length of the semiaxes of the best-fit ellipse, shape characteristics like eccentricity, circularity, rectangularity. That should make the mask detection a lot more stable. But you'll have to find the right thresholds empirically, using (a lot) more than two samples


• if the mask that is found contains other objects (e.g. lines running through the table), you can filter them away using morphological operations.


• you could simply skip the gridline-search, and use the corners of the mask to calculate the geometric transformation, since you already know where the cells are in relation to the grid outline



• even simpler: maybe you can just use the centroid and orientation found by ComponentMeasurements for the geometric transformation, without using the mask and grid lines at all.


• you could select only the grid lines that are roughly in the positions you expect them, in relation to the full rectangle.


• you could filter out grid lines that leave the mask area


• you could only select grid lines that have the right caliper length

These are just a few ideas of the top of my head. Since you already have the position of the table (either using the mask or the centroid&orientation properties from ComponentMeasurements) and the grid lines, the implementation of these ideas should be mostly straightforward. But there's no way to tell which of them work and how well without implementing them and testing them on a large range of sample images. (At least, I know of no way.)