Содержание к диссертации
Введение
ГЛАВА 1. Обзор и анализ алгоритмов и методов совмещения изображений в системах улучшенного видения 16
1.1 Алгоритмы и методы предварительной обработки изображений с целью их последующего совмещения в авиационных системах видения 17
1.2 Корреляционные методы совмещения 18
1.2.1 Систематизация и анализ критериальных функций, пригодных для использования в системах улучшенного видения 18
1.2.2 Корреляционная критериальная функция 18
1.2.3 Разностные критериальные функции 19
1.2.4 Парные критериальные функции 20
1.4 Методы поиска глобального экстремума в задачах многоэкстремальной оптимизации 23
1.4.1 Метод мультистарт 28
1.4.2 Туннельный алгоритм 29
1.4.3 Сетки и методы покрытий 30
1.4.4 Поиск с запретами 31
1.4.5 Генетические алгоритмы
1.5 Некорреляционные методы совмещения изображений 35
1.6 Обзор дескрипторов ключевых точек
1.6.1 Дескриптор SURF 37
1.6.2 Дескриптор SIFT 40
1.6.3 Выводы по применимости дескрипторов для совмещения разнородных изображений 43
1.7 Основные выводы по главе 43
Постановка задач исследования 45
ГЛАВА 2. Алгоритмы совмещения изображений в системах комбинированного видения 46
2.1 Сравнение и выбор видов критериальных функции 46
2.2 Совмещение изображений с помощью аффинных преобразований 52
2.3 Некорреляционное совмещение с применением дробно-линейных преобразований 54
2.3.1 Алгоритм построения матрицы гомографии по минимальному числу ключевых точек. 54
2.3.2 Разработка алгоритма построения матрицы гомографии по произвольному числу ключевых точек 59
2.3.3 Разработка алгоритма выделения значимых объектов 61
2.3.4 Разработка алгоритма получения связных контуров
2.3.6 Разработка алгоритма сокращения количества точек в контурах 67
2.3.7 Разработка алгоритма установления однозначного соответствия между угловыми точками 2.3.7 Разработка алгоритма отбраковки недостоверных пар ключевых точек 72
2.3.8 Пошаговый алгоритм поиска матрицы гомографии 79
2.4 Алгоритм совмещения изображений на основе единственной пары ключевых точек 80
2.5 Основные выводы по главе 89
ГЛАВА 3. Алгоритмы оценки качества совмещения изображений 91
3.1 Постановка задачи по оценке качества совмещения изображений 92
3.2 Классификация существующих подходов к оценке качества совмещения 93
3.3 Алгоритмы сравнения площадей пересекающихся контуров протяженных объектов 97
3.4 Алгоритм оценки качества совмещения на основе межпиксельного расстояния 101
3.5 Алгоритм оценки качества совмещения на основе углов между линиями контуров 106
3.6 Варианты совместного использования предлагаемых подходов по оценке качества совмещения 112
3.7 Основные выводы по главе 113
ГЛАВА 4. Программно-алгоритмические средства исследования и апробации предлагаемых алгоритмов 115
4.1 Проектирование программного обеспечения для исследования алгоритмов отладки изображений 115
4.1.1 Структура программного обеспечения 115
4.1.2 Описание отдельных модулей программного обеспечения 116
4.2 Методика проведения экспериментов 120
4.2 Исследование методов поиска глобального экстремума 122
4.2.1 Метод покрытий 122
4.2.2 Мультистарт 124
4.2.3 Генетический алгоритм 126
4.3 Исследование алгоритма совмещения по единственной паре ключевых точек 129
4.3.1 Исследование методов оценки качества совмещения изображений 129
4.3.2 Сравнительный анализ трудоемкости алгоритмов совмещения 135
4.3 Применение алгоритма совмещения с использованием произвольного количества пар ключевых точек 137
4.4 Описание аппаратной реализации предлагаемых алгоритмов 146
4.4.1 Реализация алгоритма преобразования одного изображения к плоскости другого с применением матрицы гомографии 148
4.4.2 Реализация алгоритма оценки качества совмещения изображений на основе межпиксельного расстояния 150
4.5 Основные выводы по главе 152
Заключение 153
Список сокращений и условных обозначений 155
Список литературы 156
- Систематизация и анализ критериальных функций, пригодных для использования в системах улучшенного видения
- Некорреляционное совмещение с применением дробно-линейных преобразований
- Алгоритмы сравнения площадей пересекающихся контуров протяженных объектов
- Описание отдельных модулей программного обеспечения
Введение к работе
Актуальность темы исследования. В авионике перспективных летательных аппаратов (ЛА) должна осуществляться комплексная обработка видеоинформации от датчиков системы технического зрения (СТЗ) и изображения виртуальной модели местности (ВММ), формируемого на базе априорной цифровой картографической информации с использованием навигационных данных. Цель комплексной обработки информации заключается в формировании максимально полной и адекватной информации о текущей ситуации в воздушном пространстве и наземной инфраструктуре аэропорта в сложных условиях видимости и, как следствие, существенно повысить безопасность полетов и особенно в сложных метеоусловиях и на этапе посадки воздушного судна.
Совокупность средств, обеспечивающих комплексную обработку информации и ее отображение экипажу, принято называть системой комбинированного видения (Combined Vision System – CVS), которая должна не только отвечать требованиям и выполнять функции двух систем: системы улучшенного видения (Enhanced Vision System – EVS) и системы синтезированного видения (Synthetic Vision System – SVS), включающей формирование ВММ, но и обладать новыми возможностями, связанными с одновременной совместной индикацией EVS и SVS изображений. Слияние реального и виртуального изображений, то есть объединение изображений от датчиков, имеющихся на борту, и SVS-изображения в единое изображение CVS, способно значительно улучшить ситуационную осведомленность экипажа ЛА.
Основные проблемы при создании систем комбинированного видения связаны с разработкой:
– алгоритмов предварительной обработки изображений от сенсоров СТЗ (изменение диапазона яркостей, выделение границ объектов, утоньшение и векторизация фрагментов, формирование связных фрагментов) с целью улучшения видения и подготовки их для геометрического совмещения с изображениями ВММ;
– алгоритмов геометрического совмещения изображений от датчиков на борту ЛА и SVS изображений, которые могут исполнятся в бортовом вычислителе в режиме реального времени;
– эффективных способов совместной визуализации реальных и виртуальных изображений, обеспечивающих экипаж ЛА максимально полной информацией о состоянии окружающей среды.
Наиболее сложной является задача совмещения получаемых от сенсоров СТЗ изображений, с изображением виртуальной модели местности, создаваемым с использованием цифровой карты местности (ЦКМ) с учетом навигационных данных летательного аппарата: текущих координат местоположения и углов позиционирования линий визирования сенсоров СТЗ. Причиной этого служит существенная величина погрешности определения местоположения ЛА в пространстве.
Разработка конкретных систем обработки изображений на борту ЛА определяется следующими основными особенностями.
Во-первых, при разработке подсистем обработки и совмещения изображений на борту ЛА требуется решать не проблему общего автоматического понимания изображения некоторой произвольной сцены, а более узкую задачу проблемно-
ориентированной интерпретации изображения. Обычно эта задача сводится к обнаружению и идентификации на изображении набора примитивов, соответствующих реальным физическим объектам, присутствие которых должно некоторым образом отражаться на управлении ЛА.
Во-вторых, к алгоритмам обработки изображений в подсистемах информационного обеспечения предъявляются специальные требования, связанные с назначением и конкретными характеристиками разрабатываемой или уже существующей системы управления ЛА.
В последнее время одной из наиболее актуальных задач современной авионики стало создание систем улучшенного видения (Enhanced Synthetic Vision System – ESVS). Системы данного класса позволяют путем совмещения реальных изображений, получаемых от датчиков систем технического зрения, установленных на борту ЛА, и изображений виртуальной карты местности, создавать и отображать комбинированное изображение, предоставляющее летчику более подробную и точную информацию о местонахождении летательного аппарата, позволяющее осуществлять управление в сложных метеоусловиях, при плохой видимости, в ночное время. Обеспечение экипажа такого рода информацией существенно повышает безопасность полетов.
В качестве источников информации в таких системах могут использоваться:
телевизионные видео датчики (ТВ камеры),
инфракрасные (ИК) датчики различных диапазонов (коротковолновые и длинноволновые ИК камеры),
миллиметровые радары (МР),
лазерные локаторы (ЛЛ),
базы данных рельефа местности вдоль маршрутов полёта,
базы данных объектов аэропортов и взлётно-посадочной полосы (ВПП),
навигационные параметры ЛА другие.
Сформированная системой EVS графическая информация далее
представляется пилоту на одном из доступных устройств отображения – индикаторе на лобовом стекле или многофункциональном индикаторе, представляющем собой дисплей, входящий в состав бортовой системы отображения информации. В составе EVS выделяются две основные подсистемы:
СТЗ, выполняющая операции регистрации и обработки видеоинформации;
система компьютерной визуализации (СКВ), непосредственно формирующая и представляющая пилоту графическую информацию о закабинной обстановке.
Наиболее востребованными задачами для создания полностью автоматических летательных аппаратов являются:
– задача совмещения реального изображения, получаемого от одного из сенсоров, установленного на борту летательного аппарата, с изображением виртуальной модели местности, создаваемым на основе виртуальной карты;
– задачи комплексирования и совмещения изображений, получаемых от датчиков с различной природой формирования изображений.
Анализ публикаций и научной литературы в области алгоритмов и методов совмещения изображений, применимых для задач, требующих решения на борту воздушного судна, позволяет выделить ряд проблем, которые возникают при обработке изображений различной физической природы. Они обусловливаются
неоднородностью представления, различными формами хранения, рассогласованием в работе регистрирующей аппаратуры.
Степень разработанности темы. В настоящее время проблематике обработки изображений уделяется значительное внимание в отечественной и зарубежной литературе. Существенной вклад в развитие методов цифровой обработки изображений внесли отечественные ученые Алпатов Б.А., Визильтер Ю.В., Еремеев В.В., Желтов С.Ю., Злобин В.К., Сергеев В.В., Сойфер В.А. и другие, а также зарубежные ученые Блейхут Р., Гонзалес Р., Понс Ж., Прэтт У., Форсайт Д.
На данный момент активно проводятся исследования по разработке и созданию систем совмещения и визуализации изображений в бортовых вычислительных комплексах. Однако большая часть известных технологий обработки и конкретных алгоритмов обладают чрезмерно высокой вычислительной трудоемкостью, делающей затруднительным или невозможным их применение на борту летательного аппарата. Алгоритмы, пригодные для практического применения в бортовых вычислителях, еще недостаточно освещены в научной литературе.
В настоящей диссертации приведены разработанные автором новые некорреляционные алгоритмы совмещения изображений, а также модификации известных алгоритмов. Они, в сравнении с корреляционными алгоритмами, обладают высоким быстродействием и требуют существенно меньших вычислительных затрат. Приводится сравнительный анализ предлагаемых алгоритмов с известными решениями.
Цель диссертации состоит в повышении быстродействия систем совмещения изображений до уровня, необходимого для использования в бортовом вычислительном комплексе летательных аппаратов за счет разработки и исследования алгоритмов, позволяющих снизить трудоемкость вычислительного процесса.
Для достижения цели необходимо решение следующих задач:
– осуществить анализ существующих методов и алгоритмов совмещения изображений в бортовых вычислительных комплексах, в том числе рассмотреть корреляционные и некорреляционные подходы;
– оценить степень пригодности существующих алгоритмических решений для применения в системах комбинированного видения летательных аппаратов;
– разработать алгоритмы совмещения реальных изображений с изображениями ВММ, пригодные к применению в бортовых вычислителях;
– разработать алгоритмы совмещения и взаимной геометрической коррекции разнородных изображений;
– разработать алгоритмы для оценки качества получаемых совмещений;
– оценить реализуемость предложенных алгоритмов на специализированных вычислителях, в частности, на программируемых логических интегральных схемах (ПЛИС).
Научная новизна диссертации заключается в том, что в ней разработаны алгоритмы совмещения разнородных изображений в бортовых вычислительных комплексах, которые позволяют ускорить процесс совмещения изображений на 52-58 % за счет применения методов контурного анализа и алгоритмов проективных преобразований без потери качества получаемых совмещений.
Теоретическая значимость работы состоит в том, что разработаны алгоритмы совмещения изображений для систем комбинированного видения летательных аппаратов, основанные на методах контурного анализа и алгоритмах проективных преобразований, а также алгоритмы оценки качества совмещения.
Практическая значимость работы состоит в том, что на базе разработанных алгоритмов созданы программные средства, обеспечивающие совмещение изображений, полученных от бортовых видеодатчиков, с изображениями, построенными по виртуальной модели местности, и автоматическую оценку качества получаемых результатов.
Методология и методы исследования. Для решения поставленных задач применялись методы вычислительной математики, теории обработки изображений и распознавания образов, математического моделирования, системного анализа, подходы контурного анализа.
Положения, выносимые на защиту:
– выбор и обоснование набора критериальных функций, применимых для совмещения изображений в системах комбинированного видения летательных аппаратов;
– алгоритм совмещения изображений, основанный на поиске единственной пары ключевых точек, позволяющий сократить число изображений ВММ, требуемых для совмещения, в 10-12 раз и ускоряющий процесс совмещения на 52-58%;
- пошаговый алгоритм поиска матрицы гомографии, применяемый в случае наличия недостоверных пар точек, использующий нахождение элементов матрицы гомографии по произвольному числу ключевых точек, позволяющий ускорить совмещение изображений на 42-46% в сравнении с корреляционными алгоритмами;
– алгоритм отсеивания недостоверных пар ключевых точек, позволяющий исключить их негативное влияние на конечный результат совмещения;
– алгоритмы оценки качества совмещения изображений, обеспечивающие автоматическое нахождение показателя качества совмещения изображений для взаимного сравнения характеристик функционирования алгоритмов совмещения.
Степень достоверности и апробация результатов. Диссертация выполнена в Рязанском государственном радиотехническом университете в рамках следующих хоздоговорных научно-исследовательских работ, выполненных по заказу АО «ГРПЗ»:
НИР «Совмещение-РГРТУ-1» по теме «Разработка программно-математического обеспечения предобработки и визуализации изображений, поступающих от сенсоров системы технического зрения ЛА и формируемых на основе цифровой карты местности»;
НИР «Совмещение-РГРТУ-3» по теме «Разработка методов и алгоритмов уменьшения вычислительной сложности совмещения реальных и виртуальных изображений в авиационных комбинированных системах видения»;
НИР 3-12 по теме «Разработка программно-математического обеспечения для улучшенного и синтезированного изображений в системах технического зрения для управления летательным аппаратом, с использованием комплексной пилотажной и навигационной информации»;
НИР 3-13 по теме «Разработка и исследование компонентов математического и алгоритмического обеспечения совмещения и визуализации изображений в авиационных многоспектральных системах технического зрения»;
НИР 2-14 по теме «Разработка и исследование методов и алгоритмов уменьшения вычислительной сложности совмещения изображений в многоспектральных системах технического зрения летательных аппаратов»;
СЧ НИОКР «МСТЗ-РГРТУ» по теме «Отладка программного обеспечения стенда для проведения испытаний и отладки компонент многоспектральной системы технического зрения в части СДМВ»;
НИР 12-15 по теме «Формирование и анализ исходных данных для экспериментальных исследований технологии анализа изображений для систем технического зрения летательных аппаратов»;
НИР 14-14Г, выполненной в ходе реализации проекта РФФИ № 14-07-97515.
Результаты диссертационной работы внедрены в разработках АО «Государственный Рязанский приборный завод», направленных на создание систем технического зрения для перспективных летательных аппаратов, и в учебном процессе кафедры ЭВМ ФГБОУ ВО «Рязанский государственный радиотехнический университет» (дисциплины «Алгоритмические основы совмещения изображений различной физической природы», «Методы и алгоритмы обработки изображений» направления подготовки – 09.03.01 и 09.04.01 «Информатика и вычислительная техника»).
Личный вклад автора. Все выносимые на защиту результаты получены автором лично.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на 8-й международной научно-технической конференции CSIT’2013 (Украина, Львов, 2013), 16-й международной конференции «Цифровая обработка сигналов и её применение» (ИПУ РАН, Москва, 2014), 3-й средиземноморской конференции по встроенным вычислениям MECO-2014 (Черногория, Будва, 2014), 4-й средиземноморской конференции по встроенным вычислениям MECO-2015 (Черногория, Будва, 2015), научно-технической конференции «Техническое зрение в системах управления» (ИКИ РАН, Москва, 2015), 3-й международной научно-технической конференции «Актуальные проблемы создания космических систем дистанционного зондирования Земли» (АО «Корпорация «ВНИИЭМ» Москва, 2015).
Публикации. По теме диссертации опубликовано 16 работ, в том числе 7 статей, 3 из которых в изданиях, рекомендуемых ВАК РФ, и 5 тезисов докладов в материалах международных и всероссийских конференций. В Федеральной службе по интеллектуальной собственности, патентам и товарным маркам зарегистрированы три программы для ЭВМ (№ 2015610172 от 12.01.2015, №2015660419 от 30.09.2015, №2015660721 от 07.10.2015).
Структура и объем работы. Диссертация состоит из введения, 4-х глав, заключения, списка использованных источников и приложения. Основной текст работы содержит 164 страницы, 75 рисунков и 10 таблиц. Список использованных источников включает 74 наименования.
Систематизация и анализ критериальных функций, пригодных для использования в системах улучшенного видения
Известные на сегодняшний день методы, исходя из критерия требуемого качества получения результата, можно отнести к одному из двух классов: методы, которые всегда приводят к нахождению оптимального решения, но требуют для этого в наихудшем случае недопустимо большого числа операций (говоря иначе, решение будет найдено, но, сколько времени потребуется на его поиск, заранее сказать невозможно); методы, которые не всегда приводят к нахождению оптимального решения, но требуют для получения этого решения приемлемого числа операций (решение будет найдено за требуемое время, однако, в общем случае оно не совпадет с искомым глобальным оптимумом, вопрос заключается в том, насколько серьезно найденное решение будет отличаться от истинного значения ГЭ) [20].
Подробная классификация представлена в таблице 1.1.
Наиболее общими в теории дискретного программирования являются точные методы решения. К данной группе относятся алгоритмы, в которых осуществляется либо попытка полного перебора при небольшой размерности задачи, или максимального сокращения объема перебора в случае, когда задача имеет большую размерность. При этом имеет место неизбежность экспоненциального времени работы алгоритмов.
Часто используемым на практике приемом сокращения перебора является целенаправленный перебор, основанный на методе «ветвей и границ» или методе «неявного перебора». Он заключается в отыскивании частных решений, представленных в виде дерева поиска, и применении методов построения оценок для сравнения получаемых решений. Названные оценки должны указать на бесперспективные частичные решения, в результате чего от дерева решений сразу отсекаются целые ветви, что сразу существенно сокращает пространство поиска. Для такого рода алгоритмов необходимо предусматривать процедуру возврата по дереву поиска, применяемую в случае, если исследование текущего направления полностью завершено и необходим просмотр тех ветвей дерева, которые еще не подвергнуты рассмотрению.
Наименование алгоритма (метода) Достоинства Недостатки 1 группа(точные методы) Методы иалгоритмыпоследовательногосужениямножестварешений (полный ицеленаправленныйперебор) Полный перебор вариантов Оптимальное решение NP полнота.Нереализуемыпри большомчислеисходныхданных Метод ветвей и границ Метод динамического программирования Метод множителей Лагранжа Алгоритмы предварительного расширения и последующего сужения Алгоритмы отсечений Алгоритмы конечного расширения и сужения Композитные алгоритмы 2 группа(приближенные методы) Методы иалгоритмыпоследовательногоулучшениярешений(эвристическиеалгоритмы) Итеративные(локальные)алгоритмы Алгоритмближайшегососеда Высокая скорость получения результата Ростпогрешности сувеличениемобъемаисходныхданных
Алгоритмсреднейвеличины Стохастические алгоритмы Случайный поиск Просмотр области решении с заданной вероятностью Вероятностный поиск Направленныйслучайныйпоиск Имитация отжига Решение, близкое к оптимальному Низкая скорость получения результата Методыпараллельнойобработки данных(методыискусственногоинтеллекта) Нейронные сети Высокая скорость и точность получения результата Сложность анализа, программной и аппаратной реализации Локально-стохастические методы(эволюционные методы) Эволюционные вычисления Ко второй группе относятся алгоритмы последовательного улучшения решений, хорошо развитые в теории математического программирования. Они используют прием, который можно назвать «снижение требований». Он заключается в отказе от поиска оптимального решения, а в нахождении «хорошего» решения за приемлемое время [21]. Алгоритмы, основанные на этом приеме, обычно называются эвристическими, поскольку они используют разумные соображения без строгих обоснований. При их разработке используются интуитивные соображения, не подкрепленные соответствующим математическим обоснованием.
Методы, применяемые для построения алгоритмов такого типа, сильно зависят от специфики задачи. Итеративные процедуры, применяемые для этой цели, напоминают итеративные процедуры поиска экстремума при использовании алгоритмов градиентного типа и алгоритмов метода возможных направлений.
При использовании алгоритмов данного класса возникает вопрос о возможности отыскания с их помощью глобального оптимума или приближения к нему с точностью до некоторой задаваемой ошибки . На практике оказывается, что в большинстве случаев гарантированно можно достичь только некоторого локального экстремума целевой функции. Данные алгоритмы являются приближенными, но они принципиально отличаются от приближенных алгоритмов - оптимизации, строящихся на основе методов последовательного сужения множества решений и гарантирующих приближение к экстремуму с точностью до .
Для корреляционного совмещения изображений можно определить следующие классификационные признаки методов оптимизации: – характер оптимизации: в зависимости от применяемого алгоритма возможно отыскание локального или глобального экстремума, соответственно методы оптимизации подразделяются на локальные и глобальные. – вид оптимизации: условная или безусловная. Для задачи совмещения изображений не требуется предусматривать в методе оптимизации каких-либо дополнительных ограничений. Поиск наилучшего совмещения с изображением ВММ осуществляется в шестимерном пространстве, возможный выход за пределы которого можно исключить программными ограничениями; – размерность решаемой задачи. В целом решается задача в шестимерном пространстве поиска (высота, широта, долгота, курс, тангаж и крен). Увеличив размер изображения ВММ можно исключить из рассмотрения тангаж и крен, но появляются два параметра – координаты по X и Y при перемещении РИ по ВИ. Также можно исключить курс, который соответствует повороту ВММ, который в рассматриваемой задаче незначительный. Таким образом, получаем задачу в пятимерном пространстве поиска (высота, широта, долгота и координаты по X и Y).
Некорреляционное совмещение с применением дробно-линейных преобразований
Аффинное преобразование можно рассматривать как преобразования сдвига и одновременно поворота вектора в комплексной плоскости на угол а, т.е. z = z0+z -zпр. Здесь z0,z ,zпр - комплексные числа: z0 = (х0,у0) = х0 + iy0, z = (xf,у ) = х + iy , zпр = [хпр,упр)= хпр + iyпр. При этом число z0 «отвечает» за сдвиг, а число zпр - за изменение масштаба и поворот в комплексной плоскости. Такой способ совмещения изображений был применен в работе [37]. Совмещение с помощью методов комплексного контурного анализа позволяет учитывать три вида аффинных преобразований изображения: - сдвиг изображения вдоль вектора; - изменение масштаба изображения; - поворот относительно начала общей для двух изображений декартовой прямоугольной системы координат. Следует отметить, что аффинные преобразования не могут учитывать проективные искажения, неизбежно возникающие при сопоставлении двух изображений, полученных под различными ракурсами с борта воздушного судна, и, тем более, при совмещении разнородных изображений.
Аффинные преобразования позволяют обнаруживать и оценивать изменения масштаба, сдвиги и повороты изображений [37]. Однако изображения, получаемые на борту воздушного судна от разноспектральных датчиков, могут содержать еще и проективные искажения. Они описываются дробно-линейными функциями, содержащими в общем случае 8 неизвестных параметров (в случае плоской гомографии). Соответствующее преобразование одного изображения X к плоскости другого X при наличии проективных искажений можно записать и в матричной форме X = НХ, где Н - матрица гомографии [38, 39].
Для получения адекватной оценки матрицы гомографии по двум изображениям, которые предполагается совмещать, необходимо иметь не менее четырех удачно подобранных пар ключевых (особых, соответствующих) точек на этих изображениях.
При совмещении изображений методами проективной геометрии необходимо решение ряда ключевых задач: 1) обнаружение ключевых точек на изображении и формирование множества таких точек; 2) установление соответствия между ключевых точками и оценка правильности найденного соответствия; 3) оптимальное использование множества пар ключевых точек при построении матрицы гомографии. Поиск ключевых точек является наиболее важной задачей в методе совмещения изображений с помощью проективного преобразования, в этом сходятся многие авторы [40, 41]. Далеко не всегда удается найти такие точки в автоматическом режиме. Но если даже найдено некоторое множество пар ключевых точек, то остается вопрос об их оптимальном использовании [42]. Неудачный выбор ключевых точек может приводить к плохому и даже очень плохому качеству совмещения изображений. Один из широко применяемых методов автоматического выбора корректного набора точек - метод RANSAC [43]. Исследования, проведенные автором, показали, что и он в общем случае не гарантирует получение требуемого результата [44]. В настоящей работе в параграфах 2.3.7 и 2.3.8 приведены результаты проведенного автором исследования, по оптимальному использованию множества пар ключевых точек в задаче совмещения изображений. Совмещение изображений с помощью проективных преобразований.
Аффинные преобразования не могут учитывать проективные искажения, неизбежно возникающие при сопоставлении двух изображений, полученных под различными ракурсами с борта воздушного судна, и, тем более, - при совмещении разнородных изображений. Под разнородными изображениями здесь понимаются, с одной стороны, реальное изображение (видеоизображение, тепловизионное и т.д.), с другой, виртуальное изображение, сгенерированное по цифровой карте местности. Для учета проективных искажений можно использовать дробно-линейные преобразования [40]: Г h11x + h12y + h13 х = h31x + h32y + 1 , h21x + h22y + h23 . (2.1) [ h31x + h32y + 1 В матричной форме (в однородных координатах): У у \1 J (лх) (h1 h2 h13 (2.2) \Лу\= h21 h22 h23 [Я] [h31 h32 1 J Матрица Н = (/ 3 в составе формулы (2.1) называется матрицей гомографии. Она содержит 8 неизвестных параметров, для нахождения которых необходимо как минимум 4 пары ключевых точек на сопоставляемых изображениях. Формирование множества пар ключевых точек, с одной стороны, и выбор из этого множества оптимального набора точек, обеспечивающих корректное определение элементов матрицы гомографии, с другой стороны, это две основные задачи в проблеме совмещения изображений с помощью матрицы гомографии.
Для решения первой задачи предложено большое число методов (SURF, SIFT [45, 31], методы основанные на идеях контурного анализа [41, 43]). Как уже отмечалось в параграфе 1.6.3 методы SURF и SIFT дают хорошие результаты при поиске ключевых точек на паре изображений, полученных с помощью однотипных датчиков и не приемлемы для сопоставления разнородных изображений и, особенно, если последние представлены контурами основных объектов на подстилающей поверхности. Именно такие изображения приходится сопоставлять в авиационных СТЗ. Для поиска ключевых точек на контурных изображениях разработаны оригинальные методы, например [41, 43], дающие достаточно хорошие результаты.
Алгоритмы сравнения площадей пересекающихся контуров протяженных объектов
Следует отметить, что при визуальном оценивании качества, человек весьма быстро принимает решение о том, удачное совмещение или нет. В частности, при оценивании результата на рисунке 3.5а, человеком будет вынесено решение об удачном совмещении, хотя там и присутствуют блоки с относительно невысокими 104 оценками (0,620,69). Оценка результата на рисунке 3.5б сразу будет признана неудовлетворительной по причине большого количества нулевых локальных оценок, соответствующих полному отсутствию совмещения. Таким образом, для человеческого восприятия более важна цельная картина, на фоне которой теряются отдельные локальные неточности. Однако для автоматического оценивания качества локальные оценки представляются крайне важными, позволяя получать сведения о качестве совмещения вблизи наиболее значимых объектов на ВММ: линии горизонта, водных объектов, дорожной инфраструктуры. На рисунке 3.6 приведена иллюстрация оценки качества предлагаемым алгоритмом по всему изображению. Рисунок 3.6 - Иллюстрация интегрального оценивания качества Оценка по интегральному критерию происходит следующим образом: ищется сумма локальных оценок в каждом блоке, определяемых по формуле осi =mim, причем пустые блоки (не содержащие информативных пикселей ни на одном из совмещаемых изображений), исключаются из рассмотрения. Затем эта сумма делится на общее количество блоков, за вычетом пустых. Итоговая оценка
Интегральные оценки качества совмещения контуров для 9 лучших наборов из 4 пар ключевых точек приведены в таблице 3.1. Данные результаты получены при разбиении исходного изображения на блоки размером 100x100 пикселей. Исходные изображения островов имеют размер 1700 х 1500 пикселей. Приведенные в таблице результаты достаточно интересны. Визуальный анализ рисунка 2.19 позволяет предположить, что наилучшими должны были бы быть наборы ключевых точек 3, 10, 15 или 16, и 17 или 18. Указанные наборы также дают достаточно высокое качество совмещения, например, для набора 3,10,15,18 значение показателя а качества совмещения равно 0,795. Однако, приведенные в таблице оценки качества совмещения выше (все больше 0,8).
Приведенный выше алгоритм зарекомендовал себя как надежное средство оценки качества совмещения в случае, когда на совмещаемых изображениях присутствует малое количество объектов, но большой протяженности. Следует отметить, что данный алгоритм будет давать хорошие результаты в том случае, когда на виртуальном изображении отсутствует «мусор», которому не соответствуют физические объекты на реальном изображении. В ходе сравнения результатов работы данного алгоритма с визуальными оценками качества совмещения установлено, что при значении интегрального показателя качества а 0,75 совмещение можно считать удачным и пригодным для дальнейшей визуализации [68].
Результат совмещения может быть оценен экспертно, но такой метод требует оценивать визуально значительное количество результирующих изображений и наличие человека-эксперта, что не всегда приемлемо. Возможность производить оценку с учетом эталонного совмещения, также сводиться к предварительному изготовлению значительного количества результатов совмещения, что также не представляется возможным при обработке большого массива данных. Предлагается иной алгоритм оценки совмещения основанный на векторном представлении изображений содержащих контуры объектов.
Также предлагается алгоритм оценки совмещения, основанный на векторном представлении изображений, содержащих контуры объектов. Этот алгоритм основан на подходе, предлагаемом в [69] и является его модификацией в части способа поиска и отбора отрезков, используемых для расчета оценки качества. Оценка совмещения изображений в данном случае сводится к нахождению расстояний и углов наклона между парами отрезков. Пары образуются отрезками, находящимися в составе линий контуров объектов, полученных на изображениях, с длиной превышающей или равной некоторому пороговому значению А. Исключение из анализа отрезков с длиной меньшей А позволяет существенно повысить точность получаемых оценок. За счет этого становится возможным не учитывать линии, соответствующие шумам на реальном изображении.
Для повышения достоверности оценки совмещения, каждому отрезку в составе линии на виртуальном изображении (ВММ) следует сопоставить в пару отрезки расположенные на реальном изображении в некоторой окрестности D. Окрестность D рассчитывается по координатам вершин отрезка на ВММ с учетом навигационных данных и погрешностей их измерения. Алгоритм состоит в следующем: результате выполнения шагов 1-5 алгоритма, для каждого отрезка виртуального изображения длиной больше или равной А, получили значения Kt, определяющие меру сходства с отрезками реального изображения, затем происходит усреднение показателя по всем отрезкам. Результат усреднения и будет искомой оценкой качества совмещения. Иллюстрация данного способа определения качества совмещения приведена на рисунке 3.7.
Описание отдельных модулей программного обеспечения
Для каждого кадра видеопоследовательности автомат пребывает в состоянии С1 только 1 раз, затем циклически повторяется цепочка С2С3C4С5С2. Таким образом, для пересчёта координат одной точки требуется 4 такта синхроимпульса.
Данный автомат в общем случае можно использовать параллельно для произвольного числа обрабатываемых точек, но это сильно усложняет структуру устройства и его отладку. Поэтому было принято решение использовать 32 параллельно работающих блока. Тогда для обработки изображения размером 704576 требуется 50688 тактов. Это соответствует 1,013 мс при частоте 50 МГц и 0.25мс при частоте 200 МГц. Выполнение аналогичной операции пересчета координат пикселей одного изображения к плоскости другого на ЭВМ классической архитектуры с однопоточной обработкой занимает в среднем 65мс. В случае использования четырех ядер процессора, время обработки сокращается 150 до 17 мс. Получаем, что аппаратная реализация алгоритма преобразования одного изображения к плоскости другого позволяет повысить быстродействие в 65 раз. После вычисления координат пикселей одного изображения, в плоскости другого, требуется лишь перестановка яркости пикселей в соответствии с новыми координатами. Возможно также комплексирование совмещаемых изображений.
Реализация алгоритма оценки качества совмещения изображений на основе межпиксельного расстояния Обработка изображений плавающим окном легко поддаётся распараллеливанию. Алгоритм оценки качества (приведен в пункте 3.4) относительно прост и использует малое количество элементов внутренней логики кристалла, что позволяет одновременное использование большого количества обработчиков.
Более узкое место – память кристалла. Однако, для реализации указанного алгоритма используются только два буфера памяти (реализованные на параметризированных блоках Xilinx Core Generator) и массив из 25 шестнадцатибитных регистров, хранящий смещения относительно адреса центра окна.
При реализации параллельной структуры необходимо учитывать перекрытия – области изображения, загружаемые одновременно в два обработчика. Для изображений размером 704576 пикселей целесообразно использовать от восьми до десяти параллельно работающих блоков.
Каждый блок обработчика представляет собой конечный автомат, содержащий 3 состояния: 1) загрузка части изображения с перекрытием в память; 2) непосредственно обработка – отыскание на втором изображении черных точек в окрестности kk обрабатываемой черной точки на первом изображении (размер окрестности поиска принят равным 55); 3) расчет локальных и интегральных показателей качества совмещения; 4) передача обработанной части изображения на Ethernet. 151 На обработку одной точки первого изображения требуется от 1 до 50 тактов. Если на первом (исходном изображении) яркость точки равна 255, то обработчик сразу переходит к следующей точке, затрачивая 1 такт. Если яркость точки первого изображения равна 0, а на втором изображении в пределах окна 55 нет точек с яркостью 0, то обработчик затрачивает 25 тактов. В случае, когда на втором изображении в окрестности 55 есть точка с яркостью 0, на её обработку тратится два такта: 1 – сравнение, 2 – запись по текущему адресу значение яркости – 100. То есть если для черной точки первого изображения все точки окна второго изображения также черные, обработчику потребуется 50 тактов синхроимпульса.
Дополнительные затраты на расчет интегральных и локальных показателей качества можно оценить в среднем как 5 тактов на 1 пиксель обрабатываемого изображения. На рисунке 4.32 приведена оценка предельного быстродействия обработки, измеряемая в кадрах в секунду, в зависимости от доли черных пикселей на первом обрабатываемом изображении. Зависимость предельного быстродействия от доли черных пикселей на изображении На практике возможно обрабатывать от 100 до 120 кадров в секунду, а ограничения на скорость обработки будет накладывать только канал передачи данных. В нашем случае используется Ethernet 1 Gbit.
При реализации данного подхода с применением вычислительной машины классической архитектуры с однопоточной обработкой была достигнута скорость обработки в 12-14 кадров в секунду. Таким образом, аппаратная реализация алгоритма оценки качества совмещения изображений на основе межпиксельного расстояния позволяет повысить быстродействие оценки качества в 8,5 раза.
В главе представлена структура разработанных программных средств для исследования и отладки алгоритмов совмещения изображений от бортовых датчиков с изображениями ВММ, а также оценивания качества получаемых результатов совмещения. Основные результаты:
1. Приведены результаты экспериментальной проверки алгоритмов, предлагаемых в главах 2 и 3, показана эффективность предложенных решений в сравнении с корреляционными методами и алгоритмами совмещения изображений.
2. Проработана аппаратная реализация основных алгоритмов, предложенных в настоящей работе: алгоритма проективного преобразования одного изображения к плоскости другого, алгоритма оценивания качества совмещения изображений на основе межпиксельного расстояния. Продемонстрирован выигрыш в быстродействии, получаемый за счет реализации названных алгоритмов в ПЛИС.
3. В ходе апробации алгоритмов доказана их применимость для решения задачи совмещения изображений в бортовом вычислительном комплексе летательного аппарата.