Fast Image Rotation For .NET Compact Framework

• Download source - 54 KB

Introduction

When I was writing an application for another article, I ran into some problems when trying to rotate an image. The application I was writing was a .NET Compact Framework application and I realized that the method that I would use on the normal .NET Framework, Image.RotateFlip, is not implemented on the Compact Framework.

This article will describe how I implemented an image rotate method and the optimizations I had to come up with to get the performance I wanted.

Using the Code

The article source code is a solution containing a class library and a test application, both are for the .NET Compact Framework but they should compile under the normal .NET Framework if the source files are moved into such projects.

Requirements

My code was dealing with rotating photos that had been taken when the camera/device was held at an angle (taking portrait instead of landscape pictures) and therefore the rotation algorithm required only had to deal with angles such as 90, 180 and 270 degrees. This is the same as is provided by the Image.RotateFlip method in the normal .NET Compact Framework (this method actually also allow you to flip the image but my application had no need for that so I didn't implement that part).

The requirement for this class library is therefore quite simple (simple to define that is, not necessarily to implement):

• It must be possible to rotate an image by 90, 180 and 270 degrees.

Rotating an Image

The only way I can come up with when rotating an image is to go pixel by pixel and translate the pixel location from the source image to a location in the destination image. So for a 2 by 3 pixel image that's being rotated by 90 degrees, the translation would look something like this:

This mapping expressed in x, y coordinates would be:

Source X	Source Y	Destination X	Destination Y
0	0	0	1
1	0	0	0
0	1	1	1
1	1	1	0
0	2	2	1
1	2	2	0

A pattern emerges!

In code, this pattern can be expressed as:

int destinationX = rotatedImageWidth - 1 - sourceY;
int destinationY = sourceX;    

The patterns for 180 and 270 degrees differs slightly but follows the same principle.

Grabbing Pixels

So now we know where each pixel from the source image goes on the destination image after rotation, all we need to do now is to iterate over all the pixels and grab the Color from the source and apply it to the destination. So how do we do that? It's actually really easy as System.Drawing.Bitmap has methods for this:

for (int y = 0; y < sourceImage.Height; ++y)
{
    for (int x = 0; x < sourceImage.Width; ++x)
    {
        destinationImage.SetPixel(
            sourceImage.Width - 1 - y, 
            x, 
            originalBitmap.GetPixel(x, y));
    }
}

And that's it basically, this will rotate our image by 90 degrees.
So I implemented my rotation function to do that and tested it on an image that was 800 by 600 pixels and nothing happened! I went over the code but couldn't find anything so I did what I normally do; I tried again. Nothing. So I went to get some coffee instead. My implementation contained code that timed how long the rotation took, I did this from the start as I expected it to be rather slow, and when I got back with my cup of coffee the image was rotated, elapsed time 2m 53s. Not very fast at all and much slower than I had expected.

I decided that I needed to optimize my method.

First Level of Optimization

I started optimizing the easy parts and hoping (but not actually believing) that it would speed up my algorithm enough for the method to run at a decent speed.
I pre-calculated as much as possible. Since I would need the value sourceImage.Width - 1 for each pixel but the value is the same for the entire rotation, I moved that part outside the loop.

// Pre-calculated
int sourceImageWidthMinusOne = sourceImage.Width - 1;
for (int y = 0; y < sourceImage.Height; ++y)
{
    for (int x = 0; x < sourceImage.Width; ++x)
    {
        destinationImage.SetPixel(
            sourceImageWidthMinusOne - y, 
            x, 
            originalBitmap.GetPixel(x, y));
    }
}

I also tried to remove any method calls by storing the result from the .Width and .Height calls outside of the loop. This should speed up things as there were now sourceImage.Width times sourceImage.Height less methods being called (properties are methods too, remember).

// Pre-stored
int sourceImageWidth = sourceImage.Widht;
int sourceImageHeight = sourceImage.Height;
// Pre-calculated
int sourceImageWidthMinusOne = sourceImageWidth - 1;

for (int y = 0; y < sourceImageHeight; ++y)
{
    for (int x = 0; x < sourceImageWidth; ++x)
    {
        destinationImage.SetPixel(
            sourceImageWidthMinusOne - y, 
            x, 
            originalBitmap.GetPixel(x, y));
    }
}

After these awesome optimizations, I re-ran my test application.
Result: Image rotated in 2m 45s. Hardly worth the effort.

Since my lightweight optimization attack had failed, it was time to bring out the big guns. And by big guns, I mean pointers. And unsafe code.

Second Level of Optimization

Since getting and setting pixels using the methods provided by Bitmap is all too slow, I needed some other way of getting to that data. It is possible to get to the pixel data in a rather low-level way by getting a BitmapData object from the Bitmap. There's a method, Bitmap.LockBits that "locks" the bits representing the pixels into system memory and returns a BitmapData object.

// original here means source
// rotated here means destination
BitmapData originalData = originalBitmap.LockBits(
    new Rectangle(0, 0, originalWidth, originalHeight), 
    ImageLockMode.ReadOnly, 
    PixelFormat.Format32bppRgb);

BitmapData rotatedData = rotatedBitmap.LockBits(
    new Rectangle(0, 0, rotatedBitmap.Width, rotatedBitmap.Height), 
    ImageLockMode.WriteOnly, 
    PixelFormat.Format32bppRgb);

You have to specify an ImageLockMode when locking the bits and I use a read-only lock for the source (since I'm only going to read the pixels) and a write-only lock for the destination (since I need to write but not read those pixels).
Also, you have to specify a PixelFormat, I hardcoded this to PixelFormat.Format32bppRgb which means that my code only works on images of 32 bits per pixel. Watch out for that if you're running into problems with this code.

Once the bits are locked, it is possible to get a pointer to the first pixel data by calling BitmapData.ScanO which returns an IntPtr, but I intended to use pointer-arithmetic to speed up the processing so simply having a IntPtr wouldn't do, I needed an int*. By having a "proper" pointer I can (more or less) do whatever I want, and at blazing speeds!

The "proper" pointers are gotten like this:

unsafe
{
    int* originalPointer = (int*)originalData.Scan0.ToPointer();
    int* rotatedPointer = (int*)rotatedData.Scan0.ToPointer();
}

Notice the use of the unsafe keyword, since having a "proper" pointer will let me do just about anything to the memory, it is considered "unsafe" and therefore you'll have to explicitly tell the compiler that this is your intention (you also have to allow unsafe code in the project properties).

With my proper pointer I can easily manipulate the memory where the pixel data is held and my image rotation code now looks like this:

for (int y = 0; y < originalHeight; ++y)
{
    int destinationX = newWidthMinusOne - y;
    for (int x = 0; x < originalWidth; ++x)
    {
        int sourcePosition = (x + y * originalWidth);
        int destinationY = x;
        int destinationPosition = (destinationX + destinationY * newWidth);

        // Here I read and assign the pixel value
        rotatedPointer[destinationPosition] = originalPointer[sourcePosition];
    }
}

It is important to release the lock you have acquired on the bits, this is done after all the rotation is complete:

// We have to remember to unlock the bits when we're done.
originalBitmap.UnlockBits(originalData);
rotatedBitmap.UnlockBits(rotatedData);

And those are all the optimizations I could think of at that time, the complete rotation function now looked like this:

private static void InternalRotateImage(int rotationAngle, 
                                        Bitmap originalBitmap, 
                                        Bitmap rotatedBitmap)
{
    // It should be faster to access values stored on the stack
    // compared to calling a method (in this case a property) to 
    // retrieve a value. That's why we store the width and height
    // of the bitmaps here so that when we're traversing the pixels
    // we won't have to call more methods than necessary.

    int newWidth = rotatedBitmap.Width;
    int newHeight = rotatedBitmap.Height;

    int originalWidth = originalBitmap.Width;
    int originalHeight = originalBitmap.Height;

    // We're going to use the new width and height minus one a lot so lets 
    // pre-calculate that once to save some more time
    int newWidthMinusOne = newWidth - 1;
    int newHeightMinusOne = newHeight - 1;

    // To grab the raw bitmap data into a BitmapData object we need to
    // "lock" the data (bits that make up the image) into system memory.
    // We lock the source image as ReadOnly and the destination image
    // as WriteOnly and hope that the .NET Framework can perform some
    // sort of optimization based on this.
    // Note that this piece of code relies on the PixelFormat of the 
    // images to be 32 bpp (bits per pixel). We're not interested in 
    // the order of the components (red, green, blue and alpha) as 
    // we're going to copy the entire 32 bits as they are.
    BitmapData originalData = originalBitmap.LockBits(
        new Rectangle(0, 0, originalWidth, originalHeight), 
        ImageLockMode.ReadOnly, 
        PixelFormat.Format32bppRgb);
    BitmapData rotatedData = rotatedBitmap.LockBits(
        new Rectangle(0, 0, rotatedBitmap.Width, rotatedBitmap.Height), 
        ImageLockMode.WriteOnly, 
        PixelFormat.Format32bppRgb);

    // We're not allowed to use pointers in "safe" code so this
    // section has to be marked as "unsafe". Cool!
    unsafe
    {
        // Grab int pointers to the source image data and the 
        // destination image data. We can think of this pointer
        // as a reference to the first pixel on the first row of the 
        // image. It's actually a pointer to the piece of memory 
        // holding the int pixel data and we're going to treat it as
        // an array of one dimension later on to address the pixels.
        int* originalPointer = (int*)originalData.Scan0.ToPointer();
        int* rotatedPointer = (int*)rotatedData.Scan0.ToPointer();

        // There are nested for-loops in all of these case statements
        // and one might argue that it would have been neater and more
        // tidy to have the switch statement inside the a single nested
        // set of for loops, doing it this way saves us up to three int 
        // to int comparisons per pixel. 
        //
        switch (rotationAngle)
        {
            case 90:
                for (int y = 0; y < originalHeight; ++y)
                {
                    int destinationX = newWidthMinusOne - y;
                    for (int x = 0; x < originalWidth; ++x)
                    {
                        int sourcePosition = (x + y * originalWidth);
                        int destinationY = x;
                        int destinationPosition = 
                                (destinationX + destinationY * newWidth);
                        rotatedPointer[destinationPosition] = 
                            originalPointer[sourcePosition];
                    }
                }
                break;
            case 180:
                for (int y = 0; y < originalHeight; ++y)
                {
                    int destinationY = (newHeightMinusOne - y) * newWidth;
                    for (int x = 0; x < originalWidth; ++x)
                    {
                        int sourcePosition = (x + y * originalWidth);
                        int destinationX = newWidthMinusOne - x;
                        int destinationPosition = (destinationX + destinationY);
                        rotatedPointer[destinationPosition] = 
                            originalPointer[sourcePosition];
                    }
                }
                break;
            case 270:
                for (int y = 0; y < originalHeight; ++y)
                {
                    int destinationX = y;
                    for (int x = 0; x < originalWidth; ++x)
                    {
                        int sourcePosition = (x + y * originalWidth);
                        int destinationY = newHeightMinusOne - x;
                        int destinationPosition = 
                            (destinationX + destinationY * newWidth);
                        rotatedPointer[destinationPosition] = 
                            originalPointer[sourcePosition];
                    }
                }
                break;
        }

        // We have to remember to unlock the bits when we're done.
        originalBitmap.UnlockBits(originalData);
        rotatedBitmap.UnlockBits(rotatedData);
    }
}

The reason that the method is declared as:

private static void InternalRotateImage(...)    

instead of the perhaps more logical and useful:

 public static Image RotateImage(...)    

is because my class library contains two implementations, both the fast unsafe and the slow safe version, and which one to use is decided at compile-time using a pre-processor directive. You might wonder why I went with a pre-processor directive to determine which implementation to use instead of for example a boolean parameter (bool useFastVersion). If you want your assembly to be marked as safe no unsafe code may exist in it, regardless of whether it's being called or not. That is why a pre-processor directive is required.

Final Result

So how did the implementation turn out?

First of all, looking at the one requirement I had to implement, the class library is able to rotate an image at 90, 180 and 270 degrees. That means that all my requirements were fulfilled. Great!

But since most of this article has been about optimizations you might wonder how fast the final implementation is, and I'm pleased to say it's actually quite fast. It no longer takes minutes to rotate the image, an image of 800 by 600 pixels is rotated in less then 5 seconds now. And often it's less than 3 seconds. That's quite acceptable I think.

The test application lets you rotate an image resource and measures the time it takes and for the test image (410 by 312 pixels) the rotation time is no less than a second.

Points of Interest

I think the most interesting part of this implementation is the fact that it is possible to get decent speeds without having to resort to calling native code in some GDI library. I have nothing against using native DLLs but I find it neat and tidy when I can avoid it nonetheless.

All comments and suggestions are welcome.

History

• 2007-11-26: First version