C: Image rotation algorithm problem

[TikTok]

I've written a small piece of code to rotate a 2D image. I loop through each pixel in the image and use the following to find the new values for x and y:

x2 = cos(angle) * x - sin(angle) * y;
y2 = sin(angle) * y - cos(angle) * x;

This kind of works, except the resulting image is badly skewed (squashed vertically). I thought this might be because of the conversion from doubles to ints for x2 and y2, but rounding them up produces the same results.

I've attached a small example below - original is on the left, "rotated" version on the right. Any ideas?

[eLowar]

Well for one thing there's a sign error there, the second line should be plus, not minus. Also this will rotate around (0,0), if you want to rotate around the center you first have to translate the pixels so the center beoomes (0,0), then rotate, then translate back.

[thor]

y2 = sin(angle) * x + cos(angle) * y;

Originally Posted by eLowar

Well for one thing there's a sign error there, the second line should be plus, not minus.

And sin/cos are wrong way round

[eLowar]

While you're at it, you may also want to create a sort of lookup table for sin and cos, because the library functions are typically slow.

Edit: Hokay, don't want to get carried away, just a suggestion.

Edit 2: Whoops, thor is right of course, I missed that x and y were swapped.

Edit 3: Also to minimize computations, you might want to store intermediate values, like so:

coordinate_t wHalf = w / 2;   /* or shift by one for integer types */
coordinate_t hHalf = h / 2;
coordinate_t xt = x - wHalf;
coordinate_t yt = y - hHalf;
angle_t sinAngle = sin(angle);   /* or use a lookup table */
angle_t cosAngle = cos(angle);
x2 = (cosAngle * xt - sinAngle * yt) + wHalf;
y2 = (sinAngle * xt + cosAngle * yt) + hHalf;

xt and yt might actually be pointless, seeing as subtractions probably aren't very slow, but you definitely want to reduce sin/cos calls and divisions (unless you use integer coordinates and can shift instead).

Edit 4: Umm, w and h being the image's width and height of course.

[girv]

Rather than map from original -> rotated, I believe the accepted wisdom in these things is that you get much, much better results if you go the other way round, ie: for every pixel in your new rotated shape determine which source pixel or pixels it came from.

Now don't you dare ask me how to do it I just remember reading that.

[eLowar]

That is most likely true, as that avoids gaps and in case of non-integer coordinates gives you a chance to interpolate. Err, I guess you'd just have to do the same thing the other way around?

[TikTok]

Thanks everyone for your help and suggestions. Even fixing the sign errors (oops) the results are not good. I'm pretty sure now that the skewed effect is because more than one source pixel ends up mapping to the same destination pixel, because of the rounding. As girv says it might be better to do things 'backwards', so I'll try that.

[Doc Mindie]

I need to load up AMOS..... just to remind meself what I did "way back when" and such.... but I do believe I could produce the working (AMOS)code.... just hang out there for a few minutes... I mean, hours

:EDIT: Whoops, forgot that I've not touched it in years...

[thor]

It all depends on how good you want the image and how complex it can be. You might read the rotation section at http://www.leptonica.com/local-sources.html and have a look at the C source there or look at image processing packages at sourceforge.

[TikTok]

Thanks thor - I looked at that site originally but could only understand the first simple example

I have actually given up for now and decided to temporarily rotate my images using a paint package instead

[eLowar]

Here's tested code for nearest match rotation:

/* assuming width and height are integers with the image's dimensions */

for(int x = 0; x < width; x++) {
	for(int y = 0; y < height; y++) {
		int hwidth = width / 2;
		int hheight = height / 2;
		
		int xt = x - hwidth;
		int yt = y - hheight;
		
		double sinma = sin(-angle);
		double cosma = cos(-angle);
		
		int xs = (int)round((cosma * xt - sinma * yt) + hwidth);
		int ys = (int)round((sinma * xt + cosma * yt) + hheight);

		if(xs >= 0 && xs < width && ys >= 0 && ys < height) {
			/* set target pixel (x,y) to color at (xs,ys) */
		} else {
			/* set target pixel (x,y) to some default background */
		}
	}
}

Substitute your own color setting code and your favorite datatypes. Please note that for the sake of being understandable this is not optimized in any way. (except storing values that are used more than once in variables)

Attached a demonstration with a 64x64 picture, rotated by 45 degrees with a black default background.

[eLowar]

For a better idea of the "quality" this produces:

[TikTok]

That looks pretty sweet eLowar, I'll work on it again tonight. Thanks

[eLowar]

By the way, that is working C++ code, not C code. Sorry, force of habit. But you should be able to make it work with a C compiler with minimal effort (just move the variable declarations to the beginning, etc.). It might even work just like that with C99.

Edit: <RANT>++x would be more efficient than x++, too, unless your compiler optimizes it away.</RANT>

[TikTok]

Well, I got this working thanks to eLowar's code. The rotations are a little bit out (i.e. 180 degrees looks more like 178 degrees), but I guess that is due to the rounding, and I just compensated for it by rotating a bit more

[eLowar]

Hmm, must be. Look at my examples in out.zip above. The multiples of 90° all look perfect as far as I can tell.

Depending on what you're doing, you might want to write special cases for angles that are close to those, especially if you're only using integer angles anyway. Likewise, if you're only using integer angles and can spare the memory, you might want to compute the 360 values for cos and sin in advance, throw them in some array and then just read them from there, that should be a lot faster than computing them for every pixel--- (at this point I had one of those ouch-I'm-stupid experiences)

Speaking of which, my code is stupid.

Definitely pull this:

		double sinma = sin(-angle);
		double cosma = cos(-angle);

and this:

		int hwidth = width / 2;
		int hheight = height / 2;

out of the inner loop, that way you only have to compute the sines and cosines once per rotation, not once per pixel which is totally pointless.

*slaps self* sorry about that

[TikTok]

Doh, I missed that one myself too.

[eLowar]

... what is it you're making anyways?

[Calgor]

excellent stuff guys!

[TikTok]

Its a very basic game, just to help me learn C++ really. It will be a 'Scalextric' (slot cars) type overhead racing game (the first image posted above was the starting track piece).

I have actually gone off the idea a little bit since I started it, but I am a project person and I desperately need a project to keep me occupied My last 'project' was climbing mount Kilimanjaro with a group of my students, so now I am settling for something a bit more down to earth until something...crazier...comes along!