12,546,997 members (57,397 online)
alternative version

142.9K views
94 bookmarked
Posted

# How to deskew an image

, 25 Apr 2006 CPOL
 Rate this:
The article describes an algorithm to calculate the skew angle of an image.

## Introduction

The following article describes an algorithm in VB.NET to deskew an image.

## Background

Deskewing an image can help a lot, if you want to do OCR, OMR, barcode detection, or just improve the readability of scanned images. For example, think of a camera that automatically takes photos of goods with a barcode. If the skew angle is too high, the barcode can not be detected. After deskewing, the barcode can be read.

Before deskewing:

After deskewing:

## Using the code

The following code determines the skew angle of the image `bmpIn`:

```Dim sk As New gmseDeskew(bmpIn)
Dim skewangle As Double = sk.GetSkewAngle
Dim bmpOut As Bitmap = RotateImage(bmpIn, -skewangle)```

## Points of interest

The basic idea of the algorithm is:

• Find reference lines in the image.
• Calculate the angle of the lines.
• Calculate the skew angle as an average of the angles.
• Rotate the image.

The lines are detected with the Hough algorithm. Each point in the image can lie on an infinite number of lines. To find the reference lines, we let each point vote for all the lines that pass through the point. The lines with the highest number of points are our reference lines.

First, we need the parameterization of a line. A line can be parameterized as:

`y = m*x+t`

with slope m and offset t. We are interested in the angle and not the slope. The angle alpha of the line satisfies:

`m=tan(alpha)=sin(alpha)/cos(alpha)`

We get:

`y=sin(alpha)/cos(alpha)*x+t`

Which is equivalent to:

`y*cos(alpha)-x*sin(alpha)=d`

We can not search an infinite parameter space, so we have to define a discrete one. We search for all lines with:

`-20<=alpha<=20`

in 0.2 steps, and we round d to an integer.

#### The basic algorithm in pseudo code:

```1. Create a two-dimensional matrix Hough and initialize the values with 0
2. for y=0 to Height-1
3.    for x=0 to Width-1
4.      if Point(x,y) is black then
5.        for alpha=-20 to 20 step 0.2
6.          d= Trunc(y*cos(alpha)-x*sin(alpha))
7.          Hough(Trunc(alpha*5),d)+=1
8.        next alpha
9.      end if
10.   next x
11. next y
12. Find the top 20 (alpha,d) pairs that have the highest count in the Hough matrix
13. Calculate the skew angle as an average of the alphas
14. Rotate the image by – skew angle```

The algorithm is computationally expensive. To save some time, the number of voting points is reduced. For each text line, you can draw many lines with different angles through the letters:

For deskewing, only the bottom line is important.

The points on the bottom line have a lower neighbour that is white. So, we only let points (x,y) vote that satisfy:

• The point (x,y) is black.
• The lower neighbour (x,y+1) is white.

## References

The article was taken from GMSE Imaging.

## History

• 03-30-06: Original article.
• 03-31-06: More explanations about the Hough algorithm.
• 04-25-06: Added the References section.

## Share

 Germany
No Biography provided

## You may also be interested in...

 Pro Pro

 First PrevNext
 thank u very much :) Member 1121113415-Apr-15 21:44 Member 11211134 15-Apr-15 21:44
 Translated to c# but images with less black lines go skew Jdarmanovich10-Feb-15 19:52 Jdarmanovich 10-Feb-15 19:52
 I am so appreciate it! marshell_w3-Feb-14 8:48 marshell_w 3-Feb-14 8:48
 Code in windows service error Member 983823212-Mar-13 7:44 Member 9838232 12-Mar-13 7:44
 It's really helpful! shimizu_masato29-Mar-12 22:41 shimizu_masato 29-Mar-12 22:41
 My vote of 5 manoj kumar choubey1-Mar-12 22:18 manoj kumar choubey 1-Mar-12 22:18
 My vote of 5 Johannes_Franke1-Feb-11 1:35 Johannes_Franke 1-Feb-11 1:35
 Re: My vote of 5 [modified] nguyenq112-Mar-11 14:57 nguyenq1 12-Mar-11 14:57
 Port to C++ Syd Logan10-Dec-09 23:18 Syd Logan 10-Dec-09 23:18
 Upload souce code Deskew, Visual C++ or C#, Please ? lung_tung_chuong_IT25-Nov-09 10:28 lung_tung_chuong_IT 25-Nov-09 10:28
 Java port of this deskew code now available! Roland Quast24-Oct-09 3:33 Roland Quast 24-Oct-09 3:33
 This is excellent and it works in grayscale images at 300dpi daelin24-Jul-09 5:42 daelin 24-Jul-09 5:42
 Just so I understand TheGuy20-Mar-09 7:06 TheGuy 20-Mar-09 7:06
 A note on full page scanning smartyP11-Feb-09 4:59 smartyP 11-Feb-09 4:59
 How to run nanni_n25-Feb-08 22:11 nanni_n 25-Feb-08 22:11
 Performances lucapan11-Oct-07 5:58 lucapan 11-Oct-07 5:58
 Re: Performances nanni_n25-Feb-08 22:08 nanni_n 25-Feb-08 22:08
 Re: Performances defwebserver20-Apr-08 12:59 defwebserver 20-Apr-08 12:59
 Re: Performances lucapan18-Oct-09 21:47 lucapan 18-Oct-09 21:47
 gr8 work but ... looka730-Mar-07 22:21 looka7 30-Mar-07 22:21
 Nice work karulont28-Mar-07 3:56 karulont 28-Mar-07 3:56
 Re: Nice work Vimmi2616-Aug-08 13:26 Vimmi261 6-Aug-08 13:26
 circular hough transfrom shdelpiero23-Feb-07 12:36 shdelpiero 23-Feb-07 12:36
 Renuka Member #369869024-Jan-07 17:45 Member #3698690 24-Jan-07 17:45
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Oct-16 21:59 Refresh 12 Next »