Задание 3. Алгоритм компенсации движения

Начало: 23 февраля 2012 года
Конец: 04 марта 2012 года

Цель задания

Необходимо написать фильтр к VirtualDub, который умеет, получая на вход параметр скорости, находить вектора движения в фильме, используя рассмотренные на лекции алгоритмы (Cross search, orthogonal search, TSS, FSS, spiral search, hierarchical search) и ваши собственные идеи.

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

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

Замер будет проводиться в двух номинациях:

  • (основная) Поиск с пиксельной точностью и поиск с полупиксельной точностью с блоками 16х16.
  • (также теперь обязательная) Поиск с полупиксельной точностью с использованием блоков 8х8.

Все результаты (с фамилиями авторов) будут сведены на двумерные графики - качество/время работы фильтра, где ваши результаты будут в виде параметрических кривых (параметр - параметр фильтра по скорости).

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

Фильтры для разных номинаций необходимо делать в отдельных файлах и называть их по разному. Это означает, что если кто-то сделает один фильтр, который при каких-либо настройках использует блоки 8х8, то этот фильтр будет сравниваться только во второй номинации.

Тестовые фильмы можно скачать по следующим ссылкам:

Также рекомендуется использовать свои собственные фильмы. Имейте ввиду, что после DivX - вы будете в основном находить вектора те же, что уже нашел DivX, а проверяться все будет на "чистых", не испорченных кодеками последовательностях.

Чтобы свести к минимуму ваши затраты времени на освоение написания видео-фильтров, вам будет предоставлена "болванка" (ссылка в начале задания) - фильтр, умеющий:

  • Искать моушн-вектора методом полного перебора.
  • Считать длину всех моушн-векторов и "ошибку" для каждого вектора, а также для кадра в целом, в т.ч. сбрасывая их в лог-файл.
  • Показывать исходное видео, скомпенсированное видео, межкадровую разницу и моушн-вектора.
  • Готовить изображения для пиксельного и полупиксельного поисков, грамотно заполняя все за краями изображения.
  • Быстро (в т.ч. с использованием MMX) считать SAD (сумму абсолютных разностей). Т.е. самая медленная часть алгоритма уже будет на MMX и вам надо только саму стратегию выбора блоков правильно отладить. (основная) Поиск с пиксельной точностью и поиск с полупиксельной точностью.

Т.е. все, что вам надо, это заменить в этом фильтре процедуру полного перебора своим алгоритмом и получить отличный результат.

ИЗМЕНЯТЬ В БОЛВАНКЕ ЛЮБОЙ КОД, НЕ КАСАЮЩИЙСЯ АЛГОРИТМА ПОИСКА НЕЛЬЗЯ!

Также фильтр ОБЯЗАТЕЛЬНО должен быть подписан так, чтобы ваша фамилия показывалась в списке фильтров (см. строку "PUT YOUR NAME HERE" в коде). Это заметно уменьшит шанс, что вас с кем-то перепутают. :)

И еще - код болванки позволит использовать ее с механизмом JOB-ов, т.е. делать прогоны в автоматическом режиме. Необходимо, чтобы ваш фильтр позволял также работать с теми же JOB файлами. (Примеры будут выложены). Это делается, чтобы существенно сократить время проверки.

Фильтр-"болванка" работает с VirtualDub, соответственно у вас не будет проблем с чтением любых стандартных AVI файлов, записью скомпенсированных файлов и т.п.

Скачать "болванку" можно с помощью ссылки в верхней части страницы.

Настоятельно рекомендуется использовать следующие возможности VD для отладки:

  • Выбрать какой-то кадр с характерным движением в тестовой последовательности, и сохранять его скомпенсированный вид (Ctrl-2) в отдельный слой изображения в Photoshop (Ctrl-N - создать изображение в первый раз; если кадр был в буфере, новое изображение будет его размера и Ctrl-Ins - вставить слой). Переключение между слоями поможет вам лучше понимать, что происходит в алгоритме при вносимых изменениях.
  • Также рекомендуется сохранять логи качества работы фильтра при его изменении, а потом визуализировать их в Excel или MathCad. При этом, если у вас какой-то кадр или какой-то фильм резко просядет при изменении алгоритма - вы это сразу увидите. И дальше уже сможете предметно с ним разобраться, бага это или фича. :) (Такой подход в разы быстрее просмотра "глазами", особенно когда основные баги будут вычищены и уже пойдет "отладка и заточка").

Базовый размер блока - 16х16 пикселов.

Оптимальную максимальную длину моушн-векторов требуется определять самим.

Зависимости от параметра скорости/качества делайте в виде порогов, по которым вы перестаете искать дальше.

За первое место (после собеседования по алгоритму) - большие дополнительные баллы.

За второе и третье место - дополнительные баллы.

Для в своем алгоритме рекомендуется использовать следующие методы:

  • Используйте комбинацию из нескольких простых методов поиска (в т.ч. спирального).
  • Используйте найденные вектора в соседних блоках и в предыдущем кадре для начальных приближений в новом блоке.
  • Определяйте "на лету" оценку сдвига объектов для того, чтобы не проверять "сильное движение" в тех ОБЛАСТЯХ кадров и тех КАДРАХ, где его нет.
  • Наилучший результат по качеству будет при грамотном использовании полупиксельной точности при минимальном числе дополнительных замеров.
  • Используйте такой параметр, как "среднее количество замеров на кадр", самостоятельно сбросьте его в лог и оптимизируйте.

Общий рекомендуемый порядок действий такой. Реализуйте простую стратегию и зависимости от порогов. Добейтесь, чтобы у вас заработало большее-меньшее ускорение в зависимости от параметра качества. Добейтесь, чтобы алгоритм всегда находил достаточно адекватные блоки по сравнению с полным перебором. И далее доведите алгоритм, проанализировав тонкие места статистикой по кадрами и фильмам.

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

ВНИМАНИЕ! Письменного экзамена по курсу нет. Т.е. необходимо набрать необходимое количество баллов для положительной оценки.

Литература

  1. Описание можно найти в материалах лекций.
  2. VirtualDub доступен на: http://www.virtualdub.org
  3. Программа для измерения PSNR: исполняемый файл и исходный код.

Требования к фильтру

Главное требование - выполнить обязательную часть задания.

Язык реализации - С или С++.

Программа должна быть написана с использованием тестового примера.

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

Программа должна устойчиво работать с фильмами с размерами, кратными 16.

Фильтр должен называться motion_YOUR_SURNAME.vdf, чтобы можно было тестировать несколько фильтров одновременно. В названии фильтра обязательно должна быть указана ваша фамилия и номер группы.

Требования к программе

Главное требование - выполнить обязательную часть задания.

Язык реализации – С или С++

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

Программа должна устойчиво работать с файлами большого размера. Т.е. если
программе на вход дать файл размером 10Мб, то на Pentium4-1700 она должна
отработать за 3 минуты, не упасть и корректно распаковать архив.
Внимательно изучите требования к
сдаваемым работам
на сайте. В частности 0 баллов ставится, если вы
забудете исходные тексты.
Оформление работы
Правила организации ZIP-архива, который вы посылаете как результат вашей работы
по заданию, четко определены.

Структура следующая:
readme.txt

bin
  yourprogname.exe
    ...
 src
yoursource.cpp yoursource.h ...
В корневом каталоге архиве должен быть файл readme.txt и два подкаталога: exe

и src. Оба подкаталога могут в свою очередь содержать подкаталоги.

В каталоге exe должны находится все исполняемые файлы (обычно один) и
необходимые файлы данных (Проверьте, чтобы программа работала при запуске не
из среды программирования! А еще лучше - на другой машине)
Подкаталог src должен содержать все исходные коды ваших программ и все
необходимое для компиляции программы. Но не включайте в архив файлы,
генерируемые вашим компилятором!

Если вы пользуетесь Microsoft Visual C++ 5.0/ 6.0, то в каталог srс обычно
достаточно положить файлы *.cpp, *.h, *.dsw, *.dsp, *.res, *.rc, *.ico, *.rc2 с
сохранением подкаталогов. Подкаталоги Release и Debug не нужны: вашу
скомпилированную программу нужно скопировать в каталог exe вашего архива. Как
правило, архив не должен занимать более 300-500 килобайт.
За нарушение данных требований и, следовательно, усложнение работы проверяющих
будет сниматься 1 балл.

Файл readme.txt должен быть текстовым файлом в любой кодировке. Не нужно
присылать файлы в формате MS Word или HTML. Для создания файла нужен только
Notepad.
Формат файла такой:

ФИО: [Фамилия Имя Отчество]Группа: [номер группы]

Задание: [ номер задания] / [название задания]
подзадание 1: [[+/-]]
подзадание 2: [[+/-]]
...
подзадание M: [[+/-]]

Система: [система программирования]
ОС: [операционная система]
Аппаратура: [конфигурация машины]

Комментарии: [комментарии по реализации / пожелания и т.д.]

Подзадания указаны в формулировке задания. В файле readme.txt вы должны
указать те из них, которые вы реализовали [+] или не реализовали [-], по вашему
мнению. В поле "Аппаратура" указывайте конфигурацию машины, на
которой выполнялась работа. Внимательно заполняйте файл, - это поможет
проверяющему более оперативно проверить вашу работу,а также в случае каких-либо
недоразумений.
Вот пример правильного оформления файла readme.txt

ФИО: Иванов Василий ПетровичГруппа: 203

Задание: 1 / Универсальный архиватор файлов
база: [+]
PPM1: [-]
PPM2: [+]

Система: MS VC++
ОС: Windows 2000
Аппаратура: PIII-866, 512Mb, NVidia GeForce2 Pro 64Mb

Комментарии: Дополнительно реализован новый изобретенный мной метод
сжатия файлов

 

НЕ ЗАБУДЬТЕ ПОЛОЖИТЬ В АРХИВ файл readme.txt.
Для сдачи работы необходимо зарегистрироватся в системе.

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