Сегментация спутниковых изображений на основе суперпикселей и разрезов на графах

Введение

Сегментация изображений – это процесс разбиения снимков на группы пикселей на основе определенных критериев. Сегментация является необходимым предварительным этапов для решения многих задач компьютерного зрения высокого уровня: поиск и распознавание объектов, интерпретация сцен, трехмерная реконструкция ^{[1, 2, 3]}. Часто при сегментации из-за большого количества возможных разбиений изображения получаются неоднозначные результаты. Несмотря на широкое использование, задача сегментации часто сопряжена со сложностями. Разработка надежных алгоритмов сегментации, позволяющих формировать значимые области, представляет актуальную задачу. Часто существующие алгоритмы требуют интенсивного ручного ввода и последующего редактирования результатов. Многие исследования в области обработки изображений направлены на то, чтобы улучшить результаты сегментации на основе использования априорной информации. Эти информационные приоритеты включаются в структуру алгоритмов сегментации, чтобы получить более осмысленные результаты.

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

Наиболее известными методами сегментации на основе графов являются: метод на основе минимального покрывающего дерева ^[4]; методы, использующие разрезы графов с функциями стоимости ^{[5, 6]}; методы, использующие разрезы графов с использованием случайных полей Маркова (MRF – Markov Random Field) ^[7]; методы, основанные на поиске кратчайшего пути ^[8]; методы случайного поиска ^[9].

Преимуществом методов разрезов на графах является то, что для разных приложений могут быть использованы различные функции стоимости. Это позволяет задавать условия для выделения на изображениях объектов определенного типа. Существенным недостатком алгоритмов сегментации с использованием разрезов на графах является высокая трудоемкость. Для повышения производительности предлагается использовать суперпиксели ^[10]. Суперпиксели представляют собой сегменты изображения, которые значительно уменьшают сложность последующих задач обработки. Целью работы является разработка алгоритма сегментации спутниковых изображений местности для задач выделения зданий на изображениях.

Разработка алгоритма сегментации спутниковых изображений на основе суперпикселей и разрезов на графах

Для сегментации и последующего выделения объектов необходимо сгруппировать суперпиксели, имеющие определенные цветовые характеристики и значения высоты. Для формирования суперпикселей изображение сегментируется на основе алгоритма минимального покрывающего дерева ^[4] (рис. 1, б). Каждому сегменту были присвоены следующие атрибуты: значение высоты, принадлежность к области растительности, к затененной области или остальным объектам сцены. Значение каждого атрибута в суперпикселе усредняется. Значение высоты осуществляется на основе алгоритма минимизации энергии в пределах региона ^[11] (рис. 1, в).

а)

б)

в)

Рисунок 1. Формирование суперпикселей изображения: а) исходное изображение, б) сегментация на основе минимального покрывающего дерева, в) вычисление карты высот

Следует отметить, что области растительности могут быть представлены деревьями, кустарниками и травяным покровом. При этом области травяного покрова имеют нулевую высоту. Здания имеют ненулевую высоту. Цветовые характеристики крыш зданий в большинстве случаев отличаются от цветовых характеристик растительности и теней. Разработанный алгоритм использует сегментацию на основе спектральной теории графов. Каждый регион имеет свой вес, определяемый цветовыми и трехмерными характеристиками. Изображение представляет собой неориентированный взвешенный граф, узлами которого являются сегменты (рис. 2.). Весами вершин графа являются числа, определяющие принадлежность к некоторому классу (табл. 1). Для разделения регионов на кластеры используется метод разрезов на графах. Преимуществом предлагаемого подхода по сравнению с известным методом нормализованных разрезов является высокая скорость обработки, так как в процессе сегментации участвуют не отдельные пиксели, а сегменты изображения.

а)

б)

Рисунок 2. Представление изображения в виде графа: а) исходное

сегментированное изображение, б) граф сегментированного изображения

Таблица 1. Характеристики сегментов изображения, используемые при группировке регионов

Для выделения растительности по цвету используется величина Ψ_g (i, j), называемая цветовым инвариантом. Цветовой инвариант использует значения пикселей в цветовых каналах системы RGB ^[12]:

Ψ_g (i, j)=4/π*arctan((I(i, j)_g - I(i, j)_b)/ (I(i, j)_g + I(i, j)_b)),

где I(i, j)_g– значения пикселей с координатами i, j в зеленом канале цветовой системы RGB; I(i, j)_b – значения пикселей с координатами i, j в синем канале цветовой системы RGB.

Все пиксели, имеющие значение выше порога T_g, относятся к области растительности V(i, j). Порог вычисляется на основе метода Оцу ^[13]. С использованием метода Оцу пиксели разделяются на два класса: растительность и остальные объекты. Метод использует гистограмму для разделения изображения на 2 класса.

Гистограмма изображения строится следующим образом:

P_i=n_i/N,

i=1, 2, 3,..., L ,

где n_i – количество пикселей, принадлежащих уровню i на всей области цветового инварианта; N – количество пикселей изображения; L – количество уровней цветового инварианта.

При этом находится такое значение порога t, чтобы дисперсия между классами была максимальной. Порог находится итеративно. Начальное значение порога устанавливается t=1. На каждом шаге дисперсия пересчитывается и запоминается ее максимальное значение и величина порога.

Таким образом, изображение можно представить в виде двух непересекающихся множеств пикселей (растительности и других объектов):

[V(i, j)=1 | Ψ_g(i, j)>T_g] v [V(i, j)=0 | Ψ_g(i, j)≤T_g],

где T_g – порог для выделения области растительности по методу Оцу; [V(I, j)=1 | Ψ_g(i, j)>T_g] – множество пикселей, относящихся к области растительности; [V(i, j)=0 | Ψ_g(i, j)≤T_g] – множество пикселей, не относящихся к области растительности.

Для обнаружения областей тени на изображении используется цветовой инвариант Ψ_S(i, j) ^[14]:

Ψ_S(i, j)= 4/π*((I(i, j)_r –(I(i, j)_r² + I(i, j)_g² + I(i, j)_b²)^1/2)/(I(i, j)_r +(I(i, j)_r² + I(i, j)_g² + I(i, j)_b²)^1/2)),

где I(i, j)_r, I(i, j)_g, I(i, j)_b – значения пикселей с координатами i, j в красном, зеленом и синем каналах цветовой системы RGB соответственно.

При обнаружении затененных областей порог рассчитывается также на основе м