投影变换

Question

给定两个图像缓冲区（假设它是一个大小为宽度 * 高度的int数组，每个元素都是颜色值），如何将由四边形定义的区域从一个图像缓冲区映射到另一个（始终为正方形）图像缓冲区？我了解到这被称为“投影变换”。

我还在寻找一种通用的方法（不依赖于“可以为我完成所有工作的神奇函数X”），以便可以合理地应用于任何语言，而不会涉及特定于语言或库的内容。

例如：我已经使用Processing库（processing.org）在Java中编写了一个短程序，用于从摄像机中捕获视频。在初始的“校准”步骤中，捕获的视频直接输出到窗口中。然后，用户单击四个点来定义将要转换的视频区域，然后在程序的后续操作中将其映射到正方形窗口中。如果用户单击定义在相机输出中以某个角度可见的门的四个角，则此变换将导致后续视频将门的变换图像映射到整个窗口区域，尽管略有扭曲。

- Michael Wehner

---

澄清请求：缓冲区是矩形，但被复制的区域是正方形吗？ - wnoise

目标区域是一个矩形，但源区域可能是一个非矩形的四边形。 - MusiGenesis

你在这方面有什么进展了吗？ - zaf

@CarlWitthoft 那个链接不对，它指向了这个问题。 - Matthias Urlichs

@MatthiasUrlichs 噢——抱歉；在这么晚的时候我忘记了应该链接哪个问题。已删除。 - Carl Witthoft

Answer 1

使用线性代数比几何容易得多！此外，您不需要使用正弦、余弦等函数，因此可以将每个数字存储为有理分数，并在需要时获得精确的数值结果。

您需要的是将旧的 (x,y) 坐标映射到新的 (x',y') 坐标。您可以使用矩阵来完成。您需要找到 2×4 投影矩阵 P，使 P 乘以旧坐标等于新坐标。我们假设您正在将直线映射到直线（而不是例如将直线映射到抛物线）。由于您有投影（平行线不保持平行）和平移（滑动），您还需要一个因子 (xy) 和 (1)。表示成矩阵形式：

          [x  ]
[a b c d]*[y  ] = [x']
[e f g h] [x*y]   [y']
          [1  ]

你需要了解 a 到 h 才能解决这些方程：

a*x_0 + b*y_0 + c*x_0*y_0 + d = i_0
a*x_1 + b*y_1 + c*x_1*y_1 + d = i_1
a*x_2 + b*y_2 + c*x_2*y_2 + d = i_2
a*x_3 + b*y_3 + c*x_3*y_3 + d = i_3

e*x_0 + f*y_0 + g*x_0*y_0 + h = j_0
e*x_1 + f*y_1 + g*x_1*y_1 + h = j_1
e*x_2 + f*y_2 + g*x_2*y_2 + h = j_2
e*x_3 + f*y_3 + g*x_3*y_3 + h = j_3

再次强调，您可以使用线性代数：

[x_0 y_0 x_0*y_0 1]   [a e]   [i_0 j_0]
[x_1 y_1 x_1*y_1 1] * [b f] = [i_1 j_1]
[x_2 y_2 x_2*y_2 1]   [c g]   [i_2 j_2]
[x_3 y_3 x_3*y_3 1]   [d h]   [i_3 j_3]

将x_n、y_n、i_n、j_n插入角落。 （角落最好，因为它们相距较远，这样如果您从用户点击中选择点，则可以减少误差。）取4x4矩阵的逆，然后将其乘以方程的右侧。该矩阵的转置是P。您应该能够找到在线计算矩阵逆和乘法的函数。

您可能会遇到错误的地方：

- 在计算时，请记住检查是否存在除零。 这表明您的矩阵不可逆。 如果您尝试将一个（x，y）坐标映射到两个不同的点，则可能会发生这种情况。 - 如果编写自己的矩阵数学，请记住矩阵通常是按行、列（垂直、水平）指定的，而屏幕图形是x、y（水平、垂直）。 第一次肯定会出错。

- Eyal

Answer 2

编辑

以下假设角度比率不变是错误的。射影变换可以保留交叉比和关系。解决方案如下：

1. 找到线段AD和CP定义的线的交点C'。
2. 找到线段AD和BP定义的线的交点B'。
3. 确定B'DAC'的交叉比，即r = (BA' * DC') / (DA * B'C')。
4. 构造投影线F'HEG'。这些点的交叉比等于r，即r = (F'E * HG') / (HE * F'G')。
5. F'F和G'G将在投影点Q处相交，因此等式交叉比并知道正方形边的长度，您可以通过一些算术技巧确定Q的位置。

---

嗯......我会试一试这个。 这个解决方案依赖于角度比例在变换中被保留的假设。 请参见图像以获取指导（对于图像质量很差的抱歉......太晚了）。该算法仅提供了四边形中的点到正方形中点的映射。您仍需要实现处理多个四边形点映射到同一正方形点的方法。

让ABCD为四边形，其中A是左上顶点，B是右上顶点，C是右下顶点，D是左下顶点。 （xA，yA）表示顶点A的x和y坐标。 我们正在将此四边形中的点映射到边长为m的正方形EFGH中。

计算AD，CD，AC，BD和BC的长度：

AD = sqrt((xA-xD)^2 + (yA-yD)^2)
CD = sqrt((xC-xD)^2 + (yC-yD)^2)
AC = sqrt((xA-xC)^2 + (yA-yC)^2)
BD = sqrt((xB-xD)^2 + (yB-yD)^2)
BC = sqrt((xB-xC)^2 + (yB-yC)^2)

设θD为顶点D的角度，θC为顶点C的角度。使用余弦定理计算这些角度：

thetaD = arccos((AD^2 + CD^2 - AC^2) / (2*AD*CD))
thetaC = arccos((BC^2 + CD^2 - BD^2) / (2*BC*CD))

我们将四边形中的每个点P映射到正方形中的一个点Q。对于四边形中的每个点P，执行以下操作：

• Find the distance DP:

  DP = sqrt((xP-xD)^2 + (yP-yD)^2)
  

• Find the distance CP:

  CP = sqrt((xP-xC)^2 + (yP-yC)^2)
  

• Find the angle thetaP1 between CD and DP:

  thetaP1 = arccos((DP^2 + CD^2 - CP^2) / (2*DP*CD))
  

• Find the angle thetaP2 between CD and CP:

  thetaP2 = arccos((CP^2 + CD^2 - DP^2) / (2*CP*CD))
  

• The ratio of thetaP1 to thetaD should be the ratio of thetaQ1 to 90. Therefore, calculate thetaQ1:

  thetaQ1 = thetaP1 * 90 / thetaD
  

• Similarly, calculate thetaQ2:

  thetaQ2 = thetaP2 * 90 / thetaC
  

• Find the distance HQ:

  HQ = m * sin(thetaQ2) / sin(180-thetaQ1-thetaQ2)
  

• Finally, the x and y position of Q relative to the bottom-left corner of EFGH is:

  x = HQ * cos(thetaQ1)
  y = HQ * sin(thetaQ1)
  

您需要追踪每个点映射到多少颜色值，以便计算每个点的平均颜色。这与方格中的每个点相关。

- b3

---

我知道这个答案有点老了，但你能解释一下角度比例的假设吗？我尝试了你的方法，得到了以下结果：http://i.imgur.com/Wr76L.png。这个四边形的形状有什么限制吗？ - zaf

@zaf - 回顾这个问题，我错误地假设角度比例会被保留。相反，我应该假设交叉比率是不变的。我编辑了一些注释来说明这一点。 - b3.

那会教你晚上回答的教训。点赞很有趣。如果您能添加新算法的方程式，那就太好了。实际测试会更加超级。我花了将近一整天的时间研究您的原始算法以及StackOverflow和互联网上的其他算法，并惊讶地发现在获取可行解决方案时遇到了困难。最终，我用白板和键盘花了一个小时来开发自己的算法。所以这一天被拯救了，没有完全成为灾难 :) - zaf

@zaf - 很高兴听到你找到了自己的解决方案。希望我没有误导你太远。我很快会发布更新的解决方案。与此同时，可以继续对这个答案进行投票。 - b3.

你应该保留这些赞，你的回答很有启发性。至少它让我更深入地思考了这个问题。 - zaf

Answer 3

我认为你需要的是平面单应性，可以看一下这些讲义：http://www.cs.utoronto.ca/~strider/vis-notes/tutHomography04.pdf。如果你向下滚动到底部，你会看到一个恰好描述你所需的示例。我相信在Intel OpenCV库中有一个函数可以完成这个任务。

- Ian Hopkinson

Answer 4

这段文字的翻译如下：

在 CodeProject 上有一个 C++ 项目，其中包括位图投影变换的源代码。数学知识可以在维基百科 这里 找到。请注意，据我所知，射影变换不能将任意四边形映射到另一个四边形，但对于三角形可以这样做，您还可以查找倾斜变换。

- smacl

Answer 5

如果这种转换要看起来好（与在Paint中调整大小时位图的外观不同），那么您不能仅创建一个将目标像素映射到源像素的公式。目标缓冲区中的值必须基于附近源像素的复杂平均值，否则结果会极为像素化。

因此，除非您想进行一些复杂的编码，否则像smacl和Ian建议的那样，使用其他人的魔术函数。

- MusiGenesis

Answer 6

以下是原理：

• 通过平移向量 t 将 A 的原点映射到 B 的原点。
• 取 A 的单位向量 (1,0) 和 (0,1)，并计算它们将如何映射到 B 的单位向量。
• 这将给出一个转换矩阵 M，使得 A 中的每个向量 a 都映射到 M a + t
• 反转矩阵并否定平移向量，以便对于 B 中的每个向量 b，您都有逆映射 b -> M^-1 (b - t)
• 一旦您获得了此转换，对于 B 中目标区域中的每个点，找到相应的 A 中的点并复制。

这种映射的优点是您只计算所需的点，即在目标点上循环，而不是在源点上循环。几年前，“演示编码”场景中广泛使用了这种技术。

- Sklivvz

---

你正在描述一种线性变换，它允许平移、旋转、缩放、反射和剪切。不幸的是，透视变换通常不是线性的（在它不仅仅是矩阵乘法的意义上）。 - Hugh Allen

嗯，线性变换没有平移元素。此外，线性变换肯定包括投影（例如((1,0),(0,0))是一个投影）。 - Sklivvz

顺便提一下，投影变换通常不是投影。 - Hugh Allen

Hugh，没错，仿射变换确实更通用，但也更加难以解释。我试图给出一个简单的答案。关于投影变换，我认为它们对作者的需求来说有点过头了，但还是感谢你指出。 - Sklivvz

在我的回答中，我展示了如何使用线性代数来完成。只需要添加翻译（1）和投影（xy）因子即可。您拥有的点越多，您需要的x和y的阶数就越高。 - Eyal