Содержание к диссертации
Введение
Глава 1. Модели, методы и алгоритмы оценивания межкадровых геометрических деформаций изображений 12
1.1. Постановка задачи 12
1.2. Модели межкадровых геометрических деформаций изображений . 14
1.3. Подходы к оцениванию межкадровых геометрических деформаций изображений 17
1.4. Оптимальные алгоритмы оценивания межкадровых геометрических деформаций изображений 30
1.5. Выбор целевых функций и псевдоградиента при оценивания межкадровых геометрических деформаций изображений 33
1.6. Псевдоградиентные алгоритмы оценивания межкадровых геометрических деформаций изображений 39
1.7. Выводы и постановка задач исследований 45
Глава 2. Структурная оптимизация псевдоградиентных алгоритмов оценивания параметров межкадровых геометрических деформаций изображений 47
2.1. Постановка задачи 47
2.2. Принцип структурной оптимизации псевдо градиентных алгоритмов 51
2.3. Функция штрафа в задаче структурной оптимизации псевдо градиентных алгоритмов 56
2.4. Функции штрафа при оценивании параметров межкадровых пространственных деформаций 61
2.5. Основные результаты и выводы 73
Глава 3. Достоверность результатов и вычислительные затраты при использовании структурной оптимизации псевдоградиентных алгоритмов 74
3.1. Постановка задачи 74
3.2 Проверка гипотезы об отсутствии искомого вектора в исследуемой области определения параметров геометрических деформаций 16
3.3. Достоверность критерия проверки гипотезы об отсутствии искомых подобластей в исследуемой области определения параметров 82
3.4. Вероятность ошибки при решении задачи поиска V-подобластей в области определения параметров 85
3.5. Вычислительные затраты при структурной оптимизации алгоритмов 95
3.6. Основные результаты и выводы 104
Глава 4. Примеры реализации псевдоградиентных алгоритмов, основанных на принципе структурной оптимизации 106
4.1. Постановка задачи 106
4.2. Сокращение вычислительных затрат при расчете псевдоградиента целевой функции 107
4.3. Псевдоградиент целевой функции при решении задачи поиска фрагмента на большом изображении 114
4.4. Программная реализация автоматизированного поиска местоположения фрагмента на изображении 118
4.5. Основные результаты и выводы 129
Заключение 130
Литература 132
- Оптимальные алгоритмы оценивания межкадровых геометрических деформаций изображений
- Функция штрафа в задаче структурной оптимизации псевдо градиентных алгоритмов
- Вероятность ошибки при решении задачи поиска V-подобластей в области определения параметров
- Псевдоградиент целевой функции при решении задачи поиска фрагмента на большом изображении
Введение к работе
В последние годы происходит активное расширение области применения систем извлечения информации, включающих в себя пространственные апертуры датчиков сигналов. Такие системы используются для дистанционного исследования Земли, в медицинской диагностике, в навигации, в радиолокации, при обеспечении государственной безопасности и в других областях. Исходной информацией в указанных системах являются динамические массивы данных, получаемых оптическими, радиолокационными, акустическими и другими методами. Широкий класс подобных данных может быть представлен в виде изображений. Такое представление обладает высокой информационной емкостью, компактностью и наглядностью.
Исследование временной динамики наблюдаемых объектов приводит к необходимости анализа последовательностей изображений. При создании алгоритмического обеспечения приходится учитывать не только динамику наблюдаемой сцены, но и пространственные перемещения датчиков сигналов, нестабильность разверток электронных мишеней и т.д. Эти факторы могут быть учтены с помощью оценивания межкадровых геометрических деформаций (МГД) изображений. Создание эффективных методов оценки МГД изображений является одной из важных проблем обработки последовательностей изменяющихся изображений.
Реальные информационные системы характеризуются очень большими скоростями поступления данных. Это обусловливает актуальность создания новых алгоритмов оценивания параметров МГД, ориентированных на реализацию в реальном времени. Анализ научных публикаций показывает, что для изображений больших размеров перспективным является построение алгоритмов на базе псевдоградиентных (ПГ) процедур. Связано это с тем, что ПГ процедуры рекуррентны, сочетают хорошие точностные характеристики с высоким быстродействием, не требуют предварительной оценки параметров исследуемых изображений и применимы к обработке изображений с плавно меняющейся неоднородностью. Формируемые ими меняющейся неоднородностью. Формируемые ими оценки параметров устойчивы к импульсным помехам и сходятся к точным значениям при довольно слабых условиях. Кроме того, обработка отсчетов кадров изображений может вестись в произвольном порядке, например, в порядке развертки изображений, что во многих случаях позволяет разрешить противоречие между скоростью поступления изображений и быстродействием вычислительных средств.
Однако при решении практических задач из-за ограниченности вычислительных ресурсов требуемая точность оценок параметров МГД изображений достигается обычно не во всей области возможных значений, а в только в некоторой подобласти. Ограниченность рабочего диапазона ПГ процедур приводит к необходимости разбиения области определения параметров МГД на подобласти, размеры которых соответствуют рабочему диапазону процедур. При этом подобласть, которой принадлежит искомый вектор параметров МГД, называют V-подобластью (от Veritas-истинная). В результате работы всех ПГ процедур, каждая из которых работает в своей подобласти, формируется множество векторов оценок параметров МГД и возникает задача определения среди них искомого вектора, т.е. задача нахождения V-подобласти среди всех имеющихся подобластей. В задачах оценивания параметров МГД изображений число подобластей может достигать десятков тысяч и более, что влечет очень большие вычислительные затраты. Поэтому актуальным является решение поставленной задачи с минимальными вычислительными затратами.
Целью диссертационной работы является структурная оптимизация псевдоградиентных алгоритмов (ПГА) оценивания параметров МГД изображений, направленная на уменьшение вычислительных затрат при произвольной области определения параметров деформаций.
Для достижения цели исследования необходимо решить следующие задачи:
Разработать методику структурной оптимизации ПГА поиска V-подобласти в произвольной области определения параметров МГД изображений, направленную на уменьшение вычислительных затрат.
С использованием разработанной методики построить ПГА поиска V-подобласти.
Разработать алгоритм проверки гипотезы об отсутствии в области определения МГД изображений искомого вектора параметров.
Провести вероятностный анализ достоверности нахождения V-подобласти и вычислительной сложности алгоритмов, построенных по методике структурной оптимизации.
Для достижения цели исследований применялись следующие методы исследований: математического моделирования, теории множеств, теории вероятностей, математической статистики, теории случайных процессов и полей, статистических испытаний. Научная новизна работы
Предложена новая методика структурной оптимизации алгоритмов поиска в произвольной области определения параметров МГД изображений V-подобласти, которая направлена на уменьшение вычислительных затрат. Методика предполагает разбиение области определения МГД на подобласти в соответствии с рабочим диапазоном работающих в них ПГ процедур и предоставление приоритета в выполнении очередной итерации процедуре, имеющей в текущий момент времени наименьшее значение некоторой функции штрафа (ФШ).
Впервые разработан алгоритм проверки гипотезы об отсутствии V-подобласти в области определения МГД изображений. Получены расчетные соотношения для параметров алгоритма, обеспечивающих заданные вероятности ошибок первого и второго рода.
Предложен и реализован новый подход к вероятностному анализу достоверности нахождения с помощью структурно оптимизированных алго- ритмов V-подобласти, основанный на математическом моделировании процесса оценивания МГД изображений.
4. Для структурно оптимизированных алгоритмов найдены дискретные распределения вероятностей числа итераций, выполненных ПГ процедурами при наличии и отсутствии в области определения МГД искомого вектора параметров. Показано, что использование структурной оптимизации позволяет значительно сократить вычислительные затраты.
Практическая ценность и использование результатов
Разработанные на принципе структурной оптимизации ПГА поиска V-подобласти в области определения параметров МГД изображений могут быть непосредственно использованы в различных прикладных задачах обработки изображений. Алгоритмы характеризуются высокой точностью и небольшими вычислительными затратами.
Предложенный подход к вероятностному анализу вычислительной сложности структурно оптимизированных ПГА может быть положен в основу программного обеспечения их сравнительного имитационного моделирования.
Разработанные рекомендации по сокращению вычислительных затрат при расчете псевдоградиента целевой функции позволяют строить ПГА, реализуемые в реальном времени. В частности, использование этих рекомендаций при автоматизированном поиске местоположения фрагмента на изображении дает сокращение вычислительных затрат в несколько раз.
Программная реализация автоматизированного поиска локального фрагмента на большом изображении позволяет осуществлять оперативный поиск фрагмента, применяя стандартные ПЭВМ. При этом вектор параметров МГД изображений может включать угол поворота, параллельный сдвиг, коэффициент изменения масштаба и яркостные искажения.
Основные положения, выносимые на защиту
Разработана методика структурной оптимизации ПГЛ поиска V-подобласти МГД изображений, позволяющая по сравнению с известными подходами уменьшить вычислительные затраты.
Синтезированы ПГА поиска V-подобласти МГД, осуществляющие поиск с заданной достоверностью.
Разработан алгоритм проверки гипотезы об отсутствии V-подобласти в области определения МГД изображений, обеспечивающий требуемую вероятность ошибки первого или второго рода.
Получены соотношения для расчета вероятности ошибочного выбора V-подобласти через пороговое число итераций ПГ процедур.
Найдены дискретные распределения вероятностей числа итераций, выполненных ПГ процедурами, позволяющие осуществить вероятностный анализ вычислительной сложности алгоритмов, построенных по методике структурной оптимизации.
Реализация результатов. Результаты диссертационной работы использованы в научно-исследовательском проекте 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 наименований и приложения.
В первой главе дан обзор и проведен сравнительный анализ известных моделей и методов оценивания МГД изображений, показано, что для изо- бражений больших размеров в условиях ограниченности вычислительных ресурсов наиболее приемлемым является метод псевдоградиентного оценивания Рассмотрены известные оптимальные алгоритмы оценивания параметров МГД в условиях шумов, на основе которых получены целевые функции для рекуррентных ПГ алгоритмов. Дан анализ достоинств и недостатков известных классов квазиоптимальных ПГ алгоритмов, на основе которого сформулированы задачи дальнейших исследований.
Во второй главе предложена новая методика структурной оптимизации алгоритмов поиска подобласти области определения МГД изображений, содержащей искомый вектор параметров, направленная на сокращение вычислительных затрат. Получены рекуррентные выражения для расчета ПРВ ФШ для целевых функций, характерных при оценивании параметров МГД изображений, в частности, выборочного коэффициента межкадровой корреляции и среднего квадрата межкадровой разности.
В третьей главе разработан алгоритм проверки гипотезы об отсутствии в области определения МГД искомого вектора параметров, получены необходимые расчетные соотношения. Проведен вероятностный анализ достоверности нахождения подобласти МГД, содержащей искомый вектор параметров. Получены выражения для расчета вероятности пропуска искомой подобласти. Исследованы вычислительные затраты структурно оптимизированных алгоритмов, для чего найдены дискретное распределение вероятностей числа итераций, выполненных ПГ процедурами.
В четвертой главе на основе проведенных исследований выработаны рекомендации по сокращению вычислительных затрат при расчете ПГ целевой функции в задачах оценивания МГД изображений, найден ПГ для задачи поиска фрагмента на изображении, на основе которого разработан алгоритм автоматизированного поиска и выполнена его программная реализация. Приведены примеры результатов работы алгоритма.
Оптимальные алгоритмы оценивания межкадровых геометрических деформаций изображений
При сжатии видеоинформации часто используется то обстоятельство, что параметры межкадровых аффинных преобразований в любой точке могут быть определены по сдвигам трех (при билинейной интерполяции) или четырех (при перспективной интерполяции) точек изображения [66], расположенных в узлах соответствующей сетки. При этом использование методов, основанных на исследовании оптического потока, может приводить к нарушениям связности сетки. Международные стандарты сжатия видеоинформации, например Н.263 и MPEG 1-2 используют блок оценивания МГД, которому присущ указанный выше недостаток. Для уменьшения искажений при оценке сдвигов узлов сетки используют расширение локальной области. Однако это полностью не решает проблемы и ведет к увеличению объема вычислений. Независимая оценка сдвигов каждого узла нежелательна, т.к. вектора оценок могут пересекаться, нарушая связность сетки. Поэтому при нахождении методом наименьших квадратов векторов сдвигов накладывают ограничения, сохраняющие связность сетки. Известно использование для интерполяции треугольных, четырехугольных и шестиугольных [84] связных сеток, где параметры аффинного преобразования однозначно определяются решением системы соответственно трех, четырех или шести уравнений. Предложены регулярная [84], иерархическая [79], объемная [100] и интеллектуальная [66] сетки. Регулярные сетки получают делением области изображения на равные треугольные и прямоугольные элементы. Их недостатком является неспособность отражать особенности изображения, например, в один элемент сетки может попасть несколько движущихся объектов. В иерархических сетках движущиеся объекты разделяются по элементам сетки. В объемных сетках элементы стараются согласовать с интересующими особенностями изображений. Интеллектуальная сетка использует прогноз трехмерного изображения на плоскость и может быть применена, если априорная информация о содержании изображения доступна.
Можно выделить два недостатка, общих для методов оценивания МГД, основанных на анализе оптического потока с ограничениями. Во-первых, рассмотренные методы направлены на оценивание сдвига каждой точки изображения и не позволяют непосредственно оценивать глобальные параметры МГД. Во-вторых, они требуют больших вычислительных затрат, что делает проблематичной их реализацию в системах реального времени.
Методы анализа оптического потока, использующие регуляризацию При использовании методов регуляризации оценка оптического потока рассматривается как некорректная задача [4, 60], в которой решение получается минимизацией некоторого функционала. Нахождение решения усложняют ограничения на гладкость минимизируемого функционала. Обычно использование этих методов приводит к итеративным решениям. Применительно к оцениванию МГД изображений можно выделить три группы методов, использующих регуляризацию. Методы первой группы позволяют оценить сдвиг точек изображения только в контурах движущихся объектов [72]. При этом исследуемые точки изображений соответствуют узлам сетки отсчетов. Методы второй группы направлены на оценивание межкадровых сдвигов каждой точки изображения, соответствующей узлам сетки отсчетов [78, 71]. Например, для движущегося объекта оценивается сдвиг каждой его точки, а не только контуров. К третьей группе можно отнести методы, оценивающие интегральные параметры МГД, такие как поворот, межкадровый сдвиг всего изображении, изменение масштаба и т.д. Среди этой группы методов следует выделить методы, использующие рекуррентный ПГ подход к оцениванию параметров МГД [45]. Недостатком методов регуляризации первых двух групп является возможность возникновения нарушений непрерывности оцениваемых параметров МГД изображений, особенно при наличии шумов. Это приводит к тому, что при восстановлении изображений по оцененным параметрам на границах объектов могут возникать разрывы или "распространение" одного объекта внутрь другого. При этом величина этих дефектов зависит от числа итераций и использованных весовых коэффициентов. Кроме того, такие методы часто ведут к сглаживанию информации о форме объектов [67]. Наиболее перспективными для задачи оценивания параметров МГД изображений являются ПГ методы, позволяющие достичь высокой точности оценивания параметров при относительно небольших вычислительных затратах [64, 93, 94]. Кроме того, оценки параметров, формируемые с помощью ПГ методов, устойчивы при воздействии аддитивных и мультипликативных шумов. Учитывая отмеченные достоинства ПГ методов, а также их широкое распространение в последнее время, рассмотрим подробнее описание и общие свойства ПГ процедур, а также известные классы ПГА. Псевдоградиентный подход к оцениванию параметров изображений Предположим, что модель МГД изображений определена с точностью до набора параметров а и сформулирован критерий качества оценивания параметров а как минимизация некоторого функционала J(a), отражающего ожидаемые потери. При этом в указанном смысле найти оптимальные параметры аи нет возможности из-за неполноты описания изображения Z. Оценку параметров а можно найти на основании анализа имеющейся реализации Z, т.е. двух кадров Z и Z 2 изображений, между которыми ищутся параметры МГД. Тогда задача может быть сформулирована как задача минимизации J(a) = J(a,Z" ,Z 2 ) для конкретной реализации. Параметры аи могут быть найдены из анализа Z и . Однако представляет интерес обойти этот этап исследования и определять а непосредственно по получаемым значениям функционала где a, - следующее за aM приближение точки минимума j(a, Z Z 2 ); А, - положительно определенная матрица, определяющая длину шагов; VJ(a,_,,Z(,),Z{2)) - градиент функции J(a,_,,Z(,),Z{2)). В алгоритме (1.3.1) каждый очередной шаг из точки сё,., производится по направлению антиградиента (наискорейшего спуска). При выполнении определенных условий имеет место сходимость а, к истинным значениям au. В методах Ньютона и сопряженных градиентов [5] для ускорения сходимости выбирают направления, отличные от антиградиента. Однако применению этих методов в обработке изображений препятствует необходимость громоздких вычислений Vj(aM,Z ,Z 2 J. Значительно сократить вычисления можно, если вместо Vj(a,_j,Z %Z j использовать его усечение V2Ca;_i) = VJ(aM,Z;) на некоторую часть Z( реализации (Z ,Z 2 ). Например, в качестве Z, можно взять двумерное скользящее окно.
Функция штрафа в задаче структурной оптимизации псевдо градиентных алгоритмов
Как показано в первой главе, ПГА оценивания МГД двух изображений Z = {z } и Z = {2 2)}, заданных на регулярной дискретной сетке П, позволяют в условиях воздействия помех обеспечить сравнительно высокую точность оценок при малых вычислительных затратах. Для оценивания качества работы ПГА задается целевая функция. В свою очередь для оценивания значений целевой функции на каждой итерации ПГА формируется некоторый массив наблюдений Z, — z ,,zr l) j (названный в п. 1.4 локальной выборкой целевой функции), взятых из деформированного z(-2(} є Z 2 и проинтерполированного опорного z = 2 (/,,07,.,)є Z(,) изображений, где Z - непрерывное изображение, полученное с помощью некоторой интерполяции из Z 1 . Сходимость к точным значениям аи оценок а =(аиа.2,...Дт)г параметров МГД, формируемых ПГ процедурами, обеспечивается за счет коррелиро-ванности отсчетов деформированного {z-2 J и опорного )2- j изображений, попавших на каждой из итераций оценивания в локальную выборку Zt целевой функции. При этом увеличение объема локальной выборки Zt приводит к улучшению точности оценивания коэффициента корреляции и, соответственно, к увеличению скорости сходимости оценок а параметров МГД к истинным значениям аи. Причем по мере сходимости оценок увеличивается коррелированность Ц2) j и (z-,l)), а, следовательно, и скорость сходимости. С другой стороны увеличение объема локальной выборки Z, ведет к значительному увеличению вычислительных затрат на выполнение ПГ процедуры. В практических задачах вычислительные ресурсы и быстродействие вычислительных средств всегда ограничены, особенно в системах реального времени. Поэтому, из-за указанного ограничения заданная точность оценок параметров МГД достигается лишь в некоторой подобласти 2р(сТ) возмоных значений параметров а. Подобласть Пр(а) области определения Q(a) параметров МГД в дальнейшем будем называть рабочим диапазоном ПГ процедуры (рабочим диапазоном ПГА). Естественно, что в общем случае область Q(ct) определения параметров деформаций вектора а превышает рабочий диапазон Пр(а) ПГ процедуры. Тогда для покрытия всей области определения Q(a) ПГ процедуру нужно выполнить многократно (TV 1 раз), задаваясь различными начальными приближениями а , i = \,N. Заметим, что процедура может быть выполнена либо последовательно N раз (изменением начальных приближений а о ), либо в области Ф(а) может одновременно работать N процедур с различными начальными приближениями. При этом важно лишь, чтобы было соблюдено условие т.е. чтобы объединение рабочих диапазонов всех процедур полностью покрывало заданную область fi(cc) возможных значений а. Наглядным примером задачи, требующей при использовании ПГ подхода разбиения области определения возможных параметров на рабочие подобласти, может служить задача поиска местоположения локального фрагмента на изображении большого размера. При этом если подобласть большого изображения отстоит от искомого фрагмента далеко, то коррелированность отсчетов, попавших в локальную выборку целевой функции, в среднем близка к нулю, что не обеспечит сходимости оценок искомых параметров. Максимальную скорость сходимости оценок параметров обеспечит подобласть, которой принадлежит искомый фрагмент, В дальнейшем, ориентируясь на принятую в [42] терминологию, подобласть области определения параметров, которой принадлежит искомый вектор сси параметров МГ называть V-подобластью (от veritas-истинная), а соответствующую ПГ процедуру, рабочий диапазон &р \а,а1 А которой включает искомое значение параметров аи, - V-процедурой. Подобласти области определения, которым не принадлежит искомый вектор ац будем называть Р-подобластями (от pseudo-ложная) Соответственно ПГ процедуры, рабочие диапазоны О а ) которых не содержат искомого вектора параметров аи, будем называть Р-процедурами (Pseudo-процедурой). Заметим, что целевая функция может иметь как один «истинный» экстремум, которому соответствует один вектор ам искомых параметров МГД, так и несколько (М 1) «истинных» экстремумов, которым соответствуют несколько различных векторов oL,-, т = 1, 2, ..., М искомых параметров МГД. Кроме того, целевая функция может иметь и множество «ложных» экстремумов, не соответствующих решению исходной задачи, которые условно будем называть локальными, только для того, чтобы отразить их несоответствие искомым, «истинным» экстремумам, которые будем называть просто экстремумами целевой функции. В частности, в упомянутой выше задаче поиска на большом изображении местоположения фрагмента, соответствующего некоторому эталону, найденных фрагментов (соответствующих эталону) может оказаться несколько. Например, это происходит в ситуации, если ищется изображение какого-то относительно малоразмерного объекта (самолета, танка и т.д.), а таких объектов на изображении несколько и они имеют различную ориентацию (т.е. различный набор параметров МГД по отношению к эталонному изображению). При этом участки изображения, в какой-то мере схожие с эталонным изображением, но не соответствующие искомому объекту дадут локальные экстремумы целевой функции.
В дальнейшем, учитывая некоторую специфику, которая будет рассмотрена ниже, задачи поиска одного с и нескольких ctm,, m = I, 2, ..., М, экстремумов будем различать.
Рассмотрим теперь поставленную задачу с позиций возможностей нахождения искомого вектора аи МГД, удовлетворяющего экстремуму целевой функции, в одной или нескольких подобластях П оТДо0] области определения параметров и определения принадлежности а„ рабочим диапазонам, i = l,N, ПГ процедур. Если область П(а) определения параметров МГД содержит единственный вектор аи и выполняются условия:
Вероятность ошибки при решении задачи поиска V-подобластей в области определения параметров
Исходя из сделанных выше предположений, найдем вероятность P0ldy для случая наличия в области определения параметров одной V-подобласти и произвольного числе Р-подобластей. При этом значения ФШ процедур, работающих в Р-подобластях будем считать независимыми. Принятое ограничение на независимость локальных выборок из различных Р-подобластей не является жестким, т.к. отсчеты в областях, соответствующих Р-процедурам, в среднем некоррелированы с отсчетами опорного изображения.
Считая, что область определения разбита на N подобластей, получаем где - / г(ч ) функции распределения ФШ для ПГ процедуры, работающей в Р-подобласти [53],
На рис. 3.2 для примера приведены графики вероятности Рош]у пропуска искомого фрагмента изображения на опорном изображении различного размера. Параметрами МГД являлись параллельный сдвиг h={hlth ) искомого и эталонного фрагментов и угол поворота ср между ними. При проведении эксперимента использовалась процедура релейного типа, имеющая диагональную матрицу усиления (1.3.8) с диагональными элементами для угла поворота. При этом использовалось правило (4.2.4) формирования ПГ. Расчет проводился для ситуации, когда рабочий диапазон ПГ процедуры требовал разбиения области определения параметров МГД на 2, 50 и 1000 подобластей соответственно. Графики соответствуют 400 итерациям алгоритма и приведены для ситуации, когда модуль начального приближения h0 параллельного сдвига был одинаковым и равным 5 шагам сетки отсчетов, а начальное приближение ср0 угла поворота изменялось от 25 градусов до нуля. Результаты получены при следующих параметрах фрагмента и опорного изображения: отношение дисперсии сигнала к дисперсии шума на опорном изображении 100, радиус корреляции равен 5 (расстояние в шагах сетки отсчетов, при котором автокорреляционная функция изображения равна 0.5). По графикам можно найти, например, максимальный взаимный угол поворота фрагмента и опорного изображения, при котором обеспечивается требуемая вероятность ошибки при поиске фрагмента. Анализ графиков показывает, что с уменьшением начального рассогласования по углу поворота указанная вероятность уменьшается (например, при ф0 =10 и разбиении области определения параметров МГД на 50 подобластей не превышает 10 2, а при разбиении на 1000 подобластей - 10 3). векторе аи может быть несколько, что уменьшает вероятность Рош]у ошибки при поиске V-подобласти. Объясняется это тем, что в этой ситуации условием ошибочного выбора V-подобласти является меньшее, чем у всех V-процедур значение ФШ у Р-процедуры, лидирующей по числу итераций. Для определения вероятности Рош.у ошибки в этой ситуации можно использовать выражение (6.3.15). Однако ПРВ иу у) при этом будет иметь другой смысл - распределения вероятностей наименьшего значения ФШ среди всех V-процедур. Вероятность ошибки при выборе нескольких подобластей, среди которых должна находиться V-n од область До этого рассматривалась ситуация, когда в качестве искомой подобласти выбиралась та, в которой соответствующая ей процедура первой достигла заданного порогового числа Г итераций. При этом обеспечение малых вероятностей Рощ.у ошибки в выборе V-подобласти требует задания большого значения порогового числа Т итераций. При большом отношении дисперсии сигнала к дисперсии шума пороговое число итераций может стать чрезмерно большим. Снизить вероятность ошибки при сохранении порогового числа итераций можно, если выбирать не одну, а несколько подобластей, в которых ПГ процедуры достигли заданного порогового числа итераций. При этом, естественно, увеличивается вероятность того, что среди выбранных подобластей присутствует V-подобласть, а не вероятность правильного выбора V-подобласти. При решении многих задач обработки изображений существуют критерии, позволяющие с низкой (а иногда и с минимальной) вероятностью ошибки определить V-подобласть. Такие критерии требуют, как правило, больших вычислительных затрат и их использование для большого числа подобластей сдерживается ограниченностью имеющихся в наличии вычислительных ресурсов. Однако к небольшому числу подобластей, например к двум, применение таких критериев вполне реально. К таким задачам относится и задача поиска фрагмента на большом изображении. При этом в качестве критерия выбора может быть использована, например, максимальная из оценок коэффициента корреляции, вычисленных по всему фрагменту. Таким образом, постановка задачи об отборе нескольких подобластей в предположении последующего выбора из них V-подобласти является актуальной. Учитывая вышесказанное, рассмотрим задачу поиска одной V-подобласти среди N подобластей области определения параметров в следующей постановке. Найдем вероятность того, что V-подобласть находится среди ц подобластей, в которых закрепленные за подобластями ПГ процедуры первыми достигших заданного числа Т итераций. Если считать локальные выборки целевой функции всех процедур независимыми, а за случайное событие принять лучшее значение ФЩ у Р-процедуры, то поставленную задачу можно свести к схеме Бернулли. Тогда выражение для вероятности Р у пропуска V-подобласти при выборе ц. процедур, первыми достигших числа Т итераций, может быть записано с использованием биномиального закона распределения.
Псевдоградиент целевой функции при решении задачи поиска фрагмента на большом изображении
Получены расчетные соотношения для критерия проверки гипотезы об отсутствии искомого вектора в области определения параметров, позволяющие находить пороговые значения числа итераций лидирующей процедуры и числа шагов алгоритма для требуемого уровня вероятностей ошибок первого и второго рода, 2. При условии наличия в области определения параметров МГД изображений подобласти, содержащей искомый вектор параметров, найдена вероятность невыбора этой подобласти. При этом расчетные соотношения используют ПРВ функции штрафа и пороговое число итераций лидирующей процедуры. 3. Для ПГА, построенных на принципе структурной оптимизации, получены дискретные распределения вероятностей числа итераций, выполненных ПГ процедурами для ситуаций наличия и отсутствия в области определения искомого вектора параметров. С использованием полученных распределений найдены основные соотношения, характеризующие вычислительные затраты ПГА. 4. Приведены примеры анализа вычислительных затрат ПГА, показавшие, что использование структурной оптимизации позволяет значительно сократить вычислительные затраты. При этом выигрыш в затратах растет с увеличением области определения возможных значений искомого вектора параметров и существенно зависит от числа подобластей. В частности, для изображений оптического диапазона основной выигрыш достигается уже при нескольких тысячах итераций лидирующей процедуры. Например, для изображений с гауссовской КФ с радиусом корреляции 5 шагов сетки при 1000 итерациях ПГ процедуры выигрыш по быстродействию у структурно оптимизированного алгоритма составляет: при разбиении области определения параметров на 50 подобластей - 1.6 раза, при разбиении на 200 подобластей - 2.5 раза, при разбиении на 1000 подобластей - 5.3 раза. 5. Проведен анализ вычислительных затрат, необходимых для реализации предложенного алгоритма проверки гипотезы об отсутствии искомого вектора в области определения параметров МГД изображений. В частности, показано, что при исследовании изображений оптического диапазона с гауссовской корреляционной функцией и разбиении области определения параметров на 900 подобластей, вычислительные затраты на проверку гипотезы при отсутствии искомого вектора параметров в области определения увеличиваются в среднем в 2.2 раза по сравнению со случаем его наличия в области определения.
В первой главе уже отмечалось, что наиболее важными этапами при построении ПГА оценивания параметров МГД изображений являются выбор целевой функции и нахождение для этой функции легко вычисляемого ПГ. Первая из этих задач рассмотрена в п. 1.5 первой главы, где показано, что в задачах оценивания параметров МГД изображений основными целевыми функциями могут являться СКМР и ВКМК. Выбор СКМР целесообразен при отсутствии в принятых моделях изображений Z и Z мультипликативных искажений и нецентрированных помех, а ВКМР - при линейной модели межкадровых яркостных искажений. Вторая важная задача - сокращение вычислительных затрат при расчете ПГ целевой функции рассмотрена в настоящей главе. При этом полученные результаты использованы для решения конкретной прикладной задачи - нахождения ПГ целевой функции при поиске фрагмента на изображении.
В качестве примера практического использования методики структурной оптимизации ПГ алгоритмов в настоящей главе рассмотрено ее применение при разработке алгоритма автоматизированного поиска местоположения локального фрагмента на изображении большого размера. Указанный алгоритм и соответствующее ему программное обеспечение разрабатывались при непосредственном участии автора в ходе выполнения НИР "Методы представления и статистического анализа многомерных изображений" и "Методы и адаптивные алгоритмы оперативного обнаружения аномалий на изображениях и в многомерных сигналах, заданных на сетках со случайными деформациями", проводимых в рамках направления "Распознавание образов и обработка изображений" Федеральной целевой научно-технической программы "Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения".
Решению поставленных задач посвящены следующие подразделы данной главы. В п. 4.2. исследуется возможности сокращения вычислительных затрат при расчете ПГ целевой функции. Нахождению и исследованию ГТГ целевой функции при решении задачи поиска фрагмента на большом изображении посвящен п. 4.3. При этом особое внимание также уделено сокращению вычислительных затрат. В п. 4.4 рассмотрена программная реализация решения задачи автоматизированного поиска местоположения фрагмента на изображении при наличии между изображением и фрагментом МГД и амплитудных искажений.
