Графические модели (курс лекций)/2013/Задание 5

Среда реализации — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.

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

Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: . Здесь X — признаки, Y — «суперпиксельная» сегментация, W — параметры модели. Функция Е выглядит следующим образом:

Здесь V — множество суперпикселей изображения, — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные — метки классов, 0 — фон, 1 — объект; — векторы унарных признаков для суперпикселей; — векторы парных признаков для пар соседних суперпикселей; — веса унарных и парных признаков.

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

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

1. слагаемые, образующие парные потенциалы, записывались так: в рамках данного задания для упрощения работы парные потенциалы ограничиваются только обобщенными потенциалами Поттса, что соответствует следующим ограничениям на веса: ;
2. слагаемые, образующие унарные потенциалы, записывались так: в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».

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

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

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

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

Здесь T — текущая разметка изображения, — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.

В рамках 1-го этапа задания необходимо:

1. выписать формулу для ошибки, усредненной по классам, в терминах суперпикселей Y;
2. показать, как решать задачу при помощи алгоритма построения разреза графа;
3. реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений;
4. протестировать реализованные процедуры на модельных данных, используя хотя бы 1 парный признак;
5. написать отчет в формате PDF с описанием всех проведенных исследований.

В рамках 2-го этапа задания необходимо:

1. придумать не менее 5 различных парных признаков;
2. при помощи скользящего контроля подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке, в крайних значениях нужно получить ситуации недообучения и переобучения;
3. при помощи обученного сегментатора получить разметки тестовой выборки изображений; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы;
4. написать отчет в формате PDF с описанием всех проведенных исследований.

Для выполнения задания выдается:

1. реализация алгоритма построения разреза графов, совместимая с MATLAB;
2. реализации структурного метода опорных векторов в библиотеке SVM-struct с интерфейсом под MATLAB: http://www.vlfeat.org/

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

• изображение: imgTrain_XXX.png
• правильная разметка изображения: imgTrain_XXX_groundtruth.png
• mat-файлы, содержащие признаки и суперпиксели для изображения: imgTrain_XXX_data.mat. В каждом файле присутствуют следующие переменные:
  • superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
  • neighborhood — массив типа double размером #(пары соседних суперпикселей) x 2; каждая строка содержит номера соседних суперпикселей;
  • unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).

  Здесь и далее через #(название объекта) обозначается количество объектов.

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

  • изображение: imgTest_XXX.png
  • mat-файлы, содержащие признаки и суперпиксели для изображения: imgTest_XXX_data.mat. В каждом файле присутствуют следующие переменные:
    • superpixelMap — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
    • neighborhood — массив типа double размером #(пары соседних суперпикселей) x 2; каждая строка содержит номера соседних суперпикселей;
    • unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели).

    ВНИМАНИЕ! Разметку тестовой выборки необходимо присылать в следующем формате: файлы imgTest_XXX_labeling.png в одной директории. Каждый файл должен содержать черно-белое изображение, аналогичное imgTrain_XXX_groundtruth.png

    Спецификация реализуемых функций

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

    📎📎📎📎📎📎📎📎📎📎