A robust and fast skew detection algorithm for generic documents

A robust and fast skew detection algorithm based on hierarchical Hough transform is proposed. It is capable of detecting the skew angle for various document images, including technical articles, postal labels, handwritten text, forms, drawings and bar codes. The algorithm is robust even when black margins introduced by photocopying are present in the image and when the document is scanned at a low resolution of 50 dpi. The algorithm consists of two steps. In the first step we quickly extract the centroids of connected components using a graph data structure. Then, a hierarchical Hough transform (at two different angular resolutions) is applied to the selected centroids. The skew angle corresponds to the location of the highest peak in the Hough space. The performance of the algorithm is shown on a number of document images collected from various application domains. The algorithm is not very sensitive to algorithmic parameters. For an A4 size document image scanned at 50 dpi (typically 413 x 575 pixels), our algorithm is able to detect the skew angle with an accuracy of 0.1 degrees in 0.4s of CPU time on a SunSparc 20 workstation. Copyright (C) 1996 Pattern Recognition Society.