ГЛАВА 2. КВАЗИОПТИМАЛЬНЫЕ НЕАДАПТИВНЫЕ АЛГОРИТМЫ ОЦЕНИВАНИЯ МЕЖКАДРОВЫХ СДВИГОВ ИЗОБРАЖЕНИЙ

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

Проблема измерения параллельного сдвига изображений исследовалась в многочисленных работах [19,20,23,34,39,68,69,78,80 и др.]. При этом разработанные алгоритмы оценивания, основанные на корреляционно-экстремальном методе [18,19,23,39,69,78,80] и исследовании пространственного спектра (например, посредством многомерного преобразования Фурье) требуют огромного объема вычислительных операций и, как правило, не удовлетворяют условию реализуемости в реальном времени. Из известных процедур указанному условию удовлетворяют алгоритмы независимой (по координатам) оценки проекций вектора сдвига, полученные А. Нетравали и Д. Роббинсом Д. Лимбом и Д. Мэрфи А. В. Губановым и В. С. Киричуком алгоритмы, предложенные К. Каффорио и Ф. Рокка [74] и ряд других. Однако известные алгоритмы не обеспечивают высокой точности оценивания и имеют небольшой рабочий диапазон, ограниченный, как правило, несколькими шагами сетки отсчетов. Недостаточно уделено внимания и анализу точности алгоритмов, в частности, влиянию коррелированности отсчетов изображения на точность получаемых оценок.

Отметим также, что для реальных изображений характерна анизотропность, приводящая при независимой по координатам оценке проекций вектора сдвига к смещенности получаемых оценок. Известный алгоритм К. Каффорио и Ф. Рокка [74] позволяет избавиться от влияния на смещенность оценок асимметричности эллипсообразной КФ изображений; однако достигается это за счет существенного снижения точности оценивания. В целом же вопрос коррекции смещенности оценок, вызванной асимметричностью КФ, исследован мало. Учитывая сказанное, основное внимание в данной главе уделено разработке и исследованию реализуемых в реальном времени неадаптивных алгоритмов оценивания параллельного сдвига изображений двух кадров.

2.1. Синтез квазиоптимальных неадаптивных алгоритмов оценивания межкадрового сдвига изображений

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

и - дисперсии шумов и оценки сдвига соответственно; - прогноз наблюдения . Подставляя (2.2) в (2.1) и полагая , получим

Используя квадратичное приближение для производных (при квадратичной интерполяции ) приведем (2.3) к симметричному виду

Алгоритм (2.4) содержит оценки случайного поля, которые можно получить с помощью методов нелинейной фильтрации [11,12,31 и др.]. Однако объем вычислений при нахождении таких оценок весьма значителен. Поэтому дальнейшее упрощение (2.4) при небольшом уровне шумов заключается в замене оценок наблюдаемыми значениями изображения . При этом алгоритм оценивания сдвига принимает вид

Для более компактной записи введем обозначения . Тогда (2.5) запишется как

Заметим, что к выражению (2.6) приводит также минимизация среднего квадрата ошибки линейного прогноза при использовании для прогноза наблюдений квадратичной интерполяции и предположении, что коэффициент межкадровой корреляции . Аналогичное выражение было получено А. Нетравали и Д. Роббинсом в работе [95] при синтезе алгоритма оценки сдвига методом разложения изображений в ряд Маклорена.

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

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

корреляционных моментов и . При отсутствии сдвига между и корреляционные моменты равны. При появлении положительного сдвига возрастает первый элемент и уменьшается второй. При отрицательном сдвиге наблюдается обратная картина.

Смысл умножения на разность и деления на квадрат этой разности в (2.5) становятся более понятными, если значение представить в виде . После подстановки этого выражения формула (2.5) преобразуется к виду

Другая модификация выражения (2.6), основанная на предположении пропорциональности величины сдвига отношению и направленная на исключение операций умножения, была предложена Д. Лимбом и Д. Мэрфи [90]:

Отметим также, что одномерный вариант алгоритма, предложенного К. Каффорио и Ф. Рокка [74] полностью идентичен (2.8). Дальнейшим упрощением (2.8) можно считать оценку

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

Модификация (2.7), использующая по аналогии с (2.8) в знаменателе сумму модулей, приводит к соотношению

Алгоритмы на каждом шаге накопления сумм требуют использования трех отсчетов: двух из опорного кадра и одного из сдвинутого. В этом смысле их можно условно назвать . Известны и другие трехточечные процедуры [17,55,59,61 и др.]. Так, использование метода максимального правдоподобия для авторегрессионной модели изображений приводит [17] к алгоритму

Трехточечные процедуры обеспечивают определение направления сдвига (знака оценки) за использования отсчетов опорного кадра, отстоящих от на расстоянии а друг от друга, соответственно, на расстоянии 2. Это приводит к низкой точности аппроксимации изображения. Улучшить качество аппроксимации и, следовательно, точность оценок сдвига можно сократив расстояние между опорными отсчетами до 1. Однако при этом требуется дополнительно оценивать направление сдвига. Это удается осуществить за счет использования на каждом шаге формирования сумм четырех отсчетов - по два с опорного и сдвинутого кадров. В частности, "четырехточечный" модифицированный алгоритм (2.8) принимает вид

В (2.12) в качестве решающего правила выбора для оценки сдвига положительного знака используется условие

"Четырехточечный" аналог алгоритма (2.6) принимает вид

При этом для выбора знака оцениваемого сдвига целесообразно использовать решающее правило

Проведенные исследования показали, что правила (2.14) и (2.16) обеспечивают очень высокую надежность определения направления сдвига.

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

Оценка проекции вектора сдвига на строится аналогично

Алгоритм (2.12) для двумерного случая принимает вид

Аналогичным образом для двумерных изображений могут быть записаны и другие алгоритмы, рассмотренные в этом разделе. Проведенные исследования показали, что в случае круговой автокорреляционной функции плоского изображения точностные возможности алгоритмов в рабочей области примерно соответствует их одномерному варианту. При этом СКО оценки проекции на одну из базовых осей при увеличении сдвига по другой от 0 до 1 возрастает приблизительно на 20-25%.

Заметим также, что в рассмотренных выше алгоритмах при накоплении сумм числителя и знаменателя координаты отсчетов могут выбираться не только подряд (как в алгоритме (2.17)), но и с некоторым детерминированным или случайным прореживанием. Тогда координаты отсчетов, входящих в суммы будут функциями номеров суммирования и то есть . Как будет показано в разделе 2.3, такой подход к выбору отсчетов позволяет снизить дисперсию оценок за счет уменьшения коррелированности слагаемых в суммах.

Расширение рабочего диапазона квазиоптимальных алгоритмов

Квазиоптимальные алгоритмы оценивания сдвига, полученные в разделе 2.2, имеют, как правило, рабочий диапазон что ограничивает их применение при решения практических задач. Для расширения рабочего диапазона может быть использовано предварительное измерение целой части сдвига с последующим переносом координат и измерением дробной части сдвига. Исследования показали, что задача измерения целой части сдвига с успехом может быть решена с использованием тех же алгоритмов. При этом, например для гауссовских СП с , рабочий диапазон алгоритмов может быть увеличен в 5-10 раз.

В приложении в качестве примера приведен алгоритм оценивания двумерного сдвига с рабочей областью использующий процедуры (2.18), (2.20) и хорошо зарекомендовавший себя на практике. Алгоритм ориентирован на работу с изображениями небольших размеров, поэтому в нем обращается особое внимание на обеспечение максимально возможного числа слагаемых при формировании сумм числителя и знаменателя (2.18). Заметим, что при сдвиге кадра относительно на несколько элементов, например влево, область изображения, соответствующая крайним правым отсчетам кадра отсутствует на кадре . Поэтому на первых этапах алгоритма из рассмотрения должны быть исключены отсчеты, расположенные по периметру кадров и на расстоянии от границ изображения, соответствующем максимальному сдвигу. По мере уточнения оценок на последующих этапах, рабочая область изображений расширяется (см. приложение), достигая максимума при оценке дробных частей проекций вектора сдвига.

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