Графические модели (курс лекций)/2012/Задание 3
Материал из MachineLearning.
м (орфография) |
м |
||
(3 промежуточные версии не показаны) | |||
Строка 1: | Строка 1: | ||
- | |||
- | |||
- | |||
- | |||
- | |||
{{TOCright|300px}} | {{TOCright|300px}} | ||
Строка 50: | Строка 45: | ||
Марковское случайное поле (MRF) — графическая модель, энергия которой записывается в виде:<br> | Марковское случайное поле (MRF) — графическая модель, энергия которой записывается в виде:<br> | ||
<tex> | <tex> | ||
- | E(X) = \sum_{p \in P | + | E(X) = \sum_{p \in P} D_p(x_p) + \sum_{(p, q) \in E} V_{pq}(x_p, x_q), |
</tex><br> | </tex><br> | ||
где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы. | где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы. | ||
Строка 57: | Строка 52: | ||
*переменные <tex> x_p </tex> дискретны и принимают значения из множества {1,…,K}, K ≥ 2, | *переменные <tex> x_p </tex> дискретны и принимают значения из множества {1,…,K}, K ≥ 2, | ||
*система соседства E — прямоугольная решетка, | *система соседства E — прямоугольная решетка, | ||
- | *бинарные потенциалы V представимы в виде произведения множителя, не зависящего от значений соседних переменных, и множителя, зависящего только от них | + | *бинарные потенциалы V представимы в виде произведения множителя, не зависящего от значений соседних переменных, и множителя, зависящего только от них: <tex>V_{pq} = c_{pq} d(x_p, x_q) </tex>. |
В рамках этого задания требуется: | В рамках этого задания требуется: | ||
Строка 71: | Строка 66: | ||
*Переменная <tex>x_p</tex> соответствуют пикселям одного из изображений. | *Переменная <tex>x_p</tex> соответствуют пикселям одного из изображений. | ||
*Используется стандартная 4-х связная система соседства. | *Используется стандартная 4-х связная система соседства. | ||
- | *Унарные потенциалы должны показывать насколько хорошо выбранные пиксели двух изображений соответствуют друг другу. В простейшем случае можно взять евклидово расстояние между цветами пикселей в формате [http://en.wikipedia.org/wiki/YUV YUV]. Более совершенные унарные потенциалы описаны в статье: S. Birchfield, C. Tomasi, A pixel dissimilarity measure that is insensitive to image sampling, IEEE TPAMI, 20(4):401–409, 1998, http://ce.sharif.edu/~elno/disparitymap/Papers/dissimilarity_pami1998.pdf. | + | *Унарные потенциалы должны показывать, насколько хорошо выбранные пиксели двух изображений соответствуют друг другу. В простейшем случае можно взять евклидово расстояние между цветами пикселей в формате [http://en.wikipedia.org/wiki/YUV YUV]. Более совершенные унарные потенциалы описаны в статье: S. Birchfield, C. Tomasi, A pixel dissimilarity measure that is insensitive to image sampling, IEEE TPAMI, 20(4):401–409, 1998, http://ce.sharif.edu/~elno/disparitymap/Papers/dissimilarity_pami1998.pdf. |
*В качестве расстояния d между метками соседних переменных можно взять усеченный модуль разности: <tex>d(x_p, x_q) = |x_p - x_q| [x_p-x_q < L] + L [x_p-x_q \geq L]</tex>, L ≥ 0 — параметр. | *В качестве расстояния d между метками соседних переменных можно взять усеченный модуль разности: <tex>d(x_p, x_q) = |x_p - x_q| [x_p-x_q < L] + L [x_p-x_q \geq L]</tex>, L ≥ 0 — параметр. | ||
*Веса ребер c могут иметь большие значения там, где градиент на изображении мал, и маленькие значения там, где градиент большой. Например: <tex>c_{pq} = a \exp(-\|I_p - I_q\| / s)</tex>, где a ≥ 0, s ≥ 0 — параметры. | *Веса ребер c могут иметь большие значения там, где градиент на изображении мал, и маленькие значения там, где градиент большой. Например: <tex>c_{pq} = a \exp(-\|I_p - I_q\| / s)</tex>, где a ≥ 0, s ≥ 0 — параметры. | ||
Строка 133: | Строка 128: | ||
!''Стерео'' | !''Стерео'' | ||
|- | |- | ||
- | |[ | + | |[disparity] = stereo(name) |
+ | |- | ||
+ | |ВХОД | ||
+ | |- | ||
+ | | | ||
+ | {|border="0" | ||
+ | |name — название стерео пары, строка. | ||
+ | |} | ||
|- | |- | ||
|ВЫХОД | |ВЫХОД | ||
Строка 139: | Строка 141: | ||
| | | | ||
{| | {| | ||
- | | | + | |disparity — массив смещений массив типа double размера N x M со значениями -∞,...,∞. |
|} | |} | ||
|} | |} | ||
- | В каталоге из которого будет запускаться решение при проверке будет лежать выданный каталог datasets. | + | В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets. |
=== Рекомендации по выполнению задания === | === Рекомендации по выполнению задания === | ||
Строка 161: | Строка 163: | ||
\max(\gamma_1 \delta_t, \; \varepsilon ), \;\; \text{Dual}_t \leq \text{Dual}_{t-1}. \end{cases}</tex><br> | \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>. Конкретные значения этих параметров нужно подобрать. | <tex>\gamma_0, \; \gamma_1, \; \varepsilon</tex> — параметры метода. Обычно <tex>\gamma_0 > 1, \; 1 > \gamma_1 > 0, \; \varepsilon \to 0+ </tex>. Конкретные значения этих параметров нужно подобрать. | ||
+ | |||
+ | Подробнее о методах субградиентного подъема написано в статье: | ||
+ | N. Komodakis, N.Paragios and G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE TPAMI, 33(3):531-552, 2011, | ||
+ | http://www.csd.uoc.gr/~komod/publications/docs/DualDecomposition_PAMI.pdf | ||
3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам. | 3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам. | ||
Строка 174: | Строка 180: | ||
=== Оформление задания === | === Оформление задания === | ||
- | Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 3. ФИО | + | Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 3. ФИО, вариант 1». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации. |
Письмо должно содержать: | Письмо должно содержать: | ||
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел) | *PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел) | ||
- | *trwGridPotts | + | *trwGridPotts.m, stereo.m |
- | + | ||
*Набор вспомогательных файлов при необходимости | *Набор вспомогательных файлов при необходимости | ||
Строка 235: | Строка 240: | ||
!''Стерео'' | !''Стерео'' | ||
|- | |- | ||
- | |[ | + | |[disparity] = stereo(name) |
+ | |- | ||
+ | |ВХОД | ||
+ | |- | ||
+ | | | ||
+ | {|border="0" | ||
+ | |name — название стерео пары, строка. | ||
+ | |} | ||
|- | |- | ||
|ВЫХОД | |ВЫХОД | ||
Строка 241: | Строка 253: | ||
| | | | ||
{| | {| | ||
- | | | + | |disparity — массив смещений массив типа double размера N x M со значениями -∞,...,∞. |
|} | |} | ||
|} | |} | ||
- | В каталоге из которого будет запускаться решение при проверке будет лежать выданный каталог datasets. | + | В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets. |
=== Рекомендации по выполнению задания === | === Рекомендации по выполнению задания === | ||
Строка 261: | Строка 273: | ||
=== Оформление задания === | === Оформление задания === | ||
- | Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 3. ФИО | + | Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «Задание 3. ФИО, вариант 2». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации. |
Письмо должно содержать: | Письмо должно содержать: | ||
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел) | *PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел) | ||
- | *alphaExpansionGridPotts | + | *alphaExpansionGridPotts.m, stereo.m |
- | + | ||
*Набор вспомогательных файлов при необходимости | *Набор вспомогательных файлов при необходимости | ||
[[Категория:Учебные курсы]] | [[Категория:Учебные курсы]] | ||
[[Категория:Байесовские методы]] | [[Категория:Байесовские методы]] |
Текущая версия
|
Начало выполнения задания: 28 марта 2012
Срок сдачи: 11 апреля 2012, 23:59
Задание состоит из двух вариантов. Распределение вариантов задания по студентам:
Вариант 1 | Вариант 2 |
---|---|
Бобрик К. | Ермушева А. |
Кириллов А. | Фигурнов М. |
Сабурова М. | Меркулова Т. |
Елшин Д. | Некрасов К. |
Новиков П. | Артюхин С. |
Полежаев В. | Гаврилюк К. |
Соколов Е. | Шанин И. |
Зимовнов А. | Матвеева Д. |
Алексадров Я. | Марченко Е. |
Плященко Е. | Цупков С. |
Игнатьев О. | Панов А. |
Тихонов А. |
Среда реализации для всех вариантов — MATLAB. Неэффективная реализация кода может негативно отразиться на оценке.
Марковское случайное поле
Марковское случайное поле (MRF) — графическая модель, энергия которой записывается в виде:
где P — множество индексов переменных, E — система соседства, D — унарные потенциалы, V — бинарные потенциалы.
Рассмотрим модель со следующими ограничениями:
- переменные
дискретны и принимают значения из множества {1,…,K}, K ≥ 2,
- система соседства E — прямоугольная решетка,
- бинарные потенциалы V представимы в виде произведения множителя, не зависящего от значений соседних переменных, и множителя, зависящего только от них:
.
В рамках этого задания требуется:
- реализовать алгоритм поиска конфигурации
, обладающей минимальной энергией (TRW или α-расширение),
- протестировать реализованный алгоритм на модельных задачах,
- применить реализованный алгоритм для задачи стерео,
- сравнить алгоритмы TRW и α-расширение на задаче стерео.
MRF для стерео
Задача стерео состоит в сопоставлении каждому пикселю одного изображения пикселя другого изображений. В рамках данного задания рассматривается выровненное стерео, что означает, что соответствующие пиксели лежат на одной горизонтальной линии. В этих условиях переменные имеют смысл смещений по горизонтали (диспаритетов).
Для задачи стерео марковское случайное поле строится следующим образом:
- Переменная
соответствуют пикселям одного из изображений.
- Используется стандартная 4-х связная система соседства.
- Унарные потенциалы должны показывать, насколько хорошо выбранные пиксели двух изображений соответствуют друг другу. В простейшем случае можно взять евклидово расстояние между цветами пикселей в формате YUV. Более совершенные унарные потенциалы описаны в статье: S. Birchfield, C. Tomasi, A pixel dissimilarity measure that is insensitive to image sampling, IEEE TPAMI, 20(4):401–409, 1998, http://ce.sharif.edu/~elno/disparitymap/Papers/dissimilarity_pami1998.pdf.
- В качестве расстояния d между метками соседних переменных можно взять усеченный модуль разности:
, L ≥ 0 — параметр.
- Веса ребер c могут иметь большие значения там, где градиент на изображении мал, и маленькие значения там, где градиент большой. Например:
, где a ≥ 0, s ≥ 0 — параметры.
Вариант 1 : TRW
Задание
- Вывести все формулы, использующиеся в вашей реализации TRW (формулировки прямой и двойственной задач, формула подсчета субградиента, конкретная схема субградиентного подъема, и т.д.).
- Реализовать алгоритм TRW.
- Протестировать алгоритм TRW на модельных данных.
- Привести примеры наличия и отсутствия зазора между решениями прямой и двойственной задач (например, зазор должен отсутствовать в случае субмодулярной энергии).
- Реализовать процедуру решения задачи стерео.
- Подобрать параметры так, чтобы на выданных стереопарах достигался хороший результат. Набор параметров может быть своим для каждой стереопары.
- На одной стереопаре из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству решения. Все выводы должны быть подтверждены числами, графиками, картинками.
- Написать отчет в формате PDF с описанием всех проведенных исследований.
Спецификация реализуемых функций
Алгоритм TRW | ||||||||
---|---|---|---|---|---|---|---|---|
[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, metric) | ||||||||
[labels, energy, lowerBound, time] = trwGridPotts(unary, vertC, horC, metric, options) | ||||||||
ВХОД | ||||||||
| ||||||||
ВЫХОД | ||||||||
|
Обратите внимание: в процедуре trwGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
Стерео | |
---|---|
[disparity] = stereo(name) | |
ВХОД | |
| |
ВЫХОД | |
|
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets.
Рекомендации по выполнению задания
1. При разбиении MRF-решетки только на вертикальные и горизонтальные цепочки формулировка несколько упрощается:
- Каждое ребро графа принадлежит только одному подграфу, а, значит, не нужно вводить двойственные переменные, соответствующие ребрам.
- Каждая вершина принадлежит только двум деревьям, а, значит, можно ввести |P|K двойственных переменных, соответствующих условиям
, где hor и vert обозначают горизонтальную и вертикальную цепочку, проходящую через p-ю вершину.
2. Поскольку двойственная функция вогнута и кусочно-линейна, оптимизировать ее можно при помощи алгоритма субградиентного подъема.
Каждый шаг метода субградиентного подъема состоит в пересчете значений двойственных переменных λ по следующему правилу:
где
— субградиент в текущей точке,
— параметр, отвечающий за длину сдвига.
В рамках данного практического задания можно использовать любой способ субградиентного подъема. Например, можно использовать следующий адаптивный метод выбора длины шага:
где — текущее значение двойственной функции,
— оценка оптимума двойственной функции, которую можно определять следующим способом:
где
— лучшее на данный момент значение двойственной функции,
— параметры метода. Обычно
. Конкретные значения этих параметров нужно подобрать.
Подробнее о методах субградиентного подъема написано в статье: N. Komodakis, N.Paragios and G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE TPAMI, 33(3):531-552, 2011, http://www.csd.uoc.gr/~komod/publications/docs/DualDecomposition_PAMI.pdf
3. В качестве текущего значения энергии в рамках алгоритма TRW можно выбрать минимум энергий разметок, полученных по только вертикальным и только горизонтальным цепочкам.
4. При тестировании алгоритма TRW необходимо следить, чтобы наибольшее значение нижней границы было не больше, чем наименьшее значение энергии.
5. Потенциалы для стереопары tsukuba и примеры работы различных алгоритмов: http://vision.middlebury.edu/MRF/results/tsukuba/index.html
Данные для выполнения задания
rgb2luv — конвертер изображений в формат YUV.
datasets — стереопары.
Оформление задания
Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 3. ФИО, вариант 1». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
- PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
- trwGridPotts.m, stereo.m
- Набор вспомогательных файлов при необходимости
Вариант 2 : α-расширение
Задание
- Вывести все формулы, использующиеся в вашей реализации α-расширения (сведение шага алгоритма к разрезу графа).
- Реализовать алгоритм α-расширение, используя выданный код разрезов графов.
- Протестировать алгоритм α-расширение на модельных данных (например, решетка 100 x 100, 10 классов, случайные потенциалы).
- Реализовать процедуру решения задачи стерео.
- Подобрать параметры так, чтобы на выданных стереопарах достигался хороший результат. Набор параметров может быть своим для каждой стереопары.
- На одной стереопаре из предыдущего пункта сравнить работу алгоритмов TRW и α-расширение. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству решения. Все выводы должны быть подтверждены числами, графиками, картинками.
- Написать отчет в формате PDF с описанием всех проведенных исследований.
Спецификация реализуемых функций
Алгоритм α-расширение | |||||||
---|---|---|---|---|---|---|---|
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, metric) | |||||||
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, metric, options) | |||||||
ВХОД | |||||||
| |||||||
ВЫХОД | |||||||
|
Обратите внимание: в процедуре alphaExpansionGridPotts параметры N, M, и K определяются неявно по размеру соответствующих элементов.
Стерео | |
---|---|
[disparity] = stereo(name) | |
ВХОД | |
| |
ВЫХОД | |
|
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets.
Рекомендации по выполнению задания
- Обратите внимание на область применимости алгоритма α-расширение.
- При тестировании алгоритма α-расширение необходимо следить за следующим:
- после каждого применения разреза графа общая энергия не возрастает;
- значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
- Потенциалы для стереопары tsukuba и примеры работы различных алгоритмов: http://vision.middlebury.edu/MRF/results/tsukuba/index.html
Данные для выполнения задания
graphCut — MATLAB интерфейс к разрезам графов.
rgb2luv — конвертер изображений в формат YUV.
datasets — стереопары.
Оформление задания
Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «Задание 3. ФИО, вариант 2». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
- PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
- alphaExpansionGridPotts.m, stereo.m
- Набор вспомогательных файлов при необходимости