Разделы

Вход в систему

Сейчас на сайте

Сейчас на сайте 0 users и 0 гостя.

Рейтинг@Mail.ru Rambler's Top100

Главная

Задание 1. Минимизация энергии с помощью разрезов графа.

Авторы: Ольга Баринова,
Глеб Кривовязь,
Михаил Синдеев,
Рамиз Зейналов

Начало: 3 октября 2009
Конец: 18 октября 2009 (23:59)

Цель задания

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

Описание задания

Данное задание предполагает применение метода разрезов графа к задаче восстановления изображений. Алгоритм принимает на вход зашумленное изображение и возвращает восстановленное. Примеры исходного, зашумленного и восстановленного изображений приведены на Рис. 1.


Рис. 1. Пример работы алгоритма восстановления изображений

Изображение представляется в виде графа-решетки. Задача восстановления изображения подразумевает разметку графа на множество классов (каждый класс соответствует определенному цвету) и формулируется в терминах минимизации энергии на графе. Поскольку классов более двух, необходимо пользоваться итерационными алгоритмами (альфа-расширение, альфа-бета-замена). Реализовывать эти алгоритмы самостоятельно не требуется, к заданию прилагается готовая реализация в виде MEX-функции, которую можно вызвать из MATLAB.

Минимизируемая энергия имеет следующий вид:
E(F)=\sum\limits_{p \in P} R_p(F_p)+\sum\limits_{(p,q) \in N} V_{p,q}(F_p,F_q)
Примеры возможных унарных и бинарных потенциалов:
R_p(F_p)=\displaystyle\frac{(F_p-I_p)^2}{\sigma^2}

R_p(F_p)=\displaystyle\frac{\lvert F_p-I_p \rvert^2}\sigma

R_p(F_p)=\displaystyle\frac{(F_p-I_p)^2}{(F_p-I_p)^2+\sigma^2}

V_{p,q}(F_p,F_q)=\lambda(F_p-F_q)^2

V_{p,q}(F_p,F_q)=\lambda \lvert F_p-F_q \rvert

В приведенных формулах $ I $ – входное (зашумленное) изображение, $ F $ – выходное. Унарный потенциал отвечает за похожесть выходного изображения на исходное, бинарный – за гладкость выходного изображения.

Входными данными в задании являются три набора изображений. В каждом наборе изображения зашумлены определенным видом шума (равномерный, гауссов, импульсный). Необходимо предложить по алгоритму (т.е. комбинацию потенциалов функции энергии и весов) для каждого набора. Можно использовать приведенные выше примеры потенциалов, а также экспериментировать с собственными. Как объективную метрику качества восстановленных изображений можно использовать метрику PSNR (исходные изображения прилагаются), однако при проверке в первую очередь будет учитываться визуальное качество получаемых результатов.

Задание делится на основную и дополнительную часть. Основная часть обязательна для выполнения, дополнительная является бонусом.

В основной части предлагается использовать простой вариант восстановления цветных изображений: каждый цветовой канал рассматривается независимо, а в качестве меток, присваиваемых пикселям восстанавливаемого изображения, используются равномерные градации значений из соответствующего канала. Число меток может варьироваться, однако следует помнить, что увеличение числа меток влечет увеличение расхода памяти и снижает скорость работы алгоритма. Рекомендуемые значения: N = 10…40 меток.

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

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

Задание выполняется в среде MATLAB.

Алгоритмы должны быть оформлены в виде единой функции Restore(), имеющей следующий интерфейс:

RestoredImage = Restore(NoisyImage, noise, method), где:

  • NoisyImage - матрица зашумленного изображения (уже загруженная, а не путь к файлу!)
  • RestoredImage – матрица восстановленного изображения
  • noise – параметр-строка со следующими возможными значениями: ‘uniform’, ‘gaussian’, ‘impulse’, задающими алгоритм восстановления, используемый для данного типа шума
  • method – параметр-строка, принимающий значения ‘simple’ либо ‘adaptive’ в зависимости от того, какой вариант выбора меток используется. Если дополнительная часть не реализована, то при использовании параметра ‘adaptive’ программа должна выдавать предупреждение и продолжать работу в режиме ‘simple’

Работа должна быть оформлена в виде ZIP-архива, содержащего:

  • Файл Report.doc, в котором указаны ФИО сдающего, а также краткие комментарии по работе:
    • какие функционалы, веса и итерационные алгоритмы использовались и почему
    • какие получены результаты и сделаны наблюдения
    • каким способом реализовано адаптивное определение меток (если выполнена дополнительная часть)
    • произвольные комментарии по работе (если необходимо)
  • Файл Restore.m, содержащий функцию Restore
  • Вспомогательные MATLAB-скрипты, если необходимо (GCMex присылать не нужно!)

Исходные данные

  • MEX-функция (см. комментарии в файле GCMex.m), выполняющая минимизацию энергии с помощью одного из итерационных алгоритмов.
    ВНИМАНИЕ: В комментариях в файле GCMex.m есть опечатка: первый параметр должен быть размера Nx1, а не 1xN. То же касается и выходного параметра.
    Пример использования см. в GCMex_test.m.
  • Тестовый набор изображений.
  • Скрипт для вычисления схожести двух изображений по метрике PSNR.

Вопросы

Вопросы по заданию можно задать либо на очередной лекции, либо на форуме.

© Лаборатория компьютерной графики при ВМиК МГУ