алгоритм упрощения строки: Visvalingam vs Douglas-Peucker

Question

Я пытаюсь реализовать алгоритм siplification. Основными 2 алгоритмами, которые я нашел, являются Ramer-Douglas-Peucker: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm и Visvalingam-Whyatt: https://bost.ocks.org/mike/simplify/ В настоящее время я запускаю несколько имитаций их на Matlab, чтобы определить, какие ответы мне нужны лучше.

Основная цель алгоритма - использовать многоугольники на карте. My Input - многоугольник \ полилиния и порог для ошибки-эпсилон.

Мне нужен симлитированный многоугольник, чтобы быть как можно ближе к оригиналу, и у меня нет требования к количеству пунктов, которые нужно сохранить.

У меня возникают трудности при сравнении двух алгоритмов, потому что: epsilon для R-D-P - это расстояние, в то время как эпсилон для V-W - это область. Мне нужна помощь, чтобы понять, как сравнивать между двумя алгоритмами. , который может дать мне меньше очков, чтобы держать в пороге?

Answer 1

Мне нужен simlified полигон, чтобы быть как можно ближе к оригиналу , и у меня нет Requirment для числа точек, чтобы сохранить.

Метод DP даст вам более ощутимую посадку с меньшим количеством точек - в качестве параметра управления i.e допуск на расстояние определяется вашим требованием «как можно ближе».

Сказав, что масштаб общего полигона или облака точек относительно размеров пикселей будет иметь большее влияние на изображения меньшего размера. Упражнение ниже может дать вам «ощущение» того, как работают оба алгоритма.

Вот несколько сравнений, которые я провел между 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 - точка сокращений: т% допуска. это непосредственно определяет n = t * orig/100.п окончательное число точек

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] 

---

Метод ДП приводит использованием OpenCV approxPolyDP

Дуглас-Peucker - точка сокращений т: расстояние пикселя допуска => нет прямая корреляция с 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.

Но в целом я чувствую, что реализация DP в openCVs дает более плавное восприятие.

Хотя мои выводы о производительности VSV основаны только на реализации Заха, я сомневаюсь, что другие реализации дадут характерно разные подмножества полигонов.

[UPDATE1] Вот сравнение для наихудшего сценария. DP визуально более приемлемо.