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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
-
{|class = "standard sortable"
+
{{TOCright|300px}}
-
! class="unsortable"|№ п/п !! Студент !! Научный руководитель
+
[[Изображение:SMAIS11_task2_illustration2.jpg]]
 +
 
 +
[[Структурные методы анализа изображений и сигналов (курс лекций)|Перейти к основной странице курса]]
 +
 
 +
'''Начало выполнения задания''': 15 апреля 2011
 +
 
 +
'''Срок сдачи''': {{ins|1 мая 2011, 23:59}}
 +
 
 +
Задание состоит из двух вариантов. Распределение студентов по вариантам сохраняется с первого задания. Тем, кто реализовывал СММ, достается TRW, остальным — <tex>\alpha</tex>-расширение.
 +
 
 +
Среда реализации для всех вариантов — 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>X</tex>, обладающей минимальной энергией (TRW или α-расширение),
 +
#протестировать реализованный алгоритм на модельных задачах,
 +
#применить реализованный алгоритм для задачи интерактивной сегментации изображений,
 +
#сравнить алгоритмы TRW и α-расширение на задаче сегментации изображений.
 +
 
 +
=== MRF для интерактивной сегментации изображений ===
 +
[[Изображение:SMAIS11_task2_illustration.jpg‎|300px|thumb|Пример изображения с пользовательской маской семян]]
 +
Задача сегментации изображения состоит в отнесении каждого пикселя изображения к одному из 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-алгоритма восстановления смеси нормальных распределений в пространстве [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==
 +
 
 +
=== Задание ===
 +
* Вывести все формулы, использующиеся в вашей реализации TRW (формулировки прямой и двойственной задач, формула подсчета субградиента, конкретная схема субградиентного подъема, и т.д.).
 +
* Реализовать алгоритм TRW.
 +
* Протестировать алгоритм TRW на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
 +
* Привести примеры наличия и отсутствия зазора между решениями прямой и двойственной задач (например, зазор должен отсутствовать в случае субмодулярной энергии).
 +
* Реализовать процедуру сегментации изображений с заданными пользователем семенами.
 +
* Привести примеры удачных сегментаций (не менее 5). Требуется самостоятельно выбрать изображения (реалистичные), указать семена и отсегментировать при помощи реализованного метода. В отчет нужно вставлять и исходные изображения, и маски семян.
 +
* На нескольких (не менее 3) задачах сегментации из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству сегментации. Все выводы должны быть подтверждены числами, графиками, картинками.
 +
* Написать отчет в формате PDF с описанием всех проведенных исследований.
 +
 
 +
=== Спецификация реализуемых функций ===
 +
{|class="standard"
 +
!''Алгоритм TRW''
|-
|-
-
| align="center"|1 || Александров Ярослав Алексеевич || align="center"|[[Участник:Sgur|С.И. Гуров]]
+
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC)
|-
|-
-
| align="center"|2 || Артюхин Станислав Геннадьевич || align="center"|[[Участник:Mest|Л.М. Местецкий]]
+
|[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, options)
|-
|-
-
| align="center"|3 || Бобрик Ксения Петровна || align="center"|[[Участник:Dj|А.Г. Дьяконов]]
+
|ВХОД
|-
|-
-
| align="center"|4 || Гаврилюк Кирилл Артурович || align="center"|[[Участник:Vokov|К.В. Воронцов]]
+
|
 +
{|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' — порог сходимости по аргументу;
 +
|-
 +
|&nbsp;&nbsp;'display' — параметр типа logical: если true, то на каждой итерации нужно выводить на экран номер итерации, текущее значение энергии и нижней границы;
 +
|}
|-
|-
-
| align="center"|5 || Елшин Денис Александрович || align="center"|[[Участник:Dmitry Vetrov|Д.П. Ветров]]
+
|ВЫХОД
|-
|-
-
| align="center"|6 || Ермушева Александра Александровна || align="center"|[[Участник:Dj|А.Г. Дьяконов]]
+
|
 +
{|
 +
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
 +
|-
 +
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 +
|-
 +
|lowerBound — значения нижней границы на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 +
|-
 +
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма.
 +
|}
 +
|}
 +
Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 +
 
 +
{|class="standard"
 +
!''Сегментация изображений''
|-
|-
-
| align="center"|7 || Зимовнов Андрей Владимирович || align="center"|[[Участник:Mest|Л.М. Местецкий]]
+
|[segmentation] = segmentImage(image, seeds)
|-
|-
-
| align="center"|8 || Игнатьев Олег Анатольевич || align="center"|[[Журавлев, Юрий Иванович|Ю.И. Журавлев]]
+
|ВХОД
|-
|-
-
| align="center"|9 || Кириллов Александр Николаевич || align="center"|[[Участник:Dj|А.Г. Дьяконов]]
+
|
 +
{|border="0"
 +
|image — изображение, массив типа double размера N x M x 3 (все значения в этом массиве в интервале от 0 до 1).
 +
|-
 +
|seeds — семена, заданные пользователем, массив типа logical размера N x M x K, элементы массива принимают значения true или false;
 +
|}
|-
|-
-
| align="center"|10 || Марченко Евгений Андреевич || align="center"|[[Участник:Sgur|С.И. Гуров]]
+
|ВЫХОД
|-
|-
-
| align="center"|11 || Матвеева Дарья Сергеевна || align="center"|[[Участник:Mest|Л.М. Местецкий]]
+
|
 +
{|
 +
|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"
 +
!''Алгоритм α-расширение''
|-
|-
-
| align="center"|12 || Меркулова Татьяна Дмитриевна || align="center"|[[Участник:Yury Chekhovich|Ю.В. Чехович]]
+
|[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC)
|-
|-
-
| align="center"|13 || [[Участник:knek|Некрасов Константин Викторович]] || align="center"|[[Участник:Dmitry Vetrov|Д.П. Ветров]]
+
|[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, options)
|-
|-
-
| align="center"|14 || Новиков Павел Александрович || align="center"|[[Участник:Dmitry Vetrov|Д.П. Ветров]]
+
|ВХОД
|-
|-
-
| align="center"|15 || Панов Алексей Витальевич || align="center"|[[Журавлев, Юрий Иванович|Ю.И. Журавлев]]
+
|
 +
{|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;'display' — параметр типа logical: если true, то при каждом запуске алгоритма разреза графа нужно выводить на экран номер итерации, номер расширяемой метки, текущее значение энергии;
 +
|}
|-
|-
-
| align="center"|16 || Плященко Егор Эдуардович || align="center"|[[Участник:Yury Chekhovich|Ю.В. Чехович]]
+
|ВЫХОД
|-
|-
-
| align="center"|17 || Полежаев Валентин Александрович || align="center"|[[Участник:Vokov|К.В. Воронцов]]
+
|
 +
{|
 +
|labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
 +
|-
 +
|energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 +
|-
 +
|time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
 +
|}
 +
|}
 +
Обратите внимание: в процедуре alphaExpansionGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 +
 
 +
{|class="standard"
 +
!''Сегментация изображений''
|-
|-
-
| align="center"|18 || Сабурова Мария Ивановна (С) || align="center"|[[Участник:AIM|А.И. Майсурадзе]]
+
|[segmentation] = segmentImage(image, seeds)
|-
|-
-
| align="center"|19 || [[Участник:EvgSokolov|Соколов Евгений Андреевич]] || align="center"|[[Участник:Vokov|К.В. Воронцов]]
+
|ВХОД
|-
|-
-
| align="center"|20 || Фигурнов Михаил Викторович || align="center"|[[Участник:Dj|А.Г. Дьяконов]]
+
|
 +
{|border="0"
 +
|image — изображение, массив типа double размера N x M x 3 (все значения в этом массиве лежат в интервале от 0 до 1).
 +
|-
 +
|seeds — семена, заданные пользователем, массив типа logical размера N x M x K, элементы массива принимают значения true или false;
 +
|}
|-
|-
-
| align="center"|21 || Цупков Сергей Олегович || align="center"|[[Участник:Yury Chekhovich|Ю.В. Чехович]]
+
|ВЫХОД
|-
|-
-
| align="center"|22 || Шанин Иван Андреевич || align="center"|[[Участник:Vokov|К.В. Воронцов]]
+
|
 +
{|
 +
|segmentation — сегментация изображения, массив типа double размера N x M со значениями 1...K;
 +
|}
|}
|}
 +
Обратите внимание: в процедуре segmentImage параметры N, M, и K определяются неявно по размеру соответствующих элементов.
 +
 +
=== Рекомендации по выполнению задания ===
 +
# Обратите внимание на область применимости алгоритма α-расширение.
 +
# При тестировании алгоритма α-расширение необходимо следить за следующим:
 +
#* после каждого применения разреза графа общая энергия не возрастает;
 +
#* значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
 +
# Для генерации масок семян для сегментации изображений можно использовать любой редактор растровой графики (например, Paint). На изображении нужно определенным цветом закрасить пиксели, относящиеся к маске, и, впоследствии, выделить их в MATLAB.
 +
 +
=== Данные для выполнения задания ===
 +
 +
[[Media:SMAIS11_task2_graphCuts.zip|ZIP архив]] с MATLAB интерфейсом к разрезам графов.
 +
 +
[[Media:SMAIS11_task2_Converter.zip|ZIP архив]] с MATLAB реализацией конвертера изображений.
 +
 +
=== Оформление задания ===
 +
 +
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 2. ФИО, номер группы, вариант 2». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
 +
 +
Письмо должно содержать:
 +
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
 +
*alphaExpansionGridPotts.m
 +
*segmentImage.m
 +
*Набор вспомогательных файлов при необходимости
 +
 +
[[Категория:Учебные курсы]]
 +
[[Категория:Байесовские методы]]

Версия 13:41, 26 марта 2012

Содержание

Изображение:SMAIS11_task2_illustration2.jpg

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

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

Срок сдачи: 1 мая 2011, 23:59

Задание состоит из двух вариантов. Распределение студентов по вариантам сохраняется с первого задания. Тем, кто реализовывал СММ, достается TRW, остальным — \alpha-расширение.

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

Марковское случайное поле

Система соседства — прямоугольная решетка
Система соседства — прямоугольная решетка

Марковское случайное поле (MRF) — графическая модель, энергия (отрицательный логарифм правдоподобия) которой записывается в виде:
E(X) = \sum_{p \in P} D_p(x_p) + \sum_{(p, q) \in E} V_{pq}(x_p, x_q),
где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы.

Рассмотрим модель со следующими ограничениями:

  • переменные x_p дискретны и принимают значения из множества {1,…,K}, K ≥ 2,
  • система соседства E — прямоугольная решетка,
  • бинарные потенциалы V являются обобщенными потенциалами Поттса: V_{pq} = c_{pq} [x_p \neq x_q] .

В рамках этого задания требуется:

  1. реализовать алгоритм поиска конфигурации X, обладающей минимальной энергией (TRW или α-расширение),
  2. протестировать реализованный алгоритм на модельных задачах,
  3. применить реализованный алгоритм для задачи интерактивной сегментации изображений,
  4. сравнить алгоритмы TRW и α-расширение на задаче сегментации изображений.

MRF для интерактивной сегментации изображений

Пример изображения с пользовательской маской семян
Пример изображения с пользовательской маской семян

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

Для задачи сегментации марковское случайное поле строится следующим образом:

  • Каждая переменная x_p соответствует пикселю изображения.
  • Используется стандартная 4-х связная система соседства.
  • Если пиксель p отнесен пользователем к классу k, то унарные потенциалы „разрешают“ переменной x_p принимать только значение k:
    D_p(k) = 0,\ D_p(l) = +\infty, l \neq k.
  • Если пиксель p не отнесен пользователем ни к одному из классов, то унарные потенциалы принимают значения равные минус логарифму правдоподобия принадлежности пикселя цвета I_p соответствующему классу: D_p(k) = -\log P_k(I_p) .
  • Цветовые модели объектов можно восстановить по пикселям, размеченным пользователем, при помощи EM-алгоритма восстановления смеси нормальных распределений в пространстве YUV.
  • В качестве парных потенциалов выбираются обобщенные потенциалы Поттса, которые поощряют разрезы в тех местах, где цвет изображения сильно меняется: c_{pq} = A + B\:\exp\left(-\frac{|| I_p - I_q ||^2}{2\sigma^2}\right) , A ≥ 0, B ≥ 0, σ — параметры.

Вариант 1 : TRW

Задание

  • Вывести все формулы, использующиеся в вашей реализации TRW (формулировки прямой и двойственной задач, формула подсчета субградиента, конкретная схема субградиентного подъема, и т.д.).
  • Реализовать алгоритм TRW.
  • Протестировать алгоритм TRW на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
  • Привести примеры наличия и отсутствия зазора между решениями прямой и двойственной задач (например, зазор должен отсутствовать в случае субмодулярной энергии).
  • Реализовать процедуру сегментации изображений с заданными пользователем семенами.
  • Привести примеры удачных сегментаций (не менее 5). Требуется самостоятельно выбрать изображения (реалистичные), указать семена и отсегментировать при помощи реализованного метода. В отчет нужно вставлять и исходные изображения, и маски семян.
  • На нескольких (не менее 3) задачах сегментации из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству сегментации. Все выводы должны быть подтверждены числами, графиками, картинками.
  • Написать отчет в формате PDF с описанием всех проведенных исследований.

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

Алгоритм TRW
[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC)
[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, options)
ВХОД
unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
vertC — коэффициенты c_{pq}, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
horC — коэффициенты c_{pq}, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
options — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
  'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
  'argEps' — порог сходимости по аргументу;
  'display' — параметр типа logical: если true, то на каждой итерации нужно выводить на экран номер итерации, текущее значение энергии и нижней границы;
ВЫХОД
labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
lowerBound — значения нижней границы на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма.

Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.

Сегментация изображений
[segmentation] = segmentImage(image, seeds)
ВХОД
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 двойственных переменных, соответствующих условиям y_{pk}^{hor} = y_{pk}^{vert}, \;\; p \in P, \;\; k = 1,\dots,K, где hor и vert обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.

2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема. Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:
\vec{\lambda}_{new} = \vec{\lambda}_{old} + \alpha_t \vec{g}_t, где \vec{g}_t — субградиент в текущей точке, \alpha_t — параметр, отвечающий за длину сдвига. В рамках данного практического задания можно использовать любой способ субградиентного подъема. Например, можно использовать следующий адаптивный метод выбора длины шага:
\alpha_t = \frac{\text{Approx}_t - \text{Dual}_t}{|| \nabla \vec{g}_t|| ^ 2},
где \text{Dual}_t — текущее значение двойственной функции, \text{Approx}_t — оценка оптимума двойственной функции, которую можно определять следующим способом:
\text{Approx}_t = \text{BestDual}_t + \delta_t, где \text{BestDual}_t — лучшее на данный момент значение двойственной функции,
\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}
\gamma_0, \; \gamma_1, \; \varepsilon — параметры метода. Обычно \gamma_0 > 1, \; 1 > \gamma_1 > 0, \; \varepsilon \to 0+ . Конкретные значения этих параметров нужно подобрать.

3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам.

4. При тестировании алгоритма TRW необходимо следить, чтобы наибольшее значение нижней границы было не больше, чем наименьшее значение энергии.

5. Для генерации масок семян для сегментации изображений можно использовать любой редактор растровой графики (например, Paint). На изображении нужно определенным цветом закрасить пиксели, относящиеся к маске, и, впоследствии, выделить их в MATLAB.

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

ZIP архив с MATLAB реализацией конвертера изображений.

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

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

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

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • trwGridPotts.m
  • segmentImage.m
  • Набор вспомогательных файлов при необходимости

Вариант 2 : α-расширение

Задание

  • Вывести все формулы, использующиеся в вашей реализации α-расширения (сведение шага алгоритма к разрезу графа).
  • Реализовать алгоритм α-расширение, используя выданный код разрезов графов.
  • Протестировать алгоритм α-расширение на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
  • Реализовать процедуру сегментации изображений с заданными пользователем семенами.
  • Привести примеры удачных сегментаций (не менее 5). Требуется самостоятельно выбрать изображения (реалистичные), указать семена и отсегментировать при помощи реализованного метода. В отчет нужно вставлять и исходные изображения, и маски семян.
  • На нескольких (не менее 3) задачах сегментации из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству сегментации. Все выводы должны быть подтверждены числами, графиками, картинками.
  • Написать отчет в формате PDF с описанием всех проведенных исследований.

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

Алгоритм α-расширение
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC)
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, options)
ВХОД
unary — унарные потенциалы, массив типа double размера N x M x K, где N — высота решетки, M — ширина решетки, K — количество меток.
vertC — коэффициенты c_{pq}, соответствующие вертикальным ребрам, массив типа double размера (N — 1) x M;
horC — коэффициенты c_{pq}, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
options — (необязательный аргумент) набор дополнительных параметров, массив типа cell вида ParameterName1, ParameterValue1, ParameterName2, ParameterValue2 и т.д. Возможны следующие параметры:
  'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
  'display' — параметр типа logical: если true, то при каждом запуске алгоритма разреза графа нужно выводить на экран номер итерации, номер расширяемой метки, текущее значение энергии;
ВЫХОД
labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;

Обратите внимание: в процедуре alphaExpansionGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.

Сегментация изображений
[segmentation] = segmentImage(image, seeds)
ВХОД
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. Обратите внимание на область применимости алгоритма α-расширение.
  2. При тестировании алгоритма α-расширение необходимо следить за следующим:
    • после каждого применения разреза графа общая энергия не возрастает;
    • значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
  3. Для генерации масок семян для сегментации изображений можно использовать любой редактор растровой графики (например, Paint). На изображении нужно определенным цветом закрасить пиксели, относящиеся к маске, и, впоследствии, выделить их в MATLAB.

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

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

ZIP архив с MATLAB реализацией конвертера изображений.

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

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

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

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • alphaExpansionGridPotts.m
  • segmentImage.m
  • Набор вспомогательных файлов при необходимости
Источник — «http://www.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»
Личные инструменты