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

Question

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

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

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

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

Answer 1

В этой статье рассматриваются известные алгоритмы точного преобразования расстояний:

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

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

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

Дизайн алгоритма особенно хорошо подходит для параллельных вычислений.

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

https://github.com/vinniefalco/LayerEffects

Answer 2

Библиотека 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-клеток. После этого выполняется второй проход снизу справа вверху слева (с перевернутой вертикальной и горизонтальной маской). После второго прохода рассчитываются расстояния.

Answer 3

Есть тонны более новой работы по вычислению функций расстояния.

• Алгоритмы быстрого марширования, которые первоначально пришли из Цициклиса (не Сетиана, как говорит Википедия). Для реализации доступны тонныthis.
• Алгоритмы быстрого свипирования от Чжао
• O (n) (приблизительный) быстрого марша по Яциву

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

Answer 4

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

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

Answer 5

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

Приятно то, что его можно очень эффективно распараллелить, независимо вычисляя каждую линию пикселя (это отдельный метод).Работая на 12 ядрах ЦП, поле расстояния объемного изображения 1000 ^ 3 вычисляется за несколько секунд.

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

Answer 6

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

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

Я никогда не видел быструю дт.