Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This was originally posted as a programming question so I will try to keep it as abstract as possible.

We are dealing with two images. The first is the original and second is a distorted version of the original. Sample images attached.

The original has one square (marker) drawn at the top-left, one at the top-right and one at the bottom right. The three squares are used for determining orientation. We know the $width$, $height$ of the image and the $(x,y)$ coordinates of all three markers. There is also a point of interest $(p)$ on the image whose $(x,y)$ position we know.

The distorted version has some transformations applied to it (translation, scaling and rotation only). This is very common if a document/image is printed and scanned back into the system. It could even be upside down, skewed etc. but for now let's ignore that and assume that even rotation is no more than 15 degrees.

Now, I am able to detect the $(x,y)$ coordinates of all markers and calculate the angle of rotation, the amount of $(x,y)$ translation and the $(x,y)$ scaling factor.

Now, I am able to detect the $(x,y)$ coordinates of all markers for the transformed image and need to calculate the transformed $p$:

$tp = f(om1, om2, om3, op, tm1, tm2, tm3)$ where

  • $om1, om2, om3$ are the original markers.
  • $op$ is the original point of interest.
  • $tm1, tm2, tm3$ are the transformed markers.
  • $tp$ is the transformed point of interest.

There are two distinct questions here:

  • How can I calculate coordinates for the transformed $(p)$?
  • What corner cases should be factored in?

Original Transformed/Distorted

share|improve this question
    
I see. That tells me if we allow for scaling on both x and y, and we have rotation on top of that, we get skewing as a natural result. In any case, I'm not sure how to answer your questions on the 'order' of transformations since the transformations are the result of inaccurate scanners and not under my control. Normally this would not induce scaling differently on x and y and we can make do with the assumption that scaling will be a single value. Does this answer your question? –  Raheel Khan Aug 27 '12 at 7:13
    
It does, and it makes the answer a bit simpler. –  joriki Aug 27 '12 at 7:15
    
I've given an answer. I also removed all my comments to reduce the clutter, and also because I used the wrong terminology in some of them; the class of transforms you're considering is the class of similarity transforms of the plane. –  joriki Aug 27 '12 at 7:47
add comment

1 Answer 1

up vote 1 down vote accepted

As clarified in the comments, the transforms considered amount to all similarity transforms of the plane. Any such transform can be written as a product $TRS$, where $T$ is a translation, $R$ is a rotation and $S$ is a homogeneous scaling. In coordinates, this is

$$ \pmatrix{x'\\y'}=\pmatrix{\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha}\pmatrix{s&0\\0&s}\pmatrix{x\\y}+\pmatrix{t_x\\t_y}\;. $$

I'll assume that the aspect ratio of the image is such that the rotations up to $15^\circ$ can't tilt the diagonal beyond the horizontal or vertical, that is, the markers on the top stay on the top and the markers on the right stay on the right. If not, you may have to do some additional tests first to identify the markers correctly.

The rotation angle $\alpha$ can be extracted from the top markers: $\alpha=\arctan((y_2'-y_1')/(x_2'-x_1'))$, where $(x_1',y_1')$ are the coordinates of the top left marker and $(x_2',y_2')$ are the coordinates of the top right marker. (This assumes that the markers originally have the same $y$ coordinate; if not, you need to subtract the corresponding angle calculated from the original coordinates.)

The scaling factor $s$ can be determined from the change in the distance between any two markers, say the top markers: $s=\sqrt{(x_2'-x_1')^2+(y_2'-y_1')^2}/(x_2-x_1)$, where $x_1$ and $x_2$ are the original $x$ coordinates of the top markers. (Again this assumes that their original $y$ coordinates are equal; if not, the denominator is a square root analogous to the numerator.)

Now the translation $(t_x,t_y)$ can be determined from any marker, say the top left marker:

$$ \pmatrix{t_x\\t_y}=\pmatrix{\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha}\pmatrix{s&0\\0&s}\pmatrix{x_1\\y_1}+\pmatrix{x_1'\\y_1'}\;. $$

Then you just have to apply the transformation equation to $p$ to transform it.

share|improve this answer
    
Thank you. Are there any other corner cases to watch out for besides the rotation threshold you mentioned? And even if that threshold were to be crossed, I assume I could calculate and apply only R, the read in the new marker positions then apply only TS to avoid commutative side-effects. –  Raheel Khan Aug 27 '12 at 9:32
1  
@Raheel: I'm not sure what you mean by "corner cases". If the rotation threshold isn't crossed, there shouldn't be any problematic special cases. If it is, the main problem becomes correctly identifying the markers. I don't understand your proposal for doing that, since $R$ can only be determined once you've already correctly identified the markers, and if you have, you don't need any special treatment anymore. I'd suggest to identify the markers by calculating the angles in the triangle they form; the top right marker is the one with the right angle. –  joriki Aug 27 '12 at 9:40
    
I see. I thought you initially meant that the function would only work for up to 15 degrees of rotation but I realize you meant 'as long as the markers are identified correctly, all is good'. –  Raheel Khan Aug 28 '12 at 6:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.