|
Скачать болванку (135Kb)
Необходимо написать фильтр к VirtualDub, который умеет, получая на
вход параметр скорости, находить вектора движения в фильме, используя
рассмотренные на лекции алгоритмы (Cross search, orthogonal search,
TSS, FSS, spiral search, hierarchical search) и ваши собственные идеи.
Результат будет оцениваться в 2 координатах - скорость и качество,
задача - достичь как можно лучшего их соотношения (т.е. ваша линия на
графике должна пройти выше - в качестве примера оценки по 2
параметрам смотрите результаты проверки фрактального сжатия).
Мерой качества будет служить PSNR (метрика, обратно пропорциональная
среднеквадратичному отклонению пикселов) для скомпенсированного кадра.
Качество в цветовых компонентах будет учитываться в средневзвешенной
оценке.
Замер будет проводиться в двух номинациях:
-
(основная) Поиск с пиксельной точностью и поиск с полупиксельной
точностью с блоками 16х16.
-
(дополнительная) Поиск с четвертьпиксельной точностью и поиск с
использованием блоков 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 пикселов.
Оптимальную максимальную длину моушн-векторов требуется определять
самим.
Зависимости от параметра скорости/качества делайте в виде порогов, по
которым вы перестаете искать дальше.
За первое место (после собеседования по алгоритму) - большие
дополнительные баллы.
За второе и третье место - дополнительные баллы.
Для в своем алгоритме рекомендуется использовать
следующие методы:
-
Используйте комбинацию из нескольких простых методов поиска (в т.ч.
спирального).
-
Используйте найденные вектора в соседних блоках и в предыдущем
кадре для начальных приближений в новом блоке.
-
Определяйте "на лету" оценку сдвига объектов для того, чтобы не
проверять "сильное движение" в тех ОБЛАСТЯХ кадров и тех КАДРАХ,
где его нет.
-
Наилучший результат по качеству будет при грамотном использовании
полупиксельной точности при минимальном числе дополнительных
замеров.
-
Используйте такой параметр, как "среднее количество замеров на
кадр", самостоятельно сбросьте его в лог и оптимизируйте.
Общий рекомендуемый порядок действий такой. Реализуйте простую
стратегию и зависимости от порогов. Добейтесь, чтобы у вас заработало
большее-меньшее ускорение в зависимости от параметра качества.
Добейтесь, чтобы алгоритм всегда находил достаточно адекватные блоки
по сравнению с полным перебором. И далее доведите алгоритм,
проанализировав тонкие места статистикой по кадрами и фильмам.
Выполнение данного задания позволяет получить баллы, необходимые для
получения высокой оценки за курс.
ВНИМАНИЕ! Баллов, набираемых на экзамене (письменном) по курсу будет
недостаточно для положительной оценки. Т.е. необходимо выполнить
УСПЕШНО хотя бы одно задание.
-
Описание можно найти в материалах лекций.
-
Подборка статей по методам компенсации движения доступна на
http://library.graphicon.ru:8080/catalog/276
Если вы найдете еще хорошие статьи - пожалуйста сообщайте, мы
их добавим!!! Присылать ссылки можно на адрес задания!
-
VirtualDub доступен на:
http://www.virtualdub.org/
-
Программа для измерения PSNR доступна в библиотеке:
исполняемый файл и
исходный код
Главное требование - выполнить обязательную часть задания.
Язык реализации - С или С++.
Программа должна быть написана с использованием тестового примера.
За использование чужих исходных текстов или совместное написание - программы
всех участников будут сниматься с замеров, и будет выставляться 0 баллов. В
качестве альтернативы желающим все-таки получить высокую оценку будет
предложено реализовать более сложный алгоритм.
Программа должна устойчиво работать с фильмами с размерами,
кратными 16.
Внимательно изучите требования к
сдаваемым работам на сайте. В частности 0 баллов ставится, если вы
забудете исходные тексты.
Фильтр должен называться motion_YOUR_SURNAME.vdf, чтобы можно
было тестировать несколько фильтров одновременно. В названии фильтра
обязательно должна быть указана ваша фамилия и номер группы.
ZIP-архив с исходными текстами и исполняемыми файлами, названный
по схеме GGG_Z_V_nnnnnnnn.zip (где G - трехзначный номер группы, Z - номер
задания, V - номер версии задания, nnnnnnnn - номер студенческого билета)
присылайте на 
Например, студент 306 группы с номером студенческого билета 05015042, сдающий
обновленную (вторую) версию программы по первому заданию, должен прислать архив
с именем 306_1_2_05015042.zip.
Также смотрите здесь, какие файлы
нам присылать и как их оформить.
НЕ ЗАБУДЬТЕ ПОЛОЖИТЬ В АРХИВ файл readme.txt.
|
