ГЛАВА 1. СИНТЕЗ АЛГОРИТМОВ ОЦЕНИВАНИЯ ПАРАМЕТРОВ ПРОСТРАНСТВЕННЫХ ДЕФОРМАЦИЙ МНОГОМЕРНЫХ ИЗОБРАЖЕНИЙ, НАБЛЮДАЕМЫХ НА ФОНЕ ПОМЕХ

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

1.1. Модели и методы оценивания параметров пространственно- временных деформаций изображений

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

Исходное изображение обычно является динамическим, то есть изменяю­щимся во времени. Датчик часто находится на подвижном объекте. Это приво­дит к тому, что получаемые с его помощью изображения различных кадров имеют взаимные сдвиги, повороты, изменения масштаба и т.п. Вклад в ПД по­следовательностей изображений вносят также искажения оптических трактов, нестабильность разверток считывающих устройств датчиков, дефекты их изго­товления. Можно отметить также искажения, вызванные изменением оптиче­ской плотности среды, турбулентностью атмосферы и т.д. Таким образом, прак­тически все составляющие системы формирования изображений могут вносить ПД в получаемые изображения. В некоторых случаях ПД - мешающий фактор и

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

Модели пространственно-временных деформаций

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

Смещение каждого узла сетки относительно его положения на

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

Рис. 1.1. Примеры возможных ПД изображений двух кадров.

векторное СП заданное на сетке. Если рассматривается последовательность кадров, то получим СП где - номер кадра. Очевидно, что при таком представлении размерность векторов (или ) совпадает с размерностью сетки .

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

системы координат в систему координат где - размерность сетки . В тех случаях, когда вид межкадровых ПД известен (сдвиг, поворот, изменение масштаба и т. д. ), преобразование (1.1) может быть задано параметрически:

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

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

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

Рис. 1.2. Структурная схема формирования последовательности изображений.

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

Методы оценивания пространственно-временных деформаций

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

В первом подходе используется сопоставление изображений или их отдельных локальных областей. При этом многие методы [1,2,18,20,49,65,95] основаны на выделении небольшого множества признаков (яркие и темные точки или их группы, контуры, углы, перекрестья и т. д.). При переходе от кадра к кадру устанавливается соответствие между этими признаками. Например, находятся межкадровые сдвиги в нескольких точках изображения. Далее учетом физических свойств наблюдаемых объектов (например, предположения об их твердости) значения межкадровых сдвигов интерполируются на остальную

часть изображения. Для применения таких методов необходимы

существование и стабильность выбранных признаков, которые могут быть весьма слабо выражены или отсутствовать.

Среди методов, основанных на сопоставлении изображений, отметим метод разложения на множители применяемый при восстановлении формы трехмерных объектов и характеристик движения камеры по последовательности кадров изображений. Такая задача возникает, например, в навигации и робототехнике. Нерекуррентный алгоритм, реализующий этот метод предложен в работе [108]. В [97] он обобщен для случая использования в качестве модели изображения конической проекции, учитывающей пространственные искажения за счет перспективы. На изображении выбирается характерных точек или локальных областей и оцениваются их координаты на кадрах изображений. По полученной совокупности данных восстанавливается форма объекта и траектория движения камеры. При этом форма объекта считается неизменной. Величина составляет, как правило, несколько десятков. Решение связано с обработкой матриц, размер которых увеличивается с увеличением числа кадров. При этом время, затрачиваемое на восстановление формы объекта, пропорционально Существенным недостатком такого подхода являются большие вычислительные затраты и необходимость хранения больших объемов данных. С целью уменьшения объема вычислений в работе [91] была предложена рекуррентная реализация метода разложения на множители. При этом оценки формы объекта и траектории движения камеры производятся в каждом кадре. Вычислительные затраты на восстановление формы объекта становятся постоянными и пропорциональными . Соответственно и обработка последовательности кадров теоретически может вестись в реальном времени. При обработке каждого очередного кадра форма объекта уточняется с применением ортогональных базисных функций, которые могут быть получены с использованием процедуры Грамма-Шмидта. Для дальнейшего уменьшения вычислительных затрат в ряде работ предложено использовать ортогональные итерации с ускорением [77]. Отметим, что даже в рекуррентном варианте метода разложения на множителя требования к вычислительным ресурсам остаются очень высокими и при современном развитии вычислительных средств его реализация в системах реального времени остается проблематичной.

Другой распространенной разновидностью методов, основанных на сопоставлении

изображений, являются корреляционно-экстремальные,

исходной посылкой которых является предположение о высокой коррелиро- ванности характеристик изображений на последовательности кадров [69,78,83,86]. К недостаткам этих методов можно отнести большие вычисли­тельные затраты в случае оценивания многокомпонентного вектора параметров ПД.

Оценка ПД при пространственно-временной фильтрации изображений [67,80,84] достигается за счет фильтрации изображений в пространственной и временной областях. Для этого параметры фильтра подстраиваются по про­странственным частотам. Этот подход требует использования информации о ПД изображений, содержащейся во всем изображении, поэтому применим, в основном, для оценки глобальных параметров деформаций, характерных для всего изображения (параллельный сдвиг, поворот и т.д.).

В подходе, основанном на использовании оптического потока, рассматри­ваются изменения яркости в узлах сетки отсчетов, то есть векторное поле ско­ростей движения точек яркостей сцены или их характеристик, например, кон­трастности, градиента, энтропии и т.д. [1,2,4,9,19,32,34,39,44,48,53,55,75,101]. Эти изменения обычно и называют оптическим потоком. Отметим, что в ряде работ такой подход называется также градиентным [77,81,109,110]. При кони­ческой проекции трехмерного изображения на плоскость ПД, вообще говоря, неоднозначно связаны с изменением яркости в узлах сетки отсчетов. Тем не ме­нее, как показывают исследования различных авторов [79,92,111], в большин­стве приложений оптический поток достаточно полно характеризует ПД изо­бражений последовательности кадров. При описании оптического потока обычно используются дифференциальные уравнения с частными производны­ми. Причем яркость изображения, как правило, считается неизменной во време­ни. Для вычисления оптического потока применяются методы регуляризации и методы, основанные на ограничениях.

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

отсчетов [77,81,94]. Например, для движущегося объекта оценивается сдвиг всех его точек, а не только контуров. Однако известен подход [78] к оцениванию оптического потока только в контурах движущихся объектов. Недостатком методов регуляризации является возможность возникновения нарушений непрерывности оцениваемых параметров ПД. Это приводит к тому, что при восстановлении изображений по оцененным параметрам на границах объектов могут возникать разрывы или "распространение" одного объекта внутрь другого. При этом величина этих дефектов зависит от числа итераций и использованных весовых коэффициентов. Кроме того, методы регуляризации во многих случаях ведут к потери части важной информации о форме объектов [72].

Методы, основанные на ограничениях, базируются на предположении, что условие неизменности яркости изображения справедливо и для некоторой другой функции в качестве которой могут выступать, например, контрастность, энтропия, выборочное среднее, кривизна, величина градиента, локальная интенсивность, спектр и т. д. Используя набор таких функций, оцененных в одной и той же точке изображений, можно получить систему уравнений для неизвестных параметров ПД [112]. При этом решение получается только в тех случаях, когда система уравнений разрешима, что имеет место не всегда. Другой, более частный прием, состоит в использовании ограничений относительно вторых частных производных яркости изображения [110]. Результаты, полученные при использовании методов, основанных на ограничениях, существенно зависят от выбора функций При гладкой оптической области потока в ряде работ [76,94] допускается, что ограничения для точек изображения, смежных с анализируемой точкой, определяют такие же параметры ПД как для анализируемой точки. Тогда множество одинаковых ограничений в районе исследуемой точки дает переопределенную систему уравнений, которая решается методом наименьших квадратов. Такой прием получил название "многоточечного метода". Он был использован, в частности, в работах [75,76] при оценивании параллельного сдвига изображений.

В методах, основанных на ограничениях, для улучшения оценок ПД применяют предварительную фильтрацию изображений [74,110,112], увеличение локальной области исследования [76], а также фильтрацию полученных оценок [110]. Однако указанные операции приводят также к некоторым неточностям в оценке границ движущегося объекта. Компромисс между точностью оценок и

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

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

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

Разновидностью метода, основанного на исследовании оптического потока, является использование локальных базисных функций [81,109] применение которых приводит к существенному уменьшению вычислительных затрат. Выбор базисных функций определяется требованиями к точности оценок сдвига и к вычислительным затратам. При наличии в изображениях высоких пространственных частот главным источником погрешностей оценок сдвига являются неточности формирования производных изображения, которые также определяются выбором базисных функций. Предложены различные базисные функции. Так, в работе [99] в качестве базисных функций исследованы линейная (с областью определения кубическая (с областью а также пяти- и семиточечные функции типа (с областями соответственно и). Объем вычислений растет пропорционально где - линейный размер области определения локальной базисной функции. Показано, что при одной и той же области определения кубические сплайны предпочтительнее функций типа Отметим также, что в работе [71] показано, что при дискретизации изображений частота Найквиста с вычислительной точки зрения не является

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

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

При сжатии видеоинформации часто используется то обстоятельство, что параметры межкадровых афинных преобразований в любой точке трехугольной или четырехугольной области могут быть определены по сдвигам соответственно трех (при билинейной интерполяции) или четырех (при перспективной интерполяции) точек изображения [68,70,89], расположенных в узлах соответствующей сетки. Использование методов, основанных на исследовании оптического потока, как уже отмечалось, может приводить к нарушениям связности сетки. Например, международные стандарты сжатия видеоинформации и MPEG используют процедуры оценивания ПД, которым присущ указанный недостаток. Для уменьшения погрешностей при оценке сдвигов узлов сетки в работе [96] используется расширение локальной области. Однако это полностью не решает проблемы и ведет к увеличению объема вычислений. Другим подходом является использование связных сеток. Так, в работе [102] для интерполяции была предложена треугольная и четырехугольная, а в работе [93] - шестиугольная связные сетки, где параметры афинного преобразования однозначно определяются решением системы соответственно трех, четырех или шести уравнений. Независимая оценка сдвигов каждого узла нежелательна, так как вектора могут пересекаться, нарушая связность сетки. Поэтому при нахождении методом наименьших квадратов векторов сдвигов накладывают ограничения, сохраняющие связность сетки. Предложены различные виды сеток: регулярная, иерархическая, объемная, интеллектуальная и др. Регулярные сетки получают делением области изображения на равные треугольные или прямоугольные элементы [93]. Недостатком этих сеток является их неспособность отражать особенности изображения, например, в один элемент сетки может попасть несколько движущихся объектов. В иерархических сетках движущиеся объекты распределяются по элементам сетки [82]. В объемных сетках элементы стараются согласовать с интересующими особенностями изображений. Если априорная

информация о содержании изображения доступна, то может быть использована интеллектуальная сетка, которая использует прогноз трехмерного изображения на плоскость [70].

В подходе, базирующемся на морфологическом анализе изображений [40,41], используется понятие формы изображения [40] как его максимального инварианта. Такой подход позволяет решать задачу оценивания пространственных деформаций, когда другие подходы оказываются неприменимыми, например, для случая произвольного функционального преобразования яркостей. Однако указанный подход также требует большого объема вычислений.

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