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 robu st even when black margins introduced by photocopying are present in t he image and when the document is scanned at a low resolution of 50 dp i. The algorithm consists of two steps. In the first step we quickly e xtract the centroids of connected components using a graph data struct ure. Then, a hierarchical Hough transform (at two different angular re solutions) is applied to the selected centroids. The skew angle corres ponds to the location of the highest peak in the Hough space. The perf ormance of the algorithm is shown on a number of document images colle cted from various application domains. The algorithm is not very sensi tive to algorithmic parameters. For an A4 size document image scanned at 50 dpi (typically 413 x 575 pixels), our algorithm is able to detec t the skew angle with an accuracy of 0.1 degrees in 0.4s of CPU time o n a SunSparc 20 workstation. Copyright (C) 1996 Pattern Recognition So ciety.