Puzzle for math geniuses with spare time.

[Maui]

I have a puzzle for any math (specifically trig) geniuses out there with spare time on their hands.

I am having an issue with an imaging toolkit that it returning coordinates that are somewhat off. Basically, the degree of error in the returned coordinates is a function of the amount the image has been rotated and the distance the coordinates are from the center of the image.

The toolkit author claims this is because I am retrieving coordinates from legacy (deprecated) functions and that it is impossible to return accurate coordinates without using newer functions which take into account more factors than just image rotation. Unfortunately, adapting my code to use the newer functions would be more work than its worth (and the author is clear its not worth their time to address the legacy functions I am using).

However, I suspect I am not getting the truth about the coordinates from the legacy functions-- it seems likely to me that they can be mathematically manipulated to meet my needs; I would guess it is only in more complex usage scenarios than mine that there is no way to get accurate coordinates using the legacy functions.

The reason I say this is the errors in the coordinates appear very systemmatic based on the amount of rotation and distance from the image center. I strongly suspect straight-forward trigonometry can be used to compensate for the error. The error in the X,y coordinates are off in the following directions based upon the location of the coordinate in relation to the image center. In the table below "+" means the coordinate returned is higher than it should be and "-" means it is lower than it should be. Coordinates further from the image center are off by a greater magnitude, but in the same direction.

Code: Select all

           left right
top        +,-  -,-
bottom     +,+  -,+

(this is true whether the image has been rotated clockwise or counter-clockwise)

I started with good intentions, employing trigonometry to the best of my abilities to try to find an equation that converts the returned coordinates into accurate coordinates. However, that quickly devolved into thoughtless trial-and-error after my first attempts didn't pan out. This lead to a couple of formulas that get much better coordinates, but I'm failing to come up within any reasoned mathematical theory that might help me get exactly correct coordinates. Can you come up with the explanation I am not and suggest a formula that might get the exact result I am looking for?

Where:
x1 = x coordinate on non-rotated image relative to image center
x2 = x coordinate on rotated version of image relative to image center
y1 = y coordinate on non-rotated image relative to image center
y2 = y coordinate on rotated version of image relative to image center
costheta = the cosine of the angle of rotation in the rotated version
sintheta = the sine of the angle of rotation in the rotated version

I have found the following simple compensation gets me pretty close (~25% the magnitude of the original error):
x2/costheta;
y2*costheta;

In this case the direction of error changes and is dependent on the direction of rotation such that in images rotated clockwise (negative theta) the direction of error is:

Code: Select all

           left right
top        +,+  +,-
bottom     -,+   -,-

In the case of counter-clockwise (positive theta), the direction of error is:

Code: Select all

           left right
top        -,-  -,+
bottom     +,-  +,+

I have found following gets me closer still (~10% of the original error):
x2*costheta + (y2 - y1) * sintheta;
y2/costheta + (x2 - x1) * sintheta;

While the resulting coordinates of the second formula are more accurate, the direction of error in this case is the same as in the first compensation attempt. Again, there's almost no thought to how I came up with this in the end... I just kept pluging stuff in until I found something that (almost) worked in hopes that I could find a theory to explain it afterwards. I haven't.

Anyone think they might be able to explain the math behind the error in the coordinates I am receiving?

[krenshala]

What I do to troubleshoot that kind of thing is add some debugging lines to print out the X,Y values at various points during the calculations. From what you've described I have it output the before and after rotation values at the least, and preferably some of them during the rotation in case you are doing any manipulation between initial values and final rotation.

My guess, based on what you've described, is there is some bit of math being done of the values that isn't quite what you want. Maybe a rounding (or truncating) issue, and that rounded (truncated) error value is getting multiplied during the rotation.

[Diogenes]

It's been a few years since I messed with this stuff. Are you using a matrix to describe the objects position?


Myself and a friend developed an excellent algorithm for rotating matrices.


You call the function with a pointer to your model's matrix and a rotation vector, and it rotates your matrix around your rotation vector. You then multiply your vertices by the new axises to get your coordinates.


His original rotation algorithm introduced all sorts of errors such as you described, and he had to re-normalize and re-perpendicularize his axis vectors after every computation. I pointed out how sh*tty was the operation of his rotation algorithm and he asked me if I could do better.

Turns out I could.


If you think this might help, i'll see if I can scrounge up that old code. It's in C.

[Maui]

Krenshala,

Thanks... but actually my problem is that I have ONLY the output coordinates that are supposed to relate to a feature in the image as well as the angle of rotation that has been applied to the image. On an image with no rotation, I can see that the coordinates are always correct. However on an image that has rotation, I can see that the returned coordinates are slightly off... more so the more the image is rotated and the further from the center you go.

I have no ability to debug the code that the toolkit has done to deal with the rotation; I am trying to correct after-the-fact what the toolkit has done apparently incorrectly. I'm trying to develop a "prescription" for a near-sighted algorithm, so-to-speak.

Diogenes,

Thanks for the offer, but as I told Krenshala, the problem is I don't have access to debug or manipulate the code that is producing the incorrect result. I have well-tested code to perform rotation operations that I would be able to use if I were in control of the operation, but what I hope to do is to figure out what the toolkit is doing wrong and compensate for it.

Well, actually, I've mostly compensated for it... but I would feel a whole lot better if I understood *why* what I've done mostly works. (If I knew what the algorithm is doing wrong or what it is taking into account that I'm not expecting it to.)

[GIThruster]

Sounds like you need to filter out the determinant -1 that generates improper rotations:

http://en.wikipedia.org/wiki/Rotation_matrix

[rj40]

What software are you using?
What is the nature of the image (satellite imagery, picture of a pretty girl)?
Hmmmm...

[JoeP]

It sounds like the author deprecated those functions for a reason.

[Maui]

I certainly would have enjoyed this issue more if it would have involved closely inspecting pictures of pretty girls...

[hanelyp]

Are the functions used rotating around the right point?

[Maui]

Are the functions used rotating around the right point?

I strongly suspect you are on the right track here. Only I was thinking a little more along the lines that the rotated coordinates are being reported in an altered coordinate system; that is the origin is not in the same spot it was prior to the image being rotated. If that's the case, I haven't been able to figure exactly how the coordinate system has changed, though. I suppose that really boils down to a restatement of your theory, however.