矩阵/坐标变换顺序
我有两个点数组：
Point [] original; AND Point [] returned;
这些变换后的数组只是应用了变换的原始数组的副本。示例：
matrix.Rotate(5f);
matrix.Scale(.8f, 1.1f);
matrix.Translate(30f, 18f);
matrix.TransformPoints(transformed);
- 原始点已知。
- 变换值已知。
- 应用转换的顺序不已知。
我如何计算/推断转换的顺序？
编辑
- 只有一轮转换。
- 一轮最多可以包含三个转换，如下所示。
- 唯一应用的变换是旋转、缩放和平移的任意组合。
为了给它一些真实世界的背景，请考虑使用具有已知兴趣点的图像。您打印图像，扫描它并尝试再次阅读。该图像包含方向标记，使我能够计算扫描过程中应用的变换。
现在，一种强力方法是：
- 读取扫描图像。
- 计算扫描图像上的旋转。
- 对扫描图像应用旋转。
- 计算旋转图像的比例。
- 在旋转图像上应用比例。
- 计算缩放图像上的平移。
- 对缩放后的图像应用平移。
现在，您可以使用原始点从处理后的图像中读取兴趣点，就好像没有进行任何变换一样。当然这种方法的成本很高。 500MB 的图像一次需要在内存中至少有两个副本，并且必须使用图形对象进行转换。
这个问题的前提是只读取图像一次，计算所有变换并将它们应用于坐标而不是图像本身。使用转换后的坐标来读取兴趣点。这就是“转换顺序”问题出现的地方。下面有一些非常有用的答案，我希望这可以澄清上下文。
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:
- Read scanned image.
- Calculate rotation on the scanned image.
- Apply rotation on the scanned image.
- Calculate scale on the rotated image.
- Apply scale on the rotated image.
- Calculate translation on the scaled image.
- 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于您正在寻找的转换数量，暴力可能是最简单的方法，而不是尝试对事物进行任何数学分析（我不确定这是否可能，但会非常困难）。
对于三种不同的变换（A、B、C），您有六种不同的应用方式。它们是：
因此，对于每一个，都按顺序将它们应用于您的输入，并检查最终产品是否与您的输出匹配。
如果您没有特定转换之一，那么您只剩下两种顺序选项。最好的解决方法是仅使用上述六个选项并在缺少变换的位置应用单位矩阵（或无操作）。当然，您还需要检查以防止重复相同的转换顺序。
为了获得最佳性能，您不一定需要检查数组中的所有点 - 如果第一个点不匹配，则无需再检查。您当然需要检查数组中的所有点是否有任何匹配项，以确保第一个点转换的效果不仅仅是偶然的。此外，您还可以检查是否存在微不足道的变换（例如缩放比例为 1 倍）并将它们视为不存在，因为它们可能出现在任何位置，因此您不妨假设它们位于开头（或结尾或中间 - 个人）偏爱）。
最后，仍然存在歧义的可能性。它不太可能，即使只有一小部分输入点，它也变得非常不可能。不过，这是您需要注意的一点。另请参阅下面对更可能出现歧义的特殊情况的讨论。
我希望这足以让您朝着正确的方向前进。我无法编写完整的代码，因为我不知道您的转换数据是如何存储的等等。
经过一些关于某些翻译是否可交换的简短讨论（例如先做 A 然后 B 与先做 B 然后 A 相同），我相信它们不是。在 X 和 Y 的缩放比例相等的特殊情况下，缩放和旋转是可交换的，但此处使用的语法表明缩放有两个因子，我认为它们是 X 和 Y 缩放因子。这意味着在这种情况下缩放和旋转不可交换。翻译永远不是可交换的（想象一下这样的小情况，翻译会将点移动到原点，你会发现这很重要）。
如果 X 轴和 Y 轴上的比例相同，Nocturn 关于交换性的观点（在注释中）确实适用。这意味着，如果您有这样的比例并且它紧邻旋转，那么您将获得两个可能的有效变换顺序。将无法区分两者。
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:
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.
在 CG 中，保存一个矩阵堆栈是很常见的，即每次对矩阵执行操作（变换、旋转或缩放）时，都会将新的矩阵放入堆栈中。这样你就可以回溯到原来的状态。
in CG it's quite common to hold a Matrix
Stack, i.e. each time you perform an operation on the matrix (transform, rotate, or scale), you put the new Matrix to a stack. this way you can track-back to your original state.