Самый быстрый доступный алгоритм преобразования расстояния

Я ищу самый быстрый доступный алгоритм для преобразования расстояния.

В соответствии с этим сайтом http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm он описывает: "Преобразование расстояния может быть рассчитано гораздо эффективнее с использованием умных алгоритмов всего за два прохода (например, Розенфельд и Пфальц 1968)".

Поиск вокруг, я обнаружил: "Розенфельд, А и Пфальц, Дж. Л. 1968. Функции расстояния на цифровых снимках. Распознавание образов, 1, 33-61."

Но я считаю, что мы должны иметь более быстрый и быстрый алгоритм, чем тот, который был в 1968 году? На самом деле, я не мог найти источник с 1968 года, поэтому любая помощь высоко ценится.

Ответ 1

Там много новых работ по вычислению дистанционных функций.

Быстрые алгоритмы марша, которые изначально пришли из Цициклиса (не Sethian, как Wikipedia). Для этого доступны тонны реализаций.
Быстрорадиционные алгоритмы от Zhao
O (n) (приблизительный) быстрый ход Яцива

Кстати, вы действительно хотели бы использовать их вместо работы Розенфельда, особенно если вы хотите вычислить расстояния при наличии препятствий.

Ответ 2

В настоящем документе рассматриваются известные алгоритмы точного преобразования расстояния:

"Двумерные евклидовы алгоритмы дальнего преобразования: сравнительный обзор"
http://liu.diva-portal.org/smash/get/diva2:23335/FULLTEXT01

Самое быстрое точное преобразование расстояния от Мейстера:

"Общий алгоритм вычисления расстояний в линейном времени".
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Конструкция алгоритма особенно хорошо подходит для параллельного вычисления.

Это реализовано в моей библиотеке с открытым исходным кодом, которая пытается имитировать Photoshop "Стиль слоя:"

https://github.com/vinniefalco/LayerEffects

Ответ 3

Библиотека OpenCV использует для своей приближенной cv:: distanceTransform функцию, которая передает изображение слева вверху слева и назад. Алгоритм описан в статье "Дистанционные преобразования в цифровых изображениях" из Gunilla Borgefors (Comput. Vision Graph. Image Process, 34, 3, pp. 344-371, 1986).

Алгоритм вычисляет расстояние через комбинацию некоторых основных прыжков (горизонтальный, вертикальный, диагональный и движение рыцаря). Каждый прыжок несет расходы. В следующей таблице показаны затраты на различные скачки.

+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
|   2  |   1  |   0  |   1  |   2  |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+

Расстояние от одного пикселя до другого - это сумма затрат на необходимые прыжки. На следующем изображении показано расстояние от 0-клеток до друг друга. Стрелки показывают путь к некоторым ячейкам. Цветные цифры отражают точное (эвклидовое) расстояние.

Алгоритм работает следующим образом: Следующая маска

+------+------+------+
|   0  |   1  |   2  |
+------+------+------+
|   1  |  1.4 |2.1969|
+------+------+------+
|   2  |2.1969|  2.8 |
+------+------+------+

перемещается из левого верхнего угла изображения в нижнее правое. Во время этого прохода клетки, лежащие внутри границ маски, либо сохраняют свою ценность (если она известна, но и меньше), либо получают значение, рассчитанное путем суммирования значения маски и значения ячейки (если известно) из ячейки ниже маски-0-клетки. После этого выполняется второй проход снизу справа вверху (с вертикальной и горизонтальной перевернутой маской). После второго прохода рассчитываются расстояния.

Ответ 4

Felzenszwalb и Huttenlocher представляют изящный алгоритм, который является точным и O (N) в их статье "Преобразования расстояний выборочных функций", доступной здесь. Они используют тот факт, что квадрат евклидова расстояния является параболой, которая может быть оценена независимо в каждом измерении.

Исходный код также доступен.

Ответ 5

Я применил метод Meijster O (N), указанный в ответе Винни. "Общий алгоритм вычисления расстояний в линейном времени". http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Хорошо, что он может быть распараллелен очень эффективно, вычисляя каждую линию пикселя независимо (это разделительный метод). Запуск на 12 ядрах процессора, поле расстояния 1000 мм объемного изображения вычисляется за несколько секунд.

Решение Felzenszwalb и Huttenlocher "Трансформация расстояний выборочных функций", датированное 2012 г. (цитируется в ответе bw1024), основано на одной и той же идее. Интересно, что они не цитируют работу Мейстера, сделанного 12 лет назад.

Ответ 6

В "Ускоренном алгоритме графического ускорения для сопоставления фазовых фасок и детальном сравнении с высоко оптимизированной реализацией процессора" Майкл Раутер и Дэвид Шрайбер описывают свои характеристики с использованием алгоритма преобразования расстояний "Унифицированного алгоритма линейного времени для вычисления карт расстояний".

В 2012 году они использовали около 15 мс для 8 преобразований расстояния (720 × 576) на процессоре Intel Xeon без многопоточности. На GPU GTX 460 они сделали это за 7 мс.

Я никогда не видел более быстрый ДТ.