Структурные методы анализа изображений и сигналов (курс лекций)/2011/Задание 2
Материал из MachineLearning.
![]() | Статья в настоящий момент дорабатывается. Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. Anton 18:11, 7 апреля 2011 (MSD) |
|
Перейти к основной странице курса
Задание состоит из двух вариантов.
Среда реализации для всех вариантов – MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Марковское случайное поле
Марковское случайное поле (MRF) — графическая модель, энергия (отрицательный логарифм правдоподобия) которой записывается в виде:
где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы.
Рассмотрим модель со следующими ограничения:
- переменные
дискретны и принимают значения из множества {1,…,K}, K ≥ 2,
- система соседства E - прямоугольная решетка,
- бинарные потенциалы V являются обобщенными потенциалами Поттса:
.
В рамках этого задания требуется:
- реализовать алгоритм поиска конфигурации MRF, обладающей минимальной энергией (TRW или α-expansion),
- протестировать реализованный алгоритм на модельных задачах,
- применить реализованный алгоритм для задачи интерактивной сегментации изображений,
- сравнить алгоритмы TRW и α-expansion на задаче сегментации изображений.
MRF для интерактивной сегментации изображений
Задача сегментации изображения состоит в отнесении каждого пикселя изображения к одному из K классов. В интерактивном варианте пользователь отмечает часть пикселей, принадлежащих каждому классу. После этого требуется автоматически разметить оставшуюся часть изображения.
Для задачи сегментации марковское случайное поле строится, например, так:
- Каждая переменная
соответствует пикселю изображения.
- Используется стандартная 4-х связная система соседства.
- Если пиксель p отнесен пользователем к классу k, то унарные потенциалы „разрешают“ переменной
принимать только значение k:
.
- Если пиксель p не отнесен пользователем ни к одному из классов, то унарные потенциалы принимают значения равные минус логарифму правдоподобия принадлежности пикселя цвета
соответствующему классу:
.
- Цветовые модели объектов можно восстановить по пикселям, размеченным пользователем, при помощи EM-алгоритма восстановления смеси нормальных распределений в пространстве Luv.
- В качестве парных потенциалов выбираются обобщенные потенциалы Поттса с коэффициентами α, делающими разрез более энергетически-выгодным, там где цвет изображения сильно меняется:
, A ≥ 0, B ≥ 0, σ — параметры.
Вариант 1 : TRW
Задание
- Вывести все формулы, использующиеся в вашей реализации TRW.
- Реализовать алгоритм TRW.
- Протестировать алгоритм TRW на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
- Привести примеры наличия duality gap (разрыв двойственности, двойственный зазор?) и отсутствия его.
- Реализовать процедуру сегментации изображений с заданными пользователем семенами.
- Привести примеры удачных сегментаций (не менее 5).
- На нескольких (не менее 3-х) задачах сегментации сравнить работу алгоритмов TRW и α-expansion. Недостающую реализацию можно взять у товарища, выполняющего другой вариант.
- Написать отчет в формате PDF с описанием всех проведенных исследований.
Спецификация реализуемых функций
Алгоритм TRW | ||||||
---|---|---|---|---|---|---|
[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC) | ||||||
[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, options) | ||||||
ВХОД | ||||||
| ||||||
ВЫХОД | ||||||
|
Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
Сегментация изображений | ||
---|---|---|
[segmentation] = segmentImage(image, seeds) | ||
ВХОД | ||
| ||
ВЫХОД | ||
|
Обратите внимание: в процедуре segmentImage параметры N, M, и K определяются неявно по размеру соответствующих элементов.
Рекомендации по выполнению задания
1. При разбиении MRF-решетки на вертикальные и горизонтальные цепочки формулировка несколько упрощается:
- Каждое ребро графа принадлежит только одному подграфу, а значит не нужно вводить двойственные переменные, соответствующие ребрам.
- Каждое вершина принадлежит только двум деревьям, а значит можно ввести |P|K двойственных переменных, соответствующих условиям
, где hor и vert, обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.
2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема.
Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:
где
— субградиент в текущей точке,
— параметр, отвечающий за длину сдвига.
В рамках данного практического задания рекомендуется использовать адаптивный метод выбора длины шага:
где — текущее значение двойственной функции, </tex>\text{Approx}_t</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 с описанием всех проведенных исследований.
Спецификация реализуемых функций
Алгоритм α-expansion | |||||
---|---|---|---|---|---|
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC) | |||||
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, options) | |||||
ВХОД | |||||
| |||||
ВЫХОД | |||||
|
Обратите внимание: в процедуре alphaExpansionGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
Сегментация изображений | ||
---|---|---|
[segmentation] = segmentImage(image, seeds) | ||
ВХОД | ||
| ||
ВЫХОД | ||
|
Обратите внимание: в процедуре segmentImage параметры N, M, и K определяются неявно по размеру соответствующих элементов.
Рекомендации по выполнению задания
- Обратите внимание на область применимости алгоритма α-expansion.
- При тестировании алгоритма α-expansion необходимо следить чтобы:
- после каждого применения разреза графа общая энергия не возрастает;
- значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
Данные для выполнения задания
ZIP архив с MATLAB интерфейсом к разрезам графов.
Оформление задания
Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 2. ФИО, номер группы, вариант 2». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
- PDF-файл с описанием проведенных исследований
- alphaExpansionGridPotts.m
- segmentImage.m
- Набор вспомогательных файлов при необходимости