Click here to Skip to main content
13,293,369 members (43,986 online)
Click here to Skip to main content
Add your own
alternative version

Stats

12.1K views
847 downloads
17 bookmarked
Posted 1 Nov 2015

Automatic Skew Correction of Scanned Documents

, 1 Nov 2015
Rate this:
Please Sign up or sign in to vote.
Simple and fast skew correction of scan docs in C#

Usually scanned and photographed documents are skewed.

I would like to get rid of these skews, and do it by a simple and fast way, without heavy-weight libraries like OpenCV, AForge, etc.

Idea of the Algorithm

Let's divide the original image into vertical strips and calculate the average brightness of the pixels in each line of each strip:

Each line of text leaves a characteristic dark line. If there was no skew, the dark lines in the right strip would coincide with the lines in the left strip. But as a result of the skew, lines are shifted:

Now, if we found such a shift, in which the maximum number of lines in strips coincide, we can calculate the angle of original image to remove skew.

Required shifting can be found if we shift one of the strips on 1, 2, 3, etc. pixels by vertical and calculate the correlation coefficient between the strips (intercorrelation function). Where the correlation reaches the maximum value - the shifting is optimal.

Implementation

Firstly, it is necessary to find the average values of the pixels in the vertical strips of the source image. It is a time-consuming task because the source image can be large, and enumeration of all pixels - a long process.

To do this quickly, we make the trick - use the built-in GDI+ mechanism. We will create a new bitmap whose height is equal to the height of the original image, and the width - equals 2 pixels.

So, we draw the source image on the new bitmap, compressing the image horizontally to 2 pixels:

using (var bmp = new Bitmap(2, sourceImage.Height))
using (var gr = Graphics.FromImage(bmp))
{
    gr.InterpolationMode = InterpolationMode.Low;
    gr.DrawImage(sourceImage, 0, 0, 2, sourceImage.Height);
    ...
}

Because GDI+ uses interpolation when decreasing the width of image, each pixel of the new bitmap will be equal to average of pixel values for each line of each strip.

As the quality of interpolation does not matter, we choose the fastest interpolation mode - InterpolationMode.Low.

At this stage, the image can be a little compressed also vertically to reduce the length of the strips and to increase performance of further calculations.

Next, we need to move the brightness of found pixels in an array int[] for each strip. To do this, use method Bitmap.LockBits for fast access to pixels. The brightness of the pixel can be calculated by Color.GetBrightness(), but I used a faster analog - just take the green color channel Color.G as brightness.

After we received the averaged strips, we will calculate cross-correlation function between the two:

var sum = 0;

for (int i = 0; i < strip1.Length - shift; i++)
    sum += -Math.Abs(strip1[i] - strip2[i + shift]);

Instead of classical correlations, I simply use the sum of absolute differences between strips. It is faster and produces better results.

After these calculations for different values of offset, we will find a shift, where the correlation reaches the maximum.

Now we need only to find the angle of rotation. To do this, we create a vector between the centers of the strips, taking into account the found shift. The horizontal distance between the centers of the strips will:

var dx = sourceImage.Width / 2;
var dy = shift;

Now we can find the angle of rotation:

var angle = Math.Atan2(dy, dx);

Finally, we rotate the source image:

var rotated = new Bitmap(sourceImage.Width, sourceImage.Height);

using (var gr = Graphics.FromImage(rotated))
{
    gr.InterpolationMode = InterpolationMode.HighQualityBicubic;
    gr.TranslateTransform(sourceImage.Width / 2, sourceImage.Height / 2);
    gr.RotateTransform(-(float)angle);
    gr.DrawImage(sourceImage, -sourceImage.Width / 2, -sourceImage.Height / 2, 
			sourceImage.Width, sourceImage.Height);
}

I use the highest level of interpolation InterpolationMode.HighQualityBicubic. It makes the rotation more slowly, but we get perfect quality of the result image.

Save the image to a file. Enjoy.

Remarks

Above, I've described a simplified implementation. But the real code is a bit more complicated:

  1. Actually the image is divided in 10 strips (not 2). The narrower the strip, the more accurate we can calculate the offset.
  2. To find the most accurate results, I compare several pairs of strips. It allows to avoid the unsuccessful cases, when the strip gets into an empty area of the document.
  3. The shift is searched both up and down.
  4. To increase performance, when calculating the strips, the original image is compressed to 600 pixels vertically (or less).
  5. The most time consuming operation - turn the original image by a predetermined angle. In order to do this quickly - you can either reduce the size of the original image or reduce the quality of interpolation.
  6. This algorithm is not designed for keystone correction (perspective distortion, for example).

Results

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Pavel Torgashov
Software Developer Freelancer
Ukraine Ukraine
I am Pavеl Tоrgаshоv, and I live in Kyiv, Ukraine.
I've been developing software since 1998.
Main activities: processing of large volumes of data, statistics, computer vision and graphics.

You may also be interested in...

Pro
Pro

Comments and Discussions

 
GeneralThanks! Pin
thiggs38311-Nov-16 14:49
memberthiggs38311-Nov-16 14:49 
QuestionThanks for sharing! Pin
Member 1254020920-Sep-16 22:23
memberMember 1254020920-Sep-16 22:23 
QuestionI vote 5, bravo Pin
PCMF28-Apr-16 2:09
memberPCMF28-Apr-16 2:09 
QuestionHow can i save the rotated image as same image size Pin
compvelo10-Feb-16 13:59
membercompvelo10-Feb-16 13:59 
GeneralMy vote of 5 Pin
Igor Ladnik3-Nov-15 2:56
professionalIgor Ladnik3-Nov-15 2:56 
QuestionOCR Pin
kiquenet.com2-Nov-15 10:50
memberkiquenet.com2-Nov-15 10:50 
QuestionSimple & elegant, as usual Pin
A.J.Wegierski2-Nov-15 4:23
memberA.J.Wegierski2-Nov-15 4:23 
QuestionFourier Pin
Tomaž Štih1-Nov-15 23:42
memberTomaž Štih1-Nov-15 23:42 
AnswerRe: Fourier Pin
Pavel Torgashov2-Nov-15 0:29
memberPavel Torgashov2-Nov-15 0:29 
QuestionClever! Pin
Chris Maunder1-Nov-15 17:55
adminChris Maunder1-Nov-15 17:55 
AnswerRe: Clever! Pin
Pavel Torgashov1-Nov-15 22:03
memberPavel Torgashov1-Nov-15 22:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.171207.1 | Last Updated 2 Nov 2015
Article Copyright 2015 by Pavel Torgashov
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid