Преобразование расстояния

Преобразование расстояния , также известное как карта расстояний или поле расстояний , представляет собой производное представление цифрового изображения . Выбор термина зависит от точки зрения на рассматриваемый объект: преобразуется ли исходное изображение в другое представление или оно просто наделяется дополнительной картой или полем.

Поля расстояний также могут быть подписаны в том случае, если важно отличить, находится ли точка внутри или снаружи фигуры. ^[1]

На карте каждый пиксель изображения помечается расстоянием до ближайшего пикселя препятствия . Наиболее распространенным типом пикселя препятствия является граничный пиксель в бинарном изображении . На изображении приведен пример преобразования расстояния Чебышева на бинарном изображении .

Обычно преобразование/карта квалифицируется выбранной метрикой . Например, можно говорить о преобразовании манхэттенского расстояния , если базовой метрикой является манхэттенское расстояние . Общие показатели:

Евклидово расстояние
Геометрия такси , также известная как расстояние городского квартала или расстояние Манхэттена .
Расстояние Чебышева

Существует несколько алгоритмов вычисления преобразования расстояния для этих различных метрик расстояния, однако вычисление точного преобразования евклидова расстояния (EEDT) требует специального подхода, если оно вычисляется на сетке изображений. ^[2] Недавно было также предложено вычисление преобразования расстояния с использованием статического уравнения Шредингера. ^[3] Преимущество этого конкретного подхода заключается в получении аналитического решения для преобразований расстояния в замкнутой форме и вычислении преобразования среднего расстояния по набору преобразований расстояния благодаря линейности уравнения Шредингера. Кроме того, этот подход также использовался для расширения преобразований расстояний на отрезки линий и кривые. ^[3]

Приложениями являются цифровая обработка изображений (например, эффекты размытия, скелетонирование ), планирование движения в робототехнике , анализ медицинских изображений для пренатального генетического тестирования и даже поиск пути . ^[4]Поля расстояний со знаком с однородной выборкой использовались для на графическом процессоре с ускорением сглаживания шрифтов , например, исследователями Valve . ^[5]

Поля расстояний со знаком также можно использовать для (3D) твердотельного моделирования . Рендеринг на типичном оборудовании графического процессора требует преобразования в полигональные сетки, например, с помощью алгоритма марширующих кубов . ^[6]

См. также

Функция расстояния со знаком
Представление функции
Параллельная кривая
Методы наборов уровней для расчета расстояний. ^[7]

Ссылки

^ Гибсон, Сара Ф. Фрискен; Перри, Рональд Н.; Роквуд, Алин П.; Джонс, Туи Р. (2000). «Поля расстояний с адаптивной выборкой: общее представление формы для компьютерной графики» (PDF) . В Брауне, Джудит Р.; Экли, Курт (ред.). Материалы 27-й ежегодной конференции по компьютерной графике и интерактивным технологиям, SIGGRAPH 2000, Новый Орлеан, Луизиана, США, 23-28 июля 2000 г. Ассоциация вычислительной техники. стр. 249–254. дои : 10.1145/344779.344899 .
^ Струц, Тило: Дистанционное преобразование и его вычисление. Июнь 2021 г., TECH/2021/06, arXiv:2106.03503v1, https://arxiv.org/abs/2106.03503
^ Jump up to: ^а ^б М. Сетхи, А. Рангараджан и К. Гурумурти, « Дистанционное преобразование Шрёдингера (SDT) для наборов точек и кривых », Конференция IEEE 2012 г. по компьютерному зрению и распознаванию образов , Провиденс, Род-Айленд, США, 2012 г., стр. 198- 205, дои : 10.1109/CVPR.2012.6247676
^ Фельценшвальб, Педро Ф.; Хуттенлохер, Дэниел П. (2012). «Дистанционные преобразования выборочных функций» . Теория вычислений . 8 : 415–428. дои : 10.4086/toc.2012.v008a019 . МР 2967180 .
^ Крис Грин. 2007. Улучшено увеличение векторных текстур и спецэффектов при альфа-тестировании. На курсах ACM SIGGRAPH 2007 (SIGGRAPH '07). Ассоциация вычислительной техники, Нью-Йорк, штат Нью-Йорк, США, 9–18. дои : 10.1145/1281500.1281665
^ Архивировано в Ghostarchive и Wayback Machine : Расширенные визуальные эффекты с DirectX 11 . Ютуб .
^ Киммел, Р.; Кирьяти Н. и Брукштейн AM: Карты расстояний и взвешенные преобразования расстояний . Журнал математического изображения и видения, специальный выпуск по топологии и геометрии в компьютерном зрении, 6: 223-233, 1996.

Внешние ссылки

Быстрое преобразование расстояния в C++ Фельценшвальба и Хуттенлохера
Учебные пособия по дистанционному преобразованию в CVonline
Обзор быстрых точных алгоритмов преобразования евклидова расстояния
Использование карт расстояний для ИИ
Преобразования расстояния Генри Квонга и преобразования динамического шага расстояния Ричарда Скотта, Демонстрационный проект Wolfram .
Морфологическая функция DistanceTransform в Mathematica
Функция морфологического обратного дистанционного преобразования в системе Mathematica
Общий алгоритм вычисления дистанционных преобразований за линейное время [1]

[1] Гибсон, Сара Ф. Фрискен; Перри, Рональд Н.; Роквуд, Алин П.; Джонс, Туи Р. (2000). «Поля расстояний с адаптивной выборкой: общее представление формы для компьютерной графики» (PDF) . В Брауне, Джудит Р.; Экли, Курт (ред.). Материалы 27-й ежегодной конференции по компьютерной графике и интерактивным технологиям, SIGGRAPH 2000, Новый Орлеан, Луизиана, США, 23-28 июля 2000 г. Ассоциация вычислительной техники. стр. 249–254. дои : 10.1145/344779.344899 .

[2] Струц, Тило: Дистанционное преобразование и его вычисление. Июнь 2021 г., TECH/2021/06, arXiv:2106.03503v1, https://arxiv.org/abs/2106.03503

[:0-3] Jump up to: ^а ^б М. Сетхи, А. Рангараджан и К. Гурумурти, « Дистанционное преобразование Шрёдингера (SDT) для наборов точек и кривых », Конференция IEEE 2012 г. по компьютерному зрению и распознаванию образов , Провиденс, Род-Айленд, США, 2012 г., стр. 198- 205, дои : 10.1109/CVPR.2012.6247676

[4] Фельценшвальб, Педро Ф.; Хуттенлохер, Дэниел П. (2012). «Дистанционные преобразования выборочных функций» . Теория вычислений . 8 : 415–428. дои : 10.4086/toc.2012.v008a019 . МР 2967180 .

[5] Крис Грин. 2007. Улучшено увеличение векторных текстур и спецэффектов при альфа-тестировании. На курсах ACM SIGGRAPH 2007 (SIGGRAPH '07). Ассоциация вычислительной техники, Нью-Йорк, штат Нью-Йорк, США, 9–18. дои : 10.1145/1281500.1281665

[6] Архивировано в Ghostarchive и Wayback Machine : Расширенные визуальные эффекты с DirectX 11 . Ютуб .

[7] Киммел, Р.; Кирьяти Н. и Брукштейн AM: Карты расстояний и взвешенные преобразования расстояний . Журнал математического изображения и видения, специальный выпуск по топологии и геометрии в компьютерном зрении, 6: 223-233, 1996.

[1]

[2]

[3]

[4]

[5]

[6]

[7]