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

ИТА ЮФУ

Кафедра ИБТКС

 

 

 

 

 

 

Реферат по предмету «Защита видеоинформации»

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнила:  Поветкина Ю.А.

                                                                           Проверил:  Балабаев С.Л.

 

 

 

 

 

Таганрог 2014

 

Введение

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

Задачи автоматической сегментации делятся на два класса:

• выделение областей изображения с известными свойствами

• разбиение изображения на однородные области

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

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

Автоматические методы

Сегментация как разбиение изображения на однородные области

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

Ясно, что задача разбиения изображения на однородные области поставлена некорректно. Внизу приведены четыре варианта сегментации одного и того же изображения из Berkeley Segmentation Dataset, выполненные разными людьми. Как видно, среди участников эксперимента нет единства в выборе разбиения изображения. Далеко не всегда для изображения есть единственно «правильная» сегментация, и далеко не всегда задача сегментации имеет единственное решение. По той же причине нет и объективного критерия оценки качества разбиения изображения.

Рис. 1. Варианты сегментации изображения

 

Оценка качества работы методов сегментации

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

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

• однородность регионов (однородность цвета или текстуры)

• непохожесть соседних регионов

• гладкость границы региона

• маленькое количество мелких «дырок» внутри региона

• и т. д.

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

Более общий подход к оценке качества работы метода, не учитывающий конкретного приложения, состоит в тестировании методов на общей базе изображений, для которых известна «правильная» сегментация. Например, Berkeley Segmentation Dataset (http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench), насчитывает более 1000 изображений, отсегментированных вручную 30 разными людьми. В [18] приводится описание базы изображений и предлагается численная мера соответствия полученной сегментации «правильной».

Кластеризация цветового пространства

В постановке задачи сегментации прослеживается аналогия с задачей кластеризации (или обучения без учителя). Для того чтобы свести задачу сегментации к задаче кластеризации, достаточно задать отображение точек изображения в некоторое пространство признаков и ввести метрику (меру близости) на этом пространстве признаков.

В качестве признаков точки изображения можно использовать представление ее цвета в некотором цветовом пространстве, примером метрики (меры близости) может быть евклидово расстояние между векторами в пространстве признаков. Тогда результатом кластеризации будет квантование цвета для изображения. Задав отображение в пространство признаков, можно воспользоваться любыми методами кластерного анализа. Наиболее популярные методы кластеризации, используемые для сегментации изображений – к-средних [35] (обобщенный метод Ллойда), EM алгоритм[5].

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

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

Выращивание регионов, дробление-слияние

Методы этой группы учитывают пространственное расположение точек напрямую.

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

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

В основном процедура выращивания региона используется для получения отдельных регионов, однако, применяя эту процедуру последовательно или одновременно для нескольких регионов, можно получить разбиение всего изображения. Существуют различные стратегии выбора зерен (seeds) и выращивания регионов [14, 15, 16, 17].

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

Конкретные методы различаются алгоритмами, используемыми на этапах дробления и слияния. Для получения пересегментации изображения используются алгоритмы k-средних [10], watershed [9, 12], fuzzy expert systems [13], на втором этапе используются алгоритмы k-средних [10], самоорганизующиеся карты Кохонена [11,6], fuzzy expert systems [16], и т. д. На этапе слияния регионов используются relaxation process[3], k-средних [10], SIDE-уравнения [14], самоорганизующиеся карты Кохонена [9],и т. д.

Моделирование изображения Марковским полем

Хорошей моделью изображения служит Марковское случайное поле [7, 8]. Данная модель основана на предположении, что цвет каждой точки изображения зависит от цветов некоторого множества соседних точек. Предложено также обобщение модели изображения также можно обобщить на текстурную сегментацию [7]. Данный подход является достаточно сложным в реализации, однако может являться наиболее адекватным в случае важности учёта текстуры при сегментации. Подробнее о Марковских полях можно прочитать в [7, 8].

Методы, основанные на операторах выделения краев

При данном подходе задача сегментации формулируется как задача поиска границ регионов. Методы поиска границ хорошо разработаны для полутоновых изображений. Полутоновое изображение рассматривается как функция двух переменных (x и y), и предполагается, что границы регионов соответствуют максимумам градиента этой функции. Для их поиска применяется аппарат дифференциальной геометрии (в простейшем случае это фильтры Roberts, Kirsch, Prewitt, Sobel).

Для повышения устойчивости к шуму, перед применением фильтрации изображение обычно размывают. Благодаря коммутативности оператора Лапласа и Гауссова фильтра, можно одновременно осуществлять размытие и поиск границ. В методе Canny комбинируются результаты поиска границ при разной степени размытия.

Рис. 2. Результат применения фильтра Canny

 

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

Исходное изображение 1ый порядок 3ий порядок 5ый порядок

Рис. 3. Результат работы steerable filters с разными параметрами

В [22] предлагается комбинированный подход, использующий steerable filters и cellular neural networks.

Ясно, что выбор критерия для граничных точек определяет качество работы краевых методов. В [33] для выбора оптимального критерия граничных точек применяется машинное обучение.

Основной проблемой методов поиска границ является неустойчивость к шуму. Кроме того, поскольку понятие границы свое для каждой задачи, каждый раз при применении методов поиска границ требуется дополнительно выбирать метод доработки результатов фильтрации (edge linking, edge relaxation).

Методы теории графов

Методы теории графов – одно из наиболее активно развивающеихся направлений в сегментации изображений.

Общая идея методов этой группы следующая. Изображение представляется в виде взвешенного графа, с вершинами в точках изображения. Вес ребра графа отражает сходство точек в некотором смысле (расстояние между точками по некоторой метрике). Разбиение изображения моделируется разрезами графа.

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

 

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

Для поиска разреза минимальной стоимости применяются различные методы: жадные алгоритмы (на каждом шаге выбирается такое ребро, чтобы суммарная стоимость разреза была минимальной), методы динамического программирования (гарантируется, что, выбирая на каждом шаге оптимальное ребро, получим в итоге оптимальный путь), алгоритм Дейкстры, и т. п. Рассмотрим некоторые методы теории графов подробнее.

Метод Normalized Cut предложен J. Shi, J. Malik (1997) [23]. Вводится нормализованный функционал качества разреза так, чтобы одновременно максимизировать различие точек между классами и минимизировать различия точек внутри класса. Оптимизация нормализованного функционала сводится к задаче поиска собственных значений матрицы попарных расстояний между всеми точками изображения. Для сегментации изображения на две части достаточно найти второе по величине собственное значение такой матрицы.

Рис. 5. Пример матрицы попарных расстояний для точечной конфигурации.

 

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

Для данного метода предложены модификации [24, 25], позволяющие сократить сложность алгоритма и требования по памяти за счет аппроксимации матрицы расстояний. Такой подход дает выигрыш в скорости работы в 10-20 раз по сравнению с исходным методом.

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

 

Метод Nested Cuts предложен Olga Veksler (2000) [26]. Основной принцип этого метода состоит в отделении каждой точки изображения от специальной точки за пределами изображения разрезом минимальной стоимости. При таком подходе изображение делится на непересекающиеся сегменты. Показано, что величиной сегментов изображения можно управлять, накладывая ограничения на стоимость разреза. В статье описывается эффективный алгоритм, основанный на свойствах разбиения. Однако этот метод работает крайне медленно.