3.3. Алгоритмы при заданном наборе параметров модели пространственных деформаций

Если вид ПД известен, то при выбранной ЦФ задача сводится к определению параметров

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

-мерная сетка. При этом для коррелированных зашумленных изображений критерием качества оценивания может служить минимум СКМР (3.32) [103,105]. При значительных шумах и наличии межкадровых яркостных искажений, близких к линейным, когда критерий (3.32) неприменим, может быть рекомендовано использование критерия максимума ВКМК (3.34). Случаи, когда и (3.32) и (3.34) не отражают качества оценивания рассмотрены в разделе 3.5.

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

на противоположное (треугольная развертка), чтобы при обходе обрабатываемые точки изображения были максимально коррелированы между собой. После определения порядка обхода отсчеты изображения оказываются пронумерованными и становится возможным применение адаптивных ПГА вида (3.3). Например, при выборе в (3.3) ЦФ СКМР и ПГ (3.30), (3.41) и (3.39) приходим соответственно к алгоритмам

- локальная выборка ЦФ на итерации ПГА; -объем двумерной локальной выборки . Для нахождения оценок производных изображения по параметрам могут быть использованы приближения (3.47), (3.49), (3.51) и другие, полученные в разделе 3.2.

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

Структурная схема измерителя параметров реализующего алгоритм (3.59) приведена на рис. 3.3. Она содержит функциональный преобразователь где - оценка СКМР на итерации, определяемая соотношением (3.54), релейный преобразователь, реализующий функцию а 1и задающий направление шагов алгоритма, величина которых определяется нелинейным преобразователем Оценки формируются с помощью дигратора.

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

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

Алгоритм (3.59) исследовался на ряде имитированных и реальных изображений и показал достаточно высокие результаты [16,49,56]. Например, на изображениях размером элемента, сформированных с помощью волновой модели сдвинутых на несколько шагов сетки отсчетов и повернутых на любой угол, даже при сдвиг оценивался с СКО порядка шага сетки

Рис. 3.3. Структурная схема измерителя параметров на базе релейного ПГА.

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

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

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

Набор алгоритмов (3.59) дополним также алгоритмом с ПГ (3.42)

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

Испытания алгоритмов (3.57) (3.59) и (3.61) на широком классе имитированных и реальных двух- и трехмерных изображений показали, что лучшие результаты показывают алгоритмы (3.59) и (3.61), причем для однородных изображений целесообразно применять (3.59), а для неоднородных - (3.61) с постоянными [103,104,105]. Для уменьшения влияния дефектов

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

некоторое усечение

где величина положительного выбирается, например, исходя из некоторого доверительного интервала для значений остатков компенсации. Заметим также, что для алгоритмов (3.57) (3.59) и (3.61) выполняются достаточные условия сходимости к с вероятностью единица.

При выборе в качестве ЦФ ВКМК и ПГ (3.31) и (3.50) получаем соответственно алгоритмы

Свойства алгоритмов (3.63) и (3.64), в целом, аналогичны свойствам алгоритмов (3.57) и (3.59), однако они более устойчивы к шумам и близким к линейным межкадровым яркостным искажениям, но требуют также и больших вычислительных затрат (в основном за счет существенно большего объема локальной выборки ЦФ), а также более чувствительны к локальным экстремумам ЦФ.

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

На рис. 3.5 приведены графики вероятности выхода погрешности

оценки 1 за пределы интервала для случая оценивания параметров параллельного сдвига и с помощью алгоритма (3.69). При этом расчет проводился для гауссовских изображений с гауссовидной КФ радиуса корреляции при . Здесь и далее под радиусом корреляции изотропного изображения будем понимать величину при которой где - КФ изображения. В алгоритме (3.59) принято и . Величина шага в одном случае была выбрана постоянной , а в другом - уменьшающейся по закону . Из анализа графиков следует, что при постоянном начиная с некоторого наступает "равновесие" между стремлением оценки к истинному значению и погрешностью, вносимой . Дальнейшее увеличение итераций уже не приводит к улучшению оценок. Этот эффект можно использовать для определения и обеспечивающих требуемую точность оценивания переменных параметров. На рис. 3.6, а и рис. 3.6, приведены зависимости ПРВ погрешности оценивания сдвига от числа итераций соответственно для постоянного и уменьшающегося Для наглядности дискретные значения представлены в виде элементарных параллелепипедов только для некоторых из диапазона . При хорошо заметен эффект стабилизации погрешности оценки (начиная с ). При изменяющемся параметре дисперсия оценки начиная с некоторого уменьшается

пропорционально что соответствует асимптотической скорости сходимости алгоритма (3.59).

На рис. 3.7 приведены ПРВ оценок сдвига угла поворота и коэффициента масштаба (рассчитанные для тех же модели изображений и алгоритма, что и в предыдущем примере) при следующих параметрах: . Шаг изменения оценок параметров выбран постоянным величина . Принимая за условное начало координат полярной системы центр изображения координаты отсчета в этой системе можно записать как где -угол. План расположения опорных отсчетов следующий. Координаты точки выбираются случайным образом на расстоянии от . Координаты выбираются как . При все ПРВ оценок параметров, показанные на рис. 3.7, стабилизируются и дальнейшее увеличение практически не приводит к уменьшению погрешности оценивания. Заметим, что как скорость сходимости оценок, так и их дисперсия существенно зависят от плана локальной выборки . Правило выбора точек плана должно минимизировать коррелированность оценок параметров. Так для случая и приведенного выше набора параметров выбор плана позволяет минимизировать коррелированность оценок параметров и . Для этого плана на рис. 3.8 приведены зависимости математических ожиданий и погрешностей оценок и от числа итераций (кривые ). На этом же рисунке для сравнения приведены аналогичные зависимости (кривые 2) для плана . Заметим, что при таком плане оценки более коррелированы,

что ухудшает их сходимость. Это подтверждают и кривые 2 на рис. 3.8. Более

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

При этом процесс в целом сходится монотонно. Комплексным

критерием, характеризующим процесс сходимости оценок, может служить ПРВ коэффициента корреляции между и .

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

Рис. 3.8. Зависимость математического ожидания погрешности оценок от числа итераций (план расположения и : для 1 - для 2 - ).

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

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

Рис. 3.9. Пример обработки бинарных изображений.

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

Псевдоградиентные алгоритмы с изменяющимся объемом локальной выборки целевой функции

В ряде случаев для обеспечения заданной скорости сходимости ПГА требуется большой объем локальной выборки . Наиболее характерно это при максимизации ВКМК, когда требуется достижение нужной точности оценок параметров а за относительно небольшое число итераций ПГА или ограниченное машинное время. Увеличение может использоваться и для борьбы с локальными экстремумами . Иногда

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

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

В качестве величины, определяющей значение на итерации, выберем значение а, оценки ЦФ (3.35). Тогда в качестве ПГ ЦФ целесообразно использовать (3.56), дополнив его знаковой функцией для обеспечения устойчивости оценок параметров в условиях шумов

где - среднее значение отсчетов

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

Тогда ПГА с изменяющимся объемом локальной выборки ЦФ для параметра а может быть записан в виде:

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

на каждой итерации - к новой совокупности отсчетов .

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

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

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

используется более простое правило формирования

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

Рис. 3.10. Структурная схема измерителя параметров реализующего алгоритм (3.65).

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

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

Рис. 3.11. Структурная измерителя параметров ПД, реализующего алгоритм (3.58).

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

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

На рис. 3.13 приведена усредненная по реализациям зависимость объема локальной выборки ЦФ от рассогласования истинного положения

Рис. 3.13. Зависимость объема локальной выборки и числа итераций от

Рис. 3.12. Пример результатов поиска местоположения фрагмента. (1 - зависимость от и от соответственно при и о - экспериментальные результаты при ).

центра фрагмента и его оценки при к=1.25, и начальном рассогласовании (кривая 1). Хорошо видно, что возрастает только при относительно небольших . На том же рисунке показаны зависимости от номера итерации кружочки соответствуют усредненному по реализациям номеру итерации, а кривая 3 отражает математическое ожидание номера итерации, рассчитанное по методике анализа точности ПГА при конечном числе итераций. При расчете использовалась модель гауссовских изображений с гауссовской же КФ радиуса корреляции 5 и отношением дисперсии сигнала к дисперсии шума, равном 0.01. Параметры алгоритма и начальные приближения вектора параметров соответствовали экспериментальным. Кривая 2 также получена аналитически и соответствует математическому ожиданию номера итерации для ситуации . Видно хорошее соответствие экспериментальных и аналитических результатов (кружочки и кривая . Алгоритм с достигает 0.3 в среднем за итераций. Алгоритм с изменяющимся обеспечивает то же качество оценивания при итерациях (кривая но затраты машинного времени оказываются в раза ниже.

Таким образом, регулирование объема локальной выборки ЦФ в процессе работы ПГА позволяет существенно снизить вычислительные затраты. В рассмотренных алгоритмах в качестве ЦФ использовался ВКМК. Однако принципы построения алгоритмов с регулируемым объемом локальной выборки ЦФ применимы и для других в частности СКМР. Ряд разработанных алгоритмов реализован в пакетах прикладных программ по обработке изображений [106].