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

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

Версия от 16:09, 11 апреля 2011; Anton (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья в настоящий момент дорабатывается.
Формулировка задания находится в стадии формирования. Просьба не приступать к выполнению задания, пока это предупреждение не будет удалено. Anton 18:11, 7 апреля 2011 (MSD)

Содержание

1 Марковское случайное поле
- 1.1 MRF для интерактивной сегментации изображений
- 1.2 Метод субградиентного подъема для алгоритма TRW
2 Вариант 1 : TRW
3 Вариант 2 : α-expansion

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

Задание состоит из двух вариантов.

Среда реализации для всех вариантов – 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} = \alpha_{pq} [x_p \neq x_q]$ .

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

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

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-алгоритма восстановления смеси нормальных распределений в пространстве Luv.
В качестве парных потенциалов выбираются обобщенные потенциалы Поттса с коэффициентами α, делающими разрез более энергетически-выгодным, там где цвет изображения сильно меняется: $\alpha_{pq} = A + B\:\exp\left(-\frac{|| I_p - I_q ||^2}{2\sigma^2}\right)$ , A ≥ 0, B ≥ 0, σ — параметры.