Травяной пожар трансформируется

В обработке изображений преобразование grassfire представляет собой вычисление расстояния от пикселя до границы области. Его можно описать как «поджигание» границ области изображения для получения дескрипторов, таких как скелет области или медиальная ось . Гарри Блюм представил эту концепцию в 1967 году. ^[1]

Мотивация

Скелет региона может быть полезным дескриптором, поскольку он описывает такие вещи, как симметрия региона, а также его подчасти, углубления и выступы. ^[2] Он также предоставляет способ соотнесения внутренней части региона с формой границы. В преобразовании grassfire скелет формируется в точках региона, где встречаются «пожары». В литературе это описывается как локус встречи волновых форм. ^[2]

Другим преимуществом использования результата преобразования grassfire в качестве дескриптора является то, что он обратим. Если предположить, что информация о том, когда медиальная ось или скелет создается путем встречи волновых форм, сохраняется, то скелет может быть восстановлен путем излучения наружу. ^[1]

Пример алгоритма

Алгоритм ниже — это простой двухпроходный метод вычисления расстояния Манхэттена от границы региона. Конечно, есть несколько других алгоритмов для выполнения преобразования grassfire.

для каждой строки на изображении слева направо для каждого столбца на изображении сверху вниз if ( пиксель находится в области ) { установить пиксель на 1 + минимальное значение северных и западных соседей } else { установить пиксель на ноль } } }​​​​                                           для каждой строки справа налево для каждого столбца снизу вверх if ( пиксель находится в области ) { установить пиксель на min ( значение пикселя , 1 + минимальное значение южных и восточных соседей ) } else { установить пиксель на ноль } } }​​​​​​                                          

Ниже представлен результат этого преобразования. Важно отметить, что наиболее интенсивные линии составляют скелет.

Приложения

Преобразование grassfire может быть абстрагировано для решения различных вычислительных задач. Было показано, что его можно расширить за пределы контекста изображений до произвольных функций. ^[3] Это включает приложения в задачах минимизации энергии, таких как те, которые обрабатываются алгоритмом Витерби , распространение убеждений максимального продукта, распределение ресурсов и методы оптимального управления. ^[3]

Его также можно использовать для вычисления расстояния между регионами, установив фон в качестве региона.

Смотрите также

• Топологический скелет
• Преобразование расстояния

Ссылки

1. Blum, Harry (1967). «Преобразование для извлечения новых дескрипторов формы». В Wathen-Dunn, Weiant (ред.). Модели восприятия речи и визуальной формы (PDF) . Кембридж, Массачусетс: MIT Press. стр. 362–380.
2. Leymarie, F; Levine, MD (1992). «Моделирование преобразования травяного пожара с использованием активной контурной модели». Труды IEEE по анализу паттернов и машинному интеллекту . 14 : 56–75. doi :10.1109/34.107013.
3. Felzenszwalb, Pedro F; Huttenlocher, Daniel P (2012). «Преобразования расстояний выборочных функций». Теория вычислений . 8 : 415–28. CiteSeerX 10.1.1.88.1647 . doi :10.4086/toc.2012.v008a019.