# Voting-Based Document Image Skew Detection
## 2 Skew Detection Algorithms
### Spatial Domain Lines  
#### 2.3.1 Mechanism  
This method uses horizontal and vertical lines in the document detected via the Hough transform [28] to compute the skew angle. We look for both vertical and especially for horizontal lines, which are most likely to be detected within lines of text. The skew angle is computed as a weighted sum of angles given by the detected lines. For the summation, these angles are weighted by properties of the lines. The algorithm performs best when there are long lines in the document, such as tables and separators.  
First, the Sobel [29] edge detection filter is applied, in order to empty the interior of the connected components. This prepares the image for the line detection procedure, eliminating shape filling pixels from being accounted in the line search procedure.  
After we apply the probabilistic Hough transform, we are left with a set of line segments, each one representing some vertical or horizontal separator, some line of a table, some line in an image, a line of text, or some line emerging at a random angle from within the placement of the symbols, randomly cutting through a block of text. The former must have discarded, as it does not represent the orientation of the document. Thus, we must sort the obtained segments by some criteria. Lines outside SASS are discarded.  
We take all pairs of segments and build an adjacency matrix which contains one in the cell [i,j] if line i and line j may be considered parallel and zero otherwise. Two lines are considered parallel if the absolute value of the dot product of their support unit vectors is greater than one minus some small threshold \(\varepsilon\). The computed dot products are also saved in a matrix for later use.  
We partition all segments into disjoint sets, each set containing lines claimed to be parallel, i.e., for any pair of lines within a set, the adjacency matrix has a value of \(1\). For this step, an optimized disjoint sets union-find data structure is used, with path compression for the find operation and union by size heuristics. For every resulting set of parallels, we compute an average line, referred to as the set representative, which gives the orientation of the set.  
If all line segments are in one set, then the returned skew angle is equal to the angle between the representative line of the set and the closest primary axis.  
If there is more than one set, we sort the sets descending by the sum of their segments' length and pick the first three or four sets (or two, if there are only two sets) as candidates for the horizontal and vertical axes of the document. If two of the sets have representatives that can be considered perpendicular, then the representatives will be picked as the document's horizontal and vertical axes and the skew angle is computed as a weighted sum of the angles each representative makes with the closest primary axis. If there are no perpendicular representatives, then the first set in the sorted candidates is picked as the horizontal or vertical axis of the document, depending on the angle it makes with the primary axes.  
In Figure 6, document orientation axes are shown passing through the center of processed images (black background), and for some images (e.g., the three rightmost images) only one axis was detected.