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

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

Адаптивный байесовский подход к задаче оценивания пространственно-временных деформаций изображений

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

Для нахождения оптимального вектора а параметров межкадровых ПД в соответствии с принятой в разделе 1.1 моделью формирования последовательности кадров МИ (рис. 1.2) необходимы модель наблюдения изображений к и модель преобразования координат отсчетов, определяемая вектором параметрами а, и критерий оптимальности. Разность выходных величин объекта исследования (наблюдаемого изображения ) и оценок к образует невязку

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

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

где - функция потерь. Критерий качества (1.41) представляет собой средние потери; чем они меньше, тем лучше оценены параметры.

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

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

где оператор

является вектор-столбцом, а - размерность вектора упрощения записи в (1.43) полагается

Векторы

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

входящие в (1.43), представляют собой матрицы Гессе - матрицы вторых производных средних потерь и функции потерь. Матричное неравенство (1.43) означает положительную определенность матрицы Гессе. Учитывая

условие оптимальности можно записать в виде

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

алгоритма меняются в зависимости от характеристик обрабатываемых данных.

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

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

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

Рис. 1.4. Структурная схема адаптивного оценивания межкадровых ПД.

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

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

Итеративные и рекуррентные алгоритмы оценивания параметров деформаций

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

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

где - матрица усиления; а - начальное приближение вектора параметров. Конкретный алгоритм определяется выбором матрицы усиления . Так, скалярная матрица усиления

где - единичная матрица, соответствует градиентному методу. Обратная матрица Гессе (1.44)

соответствует методу Ньютона, а матрица

- модифицированному методу Ньютона.

Если средние потери квадратичны по а, то алгоритм (1.47) соответствует методу Ньютона-Рафсона [30] и приводит к оптимальному решению а за одну итерацию при любом . В этом случае градиент средних потерь будет линейной функцией по и матрицы усиления (1.49) и (1.50) не будут зависеть от и .

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

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

можно записать в виде

Рис. 1.5. Структурная схема итеративного алгоритма.

где вид матрицы усиления определяется тем или иным вариантом метода стохастической аппроксимации. Так, скалярная матрица усиления

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

которые для широкого класса функций потерь и ПРВ помех обеспечивают сходимость (в вероятностном смысле) оценок рекуррентной процедуры (1.51) к оптимальному решению. Условиям (1.52) удовлетворяет, например,

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

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

Рис. 1.6. Структурная схема рекуррентного алгоритма.

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

Аргументные и критериальные алгоритмы адаптивного оценивания

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

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

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

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

Идентификационные и безыдентификационные алгоритмы

По методу нахождения оптимальных параметров адаптивные алгоритмы можно разделить на идентификационные и безыдентификационные [47]. При обработке случайных процессов и полей, большее распространение получили адаптивные алгоритмы с идентификацией [3,45,100,113]. В этих алгоритмах по имеющимся реализациям (наблюдениям) сначала оцениваются необходимые неизвестные характеристики у объекта обработки, например изображения. Затем полученные оценки используются как точные значения параметров некоторой модели объекта в рамках неадаптивного байесовского подхода [101], то есть принимается . В этом состоит суть большинства модифицированных байесовских решающих правил. В очень широком классе задач в качестве выбирают оценку МП.

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

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

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

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

Учитывая требования простоты, быстрой сходимости и работоспособности при значительных вариациях реальной ситуации, алгоритмы оценивания ПД больших МИ целесообразно искать в классе рекуррентных безыдентификационных адаптивных алгоритмов. Представительной группой таких алгоритмов являются адаптивные псевдоградиентные алгоритмы, к которым относятся, в частности, и алгоритмы типа стохастической аппроксимации [33]. К последним, в свою очередь, приводит выбор матрицы усиления вида

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

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