Самый быстрый доступный алгоритм для преобразования расстояния
Я ищу самый быстрый доступный алгоритм для преобразование расстояния.
Согласно этому сайту http://homepages.inf.ed.ac.uk/rbf/hipr2/distance.htm , он описывает: «Преобразование расстояния может быть Рассчитан гораздо более эффективно, используя умные алгоритмы только в двух проходах (например, Розенфельд и Pfaltz 1968). «
Поиск вокруг, я обнаружил: « Розенфельд, А и Пфальс, Дж Л. 1968. Дистанционные функции на цифровых картинках. Распознавание образца, 1, 33-61. "
Но я считаю, что мы должны иметь лучший и быстрый алгоритм, чем у одного в 1968 году? На самом деле я не мог найти источник с 1968 года, поэтому любая помощь высоко ценится.
2 ответа
В данной статье рассматриваются известные алгоритмы точного преобразования расстояний:
«Алгоритмы двумерного евклидового преобразования расстояний: сравнительный обзор»
http://liu.diva-portal.org / smash / get / diva2: 23335 / FULLTEXT01
Самое быстрое точное преобразование расстояния от Мейстера:
«Общий алгоритм вычисления преобразований расстояния в линейное время».
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf
Разработка алгоритма особенно хорошо подходит для параллельных вычислений. .
Это реализовано в моей библиотеке с открытым исходным кодом, которая пытается эмулировать Photoshop «Layer Style»:
В «Ускоренном алгоритме GPU для быстрого сопоставления фасок и подробного сравнения с высоко оптимизированной реализацией процессора» Майкл Раутер и Дэвид Шрайбер описывают свои характеристики с использованием алгоритма преобразования расстояний из «Унифицированного алгоритма линейного времени для вычисления карт расстояний». ».
В 2012 году они использовали около 15 мс для 8 преобразований расстояния (720 × 576) на процессоре Intel Xeon без многопоточности. На GPU GTX 460 они сделали это за 7 мс.
Я никогда не видел более быстрых ДТ.