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

  • 拉默-道格拉斯-皮克
  • 维斯瓦林厄姆·怀亚特

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

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

我需要简化的多边形尽可能接近原始多边形, 而且我不需要保留点数。

我在比较这两种算法时遇到了困难,因为: RDP的epsilon是一个距离,而VW的epsilon是一个区域。 我需要帮助,了解如何在两种算法之间进行比较。 哪些可以让我减少积分以保持阈值?


I need the simlified polygon to be as close as possible to the original, and I do not have a requirment for number of points to keep.

DP方法将以较少的点数为您提供更好的可感知拟合度-因为它的控制参数,即您的要求"尽可能接近"捕获距离公差。

话虽如此,整个多边形或点云相对于像素尺寸的比例将对较小的图像产生更大的影响。下面的练习可以使您对这两种算法的执行情况有一个"感觉"。

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

(您可能需要下载图像以了解性能上的差异)

Visvalingam-Whyatt方法的结果:由Zach在github上的实现移植到opencv数据类型。 VSV simplification - with 0.1(white), 0.5(red), 1(magenta), 2(cyan) distance tolerances

VSV简化-0.55(白色),0.4(红色),0.25(洋红色),0.15(青色)百分比公差

VSV点减少量t:%公差。这直接确定n = t * orig / 100。 n是最终分数

1234567891011121314
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]

使用openCVroxPolyDP的DP方法结果

DP simplification - with 0.1(white), 0.5(red), 1(magenta), 2(cyan) distance tolerances

Douglas-Peucker-点缩减t:像素距离公差=>与n没有直接关系-最终的点数

1234567891011121314
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的线性距离规格使公差更好。

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

但是总的来说,我觉得openCV的DP实现提供了更流畅的理解。

尽管我对VSV性能的结论仅基于Zach的实现,但我怀疑其他实现是否会提供特征上不同的多边形子集。

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

enter image description here