Корреляционно-экстремальные методы

Корреляционно-экстремальные методы

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

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

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

Корреляционный критерий сходства (мера близости):

,

где t – фрагмент изображения, g – эталон размером NxM.

К недостаткам классического алгоритма следует отнести боль­шой объем вычислений, так как вычисление функции взаимной корре­ляции производится при всех возможных относительных сдвигах об­рабатываемых изображений. При этом, если размеры эталона и зоны поиска равны NxМ  и  N1xМ1, то число точек, для которых вы­числяется функция взаимной корреляции, равно (N1–N+1)*(М1–М+1). Обыч­но это число является значительным. Во-вторых, функция корреляции может иметь размытый максимум, что затрудняет его обнаружение. В-третьих, шум на изображении может скрыть максимум корреляции. В-четвертых, если требуется обнаружение объекта, то эталонный фрагмент не должен содержать элементов фона, чтобы не произошло привязки по фону.

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

где ρС и ρR – коэффициенты корреляции между соседними по строке и столбцу элементами. В предельном случае, если ρС =ρR=1

, что представляет собой оператор Лапласа.

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

Часто классический алгоритм используется для обработки изо­бражений не в сигнальном пространстве, а в пространстве преобра­зований Фурье. В этом случае

,

где F-1 - символ обратного преобразования Фурье; G(wx, wy) и T(wx, wy) - преобразования Фурье изображений g(x, y) и t(x, y); * - символ комплексного сопряжения.

В более общем случае осуществляется «взвешивание» разностной меры спектральных компонентов с помощью функции h(wx, wy):

.

Точность локализации определяется крутизной кросс-спектральной функции вблизи экстремума, в предельном случае – это дельта-функции. Чтобы ее получить весовая функция должна иметь вид:

.

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

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

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

Таблица I. I

Соответствие между уровнем предсказуемости изобра­жения и используемым алгоритмом.

Уровень предсказуемости изображения	Возможные корреляционные алгоритмы
1. Интенсивности изображений могут быть предсказаны точно по отношению к абсолютному уровню.	Разностные алгоритмы (минимум квадрата разности, минимум модуля разности).
2. Разности интенсивностей могут быть предсказаны по отношении к абсолютному уровню, но возможно случайное смещение.	Разностные алгоритмы (нормализованные к среднему уровню).
3. Могут быть оценены относительные интенсивности (т. е. элемент i ярче, чем элемент j), но масштаб предсказать трудно.	Нормализованный классический алгоритм. Алгоритм амплитудного ранжирования.
4. Могут быть выделены области с различными интенсивностями, но относительные интенсивности непредсказуемы (т. е. возможно инвертирование интенсивности), могут иметь место непредсказуемые элементы, включая искажение перспективы.	Алгоритмы с предварительной обработкой текущих изображений (выделение контуров и других предсказуемых признаков).

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

,  где  p=0,1,2…

На практике чаще всего используются следующие алгоритмы

                                       (1.3)

                               (1.4)

                                       (1.5)

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

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

Моментами  (p+q) - го порядка двумерной функции является выражение вида

,                        где  p, q=0,1,2…

Последовательность моментов mpq  однозначно определяет кусочно-непрерывную функцию  f(x, y) на ограниченной плоскости  X - Y

Вычисление корреляционной функции в этом случае производится по формуле

где  mi - i-й момент первого изображения; ni(x, y)- i-й момент подобласти второго изображения в положении (x, у), k - количество рассматриваемых моментов.

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

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

В таблице 1.2 приведена классификация корреляционных алгоритмов, отмечены их преимущества и недостатки.

Таблица 1.2

Методы КЭ обработки	Подход к обработке изображений	Преимущества	Недостатки
Оптимальная пространственная фильтрация	Изображения фильтруются для оптимизации совмещения. Оптимальные фильтры конструируются с использованием типичных изображений.	Увеличенное отношение основного пика корреляционной функции к боковым. Гомогенность боковых лепестков. Возможность аналитического описания.	Основан на знании серого уровня изображения. Конструирование фильтра требует оценки статистики шума.
Фазовая корреляция	Площадная корреляция с использованием обратного преобразования Фурье взаимного энергетического спектра фазы.	Острые корреляционные пики. Эффективность реализации. Нечувствительность к узкополосному шуму.	Требует предсказания серого уровня изображений. Требует широкополосного сюжета изображений.
Бинарная корреляция	Изображения предварительно переводятся в бинарную форму.	Эффективная цифровая реализация. Снижение чувствительности к ошибкам в предсказании серого уровня.	Требует предсказания серого уровня изображений. Информативность изображений снижается из-за перехода к бинарным изображениям
Корреляция коэффициентов преобразований.	Обработка с помощью алгоритма минимальной абсолютной разности коэффициентов Адамара эталонного и текущего изображений.	Увеличение остроты пика. Снижение чувствительности к шумам.	Требует предсказания серого уровня изображений. Увеличение объема вычислений.
Оптический согласованный фильтр	Аналоговый согласованный фильтр с использованием когерентной обработки света.	Практически мгновенная корреляция. Исключительно большой объем памяти. Параллельная обработка нескольких эталонов.	Основано на использовании серого уровня. Гибкость обработки ограничена аппаратурной реализацией.
3-х мерная корреляция	Совмещение 3-мерной модели цели с данными активности дальномера.	Предсказание уровня серого не требуется. Может учитывать всевозможные азимуты подхода. Нечувствителен к преднамеренным изменениям признаков цели.	Требует датчика дальности. Значительный объем вычислений.
Совмещение относительных информативных векторов (ОИВ - характеризует каждый признак на основе близлежащих признаков).	Совмещение основано на максимизации соответствующих ОИВ.	Предсказание серого не требуется. Нечувствителен к инвертированию контраста. Минимальные требования к памяти.	Выделение признаков чувствительно к шуму. Аналитическое описание характеристик затруднено.
Совмещение структурных моделей.	Совмещаются структурные модели признаков (линии, сегменты, вершины, пятна и т. д.)	Предсказание серого уровня не требуется. Нечувствителен к инвертированию контраста.	Выделение признаков чувствительно к шуму. Аналитическое описание затруднено.

Выделение движущихся объектов.

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

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

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

Пусть значение яркости в точке с координатами (x, y) движущегося объекта в кадре с номером К есть Sk (x, y).

Предполагается, что яркость самого движущегося объекта от кадра к кадру не меняется. Тогда в случае поступательного движения, при котором формируется вектор перемещения с компонентами  dx, dy, межкадровые разности FD определяются выражением

FD(x, y)= Sk(x, y) - Sk-1(x, y) = Sk(x, y) - Sk(x+dx, y+dy)=

=-= - DT∇ Sk(x, y)- n(x, y)

где через n(x, y) обозначены члены высших порядков разложения в ряд Тейлора, которыми можно пренебречь, D – вектор перемещения. Градиент ∇S представляет собой вектор с составляющими в виде межэлементных разностей  ED  и межстрочных разностей  LD.

Рассмотрим одномерное перемещение объекта по оси x. В данном частном случае оценка вектора перемещения D сводится к

Если граница движущегося объекта известна, то межкадровую разность можно найти для всех элементов его изображения. Тогда, используя линейную регрессию и пренебрегая перекрестными членами по  x, y, можно аппроксимировать вектор перемещения D  выражениями

где статистическое усреднение выполняется суммированием по всей области движущегося объекта.

Алгоритм предполагает линейность функции яркости в точке (x, y). Это ограничивает применимость алгоритма областью измерения малых перемещений.

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

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

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

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

Такая модель служит хорошим отображением изменения изображения в случае наблюдения аэроландшафтов при горизонтальном полете, при сканировании траектории пикирования, и при вертикальном спуске летательного аппарата.

Данный метод был испытан на типичных изображениях авиационного ФЛИР'а. Эксперименты подтвердили работоспособность алгоритма в части выделения подвижной цели типа автотранспортных средств в присутствии таких помех, как облако поднятой ими пыли. Для борьбы с локальными помехами, в т. ч. с заслонением части объекта местными предметами, пыле-дымовыми образованиями, при отслеживании движущихся по окружающему фону целей используют метод локальной корреляции, в котором координаты и скорость целей определяются усреднением этих величин по неискаженной части цели.

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

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

Автосопровождение целей

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

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

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

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

Для более устойчивого слежения и возможности продолжать автосопровождение объекта в том случае, когда видна лишь часть объекта (например, при частичном заслонении, заезде за препятствие, затенении и т. п.) или он на некоторое время совсем пропадает из поля зрения вводится динамическая мера близости (ДМБ) D(i, j, t) с начальными значениями D(i, j,1) = 1 ∀ i, j:

Здесь τ1,τ2 > 0 - постоянные величины, число t-1 определяет количество перезаписей (количество сравнений) эталона, u(i, j, t) – значение кода точки (i, j) эталона на шаге t. При этом всегда .

Смысл функции D  состоит в том, что элементы эталона, не изменяющие свое значение от кадра к кадру, будут иметь больший "вес" по сравнению с остальными. При устойчивом слежении объект неподвижен относительно оси визирования (эталона), в то время как фон может перемещаться. Это приводит к тому, что в случае динамической цели элементы матрицы  D,  соответствующие объекту, будут иметь большие значения, нежели фоновые элементы. При исчезновении объекта функция D некоторое время сохраняет информацию о нем. Через некоторое количество кадров, определяемое величинами τ1 и τ2, информация об объекте стирается из кратковременной памяти, если объект снова не появится в поле зрения следящей системы. Значения матрицы D могут неограниченно расти, поэтому необходимо ограничить их рост некоторым пороговым значением. Это число определяется количеством сравнений эталона, после которого получается установившаяся матрица.

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

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

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

Может оказаться, что в эталон попадает только часть объекта. Может также оказаться, что объект полностью находится в эталонном изображении, но не находится на линии визирования (не в центре эталона). Задача коррекции захвата и целенаведения (или центрирования объекта) сводится к совмещению геометрического центра изображения объекта с центром эталона.

Определим координаты xQ  и yQ геометрического центра бинарного изображения:

 

где  n × n  - размер эталона, b(x, y) - яркость изображения в точке (x, y).

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

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

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