Участник:Anton/Песочница

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

< Участник:Anton(Различия между версиями)
Перейти к: навигация, поиск
 
(43 промежуточные версии не показаны)
Строка 1: Строка 1:
 +
{{stop|
 +
'''Задание находится в разработке.'''<br/>
 +
Не приступайте к выполнению задания пока не убрано это сообщение.
 +
}}
 +
{{TOCright|300px}}
{{TOCright|300px}}
{{Main|Графические модели (курс лекций)}}
{{Main|Графические модели (курс лекций)}}
-
[[Изображение:GM12 task3 intro.png‎ | 600px]]
+
[[Изображение:GM12 task4 intro.png‎ | 600px]]
-
'''Начало выполнения задания''': 28 марта 2012
+
'''Начало выполнения задания''': 18 апреля 2012
-
'''Срок сдачи''': {{ins|11 апреля 2012, 23:59}}
+
'''1-й этап сдачи задания''': {{ins|2 мая 2012, 23:59}}
-
Задание состоит из двух вариантов. Распределение вариантов задания по студентам:
+
'''2-й этап сдачи задания''': {{ins|9 мая 2012, 23:59}}
-
{|class="standard"
+
-
!''Вариант 1'' || ''Вариант 2''
+
-
|-
+
-
|Ромов Петр, 202 || Лямаев Сергей, 202
+
-
|-
+
-
|Иванов Петър, 202 || Елшин Денис, 317
+
-
|-
+
-
|Некрасов Константин, 317 || Новиков Павел, 317
+
-
|-
+
-
|Меркулова Татьяна, 317 || Лобачева Екатерина, 209
+
-
|-
+
-
|Батанов Павел, 321 || Птенцов Сергей, 321
+
-
|-
+
-
|Сапатов Александр, 321 || Новикова Татьяна, 321
+
-
|-
+
-
|Шальнов Евгений, 321 || Конев Артем, 321
+
-
|-
+
-
|Костин Григорий, 320 || Икрам Магжан, 325
+
-
|-
+
-
|Переходько Евгения, 325 || Парамонов Сергей, 324
+
-
|-
+
-
|Русланова Анна, 421 || Ермишин Федор, 321
+
-
|-
+
-
|Исламгулов Ильдар, 420 || Грядицкая Юлия, 411
+
-
|-
+
-
|Касперский Иван, 417 || Тихонов Андрей, 417
+
-
|-
+
-
|Колев Денис, 417 || Вартанов Сергей, 427
+
-
|-
+
-
|Ермаков Михаил, 427 || Баранов Леонид, 428
+
-
|-
+
-
|Пироженко Александр, 428 || Рябов Сергей, 428
+
-
|-
+
-
|Кузин Сергей, 528 || Светличный Дмитрий, ВВО
+
-
|-
+
-
|Заякина Ольга, ВВО || Беликов Владимир
+
-
|-
+
-
|Гребенкина Мария || Субботин Никита
+
-
|-
+
-
|}
+
Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
-
== Марковское случайное поле ==
 
-
[[Изображение:SMAIS11_grid.jpg‎|100px|thumb|Система соседства — прямоугольная решетка]]
 
-
Марковское случайное поле (MRF) — графическая модель, энергия (отрицательный логарифм правдоподобия) которой записывается в виде:<br>
 
-
<tex>
 
-
E(X) = \sum_{p \in P} D_p(x_p) + \sum_{(p, q) \in E} V_{pq}(x_p, x_q),
 
-
</tex><br>
 
-
где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы.
 
-
Рассмотрим модель со следующими ограничениями:
+
=== Сегментация изображений ===
-
*переменные <tex> x_p </tex> дискретны и принимают значения из множества {1,…,K}, K ≥ 2,
+
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон.
-
*система соседства E — прямоугольная решетка,
+
В дальнейшем работа осуществляется в терминах небольших сегментов изображения — суперпикселей.
-
*бинарные потенциалы V являются обобщенными потенциалами Поттса: <tex>V_{pq} = c_{pq} [x_p \neq x_q] </tex>.
+
Заметим, что по «суперпиксельной» сегментации изображения можно однозначно построить «попиксельную» сегментацию.
-
В рамках этого задания требуется:
+
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <tex> E(X, Y, W) </tex>. Здесь X — признаки, Y — «суперпиксельная» сегментация,
-
#реализовать алгоритм поиска конфигурации <tex>X</tex>, обладающей минимальной энергией (TRW или α-расширение),
+
W — параметры модели. Функция Е выглядит следующим образом: <br>
-
#протестировать реализованный алгоритм на модельных задачах,
+
<tex> E(X, Y, W) = \sum_{p \in V} ( \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>
-
#применить реализованный алгоритм для задачи стерео,
+
-
#сравнить алгоритмы TRW и α-расширение на задаче стерео.
+
-
=== MRF для стерео ===
+
Здесь V — множество суперпикселей изображения, Е — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные <tex>y_p</tex> — метки классов, 0 — фон, 1 — объект; <tex> \vec{x}_p </tex> — векторы унарных признаков для суперпикселей; <tex> \vec{x}_{pq} </tex> — векторы парных признаков для пар соседних суперпикселей; <tex> W = (\vec{w}^U, \vec{w}^P) </tex> — веса унарных и парных признаков.
-
Задача стерео состоит в отнесении каждого пикселя изображения к одному из K классов. В интерактивном варианте пользователь отмечает часть пикселей, принадлежащих каждому классу. После этого требуется автоматически разметить оставшуюся часть изображения.
+
-
Для задачи сегментации марковское случайное поле строится следующим образом:
+
Заметим, что если для всех пар соседних суперпикселей величины <tex> \vec{x}_{pq}^T \vec{w}^P </tex> неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа.
-
*Каждая переменная <tex>x_p</tex> соответствует пикселю изображения.
+
-
*Используется стандартная 4-х связная система соседства.
+
-
*Если пиксель p отнесен пользователем к классу k, то унарные потенциалы „разрешают“ переменной <tex>x_p</tex> принимать только значение k: <br><tex>D_p(k) = 0,\ D_p(l) = +\infty, l \neq k</tex>.
+
-
*Если пиксель p не отнесен пользователем ни к одному из классов, то унарные потенциалы принимают значения равные минус логарифму правдоподобия принадлежности пикселя цвета <tex> I_p </tex> соответствующему классу: <tex>D_p(k) = -\log P_k(I_p) </tex>.
+
-
*Цветовые модели объектов можно восстановить по пикселям, размеченным пользователем, при помощи EM-алгоритма восстановления смеси нормальных распределений в пространстве [http://en.wikipedia.org/wiki/YUV YUV].
+
-
*В качестве парных потенциалов выбираются обобщенные потенциалы Поттса, которые поощряют разрезы в тех местах, где цвет изображения сильно меняется: <tex> c_{pq} = A + B\:\exp\left(-\frac{|| I_p - I_q ||^2}{2\sigma^2}\right) </tex>, A ≥ 0, B ≥ 0, σ — параметры.
+
-
== Вариант 1 : TRW==
+
Приведенный выше способ записи энергии E отличается от способа записи, разобранного на лекции, в двух местах:
 +
# слагаемые, образующие парные потенциалы, записывались так: <tex>\sum_{(p, q) \in E} \sum_{k, \ell \in \{0, 1\}} (\vec{x}_{pq}^T \vec{w}^P_{k\ell}) [y_p = k][y_q = \ell];</tex> в рамках данного задания для упрощения работы парные потенциалы ограничиваются только обобщенными потенциалами Поттса, что соответствует следующим ограничениям на веса: <tex>\vec{w}^P_{00} = \vec{w}^P_{11} = 0; \; \vec{w}^P_{10} = \vec{w}^P_{01}</tex>;
 +
# слагаемые, образующие унарные потенциалы, записывались так: <tex>\sum_{k\in\{0, 1\}}\sum_{p \in V} ( \vec{x}_p^T \vec{w}^U_k) [y_p = k];</tex> в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».
 +
 
 +
Ограничения накладываемые на веса, соответствующие парным признаком уменьшают гибкость модели. Упрощение, связанное с унарными потенциалами не влияет на гибкость модели (верно только для случая двух классов).
 +
 
 +
В качестве унарных признаков обычно выбирают гистограммы по мешкам слов, построенных по каким-либо локальным дескрипторам изображений. В качестве парных признаков выбирают различных обобщенные модели Поттса; парный признак, равный одной и той же константе по всем парам соседних суперпикселей, соответствует обычной модели Поттса.
 +
 
 +
Параметры модели W можно настраивать при помощи структурного метода опорных векторов (sSVM), решая оптимизационную задачу при помощи метода отсекающих плоскостей.
 +
 
 +
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), расстояние Хэмминга между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания ошибка сегментации определяется количеством неправильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении:
 +
 
 +
<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>.
 +
 
 +
Здесь T — текущая разметка изображения, <tex>\hat{T} </tex> — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.
=== Задание ===
=== Задание ===
-
* Вывести все формулы, использующиеся в вашей реализации TRW (формулировки прямой и двойственной задач, формула подсчета субградиента, конкретная схема субградиентного подъема, и т.д.).
+
В рамках 1-го этапа задания необходимо
-
* Реализовать алгоритм TRW.
+
# выписать формулу для ошибки, усредненной по классам в терминах суперпикселей Y;
-
* Протестировать алгоритм TRW на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
+
# показать как решать задачу <tex> \max_Y (-E(X, Y, W) + error(T(Y), \hat{T}))</tex> при помощи алгоритма построения разреза графа;
-
* Привести примеры наличия и отсутствия зазора между решениями прямой и двойственной задач (например, зазор должен отсутствовать в случае субмодулярной энергии).
+
# реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений;
-
* Реализовать процедуру сегментации изображений с заданными пользователем семенами.
+
# протестировать реализованные процедуры на модельных данных, используя хотя бы 1 парный признак;
-
* Привести примеры удачных сегментаций (не менее 5). Требуется самостоятельно выбрать изображения (реалистичные), указать семена и отсегментировать при помощи реализованного метода. В отчет нужно вставлять и исходные изображения, и маски семян.
+
# написать отчет в формате PDF с описанием всех проведенных исследований.
-
* На нескольких (не менее 3) задачах сегментации из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству сегментации. Все выводы должны быть подтверждены числами, графиками, картинками.
+
 
-
* Написать отчет в формате PDF с описанием всех проведенных исследований.
+
В рамках 2-го этапа задания необходимо
 +
# придумать не менее 5 различных парных признаков;
 +
# при помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке;
 +
# при помощи обученного сегментатора получить разметки тестовой выборки изображения; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы;
 +
# написать отчет в формате PDF с описанием всех проведенных исследований.
 +
 
 +
Для выполнения задания выдается:
 +
# реализация алгоритма построения разреза графов, совместимая с MATLAB;
 +
# реализации структурного метода опорных векторов в библиотеке SVM-struct с интерфейсом под MATLAB: http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html
 +
# исходные изображения: обучающая и тестовая выборки;
 +
# правильная сегментация изображений обучающей выборки;
 +
# суперпиксели изображений обучающей и тестовой выборок, найденные при помощи библиотеки [http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html BSR];
 +
# признаки для каждого суперпикселя; вектором признаков является гистограмма по мешку из 128 слов, построенному по [http://en.wikipedia.org/wiki/Scale-invariant_feature_transform SIFT]; признаки посчитаны при помощи библиотеки [http://www.vlfeat.org/ VLFeat].
 +
 
 +
=== Описание форматов данных ===
 +
 
 +
Названия файлов, относящихся к каждому объекту обучающей выборки, начинаются с названия объекта: 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 #(суперпиксели).
=== Спецификация реализуемых функций ===
=== Спецификация реализуемых функций ===
 +
{|class="standard"
{|class="standard"
-
!''Алгоритм TRW''
+
!''Обучение''
-
|-
+
-
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC)
+
|-
|-
-
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, options)
+
|[model, time] = train_sSVM(X, Y, options)
|-
|-
|ВХОД
|ВХОД
Строка 106: Строка 99:
|
|
{|border="0"
{|border="0"
-
|unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
+
|X — обучающая выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
|-
|-
-
|vertC — коэффициенты <tex> c_{pq}</tex>, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
+
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
|-
|-
-
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
+
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
|-
|-
-
|options — (необязательный аргумент) набор дополнительных параметров, массив типа '''cell''' вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
+
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
|-
|-
-
|&nbsp;&nbsp;'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
+
|Y — ответы на обучающей выборки, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
|-
|-
-
|&nbsp;&nbsp;'argEps' — порог сходимости по аргументу;
+
|options — набор параметров метода, структура с полями:
|-
|-
-
|&nbsp;&nbsp;'display' — параметр типа logical: если true, то на каждой итерации нужно выводить на экран номер итерации, текущее значение энергии и нижней границы;
+
|&nbsp;&nbsp; 'С' — параметр C структурного метода опорных векторов;
 +
|-
 +
|&nbsp;&nbsp; 'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей;
|}
|}
|-
|-
Строка 125: Строка 120:
|
|
{|
{|
-
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
+
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки).
|-
|-
-
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
|time — время работы алгоритма;
-
|-
+
-
|lowerBound — значения нижней границы на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
-
|-
+
-
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма.
+
|}
|}
|}
|}
-
Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 
-
{|class="standard"
 
-
!''Сегментация изображений''
 
-
|-
 
-
|[segmentation] = segmentImage(image, seeds)
 
-
|-
 
-
|ВХОД
 
-
|-
 
-
|
 
-
{|border="0"
 
-
|image — изображение, массив типа double размера N x M x 3 (все значения в этом массиве в интервале от 0 до 1).
 
-
|-
 
-
|seeds — семена, заданные пользователем, массив типа logical размера N x M x K, элементы массива принимают значения true или false;
 
-
|}
 
-
|-
 
-
|ВЫХОД
 
-
|-
 
-
|
 
-
{|
 
-
|segmentation — сегментация изображения, массив типа double размера N x M со значениями 1,...,K;
 
-
|}
 
-
|}
 
-
Обратите внимание: в процедуре segmentImage параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 
-
 
-
=== Рекомендации по выполнению задания ===
 
-
1. При разбиении MRF-решетки только на вертикальные и горизонтальные цепочки формулировка несколько упрощается:
 
-
*Каждое ребро графа принадлежит только одному подграфу, а, значит, не нужно вводить двойственные переменные, соответствующие ребрам.
 
-
*Каждая вершина принадлежит только двум деревьям, а, значит, можно ввести |P|K двойственных переменных, соответствующих условиям <tex> y_{pk}^{hor} = y_{pk}^{vert}, \;\; p \in P, \;\; k = 1,\dots,K</tex>, где hor и vert обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.
 
-
 
-
2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема.
 
-
Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:<br>
 
-
<tex>\vec{\lambda}_{new} = \vec{\lambda}_{old} + \alpha_t \vec{g}_t, </tex>
 
-
где <tex>\vec{g}_t</tex> — субградиент в текущей точке, <tex>\alpha_t</tex> — параметр, отвечающий за длину сдвига.
 
-
В рамках данного практического задания можно использовать любой способ субградиентного подъема. Например, можно использовать следующий адаптивный метод выбора длины шага:<br>
 
-
<tex>\alpha_t = \frac{\text{Approx}_t - \text{Dual}_t}{|| \nabla \vec{g}_t|| ^ 2},</tex><br>
 
-
где <tex>\text{Dual}_t</tex> — текущее значение двойственной функции, <tex>\text{Approx}_t</tex> — оценка оптимума двойственной функции, которую можно определять следующим способом:<br>
 
-
<tex>\text{Approx}_t = \text{BestDual}_t + \delta_t,</tex> где <tex>\text{BestDual}_t </tex> — лучшее на данный момент значение двойственной функции, <br>
 
-
<tex>\delta_{t+1} = \begin{cases}
 
-
\gamma_0 \delta_t, \;\; \text{Dual}_t > \text{Dual}_{t-1}, \\
 
-
\max(\gamma_1 \delta_t, \; \varepsilon ), \;\; \text{Dual}_t \leq \text{Dual}_{t-1}. \end{cases}</tex><br>
 
-
<tex>\gamma_0, \; \gamma_1, \; \varepsilon</tex> — параметры метода. Обычно <tex>\gamma_0 > 1, \; 1 > \gamma_1 > 0, \; \varepsilon \to 0+ </tex>. Конкретные значения этих параметров нужно подобрать.
 
-
 
-
3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам.
 
-
 
-
4. При тестировании алгоритма TRW необходимо следить, чтобы наибольшее значение нижней границы было не больше, чем наименьшее значение энергии.
 
-
 
-
5. Для генерации масок семян для сегментации изображений можно использовать любой редактор растровой графики (например, Paint). На изображении нужно определенным цветом закрасить пиксели, относящиеся к маске, и, впоследствии, выделить их в MATLAB.
 
-
 
-
=== Данные для выполнения задания ===
 
-
 
-
[[Media:SMAIS11_task2_Converter.zip|ZIP архив]] с MATLAB реализацией конвертера изображений.
 
-
 
-
=== Оформление задания ===
 
-
 
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 2. ФИО, номер группы, вариант 1». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
 
-
 
-
Письмо должно содержать:
 
-
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
 
-
*trwGridPotts.m
 
-
*segmentImage.m
 
-
*Набор вспомогательных файлов при необходимости
 
-
 
-
== Вариант 2 : α-расширение ==
 
-
 
-
=== Задание ===
 
-
* Вывести все формулы, использующиеся в вашей реализации α-расширения (сведение шага алгоритма к разрезу графа).
 
-
* Реализовать алгоритм α-расширение, используя выданный код разрезов графов.
 
-
* Протестировать алгоритм α-расширение на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
 
-
* Реализовать процедуру сегментации изображений с заданными пользователем семенами.
 
-
* Привести примеры удачных сегментаций (не менее 5). Требуется самостоятельно выбрать изображения (реалистичные), указать семена и отсегментировать при помощи реализованного метода. В отчет нужно вставлять и исходные изображения, и маски семян.
 
-
* На нескольких (не менее 3) задачах сегментации из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству сегментации. Все выводы должны быть подтверждены числами, графиками, картинками.
 
-
* Написать отчет в формате PDF с описанием всех проведенных исследований.
 
-
 
-
=== Спецификация реализуемых функций ===
 
{|class="standard"
{|class="standard"
-
!''Алгоритм α-расширение''
+
!''Предсказание''
-
|-
+
-
|[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC)
+
|-
|-
-
|[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, options)
+
|Y = predict_sSVM(X, model)
|-
|-
|ВХОД
|ВХОД
Строка 221: Строка 136:
|
|
{|border="0"
{|border="0"
-
|unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
+
|X — выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
|-
|-
-
|vertC — коэффициенты <tex> c_{pq}</tex>, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
+
|&nbsp;&nbsp; 'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
|-
|-
-
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
+
|&nbsp;&nbsp; 'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
|-
|-
-
|options — (необязательный аргумент) набор дополнительных параметров, массив типа '''cell''' вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
+
|&nbsp;&nbsp; 'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
|-
|-
-
|&nbsp;&nbsp;'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
+
|model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки);
-
|-
+
-
|&nbsp;&nbsp;'display' — параметр типа logical: если true, то при каждом запуске алгоритма разреза графа нужно выводить на экран номер итерации, номер расширяемой метки, текущее значение энергии;
+
|}
|}
|-
|-
Строка 238: Строка 151:
|
|
{|
{|
-
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
+
|Y — ответы на выборке X, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
-
|-
+
-
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
-
|-
+
-
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
+
|}
|}
-
|}
+
|}
-
Обратите внимание: в процедуре alphaExpansionGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
+
 
{|class="standard"
{|class="standard"
-
!''Сегментация изображений''
+
!''Обучение и предсказание для базы с машинами''
|-
|-
-
|[segmentation] = segmentImage(image, seeds)
+
|[train_error, test_Y] = cars()
-
|-
+
-
|ВХОД
+
-
|-
+
-
|
+
-
{|border="0"
+
-
|image — изображение, массив типа double размера N x M x 3 (все значения в этом массиве лежат в интервале от 0 до 1).
+
-
|-
+
-
|seeds — семена, заданные пользователем, массив типа logical размера N x M x K, элементы массива принимают значения true или false;
+
-
|}
+
|-
|-
|ВЫХОД
|ВЫХОД
Строка 265: Строка 165:
|
|
{|
{|
-
|segmentation — сегментация изображения, массив типа double размера N x M со значениями 1...K;
+
|train_error — ошибка на обучающей выборке;
 +
|-
 +
|test_Y — ответы на тестовой выборке, массив типа cell размера N x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения.
|}
|}
-
|}
+
|}
-
Обратите внимание: в процедуре segmentImage параметры N, M, и K определяются неявно по размеру соответствующих элементов.
+
 
 +
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.
=== Рекомендации по выполнению задания ===
=== Рекомендации по выполнению задания ===
-
# Обратите внимание на область применимости алгоритма α-расширение.
+
# Библиотека SVM-struct не позволяет установить ограничения на знак весов парных признаков <tex> \vec{w}^P </tex>. Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
-
# При тестировании алгоритма α-расширение необходимо следить за следующим:
+
# В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При правильной реализации алгоритма точность сегментации изображений, использовавшихся при обучении должна быть высокой (более 97% в терминах ошибки, усредненной по классам).
-
#* после каждого применения разреза графа общая энергия не возрастает;
+
# Для работы с библиотекой SVM-struct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
-
#* значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
+
# На этапе отладки параметр eps стоит выбрать достаточно большим (например, 10), чтобы уменьшить время работы алгоритма. На этапе экспериментов значение eps стоит уменьшить на несколько порядков.
-
# Для генерации масок семян для сегментации изображений можно использовать любой редактор растровой графики (например, Paint). На изображении нужно определенным цветом закрасить пиксели, относящиеся к маске, и, впоследствии, выделить их в MATLAB.
+
# При правильной реализации метода одна операция обучение sSVM на полной выборке должна работать не более получаса.
 +
# В качестве процедуры скользящего контроля рекомендуется выбрать схему [[Скользящий контроль| контроля по 2 блокам]] (2-fold CV).
 +
# Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. При этом в крайних значениях нужно получить ситуации недообучения и переобучения. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее.
=== Данные для выполнения задания ===
=== Данные для выполнения задания ===
-
[[Media:SMAIS11_task2_graphCuts.zip|ZIP архив]] с MATLAB интерфейсом к разрезам графов.
+
[[Media:GM_GraphCut.zip|graphCut]] — MATLAB интерфейс к разрезам графов.
-
[[Media:SMAIS11_task2_Converter.zip|ZIP архив]] с MATLAB реализацией конвертера изображений.
+
[https://docs.google.com/open?id=0B_PZC3alifN6WDExQlR6cktSaUU База данных].
 +
 
 +
[http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html MATLAB библиотека SVM-struct]
=== Оформление задания ===
=== Оформление задания ===
-
 
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 5. ФИО». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 2. ФИО, номер группы, вариант 2». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
+
Письмо должно содержать:
Письмо должно содержать:
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
-
*alphaExpansionGridPotts.m
+
*train_sSVM.m, predict_sSVM.m, cars.m
-
*segmentImage.m
+
*разметку тестовой выборки в таком же формате, как выдана разметка обучающей выборки
*Набор вспомогательных файлов при необходимости
*Набор вспомогательных файлов при необходимости
-
 
-
[[Категория:Учебные курсы]]
 
-
[[Категория:Байесовские методы]]
 

Текущая версия

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

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


Содержание

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

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

1-й этап сдачи задания: 2 мая 2012, 23:59

2-й этап сдачи задания: 9 мая 2012, 23:59

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

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

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

Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: E(X, Y, W) . Здесь X — признаки, Y — «суперпиксельная» сегментация, W — параметры модели. Функция Е выглядит следующим образом:
E(X, Y, W) = \sum_{p \in V} ( \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]

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

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

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

  1. слагаемые, образующие парные потенциалы, записывались так: \sum_{(p, q) \in E} \sum_{k, \ell \in \{0, 1\}} (\vec{x}_{pq}^T \vec{w}^P_{k\ell}) [y_p = k][y_q = \ell]; в рамках данного задания для упрощения работы парные потенциалы ограничиваются только обобщенными потенциалами Поттса, что соответствует следующим ограничениям на веса: \vec{w}^P_{00} = \vec{w}^P_{11} = 0; \; \vec{w}^P_{10} = \vec{w}^P_{01};
  2. слагаемые, образующие унарные потенциалы, записывались так: \sum_{k\in\{0, 1\}}\sum_{p \in V} ( \vec{x}_p^T \vec{w}^U_k) [y_p = k]; в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».

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

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

Параметры модели 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; все суммы берутся по всем пикселям изображения.

Задание

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

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

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

  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 размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
    • 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 #(суперпиксели).

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

Обучение
[model, time] = train_sSVM(X, Y, options)
ВХОД
X — обучающая выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
   'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
   'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
   'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
Y — ответы на обучающей выборки, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;
options — набор параметров метода, структура с полями:
   'С' — параметр C структурного метода опорных векторов;
   'eps' — порог для добавления ограничений в рамках метода отсекающих плоскостей;
ВЫХОД
model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки).
time — время работы алгоритма;


Предсказание
Y = predict_sSVM(X, model)
ВХОД
X — выборка, массив типа cell размера #(объекты в выборке) x 1; каждый элемент массива представляет собой структуру со следующими полями:
   'superpixelMap' — массив типа double размера, равного размеру изображения; каждому пикселю соответствует номер суперпикселя, в который он попадает;
   'unaryFeatures' — массив типа single размером #(унарные признаки) x #(суперпиксели);
   'pairwiseFeatures' — массив типа double размером #(пары соседних супепикселей) x (#(парные признаки) + 2); первые два столбца содержат номера соседних суперпикселей; столбцы, начиная с 3-го содержат парные признаки;
model — модель, обученная при помощи вашего метода; вектор типа double длины #(унарные признаки) + #(парные признаки);
ВЫХОД
Y — ответы на выборке X, массив типа cell размера #(объекты в выборке) x 1; каждый элемент содержит массив типа logical размера, равному размеру изображения;


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

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

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

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

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

graphCut — MATLAB интерфейс к разрезам графов.

База данных.

MATLAB библиотека SVM-struct

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

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

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

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • train_sSVM.m, predict_sSVM.m, cars.m
  • разметку тестовой выборки в таком же формате, как выдана разметка обучающей выборки
  • Набор вспомогательных файлов при необходимости
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Anton/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»