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

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(дополнение)
Строка 21: Строка 21:
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.
-
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <tex> f(X) = \arg\min_Y E(X, Y, W) </tex>. Здесь X — признаки, Y — сегментация,
+
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <tex> E(X, Y, W) </tex>. Здесь X — признаки, Y — сегментация,
W — параметры модели. Функция Е выглядит следующим образом: <br>
W — параметры модели. Функция Е выглядит следующим образом: <br>
<tex> E(X, Y, W) = \sum_{p \in P} ( \vec{x}_p^T \vec{w}_U) y_p + \sum_{(p, q) \in E} (\vec{x}_{pq}^T \vec{w}_P) [y_p \neq y_q] </tex>
<tex> E(X, Y, W) = \sum_{p \in P} ( \vec{x}_p^T \vec{w}_U) y_p + \sum_{(p, q) \in E} (\vec{x}_{pq}^T \vec{w}_P) [y_p \neq y_q] </tex>
Строка 35: Строка 35:
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), [http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%A5%D1%8D%D0%BC%D0%BC%D0%B8%D0%BD%D0%B3%D0%B0 расстояние Хэмминга] между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания используется ошибка сегментации определяется количеством правильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении:
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), [http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%A5%D1%8D%D0%BC%D0%BC%D0%B8%D0%BD%D0%B3%D0%B0 расстояние Хэмминга] между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания используется ошибка сегментации определяется количеством правильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении:
-
<tex> error(Y, \hat{Y}) = \frac{\sum_p [y_p \neq 1][\hat{y}_p = 1]}{\sum_p [\hat{y}_p = 1]} + \frac{\sum_p [y_p \neq 0][\hat{y}_p = 0]}{\sum_p [\hat{y}_p = 0]}</tex>.
+
<tex> error(T, \hat{T}) = \frac{\sum_i [t_i \neq 1][\hat{t}_i = 1]}{\sum_i [\hat{t}_i = 1]} + \frac{\sum_i [t_i \neq 0][\hat{t}_i = 0]}{\sum_i [\hat{t}_i = 0]}</tex>.
-
Здесь Y — текущая разметка изображения, Ŷ — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.
+
Здесь T — текущая разметка изображения, <tex>\hat{T} </tex> — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения. Заметим, что по «суперпиксельной» сегментации Y можно однозначно построить «попиксельную» сегментацию T, а значит функцию потерь можно выразить в терминах «суперпиксельной» сегментации Y.
=== Задание ===
=== Задание ===
К промежуточной сдаче задания необходимо
К промежуточной сдаче задания необходимо
# Реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений.
# Реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений.
-
# Протестировать реализованные процедуры на модельных данных.
+
# Протестировать реализованные процедуры на модельных данных. Использовать хотя бы 1 парный признак.
# Написать отчет в формате PDF с описанием всех проведенных исследований.
# Написать отчет в формате PDF с описанием всех проведенных исследований.
Строка 48: Строка 48:
# Придумать не менее 5 парных различных парных признаков.
# Придумать не менее 5 парных различных парных признаков.
# При помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке.
# При помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке.
-
# При помощи обученного сегментатора получить разметки тестовой выборки изображения. Привести примеры удачных и неудачных сегментаций.
+
# При помощи обученного сегментатора получить разметки тестовой выборки изображения. Привести примеры удачных и неудачных сегментаций. Студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, будут награждены бонусами.
# Написать отчет в формате PDF с описанием всех проведенных исследований.
# Написать отчет в формате PDF с описанием всех проведенных исследований.
Строка 61: Строка 61:
=== Описание форматов данных ===
=== Описание форматов данных ===
-
Названия файлов, относящихся к каждому объекту обучающей выборке, начинаются с названия объекта: imgTrain_{номер файла}. Для каждого объекта выданы следующие файлы:
+
Названия файлов, относящихся к каждому объекту обучающей выборки, начинаются с названия объекта: imgTrain_{номер файла}. Для каждого объекта выданы следующие файлы:
*само изображение: imgTrain_XXX.png
*само изображение: imgTrain_XXX.png
*правильная разметка изображения: imgTrain_XXX_groundtruth.png
*правильная разметка изображения: imgTrain_XXX_groundtruth.png
Строка 68: Строка 68:
** unaryFeatures — массив типа double размером количество суперпикселей на количество унарных признаков.
** unaryFeatures — массив типа double размером количество суперпикселей на количество унарных признаков.
-
Названия файлов, относящихся к каждому объекту обучающей выборке, начинаются с названия объекта: imgTrain_{номер файла}. Для каждого объекта выданы следующие файлы:
+
Названия файлов, относящихся к каждому объекту тестовой выборки, начинаются с названия объекта: imgTest_{номер файла}. Для каждого объекта выданы следующие файлы:
*само изображение: imgTest_XXX.png
*само изображение: imgTest_XXX.png
*mat-файлы, содержащие признаки и суперпиксели для изображения: imgTest_XXX_data.mat. В каждом файле присутствуют следующие переменные:
*mat-файлы, содержащие признаки и суперпиксели для изображения: imgTest_XXX_data.mat. В каждом файле присутствуют следующие переменные:
Строка 144: Строка 144:
|}
|}
-
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets.
+
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.
=== Рекомендации по выполнению задания ===
=== Рекомендации по выполнению задания ===
 +
# Библиотека SVMstruct не позволяет установить ограничения на знак весов парных признаков <tex> \vec{w}_P </tex>. Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
 +
# В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При этом точность сегментации модельной выборки должна быть хорошей.
 +
# Для работы с библиотекой SVMstruct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
 +
# Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить явно выраженные ситуации недообучения и переобучения.
 +
# В качестве процедуры скользящего контроля рекомендуется выбрать схему [[Скользящий контроль| контроля по 5 блокам]] (5-fold CV).
=== Данные для выполнения задания ===
=== Данные для выполнения задания ===

Версия 16:43, 17 апреля 2012

Задание находится в разработке.

Не приступайте к выполнению задания пока не убрано это сообщение.


Содержание

Основная статья: Графические модели (курс лекций)

Начало выполнения задания: 18 апреля 2012

Промежуточная сдача задания: 2 мая 2012, 23:59

Окончательная сдача задания: 9 мая 2012, 23:59

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

Сегментация изображений

В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.

Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: E(X, Y, W) . Здесь X — признаки, Y — сегментация, W — параметры модели. Функция Е выглядит следующим образом:
E(X, Y, W) = \sum_{p \in P} ( \vec{x}_p^T \vec{w}_U) y_p + \sum_{(p, q) \in E} (\vec{x}_{pq}^T \vec{w}_P) [y_p \neq y_q]

Здесь P — множество суперпикселей (сегментов) изображения, Е — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные y_p — бинарные индикаторы, указывающие принадлежит ли суперпиксель объекту; \vec{x}_p — векторы унарных признаков для суперпикселей; \vec{x}_{pq} — векторы парных признаков для пар соседних суперпикселей; W = (\vec{w}_U, \vec{w}_P) — веса унарных и парных признаков.

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

Заметим, что если для всех пар соседних суперпикселей величины \vec{x}_{pq}^T \vec{w}_P неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа.

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

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

error(T, \hat{T}) = \frac{\sum_i [t_i \neq 1][\hat{t}_i = 1]}{\sum_i [\hat{t}_i = 1]} + \frac{\sum_i [t_i \neq 0][\hat{t}_i = 0]}{\sum_i [\hat{t}_i = 0]}.

Здесь T — текущая разметка изображения, \hat{T} — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения. Заметим, что по «суперпиксельной» сегментации Y можно однозначно построить «попиксельную» сегментацию T, а значит функцию потерь можно выразить в терминах «суперпиксельной» сегментации Y.

Задание

К промежуточной сдаче задания необходимо

  1. Реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений.
  2. Протестировать реализованные процедуры на модельных данных. Использовать хотя бы 1 парный признак.
  3. Написать отчет в формате PDF с описанием всех проведенных исследований.

К окончательной сдаче задания

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

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

  1. реализация алгоритма построения разреза графов, совместимая с MATLAB;
  2. реализации структурного метода опорных векторов в библиотеке SVM-struct с интерфейсом под MATLAB: http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html
  3. исходные изображения: обучающая и тестовая выборки;
  4. правильная сегментация изображений обучающей выборки;
  5. суперпиксели изображений обучающей и тестовой выборок, найденные при помощи библиотеки BSR;
  6. признаки для каждого суперпикселя; вектором признаков является гистограмма по мешку из 128 слов, построенному по SIFT; признаки посчитаны при помощи библиотеки VLFeat.

Описание форматов данных

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

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

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

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

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

Обучение
[model, time] = train_sSVM(X, Y, options)
ВХОД
X — обучающая выборка, массив типа cell размера N x 1, где N - размер обучающей выборки; каждая элемент содержит путь к файлу XXX_data.png для соответствующего изображения;
Y — ответы на обучающей выборки, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
options — набор параметров метода, структура с полями:
   'С' — параметр C структурного метода опорных векторов
   'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей
ВЫХОД
model — модель, обученная при помощи вашего метода;
time — время работы алгоритма;


Предсказание
Y = predict_sSVM(X, model)
ВХОД
X — выборка, массив типа cell размера N x 1, где N - размер обучающей выборки; каждая элемент содержит путь к файлу XXX_data.png для соответствующего изображения;
model — модель, полученная при помощи процедуры train_sSVM;
ВЫХОД
Y — ответы на выборке X, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;


Обучение и предсказание для базы с машинами
[train_error, test_Y] = cars()
ВЫХОД
train_error — ошибка на обучающей выборке;
test_Y — ответы на тестовой выборке, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;

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

Рекомендации по выполнению задания

  1. Библиотека SVMstruct не позволяет установить ограничения на знак весов парных признаков \vec{w}_P . Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
  2. В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При этом точность сегментации модельной выборки должна быть хорошей.
  3. Для работы с библиотекой SVMstruct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
  4. Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить явно выраженные ситуации недообучения и переобучения.
  5. В качестве процедуры скользящего контроля рекомендуется выбрать схему контроля по 5 блокам (5-fold CV).

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

Оформление задания

Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 5. ФИО». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.

Письмо должно содержать:

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • train_sSVM.m, predict_sSVM.m, cars.m
  • разметку тестовой выборки в таком же формате, как выдана разметка обучающей выборки
  • Набор вспомогательных файлов при необходимости
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29/2012/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_5»
Личные инструменты