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

На правах рукописи

МУРАТХАНОВ Дмитрий Сосович

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

Специальность: 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Ульяновск - 2004

Работа выполнена на кафедре «Радиоэлектроника» Ульяновского филиала Военного университета связи

Научный руководитель: доктор технических наук,

профессор Ташлинский А.Г.

Официальные оппоненты: доктор физико-математических наук,

профессор Валеев С.Г.

кандидат технических наук, доцент Борисов С.Г.

Ведущая организация: ФГУП НПО «Марс» (г. Ульяновск)

Защита состоится 17 марта 2004 г. в 15.00 на заседании диссертационного совета Д 212.277.02 при Ульяновском государственном техническом университете по адресу: 432027, Ульяновск, ул. Северный Венец, 32, ауд. 211.

С диссертацией можно ознакомиться в библиотеке Ульяновского государственного технического университета.

Автореферат разослан "АЗ " 02. 2004 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

Крашенинников В.Р.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

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

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

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

о векто-

:астей. В

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

Цель и задачи исследований

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

Для достижения цели исследования необходимо решить следующие задачи:

1. Разработать методику структурной оптимизации ПГА поиска ^подобласти в произвольной области определения параметров МГДИ, направленную на уменьшение вычислительных затрат.

2. С использованием разработанной методики построить ПГА поиска ^подобласти.

3. Разработать алгоритм проверки гипотезы об отсутствии в области определения МГДИ искомого вектора параметров.

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

Методы исследований

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

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

2. Впервые разработан алгоритм проверки гипотезы об отсутствии в области определения МГДИ ^подобласти. Получены расчетные соотношения для параметров алгоритма, обеспечивающих заданные вероятности ошибок первого и второго рода.

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

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

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

Практическая ценность и использование результатов работы

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

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

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

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

Реализация результатов работы

Результаты диссертационной работы использованы в научно-исследовательском проекте 209.01.01.072 «Рекуррентное оценивание параметров пространственных деформаций последовательностей многомерных изображений» программы «Научные исследования высшей школы по приоритетным направлениям науки и техники», а также при выполнении хоздоговорных НИР 2/2000-ПИТ "Методы представления и статистического анализа многомерных изображений" и 2/2001-ПИТ "Методы и адаптивные алгоритмы оперативного обнаружения аномалий на изображениях и в многомерных сигналах, заданных на сетках со случайными деформациями", проводимых в рамках проекта 0201.05.237 направления "Распознавание образов и обработка изображений" Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения".

Разработанная методика структурной оптимизации алгоритмов определения параметров МГДИ при области определения возможных значений параметров, превосходящей рабочий диапазон измерительной процедуры, реализованная в форме алгоритмически-программного обеспечения внедрена в деятельность Института систем обработки изображений РАН (г. Самара). Кроме того, некоторые полученные результаты применяются в учебном процессе Ульяновского государственного технического университета при изучении дисциплины «Цифровые методы обработки изображении» для направления 657100 «Прикладная математика».

Достоверность результатов

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

Основные положения, выносимые на защиту

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

2. Синтезированы ПГА поиска V-подобласти МГДИ, осуществляющие поиск с заданной достоверностью.

3. Разработан алгоритм проверки гипотезы об отсутствии V-подобласти в области определения МГДИ, обеспечивающий требуемую вероятность ошибки первого или второго рода.

4. Получены соотношения для расчета вероятности ошибочного выбора V-подобласти через пороговое число итераций ПГП.

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

Апробация работы

Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на международных конференциях "Континуальные логико-алгебраические и нейросетевые методы в науке, технике и экономике" (г. Ульяновск, 2000), "Распознавание образов и анализ изображений: новые информационные технологии" (г. Самара, 2000, г. Великий Новгород, 2002), "Contemporary information technologies" (г. Пенза, 2000), "Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике" (г. Ульяновск, 2002, 2003), на 56 и 57 Международных сессиях, посвященных Дню радио (г. Москва, 2001, 2002), III Всероссийской научно-практической конференции (с участием стран СНГ) "Современные проблемы создания и эксплуатации радиотехнических систем" (г. Ульяновск, 2001).

Публикации

По теме диссертации опубликовано 16 работ, в том числе 7 статей, всего 4.1 печатных листа.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы из 101 наименования и приложения. Содержит 150 страниц машинописного текста, 21 рисунок и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

а^ам-ЛДСЗ). (!)

где а - вектор оцениваемых параметров геометрических деформаций; А, -матрица усиления, а0 -начальное приближение вектора параметров;

- псевдоградиент целевой функции (ЦФ) Q , характеризующей качество оценивания.

Рассмотрены известные оптимальные алгоритмы оценивания параметров МГДИ изображений в условиях шумов, которые на современном этапе нереа-лизуемы из-за чрезмерной вычислительной сложности. Однако на основе оптимальных алгоритмов можно получить ЦФ для рекуррентного оценивания МГДИ. В предположении реализуемости в системах реального времени в качестве ЦФ ПГА целесообразно выбирать: при отсутствии яркостных искажений изображений - средний квадрат межкадровой разности (СКМР); при межкадровых яркостных искажениях близких к линейным, - выборочный коэффициент межкадровой корреляции (ВКМК).

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

мационного изображения {д^} и независимого гауссовского шума {0^}:

сетка отсчетов; а - вектор неизвестных параметров МГДИ. Для повышения быстродействия при нахождении псевдоградиента Р(б) указанные алгоритмы на каждой t-й итерации используют небольшие локальные выборки ЦФ ¡2

где Z — непрерывное изображение, интерполяционно полученное из Z^ .

В практических задачах оценивания МГДИ из-за ограниченности вычислительных ресурсов требуемая точность оценок параметров а МГДИ достигается не во всей области П(а) возможных значений а , алишь в некоторой подобласти С1р (а), ограниченной рабочим диапазоном ПГП. Это приводит к необходимости разбиения области П(а) на N подоблаединение рабочих диапазонов всех ПГП должно полностью покрывать заданную область), соответствующих рабочему диапазону процедур, где а^ - начальное приближение МГПИ для ПГП, работающей в i -й подобласти. Процедуру, работающую в У-подобласти (цодобласти, которой принадлежит искомый вектор аи параметров МГДИ), будем называть У-процедурой. Подобласти, не включающие а,, будем называть Р-подобластями (от р8еиёо-ложная), а соответствующие ПГП - Р-процедурами. В результате работы всех ПГП формируется N векторов 1 = 1,^, оценок параметров МГДИ и возникает задача определения среди них с требуемой доверительной У-подобласти, в которой достигается экстремум ЦФ. Решению этой задачи в основном и посвящена диссертационная работа.

Во второй главе предложена новая методика структурной оптимизации алгоритмов поиска V-подобласти, направленная на сокращение вычислительных затрат. Получены рекуррентные выражения для расчета плотности распределения вероятностей (ПРВ) ФШ, которые конкретизированы для ЦФ, характерных при оценивании параметров МГДИ, в частности, ВКМКиСКМР.

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

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

Исследованы требования к ФШ у, позволяющие сравнивать значения «штрафа» ПГП, выполнивших разное число итераций. Показано, что если при решении задачи оценивания МГДИ выбрана ЦФ, подлежащая минимизации, то таким требованиям удовлетворяет функция

(2)

где (¿^йа^^Ц - величина, меньшая нижней границы множества 1^,7 = 1,?} значений оценок ЦФ (). Если выбрана функция, подлежащая максимизации, то требованиям удовлетворяет

где б™, ^ир)^0).

В процессе сходимости оценок параметров МГДИ к истинным значениям изменяются вероятностные свойства оценок ЦФ, соответственно изменяются и вероятностные свойства ФШ. Поэтому при исследовании и опттимизации необходимо для каждой г -й итерации знать ее ПРВ 'И'((\1/):, которая определяются

правилом формирования локальной выборки ЦФ Хг = качестве ме-

ры соответствия величин , входящих в локальную вы-

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

^ (Ду) = |м<Ду1 р)н<р)ф, (4)

где и{Ду|р) - условная ПРВ приращения; и{р) - ПРВ коэффиириента корреляции. Для У-процедур н^Ду1 р) зависит от номера итерации, т.к. по мере сходимости вектора оценок а к истинным значениям р увеличивается

Приняв, что ФШ может принимать только положительные значения, для ПРВ ФШ на ? -й итерации У-процедуры получим рекуррентное соотношение

IV, (у)=]и-м (у-Ду, Мду) ЙДV = ] к.1 (у-Ду, V» (АУI рМр>) ^ Ф • (5) Для Р-процедур ЦДу)='Н'((Ду|р = о) не зависит от номера итерации

10

Получены выражения для расчета ПРВ ФШ для ЦФ, характерных при оценивании параметров МГДИ, в частности, для СКМР и ВКМК. В качестве примера на рис. 1 приведены кривые условной ПРВ н{Д\(/|р) приращения А у СКМР при р=0.5, 0.6, 0.8 и 0.9, объеме локальной выборки ЦФ ц = 4, радиусе корреляции Л гауссовских изображений Х^ и Х^, равном 5 шагам сетки отсчетов, и отношении дисперсии сигнала к дисперсии шума, равном 100. Примеры ПРВ ВКМК при тех же параметрах изображений, ц= 7 и числе итераций 10, 40 и 80 для У-процедуры (у)) и Р-процедуры (м'Л(\(/)) приведены на рис. 2. Сувеличе-нием числа итераций площадь пересечения ПРВ и ^^(у) резко умень-

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

Рис. 2.

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

Если: априорно неизвестно наличие ^подобласти в исследуемой области определения параметров МГДИ, то возникает задача проверки гипотезы, что среди N исследуемых подобластей области определения нет ^подобласти. Для ее решения использован простой статистический критерий: если за шаговЛ/,^, алгоритма ни одна из N ПГП не достигла Тм-й итерации, то

среди исследуемых подобластей нет подобласти ^типа. Выбор величин Тм и

Мк0 позволяет обеспечить необходимые вероятности ошибок первого (Р^) и

второго (Ррода.

Для нахождения вероятностей Р^ и Р^ необходимо знать дискретные

распределения Рп и РР1, 7 = 1 ,ТМ числа итераций для V- и Р-процедур при заданных Тм и Мкр, где - вероятность того, что У(Р)-процедура выполнила t итераций при числе N используемых ПГП и Мкр шагах алгоритма. Показано,

Рр(у)г = К„ (уХ1 - - ¿^(К),; (7)

где ^/»(к)* С'Ч') ~ ~ функция распределения ФШ на ?-й итерации для

Р(У)-нроцедуры; м>тм (у) = wm, (ч^Х1 ~ рртм МУ'1 + (ч'Х1 ~ рутм М)

ПРВ значений ФШ на Тм-й итерации, - ПРВ минимального из

N - 1)-го значений ФШ Р-процедур на Тм -й итерации. Тогда при заданных Тм и АГ„

(8)

Исследована вероятность Р^ ошибочного выбора У-подобласти при использовании методики структурной оптимизации ПГА оценивания МГДИ. Так, при N подобластях для случая наличия в области определения параметров У-подобласти и предположении о независимости значений ФШ Р-процедур для верхней границы получаем

(9)

На рис. 3. для примера приведены графики вероятности Рош¡г пропуска

искомого фрагмента на опорном изображении, когда рабочий диапазон ПГП требовал разбиения области МГДИ на 2, 50 и 1000 подобластей. Параметрами МГДИ являлись параллельный сдвиг искомого и эталонного фрагментов и угол поворота ф между ^-З. ними. Графики соответствуют 400 итерациям ПГП, начальному приближению сдвига в 5 шагов сетки отсчетов и изменению начального приближения угла поворота от 0 до 25

градусов По графикам можно определить, например, предельный угол поворота, при котором обеспечивается требуемая Р0цК. С уменьшением ф^ указанная

Фо=10° и N=50 - Рвш]гй

а при

вероятность уменьшается, так при

N = 1000 - Р01и]У < 10~3.

Для анализа вычислительных затрат структурно оптимизированных ПГА найдены дискретные распределения вероятностей }, ¿ = 1,Т, числа итераций, выполненных ПГП для ситуаций наличия

р, = К^-^л^-'ёЧ, (10)

и отсутствия

»-1

р, = НУШ-РгМу-^

(11)

О '

в области определения искомого вектора параметров, где >УГ(у) = (уХ1 -Рп(у))""' + Ч^0(^Х1 - ргг(у)); - ПРВ минималь-

ного из (N-1) -го значения ФШ Р-процедур на Г-й итерации.

Примеры дискретных распределений }, ¡ = 1,99, рассчитанных по формулам (10) и (11) для задачи поиска фрагмента на изображении с Я = 5, приведены на рис. 4 и рис. 5. Расчет проведен для 100 итераций лидирующей процедуры при начальном сдвиге фрагмента относительно центра подобласти в 6 шагов сетки отсчетов, выборе в качестве ЦФ ВКМК и отношении дисперсии сигнала к дисперсии шума на опорном изображении, равном 100. При заданном числе подобластей по распределениям легко найти общее число итераций всех ПГП, что позволяет оценить вычислительные затраты. На том же рисунке приведены экспериментальные результаты, показанные в виде кружков, которые получены на моделированных гауссовских изображениях при разбиении области изображения на 900 подобластей и усреднении по 200 реализациям. Видно, что наблюдается хорошее соответствие теоретических и экспериментальных результатов.

Анализ показал, что использование структурной оптимизации позволяет существенно сократить вычислительные затраты ПГА, при этом выигрыш в затратах растет с увеличением области МГДИ. Так, для изображении с гауссовской КФ с Я = 5 при 1000 итерациях ПГП выигрыш А по быстродействию по сравнению со случаем; когда все ПГП достигают порогового числа итераций, составляет: при N= 50 - 1.6 раза, N= 200 - 2.5 раза, при N= 1000 - 5.3 раза. Графики выигрыша А при указанном пороговом числе итераций приведены на рис. 5.

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

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

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

Упрощенная блок-схема алгоритма приведена на рис. 6. На первом этапе алгоритма выбирается ЦФ и вида ПГП (шаг 1), задается закон Л, изменения

оценок параметров а = (А],Й2,фд]Г (шаг 2), область £2 определения параметров (А1,А2,ф,А) разбивается на подобласти О,, 1 = 1,N. (шагЗ), каждой подобласти присваивается ПГП а^ ¿¡=1,ЛГ, с начальным приближением век-

тора измеряемых параметров = а10 (шаг 4). Затем с использованием структурной оптимизации (шаги 5-8) ищется подобласть изображении, соответст-

Рис. 5.

вуюшая эталонному фрагменту. При этом на шаге 5 осуществляется ранжирование значений' *|/(1 I = ФШ11111 по возрастанию, на шаге 6 определяется минимальное из значений ФШ, на шаге 7 для ПГП с минимальным производится очередная итерация и вычисляется новое значение у, (шаг 8). Оптимизация алгоритма осуществляется до выполнения одного из условий 9 или 12. Условие 9 определяет достижение заданной вероятности Р^, ошибки в выборе фрагмента изображения, задаваемой пороговым числом итераций Г,- Если ^ < Г], осуществляется проверка гипотезы об отсутствии на исследуемом изображении искомого фрагмента (условие 12, где М - общее число итераций всех ПГП; М„ - пороговое число для заданной вероятности Р® ошибки первого

рода) Если М = Мкр , принимается решение об отсутствии искомого фрагмента, если же М < Мкр, то выполняется очередная итерация. При /, £ 7], М < М„р фрагмент считается найденным с заданной вероятностью Рош ошибки.

На втором этапе алгоритма с требуемой точностью измеряются параметры (л,,А2,Ф,а) местоположения найденного фрагмента. При этом продолжает работу только ПГП, соответствующая найденному фрагменту (шаг 11). Условием достижения заданной точности является выполнение этой процедурой Т2 итераций (условие 10). Заметим, что пороговое значение Г, может быть больше Тг.

Осуществлена программная реализация алгоритма. Пример использования разработанного программного обеспечения приведен на рис. 7. Здесь размер изображения таблетки радиоактивного топлива, полученного с помощью электронного микроскопа, составляет 180x180 элементов, эталонного фрагмента 42x42 элемента Точные и найденные параметры МГДИ и межкадровые ярко-стные искажения (ст,/о0 - отношение среднеквадратических отклонений яркости эталонного и искомого фрагментов) приведены в таблице.

Табл.

Параметры (Ai. Ф к

Точные (100,100) -30° 0.8 1.15

Оценки (99.99,99.81) -2994° 0.799 Не оценивались

Эталонный фрагмент

Найденный фрагмент •У*IV

Программа позволяет производить быстрый поиск фрагмента на стандартных ПЭВМ. Так, при реализации в среде Borland С, C++ для Windows время поиска местоположения фрагмента размером 90x90 элементов на изображении

Рис.7

2048x2048 элементов, имеющего поворот в пределах ±90° и изменение масштаба в пределах 0.65 --1.35, составляет примерно 20 сек. при вероятности выбора ложного фрагмента менее 3 • 10-5 и использовании ПЭВМ класса Pentium 1700 МГц.

В заключении приведены основные результаты и выводы, имеющие научную и практическую ценность.

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

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

2. Получены рекуррентные соотношения для расчета ПРВ ФШ при использовании в качестве ЦФ выборочного коэффициента межкадровой корреляции и среднего квадрата межкадровой разности.

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

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

5. Проведен анализ вычислительных затрат структурно оптимизированных алгоритмов. Для этой цели найдены дискретные распределения вероятностей числа итераций, выполненных ПГП при наличии и отсутствии в области определения искомого вектора параметров. Показано, что использование структурной оптимизации позволяет значительно сократить вычислительные затраты. При этом выигрыш в быстродействии растет с увеличением числа подобластей МГДИ. Например, при 1000 итераций лидирующей ПГП и разбиении области определения параметров на 50 подобластей выигрыш по быстродействию со-

ставляет 1.6 раза, при разбиении на 200 подобластей - 2.5 раза, при разбиении на 1000 подобластей - 5.3 раза (для изображений с гауссовской КФ с R = 5).

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

7. Разработанные алгоритмы поиска подобласти МГДИ, содержащей искомый вектор параметров, требуют небольших вычислительных затрат и могут быть непосредственно использованы в различных прикладных задачах обработки изображений. Приведен пример программной реализации алгоритма автоматизированного поиска местоположения фрагмента на изображении при наличии между изображением и фрагментом геометрических деформаций и ярко-стных искажений. В среде Borland С, С++ для Windows время поиска фрагмента размером 90 х 90 элементов на изображении 2048 х 2048 элементов, имеющего поворот до ±90° и изменение масштаба в пределах 0.65 4-1.35, составляет примерно 20 сек. при вероятности выбора ложного фрагмента менее 3 • 10-5 и использовании компьютеров класса Pentium 1700 МГц.

В приложении приведен алгоритм расчета распределения вероятностей выборочного коэффициента корреляции локальной выборки ЦФ и примеры расчета.

Опубликованные работы по теме диссертации:

1. Гиниятуллин Н.Ф., Гиниятуллин Ф.Г., Муратханов Д.С. Анализ эффективности непараметрического алгоритма оценивания векторов сигнала / Известия высших учебных заведений "Радиоэлектроника", Киев, № 10, 2001. -С. 7-15.

2. Ташлинский А.Г., Муратханов Д.С. Структурная оптимизация алгоритмов оценивания параметров геометрических деформаций изображений / Приложение к журналу "Физика волновых процессов и радиотехнических систем" -Самара, 2001.-С. 102.

3. Ташлинский А.Г., Муратханов Д.С. Приоритетный подход при оценивании параметров пространственных деформаций двух изображений / Научно-технический калейдоскоп. Серия "Приборостроение, радиотехника и информационные технологии", 2000, № 1. - С. 90-94.

4. Ташлинский А.Г., Наскальнюк А.Н., Муратханов Д.С. Структурная оптимизация псевдоградиентных алгоритмов в задаче оценивания геометрических деформаций изображений / Вестник УлГТУ, № 4,2001. - С. 4-6.

5. Ташлииский А.Г., Муратханов Д.С., Тихонов В.О. Применение приоритетного метода при измерении межкадровых пространственных деформаций изображений / Труды Ульяновского научного центра "Ноосферные знания и технологии".- Т. 3, Выпуск 1, Ульяновск, 2001. - С. 66-68.

6. Tashlinskii A.G., Gorin A.A., Muratkhanov D.S., Tikhonov V.O. Priority Approach to the Estimation of the Parameters of the Spatial Image Distortions. / Pattern Recognition and Image Analysis, Vol. 11, No. 1,2001. - Pp. 251-253.

7. Tashlinskii A.G. and Muratkhanov D.S. Structural Optimization of Pseudogradient Algorithms for Measuring Interframe Image Deformations / Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003. - Pp. 177-178.

8. Муратханов Д.С. Структурная оптимизация алгоритмов при оценивании геометрических деформаций изображений // Современные проблемы создания и эксплуатации радиотехнических систем: Труды 3 Всероссийской научно-практической конференции (с участием стран СНГ). - Ульяновск: УлГТУ, 2001. -С. 129-131.

9. Ташлинский А.Г., Муратханов Д.С. Использование приоритетного метода при оценивании геометрических деформаций изображений // Нейронные сети и искусственный интеллект в задачах науки, техники и экономики: Труды междунар. конф. "Континуальные логико-алгебраические и нейросетевые методы в науке, технике и экономике". - Ульяновск: УлГТУ, 2000. - Том 2. -С. 96-97.

10. Ташлинский А.Г., Горин АА, Муратханов С.Д., Тихонов В.О. Приоритетный подход при оценивании параметров пространственных деформаций изображений // Распознавание образов и анализ изображений: новые информационные технологии: Труды 5 Международной конф. в 4 томах. - Самара: СГАУ, Т.2. -2000.- С. 396-398.

11. Ташлинский А.Г., Тихонов В.О., Муратханов С.Д. Анализ эффективности оценок пространственных деформаций изображений, полученных с помощью псевдоградиентных алгоритмов // Информационные технологии в математических исследованиях: Труды международной научно-технической конференции "Contemporary information technologies". - Пенза: ПТИ, 2000. - С. 8-10.

12. Ташлинский А.Г., Муратханов Д.С. Использование приоритетного метода при оценивании параметров пространственных деформаций изображений // Труды 56 сессии, посвященной дню радио, Т.2, М.: Радиотехника, 2001. -С. 325-327.

13. Ташлинский А.Г., Муратханов Д.С. Возможности структурной оптимизации рекуррентных алгоритмов измерения межкадровых деформаций изображений // Математические методы и модели в прикладных задачах науки и техники: Труды международной конференции "Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике", Т. 5, Ульяновск: УлГТУ, 2002. - С. 42-43.

14. Ташлинский А.Г., Муратханов Д.С. Структурная оптимизация псевдоградиентных алгоритмов измерения межкадровых деформаций изображений // Распознавание образов и анализ изображений: новые информационпые технологии: Труды 6 Международной конференции, Т. 2, Великий Новгород: ИПЦ НовГУ, 2002.-С. 549-551.

15. Ташлинский А.Г., Муратханов Д.С, Наскальнюк А.Н. Структурная оптимизация псевдоградиентных процедур оценивания межкадровых деформаций изображений // Труды научной сессии, посв. Дню радио. - М.: РНТОРЭС, 2002. - С. 145-146.

16. Ташлинский А.Г., Муратханов Д.С., Тихонов В.О. Структурная оптимизация алгоритмов псевдоградиентного оценивания параметров межкадровых деформаций изображений // Математические методы и модели в прикладных задачах пауки и техники: Труды международной конференции «КЛИН-2003» -Ульяновск: УлГТУ, 2003. -Том 5. - С. 105-107.

Муратханов Дмитрий Сосович

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

Автореферат

Подписано в печать 28.01.04. Формат 60x84/16. Бумага писчая. Усл.печ.л. 1,16. Уч.-изд.л. 1,00. Тираж 100 экз. Заказ 3725 Типография УлГТУ, 432027, г. Ульяновск, Сев.Венец, 32.

№-27 58

Список основных сокращений.

ВВЕДЕНИЕ.

Глава 1. МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ОЦЕНИВАНИЯ МЕЖКАДРОВЫХ ГЕОМЕТРИЧЕСКИХ ДЕФОРМАЦИЙ ИЗОБРАЖЕНИЙ.

1.1. Постановка задач и.

1.2. Модели межкадровых геометрических деформаций изображений

1.3. Подходы к оцениванию межкадровых геометрических деформаций изображений.

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

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

1.7. Выводы и постановка задач исследований.

Глава 2. СТРУКТУРНАЯ ОПТИМИЗАЦИЯ ПСЕВДОГРАДИЕНТНЫХ АЛГОРИТМОВ ОЦЕНИВАНИЯ ПАРАМЕТРОВ МЕЖКАДРОВЫХ ГЕОМЕТРИЧЕСКИХ ДЕФОРМАЦИЙ ИЗОБРАЖЕНИЙ.

2.1. Постановка задачи.

2.2. Принцип структурной оптимизации псевдоградиентных алгоритмов

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

2.4. Функции штрафа при оценивании параметров межкадровых пространственных деформаций.

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

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

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

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

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

Для достижения цели исследования необходимо решить следующие задачи:

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

2. С использованием разработанной методики построить ПГА поиска V-подобласти.

3. Разработать алгоритм проверки гипотезы об отсутствии в области определения МГД изображений искомого вектора параметров.

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

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

Научная новизна работы

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

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

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

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

Практическая ценность и использование результатов

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

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

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

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

Основные положения, выносимые на защиту

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

2. Синтезированы ПГА поиска V-подобласти МГД, осуществляющие поиск с заданной достоверностью.

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

4. Получены соотношения для расчета вероятности ошибочного выбора V-подобласти через пороговое число итераций ПГ процедур.

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

Реализация результатов. Результаты диссертационной работы использованы в научно-исследовательском проекте 209.01.01.072 «Рекуррентное оценивание параметров пространственных деформаций последовательностей многомерных изображений» программы «Научные исследования высшей школы по приоритетным направлениям науки и техники», а также при выполнении хоздоговорных НИР 2/2000-ПИТ "Методы представления и статистического анализа многомерных изображений" и 2/2001-ПИТ "Методы и адаптивные алгоритмы оперативного обнаружения аномалий на изображениях и в многомерных сигналах, заданных на сетках со случайными деформациями", проводимых в рамках проекта 0201.05.237 направления "Распознавание образов и обработка изображений" Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения". Разработанная методика структурной оптимизации алгоритмов определения параметров МГД изображений при области определения возможных значений параметров, превосходящей рабочий диапазон измерительной процедуры, реализованная в форме алгоритмически-программного обеспечения внедрена в деятельность Института систем обработки изображений РАН (г. Самара). Кроме того, некоторые полученные результаты применяются в учебном процессе Ульяновского государственного технического университета при изучении дисциплины «Цифровые методы обработки изображений» для направления 657100 «Прикладная математика».

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

Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на международных конференциях "Континуальные логико-алгебраические и нейросе-тевые методы в науке, технике и экономике" (г. Ульяновск, 2000), "Распознавание образов и анализ изображений: новые информационные технологии" (г. Самара, 2000, г. Великий Новгород, 2002), "Contemporary information technologies" (г. Пенза, 2000), "Континуальные алгебраические логики, исчисления и нейроматематика в науке, технике и экономике" (г. Ульяновск, 2002, 2003), на 56 и 57 Международных сессиях, посвященных Дню радио (г. Москва, 2001, 2002), III Всероссийской научно-практической конференции (с участием стран СНГ) "Современные проблемы создания и эксплуатации радиотехнических систем" (г. Ульяновск, 2001).

Публикация результатов работы. По теме диссертации опубликовано 16 работ, в том числе 7 статей, всего 4.1 печатных листа. Некоторые результаты работы отражены также в отчетах по НИР 2/2000-ПИТ и 2/2001-ПИТ.

Структура и объем работы. Основное содержание диссертационной работы изложено на 150 страницах машинописного текста, содержит 21 рисунок и 5 таблиц и состоит из введения, четырех глав, заключения, списка литературы из 102 наименований и приложения.

4.5. Основные результаты и выводы

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

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

3. С использованием принципа структурной оптимизации ПГ алгоритмов разработан алгоритм и осуществлена его программная реализация решения задачи автоматизированного поиска местоположения фрагмента на изображении при наличии между изображением и фрагментом пространственных и яркостных деформаций. Программа позволяет производить быстрый поиск фрагмента на стандартных ПЭВМ. Так, при реализации в среде Borland С, С++ для Windows время поиска местоположения фрагмента размером 90 х 90 элементов на изображении 2048 х 2048 элементов, имеющего поворот в пределах ±90° и изменение масштаба в пределах 0.65-И .35, составляет примерно 20 сек при вероятности выбора ложного фрагмента менее 3 • 10"5 и использовании ПЭВМ класса Pentium 1700 МГц.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Проведен анализ вычислительных затрат структурно оптимизированных алгоритмов. Для этой цели найдены дискретные распределения вероятностей числа итераций, выполненных ПГ процедурами при наличии и отсутствии в области определения искомого вектора параметров. Показано, что использование структурной оптимизации позволяет значительно сократить вычислительные затраты. При этом выигрыш в быстродействии растет с увеличением числа подобластей в области определения МГД. Например, при 1000 итераций лидирующей процедуры и разбиении области определения параметров на 50 подобластей выигрыш по быстродействию составляет 1.6 раза, при разбиении на 200 подобластей - 2.5 раза, при разбиении на 1000 подобластей - 5.3 раза (для изображений с гауссовской КФ с радиусом корреляции 5 шагов сетки).

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

7. Разработанные алгоритмы поиска подобласти МГД, содержащей искомый вектор параметров, требуют небольших вычислительных затрат и могут быть непосредственно использованы в различных прикладных задачах обработки изображений. Приведен пример программной реализации алгоритма автоматизированного поиска местоположения фрагмента на изображении при наличии между изображением и фрагментом геометрических деформаций и яркостных искажений. В среде Borland С, С++ для Windows время поиска фрагмента размером 90x90 элементов на изображении 2048x2048 элементов, имеющего поворот до ±90° и изменение масштаба в пределах 0.65 ч-1.35, составляет примерно 20 сек. при вероятности выбора ложного фрагмента менее 3 -10~5 и использовании компьютеров класса Pentium 1700 МГц.

1. Аггравал Дж.К., Нандакумар Н. Определение параметров движения по последовательности изображений. Обзор // ТИИЭР,1988, Т.76, N 8. -С. 69-90.

2. Алпатов Б.А. Оптимальное оценивание параметров движущегося объекта в последовательности изображений // Автометрия, 1994, N 2. -С. 32-37.

3. Андросов В.А., Бойко Ю.И., Бочкарев A.M., Однорог А.П. Совмещение изображений в условиях неопределенности // Зарубежная радиоэлектроника, 1985,N4.-С. 32-41.

4. Бакушинский А.Б., Гончарский А.В. Некорректные задачи. Численные методы и приложения. М.: МГУ, 1989. - 198 с.

5. Березин И.С., Жидков Н.П. Методы вычислений. Т. 2.- М.: Физматгиз, 1962.-640 с.

6. Богуславский И.А., Владимиров И.Г. Адаптивное оценивание вектора сдвига//Техническая кибернетика, 1990, N4. С.47-64.

7. Борукаев Т.Б., Грузман И.С. Совмещение изображений при наличии масштабных искажений и разворота // Тез. докл. Междунар. конф. "ОИДИ-90". Новосибирск: ВЦ СО АН СССР, 1990. С. 40.

8. Бьемон Ж., Лагендейк Л., Мерсеро P.M. Итерационные методы улучшения изображений // ТИИЭР, т.78, 1990, N 5. С. 58-84.

9. Васильев К.К. Рекуррентное оптимальное оценивание случайных полей на многомерных сетках // Методы обработки сигналов и полей. Саратов: СПИ, 1986.-С. 18-33.

10. Васильев К.К., Крашенинников В.Р. Методы фильтрации многомерных случайных полей. Саратов: СГУ, 1990. - 128 с.

11. Васильев К.К., В.Р.Крашенинников В.Р., Ташлинский А.Г. Адаптивные методы обработки динамических изображений // Конверсия вузов защите окружающей среды: Тез. докл. Всероссийск. межвуз. науч.-практ. конф. -Екатеринбург, 1994.- С.41.

12. Васильев К.К., Ташлинский А.Г. Оценивание параметров деформаций многомерных изображений, наблюдаемых на фоне помех // Распознавание образов и анализ изображений: новые информационные технологии:

13. Труды IV Всероссийская конф. в 2 ч. Новосибирск: СО РАН, 1998. - 4.1. -С. 261-264.

14. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований.- М.: Наука, 1982. -214 с.

15. Гиниятуллин Н.Ф. Гиниятуллин Ф.Г. Муратханов Д.С. Анализ эффективности непараметрического алгоритма оценивания векторов сигнала / Известия вузов: Радиоэлектроника, Т. 44, № 10, 2001. С. 7-15.

16. Голенков А.Ю., Грузман И.С., Дейхин J1.E. Автоматическая идентификация опорных точек для совмещения изображений // Тез. докл. регион, конф. ОИДИ-87. Новосибирск ВЦ СО АН СССР, 1987. С. 274.

17. Грузман И.С. Квазиоптимальный алгоритм совмещения изображений // Тез. докл. Регион, конф. ОИДИ-87. Новосибирск: ВЦ СО АН СССР, 1987.-С. 78.

18. Губанов А.В., Ефимов В.М., Киричук B.C., Пустовских А.И., Резник A.JI. Методы оценивания взаимного смещения фрагментов изображений // Автометрия, 1988, N 3. С. 70-73.

19. Кормилин В.А., Мартышевский Ю.В. Оптимальная обработка изображений при определении координат объектов // Тез. докл. Междунар. конф. ОИДИ-90. Новосибирск: ВЦ СО АН СССР, 1990. С. 135-136.

20. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). М.: Наука, 1974. - 832 с.

21. Крашенинников В.Р. Волновые модели многомерных случайных полей // Методы обработки сигналов и полей. Ульяновск: УлПИ, 1987. -С. 5-13.

22. Крашенинников В.Р., Ташлинский А.Г. Методы измерения параметров смещения спектрозональных изображений // Идентификация, измерение характеристик и имитация случайных сигналов: Тез. докл. Всесоюзн. научн.-техн.конф. Новосибирск: НЭТИ, 1991. - С.280-281.

23. Лазарев A.M. Исследование сходимости алгоритмов адаптации при задержке в оценке градиента // Радиотехника, 1987, N 10. С. 40-41.

24. Левин Б.Р. Теоретические основы статистической радиотехники. -М.: Радио и связь, 1989. 656 с.

25. Математический энциклопедический словарь // Гл. ред. Ю.В.Прохоров. М.: Сов. Энциклопедия, 1988. - 847 с.

26. Моттль В.В., Копылов А.В. Алгоритмы совмещения изображений при растровых искажениях // Тез.докл. 2-й Всеросс. с участием стран СНГ конф. "Распознавание образов и анализ изображений" РОАИ-2-95. Ульяновск: УлГТУ, 1995, ч. 2. С. 162-164.

27. Невельсон М.Б., Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание.- М.: Наука, 1972. 304 с.

28. Панкова Т.Л., Резник А.Л. Эффективность алгоритмов прецизионного совмещения цифровых изображений // Автометрия, 1991, N 5. С. 39-43.

29. Поляк Б.Т., Цыпкин Я.З. Критериальные алгоритмы стохастической оптимизации // Автоматика и телемеханика, 1984, N 6. С. 95-104.

30. Попов П.Г. Совмещение изображений телевизионного и тепловизи-онного каналов // Автометрия, 1993, N 1. С. 35-39.

31. Прэтт У. Цифровая обработка изображений. Пер. с англ. под ред. Д.С.Лебедева.-М.: Мир, 1982, кн. 1, 312с.; кн.2. 480с.

32. Пытьев Ю.П. Морфологический анализ изображений // Докл. АН СССР, 1983, Т. 269. С. 1061-1064.

33. Пытьев Ю.П., Чуличков А.И. ЭВМ анализирует форму изображения. -М.: Знание, 1988.-48 с.

34. Растригин Л.А. Статистические методы поиска. М.: Наука, 1968. - 376 с.

35. Справочник по теории вероятностей и математической статистике / В.С.Королюк, Н.И.Портенко, А.В.Скороход, А.Ф.Турбин. М.: Наука, 1985.-640 с.

36. Степанов О.А. Предельно достижимая точность совмещения гаус-совских изображений // Автометрия, 1990, N 5. С. 16-23.

37. Ташлинский А.Г. Погрешность оценивания параметров геометрических деформаций изображений при использовании псевдоградиентных процедур // Труды Ульяновского научного центра "Ноосферные знания и технологии", Т.2, вып. 1, Ульяновск: УлГТУ, 1999. - С.35-44.

38. Ташлинский А.Г. Оценивание параметров пространственых деформаций последовательностей изображений. Ульяновск: УлГТУ, 2000. 131 с.

39. Ташлинский А.Г. Псевдоградиентное оценивание пространственных деформаций последовательности изображений. Наукоемкие технологии № 3, Т. 3,2002.-С. 32-43.

40. Ташлинский А.Г., Муратханов Д.С. Приоритетный подход при оценивании параметров пространственных деформаций двух изображений // Научно-технический калейдоскоп. Серия "Приборостроение, радиотехника и информационные технологии", 2000, № 1. С. 90-94.

41. Ташлинский А.Г., Муратханов Д.С. Структурная оптимизация параметров алгоритмов оценивания параметров геометрических деформаций изображений / Приложение к журналу "Физика волновых процессов и радиотехнических систем" Самара, 2001. - С. 102.

42. Ташлинский А.Г., Муратханов Д.С. Использование приоритетного метода при оценивании параметров пространственных деформаций изображений // Труды 56 сессии, посвященной дню радио, Т.2, М.: Радиотехника, 2001.-325-327.

43. Ташлинский А.Г., Муратханов Д.С., Наскальнюк А.Н. Структурная оптимизация псевдоградиентных процедур оценивания межкадровых деформаций изображений // Труды научной сессии, поев, дню Радио. М.: РНТОРЭС, 2002. - С. 145-146.

44. Ташлинский А.Г., Наскальнюк А.Н., Муратханов Д.С. Структурная оптимизация псевдоградиентных алгоритмов в задаче оценивания геометрических деформаций изображений / Вестник УлГТУ, № 4, 2001. С. 4-6.

45. Техническое зрение роботов. Под ред. А. Пью. Пер. с англ. под ред. Г.П. Катыса.- М.: Машиностроение, 1987. 320 с.

46. Тихонов А.Н., Арсенин В .Я. Методы решения некорректных задач. -М.: Наука, 1974.-223 с.

47. Уидроу Б., Стирнз С. Адаптивная обработка сигналов. Пер. с англ. под ред. В.В.Шахгильдяна,- М.: Радио и связь, 1989. 440 с.

48. Фурман Я.А. Обнаружение зашумленных контуров изображений // Радиотехника, 1994, N 10. С. 13-17.

49. Цифровая обработка изображений в информационных системах: Учеб. пособие / И.С.Грузман, В.С.Киричук идр. Новосибирск: Изд-во НГТУ, 2002.-352 с.

50. Цыпкин ЯЗ. Информационная теория идентификации М.: Наука. Физматлит, 1995. - 336 с.

51. Adelson Е. Н., Bergen J. R. Spatiotemporal energy models for the perception of motion // J. Opt. Soc. Amer. A, 1985, vol. 2, 1985. Pp. 284-299.

52. Altunbasak Y., Tekalp A.M. Closed-Form Connectivity-Preserving Solutions for Motion Compensation Using 2-D Meshes // IEEE Trans, on Image processing, vol. 6, no 9,1997. Pp. 1255-1266.

53. Bimbo A., Nesi P. Sanz L.C. Optical Flow Computation Using Extended Constraints // IEEE Trans, on Image processing, vol. 5, no 5, 1996. Pp. 720-738.

54. Bresler Y., Merhav S.J. Recursive image registration with application to motion estimation // IEEE Trans., V. ASSP-35, N 1, 1996. Pp. 70-85.

55. Cafforio C., Rocca F. The differential method for motion estimation // Image Seq. Proc. and Dinamic Scene Anal., New York, 1983. Pp. 104-124.

56. Campani M. and Verri A. Computing optical flow from an overcon-strained system of linear algebraic equations // in Proc. 3rd IEEE Int. Conf. Com-pul. Vision ICCV '90. Japan: Osaka, 1990. Pp. 22-26.

57. Comon P. and Golub G.H. Tracking a Few Extreme Singular Values and Vectors in Signal Processing // Proc. IEEE, Vol. 78, no. 8, 1990. Pp. 1327-1343.

58. Davis L. S., Wu Z., Sun H. Contour-based motion estimation // Comput. Vision. Graphics, Image Processing, vol. 23, 1983. Pp. 313-326.

59. DelBimbo A., Nesi P., and Sanz J. L. Analysis of optical flow constraints // IEEE Trans. Image Processing, vol. 4, 1995. Pp. 460-469.

60. Driessen J.N., Biemond J. Motion field estimation by 2-D Kalman filtering // Proc. SPIE Conf. Visual Commun. and Image Proc., Boston, 1991. -Pp. 511-521.

61. Dubois E., Sabri S. Noise reduction in image sequence using "A pel-recursive Wiener-based displacement estimation algorithm" // Signal Proc., N 12, 1987.-Pp. 399-412.

62. Heeger D. Model for the extraction of image flow // J. Opt. Soc. Amer. A, vol.4, 1987.-Pp. 1455-1471.

63. Heijmans Н. Mathematical Morphology: Paric Principles // Proceedingsof Summer School on Morphological Image and Signal Processing. Zakopane, Poland, 1995.

64. Horn В. K. P. and Schunck B. G. Determining optical flow // Artificial Intell., vol. 17, 1981. pp. 185-204.

65. Huang C. L., Hsu C. Y. A new motion compensation method for image sequence coding using hierarchical grid interpolation // IEEE Trans. Circuits Syst. Video Technol., vol. 4, 1994. Pp. 72-85.

66. Huang T. S., T. S. Netravali T. S., 3-D motion estimation // in Machine Vision for Three-Dimensional Scenes. New York: Academic, 1990. Pp. 195-219.

67. Jacobson L. and Wechsler H., Derivation of optical flow using a spatio-temporal-frequency approach // Comput. Vision, Graphics. Image Processing, Vol. 38, 1987.-Pp. 29-65.

68. Katayama T. Restoration of images degraded by motionblur and noise // IEEE Trans., v. AC-27, N 10, 1982. Pp.1024-1030.

69. Nesi P., DelBimboA. and Ben-Tzvi D. A robust algorithm for optical flow estimation // Compul. Vision. Graphics, Image Processing: Image Understanding, 1995.

70. Netravali A.N., Robbins J.D. Motion compensated television coding: Part 1. Bell Syst. Tech, v. 58, N4, 1979. - Pp. 631-670.

71. Poelman C.J. and Kanade T. A Paraperspective Factorization Method for Shape and Motion Recovery// Computer Vision, vol. 1, 1994. Pp. 97-110.

72. Pyt'ev Yu.P., Pyt'ev A.Yu. Effective Dimensionality and Data Compression, Pattern Recognition and Image Analysis, v.7, T. 4, 1997. Pp. 393-406.

73. Rakshit S., Anderson C.H. Computation of Optical Flow Using Basis Functions // IEEE Trans, on Image processing, v. 6, no 9, 1997. Pp. 1246-1253.

74. Rajala S.A., Abdelqader I.M., Bilbro G.L, Synder W.E. Motion estimation optimization // IEEE Proc, ICASSP-92, v. 3, 1992. Pp. 3-253-3-236.

75. Serra J. Image Analysis and Mathematical Morphology. London-New York: Academic Press, 1982.

76. Soille P. Morphological Image Analysis. Berlin, Heidelberg, New f York: Springer-Verlag, 1999.

77. Tashlinskii Alexandr. Computational Expenditure Reduction in Pseudo-Gradient Image Parameter Estimation / Computational Scince ICCS 2003. Vol. 2658. Proceeding, Part II. - Berlin, New York, London, Paris, Tokyo: Springer, 2003.-Pp. 456-462.

78. Tashlinskii A.G., Gorin A.A., Muratkhanov D.S., Tikhonov V.O. Priotity Approach to the Estimation of the Parameters of the Spatial Image Distortions. // Pattern Recognition and Image Analysis, Vol. 11, No. 1, 2001. Pp. 251-253.

79. Tashlinskii A. G., Muratkhanov D. S. Structural Optimization of Pseudo-gradient Algorithms for Measuring Interframe Image Deformations / Pattern Recognition and Image Analysis, Vol. 13, No. 1, 2003. Pp. 177-178.

80. Tomasi С and Kanade T. Shape and Motion from Image Streams Under Orthography: A Factorization Method // Int'l J. Computer Vision, vol. 9, no. 2, 1992.-Pp. 137-154.

81. Verri A., Girosi F. and Torre V. Differential techniques for optical flow // J. Opt. Soc. Amer. A, vol. 7, 1990. Pp. 912-922.

82. Verri and A. Poggio T. Motion field and optical flow: Qualitative properties // IEEE Trans. Pall. Anal. Machine Inlell., vol. 11, 1989. Pp. 490-498.

83. Wang Y. and Lee O. Active mesh A feature seeking and tracking image sequence representation scheme // IEEE Trails. Image Processing, vol. 3, 1994.-Pp. 610-624.

84. Woodham R. J. Multiple light source optical flow // in Prnc. 3rd IEEE Int. Conf. Compul. Vision ICCV '90.- Japan: Osaka, 1990. Pp. 42-46.