Что представляет собой текстурная сегментация

Рис. 7. Результат работы Nested Cuts

 

M. Pavan и M. Pelillo (2003) был предложен новый подход, основанный на разрезах графа [27]. Авторы вводят такое определение сегмента, которое позволяет переформулировать задачу поиска разреза на графе как задачу квадратичного программирования. Предложен метод решения полученной задачи, основанный на методах эволюционной теории игр. Этот подход также требует хранения в памяти матрицы попарных расстояний, как и метод Normalized Cuts.

Рис. 8. Результаты работы метода

 

Метод сегментации SWA (Segmentation by Weighted Aggregation) основан на группировании схожих точек изображения [28, 29, 30] . Основная идея метода состоит в построении пирамиды взвешенных графов, каждый из которых получен из предыдущего путем объединения схожих вершин.

Рис. 9 Построение пирамиды взвешенных графов для изображения.

 

На каждом шаге веса связей пересчитываются. В процессе построения пирамиды вычисляются различные статистики, характеризующие форму, цвет, текстуру регионов, эти статистики используются для вычисления меры сходства регионов. Затем, следуя идеологии методов теории графов, для полученного графа вводится функционал стоимости разреза и ищется разрез минимальной стоимости. При этом, в отличие от большинства методов теории графов, SWA имеет сложность O(n), где n - число точек изображения, причем число операций для каждой точки составляет всего несколько десятков.

В модификации алгоритма [29] на каждом следующем шаге анализируется и корректируется результат предыдущего агрегирования, а также используется информация о границах полученных сегментов.

Рис. 10. Сравнение результатов работы алгоритма SWA [28], его модификации [29] и Normalized cuts

 

Качество работы методов теории графов сильно зависит от выбора метрики. Поэтому для выбора оптимальной метрики в [31, 32] применяют машинное обучение. Основные проблемы методов теории графов - это низкая скорость работы и большие затраты памяти. Большинство методов требует хранения в памяти матрицы попарных расстояний между точками изображения, размер которой равен квадрату числа точек. Такие ограничения делают графовые методы практически неприменимыми для больших изображений.

Оптимизационный подход

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

Примером оптимизационного метода являетя алгоритм JSEG [17]. Вводится функционал качества сегментации, использующий распределение цветов на изображении.

Рис. 11. Примеры разных цветовых карт (+, 0, * - различные цвета). Значения функционала: 1) J=1.72, 2) J=0, 3) J=0.855, 4) J=0.05, 5) J=0

 

Однако оптимизация этого функционала напрямую – очень трудоемкая задача. В методе JSEG используется жадный алгоритм оптимизации введенного функционала качества сегментации. Значение функционала качества вычисляется для окрестности каждой точки. Большие значения функционала качества соответствуют границам однородных областей, маленькие значения соответствуют центрам регионов. Затем применяется выращивание регионов, в качестве зерен используются точки с минимальными значениями функционала. На последнем этапе проводится слияние мелких регионов.

На рисунке внизу приведены результаты работы алгоритма JSEG на разных картинках и приведены значения функционала качества для исходной картинки и для полученного разбиения.

Рис. 12. Результаты работы JSEG.

 

Настройка параметров

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

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

Например, в [20] предлагается метод настройки порога для бинаризации фотографий рукописных текстов. Метод обучается на наборе изображений, для каждого из которых вручную выбраны оптимальные значения порога.

Рис. 13 Изображение рукописного текста, бинаризованное изображение, полученное методом Бернсена и бинаризованное изображение, полученное описанным методом

 

Во многих работах при помощи машинного обучения настраиваются параметры метрики для графовых методов. В [31, 34] авторы графового метода Normalized Cut предложили вариант Normalized Cut с настраиваемой метрикой.

По набору размеченных фотографий (Berkley Segmentation dataset) составляется обучающая выборка для настройки метрики. В обучающую выборку входят пары точек с известной классификацией. К первому классу относятся пары точек, лежащие в одном регионе, второй класс составляют пары точек, лежащие в разных регионах. Причем, две точки изображения считаются лежащими в одном и том же регионе только, если они оказались в одном и том же регионе во всех вариантах сегментации данного изображения.

Затем, в соответствии с идеологией машинного обучения, задача сегментации изображения формулируется как задача построения классификатора по данной обучающей выборке. Далее для каждой пары точек из обучающей выборки вычисляется вектор признаков. В [31] в качестве признаков используются несколько простых метрик: текстурный градиент, энергия по направлению, градиент яркости, градиент цвета по прямой, соединяющей пару точек. Также используются метрики, учитывающие различия в распределении цвета и текстурных элементов в небольших окрестностях этих точек.

Рис. 14 Результаты работы настроенного метода

 

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

Такую методику целесообразно использовать в случае, когда известно, что предстоит работать с однотипными изображениями и есть много примеров таких изображений. Чем более похожи между собой изображения, тем лучше можно настроить параметры, и, соответственно, тем лучшие результаты даст обученный метод на новых изображениях.