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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
-
{{UnderConstruction|Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. [[Участник:Anton|Anton]] 18:11, 7 апреля 2011 (MSD)}}
+
[[ГМ|Перейти к основной странице курса]]
-
{{TOCright|300px}}
+
'''Начало выполнения задания''': 29 февраля 2012
-
[[Структурные методы анализа изображений и сигналов (курс лекций)|Перейти к основной странице курса]]
+
'''Срок сдачи''': {{ins|7 марта 2012, 18:00}}
-
Задание состоит из двух вариантов.
 
-
Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
+
=== Формулировка задания ===
-
== Марковское случайное поле ==
+
[[Изображение:sinc_rvr.jpg|150px|thumb|Пример решения задачи регрессии: восстановление зашумленной функции sinc]]
-
Марковское случайное поле (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,
+
<center>
-
*система соседства E - прямоугольная решетка,
+
<tex>
-
*бинарные потенциалы V являются обобщенными потенциалами Поттса: <tex>V_{pq} = c_{pq} [x_p \neq x_q] </tex>.
+
p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )
 +
</tex>
 +
</center>
-
В рамках этого задания требуется:
 
-
#реализовать алгоритм поиска конфигурации MRF, обладающей минимальной энергией (TRW или α-expansion),
 
-
#протестировать реализованный алгоритм на модельных задачах,
 
-
#применить реализованный алгоритм для задачи интерактивной сегментации изображений,
 
-
#сравнить алгоритмы TRW и α-expansion на задаче сегментации изображений.
 
-
 
-
=== MRF для интерактивной сегментации изображений ===
 
-
Задача сегментации изображения состоит в отнесении каждого пикселя изображения к одному из K классов. В интерактивном варианте пользователь отмечает часть пикселей, принадлежащих каждому классу. После этого требуется автоматически разметить оставшуюся часть изображения.
 
-
 
-
Для задачи сегментации марковское случайное поле строится, например, так:
 
-
*Каждая переменная <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-алгоритма восстановления смеси нормальных распределений в пространстве Luv.
 
-
*В качестве парных потенциалов выбираются обобщенные потенциалы Поттса с коэффициентами α, делающими разрез более энергетически-выгодным, там где цвет изображения сильно меняется: <tex> c_{pq} = A + B\:\exp\left(-\frac{|| I_p - I_q ||^2}{2\sigma^2}\right) </tex>, A ≥ 0, B ≥ 0, σ — параметры.
 
-
 
-
== Вариант 1 : TRW==
 
-
=== Задание ===
 
-
* Вывести все формулы, использующиеся в вашей реализации TRW.
 
-
* Реализовать алгоритм TRW.
 
-
* Протестировать алгоритм TRW на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
 
-
* Привести примеры наличия duality gap (разрыв двойственности, двойственный зазор?) и отсутствия его.
 
-
* Реализовать процедуру сегментации изображений с заданными пользователем семенами.
 
-
* Привести примеры удачных сегментаций (не менее 5).
 
-
* На нескольких (не менее 3-х) задачах сегментации сравнить работу алгоритмов TRW и α-expansion. Недостающую реализацию можно взять у товарища, выполняющего другой вариант.
 
-
* Написать отчет в формате PDF с описанием всех проведенных исследований.
 
-
 
-
=== Спецификация реализуемых функций ===
 
-
{|class="standard"
 
-
!''Алгоритм TRW''
 
-
|-
 
-
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC)
 
-
|-
 
-
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, options)
 
-
|-
 
-
|ВХОД
 
-
|-
 
-
|
 
-
{|border="0"
 
-
|unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
 
-
|-
 
-
|vertC — коэффициенты <tex> c_{pq}</tex>, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
 
-
|-
 
-
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
 
-
|-
 
-
|options — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
 
-
|-
 
-
|&nbsp;&nbsp;'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
 
-
|-
 
-
|&nbsp;&nbsp;'argEps' — порог сходимости по аргументу;
 
-
|}
 
-
|-
 
-
|ВЫХОД
 
-
|-
 
-
|
 
-
{|
 
-
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
 
-
|-
 
-
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 
-
|-
 
-
|lowerBound — значения нижней границы на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 
-
|-
 
-
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 
-
|}
 
-
|}
 
-
Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 
-
 
-
{|class="standard"
 
-
!''Сегментация изображений''
 
-
|-
 
-
|[segmentation] = segmentImage(image, seeds)
 
-
|-
 
-
|ВХОД
 
-
|-
 
-
|
 
-
{|border="0"
 
-
|image — изображение, массив типа double размера N x M x 3.
 
-
|-
 
-
|seeds — семена, заданные пользователем, массив типа double размера N x M x K, элементы массивы принимают значения 0 или 1;
 
-
|}
 
-
|-
 
-
|ВЫХОД
 
-
|-
 
-
|
 
-
{|
 
-
|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>\lambda_{new} = \lambda_{old} + \alpha_t g_t, </tex>
 
-
где <tex>g_t</tex> — субградиент в текущей точке, <tex>\alpha_t</tex> — параметр, отвечающий за длину сдвига.
 
-
В рамках данного практического задания рекомендуется использовать адаптивный метод выбора длины шага:<br>
 
-
<tex>\alpha_t = \frac{\text{Approx}_t - \text{Dual}_t}{|| \nabla 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 необходимо следить чтобы наибольшее значение нижней границы было не больше чем наименьшее значение энергии.
 
-
 
-
=== Оформление задания ===
 
-
 
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 2. ФИО, номер группы, вариант 1». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
 
-
 
-
Письмо должно содержать:
 
-
*PDF-файл с описанием проведенных исследований
 
-
*trwGridPotts.m
 
-
*segmentImage.m
 
-
*Набор вспомогательных файлов при необходимости
 
-
 
-
== Вариант 2 : α-expansion ==
 
-
 
-
=== Задание ===
 
-
* Вывести все формулы, использующиеся в вашей реализации α-expansion.
 
-
* Реализовать алгоритм α-expansion, используя выданный код разрезов графов.
 
-
* Протестировать алгоритм α на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
 
-
* Реализовать процедуру сегментации изображений с заданными пользователем семенами.
 
-
* Привести примеры удачных сегментаций (не менее 5).
 
-
* На нескольких (не менее 3-х) задачах сегментации сравнить работу алгоритмов TRW и α-expansion. Недостающую реализацию можно взять у товарища, выполняющего другой вариант.
 
-
* Написать отчет в формате PDF с описанием всех проведенных исследований.
 
-
 
-
=== Спецификация реализуемых функций ===
 
-
{|class="standard"
 
-
!''Алгоритм α-expansion''
 
-
|-
 
-
|[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC)
 
-
|-
 
-
|[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, options)
 
-
|-
 
-
|ВХОД
 
-
|-
 
-
|
 
-
{|border="0"
 
-
|unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
 
-
|-
 
-
|vertC — коэффициенты <tex> c_{pq}</tex>, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
 
-
|-
 
-
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
 
-
|-
 
-
|options — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
 
-
|-
 
-
|&nbsp;&nbsp;'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
 
-
|}
 
-
|-
 
-
|ВЫХОД
 
-
|-
 
-
|
 
-
{|
 
-
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
 
-
|-
 
-
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 
-
|-
 
-
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 
-
|}
 
-
|}
 
-
Обратите внимание: в процедуре alphaExpansionGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 
-
 
-
{|class="standard"
 
-
!''Сегментация изображений''
 
-
|-
 
-
|[segmentation] = segmentImage(image, seeds)
 
-
|-
 
-
|ВХОД
 
-
|-
 
-
|
 
-
{|border="0"
 
-
|image — изображение, массив типа double размера N x M x 3.
 
-
|-
 
-
|seeds — семена, заданные пользователем, массив типа double размера N x M x K, элементы массивы принимают значения 0 или 1;
 
-
|}
 
-
|-
 
-
|ВЫХОД
 
-
|-
 
-
|
 
-
{|
 
-
|segmentation — сегментация изображения, массив типа double размера N x M со значениями 1...K;
 
-
|}
 
-
|}
 
-
Обратите внимание: в процедуре segmentImage параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 
-
 
-
=== Рекомендации по выполнению задания ===
 
-
# Обратите внимание на область применимости алгоритма α-expansion.
 
-
# При тестировании алгоритма α-expansion необходимо следить чтобы:
 
-
#* после каждого применения разреза графа общая энергия не возрастает;
 
-
#* значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
 
-
 
-
=== Данные для выполнения задания ===
 
-
 
-
[[Media:SMAIS11_task2_graphCuts.zip|ZIP архив]] с MATLAB интерфейсом к разрезам графов.
 
=== Оформление задания ===
=== Оформление задания ===
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 2. ФИО, номер группы, вариант 2». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 1. ФИО, номер группы». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
Письмо должно содержать:
*PDF-файл с описанием проведенных исследований
*PDF-файл с описанием проведенных исследований
-
*alphaExpansionGridPotts.m
+
*LDS_GENERATE.m
-
*segmentImage.m
+
*LDS_forwardbackward.m
 +
*LDS_EM_TRAIN.m
 +
*TRAJECTORY_GENERATE.m
 +
*Ссылка на видео-файл, размещенный на файлообменнике или на видео-хостинге, с наложенными исходной и фильтрованной траекториями движения центра масс мыши. Лучше вставить видео-файл непосредственно внутрь PDF-файла с отчетом (это можно сделать, например, в программе Adobe Acrobat 9 и выше). Тогда нужно прислать ссылку на этот PDF-файл.
*Набор вспомогательных файлов при необходимости
*Набор вспомогательных файлов при необходимости
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]
[[Категория:Байесовские методы]]
[[Категория:Байесовские методы]]

Версия 13:24, 28 февраля 2012

Перейти к основной странице курса

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

Срок сдачи: 7 марта 2012, 18:00


Формулировка задания

Пример решения задачи регрессии: восстановление зашумленной функции sinc
Пример решения задачи регрессии: восстановление зашумленной функции sinc

Рассматривается классическая скрытая марковская модель (СММ) первого порядка, в которой полное правдоподобие задается как:


p(X,T|\theta)=p(t_1)\prod_{n=2}^Np(t_n |t_{n-1})\prod_{n=1}^Np(x_n |t_n )


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

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

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

  • PDF-файл с описанием проведенных исследований
  • LDS_GENERATE.m
  • LDS_forwardbackward.m
  • LDS_EM_TRAIN.m
  • TRAJECTORY_GENERATE.m
  • Ссылка на видео-файл, размещенный на файлообменнике или на видео-хостинге, с наложенными исходной и фильтрованной траекториями движения центра масс мыши. Лучше вставить видео-файл непосредственно внутрь PDF-файла с отчетом (это можно сделать, например, в программе Adobe Acrobat 9 и выше). Тогда нужно прислать ссылку на этот PDF-файл.
  • Набор вспомогательных файлов при необходимости
Личные инструменты