Need an efficient C/C++ code for rotating an image

see also
http://www.codeproject.com/bitmap/rotatebyshear.asp

ozo,
Thanks for your comment, but what I'm looking for, is the following:
Rotating an image using Bilinear interpolation is quick and easy, but, unfortunately does not yeild a high quality results. Using Shear transformations on the other hand will be too slow.
It seems to me that Bicubic interpolation is a good compramise. Unfortunately I could not find any efficient algorithms for BiCubic interpolation (it seems to me that since this is a well known problem probably there are well known efficient solutions as well).

Any help is very welcome.

Thanks

guitaristx:
Thanks for your comment.
It seems you suggested a linear interpolation for resizing, then rotating and then another linear interpolation for shrinking (?).
In his case the interpolation method probably wont' do the job. I tried a few interpolation methods, including using a resizing operatin prior to the rotation and it seems that the best quality to efficiency ratio is for BiCubic interpolation.
Linear interpolation is not good enough (losing quality too fast).
Using resizing operations on the other hand are not better than BiCubic interpolation but are slower !

I can get some commercial licraries (like Intel's IPP) which has a "Image Rotation" functions, but since my images have some "special" properties I need to write the code myself.

Thanks,
Yaniv

Also, SSE doesn't apply here - you'll be doing integer math exclusively.  MMX would apply.  MMX applies to integer math, whereas SSE applies to floating-point math.

An MMX programming primer:
http://codeproject.com/cpp/mmxintro.asp

> Also, SSE doesn't apply here - you'll be doing integer math exclusively.
> MMX would apply.  MMX applies to integer math, whereas SSE applies to floating-point math.

I just re-read your original post - SSE would apply, since you're dealing with floating-point arrays.

However, are you certain that you need your 'image' data as floating-point?  Can you go into any details about the application/usage for these images?

guitarx,
My images are multi-layer images. You can think of it as a 3D image that should be rotated around one of the axes. They must be floating point, as they take part of an accurate optimization algorithm of image processing. Actually I had to make them floating point in order to gain efficiency since originally they were double, so I lost some accuracy.
I liked your tip about the efficient devision using lookup table, I'll keep it in mind.
It seems that although I'm an Image Processing algorithm developer I don't know enough about efficient code writting :(

Please let me know if you can think about anything else.

Thanks.

Using floating-point values for your pixel data is very out-of-the-ordinary for image processing as i know it.  If I may, I would recommend running some analysis on your images, and find out the following:

minimum value
maximum value
minimum exponent
maximum exponent
percentage of data points that have another data point within some threshold (say, .1%)

The range of a single-precision float is (+/-)3.4e(+/-)38. Examine your data, and see what range your pixels fall into.  Use some statistical analysis; ignore the upper and lower 5 or 10%, and consider the minimum and maximum values.

This will tell you whether or not you need a floating-point array to store your pixel data.  If your data tends to fall within a very small range of what float can store, then you can safely reduce the precision of your pixels without sacrificing accuracy.  Using floating-point values is going to slow your algorithm considerably, and I'm trying to warn you against using it unless it's ABSOLUTELY NECESSARY.  It's very possible you could reduce the pixels to an unsigned short (16 bits) and maintain sufficient accuracy.  It also makes that lookup table possible - the table size would be 64k, whereas the lookup table for float would be 4GB!

Float math is slooooow, avoid it if at all possible.

const float piover180 = 0.0174532925f;

float x , xinc , y , yinc;

x -= xinc;
y += yinc;

xinc=(float)sin(rotation*piover180) * 0.5;
yinc=(float)cos(rotation*piover180) * 0.5;

Paladin_VB,
Can you explain the purpose ?

>Two shears is how most of the imaging libraries work.

oh yeah? what about >= 90 degrees? there's more logic involved.

>Can you explain the purpose

well if you'd walk through your image with those steps (if Paladin got em right), you'd have a choppy picture like if viewpoint would be rotated. if you'd plot your image using these to increment output coords, you'd have even choppiest rotated image. that was nice trick back on old, really slow machines, which allowed for only two extra multiplications for whole image to be rotated.

> oh yeah? what about >= 90 degrees? there's more logic involved.

Yes, but the additional logic to handle angles >= 90 degrees is trivial compared to the shear operations.  Shear is still going to be the best thing that I've seen thus far.

> oh yeah? what about >= 90 degrees? there's more logic involved.

rotating by 90 degrees exactly is very trivial, so the problem can always be reduced to a rotation  < 90 degrees

gkatz, is it possible to use the GPU without DirectX or OpenGL, as he said he was using niether.

Venabili,

Neither of the experts actually answered my question.
I would like to give to give 100 points to guitaristx and 20 points to each one of the other participates for their good will.

Thanks.