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

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

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

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

Однако при решении практических задач из-за ограниченности вычислительных ресурсов требуемая точность оценок параметров МГД изображений достигается обычно не во всей области возможных значений, а в только в некоторой подобласти. Ограниченность рабочего диапазона ПГ процедур приводит к необходимости разбиения области определения параметров МГД на подобласти, размеры которых соответствуют рабочему диапазону процедур. При этом подобласть, которой принадлежит искомый вектор параметров ^ МГД, называют 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 направления «Распознавание образов и обработка изображений» Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения». Разработанная методика структурной оптимизации алгоритмов определения параметров МГД изображений при области определения возможных значений параметров, превосходящей рабочий диапазон измерительной процедуры, реализованная в форме алгоритмически-программного обеспечения внедрена в деятельность Института систем обработки изображений РАН (г. Самара). Кроме того, некоторые полученные результаты применяются в учебном процессе Ульяновского государственного технического университета при изучении дисциплины «Цифровые методы обработки изображений» для направления 657 100 «Прикладная математика».

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

Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на международных конференциях «Континуальные логико-алгебраические и нейросе-тевые методы в науке, технике и экономике» (г. Ульяновск, 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 время поиска фрагмента размером 90×90 элементов на изображении 2048×2048 элементов, имеющего поворот до ±90° и изменение масштаба в пределах 0.65 ч-1.35, составляет примерно 20 сек. при вероятности выбора ложного фрагмента менее 3 -10~5 и использовании компьютеров класса Pentium 1700 МГц.