Графические модели (курс лекций)/2014/Задание 3

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{main|Графические модели (курс лекций)/2014}} __NOTOC__ {{stop| '''Задание находится в стадии разработки.'''<br/> Не пр...)
 
(6 промежуточных версий не показаны.)
Строка 1: Строка 1:
{{main|Графические модели (курс лекций)/2014}}
{{main|Графические модели (курс лекций)/2014}}
__NOTOC__
__NOTOC__
-
 
-
{{stop|
 
-
'''Задание находится в стадии разработки.'''<br/>
 
-
Не приступайте к выполнению задания, пока это объявление не убрано.
 
-
}}
 
{|
{|
Строка 20: Строка 15:
!''Вариант 1'': α-расширение || ''Вариант 2'': αβ-замена
!''Вариант 1'': α-расширение || ''Вариант 2'': αβ-замена
|-
|-
-
|Кондрашкин Д. || Нижибицкий Е.
+
|Харациди О. || Рыжков А.
|-
|-
-
|Остапец А. || Фонарев А.
+
|Ульянов Д. || Горелов А.
|-
|-
-
|Ромов П. || Лобачева Е.
+
|Антипов А. || Львов С.
|-
|-
-
|Куракин А. || Новиков М.
+
|Сокурский Ю. || Новиков А.
|-
|-
-
|Березин А. || Любимцева М.
+
|Алешин И. || Шадриков А.
|-
|-
-
| Исмагилов Т. || Потапенко А.
+
| Ломов Н. || Никифоров А.
|-
|-
-
| Шаймарданов И. || Зак Е.
+
| Найдин О. || Шабашев Ф.
|-
|-
-
| Малышева Е. || Огнева Д.
+
| Зиннурова Э. || Подоприхин Д.
|-
|-
-
| Морозова Д. || Борисов М.
+
| Корольков М. || Арбузова Д.
|-
|-
-
| Гавриков М. ||
+
| Новиков М. (420) || Петров Г.
 +
|-
 +
| Шахуро В. (420) || Грингауз А. (320)
 +
|-
 +
| Ибадов Т. (420) || Старцев М. (420)
|-
|-
|}
|}
Строка 46: Строка 45:
Марковское случайное поле (MRF) — графическая модель, энергия которой записывается в виде:<br>
Марковское случайное поле (MRF) — графическая модель, энергия которой записывается в виде:<br>
<tex>
<tex>
-
E(X) = \sum_{p \in P} D_p(x_p) + \sum_{(p, q) \in \mathcal{E}} V_{pq}(x_p, x_q),
+
E(X) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{(i, j) \in \mathcal{E}} \theta_{ij}(x_i, x_j), \quad x_i \in \mathcal{P},
</tex><br>
</tex><br>
-
где P — множество индексов переменных, <tex>\mathcal{E} </tex> — система соседства, D — унарные потенциалы, V — парные потенциалы.
+
где <tex>\mathcal{V}</tex> — множество индексов переменных, <tex>\mathcal{E} </tex> — система соседства, <tex>\theta_i: \mathcal{P} \to \mathbb{R}</tex> — унарные потенциалы, <tex>\theta_{ij}: \mathcal{P}\times\mathcal{P} \to \mathbb{R}</tex> — парные потенциалы. Обратите внимание, что в сумме по рёбрам
 +
<tex>(i, j) \in \mathcal{E}</tex> каждое ребро графа учитывается только один раз.
Рассмотрим модель со следующими ограничениями:
Рассмотрим модель со следующими ограничениями:
-
*переменные <tex> x_p </tex> дискретны и принимают значения из множества {1,…,K}, K ≥ 2,
+
*переменные <tex> x_p </tex> дискретны и принимают значения из множества <tex>\mathcal{P} = \{1,\ldots,K\}, \;K \geq 2</tex>,
*система соседства <tex>\mathcal{E} </tex> — прямоугольная решетка,
*система соседства <tex>\mathcal{E} </tex> — прямоугольная решетка,
-
*парные потенциалы V представимы в виде произведения множителя, не зависящего от значений соседних переменных, и множителя, зависящего только от них: <tex>V_{pq} = c_{pq} d(x_p, x_q) </tex>.
 
-
=== MRF для стерео ===
+
В рамках данного задания каждый студент должен реализовать один алгоритм минимизации энергии: вариант 1 реализует алгоритм α-расширение, вариант 2 — αβ-замена. Далее в задании алгоритм соответствующего варианта обозначается как ''алгоритм''.
-
Задача стерео состоит в сопоставлении каждому пикселю одного изображения пикселя другого изображений. В рамках данного задания рассматривается выровненное стерео, что означает, что соответствующие пиксели лежат на одной горизонтальной линии. В этих условиях переменные имеют смысл смещений по горизонтали (диспаритетов).
+
-
Для задачи стерео марковское случайное поле строится следующим образом:
+
=== MRF для склеивания изображений ===
-
*Переменная <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.
+
*Унарные потенциалы должны показывать, из каких изображений должны быть взяты некоторые пиксели (так называемые семена).
-
*В качестве расстояния 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 — параметр.
+
*Парные потенциалы должны поощрять 1) короткие разрезы и 2) расположение разреза там, где изображения хорошо соответствуют друг другу.
-
*Веса ребер c могут иметь большие значения там, где градиент на изображении мал, и маленькие значения там, где градиент большой.
+
-
В рамках данного задания рассматривается задача поиска конфигурации, обладающей минимальной энергией. Вариант 1 работает с алгоритмом α-расширение, вариант 2 — αβ-замена. Далее в задании алгоритм соответствующего варианта обозначается ''алгоритм''.
+
В рамках данного задание предполагается, что студентами будет проведено исследование по подбору потенциалов, обеспечивающих визуально хорошее качество склеивания изображений.
=== Задание ===
=== Задание ===
-
* Вывести все формулы, использующиеся в вашей реализации ''алгоритма'' (сведение шага алгоритма к разрезу графа).
+
# Вывести все формулы, использующиеся в вашей реализации ''алгоритма'' (сведение шага алгоритма к разрезу графа).
-
* Реализовать ''алгоритм'', используя выданный код разрезов графов.
+
# Реализовать ''алгоритм'', используя выданный код разрезов графов.
-
* Протестировать ''алгоритм'' на модельных данных.
+
# Протестировать ''алгоритм'' на модельных данных.
-
* Реализовать процедуру решения задачи стерео.
+
# Реализовать процедуру решения задачи склеивания двух изображений. Построить не менее 1 ''хорошей'' композиции, состоящей из двух частей.
-
* Подобрать унарные и парные потенциалы так, чтобы на выданных стереопарах достигался хороший (относительно истинных смещений) результат. Набор унарных и парных потенциалов, а также их параметров может быть своим для каждой стереопары.
+
# Реализовать процедуру склеивания произвольного числа изображений. Построить не менее 1 ''хорошей'' композиции, состоящей из не менее чем 4-х частей.
-
* На нескольких стереопарах из предыдущего пункта сравнить работу алгоритмов α-расширение и αβ-замена. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству решения. Все выводы должны быть подтверждены числами, графиками, картинками.
+
# На задаче склеивания Вашего набора изображений сравнить работу алгоритмов α-расширение и αβ-замена. Реализацию недостающего алгоритма можно взять у товарища, выполняющего другой вариант (в отчете обязательно указывать, чей код вы используете). Требуется провести сравнение по энергии получаемого решения, по времени работы, по визуальному качеству решения. Все выводы должны быть подтверждены числами, графиками, картинками.
-
* Написать отчет в формате PDF с описанием всех проведенных исследований.
+
# Написать отчет в формате PDF с описанием всех проведенных исследований.
 +
 
 +
Обратите внимание, что для выполнения пунктов 4 и 5 каждый студент должен использовать уникальные (отличающиеся от изображений других студентов) изображения. Допускается как использование фотографий, сделанных собственноручно, так и использование картинок из интернета. Создание необычных (на усмотрение преподавателей) коллажей будет поощряться.
 +
 
 +
Композиция является ''хорошей'', если границы на ней не более заметны, чем на композиции, приведённой в начале этого задания. Для достижения ''хорошего'' качества рекомендуется использовать редакторы изображений для выравнивания геометрии и цветов исходных изображений.
 +
 
=== Спецификация реализуемых функций ===
=== Спецификация реализуемых функций ===
Строка 100: Строка 106:
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
|horC — коэффициенты <tex> c_{pq}</tex>, соответствующие горизонтальным ребрам, массив типа double размера N x (M — 1);
|-
|-
-
|metric - расстояние между метками соседних переменных, массив типа double размера K x K;
+
|metric — расстояние между метками соседних переменных, массив типа double размера K x K;
|-
|-
|options — (необязательный аргумент) набор дополнительных параметров, структура с полями
|options — (необязательный аргумент) набор дополнительных параметров, структура с полями
Строка 127: Строка 133:
{|class="standard"
{|class="standard"
-
!''Стерео''
+
!''Склеивание''
|-
|-
-
|[disparity] = stereo(name)
+
|[resultImage, resultMask] = stichImages(images, seeds)
|-
|-
|ВХОД
|ВХОД
Строка 135: Строка 141:
|
|
{|border="0"
{|border="0"
-
|name — название стерео пары, строка.
+
|images — набор исходных изображений, cell array размера K x 1, где K – кол-во изображений. Все изображения должны быть одинакового разрешения и содержать ровно 3 цветовых канала.
 +
|-
 +
|seeds — маски, заданные пользователем, cell array размера K x 1. Каждый элемент - логический массив размера, равного разрешению изображения, в котором значение true означает, что соответствующий пиксель должен быть взят из соответствующего изображения.
|}
|}
|-
|-
Строка 142: Строка 150:
|
|
{|
{|
-
|disparity — массив смещений массив типа double размера N x M со значениями -∞,...,∞.
+
|resultImage — построенное изображение.
 +
|-
 +
|resultMask — маска ответа, массив типа double, по размеру равный разрешению изображения. Элемент results(i,j) равен k, если в построенном изображении пиксель (i, j) взят из исходного изображения номер k.
|}
|}
|}
|}
-
В каталоге, из которого будет запускаться решение при проверке, будет лежать выданный каталог datasets.
 
=== Рекомендации по выполнению задания ===
=== Рекомендации по выполнению задания ===
Строка 152: Строка 161:
#* после каждого применения разреза графа общая энергия не возрастает;
#* после каждого применения разреза графа общая энергия не возрастает;
#* значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
#* значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
-
# Потенциалы для стереопары tsukuba и примеры работы различных алгоритмов: http://vision.middlebury.edu/MRF/results/tsukuba/index.html
+
# Обратите внимание, что для достижения хорошего качества решения задачи склеивания, возможно придется изменить интерфейс, выданный в задании. При использовании измененного прототипа ОБЯЗАТЕЛЬНО нужно прислать и функцию, согласованную с выданным прототипом.
=== Данные для выполнения задания ===
=== Данные для выполнения задания ===
[[Media:GM_GraphCut.zip|graphCut]] — MATLAB интерфейс к разрезам графов.
[[Media:GM_GraphCut.zip|graphCut]] — MATLAB интерфейс к разрезам графов.
-
 
-
[[Media:SMAIS11_task2_Converter.zip|rgb2luv]] — конвертер изображений в формат [http://en.wikipedia.org/wiki/YUV YUV].
 
-
 
-
[[Media:GM_Stereo_Datasets.zip‎|datasets]] — стереопары.
 
=== Оформление задания ===
=== Оформление задания ===
-
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «[ГМ13] задание 4, вариант X, фамилия». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
+
Выполненный вариант задания необходимо прислать письмом по адресу ''bayesml@gmail.com'' с темой «[ГМ14] задание 3, вариант X, фамилия». Убедительная просьба присылать выполненное задание '''только один раз''' с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.
Письмо должно содержать:
Письмо должно содержать:
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
*PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
*Все исходные файлы, реализованные в рамках настоящего задания. Убедитесь, что Ваши файлы работают и соответствуют прототипам!
*Все исходные файлы, реализованные в рамках настоящего задания. Убедитесь, что Ваши файлы работают и соответствуют прототипам!
 +
*Не менее двух склеенных изображений и соответствующих им наборов исходных.
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Текущая версия

Основная статья: Графические модели (курс лекций)/2014


Задача склеивания изображений: построение одного изображения по набору исходных.
Задача склеивания изображений: построение одного изображения по набору исходных.

Начало выполнения задания: 1 апреля 2014 г.;
Срок сдачи: 14 апреля 2014 г. (понедельник), 23:59.

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

Задание состоит из двух вариантов. Распределение вариантов задания по студентам:

Вариант 1: α-расширение Вариант 2: αβ-замена
Харациди О. Рыжков А.
Ульянов Д. Горелов А.
Антипов А. Львов С.
Сокурский Ю. Новиков А.
Алешин И. Шадриков А.
Ломов Н. Никифоров А.
Найдин О. Шабашев Ф.
Зиннурова Э. Подоприхин Д.
Корольков М. Арбузова Д.
Новиков М. (420) Петров Г.
Шахуро В. (420) Грингауз А. (320)
Ибадов Т. (420) Старцев М. (420)

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

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

Марковское случайное поле (MRF) — графическая модель, энергия которой записывается в виде:
E(X) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{(i, j) \in \mathcal{E}} \theta_{ij}(x_i, x_j), \quad x_i \in \mathcal{P},
где \mathcal{V} — множество индексов переменных, \mathcal{E} — система соседства, \theta_i: \mathcal{P} \to \mathbb{R} — унарные потенциалы, \theta_{ij}: \mathcal{P}\times\mathcal{P} \to \mathbb{R} — парные потенциалы. Обратите внимание, что в сумме по рёбрам (i, j) \in \mathcal{E} каждое ребро графа учитывается только один раз.

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

  • переменные x_p дискретны и принимают значения из множества \mathcal{P} = \{1,\ldots,K\}, \;K \geq 2,
  • система соседства \mathcal{E} — прямоугольная решетка,

В рамках данного задания каждый студент должен реализовать один алгоритм минимизации энергии: вариант 1 реализует алгоритм α-расширение, вариант 2 — αβ-замена. Далее в задании алгоритм соответствующего варианта обозначается как алгоритм.

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

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

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

  • Переменные x_p соответствуют пикселям финального изображения.
  • Значение каждой переменной соответствует номеру изображения исходного набора, из которого взят цвет соответствующего пикселя.
  • Используется стандартная 4-х связная система соседства.
  • Унарные потенциалы должны показывать, из каких изображений должны быть взяты некоторые пиксели (так называемые семена).
  • Парные потенциалы должны поощрять 1) короткие разрезы и 2) расположение разреза там, где изображения хорошо соответствуют друг другу.

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

Задание

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

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

Композиция является хорошей, если границы на ней не более заметны, чем на композиции, приведённой в начале этого задания. Для достижения хорошего качества рекомендуется использовать редакторы изображений для выравнивания геометрии и цветов исходных изображений.


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

Алгоритм
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, metric)
[labels, energy, time] = alphaExpansionGridPotts(unary, vertC, horC, metric, options)
[labels, energy, time] = alphaBetaSwapGridPotts(unary, vertC, horC, metric)
[labels, energy, time] = alphaBetaSwapGridPotts(unary, vertC, horC, metric, 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);
metric — расстояние между метками соседних переменных, массив типа double размера K x K;
options — (необязательный аргумент) набор дополнительных параметров, структура с полями
  'maxIter' — максимально допустимое число итераций алгоритма (по умолчанию = 500);
  'display' — параметр типа logical: если true, то при каждом запуске алгоритма разреза графа нужно выводить на экран номер итерации, номера обрабатываемых меток, текущее значение энергии;
  'numStart' — количество запусков из разных начальных приближений;
  'randOrder' — параметр типа logical: если true, то при каждом запуске использовать случайный порядок меток α и β;
ВЫХОД
labels — разметка, обладающая наименьшей энергией, массив типа double размера N x M;
energy — значения энергии на каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;
time — время, пройденное с начала работы алгоритма до каждой итерации, вектор типа double длины, равной количеству итераций алгоритма;

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

Склеивание
[resultImage, resultMask] = stichImages(images, seeds)
ВХОД
images — набор исходных изображений, cell array размера K x 1, где K – кол-во изображений. Все изображения должны быть одинакового разрешения и содержать ровно 3 цветовых канала.
seeds — маски, заданные пользователем, cell array размера K x 1. Каждый элемент - логический массив размера, равного разрешению изображения, в котором значение true означает, что соответствующий пиксель должен быть взят из соответствующего изображения.
ВЫХОД
resultImage — построенное изображение.
resultMask — маска ответа, массив типа double, по размеру равный разрешению изображения. Элемент results(i,j) равен k, если в построенном изображении пиксель (i, j) взят из исходного изображения номер k.

Рекомендации по выполнению задания

  1. Обратите внимание на область применимости алгоритма.
  2. При тестировании алгоритма необходимо следить за следующим:
    • после каждого применения разреза графа общая энергия не возрастает;
    • значение энергии, выдаваемое функцией graphCutMex, совпадает со значением энергии, подсчитанным независимой процедурой.
  3. Обратите внимание, что для достижения хорошего качества решения задачи склеивания, возможно придется изменить интерфейс, выданный в задании. При использовании измененного прототипа ОБЯЗАТЕЛЬНО нужно прислать и функцию, согласованную с выданным прототипом.

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

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

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

Выполненный вариант задания необходимо прислать письмом по адресу bayesml@gmail.com с темой «[ГМ14] задание 3, вариант X, фамилия». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Новые версии будут рассматриваться только в самом крайнем случае. Также убедительная просьба строго придерживаться заданной выше спецификации реализуемых функций. Очень трудно проверять большое количество заданий, если у каждого будет свой формат реализации.

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

  • PDF-файл с описанием проведенных исследований (отчет должен включать в себя описание выполнения каждого пункта задания с приведением соответствующих графиков, изображений, чисел)
  • Все исходные файлы, реализованные в рамках настоящего задания. Убедитесь, что Ваши файлы работают и соответствуют прототипам!
  • Не менее двух склеенных изображений и соответствующих им наборов исходных.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29/2014/%D0%97%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5_3»
Личные инструменты