10

I have written a program in Python which automatically reads score sheets like this one Sheet after deskewing

At the moment I am using the following basic strategy:

  • Deskew the image using ImageMagick
  • Read into Python using PIL, converting the image to B&W
  • Calculate calculate the sums of pixels in the rows and the columns
  • Find peaks in these sums
  • Check the intersections implied by these peaks for fill.

The result of running the program is shown in this image: Image after processing

You can see the peak plots below and to the right of the image shown in the top left. The lines in the top left image are the positions of the columns and the red dots show the identified scores. The histogram bottom right shows the fill levels of each circle, and the classification line.

The problem with this method is that it requires careful tuning, and is sensitive to differences in scanning settings. Is there a more robust way of recognising the grid, which will require less a-priori information (at the moment I am using knowledge about how many dots there are) and is more robust to people drawing other shapes on the sheets? I believe it may be possible using a 2D Fourier Transform, but I'm not sure how.

I am using the EPD, so I have quite a few libraries at my disposal.

chthonicdaemon
  • 19,180
  • 2
  • 52
  • 66
  • 1
    You can try to use Hough transform for circles searching. Or even just make a cross-correlation of scanned image with image of single circle. Peaks will show coordinates of all circles, slight tuning (median or even least squares method) will give you fine grid. – Eddy_Em May 16 '13 at 06:03
  • related: [Finding number of colored shapes from picture using Python](http://stackoverflow.com/q/5298884/4279) – jfs May 16 '13 at 12:53

2 Answers2

3

First of all, I find your initial method quite sound and I would have probably tried the same way (I especially appreciate the row/column projection followed by histogramming, which is an underrated method that is usually quite efficient in real applications).

However, since you want to go for a more robust processing pipeline, here is a proposal that can probably be fully automated (also removing at the same time the deskewing via ImageMagick):

  1. Feature extraction: extract the circles via a generalized Hough transform. As suggested in other answers, you can use OpenCV's Python wrapper for that. The detector may miss some circles but this is not important.
  2. Apply a robust alignment detector using the circle centers.You can use Desloneux parameter-less detector described here. Don't be afraid by the math, the procedure is quite simple to implement (and you can find example implementations online).
  3. Get rid of diagonal lines by a selection on the orientation.
  4. Find the intersections of the lines to get the dots. You can use these coordinates for deskewing by assuming ideal fixed positions for these intersections.

This pipeline may be a bit CPU-intensive (especially step 2 that will proceed to some kind of greedy search), but it should be quite robust and automatic.

sansuiso
  • 9,259
  • 1
  • 40
  • 58
2

The correct way to do this is to use Connected Component analysis on the image, to segment it into "objects". Then you can use higher level algorithms (e.g. hough transform on the components centroids) to detect the grid and also determine for each cell whether it's on/off, by looking at the number of active pixels it contains.

Photon
  • 3,182
  • 1
  • 15
  • 16
  • +1. Also, I recommend the OP have a look at http://opencv.org/ -- it's great for image processing in Python – mpenkov May 16 '13 at 06:05
  • Could you elaborate on using the Hough transform to find a grid shape? I'm familiar with using it to find lines, but I'm sure the fact that the grid is a nice repeating pattern can be exploited. – chthonicdaemon May 16 '13 at 06:32
  • if you look at the position of components centroids as the data points you input into the hough transform (instead of individual pixels), you get a very fast "low resolution" analysis of the lines the cells are arranged in. This can also remove the need for deskew up front. Another option is using Ransac to determine the arrangement of the grid. Once you move from the pixel level to the component level, things become more intuitive and you can basically come up with robust solutions easily. – Photon May 16 '13 at 07:18
  • Your suggestion is reasonable but calling it "the correct way" is a bit exaggerated. There are multiple, equally reasonable, approaches to this problem. – tom10 May 24 '13 at 03:03