# Detect implicit grid in image with monospaced characters

I'm trying to detect the monospaced-grid in a possibly slightly deformed image of a receipt. Example input (full size here)

My idea is to obtain the centroids or bounding boxes of all components and do a kind of Hough transform on these points, but I wouldn't know how to do this in Mathematica.

The output could have different formats, but should look something like this.

In this particular example, equi-spaced lines horizontally and vertically are enough, but It would be a pro if the algorithm can also handle a little perspective distortion.

• You can do a Hough transform using the command Radon reference.wolfram.com/language/ref/Radon.html Look under the Details section and choose the Hough option. – bill s Nov 29 '14 at 16:22
• @bill, thank you! I found Radon, but the input for Radon is an image. It would be preferable if I can just input a list of 2D-points. – Thijs Nov 29 '14 at 16:32
• If you have a 2D list, then you can turn it into an image using Image[list], then apply Radon. – bill s Nov 29 '14 at 17:14
• The input you mention in your question is an image. In the comment above you state the input is a list. IMHO you have to be a bit clearer about your intentions. – Sjoerd C. de Vries Nov 29 '14 at 17:31
• @sjoerd, yeah you're right. Sorry I was confused. In my own approach, I use the centroids of the components as points. belisarius' answer is exactly what i'm looking for though. – Thijs Nov 29 '14 at 19:46

Simple enough, and fails only on one scarcely populated column. Easily fixed if you enforce the "monospaced" property

i = Binarize@Import@"http://i.stack.imgur.com/XWhHv.png";
(* delete noisy border*)
i1 = DeleteSmallComponents[ImageTake[i, {1, 1650}, {30, -1}], 10];

id = ImageDimensions@i1;
cm = ComponentMeasurements[i1, "Centroid"][[All, 2]];
bb = Abs@Mean[ Subtract @@@ ComponentMeasurements[i1, "BoundingBox"][[All, 2]]];

(* The following is basically a MeanShiftFilter[], but I couldn't make
MeanShiftFilter[] to behave properly after a cursory try. Probably you should try it *)

yc = Mean /@ Split[Sort@cm[[All, 2]], Abs[#1 - #2] <= bb[[1]]/4 &];
xc = Mean /@ Split[Sort@cm[[All, 1]], Abs[#1 - #2] <= bb[[2]]/4 &];
a = 1.3;
Show[i1, Graphics[{{Red, {Line[{{1, # - a bb[[1]]}, {id[[1]], # - a bb[[1]]}}]} & /@ yc},
{Yellow, {Line[{{# - a bb[[2]], 1}, {# - a bb[[2]], id[[2]]}}]} & /@ xc}}]]


• This is great, thanks! – Thijs Nov 29 '14 at 19:49
• Belisarius, do you by any chance also have ideas on how to adapt this method to support slight perspective distortion? – Thijs Nov 29 '14 at 20:53
• @Thijs Usually done fitting a FindGeometricTransform[]. Butyou need to provide a few sample images to be sure – Dr. belisarius Nov 29 '14 at 21:06