Преобразование Grassfire - Grassfire transform

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

Мотивация

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

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

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

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

  за каждый ряд в изображение оставили к верно    за каждый столбец в изображение верх к Нижний      если (пиксель является в область, край) {        набор пиксель к 1 + минимум ценить из то север и Запад соседи      } еще {        набор пиксель к нуль      }    }  }  за каждый ряд верно к оставили    за каждый столбец Нижний к верх      если (пиксель является в область, край) {        набор пиксель к мин(ценить из то пиксель,1 + минимум ценить из то юг и Восток соседи)      } еще {        набор пиксель к нуль      }    }  }

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

Исходное изображение

Изображение результата

Приложения

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

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

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

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

Рекомендации