图像重映射算法

Question

我已经开发了一个小项目，用C#帮助我选择住房（持续了3个小时）。

具体来说，我正在将犯罪统计信息叠加在Google地图上，以找到一个美好的社区。

这里有一个示例： http://otac0n.com/Demos/prospects.html

现在，我手动找到了与示例中显示的地图角落匹配的纬度和经度，但我还有几张地图要叠加。

我的新应用程序允许我选择一个地标并指向图像，以将像素连接到纬度和经度。就像这样：

locations.Add(new LocationPoint(37.6790f, -97.3125f, "Kellogg and I-135"));

// and later...

targetPoint.Pixel = FindPixel(mouseEvent.Location);

所以，我已经收集了一系列像素/纬度组合，并且现在想要通过仿射或非仿射变换来转换图像。

这里的目标是使每条街道都对齐。给定一个好的地图，唯一必要的变换将是旋转地图使其朝南（现在我会满意于此）。但我不知道从哪里开始。

有没有人在C#中进行图像变换有经验？我该如何找到适当的旋转角度使地图水平？

在解决完制作良好的地图之后，我最终希望能够叠加手绘地图。这显然需要对最终图像进行大量扭曲，可能超出了第一次迭代的范围。但是，我不希望开发一种无法扩展到未来的系统。

- John Gietzen

---

请在标记问题时注意建议提示。任何名称后面带有数字小于10的标签都可能是错误的。避免创建新的标签。 - Joel Coehoorn

Answer 1

我不确定你想要实现什么，但如果你想在一个地图上容纳超过三个点并将其转移到另一个地图上的超过三个点，基本上有两种方法：

1. 您可以尝试在点上创建三角网格，然后在每个三角形中应用不同的仿射变换，并获得分段线性变换。为了正确进行网格化，您可能需要执行类似于Delaunay三角剖分的操作，其中qhull可能是您首选的选项。

2. 您可以选择更高阶的变换，例如四边形畸变，但很难找到适用于任意数量处于通用位置的点的解决方案。找一本好的有限元方法书籍，阅读关于高阶等参元素的章节，包括拉格朗日或幸运的元素，这将为您提供许多点到多个点的良好映射。以下是几个链接（1和2），可以帮助您入门。但请注意，这些数学内容很密集...

- Jaime

---

这几乎就是我所需要的。现在，让我们在代码中尝试一下...我们将看到它是否按照我的需求工作。 - John Gietzen

现在，我想对整个位图进行插值，包括三角形边缘之外。我应该继续基于生成的 Voronoi 图进行插值...或者其他什么...有点盲目猜测。 - John Gietzen

仿射变换可以延伸到定义它的三个点所形成的三角形之外。在此图像中，采用 Delaunay 三角剖分：http://upload.wikimedia.org/wikipedia/commons/c/cb/Delaunay_Voronoi.png在网格边缘处每个三角形定义的仿射变换可以延伸到三角形之外的无限远处。您需要小心地定义从一个变换到另一个变换的过渡。该图像启发了如何实现这一点的想法，例如从 Delaunay 顶点出发沿着相邻 Voronoi 边夹角的平分线... - Jaime

是的，那基本上就是我想尝试的。感谢你的指导。 - John Gietzen

Answer 2

在二维空间中，仿射变换可以由两组三个非线性二维点指定。在C#中，您可以使用以下例程计算适当的矩阵：

    public static Matrix fit(PointF[] src, PointF[] dst) {
        Matrix m1 = new Matrix(new RectangleF(0, 0, 1, 1), src);
        m1.Invert();
        Matrix m2 = new Matrix(new RectangleF(0, 0, 1, 1), dst);
        m2.Multiply(m1);
        return m2;
    }

它适用于具有3个元素的数组参数。

如果您只需要旋转和平移，则可以使用以下程序：

    public static Matrix fitOrt(PointF src1, PointF src2, PointF dst1, PointF dst2) {
        return fit(new PointF[] { src1, src2, ort(src1, src2) },
                new PointF[] { dst1, dst2, ort(dst1, dst2) });
    }

    public static PointF ort(PointF p, PointF q) {
        return new PointF(p.X + q.Y - p.Y, p.Y - q.X + p.X);
    }

如果你想要找到两组多个点之间的最佳逼近，那么可以从这个链接开始。

- agsamek

Answer 3

很好。

所以，感谢Jamie的指引，我找到了这个：

.NET 2.0中的Delaunay三角剖分

http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/morten.html

目前为止，这基本上就是简化版的lerping。

- John Gietzen