Преобразование Травяного огня

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

Мотивация

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

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

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

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

for each row in image left to right
  for each column in image top to bottom
    if (pixel is in region) {
      set pixel to 1 + minimum value of the north and west neighbours
    } else {
      set pixel to zero
    }
  }
}

for each row right to left
  for each column bottom to top
    if (pixel is in region) {
      set pixel to min(value of the pixel,1 + minimum value of the south and east neighbours)
    } else {
      set pixel to zero
    }
  }
}

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

Приложения

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

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

См. также

Ссылки

^ Перейти обратно: ^а ^б Блюм, Гарри (1967). «Преобразование для извлечения новых дескрипторов формы». В Уотен-Данне, Вейант (ред.). Модели восприятия речи и визуальной формы (PDF) . Кембридж, Массачусетс: MIT Press. стр. 362–380.
^ Перейти обратно: ^а ^б Леймари, Ф; Левин, доктор медицины (1992). «Имитация преобразования травяного пожара с использованием модели активного контура». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 14 : 56–75. дои : 10.1109/34.107013 .
^ Перейти обратно: ^а ^б Фельценшвальб, Педро Ф; Хуттенлохер, Дэниел П. (2012). «Дистанционные преобразования выборочных функций». Теория вычислений . 8 : 415–28. CiteSeerX 10.1.1.88.1647 . дои : 10.4086/toc.2012.v008a019 .

[blum-1] Перейти обратно: ^а ^б Блюм, Гарри (1967). «Преобразование для извлечения новых дескрипторов формы». В Уотен-Данне, Вейант (ред.). Модели восприятия речи и визуальной формы (PDF) . Кембридж, Массачусетс: MIT Press. стр. 362–380.

[active-2] Перейти обратно: ^а ^б Леймари, Ф; Левин, доктор медицины (1992). «Имитация преобразования травяного пожара с использованием модели активного контура». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 14 : 56–75. дои : 10.1109/34.107013 .

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

[1]

[2]

[3]