Motion Information Challenge
Проводится MSU Graphics & Media Lab

Новый конкурс

Сейчас прводится новый конкурс
Конкурс программ обработки видео и плагинов к ним

Idea

Соревнование закончилось 25 ноября 2002 года.
Победил студент 3-го курса Денис КУБАСОВ!

Однако, вы можете пробовать свои силы! :) Берите те же примеры и пробуйте! Ваша задача достичь ускорения как минимум в 50 раз без существенной потери точности.

ОСНОВНАЯ СУТЬ: Построить наилучший алгоритм поиска информации о сдвиге блоков в кадрах фильма. Алгоритм должен работать как можно быстрее и как можно реже находить неоптимальные блоки. 

ПОДРОБНЕЕ: Кадр бьется на блоки 16х16 и для каждого блока надо найти в предыдущем кадре наиболее похожий на него в окрестности +/- 32 пиксела по обеим координатам. 


ЭТАПЫ: 

* Этап 0. Сначала пишется простая программа, осуществляющая поиск сдвинувшихся блоков методом полного перебора. Это необходимо, чтобы вы не решали повторно технические задачи типа чтения AVI, вырезания блока, подсчета расстояний между ними, визуализации, замера времени и т.п. 

* Этап 1. Эта программа раздается всем, желающим померяться силами. Дается 2 недели на создание алгоритма. После чего подводятся предварительные итоги. Поединок у нас вежливый и открытый. :) Поэтому, помимо обмена рукопожатиями, далее происходит обмен исходными текстами! После чего дается еще 5 дней на доводку программы. Поскольку у вас все равно будут разные технические решения, то обмен позволит победить наиболее гибкому из них (далеко не все решения можно скрестить). 

* Этап 2. Программы приводятся к единому знаменателю по техническим и проводится окончательные замеры. 

Example

В качестве базы выбрана программа VirtualDub (в которой, к слову, готовится 99% фильмов в DivX - вы можете попробовать поискать в своих коллекциях сигнатуру "VirtualDub").

По адресу http://compression.graphicon.ru/video/challenge/virtualdub.rar (709К) - лежит программа VirtualDub с установленным тестовым фильтром. Она не требует инсталляции - т.е. можете скачать ее, выбрать фильтр Cool Motion Estimation (название авторское - Дениса Кубасова :) и смотреть, как он работает на своих любимых фильмах.

Если кого-то пугает сложность задачи - то размер этого исходных текстов фильтра 16Кб вместе с той частью, которая отвечает за менюшки и т.п. В ней затрудительно заблудиться. :-) Исходные тексты фильтра приведены ниже - можете брать и пробовать!

Prize

Победителю установлен приз - книга "The Software Optimization Cookbook" издательства Intel Press: http://www.intel.com/intelpress/swoptcookbook/ 

В этой "Поваренной книге оптимизации программ" рассказывается обо всех основных методах оптимизации. Начиная от оптимизации циклов и переходов, рассматривая векторные операции (MMX, SEE), оптимизацию под размер кэша процессора и заканчивая сравнительно новыми вещами типа Branch optimization, multi-thread optimization и т.д. 

Многие примеры даны на основе Intel VTune Performance Analyzer 6.0 (фактически лучшего профилировщика на сегодня) и Intel C++ Compiler (лучшего компилятора для высокоскоростных приложений для процессоров Intel - оптимизирует в том числе и под Itanium). Материал свежий - весны этого года. 

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

Из забавного: как в нормальной кулинарной книге ("Cookbook") в конце каждой главы (где голова работает похуже) приведен рецепт приготовления чего-либо. :) Например, цыпленка, или коктейля. 

Цена книги по каталогу, 50$. Впрочем, как вы можете посмотреть по ссылкам те, кто не займут первого места смогут заказать ее за 38$ или даже 36$ (хотя с пересылкой будет заметно дороже). (Ну или попросить почитать у того, кто выиграет :))). 

Почему именно эту книгу? 

  1. Во-первых, тот, кто сможет лучше всех алгоритмически ускорить алгоритм явно будет достоин такой книги. 
  2. Во-вторых, прочитав ее, победитель сможет еще в 1.5-2 раза ускорить программу. :) Уверяю вас, оптимизация под процессор может дать и больше. 

Rules

ИЗМЕРЯТЬСЯ БУДЕТ: 
  1. Скорость работы программы за вычетом времени чтения файла, отрисовки векторов и т.п.
  2. То, насколько выросло расстояние (в мере - сумма абсолютных разностей) по сравнению с полным перебором. 
Требуется реализовать 3 режима работы программы - Fast, Normal, Slow - которые будут регулировать точность/скорость. Наилучший результат будет у того, чей график в координатах (Скорость, мера расстояния) будет ближе к центру координат. 

Подробнее можно посмотреть исходные тексты примера, реализующего полный перебор. Результат значения метрики для каждого кадра сохраняется в csv файл, который можно открыть в Excel, MatLab или MatCad и проанализировать (где вы больше всего потеряли по сравнению с полным перебором, например.... и задуматься почему... :).

ДОПОЛНИТЕЛЬНЫЕ УСЛОВИЯ: 

  1. MMX Ассемблер в основном коде использовать нельзя. Задача - выяснить кто умеет лучше создавать алгоритмы, а не лучше знает технологии. 
  2. Интеловский компилятор использовать можно. 
Дополнительным критерием (в случае близости основных результатов) будет средняя длина всех найденных векторов смещения блоков. Это нужно, чтобы вы в алгоритме учитывали увеличение разброса значений векторов на зашумленных фильмах и боролись (хотя бы простыми способами) с этим. Если бы этого не делалось в приведенном выше примере, то вектора "фона" (стен комнаты) были бы существенно больше по длине ("гуляли" бы).
  • С точки зрения общей математики - это задача поиска минимума функционала. 
  • С точки зрения математической кибернетики - это задача сокращения перебора.
  • С точки зрения маш. графики - это задача поиска движения (motion estimation). 
    • Действуйте! :) Победитель получит возможность участвовать в гранте Самсунг по обработке видео. 

    Deadline

    • Окончание первого этапа (предоставить работющий фильтр и его исходные тексты):

      • 20 ноября (среда)
    • Окончание второго этапа (окончательные варианты фильтров):

      • 25 ноября (понедельник)

      Все результаты высылаются Дмитрию Ватолину по адресу dmitriy____graphics_cs_msu_su с пометкой "Challenge"

    Addional Information

    Вашим коллегой-третьекурсником Сергеем Гришиным позавчера подготовлены индексы статей по компенсации движения: http://compression.graphicon.ru/download/video_motioninfo.html

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

    Download

    Исходные тексты: 

    По адресу http://compression.graphicon.ru/video/challenge/virtualdub.rar (709К) - лежит программа VirtualDub с установленным тестовым фильтром. Она не требует инсталляции - т.е. можете скачать ее, выбрать фильтр Cool Motion Estimation и посмотреть, как он работает. Подробнее о создании фильтров под VirtualDub можно почитать по адресу http://www.virtualdub.org/.

    Тестовые последовательности: 

    • Пробовать можно на части последовательности "Сюзи" susi_small1.avi (96K) 
    • Для тех, у кого нет DivX - можно скачать несжатую еще более   короткую последовательность с susi_small1_uncompressed.rar (358K)
    • Для тех, кто намерен экспериментировать серьезнее susi_small2.avi (1.5M)

    Если есть вопросы - спрашивайте!

    Если вас не испугала постановка задачи - ВПЕРЕД! 

    Кому не слабо сразиться? :-)
     

    Let's go!