Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
458 views
in Technique[技术] by (71.8m points)

c# - Matrix / coordinate transformation order

I have two array of points:

Point [] original; AND Point [] transformed;

These transformed array is simply a copy of the original with transformations applied. Example:

matrix.Rotate(5f);  
matrix.Scale(.8f, 1.1f);  
matrix.Translate(30f, 18f);  
matrix.TransformPoints(transformed);
  • The original points ARE known.
  • The transformation values ARE known.
  • The order in which the transformations were applied is NOT known.

How can I calculate / infer the order of transformations?

EDIT

  • There is only ONE round of transformation.
  • A round could contain at most three transformations as below.
  • The only transformations applied are any combination on rotate, scale and translate.

To give it some real-world context, consider having an image with known points of interest. You print the image, scan it and try to read it again. The image contains orientation markers that allow me to calculate the transformations applied during the scanning process.

Now, a brute force approach would be:

  1. Read scanned image.
  2. Calculate rotation on the scanned image.
  3. Apply rotation on the scanned image.
  4. Calculate scale on the rotated image.
  5. Apply scale on the rotated image.
  6. Calculate translation on the scaled image.
  7. Apply translation on the scaled image.

You can now read the points of interest from the processed image using the original points as if there was no transformation. Of course this method is expensive. A 500MB image would need to have at least two copies in memory at a time and would have to be transformed using the graphics object.

The premise of this question was to read the image only once, calculate all transformations and apply them to coordinates rather than the image itself. The use the transformed coordinates to read the points of interest. This is where the problem of 'order of transformations' comes in. Some very helpful answers below and I hope this clears the context.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

For the number of transformations that you are looking at brute force is probably the easiest approach rather than trying to do any mathematical analyses on things (I'm not 100% sure if that's even possible but it would be very hard).

For three different transforms (A,B,C) you have six different ways you can apply them. They are:

  • ABC
  • ACB
  • BAC
  • BCA
  • CAB
  • CBA

So for each of those apply them in that order to your input and check whether the final product matches your output.

If you don't have one of the specific transforms then you are left with only two options of order. This may be best dealt with by just using the above six options and applying an identity matrix (or a no-op) where the missing transform is. Of course you also need checks to prevent you from duplicating the same transform order.

For optimal performance you don't necessarily need to check all the points in your array - if the first point doesn't match then no need to check any more. You will of course want to check all of the points in the array for any that match to ensure that its not just by chance that the first point transformed that works. Also you can check for trivial transformations (such as scale by a factor of 1) and treat them as not existing because they could appear at any position at all so you might as well assume they are at the beginning (or end or middle - personal preference).

Lastly there is still a possibility of ambiguity. its not very likely and with even a small set of input points it becomes very unlikely. It is a point you need to be aware of though. Also see below for discussion on special case where ambiguity becomes a lot more likely.

I hope this is enough to get you going in the right direction. I can't write full code because I have no idea how your transformation data is stored and so on.

After some brief discussion about whether certain translation are commutative or not (eg is doing A then B the same as doing B then A) I believe that they are not. In the special case where the scaling of X and Y are equal then scaling and rotation are commutative but the syntax used here suggests that scaling has two factors that I presume to be X and Y scale factors. This means that scaling and rotation are not commutative in this case. Translations are never commutative (imagine the trivial case where a translation would move the point to the origin and you can see that it matters).

Nocturn's point (in comments) on commutativity does apply though if the scale is the same on X and Y axes. This means that if you have such a scale and it is next to a rotation then you will get two possible transformation orders that are valid. There will be no way to distinguish between the two.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...