13,629,890 members
Tip/Trick
alternative version

Stats

16.4K views
20 bookmarked
Posted 1 Nov 2015
Licenced GPL3

Automatic Skew Correction of Scanned Documents

, 1 Nov 2015
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).

Share

 Software Developer Freelancer 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

 First Prev Next
 Thanks! thiggs38311-Nov-16 13:49 thiggs383 11-Nov-16 13:49
 Thanks for sharing！ Member 1254020920-Sep-16 21:23 Member 12540209 20-Sep-16 21:23
 I vote 5, bravo PCMF28-Apr-16 1:09 PCMF 28-Apr-16 1:09
 How can i save the rotated image as same image size compvelo10-Feb-16 12:59 compvelo 10-Feb-16 12:59
 OCR kiquenet.com2-Nov-15 9:50 kiquenet.com 2-Nov-15 9:50
 Simple & elegant, as usual A.J.Wegierski2-Nov-15 3:23 A.J.Wegierski 2-Nov-15 3:23
 Fourier Tomaž Štih1-Nov-15 22:42 Tomaž Štih 1-Nov-15 22:42
 Re: Fourier Pavel Torgashov1-Nov-15 23:29 Pavel Torgashov 1-Nov-15 23:29
 Clever! Chris Maunder1-Nov-15 16:55 Chris Maunder 1-Nov-15 16:55
 Re: Clever! Pavel Torgashov1-Nov-15 21:03 Pavel Torgashov 1-Nov-15 21:03
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Jul-18 0:07 Refresh 1