Компенсация движения

Компенсация движения

Компенсация движения (англ. Motion Compensation) — один из основных алгоритмов, применяемых при обработке и сжатии видеоданных. Алгоритм использует похожесть соседних кадров в видео последовательности и находит векторы движения отдельных частей изображения (обычно блоков 16x16 и 8x8). Использование компенсации позволяет при сжатии многократно увеличить степень сжатия за счет удаления избыточности в виде совпадающих частей кадров. Используется не только при сжатии, но и при фильтрации видео, изменении частоты кадров и т.д.

Содержание

Идея алгоритма

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

  • Размер кадра: 720x576 (Стандартный размер для Европейского телевидения (PAL), 414720 пикселей)
  • Частота кадров: 25 к/сек (Также стандартно для PAL)
  • Цветопредставление: YV12 (YUV 4:2:0) (16 бит на 4 пикселя + 8 бит на каждый = 12 бит на пиксель)

В итоге на запись или передачу одной секунды такого видео без применения сжатия потребуется 14,8 мегабайта без учета звука и служебной информации. Для хранения полуторачасового фильма уже будет нужно 78 (!) гигабайт.

Практически в любом видео соседние кадры похожи, имеют общие объекты, которые, как правило, смещаются друг относительно друга. И совершенно естественно желание закодировать видео так, чтобы объекты не кодировались многократно, а просто описывались некоторые их смещения.

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


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

Пример работы алгоритма

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

1. Загружается текущий кадр.
2. Кадр делится на блоки (например 16x16).

Поделенный на блоки кадр


3. Производится обход блоков (каждый блок в данном случае обрабатывается отдельно).
4. При счете одного блока производится обход некоторой окрестности блока в поиске максимального соответствия изображению блока на предыдущем кадре в пределах этой окрестности.

Наглядная иллюстрация поиска: изображен предыдущий кадр (тот в котором производится поиск) и три блока нового кадра, который мы хотим приблизить фрагментами предыдущего


5. Таким образом, после завершения поиска мы получаем набор векторов, указывающий "движение" блоков изображения между кадрами. Эти векторы могут быть естественным образом использованы для создания изображения скомпенсированного кадра, который лучше приближает кадр для которого производилась компенсация движения.

Здесь показан скомпенсированный кадр с векторами движения для каждого блока (точка - это нулевой вектор)


Как видно, разность между скомпенсированным кадром и текущим значительно меньше, чем между нескомпенсированными кадрами


Проблемы реализации

Первый вопрос, который возникает при написании алгоритма компенсации движения: "Как оценивать "похожесть" фрагментов изображения?"
Вариантов может быть несколько:

  • Вычисление SSD (суммы квадратичных отклонений). Для пары блоков дает хорошие результаты по качеству (особенно при эталонных тестах, так как метрика PSNR (вычисляется на основе среднего квадратичного отклонения) наиболее распространена), но требует значительных затрат ресурсов (умножение операция медленная, даже таблица квадратов не сильно ускоряет процесс) и сильно чувствителен к изменению яркости. Чем меньше SSD - тем больше похожи блоки.
  • Сравнение по характерным точкам. Может выполняться очень быстро (за счет обхода лишь небольшого числа точек), но может очень плохо коррелировать с более качественными метриками.
  • Вычисление SAD (суммы абсолютных разностей). Выполняется за разумное время и дает приемлемый результат по качеству (но имеет низкую устойчивость к шуму). Реально применяется и имеет хорошие скоростные показатели за счет использования SIMD расширений (которые позволяют выполнять множество вычитаний одновременно без использования "интеллектуальных" средств процессора по распараллеливанию вычислений).

Наиболее часто используется вычисление SAD. Второй вопрос более сложный: "Как искать нужный блок?"

  • Полный перебор (Full Search). В некоторой области вокруг обрабатываемого блока происходит перебор координат искомого блока. Если имеем блок 16x16 и область поиска ±32 x ±32, то нам нужно будет 4096 раз посчитать SAD для каждого обрабатываемого блока. Это медленно, но дает гарантированно лучший результат по заданной метрике.
  • Поиск по шаблону. Выполняется быстро, дает не лучшие результаты. (Будет рассмотрен более подробно)
  • Спиральный поиск. Считается, что чем ближе блок к текущему, тем больше вероятность того, что он искомый. И его точность уменьшается от центра к краям области поиска. Имеет дополнительное преимущество. На картинке (в этой статье) с векторами движения видны длинные векторы на небе, так как использовался полный перебор начиная с левого верхнего угла области поиска, хотя очевидно, что с нулевыми векторами нет практически никакой разницы, но длинные векторы ухудшают сжимаемость поля векторов, а нулевые векторы нет. При спиральном поиске на неизменных участках всегда стоят нулевые векторы.

Пример реализации

Реализация метода полного перебора на C++

void ME (BYTE* CurrentFrame, BYTE* PreviousFrame, int Width, int Height, MV *MotionVectors)
{
        int BlocksPerHeight = (Height + 15) >> 4; //Число блоков по вертикали
        int BlocksPerWidth  = (Width  + 15) >> 4; //Число блоков по горизонтали
 
        int VerticalOffset, HorizontalOffset, TempOffset;  //Смещения
        int OffsetPerLine = Width + Border * 2;            //Смещение на одну строку
        int StartOffset = OffsetPerLine * Border + Border; //Начальное смещение
        BYTE *CurrPtr, *PrevPtr; //Указатели на предыдущий и на следующий кадры
 
        MV ProbMV;            //Пробный вектор
        long MinError, Error; //Значения погрешности
 
        for (int i = 0; i < BlocksPerHeight; i++)
        {
                for (int j = 0; j < BlocksPerWidth; j++)
                {
                        //Вычисляем смещения
                        VerticalOffset = (i << 4) * OffsetPerLine + StartOffset;
                        HorizontalOffset = (j << 4);
                        //Устанавливаем смещения на текущий блок
                        CurrPtr = CurrentFrame  + VerticalOffset + HorizontalOffset;
                        PrevPtr = PreviousFrame + VerticalOffset + HorizontalOffset;
                        MinError = MAXLONG; //Считаем ошибку очень большой
 
                        for (int y = -MaxMotion; y < MaxMotion; y++ )
                        {
                                TempOffset = y * OffsetPerLine; //Экономим на умножениях
                                for (int x = -MaxMotion; x < MaxMotion; x++ )
                                {
                                        //GetError - функция сравнения блоков, например, SAD
                                        Error = GetError (CurrPtr, PrevPtr + TempOffset + x, OffsetPerLine);
                                        //Новый кандидат :)
                                        if (Error < MinError)
                                        {
                                                ProbMV.x = x;
                                                ProbMV.y = y;
                                                MinError = Error;
                                        }
                                }
                        }
                        //Записываем полученный вектор :)
                        MotionVectors [i * BlocksPerWidth + j] = ProbMV;
                }
        }
}

В новом стандарте MPEG-4 AVC/H.264 введены также не квадратные (прямоугольные) блоки, размер которых может дробиться до 4х4 пикселя. Таким образом удаётся весьма эффективно использовать похожесть соседних кадров, а благодаря более сложной форме блоков возрастает точность компенсации движения на границах движущихся объектов. Кроме компенсации движения для дальнейшего уточнения изображение (или для вновь появляющихся областей, которых не было в прошлых кадрах) используется сжатие межкадровой информации и независимое сжатие блоков.

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

См. также

Ссылки

  • Temporal Rate Conversion (англ.) — Статья о компенсации движения на сайте Microsoft.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Компенсация движения" в других словарях:

  • компенсация движения в телевизионном изображении — Определение величины смещения точки фрагмента телевизионного изображения в текущем кадре по отношению к тем же точкам фрагмента из предыдущего кадра и перемещение их в соответствующие точки текущего кадра. [ГОСТ Р 52210 2004] Тематики телевидение …   Справочник технического переводчика

  • компенсация движения в телевизионном изображении — 53 компенсация движения в телевизионном изображении: Определение величины смещения точки фрагмента телевизионного изображения в текущем кадре по отношению к тем же точкам фрагмента из предыдущего кадра и перемещение их в соответствующие точки… …   Словарь-справочник терминов нормативно-технической документации

  • Компенсация движения в телевизионном изображении — 1. Определение величины смещения точки фрагмента телевизионного изображения в текущем кадре по отношению к тем же точкам фрагмента из предыдущего кадра и перемещение их в соответствующие точки текущего кадра Употребляется в документе: ГОСТ Р… …   Телекоммуникационный словарь

  • Компенсация — Компенсация  (от лат. compesatio  «возмещение») Денежные компенсации Возмещение ущерба; Вознаграждение за неиспользованное право; Способ погашения обязательств путём зачета встречных требований должника и кредитора; Выдача денежных …   Википедия

  • Торсионные Движения — (от фр. torsion скручивание) вращательные движения глаз вокруг зрительных осей, за счет которых происходит, например, компенсация зрительного образа при боковых наклонах головы …   Психологический словарь

  • торсионные движения глаз — Этимология. Происходит от фр. torsion скручивание. Категория. Форма движений глаз. Специфика. Вращательные движения вокруг зрительных осей, за счет которых происходит, например, компенсация зрительного образа при боковых наклонах головы.… …   Большая психологическая энциклопедия

  • Череспериодная компенсация — (ЧПК)         метод выделения отражённых от цели радиосигналов на фоне пассивных радиолокационных помех (См. Радиолокационные помехи), основанный на использовании различия скоростей движения цели и источника помех. Применяется в когерентно… …   Большая советская энциклопедия

  • H.264/MPEG-4 AVC — H.264, MPEG 4 Part 10, или AVC ( Advanced Video Coding ) стандарт сжатия видео, предназначенный для достижения высокой степени сжатия видеопотока при сохранении высокого качества. Он был создан ITU T Video Coding Experts Group (VCEG) совместно с… …   Википедия

  • H.264 — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. H.264 …   Википедия

  • AVC — H.264, MPEG 4 Part 10 или AVC (Advanced Video Coding)  стандарт сжатия видео, предназначенный для достижения высокой степени сжатия видеопотока при сохранении высокого качества. Содержание 1 О стандарте 2 Возможности 3 Недостатки …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»