线简化算法: Visvalingam对Douglas-Peucker

Question

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

• 拉姆尔-道格拉斯-派克
• 维斯瓦林甘

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

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

我需要简化多边形尽可能接近原，我没有一个要求的点数保持。

我在比较这两种算法时遇到了困难，因为: epsilon用于RDP是一个距离，而epsilon用于VW是一个区域。我需要帮助理解如何比较这两种算法。哪一个能给我更少的分数让我保持在门槛之内？

Answer 1

我需要简化多边形尽可能接近原始，我没有一个要求的点数保持。

DP方法将给你更好的适应与较少的点数-作为它的控制参数，即距离公差被你的要求‘尽可能接近’。

话虽如此，相对于像素尺寸，整体多边形或点云的比例对于较小的图像将产生更大的影响。下面的练习可以让你对这两种算法的表现有一个“感觉”。

下面是我在Visvalingam和之间进行的一些比较，以获得一些包含在大约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实现

​

​

道格拉斯-派克点约简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的实现，但我怀疑其他实现是否会给出不同的多边形子集。

UPDATE1这里是最坏情况的比较。DP在视觉上更容易被接受。

​

​