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

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

3.1. Описание и общие свойства псевдоградиентных алгоритмов

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

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

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

В алгоритме (3.1) каждый очередной шаг производится по направлению

наискорейшего спуска. При выполнении определенных условий [37,38] имеет место сходимость но она может оказаться слишком медленной. Для

ее ускорения можно выбрать направления, отличные от антиградиента, как это сделано, например, в методах Ньютона и сопряженных градиентов [7]. Однако, применению этих методов в обработке изображений препятствует необходимость многократных громоздких вычислений каждое из которых обычно включает в себя всю процедуру обработки при параметрах . Значительно сократить объем вычислений можно, если использовать вместо его усечение на некоторую часть реализации Например, в качестве можно взять скользящее окно. В этом случае в (3.1) на каждом шаге нужно производить меньше вычислений, но вместо точного значения будут использоваться значения градиента со случайной ошибкой

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

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

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

анализу и синтезу разнообразных алгоритмов стохастической минимизации функционалов, было введено Т. Поляком и Я. З. Цыпкиным в работе [36]. Класс ПГА адаптации очень широк и включает в себя алгоритмы стохастической аппроксимации, случайного поиска и многие другие.

В ПГА используется процедура [36]

Рис. 3.1. Градиент и псевдоградиент.

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

Направление в называется ПГ функционала в точке если выполнено условие [36]

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

минимума . Действительно, выполнение некоторых относительно слабых

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

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

Если градиент средних потерь известен (условие оптимальности (1.42) полностью определено), то итерационный алгоритм (1.47) будет псевдоградиентным при выборе диагональной матрицы усиления вида [66]

Для рекуррентных алгоритмов (1.51) псевдоградиентному подходу соответствует положительно определенная матрица усиления

В частности, если - единичная матрица, то

а при имеем

К рекуррентному ПГА стохастической аппроксимации приводит матрица усиления (1.54). При этом скалярный множитель в (3.6), а также в (1.54) также

Рис. 3.2. Структурная схема измерителя параметров межкадровых ПД изображений.

должны удовлетворять условиям (2.53).

Как уже отмечалось, не всегда целью является приближение к иногда достаточно только потребовать, чтобы было достаточно близко к то есть чтобы качество обработки было близко к потенциально достижимому . Вопросы критериальной сходимости ПГА исследованы в [38]. Отметим, что условия критериальной сходимости несколько слабее условий сходимости аргументной. Скорость сходимости в обоих случаях, как правило, имеет обычный для стохастических алгоритмов порядок хотя для критериальных алгоритмов она часто несколько выше, чем для аргументных.

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

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

например, алгоритмами калмановской фильтрации. Действительно, (3.9) можно представить в виде (3.3)

где в соответствует . Таким образом, существенным является не форма записи (3.3), а переход к следующим значениям параметров в среднем в сторону улучшения ожидаемого результата. Поэтому многие известные итерационные адаптивные алгоритмы, в том числе и адаптивный метод наименьших квадратов, могут быть отнесены к классу псевдоградиентных [27,35,64,73,85,86, 90,95 и др.].

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

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

обрабатывается с постоянными параметрами. Такая обработка оптимальна,

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

Отмеченные качества адаптивных ПГА делают их привлекательными для применения в обработке . Различные модификации ПГА оценивания ПД

изображений последовательности кадров проанализированы в разделах 3.3 и 3.4.

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

Для вычисления тензорных коэффициентов рекуррентного уравнения (1.24) оценивания вектора параметров приведенного в разделе 1.4, требуется задание моделей МИ и ПД. Если параметры этих моделей не заданы, то оценить их можно по имеющимся наблюдениям, то есть использовать идентификационный подход к адаптации. Однако такой подход чрезвычайно громоздок, особенно в случае неоднородных . Другим подходом к получению адаптивных алгоритмов в данных условиях является использование . Для этого введем сводный набор параметров к состоящий из тензорных коэффициентов уравнений (1.25) и (1.27).

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

где оптимальные значения тензоров неизвестны и их требуется найти.

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

можно применить адаптивный ПГА (3.3), взяв, например, ПГ

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

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

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

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