Преобразование стандартов: методы оценки векторов движения

Константин Гласман

Вектор движения

Под преобразованием стандартов в телевидении обычно понимается изменение параметров разложения изображения: формата, числа строк в кадре, частоты кадров, типа развертки (чересстрочная/построчная). Перечисленные параметры определяют дискретизацию изображения в пространстве и во времени, поэтому распределение отсчетов изображения в пространстве и времени для входа и выхода преобразователей стандартов не совпадают [1]. Для формирования выходного сигнала преобразователя надо иметь отсчеты изображения объекта в новых точках и в новые моменты времени. Естественно, что дополнительную информацию об объекте съемки уже получить нельзя, но новые отсчеты можно попытаться вычислить. Такое вычисление требует умения буквально «читать между строк», то есть рассчитывать яркость и цветность изображения в точках, лежащих между строками растра, и способности «видеть» изображение между кадрами и полями.

Поставленная проблема — типичная задача интерполяции, в которой известна таблица значений функции при заданных значениях аргумента, а требуется вычислять значения функции в промежуточных точках. Введение интерполяции на основе трехмерной пространственно-временной фильтрации телевизионного изображения в преобразователях стандартов привело к значительному улучшению характеристик преобразования в сравнении с простейшими алгоритмами, основанными на исключении или повторении строк и кадров [2]. Но и в преобразователях стандартов, работающих по алгоритмам линейной интерполяции, заметны искажения при воспроизведении быстро движущихся объектов: размытие границ, дрожание, прерывистость изображения. Причина появления этих искажений в том, что часто не выполняются условия применимости интерполяции. При быстром движении объектов в поле изображения оказывается недостаточной частота кадров, то есть частота взятия отсчетов во времени.

Ограничения, присущие алгоритмам вычисления промежуточных отсчетов на основе интерполяции, были в значительной степени преодолены в системах преобразования стандартов с компенсацией движения. Эти системы работают подобно тому, как глаз человека, сопровождая взглядом быстро движущийся объект, видит его изображение резким. Работа систем с компенсацией движения основана на анализе изображения, выявлении движущихся объектов и оценке скорости их перемещения в кадре [2]. Эта задача решается с помощью специального устройства оценки движения объектов. Измеряется и абсолютная величина скорости, и направление перемещения объекта, то есть находится скорость как векторная величина. На практике определяются значения горизонтального и вертикального смещений объекта за время между двумя кадрами. Полученные значения являются соответственно горизонтальной и вертикальной координатами вектора, пропорционального скорости и называемого «вектором движения».

В простом случае все элементы изображения могут смещаться в одном направлении с одной скоростью. Примером является смещение объектов в изображении при панорамировании. Все точки изображения имеют один и тот же вектор движения. Но движение объектов в поле изображения может быть и более сложным. Если выполняется, например, масштабирование изображения путем изменения фокусного расстояния объектива камеры, то все точки изображения имеют разные векторы движения.

В общем случае должны быть выявлены объекты, или множества элементов изображения, характеризующиеся одним и тем же движением. Каждому такому объекту элементов назначается свой вектор движения. Чем больше таких независимых областей с присвоенными векторами движения может быть определено системой, тем лучше будет компенсировано движение в изображении. В пределе количество независимых векторов может быть равно числу элементов изображения. Если известен вектор движения для всех элементов изображения, то можно переместить элементы в расчетные точки и создать промежуточное изображение, необходимое для решения задачи преобразования стандартов.

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

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

Метод согласования блоков

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

ТВ-изображение делится на большое число блоков (обычно — прямоугольных). Каждый блок одного кадра (блок поиска) сравнивается с блоками следующего кадра, и оценивается вероятность, что они являются фрагментами одного и того же участка изображения. Если в следующем кадре находится блок, подобный блоку поиска первого кадра, то делается вывод, что блоки находятся в разных местах кадра вследствие движения (рис.1). Критерием наилучшего согласования может быть минимизация некоторой меры различий в величине сигналов двух блоков: квадратичное отклонение, отклонение по абсолютной величине и т. п. Затем вычисляются компоненты смещения блока из исходного положения до того, которое наилучшим образом согласуется с блоком поиска, что дает величину и направление вектора движения. Обычно поиск похожих блоков выполняется не в пределах всего изображения, а в рамках некоторой области, окружающей исходный блок, копия которого должна быть найдена. Размеры области и блока поиска сильно влияют на качественные показатели системы оценки векторов движения.

Точность оценки вектора находится на уровне одного элемента, поскольку обнаружение согласования блоков основано на сравнении значений элементов изображения. Размеры области поиска определяют максимальную величину вектора движения, которая может быть измерена, поскольку этот параметр ограничивает максимальную скорость перемещения объекта, которую возможно зафиксировать. Например, область поиска может быть равной квадрату размером 64×64 пиксела, что является удовлетворительным во многих случаях.

Размеры блока поиска прямо влияют на разрешение и вероятность ложного согласования. Когда блок поиска представляет собой квадрат 16×16 пикселов, он содержит довольно значительную часть изображения. Если определено, что блоки согласуются, то есть похожи друг на друга, то это с высокой вероятностью говорит о том, что результат оценки действительно отражает смещение объекта. Возможность ложного согласования мала. Но для каждого блока из 256 пикселов находится всего один вектор, то есть разрешение невелико. Для малых блоков с размерами 2×2 пиксела достигается высокое разрешение, но частота ошибок становится недопустимо большой, поскольку для блоков такого размера велика вероятность ложных согласований. Известно, что в задачах компрессии оптимальным блоком, при котором достигается компромисс между разрешением и частотой ошибок, является квадрат размером 8×8 пикселов. Но для целей преобразования стандартов ни разрешение, ни частота ошибок, соответствующие такому блоку, не являются приемлемыми. Это означает, что метод согласования блоков для преобразования стандартов нуждается в доработке.

Одним из вариантов усовершенствования метода согласования блоков является иерархическая пространственная корреляция. Поиск выполняется последовательно на нескольких уровнях с разными размерами блоков, а значения векторов движения, найденные на некотором уровне, используются в качестве вероятных и исходных для получения более точного результата на следующем уровне. Согласование блоков большого размера, с которых начинается поиск, находится за сравнительно небольшое количество вычислительных операций. Однако разрешение первого уровня невелико. Найденный вектор используется в качестве предсказания при поиске на следующем уровне с меньшим размером блоков, полученных делением блока первого уровня. Процесс повторяется несколько раз. На каждом последующем уровне увеличивается разрешение. Такой подход сочетает низкую частоту ошибок, характерную для блоков большого размера, и высокое разрешение, которое появляется при использовании малых блоков. Он позволяет находить большое количество векторов с высокой точностью и разрешением, причем для сложного движения. На первом этапе изображение может подвергаться низкочастотной фильтрации и передискретизации с целью уменьшения числа отсчетов и сокращения объема вычислений. Главный недостаток такого подхода заключается в том, что маленькие и быстро движущиеся объекты могут быть потеряны на первом этапе, когда используются блоки большого размера в сочетании с фильтрацией.

Градиентный метод

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

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

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

Метод фазовой корреляции

Теоретические предпосылки

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

Корреляционная функция, вводимая в теории сигналов, характеризует степень связи (корреляции) двух функций. В теории детерминированных сигналов она вычисляется как интеграл от произведения этих функций при различных значениях сдвига одной относительно другой [3]. Точка максимума корреляционной функции указывает на величину сдвига, при котором функции наиболее зависимы, или «похожи» друг на друга. При вычислении нормированной автокорреляционной функции (функции корреляции сигнала с самим собой) максимальное значение, равное единице, имеет место в начале координат (сдвинутая копия сигнала не просто наиболее «похожа», а эквивалентна оригиналу при нулевом сдвиге, что и дает единичное значение).

Вычисление взаимной корреляционной функции сигналов изображения двух соседних кадров может использоваться для оценки вектора движения. Если сигналы двух кадров отличаются друг от друга только сдвигом, что имеет место, например, при панорамировании, то точка глобального максимума взаимной корреляционной функции и будет давать вектор движения. Изображения двух кадров, показанные на рис.1, соответствуют именно этому случаю. Разумеется, взаимная корреляционная функция сигналов изображения как двумерных распределений яркости является некоторой поверхностью — функцией двух пространственных координат. Отрезок прямой, проведенный в плоскости изображения из начала координат в точку максимума, и дает вектор движения. Если движение объектов в плоскости изображения имеет сложный характер, например, несколько объектов движутся по разным направлениям, то корреляционная поверхность будет иметь максимумы в точках, соответствующих векторам движения различных объектов. Таким образом, вычисление взаимной корреляционной функции сигналов изображения двух кадров дает сразу все множество векторов движения. Это означает, что применение корреляционного метода для преобразования стандартов требует следующего этапа — необходимо определить, какой из векторов соответствует определенному объекту в изображении. Эта процедура часто называется присваиванием векторов движения объектам.

Фазовый спектр вводится в теории преобразований Фурье. Фурье-анализ (прямое преобразование Фурье) позволяет найти частотный спектр: частоты, амплитуды и начальные фазы гармонических составляющих сигнала. Частотный спектр в общем случае — это комплексная функция частоты, описываемая двумя вещественными функциями: модулем и аргументом. Модуль комплексного спектра дает амплитудно-частотный (или просто амплитудный) спектр сигнала — распределение амплитуд составляющих как функцию частоты. Аргумент комплексного частотного спектра дает фазо-частотный (или фазовый) спектр — распределение начальных фаз. Спектры — это просто другая форма описания и представления сигнала. Осциллограмма в виде зависимости величины сигнала от времени — это представление сигнала во временной или пространственной области. Спектры сигнала дают его описание в частотной области. Применяя к спектральному описанию обратное преобразование Фурье, то есть выполняя Фурье-синтез, можно восстановить исходный сигнал (прямое и обратное преобразования — обратимые процессы).

Но зачем нужен фазовый спектр при нахождении корреляционной функции? Дело в том, что прямое определение корреляционной функции в соответствии с определением — очень трудоемкая процедура, требующая огромного объема вычислений. Ситуация коренным образом изменилась с разработкой алгоритма быстрого преобразования Фурье (БПФ), когда стало выгодным вычислять такие функции, как свертка и корреляция в частотной области. Из теории преобразований Фурье известно [3], что частотный спектр взаимной корреляционной функции равен произведению частотного спектра одного сигнала на комплексно сопряженный спектр другого. Взаимную корреляционную функцию можно рассчитать, если найти частотные спектры двух сигналов, перемножить спектр одного сигнала на комплексно сопряженный спектр другого, а к полученному произведению применить обратное преобразование Фурье. Благодаря эффективности алгоритма БПФ такая последовательность процедур требует меньшего количества вычислительных операций, чем прямое вычисление корреляционной функции как интеграла от произведения сигналов.

Для получения комплексно сопряженного спектра сигнала необходимо изменить на противоположные знаки начальных фаз гармонических составляющих; амплитуды остаются неизменными. Таким образом, вычисление взаимной корреляционной функции двух сигналов требует применения обратного преобразования Фурье к комплексному частотному спектру, модуль которого равен произведению амплитудных спектров сигналов, а аргумент — разности фазовых спектров сигналов.

Роль амплитуд и фаз спектральных составляющих сигнала различна. Восстановление сигнала с помощью обратного преобразования Фурье на основе только амплитудного спектра практически невозможно. Однако восстановление сигнала с использованием только фазового спектра позволяет в ряде задач сохранить многие его важные свойства. К таким задачам относятся: определение точек расположения атомов в кристаллической структуре в рентгеновской кристаллографии; выделение контуров и границ при обработке изображений; восстановление изображений по фазовым голограммам. Все эти случаи объединяет то, что в них определяется положение «событий» (под «событиями» здесь понимаются линии — границы объектов в изображениях, точки — места расположения атомов в кристаллической структуре и т. п.). Более того, устранение информации об амплитудах спектральных составляющих может даже «заострить» события и увеличить точность их определения [4].

Приведенные выше соображения дают понимание того, почему в методе фазовой корреляции, применяемом для оценки вектора движения, обрабатывается разность фазовых спектров изображений двух кадров. Эти соображения также указывают место фазовой корреляции в длинном перечне подобных задач, первой из которых, видимо, был Фурье-синтез кристаллографических структур [4].

Литература

1. Гласман  К.. Преобразователи стандартов// «625». 2005. № 6. С. 5-11.

2. Гласман  К.. Преобразование стандартов: принципы технических решений// «625». 2005. № 7. С. 79-87.

3. Френкс  Л. Теория сигналов. М.: Сов. радио, 1974.

4. Оппенхайм  А. В., Лим  Д. С. Важность фазы при обработке сигналов// Труды института инженеров по электротехнике и радиоэлектронике. Т.69, № 5, май 1981. С.39-54.

Окончание следует