Графические модели (курс лекций)/2013/Задание 5
Материал из MachineLearning.
(перенос задания с прошлого года) |
м (перенормирована функция потерь) |
||
(5 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | |||
- | |||
- | |||
- | |||
- | |||
{{TOCright|300px}} | {{TOCright|300px}} | ||
Строка 10: | Строка 5: | ||
[[Изображение:GM12 task4 intro.png | 600px]] | [[Изображение:GM12 task4 intro.png | 600px]] | ||
- | '''Начало выполнения задания''': | + | '''Начало выполнения задания''': 22 апреля 2013 |
- | '''1-й этап сдачи задания''': {{ins| | + | '''1-й этап сдачи задания''': {{ins|5 мая 2013, 23:59}} |
- | '''2-й этап сдачи задания''': {{ins| | + | '''2-й этап сдачи задания''': {{ins|12 мая 2013, 23:59}} |
- | Среда реализации | + | Среда реализации — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке. |
=== Сегментация изображений === | === Сегментация изображений === | ||
Строка 25: | Строка 20: | ||
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: <tex> 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 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> | + | <tex> E(X, Y, W) = \sum_{p \in V} ( \vec{x}_p^T \vec{w}^U) y_p + \sum_{(p, q) \in \mathcal{E}} (\vec{x}_{pq}^T \vec{w}^P) [y_p \neq y_q] </tex> |
- | Здесь V — множество суперпикселей изображения, | + | Здесь V — множество суперпикселей изображения, <tex>\mathcal{E}</tex> — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные <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> — веса унарных и парных признаков. |
Заметим, что если для всех пар соседних суперпикселей величины <tex> \vec{x}_{pq}^T \vec{w}^P </tex> неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа. | Заметим, что если для всех пар соседних суперпикселей величины <tex> \vec{x}_{pq}^T \vec{w}^P </tex> неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа. | ||
Приведенный выше способ записи энергии E отличается от способа записи, разобранного на лекции, в двух местах: | Приведенный выше способ записи энергии 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_{(p, q) \in \mathcal{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> в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект». | # слагаемые, образующие унарные потенциалы, записывались так: <tex>\sum_{k\in\{0, 1\}}\sum_{p \in V} ( \vec{x}_p^T \vec{w}^U_k) [y_p = k];</tex> в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект». | ||
Строка 43: | Строка 38: | ||
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), расстояние Хэмминга между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания ошибка сегментации определяется количеством неправильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении: | Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), расстояние Хэмминга между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания ошибка сегментации определяется количеством неправильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении: | ||
- | <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>. | + | <tex> error(T, \hat{T}) = 0.5 \frac{\sum_i [t_i \neq 1][\hat{t}_i = 1]}{\sum_i [\hat{t}_i = 1]} + 0.5 \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; все суммы берутся по всем пикселям изображения. | Здесь T — текущая разметка изображения, <tex>\hat{T} </tex> — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения. | ||
Строка 57: | Строка 52: | ||
В рамках 2-го этапа задания необходимо: | В рамках 2-го этапа задания необходимо: | ||
# придумать не менее 5 различных парных признаков; | # придумать не менее 5 различных парных признаков; | ||
- | # при помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке; | + | # при помощи [[Скользящий контроль| скользящего контроля]] подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке, в крайних значениях нужно получить ситуации недообучения и переобучения; |
# при помощи обученного сегментатора получить разметки тестовой выборки изображений; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы; | # при помощи обученного сегментатора получить разметки тестовой выборки изображений; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы; | ||
# написать отчет в формате PDF с описанием всех проведенных исследований. | # написать отчет в формате PDF с описанием всех проведенных исследований. | ||
Строка 87: | Строка 82: | ||
** neighborhood — массив типа double размером #(пары соседних суперпикселей) x 2; каждая строка содержит номера соседних суперпикселей; | ** neighborhood — массив типа double размером #(пары соседних суперпикселей) x 2; каждая строка содержит номера соседних суперпикселей; | ||
** unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели). | ** unaryFeatures — массив типа single размером #(унарные признаки) x #(суперпиксели). | ||
+ | |||
+ | ВНИМАНИЕ! Разметку тестовой выборки необходимо присылать в следующем формате: файлы imgTest_XXX_labeling.png в одной директории. Каждый файл должен содержать черно-белое изображение, аналогичное imgTrain_XXX_groundtruth.png | ||
=== Спецификация реализуемых функций === | === Спецификация реализуемых функций === | ||
Строка 180: | Строка 177: | ||
# При правильной реализации метода одна операция обучения sSVM на полной выборке должна работать не более получаса. | # При правильной реализации метода одна операция обучения sSVM на полной выборке должна работать не более получаса. | ||
# В качестве процедуры скользящего контроля рекомендуется выбрать схему [[Скользящий контроль| контроля по 2 блокам]] (2-fold CV). | # В качестве процедуры скользящего контроля рекомендуется выбрать схему [[Скользящий контроль| контроля по 2 блокам]] (2-fold CV). | ||
- | # Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке | + | # Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее. |
+ | # Иногда библиотека вылетает с ошибкой и закрывает Матлаб. Это может происходить из-за выполнения инструкции exit(0). Рекомендуется заменить эти инструкции либо на исключения, либо на вызов функций аналогичных mexErrMsgTxt. | ||
+ | # Библиотека SVM-struct предполагает, что функция LOSSFN возвращает 0, когда вместо обоих аргументов стоит правильная разметка. | ||
=== Данные для выполнения задания === | === Данные для выполнения задания === | ||
Строка 191: | Строка 190: | ||
=== Оформление задания === | === Оформление задания === | ||
- | Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой | + | Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «[ГМ13] задание 5, фамилия». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации. |
Письмо должно содержать: | Письмо должно содержать: | ||
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел) | *PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел) | ||
*train_sSVM.m, predict_sSVM.m, cars.m | *train_sSVM.m, predict_sSVM.m, cars.m | ||
- | *разметку тестовой | + | *разметку тестовой выборки |
*Набор вспомогательных файлов при необходимости | *Набор вспомогательных файлов при необходимости |
Текущая версия
|
Начало выполнения задания: 22 апреля 2013
1-й этап сдачи задания: 5 мая 2013, 23:59
2-й этап сдачи задания: 12 мая 2013, 23:59
Среда реализации — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Сегментация изображений
В рамках данного задания рассматривается задача сегментации изображений на два класса: машина и фон. В дальнейшем работа осуществляется в терминах небольших сегментов изображения — суперпикселей. Заметим, что по «суперпиксельной» сегментации изображения можно однозначно построить «попиксельную» сегментацию.
Ответом (сегментацией изображения) является аргминимум бинарной субмодулярной функции совместимости (максимизация супермодулярной функции), состоящей из унарных и парных потенциалов: . Здесь X — признаки, Y — «суперпиксельная» сегментация,
W — параметры модели. Функция Е выглядит следующим образом:
Здесь V — множество суперпикселей изображения, — система соседства суперпикселей, вообще говоря, не являющаяся регулярной решеткой; переменные
— метки классов, 0 — фон, 1 — объект;
— векторы унарных признаков для суперпикселей;
— векторы парных признаков для пар соседних суперпикселей;
— веса унарных и парных признаков.
Заметим, что если для всех пар соседних суперпикселей величины неотрицательны, то энергию E можно эффективно минимизировать при помощи алгоритма построения минимального разреза графа.
Приведенный выше способ записи энергии E отличается от способа записи, разобранного на лекции, в двух местах:
- слагаемые, образующие парные потенциалы, записывались так:
в рамках данного задания для упрощения работы парные потенциалы ограничиваются только обобщенными потенциалами Поттса, что соответствует следующим ограничениям на веса:
;
- слагаемые, образующие унарные потенциалы, записывались так:
в рамках данного задания для ускорения работы алгоритма вместо весов за все классы используются только веса, относящиеся классу «объект».
Ограничения, накладываемые на веса, соответствующие парным признакам, уменьшают гибкость модели. Упрощение, связанное с унарными потенциалами, не влияет на гибкость модели (верно только для случая двух классов).
В качестве унарных признаков обычно выбирают гистограммы по мешкам слов, построенных по каким-либо локальным дескрипторам изображений. В качестве парных признаков выбирают различные обобщенные модели Поттса; парный признак, равный одной и той же величине по всем парам соседних суперпикселей, соответствует обычной модели Поттса.
Параметры модели W можно настраивать при помощи структурного метода опорных векторов (sSVM), решая оптимизационную задачу при помощи метода отсекающих плоскостей.
Поскольку классы не сбалансированы (на изображениях пикселей фона намного больше, чем пикселей объекта), расстояние Хэмминга между произвольной и правильной сегментациями не является адекватной мерой качества сегментации. В рамках данного задания ошибка сегментации определяется количеством неправильно распознанных пикселей каждого класса, взвешенным на общее количество пикселей этого класса на изображении:
.
Здесь T — текущая разметка изображения, — правильная разметка; метка фона — 0, метка объекта — 1; все суммы берутся по всем пикселям изображения.
Задание
В рамках 1-го этапа задания необходимо:
- выписать формулу для ошибки, усредненной по классам, в терминах суперпикселей Y;
- показать, как решать задачу
при помощи алгоритма построения разреза графа;
- реализовать процедуру обучения при помощи структурного метода опорных векторов (библиотеки SVM-struct) и процедуру тестирования для задачи сегментации изображений;
- протестировать реализованные процедуры на модельных данных, используя хотя бы 1 парный признак;
- написать отчет в формате PDF с описанием всех проведенных исследований.
В рамках 2-го этапа задания необходимо:
- придумать не менее 5 различных парных признаков;
- при помощи скользящего контроля подобрать структурный параметр метода С и получить оценку точности алгоритма на обучающей выборке, в крайних значениях нужно получить ситуации недообучения и переобучения;
- при помощи обученного сегментатора получить разметки тестовой выборки изображений; привести примеры удачных и неудачных сегментаций; студенты, получившие наилучшие результаты с точки зрения взвешенного среднего, получат дополнительные баллы;
- написать отчет в формате PDF с описанием всех проведенных исследований.
Для выполнения задания выдается:
- реализация алгоритма построения разреза графов, совместимая с MATLAB;
- реализации структурного метода опорных векторов в библиотеке SVM-struct с интерфейсом под MATLAB: http://www.vlfeat.org/~vedaldi/code/svm-struct-matlab.html
- исходные изображения: обучающая и тестовая выборки;
- правильная сегментация изображений обучающей выборки;
- суперпиксели изображений обучающей и тестовой выборок, найденные при помощи библиотеки BSR;
- признаки для каждого суперпикселя; вектором признаков является гистограмма по мешку из 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 #(суперпиксели).
ВНИМАНИЕ! Разметку тестовой выборки необходимо присылать в следующем формате: файлы imgTest_XXX_labeling.png в одной директории. Каждый файл должен содержать черно-белое изображение, аналогичное imgTrain_XXX_groundtruth.png
Спецификация реализуемых функций
Обучение | ||||||||
---|---|---|---|---|---|---|---|---|
[model, time] = train_sSVM(X, T, options) | ||||||||
ВХОД | ||||||||
| ||||||||
ВЫХОД | ||||||||
|
Предсказание | |||||
---|---|---|---|---|---|
T = predict_sSVM(X, model) | |||||
ВХОД | |||||
| |||||
ВЫХОД | |||||
|
Обучение и предсказание для базы с машинами | ||
---|---|---|
[train_error, test_T] = cars() | ||
ВЫХОД | ||
|
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог с данными.
Рекомендации по выполнению задания
- Библиотека SVM-struct не позволяет установить ограничения на знак весов парных признаков
. Для минимизации получающихся несубмодулярных функций рекомендуется отбрасывать несубмодулярные ребра.
- В качестве модельных данных рекомендуется использовать выборку, состоящую из 2-3 изображений обучающей выборки. При правильной реализации алгоритма точность сегментации изображений, использовавшихся при обучении, должна быть высокой (более 97% в терминах ошибки, усредненной по классам).
- Для работы с библиотекой SVM-struct необходимо реализовать функцию поиска наиболее нарушаемого ограничения (CONSTRAINTFN), функцию построения вектора обобщенных признаков (FEATUREN), функцию потерь (LOSSFN). Библиотеку SVMstruct рекомендуется запускать со следующими параметрами: -p 1 -o 2 -w 4 -v 3 -y 0 -c <ваш C> -e <ваш eps>.
- На этапе отладки параметр eps стоит выбрать достаточно большим (например, 10), чтобы уменьшить время работы алгоритма. На этапе экспериментов значение eps стоит уменьшить на несколько порядков.
- При правильной реализации метода одна операция обучения sSVM на полной выборке должна работать не более получаса.
- В качестве процедуры скользящего контроля рекомендуется выбрать схему контроля по 2 блокам (2-fold CV).
- Параметр С рекомендуется перебирать по равномерной в логарифмической шкале сетке. Начинать перебор лучше с заведомо заниженных значений параметра С, поскольку в этом случае метод работает быстрее.
- Иногда библиотека вылетает с ошибкой и закрывает Матлаб. Это может происходить из-за выполнения инструкции exit(0). Рекомендуется заменить эти инструкции либо на исключения, либо на вызов функций аналогичных mexErrMsgTxt.
- Библиотека SVM-struct предполагает, что функция LOSSFN возвращает 0, когда вместо обоих аргументов стоит правильная разметка.
Данные для выполнения задания
graphCut — MATLAB интерфейс к разрезам графов.
Оформление задания
Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «[ГМ13] задание 5, фамилия». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
- PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
- train_sSVM.m, predict_sSVM.m, cars.m
- разметку тестовой выборки
- Набор вспомогательных файлов при необходимости