Efficient ways to determine tilt of an image

Question

I'm trying to write a program to programmatically determine the tilt or angle of rotation in an arbitrary image.

Images have the following properties:

• Consist of dark text on a light background
• Occasionally contain horizontal or vertical lines which only intersect at 90 degree angles.
• Skewed between -45 and 45 degrees.
• See this image as a reference (its been skewed 2.8 degrees).

So far, I've come up with this strategy: Draw a route from left to right, always selecting the nearest white pixel. Presumably, the route from left to right will prefer to follow the path between lines of text along the tilt of the image.

Here's my code:

private bool IsWhite(Color c) { return c.GetBrightness() >= 0.5 || c == Color.Transparent; }

private bool IsBlack(Color c) { return !IsWhite(c); }

private double ToDegrees(decimal slope) { return (180.0 / Math.PI) * Math.Atan(Convert.ToDouble(slope)); }

private void GetSkew(Bitmap image, out double minSkew, out double maxSkew)
{
    decimal minSlope = 0.0M;
    decimal maxSlope = 0.0M;
    for (int start_y = 0; start_y < image.Height; start_y++)
    {
        int end_y = start_y;
        for (int x = 1; x < image.Width; x++)
        {
            int above_y = Math.Max(end_y - 1, 0);
            int below_y = Math.Min(end_y + 1, image.Height - 1);

            Color center = image.GetPixel(x, end_y);
            Color above = image.GetPixel(x, above_y);
            Color below = image.GetPixel(x, below_y);

            if (IsWhite(center)) { /* no change to end_y */ }
            else if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
            else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
        }

        decimal slope = (Convert.ToDecimal(start_y) - Convert.ToDecimal(end_y)) / Convert.ToDecimal(image.Width);
        minSlope = Math.Min(minSlope, slope);
        maxSlope = Math.Max(maxSlope, slope);
    }

    minSkew = ToDegrees(minSlope);
    maxSkew = ToDegrees(maxSlope);
}

This works well on some images, not so well on others, and its slow.

Is there a more efficient, more reliable way to determine the tilt of an image?

Answer 1

If text is left (right) aligned you can determine the slope by measuring the distance between the left (right) edge of the image and the first dark pixel in two random places and calculate the slope from that. Additional measurements would lower the error while taking additional time.

Answer 2

GetPixel is slow. You can get an order of magnitude speed up using the approach listed here.

Answer 3

First I must say I like the idea. But I've never had to do this before and I'm not sure what all to suggest to improve reliability. The first thing I can think of this is this idea of throwing out statistical anomalies. If the slope suddenly changes sharply then you know you've found a white section of the image that dips into the edge skewing (no pun intended) your results. So you'd want to throw that stuff out somehow.

But from a performance standpoint there are a number of optimizations you could make which may add up.

Namely, I'd change this snippet from your inner loop from this:

Color center = image.GetPixel(x, end_y);
Color above = image.GetPixel(x, above_y);
Color below = image.GetPixel(x, below_y);

if (IsWhite(center)) { /* no change to end_y */ }
else if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }

To this:

Color center = image.GetPixel(x, end_y);

if (IsWhite(center)) { /* no change to end_y */ }
else
{
    Color above = image.GetPixel(x, above_y);
    Color below = image.GetPixel(x, below_y);
    if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
    else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
}

It's the same effect but should drastically reduce the number of calls to GetPixel.

Also consider putting the values that don't change into variables before the madness begins. Things like image.Height and image.Width have a slight overhead every time you call them. So store those values in your own variables before the loops begin. The thing I always tell myself when dealing with nested loops is to optimize everything inside the most inner loop at the expense of everything else.

Also... as Vinko Vrsalovic suggested, you may look at his GetPixel alternative for yet another boost in speed.

Answer 4

At first glance, your code looks overly naive. Which explains why it doesn't always work.

I like the approach Steve Wortham suggested, but it might run into problems if you have background images.

Another approach that often helps with images is to blur them first. If you blur your example image enough, each line of text will end up as a blurry smooth line. You then apply some sort of algorithm to basically do a regression analisys. There's lots of ways to do that, and lots of examples on the net.

Edge detection might be useful, or it might cause more problems that its worth.

By the way, a gaussian blur can be implemented very efficiently if you search hard enough for the code. Otherwise, I'm sure there's lots of libraries available. Haven't done much of that lately so don't have any links on hand. But a search for Image Processing library will get you good results.

I'm assuming you're enjoying the fun of solving this, so not much in actual implementation detalis here.

Answer 5

Measuring the angle of every line seems like overkill, especially given the performance of GetPixel.

I wonder if you would have better performance luck by looking for a white triangle in the upper-left or upper-right corner (depending on the slant direction) and measuring the angle of the hypotenuse. All text should follow the same angle on the page, and the upper-left corner of a page won't get tricked by the descenders or whitespace of content above it.

Another tip to consider: rather than blurring, work within a greatly-reduced resolution. That will give you both the smoother data you need, and fewer GetPixel calls.

For example, I made a blank page detection routine once in .NET for faxed TIFF files that simply resampled the entire page to a single pixel and tested the value for a threshold value of white.

Answer 6

Your latest output is confusing me a little. When you superimposed the blue lines on the source image, did you offset it a bit? It looks like the blue lines are about 5 pixels above the centre of the text.

Not sure about that offset, but you definitely have a problem with the derived line "drifting" away at the wrong angle. It seems to have too strong a bias towards producing a horizontal line.

I wonder if increasing your mask window from 3 pixels (centre, one above, one below) to 5 might improve this (two above, two below). You'll also get this effect if you follow richardtallent's suggestion and resample the image smaller.

Answer 7

What are your constraints in terms of time?

The Hough transform is a very effective mechanism for determining the skew angle of an image. It can be costly in time, but if you're going to use Gaussian blur, you're already burning a pile of CPU time. There are also other ways to accelerate the Hough transform that involve creative image sampling.