'Algorithm for straightening tilted document

I'm on a project involving OCR. After detecting each character, I need to combine close characters to create words. To do that I tried to create a priority queue, containing information about detected characters (the set of pixels forming the character and the position of the character on the document image), and gave higher priority to characters on top of the document, and higher to the leftmost character if two characters are on the same line. Then poll the characters out of the priority queue one after another, hoping that it would give me all the characters form left to right and up to bottom, and build words based on space between each two consequent characters. Which actually failed when the document is even slightly tilted, since some characters who are obviously on the same line for human eye are not necessarily on the same pixel height (with 5~10px threshold).

Is there any algorithm for autostraightening the document? or detecting the tilt angle? Or any library for that? Or if not, is there a way to work around this issue? It's my final year project and I have a very less time to fix this. Please help. Thanks.

algorithmcomputer-visionartificial-intelligenceocrdocument


Solution 1:[1]

If the skew and interline spacing are such that the text lines can always be separated by horizontals, it suffices to sort using a special comparison rule:

  • if the bottom of A is above the top of B, then A precedes B, and conversely;

  • else if some point in A is to the left of some point in B, then A precedes B, and conversely.

If the skew is too large, you will need to isolate the individual lines. A way is to find the close left/right neighbors of every character, and form chains. Characters in a chain are sorted by abscissa.

When the skew is very large and the interline tiny, I know of no easy and bulletproof solution.

Solution 2:[2]

I believe 2D Fourier Transform can help here:

  1. smooth the document with radius comparable to character size
  2. perform Fourier Transform
  3. analyse spectrum

I would expect strong components to correspond to vertical direction and weaker components - to the horizontal. Also knowing line distance could limit area of analysis and improve accuracy.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 maxim1000

Related Questions