Обработка видео: алгоритм компенсации движения

Автор задания:
Дмитрий Ватолин

Скачать болванку (135Kb)

Цель задания

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

Результат будет оцениваться в 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 пикселов.

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

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

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

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

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

Литература

  1. Описание можно найти в материалах лекций.
  2. Подборка статей по методам компенсации движения доступна на
    http://library.graphicon.ru:8080/catalog/276

    Если вы найдете еще хорошие статьи - пожалуйста сообщайте, мы их добавим!!! Присылать ссылки можно на адрес задания!

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

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

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

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

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

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

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

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

Оформление

Оформление практического задания подробно описано в правилах курсов

Результаты работы

Результаты работы будут опубликованы на сайте в течение трех дней после окончания срока выполнения задания.

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