线简化算法：Visvalingam 与 Douglas-Peucker

Question

我正在尝试实现一个线简化算法。我发现的主要 2 种算法是：

• 拉默-道格拉斯-普克
• 维斯瓦林加姆-怀亚特

目前我正在 Matlab 上对它们进行一些模拟，以确定哪个能更好地满足我的需求。

该算法的主要目标是简化地图中的多边形。 我的输入是多边形\折线和错误阈值 - epsilon。

我需要简化的多边形尽可能接近原始多边形， 而且我对保留的点数没有要求。

我在比较这两种算法时遇到困难，因为： RDP 的 epsilon 是距离，而 VW 的 epsilon 是面积。 我需要帮助了解如何比较两种算法。 这可以给我更少的分数来保持在阈值内？

Answer 1

我需要简化的多边形尽可能接近 原创，我对保留点数没有要求。

DP 方法将以更少的点数量为您提供更好的可感知拟合 - 作为其控制参数，即距离公差由您的要求“尽可能接近”捕获。

话虽如此，整体多边形或点云相对于像素尺寸的比例将对较小的图像产生更大的影响。下面的练习可以让您“感受”这两种算法的执行情况。

以下是我在 Visvalingam-Whyatt 和 Ramer-Douglas-Peucker 之间进行的一些比较，以获得最初大约 100x100 位图中包含的一些轮廓。这些图像是轮廓放大约 10 倍的屏幕截图。

（您可能需要下载图像以了解性能差异）

Visvalingam-Whyatt 方法结果：礼貌Zach 在 github 上的实现移植到 opencv 数据类型。

VSV 简化 - 具有 0.55（白色）、0.4（红色）、0.25（洋红色）、0.15（青色）百分比公差

VSV - 点减少 t：% 公差。这直接确定了 n = t*orig/100。 n 是最终的点数

orig 88: [n=47 for t=0.55], [n=34 for t=0.4], [n=20 for t=0.25], [n=12 for t=0.15]
orig 133: [n=72 for t=0.55], [n=52 for t=0.4], [n=32 for t=0.25], [n=18 for t=0.15]
orig 118: [n=63 for t=0.55], [n=46 for t=0.4], [n=28 for t=0.25], [n=16 for t=0.15]
orig 107: [n=57 for t=0.55], [n=41 for t=0.4], [n=25 for t=0.25], [n=15 for t=0.15]
orig 107: [n=57 for t=0.55], [n=41 for t=0.4], [n=25 for t=0.25], [n=15 for t=0.15]
orig 268: [n=146 for t=0.55], [n=106 for t=0.4], [n=65 for t=0.25], [n=39 for t=0.15]
orig 158: [n=85 for t=0.55], [n=62 for t=0.4], [n=38 for t=0.25], [n=22 for t=0.15]
orig 158: [n=85 for t=0.55], [n=62 for t=0.4], [n=38 for t=0.25], [n=22 for t=0.15]
orig 109: [n=58 for t=0.55], [n=42 for t=0.4], [n=26 for t=0.25], [n=15 for t=0.15]
orig 192: [n=104 for t=0.55], [n=75 for t=0.4], [n=46 for t=0.25], [n=27 for t=0.15]
orig 132: [n=71 for t=0.55], [n=51 for t=0.4], [n=31 for t=0.25], [n=18 for t=0.15]
orig 89: [n=47 for t=0.55], [n=34 for t=0.4], [n=21 for t=0.25], [n=12 for t=0.15]
orig 110: [n=59 for t=0.55], [n=42 for t=0.4], [n=26 for t=0.25], [n=15 for t=0.15]
orig 40: [n=20 for t=0.55], [n=14 for t=0.4], [n=8 for t=0.25], [n=4 for t=0.15]

---

DP 方法结果使用 openCV approxPolyDP

Douglas-Peucker - 点减少 t ：像素距离容差 => 与 n - 最终点数没有直接关系

orig 88: [n=33 for t=0.1], [n=29 for t=0.5], [n=8 for t=1], [n=6 for t=2]
orig 133: [n=57 for t=0.1], [n=45 for t=0.5], [n=12 for t=1], [n=7 for t=2]
orig 118: [n=50 for t=0.1], [n=40 for t=0.5], [n=15 for t=1], [n=8 for t=2]
orig 107: [n=47 for t=0.1], [n=35 for t=0.5], [n=11 for t=1], [n=6 for t=2]
orig 107: [n=30 for t=0.1], [n=24 for t=0.5], [n=8 for t=1], [n=6 for t=2]
orig 268: [n=126 for t=0.1], [n=110 for t=0.5], [n=32 for t=1], [n=23 for t=2]
orig 158: [n=80 for t=0.1], [n=62 for t=0.5], [n=17 for t=1], [n=11 for t=2]
orig 158: [n=66 for t=0.1], [n=52 for t=0.5], [n=16 for t=1], [n=9 for t=2]
orig 109: [n=50 for t=0.1], [n=38 for t=0.5], [n=12 for t=1], [n=9 for t=2]
orig 192: [n=74 for t=0.1], [n=64 for t=0.5], [n=18 for t=1], [n=15 for t=2]
orig 132: [n=58 for t=0.1], [n=45 for t=0.5], [n=14 for t=1], [n=11 for t=2]
orig 89: [n=37 for t=0.1], [n=31 for t=0.5], [n=7 for t=1], [n=6 for t=2]
orig 110: [n=42 for t=0.1], [n=36 for t=0.5], [n=9 for t=1], [n=7 for t=2]
orig 40: [n=18 for t=0.1], [n=15 for t=0.5], [n=9 for t=1], [n=3 for t=2]

---

总结：

• 这两种方法都会优雅地降级。
• VSV 允许您指定近似点的数量（在此实现中）
• 此实现中的 VSV 允许您一次性选择多个近似多边形。
• 即使对于大曲率部分，VSV 也会保留大量像素级凸性变形 - 在某些情况下这可能是不受欢迎的。
• DP 更好地遵循凸性并更多地平滑变形，但牺牲了“接近性”。
• 因此，对于相同的感知公差，DP 给出的点数较少 - 无论如何，这两种方法之间很难进行比较
• DP 作为线性距离规格，可以更好地感受公差。

对于我的应用程序，我更喜欢 VWV 在此实现中提供的控制，而不是 DP 方法可能的效率。

但总体来说我觉得openCVs的DP实现提供了更平滑的感知。

虽然我对 VSV 性能的结论仅基于 Zach 的实现，但我怀疑其他实现是否会给出特征不同的多边形子集。

[更新1] 这是最坏情况的比较。 DP在视觉上更容易接受。

Answer 2

如果我想固定DP或Visvalingam生成的保留点的数量，有没有更好的算法？