How to determine edges in an image optimally?

Question

I recently was put in front of the problem of cropping and resizing images. I needed to crop the 'main content' of an image for example if i had an image similar to this:
_{(source: msn.com)}

the result should be an image with the msn content without the white margins(left& right).

I search on the X axis for the first and last color change and on the Y axis the same thing. The problem is that traversing the image line by line takes a while..for an image that is 2000x1600px it takes up to 2 seconds to return the CropRect => x1,y1,x2,y2 data.

I tried to make for each coordinate a traversal and stop on the first value found but it didn't work in all test cases..sometimes the returned data wasn't the expected one and the duration of the operations was similar..

Any idea how to cut down the traversal time and discovery of the rectangle round the 'main content'?

public static CropRect EdgeDetection(Bitmap Image, float Threshold)
        {
            CropRect cropRectangle = new CropRect();
            int lowestX = 0;
            int lowestY = 0;
            int largestX = 0;
            int largestY = 0;

            lowestX = Image.Width;
            lowestY = Image.Height;

            //find the lowest X bound;
            for (int y = 0; y < Image.Height - 1; ++y)
            {
                for (int x = 0; x < Image.Width - 1; ++x)
                {
                    Color currentColor = Image.GetPixel(x, y);
                    Color tempXcolor = Image.GetPixel(x + 1, y);
                    Color tempYColor = Image.GetPixel(x, y + 1);
                    if ((Math.Sqrt(((currentColor.R - tempXcolor.R) * (currentColor.R - tempXcolor.R)) +
                        ((currentColor.G - tempXcolor.G) * (currentColor.G - tempXcolor.G)) +
                        ((currentColor.B - tempXcolor.B) * (currentColor.B - tempXcolor.B))) > Threshold)) 
                    {
                        if (lowestX > x)
                            lowestX = x;

                        if (largestX < x)
                            largestX = x;
                    }

                    if ((Math.Sqrt(((currentColor.R - tempYColor.R) * (currentColor.R - tempYColor.R)) +
                        ((currentColor.G - tempYColor.G) * (currentColor.G - tempYColor.G)) +
                        ((currentColor.B - tempYColor.B) * (currentColor.B - tempYColor.B))) > Threshold))
                    {
                        if (lowestY > y)
                            lowestY = y;

                        if (largestY < y)
                            largestY = y;
                    }
                }                
            }

            if (lowestX < Image.Width / 4)
                cropRectangle.X = lowestX - 3 > 0 ? lowestX - 3 : 0;
            else
                cropRectangle.X = 0;

            if (lowestY < Image.Height / 4)
                cropRectangle.Y = lowestY - 3 > 0 ? lowestY - 3 : 0;
            else
                cropRectangle.Y = 0;

            cropRectangle.Width = largestX - lowestX + 8 > Image.Width ? Image.Width : largestX - lowestX + 8;
            cropRectangle.Height = largestY + 8 > Image.Height ? Image.Height - lowestY : largestY - lowestY + 8;
            return cropRectangle;
        }
    }

Answer 1

One possible optimisation is to use Lockbits to access the color values directly rather than through the much slower GetPixel.

The Bob Powell page on LockBits is a good reference.

On the other hand, my testing has shown that the overhead associated with Lockbits makes that approach slower if you try to write a GetPixelFast equivalent to GetPixel and drop it in as a replacement. Instead you need to ensure that all pixel access is done in one hit rather than multiple hits. This should fit nicely with your code provided you don't lock/unlock on every pixel.

Here is an example

BitmapData bmd = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, b.PixelFormat);

byte* row = (byte*)bmd.Scan0 + (y * bmd.Stride);

//                           Blue                    Green                   Red 
Color c = Color.FromArgb(row[x * pixelSize + 2], row[x * pixelSize + 1], row[x * pixelSize]);

b.UnlockBits(bmd);

Two more things to note:

1. This code is unsafe because it uses pointers
2. This approach depends on pixel size within Bitmap data, so you will need to derive pixelSize from bitmap.PixelFormat