How to guess which pieces of text belong to which lines in a scanned document?

Question

I want to be able to analyze a five-years archive of supermarket receipts. The receipts are scanned, and thanks to Google Cloud Vision API, the result of an OCR is available. Google's API, however, gives only the text and its geometrical position on an image, nothing more. Example:

ID: 5620
Content: “TICKET”
Vertices: (2070, 3663); (2069, 3683); (2002, 3680); (2003, 3660)

ID: 5621
Content: “ORIGINAL”
...

My next step is to try to build a series of lines containing the pieces of text. In other words, the fact that Google's API found that the piece 5621 is after 5620 doesn't mean that it actually is, since receipts are sometimes partially rotated, curved, crumpled and mangled. Here's an example:

Towards the top, there is a list of three items, with their prices on the right. It's easy for a human to understand that the second price, 3.30€, corresponds to the second item, and not the first one; however, its y coordinate could make a program guess that it actually belongs with the text of the first item, not the second one.

In order to fix that, I decided to proceed like this:

1. For every piece of text, thanks to the vertices given by Google's API, I find the rotation of the item. Based on this rotation, I do a projection to the left side of the bounding box of the receipt.

   ^{The bounding box is shown in blue on the image. The projection is shown as green dotted lines.}

2. I find a list of pieces of text which intersect the projected line.

3. Among the ones which intersect the line, I pick the one which is situated at the right. It is then marked as the previous sibling of the piece of text.

4. Based on previous siblings, I build a series of lists with consecutive pieces of text. Each list should correspond to a line.

Those lines are indicated in black on the image. It seems to work in most cases, but not all. For instance, the line 7, 8 and 9 are correct, however the line 10 is a fail, since the projection doesn't reach the name of the product on the left (which is then considered as line 13).

Even more obvious is the “TTC” at the bottom right, line 29. Google's API failed to detect that the text is rotated, and so it's detected as belonging to “Informations” at the left, instead of “TVA” on line 30. Similarly, lines 33 and 34 are tangled, so the lines for the text on the right is completely wrong.

While I could adjust the algorithm to work well for this particular illustration (and fix the obvious bugs, like the third price at the top being split: the first two digits are on line 10, but the last one, abnormally, is marked as being on line 13), it seems tedious and it will stop working for other cases. I don't believe small adjustments like that is the correct way to solve the problem.

Is there a standard way of solving those types of problems? I suppose that artificial intelligence could be a possible alternative here, but I'm unsure what should be the inputs for the AI to be trained. Anything else could be done?

Answer 1

The ideas of the two commenters is by and large your best bet, because it relies on some kind of normalization, which is the typical way such problems are treated. Because of the "heuristic" nature of the problem you are solving (OCR), noise (of all sorts) can always bring you trouble, so the least you can do is ensure that your input is as close to the "canonical" input as possible.

Some ideas:

• You can pre-process all images and rectify them. For this, you are going to need a couple of fiducial markers to perform a rubber-sheet transformation (though any kind of general warping will do).

• As a much simpler alternative, you could determine the rotation of the bounding box of the receipt. Then rotate the entire image (from the top left corner of this bounding box, i.e. with respect to the bounding box of the receipt). This is a good first step to somewhat restore apparent orthogonality. Then perform OCR again. Otherwise, you can rotate the already determined text boxes, but always with respect to an origin at the top left corner of the receipt boundary (or top right, but generally, a point ON the boundary).

• If you need a pattern to match, remember the barcode, which has a fairly standard shape. You can have an exemplary image of a receipt (with perfect orthogonal alignment and all) and use feature matching to determine the transformation from any image to this base "ground-truth" image and warp accordingly. Here is an example of someone that wanted to do exactly that. This MATLAB example also does that, so maybe you can find some way to adapt or borrow from these examples (depending on what you use). I expect the feature matching algorithms to find the matching barcode feature relatively well.

• You can keep doing what you already do, but instead of projecting based on the text-box rotation, you can project perpendicularly to the receipt bounding box. This will result in a better "intrinsic" sense of alignment (i.e. with respect to the image, not the OCR detected text alignment). This is similar to an imaginary scanline running downwards from the top of the receipt to the bottom. At each position, whatever is intersected "should" belong to the same row. Of course, this is still like making small adjustments to cover all cases "as they come", so this is still not a very robust solution.