|
|
| Строка 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 и т.д. Возможны следующие параметры:
| |
| - | |-
| |
| - | | 'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
| |
| - | |-
| |
| - | | '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 и т.д. Возможны следующие параметры:
| |
| - | |-
| |
| - | | '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-файл. |
| | *Набор вспомогательных файлов при необходимости | | *Набор вспомогательных файлов при необходимости |
| | | | |
| | [[Категория:Учебные курсы]] | | [[Категория:Учебные курсы]] |
| | [[Категория:Байесовские методы]] | | [[Категория:Байесовские методы]] |
Рассматривается классическая скрытая марковская модель (СММ) первого порядка, в которой полное правдоподобие задается как:
