При вычислении линии сшивки двух спутниковых снимков нужно получить линию их разделения в области перекрытия так, чтобы визуально объекты оставались по возможности изображенными цельно. На сшивку могут прийти разновременные снимки, и одно и то же поле может быть распахано (коричневое), взошедшее (зеленое), цветущее (желтое или еще какое), лес весной коричневый, летом зеленый, а осенью вообще разноцветный, и нужно чтобы линия сшивки была вычислена по возможности по визуальным границам. Задача не совсем тривиальная, в ней нужно найти решение для весьма расплывчато сформулированной цели - чтобы визуально воспринималось цельно.
В настоящее время практически все основные пакеты обработки снимков используют выделение границ фильтром Собеля по исходным яркостям, выделение или сглаживание текстур в той или иной форме и выделение и их границ также. В результате получается усредненный растр с подчеркнутыми границами, в который входят яркости от границ текстур и исходных яркостей. Фильтр Собеля дает бОльшую яркость там где граница выражена ярче. И через такие пикселы надо провести линию. К ближайшим решенным задачам в этом направлении относится алгоритм Дейкстры прохождения графа с весами дуг.
Для перехода от яркостей фильтра Собеля, где узлами графа считаются пикселы с весами к графу с весами дуг выполняется инвертирование яркостей (чтобы целевые пикселы получили меньшие значения) и вес дуг получается суммой весов узлов. Таким образом, если алгоритм Дейкстры проводит путь по минимальным весам дуг, то этот путь проходит по минимальным яркостям узлов (пикселов), а поскольку используем инвертированное значение то путь соответствует прохождению по границам.
Формулировка вроде бы простая, но при реальном ее применении выясняется, что алгоритм Дейкстры находит путь не только проходящий по минимальным яркостям, но и тяготеет к метрически кратчайшему. Он ищет минимальный интеграл. И в этот интеграл входит не одна величина (вес дуг), а две: веса дуг как весовое расстояние и метрическое расстояние. Пикселы сами по себе имеют географическое расположение (между ними метр или два или сколько-то). И при вычислении линии алгоритм Дейкстры может отдать предпочтение бОльшим весам если они соединяют по более краткому в метрическом выражении пути.
Положим, у нас есть два пиксела разделенные дугой с весом 5:
И положим что рядом проходят другие пикселы, с весами 3, но отстоящие чуть в сторону:
Здесь первый путь состоит из одного отрезка весом в пять и второй из трех отрезков весом в три. Алгоритм Дейкстры выберет первый вместо второго, хотя второй по яркостям более соответствует границам (они меньше).
Здесь метрическим расстоянием в первом пути является 1, а весовым 5, а во втором метрическое расстояние 3, а весовое 3. Общие интегралы соответственно 5 и 9. Хотя второй путь визуально предпочтительнее, будет выбран первый. Визуально это приводит к тому, что даже при наличии границ поблизости будет выбрана линия практически напрямую вместо того чтобы попетлять.
Визуально это может выглядеть примерно так:
Для того чтобы дать алгоритму Дейкстры шанс попетлять перевзвесим относительные вклады метрического и весового расстояния. Будем использовать не исходные яркости, а их степени.
При степени 2 для первого пути получаем 1*52=25, для второго пути 3*32=27, и алгоритм Дейкстры снова выберет первый путь, но уже не всегда он совпадет с предыдущим вариантом. Выглядит это примерно так:
Поднимем градус и возьмем третью степень. Для первого пути получим 1*53=125, а для второго 3*33=81. и уже есть шанс что алгоритм сможет метрически попетлять в поисках более предпочтительного пути по границам. Выглядит это примерно так:
В общем-то получилось намного лучше, хотя метод выглядит как шаманство. В какой-то мере оно так и есть. Увеличение степеней дает сильное ухудшение визуального результата. На мой взгляд оптимум для спутниковых снимков с характерными для начала 21 века разрешениями пиксела (около метров) находится где-то примерно около 3. Впрочем, здесь была использована степень от суммы весов узлов, и вариаций отделения метрического расстояния от весового может быть много - сумма степеней, например.
Работа выполнялась для Image Media Center, функция мозаики спутниковых снимков, проведение линии сшивки.
В настоящее время практически все основные пакеты обработки снимков используют выделение границ фильтром Собеля по исходным яркостям, выделение или сглаживание текстур в той или иной форме и выделение и их границ также. В результате получается усредненный растр с подчеркнутыми границами, в который входят яркости от границ текстур и исходных яркостей. Фильтр Собеля дает бОльшую яркость там где граница выражена ярче. И через такие пикселы надо провести линию. К ближайшим решенным задачам в этом направлении относится алгоритм Дейкстры прохождения графа с весами дуг.
Для перехода от яркостей фильтра Собеля, где узлами графа считаются пикселы с весами к графу с весами дуг выполняется инвертирование яркостей (чтобы целевые пикселы получили меньшие значения) и вес дуг получается суммой весов узлов. Таким образом, если алгоритм Дейкстры проводит путь по минимальным весам дуг, то этот путь проходит по минимальным яркостям узлов (пикселов), а поскольку используем инвертированное значение то путь соответствует прохождению по границам.
Формулировка вроде бы простая, но при реальном ее применении выясняется, что алгоритм Дейкстры находит путь не только проходящий по минимальным яркостям, но и тяготеет к метрически кратчайшему. Он ищет минимальный интеграл. И в этот интеграл входит не одна величина (вес дуг), а две: веса дуг как весовое расстояние и метрическое расстояние. Пикселы сами по себе имеют географическое расположение (между ними метр или два или сколько-то). И при вычислении линии алгоритм Дейкстры может отдать предпочтение бОльшим весам если они соединяют по более краткому в метрическом выражении пути.
Положим, у нас есть два пиксела разделенные дугой с весом 5:
Здесь метрическим расстоянием в первом пути является 1, а весовым 5, а во втором метрическое расстояние 3, а весовое 3. Общие интегралы соответственно 5 и 9. Хотя второй путь визуально предпочтительнее, будет выбран первый. Визуально это приводит к тому, что даже при наличии границ поблизости будет выбрана линия практически напрямую вместо того чтобы попетлять.
Визуально это может выглядеть примерно так:
При степени 2 для первого пути получаем 1*52=25, для второго пути 3*32=27, и алгоритм Дейкстры снова выберет первый путь, но уже не всегда он совпадет с предыдущим вариантом. Выглядит это примерно так:
Работа выполнялась для Image Media Center, функция мозаики спутниковых снимков, проведение линии сшивки.
Комментариев нет:
Отправить комментарий