Skew Detection and Correction

Our recognition algorithm relies on the characters of a page being oriented correctly, for this reason detection and correction of any skew the page may have been scanned at is vital. Fateman has done some work in this area.

Skew Detection

There are several commonly used methods for detecting skew in a page, some rely on detecting connected components (for many purposes, they are roughly equivalent to characters) and finding the average angles connecting their centroids. The method we employed (after observing it in Fateman's program) was to project the page at several angles, and determine the variance in the number of black pixels per projected line.

The projetion parallel to the true alignment of the lines will likely have the the maximum variance, since when parallel, each given ray projected through the image will hit either almost no black pixels (as it passes between text lines) or many black pixels (while passing through many characters in sequence).

Sample image and a projection parallel to its text.

Oblique projections will commonly pass both through lines of text, and spaces between lines, the variance in the number of pixels hit by the individual rays will thus be smaller than in the parallel case.

Sample image and an oblique projection. Notice the uniform nature of the distribution

After detecting the skew, it is necessary to correct for it.

Skew Correction

After the skew angle of the page has been detected, our recognition algorithm demands that the page must be rotated to correct for this skew. Our rotation algorithm had to be both fairly fast and fairly accurate. We looked into two strategies for correcting slight skews in scanned images. The first was a pure coordinate transformation, which takes a little bit of time on large images, but gets the rotation exact. The next was somewhat less accurate, but faster (with the proper data structures) and works pretty well with slight skews that are common in scanned images. The second method uses two shears to achieve its result. Our final choice was the coordinate rotation, since we were focusing more on accuracy than speed and the this method was not horrendously slow.

An almost working rotation:
=>