В настоящее время область компьютерной графики является одной из наиболее динамично развивающихся и перспективных областей информатики. Вычислительные мощности растут, удельная стоимость хранения информации стремительно падает, и идеи, которые всего несколько десятков лет назад могли показаться фантастичными, сегодня успешно воплощаются в жизнь.
Если лет десять-пятнадцать назад верхом графических возможностей рядового персонального компьютера считалась его способность отобразить картинку из нескольких десятков тысяч точек, имея в распоряжении всего несколько десятков различных цветов, то сегодня каждый пользователь, не пожалевший денег на последнюю модель видеокарты, может наслаждаться потрясающей реалистичностью современных компьютерных игр.
Профессиональные же графические рабочие станции и суперкомпьютеры обладают несравненно большим потенциалом. В киноиндустрии они давно стали незаменимы при создании спецэффектов и фантастических сцен, а в последнее время их часто используют и для генерации некоторых сцен фильма, съемка которых традиционными способами возможна, но затруднительна либо дорогостояща. Так, несколько лет назад мировой кинопрокат потряс фильм, от начала и до конца созданный при помощи компьютера (за исключением озвучивания, которое выполняли реальные люди), причем упор при создании этого фильма делался именно на реалистичность. Надо отметить, что с этой задачей его создатели справились на <отлично> - все персонажи, их жесты и мимика, настолько хорошо продуманы и нарисованы, что практически неотличимы от настоящих людей.
Но если созданием продвинутых спецэффектов для киноиндустрии занимаются сравнительно небольшие группы профессионалов, то потребление продуктов кинорынка рассчитано на массы. И если совсем недавно самым популярным форматом распространения видеопродукции был аналоговый формат VHS, изобретенный ещё в середине семидесятых, то сегодня цифровые форматы, особенно DVD, быстро и уверенно вытесняют VHS с рынка. Это связано с тем, что с задачами хранения, обработки и показа цифрового видео, казавшимися неразрешимыми инженерам десять лет назад, сегодня успешно справляются как персональные компьютеры, имеющиеся почти в каждом доме, так и встроенные микросхемы набирающих популярность DVD-плееров и систем домашних кинотеатров.
Распространение цифрового видео во многом обязано разработке эффективных алгоритмов его сжатия. Проведя простые вычисления, получим, что размер одной минуты несжатого фильма разрешения 640х480 с частотой 25 кадров в секунду (стандарт PAL) и глубиной цвета 24 бит на пиксел равен 640*480*3*25*60 байт ≈ 1,3 Гбайт. Таким образом, на один DVD-диск стандартной ёмкости 4,5Гбайт поместится всего лишь три с половиной минуты видео. Поэтому для того, чтобы уместить фильм целиком на одном диске, нужно обеспечить сжатие в сорок раз и более (с учетом того, что есть ещё звуковая информация). А если требуется записать фильм на обычный компакт-диск ёмкостью 700 Мбайт, то степень сжатия придется поднять ещё раз в 6-7.
Алгоритмы сжатия видео во многом схожи с алгоритмами сжатия изображений, точнее, они используют те же особенности исходных данных и человеческого восприятия, а именно избыточность информации, плавность её изменения и слабую чувствительность глаза к небольшим искажениям при восстановлении. Последнее свойство активно используется алгоритмами сжатия с потерями качества, которые не гарантируют точное восстановление исходных данных, но обеспечивают значительно лучшую степень сжатия.
Как правило, различают пространственную и временную избыточность информации в видео. Под пространственной избыточностью понимают обычно схожесть значений соседних пикселов и плавность цветовых переходов в отдельно взятом кадре, то есть преобладание низких частот над высокими, если изображение рассматривать с точки зрения теории обработки сигналов. Эта избыточность используется и в алгоритмах сжатия изображений, среди которых наиболее хорошо себя зарекомендовали основанные на преобразовании Фурье (например, JPEG, описание которого можно найти в [1]) и на вейвлетном преобразовании (перспективное направление, описание можно взять в [2]).
Использование временной избыточности основывается на предположении, что за небольшой промежуток времени, соответствующий нескольким кадрам, объекты, присутствующие в видеосцене, изменяются не очень сильно. Поэтому попиксельная разность двух последовательных кадров на большей части своей площади будет близка к нулю, и, следовательно, хорошо сожмется алгоритмом, использующим пространственную избыточность информации. (Хотя сжатие разностей соседних кадров вместо самих кадров накладывает некоторые ограничения на процессы сжатия и распаковки, тем не менее этот подход с указанными ниже усовершенствованиями используется почти всеми алгоритмами сжатия видео, так как он существенно увеличивает степень сжатия).
Использование простой попиксельной разности последовательных кадров позволяет получить выгоду при сжатии видеоряда, содержащего неподвижные объекты. Но что произойдет с этой разностью, если объект или фон сдвинется всего на несколько пикселей? В зависимости от текстуры этого объекта разность может увеличиться весьма значительно, причем неприятным для алгоритма сжатия образом (может содержать много резких переходов цветов, то есть высоких частот). Поэтому все современные алгоритмы сжимают не просто попиксельную разность двух последовательных кадров, а разность текущего кадра и так называемого <скомпенсированного> кадра. Скомпенсированный кадр - это один из соседних (уже обработанных алгоритмом, то есть сжатых) кадров, в котором часть объектов (в идеале - все) перемещены и/или трансформированы так, чтобы этот измененный кадр был как можно более близок в некоторой метрике к текущему кодируемому кадру, разность с которым и будет непосредственно сжиматься. То есть скомпенсированный кадр можно получить, зная сам соседний кадр (обычно предыдущий) и некоторую дополнительную метаинформацию, которая называется информацией о движении.
На рисунке 1 приведены два последовательных кадра из фильма <Амели>, их попиксельная разность и попиксельная разность одного из них с соответствующим скомпенсированным кадром.
|
Кадр 79 |
|
|
Кадр 80 |
|
|
Разность кадров 80 и 79 (контрастность увеличена втрое) |
|
|
Разность кадра 80 со скомпенсированным кадром 79 (контрастность увеличена втрое) |
|
Рисунок 1. Фрагмент из фильма <Амели>
Таким образом, имея разность каждого кадра со скомпенсированным предыдущим, информацию о движении для каждого кадра, и распаковывая кадры в том же порядке, в каком они были сжаты, можно восстановить весь сжатый видеопоток (но хотя бы один первый кадр придется сжать независимо от других, поскольку для него ещё нет предыдущего кадра). Поэтому, чем точнее будет скомпенсировано движение и чем компактнее при этом будет представлена информация о движении, тем больший выигрыш в сжатии можно получить.
Задача компенсации движения возникает также в других областях компьютерной графики, связанной с обработкой видео. При преобразовании чересстрочной развертки в прогрессивную (деинтерлейсинге) компенсация движения позволяет заметно повысить качество результата, так как с её помощью можно привести два последовательных поля к одному моменту времени, тем самым давая возможность использовать дополнительную информацию для восстановления недостающих строк кадра. Компенсация движения является неотъемлемой частью хороших алгоритмов повышения качества видео, в частности, алгоритмов шумоподавления.
Необходимо отметить, что в настоящее время задача компенсации движения в общем случае (для всех классов объектов и любых типов видеопоследовательностей) решена быть не может, так как состоит из двух подзадач, для каждой из которых существуют только переборные решения с некоторой оптимизацией, являющие собой компромисс между точностью приближения и вычислительной сложностью. Это - задача выделения (распознавания) объектов на изображении и - собственно - задача определения траектории движения или, в более общем случае, характера деформации объекта.
Поскольку для задач обработки видео скорость работы алгоритма имеет большое значение, многие алгоритмы основаны на довольно грубых предположениях и обобщениях, которые существенно упрощают решение вышеупомянутых задач. Так, вместо объектов движение зачастую ищется для непересекающихся прямоугольных подобластей кадра - блоков, тем самым предполагается, что любой объект можно представить в виде объединения таких блоков. Среди всевозможных изменений и деформаций объектов ограничиваются рассмотрением определенного класса движений, например, класса аффинных преобразований, и в этом классе ищется наиболее близкое решение. Выбор метрики, определяющей близость решения к искомому, является отдельной задачей и осуществляется обычно с учетом требований конкретной области применения.
Классификации и обзору существующих алгоритмов компенсации движения посвящен следующий раздел.
Алгоритмы компенсации движения можно разбить на классы по ряду признаков и свойств, но наибольший интерес представляет классификация по способу работы (или архитектуре) и по назначению (области применения алгоритма).
Классификация по способу работы алгоритма учитывает следующие его архитектурные особенности:
и сумма квадратов разностей (Sum of Squared Differences, SSD):
,
где суммирование производится по всем точкам объекта компенсации (например, прямоугольного блока), FOrig и FComp- яркость (luminance) исходного и скомпенсированного кадра, соответственно, в точке p=(x,y)T.
При классификации по назначению обычно выделяют две большие группы: алгоритмы, использующиеся при сжатии видео, и алгоритмы, использующиеся при обработке видео (деинтерлейсинге, изменении частоты кадров). Разница между ними в том, что алгоритмы первой группы ориентированы на уменьшение попиксельной разницы исходного и скомпенсированного кадров, так как именно от него зависит степень сжатия видео. При этом для них, как правило, не важно, правильно ли определено движение, или просто найдены близкие по яркости области на двух последовательных кадрах. Для алгоритмов же второй группы истинность найденных параметров движения очень важна, поскольку на основе этих параметров производится настройка других параметров алгоритма.
Следует отметить, что классификация по назначению довольно условна: некоторые алгоритмы сложно отнести к той или иной группе, поскольку они с одинаковым успехом могут применяться в обоих случаях. Поэтому в дальнейшем на этой классификации внимание заостряться не будет, если только это не потребуется для повышения степени понимания материала.
Рассмотрим подробнее несколько устоявшихся и наиболее популярных подходов к компенсации движения.
Один из наиболее ранних методов компенсации движения [3]. Компенсация производится отдельно для каждого пиксела кадра, рассматриваемый класс преобразований - линейные сдвиги. Минимизируется обычно суммарная ошибка компенсации для всего кадра (Displaced Frame Difference, DFD):
,
где F(p,n) - яркость кадра номер n в точке p=(x,y)T, d(p)=(dx,dy)T - вектор смещения для точки (x,y)T. Результатом алгоритма для текущего кадра с номером n будет такой набор векторов d0 для каждой точки кадра p=(x,y)T, что
по всевозможным наборам d.
Подход основан на предположении, что яркость можно приблизить линейной функцией от положения точки в кадре. Это предположение оправданно только для сравнительно небольшой окрестности этой точки, что существенно снижает область применимости данного метода и позволяет ему корректно оценивать лишь небольшие сдвиги.
Это ограничение можно преодолеть, оценивая не сам вектор сдвига, а его разность с некоторым вектором предсказания, который с большой вероятностью расположен ближе к искомому вектору, чем нулевой. В общем случае, когда движение может составлять десятки пикселов, вектор сдвига ищется с помощью итерационного алгоритма - на каждом шаге происходит уточнение найденного на предыдущем шаге значения:
,
где i - номер итерации, update(p) - вектор уточнения, небольшой по величине. В качестве начального приближения можно взять вектор сдвига для этой же точки, найденный при обработке предыдущего кадра.
Этот метод имеет ряд серьезных недостатков, вследствие чего в настоящее время он представляет чисто теоретический интерес и практически нигде не используется. Основные его недостатки - высокая сложность (движение оценивается для каждого пиксела в отдельности), низкая точность (в силу несостоятельности основного предположения метода) и большой объем метаинформации, описывающей движение (для каждого пиксела задается вектор смещения в виде пары целых чисел).
Этот метод, точнее, класс методов, является логическим следствием предыдущего, устраняющим большую часть его недостатков, так как единицей компенсации в нем принят прямоугольный блок (обычно квадрат 16x16 пикселей или меньшего размера). Движение также ищется в классе линейных смещений, поэтому описывается такое движение двумерным вектором смещения для каждого блока.
Основное предположение метода - за время, проходящее между двумя последовательными кадрами, объекты в сцене и их местоположение изменяются незначительно. Тогда в окрестности любой точки кадра это изменение с достаточно высокой степенью точности можно приблизить параллельным переносом этой окрестности на некоторый вектор. На самом деле, подавляющее большинство обычных видеопоследовательностей удовлетворяют этому ограничению, за исключением участков резкой смены сцены, то есть характер движения объектов можно считать почти всюду непрерывным.
Итак, принцип работы метода следующий (см. рисунок 2):
Рисунок 2. Схема работы алгоритма сопоставления блоков
В качестве функции ошибки компенсации чаще всего используется мера SAD для скомпенсированного блока:
,
так как её вычисление проще реализуется на некоторых архитектурах процессоров.
Различные модификации этого подхода
различаются тем, каким образом находится минимум функции ошибки компенсации во
всей области
.
Наилучшего качества приближения, то есть минимальной ошибки компенсации, может гарантировать полный перебор всех возможных значений векторов смещения из допустимой области с подсчётом ошибки компенсации для них и выбор того вектора, на котором достигается минимум ошибки [4]. Этот подход считается эталонным, и сравнение с ним является неотъемлемой частью любой работы, посвященной разработке нового алгоритма компенсации движения. Однако практическое его применение в потребительских продуктах не представляется возможным ввиду слишком большой вычислительной сложности. Например, если требуется искать вектора движения в области +32 пиксела по каждому измерению для каждого блока размером 16x16, то SAD придется вычислить 64*64=4096 раз, в то время как каждое вычисление SAD требует 256 операций взятия модуля и 255 операций сложения.
Существуют способы ускорения полного перебора, позволяющие существенно сократить число операций за счет оптимизации вычисления самой функции ошибки [5] либо за счет вычисления некоторых оценок сверху для этой функции, что позволяет сократить количество векторов, для которых вычисляется функция ошибки [6]. Но количество операций на один пиксел размера кадра по прежнему слишком велико для работы алгоритма в реальном времени. Желательно иметь метод, позволяющий добиться близких результатов, но существенно меньшими затратами.
Перебор по шаблону Предположим, что функция
строго монотонно
сходится к своему минимуму в области
. Тогда проверкой всего нескольких точек в этой области можно
локализовать этот минимум [7]. Алгоритм, по которому эти точки выбираются,
называется шаблоном.
Минимальное число проверок обеспечивает ортогональный шаблон, сокращающий за каждый шаг, состоящий из двух проверок, область поиска вдвое (рисунок 3).
|
|
|
Рисунок 3. Ортогональный шаблон
Но, поскольку функция ошибки компенсации почти никогда не бывает монотонной, а обычно имеет множество локальных экстремумов, затрудняющих поиск глобального экстремума, часто является целесообразным использовать другие шаблоны, на каждом шаге проверяющие более чем две точки. Это уменьшает вероятность найти локальный минимум вместо глобального. Наиболее популярными являются прямоугольный и восьмиточечный шаблоны (рисунок 4), причем последний может иметь фиксированный размер на протяжении всех шагов либо уменьшаться вдвое на каждом шаге подобно рассмотренному ранее ортогональному шаблону. Последний вариант обычно называют трехшаговым поиском (Three Step Search, TSS), поскольку изначально этот шаблон применялся для области поиска +7 пикселов и находил минимум за три шага (с размером шаблона 4, 2 и 1 пиксел).
| |
Рисунок 4. Виды шаблонов
Методы, основанные на шаблонах, демонстрируют неплохую скорость работы, однако часто находят локальный минимум вместо глобального. Как преимущество можно отметить то, что поиск вектора движения для каждого отдельного блока не зависит от результатов поиска в соседних блоках и в предыдущем кадре, что делает метод более эффективным при очень интенсивном и сложном движении, чем рассмотренный ниже рекурсивный метод.
Трехмерный рекурсивный поискВ этом методе [8] проверяемое подмножество области поиска формируется для каждого блока отдельно на основе результатов поиска для соседних, уже обработанных блоков, и блоков предыдущего кадра. Основная идея состоит в том, чтобы использовать гладкость поля векторов движения для сокращения времени поиска (согласно наблюдениям, поле векторов является достаточно гладким как в пространстве, так и во времени, за исключением разрывов, возникающих на границах объектов, движущихся не одинаково, и ситуации смены общего плана). Поэтому в большинстве случаев для нахождения глобального минимума во всей области поиска бывает достаточно проверить вектора смещения для нескольких соседних блоков и уточнить их в небольшой окрестности.
Если записать формально, получим, что множество кандидатов на проверку (Candidate Set, CS) для блока с координатами p=(x,y)T кадра с номером n описывается следующим образом:
,
где M, N - размеры блока по горизонтали и вертикали, соответственно, d(p,n) - вектор смещения для блока с координатами p=(x,y)T в кадре с номером n. Вектора v1(p) и v2(p) - это так называемые вектора обновления: случайные вектора из небольшой окрестности нулевого вектора. Основной смысл их использования - избежать насильственного сглаживания поля векторов, обеспечить возможность его вариации.
Графически формирование множества CS выглядит следующим образом (см. рисунок 5).

Рисунок 5. Формирование множества кандидатов
Данный метод является самым быстрым из рассматриваемых, и при слабом движении показывает неплохой результат, однако в большинстве случаев накладываемое ограничение на гладкость поля векторов оказывается слишком сильным. Поэтому самим автором [8] был предложен улучшенный трехмерный рекурсивный метод [9], использующий больше проверок при уточнении предсказанного вектора, а именно вектор, найденный с помощью немного измененной базовой версии алгоритма, уточняется затем в окрестности +1 пиксел.
Изменение базовой версии заключается в
том, что случайные вектора обновления v1(p) и v2(p) теперь не используются: вместо одного из них
используется нулевой вектор, вместо второго - вектор
однопиксельного уточнения, найденный на
второй стадии алгоритма для предыдущего блока в текущем кадре:
,
взятый с
коэффициентом
>0. Этот коэффициент определяет, насколько быстро алгоритм
реагирует на градиентное изменение векторного поля в пространстве.
Метод носит название Enhanced 3D-RS. Вследствие своей простоты и высокой эффективности он является привлекательным для аппаратной реализации, хотя качество компенсации не всегда бывает удовлетворительным, особенно в сложных случаях.
Предположим, что все изменение в кадре вызвано только движением камеры. Тогда это движение можно описать моделью с четырьмя параметрами [3]:
.
Параметры p1(n) и p2(n) описывают параллельное перемещение камеры, в то время как p3(n) и p4(n) описывают вращение и приближение/удаление.
Можно легко обобщить этот метод на общий случай, когда в кадре есть множество независимо движущихся объектов: после разбиения кадра на блоки данная модель может быть применена для каждого из блоков кадра. На самом деле наиболее эффективным является совмещение параметрического подхода с каким-либо блочным методом, например с Enhanced 3D-RS, когда такой параметрический вектор добавляется в качестве дополнительного кандидата в его множество кандидатов [10].
При блочном подходе компенсация для каждого блока производится независимо от соседних, хотя (как в 3D-RS) результат компенсации для них может и учитываться при составлении множества кандидатов. В то же время в большинстве случаев желательно, чтобы для всех блоков объекта, состоящего из нескольких блоков, компенсация давала один и тот же результат (по крайней мере, поле векторов над одним объектом должно быть достаточно гладким и не содержать случайных выбросов). Этого можно добиться, например, приписав каждому блоку номер объекта, к которому он относится, и оценивая для каждого тестового вектора суммарную ошибку компенсации по всем блокам объекта.
Процесс сегментации может происходить независимо от процесса поиска параметров движения, либо и то, и другое может определяться в рамках единого процесса, повторяющегося итеративно. В первом случае основанием для сегментации служит обычно яркостная информация (например, [11]), во втором сегментация производится с учетом найденных параметров движения, которые затем уточняются [12]. Иногда сегментация кадра на объекты применяется после определения векторов смещения для отдельных блоков с целью коррекции найденного векторного поля [13].
Данный подход является одним из наиболее перспективных и обещает стать популярным в ближайшем будущем, хотя в настоящее время имеет достаточно высокую вычислительную сложность. Потенциально это наиболее точный и устойчивый к шуму метод (при правильно выполненной сегментации).
Комментарии
Отличная статья. Занимаюсь сей час написанием общего алгоритма. Большое спасибо!
Статья хорошая. Но по моему в
Статья хорошая. Но по моему в ней есть незначительная ошибка, которая в принципе не нарушает логики статьи. В разделе "Сопоставление блоков" и подразделе "Полный перебор" при размере области поиска 32x32 пикселя и эталонного участка 16x16 полный перебор потребует вычисления SAD (32-16+1)*(32-16+1)=289 раз (другими словами при полном переборе будет 289 положений сканирования эталонного участка относительно области поиска). А дальше фраза правильная "...в то время как каждое вычисление SAD требует 256 операций взятия модуля и 255 операций сложения." Если я ошибаюсь поправьте меня.))
Отправить комментарий