Жизнь в движении, Motion Estimation Library (часть первая, про заводную рыбу)

Признайтесь, вы же обожаете смотреть разные сериалы, голливудские блокбастеры и прочие бестселлеры? Все эти угрюмые доктора, оставшиеся в живых в знойной калифорнии среди отчаянных домохозяек? Все мы в той или иной степени наркоманы, подсаженные на иглу важнейшего из искусств. И привыканию немало способствуют такие блага цивилизации как многомегабитные каналы, многотерабайтные винчестеры, многодюймовые экраны и многоядерные процессоры, ага. По 500 Mb на серию – какой же, право, пустяк. Хотя еще 10 лет назад за файлы такого размера сисадмины устраивали кровавый офисный террор. Жизнь становится лучше, а технологии развиваются, но… Развитие не поспевает за потреблением. Терабайты и мегабиты все еще стоят довольно дорого.


Вернемся к сериалам. 0.5Gb на серию, 40 минут, 30 кадров в секунду, DVDRip = удовольствие ценой в ~36Gb чистого видео (кто первый правильно распишет, почему именно 36, получит ценный сувенир). И не у каждого найдется свободное место даже на пару сезонов (считайте сами), не говоря уже о времени на закачку. К счастью, на помощь приходит видеокодирование. И именно энкодер позволят превратить 36Gb в 0.5, т.е. сжать информацию в ~72 раза и при этом сохранить неплохое качество.


Как это возможно? Попробуем разобраться.


Принципы сжатия видеоданных основываются на восприятии человеком видеоряда (Human Visual Sense, HVS). На словах объяснить эти принципы довольно просто: 1) удалить всю «лишнюю» информацию, т.е. те детали изображения, которые все равно никто никогда не заметит, и 2) найти повторяющуюся информацию в видеопотоке и предпринять некоторые меры по минимизации дублирования. Ко второму пункту относится так называемая «статистическая» избыточность. Согласно HVS ее принято разделять на пространственную и временную. Пространственная избыточность – это значительные участки изображения с практически одинаковыми пикселями, например, небо. Сжатие таких фрагментов происходит примерно по тем же принципам, что и сжатие JPEG фотографий.


Ситуация с временной избыточностью несколько сложнее. Вспомним, что за секунду перед глазом человека проносятся 25-30 кадров. Насколько идентичная информация содержится в них? Если в кадре не происходит полной смены сцены, то достаточно близкая. Потому не имеет смысла кодировать каждый кадр по отдельности. Для минимизации объема хранимых (передаваемых, обрабатываемых, и так далее) данных, блочные стандарты видеокодирования, включая MPEG4, кодируют не весь блок целиком, а лишь остаточную разницу между этим блоком и похожим на него блоком опорного кадра.


С точки зрения работы энкодера существуют два основых функциональных блока. Первый - это дискретно-косинусное преобразование (DCT), позволяющее избавиться от пространственной избыточности статической картинки. Второй – оценка движения, которая, как было уже описано, сокращает временную избыточность следующих друг за другом видеокадров. Когда енкодер получает на вход видео, оценка движения и компенсация движения уменьшают объём одинаковой информации между соседними кадрами. Затем DCT и квантайзер минимизируют одинаковую информацию в рамках кадра. Квантовочные коэффициенты, трансформированные и квантованные коэффициенты и вектора движения поступают на энтропийный енкодер для финального сжатия. Чем лучше была произведена оценка движения, тем меньше работы достанется DCT. То есть лучшая оценка движения способствует лучшей компрессии видео.


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





Продолжим экскурс в теорию. Существуют различные методы оценки движения. Так называемые пиксельно-рекурсивные методы, позволяют вычислять вектор движения для каждого пиксела по отдельности. Отметим технику phase plane correlation, которая генерирует вектора движения исходя из корреляции между текущим фреймом и ссылочным. Однако, наиболее популярными являются алгоритмы блочного совпадения (Block Matching Algorithm - BMA).


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




иллюстрация BMA алгоритма

BMA алгоритм иллюстрирован на рисунке 2. Текущий кадр разбит на блоки пикселей и оценка движения производится для каждого блока отдельно. Результатом работы алгоритма для данного блока пикселей является нахождения наиболее похожего на него блока пикселей на ссылочном кадре и вычисление вектора движения или смещения текущего блока относительно найденного.

Таким образом, вектор движения представляет собой горизонтальное и вертикальное смещение на координаты x, y текущего блока пикселей:


где I это интенсивность пикселя в позиции вектора x в кадре n и d это смещение (вектор движения) относительно первоначальной позиции на n+1 кадре.

Существуют различные критерии определения совпадения блоков пикселей (Displaced Frame Difference - DFD), минимизирующие данную функцию:



Наиболее популярные:

Cуммарная квадратичная ошибка (Sum of Square Error - SSE):


и суммарная абсолютная разница (Sum of Absolute Difference - SAD):


SSE дает более аккуратное совпадение, однако более вычислительно сложное. SAD менее хорош в определении совпадения, но и требует меньше вычислений, поэтому наиболее часто используется в алгоритмах типа BMA. Также отметим такие критерии как взаимная корреляция и максимальное количество совпадающих пикселей.

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


Алгоритм полного поиска (Full Search – FS) относится к алгоритмам типа BMA. Алгоритм работает с каждым возможным блоком пикселей внутри области поиска. Именно поэтому результатом работы является наилучший вектор движения. Метод дает наилучшую возможную остаточную разность для видео компресии, но обладает высокой вычислительной трудностью. Это лучший из возможных алгоритмов для поиска совпадения блоков, который, к тому же отлично ложится на архитектуру многопоточности GPU.


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



Интерфейс библиотеки должен учитывать все детали алгоритма и данных. Мы знаем, что современные стандарты видеокодирования имеют блочную природу и каждый кадр делится на макроблоки с разной степенью двойки разбиением. Также нам известно, что алгоритмов оценки движения бывает нескольких видов и, разумеется, их реализация сильно отличается друг от друга. Стандарты определяют оценку по интерполированным кадрам на нецелое число пикселей. На вход приходят чистый кадр, движение которого необходимо оценить, и ссылочные (reference) кадры, с помощью которых исходный кадр и будет оцениваться. На выходе ожидаются вектора движения с привязанными значениями SAD. Учитывая эти и еще некоторые детали мы получим следующую картину-интерфейс. Заметьте, что я намерен использовать библиотеку Intel Integrated Performance Primitives, которая содержит множество полезных и быстрых функций для работы с видео. В частности, функции интерполяции и подсчета SAD.




#if !defined(__HARDWARE_ME_H)

#define __HARDWARE_ME_H


/* this implementation uses IPP defined types and structs */

#include 


#if defined(__cplusplus)

extern "C"

{

#endif /* defined(__cplusplus) */


/* Declare the types used in the accelerated ME object */

typedef struct _HW_ME_HANDLE *hw_me_handle_t;


enum 

{ 

    HW_ME_MAX_SAD               = 0x7FFFFFFF,

    HW_ME_MAX_LENGTH            = 0x7FFFFFFF,

    HW_ME_SLEEP_TIME            = 5


};


typedef

enum eHWMECodecStandard

{

    HW_ME_MPEG2                 = 0,

    HW_ME_MPEG4                 = 1,

    HW_ME_VC1                   = 2,

    HW_ME_H264                  = 3


} eHWMECodecStandard;


typedef

enum eHWMEAlgorithm

{

    HW_ME_RESIDUAL           = 0,

    HW_ME_TRUE_MOTION        = 1,


} eHWMEAlgorithm;


typedef

enum eHWMEType

{

    HW_ME_WHOLE_PIXEL           = 0,

    HW_ME_HALF_PIXEL            = 1,

    HW_ME_QUARTER_PIXEL         = 2


} eHWMEType;


typedef

enum eHWMEImageStructure

{

    HW_ME_FRAME                 = 0,

    HW_ME_TOP_FIELD             = 1,

    HW_ME_BOTTOM_FIELD          = 2,

    HW_ME_MIXED                 = 3


} eHWMEImageStructure;


typedef

enum eHWMEDivType

{

    HW_ME_DIV_16X16             = 0,

    HW_ME_DIV_16X8              = 1,

    HW_ME_DIV_8X16              = 2,

    HW_ME_DIV_8X8               = 3,

    HW_ME_DIV_8X4               = 4,

    HW_ME_DIV_4X8               = 5,

    HW_ME_DIV_4X4               = 6


} eHWMEDivType;


typedef

enum eHWMEPredictionType

{

    HW_ME_BACKWARD              = 0,

    HW_ME_FORWARD               = 1,

    HW_ME_INTRA                 = 2,

    HW_ME_BIDIRECT              = 3


} eHWMEPredictionType;


typedef

struct HW_ME_RANGE

{

    Ipp32s left;

    Ipp32s right;

    Ipp32s top;

    Ipp32s bottom;


} eHWMERange;


typedef

struct HW_ME_PARAMETERS

{

    Ipp32u structSize;                                  /* (Ipp32u) size of the current struct */

    IppiSize imageSize;                                 /* (IppiSize) size of processed images */

    Ipp32u maxNumRef;                                   /* (Ipp32u) maximum number of available references */

    IppiPoint maxVector;                                /* (IppiPoint) maximum allowed vector */

    eHWMEDivType minSubblockSize;                       /* (eHWMEDivType) minimal subblock size */

    IppiPoint maxSubBlockVectorDif;                     /* (IppiPoint) maximum vector difference between subblocks of macroblock */

    eHWMECodecStandard codecStandard;                   /* (eHWMECodecStandard) interpixel interpolation standard */

    eHWMEType meType;                                   /* (eHWMEType) type of interpolation */

    eHWMEAlgorithm algType;                             /* (eHWMEAlgorithm) algorithm type */


    IppBool strictWithinFrame;                          /* (IppBool) is it allow to be outside frame or not */


} HW_ME_PARAMETERS;


typedef

struct HW_ME_IMAGE

{

    eHWMEImageStructure imageStructure;                 /* (eHWMEImageStructure) current image structure */

    Ipp8u *pPlanes[3];                                  /* (Ipp8u *([])) array of pointers to image's planes */

    Ipp32s imageStep;                                   /* (Ipp32s) image step */


} HW_ME_IMAGE;



typedef

struct HW_ME_MB_INFO

{

	eHWMEDivType mbDiv;                                 /* (eHWEDivType) macro block fragmentation */

	eHWMEDivType subblockDiv[4];                        /* (eHWEDivType) sub macro block fragmentation */

	eHWMEPredictionType predType[4];                    /* (eHWMEPredictionType) macro block prediction types */

    Ipp32s minSAD;                                      /* (Ipp32s) minimal found SAD for the macroblock */

	Ipp32u ref[2][4];                                   /* (Ipp32u [][]) reference list for macro block */

	IppiPoint mv[2][16];                                /* (IppiPoint [][]) motion vector list */


} HW_ME_MB_INFO;


typedef

struct HW_ME_INFO

{

    HW_ME_MB_INFO *pMbInfo;                              /* (HW_ME_MB_INFO *) pointer to macroblock info store */


    Ipp32u numFrameRefs[2];                              /* (Ipp32u) number of references in reference array */

    Ipp32u refFrameList[2][16];                          /* (Ipp32u [][]) reference list for each direction */


    Ipp32u numTopFieldRefs[2];                           /* (Ipp32u) number of references in reference array */

    Ipp32u refTopFieldList[2][32];                       /* (Ipp32u [][]) reference list for each direction */


    Ipp32u numBottomFieldRefs[2];                        /* (Ipp32u) number of references in reference array */

    Ipp32u refBottomFieldList[2][32];                    /* (Ipp32u [][]) reference list for each direction */


} HW_ME_INFO;


/* Initialize the accelerated ME object */

IppStatus InitializeHWME(const HW_ME_PARAMETERS *pHWMEParams, hw_me_handle_t *pHandle);


/* Stop all ME operation and release the accelerated ME object */

IppStatus ReleaseHWME(hw_me_handle_t handle);


/* Add a reference to the accelerated ME object */

IppStatus CopyHWMEReference(hw_me_handle_t handle, const Ipp32u refIdx, const HW_ME_IMAGE *pImage);


/* Add a source image to the accelerated ME object */

IppStatus CopyHWMESource(hw_me_handle_t handle, const HW_ME_IMAGE *pImage);


/* Do a accelerated ME */

IppStatus DoHWME(hw_me_handle_t handle, HW_ME_INFO *pInfo, void **ppEvent = NULL);

IppStatus WaitHWMEDone(void *pEvent);


#if defined(__cplusplus)

} // extern "C"

#endif /* defined(__cplusplus) */


#endif /* __HARDWARE_ME_H */


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