- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试实现一个行简化算法。我发现的主要 2 种算法是:
目前,我正在 Matlab 上对它们进行一些模拟,以确定哪个能更好地满足我的需求。
该算法的主要目标是简化 map 中的多边形。我的输入是多边形\折线和错误阈值 - 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's implementation on 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]
对于我的应用程序,我更喜欢 VWV 在此实现中提供的控制,而不是 DP 方法的可能效率。
但总的来说,我觉得 openCVs 的 DP 实现提供了更平滑的感知。
虽然我对 VSV 性能的结论仅基于 Zach 的实现,但我怀疑其他实现是否会提供具有不同特征的多边形子集。
[UPDATE1] 这是最坏情况下的比较。 DP在视觉上更容易接受。
关于algorithm - 行简化算法 : Visvalingam vs Douglas-Peucker,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35290973/
边缘检测 我已经使用 Soble 运算符来获得一些有用的点。这是我的 al: for (int x = 0; x 40){ mEdgePoints.add(n
我计划使用 Douglas-Peucker 算法来减少点数(除非有人知道更好的例子)。数据是一维的,正在构造的曲线是二维的 给出一个减少的点的外壳我需要一个将穿过所有点的样条(我认为拉格朗日插值可以做
使用计数器暂停执行以显示各个处理步骤来逐步完成道格拉斯普克线简化算法是否可行?我不确定是否可能。如果是这样的话,一个特定的数据结构建议这样做。我只看到了递归的解决方案,不确定这是否可行? 最佳答案 是
我正在尝试使用 Douglas-Peucker 算法减少多边形的顶点 - 这对于线条和路径非常有效。 我的问题是我要优化的多边形是封闭的。 When choosing 2 random adjacen
我在阅读这里的文章后实现了一个路径简化算法: http://losingfight.com/blog/2011/05/30/how-to-implement-a-vector-brush/ 它非常适合
我阅读了一篇关于三角形标志检测的研究论文,该论文使用 canny 边缘检测,然后应用 Ramer-Douglas-Peucker 来检测图像中的三角形标志,例如在下面的照片中。 我设法为我的图像应用c
有没有办法在python中也找到rdp算法丢弃的点? 算法: from rdp import rdp rdp([[1, 1], [2, 2], [3, 3], [4, 4]]) 给出压缩后剩余的点数:
我正在为 iOS 开发一个绘画应用程序,为了获得平滑的线条,我对样本点应用了 Ramer–Douglas–Peucker 算法。 该算法适用于点的整个向量,结果随着点的增加而变化。它会导致结果曲线在用
我正在尝试实现一个行简化算法。我发现的主要 2 种算法是: Ramer-Douglas-Peucker Visvalingam-Whyat 目前,我正在 Matlab 上对它们进行一些模拟,以确定哪个
Douglas-Peucker 算法是一种直线泛化算法,它从原始 GPS 轨迹点集中递归地选择点。 但该算法不适用于GPS轨迹数据,因为要同时考虑空间和时间数据,而DP只考虑空间谓词。 有几种 DP
绘制地理多边形不是 R 的强项,但如果 done well 会很有收获.我使用的是来自英国的数据,多边形边界中的细节高得离谱,这使得任何绘图或操作功能(尤其是在运行 fortify 以使其可 ggpl
我想为 RDP algorithm 修改以下 python 脚本目的是不使用 epsilon 而是选择我想在最后保留的点数: class DPAlgorithm(): def distance
我是一名优秀的程序员,十分优秀!