Содержание к диссертации
Введение
1 Алгоритмы выделения контуров рельефа городской местности на телевизионных изображениях в интересах видеопозиционирования мобильных роботизированных аппаратов 13
1.1 Вводные замечания 13
1.2 Алгоритм сегментации телевизионных изображений в целях предварительного устранения областей, соответствующих крупным мешающим объектам 20
1.3 Алгоритм классификации сегментов телевизионных изображений в целях предварительного устранения областей, соответствующих крупным мешающим объектам
1.3.1 Определения набора используемых признаков 26
1.3.2 Обоснование алгоритма классификации 27
1.3.3 Экспериментальные исследования эффективности классификации сегментов изображени я 30
1.4 Алгоритм выделения элементов контуров рельефа городской местности на област ях интереса с уменьшением влияния мешающих объектов с малыми угловыми размерами 33
1.4.1 Алгоритм выделения элементов контуров рельефа городской местности 33
1.4.2 Алгоритм бинаризации на основе анализа гистограммы яркости сегментов 34
1.4.3 Алгоритм выделения элементов сигнатур контуров рельефа местности на бинарных сегмента х изображения
1.5 Алгоритм предварительной обработки сегментов телевизионных изображений в целях уменьшения влияния мешающих факторов атмосферного характера 42
1.6 Алгоритмы распознавания характерных объектов городской местности для уменьшения зоны неопределенности при видеопозиционировании мобильных роботизированных аппаратов 46
1.7 Структурная схема алгоритма выделения контуров рельефа городской местности на телевизионных изображениях 52
1.8 Экспериментальные исследования по определению точности выделения контуров рельефа городской местности на телевизионных изображениях 54
1.9 Выводы 57
2 Алгоритмы видеопозиционирования мобильного роботизированного аппарата на основе контуров рельефа городской местности выделенных на телевизионных изображениях 59
2.1 Вводные замечания 59
2.2 Обоснование структурной схемы способа видеопозиционирования 62
2.3 Алгоритм видеопозиционирования на основе контуров рельефа городской местности и цифровой карты
2.3.1 Обоснование алгоритма видеопозиционирования 67
2.3.2 Определение достижимых характеристик алгоритма видеопозиционирования на основе исследования свойств целевой функции 72
2.4 Алгоритм определения позиции мра как глобального минимума целевой функции.. 94
2.5 Алгоритм видеопозиционирования на основе контуров рельефа городской мест ности и цифровой карты с использованием информации о характеристиках движения мобильного роботизированного аппарата 102
2.6 Алгоритм видеоориентации мобильного роботизированного аппарата по азимуту на основе контуров рельефа городской местности и цифровой карты при известных координатах 107
2.7 Исследование эффективности уменьшения зоны неопределенности при использовании алгоритма распознавания характерных объектов местности 113
2.8 Выводы 117
3 Практическая реализация алгоритмов видеопозиционирования на современной элементной базе 119
3.1 Вводные замечания 119
3.2 Увеличение быстродействия алгоритмов видеопозиционирования и уменьшение требуемого объема памяти 120
3.3 Исследования современной вычислительной элементной базы в целях выбора средств для реализации системы видеопозиционирования 130
3.4 Особенности реализации алгоритмов видеопозиционирования на базе отечественной микросхемы кх1879вя1я
3.4.1 Обоснование структурной схемы реализации системы видеопозиционирования на базе микросхемы К1879ВЯ1Я 143
3.4.2 Структура программного обеспечения микросхемы К1879ВЯ1Я при реализации алгоритмо в видеопозициони ровани я 147
3.4.3 Структура программного обеспечения микросхемы К1879ВЯ1Я при реализации захвата изображений 149
3.4.4 Структура программного обеспечения микросхемы К1879ВЯ1Я при реализации этапа поиска минимума целевой функции 155
3.5 Экспериментальные исследования точности определения координат при использовании макетного образца системы видеопозиционирования 156
3.5.1 Конструкция экспериментального макета 156
3.5.2 Описание эксперимента 160
3.6 Выводы 162
Заключение 164
Список литературы 166
- Алгоритм классификации сегментов телевизионных изображений в целях предварительного устранения областей, соответствующих крупным мешающим объектам
- Алгоритм видеопозиционирования на основе контуров рельефа городской местности и цифровой карты
- Алгоритм видеоориентации мобильного роботизированного аппарата по азимуту на основе контуров рельефа городской местности и цифровой карты при известных координатах
- Структура программного обеспечения микросхемы К1879ВЯ1Я при реализации захвата изображений
Введение к работе
Актуальность работы. В связи с расширением использования мобильных роботизированных аппаратов (МРА) в последние годы возникает потребность в исследовании различных принципов позиционирования данных объектов и разработке соответствующих систем на их основе. Перспективными при отсутствии сигналов спутниковых радионавигационных систем с точки зрения использования в целях локального позиционирования являются способы определения местоположения на основе телевизионных видеоданных об окружающей городской местности, полученных из видеокамер (ВК), расположенных на борту МРА. Исследованиям в области обработки изображений с целью получения информации об окружающей обстановке посвящены работы таких зарубежных ученых, как Д. Форсайт, Дж. Понс, Р. Гонсалес, Р. Вудс, Л. Шапиро, Дж. Стокман и др., а также отечественных исследователей: Сойфера В.А., Визильтера Ю.В., Дворковича А.В., Алпатова Б.А., Бехтина Ю.С., Еремеева В.В., Клочко В.К., Фаворской М.Н., Приорова А.Л. и др. При этом в области видеонавигации и позиционирования на основе изображений работали такие зарубежные ученые, как С. Турн (Стэнфордский университет), В. Бургард (Фрайбургский университет имени Альберта-Людвига), Д. Фокс (Вашингтонский университет), Я. Кошечка, В. Жанг (Университет Джорджа Мейсона). В то время как отечественные исследования в направлении навигации по физическим параметрам окружающей местности производились Джанджгава Г.И. (Московский энергетический институт), В.И. Сырямкиным, В.С. Шидловским, И.Н. Белоглазовым, В.П. Тарасенко (Томский государственный университет), В.К. Баклицким (Московский авиационный институт) и др.
Использование телевизионных систем видеопозиционирования (СВП) обеспечивает следующие преимущества: автономность, так как для организации работы СВП не требуется какой-либо внешней инфраструктуры (спутников, опорных станций и т.п.); малозаметность ввиду отсутствия значительного излучения при работе видеоаппаратуры; устойчивость к электромагнитным воздействиям, в особенности по сравнению со спутниковыми радионавигационными системами; широкое распространение и невысокая стоимость видио-камер по сравнению с радиолокационными и лазерными устройствами.
Наиболее остро преимущества СВП проявляются в городской местности, где методы спутникового позиционирования, и без того уязвимые при воздействии различных помех, дополнительно подвергаются действию таких мешающих факторов, как электромагнитные возмущения, возникающие вследствие работы промышленных установок и телекоммуникационных систем, многолучевость и затенение сигналов спутников высокими зданиями. При этом характер телевизионного изображения (ТИ), полученного МРА в городской местности, в большей степени обусловлен координатами точки
съемки, чем для большинства природных зон (степь, лес, пустыня, тундра и т. п., которые имеют достаточно монотонный вид на больших территориях).
Использование в целях видеопозиционирования МРА контуров рельефа городской местности, представляющих границу между крупными неподвижными объектами, нанесенными на карту, и фоном (небом), обеспечивает такие преимущества, как неизменность информативной части контура, выделенного на ТИ, полученных из одной точки в разное время (при фиксированной ориентации и параметрах ВК); неповторимость контура при изменении координат точки съемки. При этом отдельно можно отметить небольшой объем информации, требуемый для описания контура рельефа местности в виде сигнатур. Вместе с тем при использовании контура рельефа городской местности требуется цифровая карта (ЦК), включающая высоты представленных на ней объектов, а также некоторые данные об ориентации телевизионных ВК во время съемки изображений, причем для улучшения характеристик СВП возможно применение информации о движении МРА. В то же время целесообразно использование видеопозиционирования совместно с иными способами определения координат для обеспечения взаимного дополнения.
Цель и задачи работы. Целью работы является разработка способа и алгоритмов обработки ТИ окружающей среды, обеспечивающих выделение контуров рельефа городской местности при наличии мешающих факторов и мешающих объектов для видеопозиционирования МРА.
В соответствии с поставленной целью при выполнении работы требуется решить следующие задачи:
- разработать алгоритм сегментации ТИ в целях предварительного
устранения областей, соответствующих крупным мешающим объектам;
разработать алгоритм классификации сегментов ТИ в целях предварительного устранения областей, соответствующих крупным мешающим объектам;
разработать алгоритм выделения элементов контура рельефа городской местности на сегментах ТИ при уменьшении влияния мешающих объектов с малыми угловыми размерами;
разработать алгоритм распознавания характерных объектов городской местности на ТИ для уменьшения зоны неопределенности при видеопозиционировании;
обосновать структурную схему алгоритма выделения контуров рельефа городской местности на ТИ;
разработать алгоритм видеопозиционирования МРА на основе контуров рельефа городской местности при использовании ЦК;
разработать алгоритм видеопозиционирования МРА на основе контуров рельефа городской местности и информации о параметрах движения МРА при использовании ЦК;
разработать алгоритм видеоориентации МРА на основе контуров рельефа городской местности и известных координат МРА использующий ЦК;
произвести анализ технической реализации рассмотренных алгоритмов видеопозиционирования МРА на современной элементной базе.
Научная новизна. При выполнении данной работы получены следующие новые научные результаты:
предложен способ видеопозиционирования МРА в городской среде на основе контуров рельефа местности, выделенных на ТИ окружающей обстановки, и ЦК;
обоснована целесообразность использования сигнатур контуров рельефа городской местности и сигнатур неинформативных направлений в интересах видеопозиционирования МРА;
- предложен алгоритм сегментации ТИ в целях предварительного
устранения областей, соответствующих крупным мешающим объектам;
предложен алгоритм классификации сегментов ТИ в целях предварительного устранения областей, соответствующих крупным мешающим объектам, обеспечивающий величину вероятности правильной классификации порядка 0,84;
предложен алгоритм выделения элементов контуров рельефа городской местности на сегментах ТИ с уменьшением влияния мешающих объектов с малыми угловыми размерами, обеспечивающий значения ошибки выделения элементов сигнатуры контура рельефа местности в пределах 0,63 градуса;
обоснована структурная схема алгоритма выделения контуров рельефа местности на ТИ окружающей обстановки, при этом экспериментально определенная угловая ошибка выделения сигнатур составила величину в пределах 2,3 градуса;
предложен алгоритм распознавания характерных объектов городской местности для уменьшения зоны неопределенности при видеопозиционировании, обеспечивающий величину вероятности правильного обнаружения снимка, содержащего объект, составляющую 0,85 при значении вероятности ошибки второго рода, равном 0,05;
обоснована структурная схема способа видеопозиционирования при наличии дополнительной информации и действии мешающих факторов;
предложен алгоритм видеопозиционирования на основе контуров рельефа городской местности и ЦК при наличии информации об ориентации МРА относительно горизонтальной плоскости;
- предложен алгоритм видеопозиционирования на основе контуров ре
льефа местности и ЦК с использованием информации о характеристиках дви
жения МРА;
предложен алгоритм видеоориентации МРА по азимуту на основе контуров рельефа городской местности и ЦК при известных координатах;
проведены исследования эффективности уменьшения зоны неопределенности при использовании распознавания характерных объектов городской местности;
предложен ряд мер по уменьшению вычислительных ресурсов, требуемых на реализацию системы видеопозиционирования МРА.
Методы исследования. В работе использовались методы вычислительной математики, статистической радиотехники, математической статистики, функционального анализа, причем численные исследования сочетались с экспериментальными.
Достоверность. Достоверность представленных результатов обосновывается корректным использованием математического аппарата, а также сопоставлением результатов, полученных при применении численных исследований и экспериментальным путем.
Практическая ценность работы. Предложенные в работе алгоритмы выделения контуров рельефа городской местности на ТИ окружающей обстановки и видеопозиционирования на основе полученной информации, а также меры по уменьшению вычислительных затрат на их реализацию могут быть использованы при создании систем позиционирования МРА.
Результаты диссертационной работы были использованы в ОАО «Российские космические системы» и в учебном процессе ФГБОУ ВО «Рязанский государственный радиотехнический университет», что подтверждается соответствующими актами о внедрении.
Основные положения, выносимые на защиту.
1. Способ видео позиционирования на основе контуров рельефа
городской местности, выделенных на телевизионных изображениях
окружающей обстановки; цифровой карты; данных об ориентации бортовых
ВК в момент съемки относительно горизонтальной плоскости.
2. Алгоритм выделения контуров рельефа местности на телевизионных
изображениях городской среды в целях видеопозиционирования МРА при
действии мешающих факторов, обеспечивающая величину угловой ошибки
определения сигнатур в пределах до 2,3 градуса.
3. Двухэтапный алгоритм видео позиционирования МРА,
использующий на первом этапе последовательный поиск совместно с
методом градиентного спуска при постоянном шаге, в целях определения
области глобального минимума целевой функции, а на втором этапе -
локальную оптимизацию методом градиентного спуска с дроблением шага в
интересах уточнения координат. При этом обеспечивается ошибка
видеопозиционирования МРА в пределах 0,81 м при использовании
видеосистемы, дающей полный круговой обзор по азимуту.
Апробация работы. Результаты исследований, проведенных в данной работе, докладывались на следующих конференциях:16-й МНТК «Цифровая обработка сигналов и ее применение - DSPA-2014», Москва, 2014; XIX ВНТК «Новые информационные технологии», Рязань, 2014; 18-й МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2015; XX ВНТК «Новые информационные технологии», Рязань, 2015; XVIII МНТК «Математические методы в технике и технологиях», Рязань, 2015; XIX Международном форуме по проблемам науки, техники и образования, Москва, 2015, 18-й МНТК «Цифровая обработка сигналов и ее применение - DSPA-2016», Москва, 2016; МНТК «Современные технологии в науке и образовании», Рязань 2016.
Публикации. По теме диссертации опубликовано 13 работ, в том числе 5 в изданиях, рекомендованных ВАК, получен 1 патент РФ RU2583756 «Способ определения местоположения на основе сигнатур изображений городской застройки в видимом и инфракрасном диапазонах», а также 1 свидетельство о государственной регистрации программы для ЭВМ № 2016611707 «Программа имитационного моделирования работы системы позиционирования в городской местности на основе видеоданных об окружающей обстановке».
Структура работы. Работа содержит три главы, введение, заключение, список литературы из 124 наименований, список сокращений и обозначений и приложения. Общий объем работы составляет 198 страниц, в том числе 117 страниц основного текста, 67 рисунков и 3 таблицы.
Алгоритм классификации сегментов телевизионных изображений в целях предварительного устранения областей, соответствующих крупным мешающим объектам
Сегментация ТИ производится с целью разделения снимка на некоторые участки, из которых впоследствии при классификации выделяются области интереса, используемые в дальнейшем при обработке. Таким образом осуществляется устранение областей, соответвующих крупным МО. В то же время при сегментации, используемой в составе алгоритма выделения СКРМ на изображении городской местности, целесообразно рассматривать текстурированные области ТИ, так как данные участки соответствуют зданиям (то есть информативным объектам представленным на цифровой карте), Тогда как участки снимка с гладкой функцией яркости характерны для фона или подстилающей поверхности. Для выявления текстурированных областей ТИ целесообразно использовать детекторы особых точек (ОТ) в виде углов - точек, образованных пересечением прямых на ТИ, окрестность которых характеризуется двумя доминирующими направлениями градиента [42].
Наиболее известным детектором углов, используемым в системах технического зрения, является детектор Харриса [5, 42], работа которого включает определение характера градиента функции яркости в некоторой локальной окрестности пиксела путем подсчета средних значений градиента по разным направлениям. При этом в случае если градиент в окрестности пиксела незначителен, то данная точка принадлежит области с равномерной функцией яркости. В то же время при наличии в рассматриваемой окрестности границы будет наблюдаться высокое значение градиента по одному из направлений, причем наличие углов характеризуется большим значением градиента по двум направлениям.
Данный детектор применяется в предлагаемом алгоритме сегментации благодаря следующим свойствам [42]: обеспечивает максимальное количество детектированных точек в сильно текстурированных областях ТИ; - имеет относительно высокое быстродействие; - инвариантен к сдвигу и вращениям. Работа алгоритма включает, приведение цветного изображения 1(п,т) к монохромному виду IG(n,m), при этом детектирование в точке (п0,т0) включает поэлементное перемножение участка изображения размером s х s с центром, имеющим координаты (п0,т0), с квадратным ядром G(u,v): y(w,v) = 2,2/G(«0-s/2 + w,m0-s/2 + v)-G( ,v), (1.1) н=0 v=0 где u,v = 1...s, G(u,v) - гауссиан, Y(u,v) - результирующая функция яркости в окрестности точки (п0,т0). В последующем вычисляются частные производные уи и yv яркости по (вертикальная и горизонтальная составляющие градиента): Уи (и, v) = Y(u, v) - Y(u -1, v), (1.2) yv(u,v) = Y(u,v)-Y(u,v-1), (1.3) и рассчитывается решающая функция: Н(п0,т0) = det(Q) / tr(0) = у- у- Уу- у-) , (1 4) 2 2 У +У где Q = у f Лу и УУ Л ) Ґ Лу и У v \ J7 - матрица локальной структуры, Y - среднее зна чение Y В качестве точек изображения, содержащих углы, принимаются локальные максимумы функции H(n,m), в которых функция превышает некоторый порог н а-тах(Н(п,т)), где « = [0,1] -экспериментально определяемый коэффи циент.
Для разделения особых точек на группы по координатам (п,т) предложено применять алгоритм кластеризации на основе метода К-средних [5, 6, 43, 44]. Данный метод предполагает разделение множества точек на К кластеров (сегментов), при этом /-тая особая точка Т,. относится ку-тому сегменту 5\ с центром С., в случае если некоторая мера D(T.,C.) принимает наименьшее значение из набора {D QXD C,),...,D(T.,C )}. В качестве меры D используется евклидово расстояние D(T.,Cy.) = J(n.-n )2 +(mi-mj)2 , где (n.,m.) и (n ,mp - соответственно координаты Т. и С. на q-й итерации алгоритма кластеризации.
Блок-схема алгоритма кластеризации по методу К-средних представлена на рисунке 1.5. Можно увидеть, что работа алгоритма кластеризации включает предварительное определение К центроидов Q к, множества особых точек на кластеры согласно описанному выше принципу. Затем вычисляются координаты центроидов для следующей итерации: / [n ,irj] = — [n.,m.], TsS (1.5) после чего осуществляется переопределение кластеров и выполняется следующая итерация алгоритма. Предваврительный выбор центроидов ч Разделение особых точек на сегменты Перевычисление координат центроидов Jr Проверка условия останова С Конец )которое производится случайным образом, с последующим разделением всего
Выход из алгоритма происходит при выполнении условия останова, при котором координаты центроидов, вычисленные для следующей итерации, отличаются от текущего значения на величину, которая меньше некоторого заданного порога Ас: (nqj - nf1)2 + (т) - mf1)2 Ac. (1.6) Алгоритмы кластеризации, основанные на методе -средних, получили широкое распространение благодаря относительно небольшим вычислительным затратам, требуемым при их реализации, и интуитивной простоте. Однако эффективность использования данного алгоритма в большинстве его применений зависит от правильного выбора количества кластеров, на который разбивается исходный набор точек.
Таким образом, предлагается эвристический алгоритм, включающий выделение ОТ при помощи детектора Харриса при последующем разделении дан ных точек на группы методом K-средних [5, 43] с дальнейшим выделением прямоугольных областей ТИ (сегментов), соответствующих полученным группам (рисунок 1.6).
Для представленного в данной работе алгоритма сегментации, используемого в целях последующего выделения СКРМ, также важно корректное определение числа сегментов. При слишком малом числе сегментов уменьшается возможность исключения неинформативных направлений, так как увеличивается размер сегмента, а вместе с ним и вероятность попадания в один сегмент элементов изображения, соответствующих разным классам (например, МО и элементам застройки). При слишком большом числе сегментов (соответственно при наименьшем их размере) увеличивается вероятность пропуска элементов контура рельефа застройки ввиду неоднородности расположения особых точек (рисунок 1.7).
Алгоритм видеопозиционирования на основе контуров рельефа городской местности и цифровой карты
Рассмотренные в известных работах алгоритмы оценки местоположения различных мобильных аппаратов на основе вдеоданных используют совмещение характерных особенностей изображений [20, 21], корреляционное сопоставление снимков [22 - 27], а также корреляционное сравнение профилей некоторых физических полей (высота, глубина, магнитное поле Земли, и т. п.), формируемых при движении объекта [55-57].
Так, в работе [20] представлена система городского позиционирования, использующая ТИ и основанная на распознавании фасадов зданий с поиском особых точек, выделяемых детектором Харриса, при наличии соответствующей базы данных. В этом случае неизбежно возникают проблемы, связанные с чувствительностью детекторов особых точек к внешним условиям, масштабу, дальности до распознаваемого фасада, освещению и т. д. Вместе с тем такой способ позиционирования может быть реализован при наличии на местности зданий с характерным фасадом, не заслоненных мешающими объектами. Использование в целях определения особых точек детекторов и дескрипторов SIFT (Scale Invariant Features Transform) уменьшает чувствительность подобных алгоритмов к масштабу, однако сохраняются проблемы, связанные с устойчивостью полученных решений при действии внешних факторов [21].
В то же время в работе [22] предлагается способ позиционирования, включающий выделение линий с использованием детектора Хаффа на изображении, полученном с помощью бортовой камеры наземного объекта, и определение местоположения при использовании ортофотоснимков (аэрофотоснимков, полученных в результате процедур устранения искажений и учета рельефа, представляющих более точное положение объектов в плане [19]). При этом не используется информация о высоте объектов представленных на изображении, и рассматривается работа системы на участках, свободных от мешающих объектов.
Также можно выделить группу работ [23, 24], в которых производится обучение алгоритма определения позиции МРА на основе выделения локальных особенностей изображений при предварительном проведении по маршруту робота под руководством человека [23] или при обработке объемной базы данных снимков [24]. Изложенные в этих работах подходы требуют значительного изучения и подготовки МРА на местности, что исключает их применение при отсутствии априорной информации в ряде задач.
В работах [27, 55, 56, 57], посвященных главным образом корреляционно-экстремальным системам навигации, представлены способы позиционирования, основанные на информации о рельефе местности или е изображении. При этом во всех случаях объект навигации находится высоко над неровностями рельефа. Это относится к навигации летательных аппаратов по оптическим или радиолокационным ТИ поверхности, а также надводных и подводных средств по эхо-локационному изображению дна. Однако эти методы не подходят для решения задачи позиционирования наземного МРА в урбанизированной местности.
Алгоритмы оценки местоположения МРА при использовании информации о контуре рельефа местности в виде сигнатур рассматриваются в работах [34, 39, 58 - 61]. Информация о контурах рельефа застройки, получение которой рассматривается в предыдущей главе, может быть использована совместно с информацией об ориентации робота для определения позиции МРА.
Вместе с тем представляет интерес алгоритм позиционирования с применением дополнительной информации в виде оценки перемещения МРА и ориентации в азимутальной плоскости. Такая информация может обеспечиватся системой инерциальной навигации (СИН) совместно с одометром, которые в большинстве случаев присутствуют в составе МР А.
При этом вариантом применения сигнатур может быть ориентация в азимутальной плоскости при наличии информации о позиции МР А. Актуальность такого применения СВП обусловлена низкой точностью магнитных приборов ориентации в городской местности ввиду большого количества металлических конструкций и электромагнитных помех.
Алгоритмы распознавания ХОМ в целях уменьшения зоны неопределенности при позиционировании МРА в городской местности представлены в предыдущей главе. В то же время требуется рассмотрение алгоритмов уменьшения зоны неопределенности на основе различной информации о ХОМ.
Исходя из вышеизложенного во второй главе работы необходимо обосновать: - алгоритм видеопозиционирования МРА в городских условиях на основе информации о контурах рельефа местности и цифровой карты при наличии данных об ориентации системы; - алгоритм видеоориентации МРА в городской местности при наличии координат объекта; - алгоритм видеопозиционирования МРА в городской местности при наличии данных о параметрах движения объекта (определение местоположения робота при наличии сигнатур, полученных в нескольких точках, а также данных о значении составляющих вектора перемещения между этими точками и ориентации МРА в момент их прохождения); - алгоритм уменьшения зоны неопределенности при использовании распознавания ХОМ.
Алгоритм видеоориентации мобильного роботизированного аппарата по азимуту на основе контуров рельефа городской местности и цифровой карты при известных координатах
Можно увидеть, что точки сетки АП расположены в основном в застроенных областях, в то время как точки АЛ - на открытых участках.
Экспериментальное исследование эффективности предложенного алгоритма проводилось при описанных выше условиях (N = 13 участков городской местности с различными типами застройки общей площадью 10,4 кв. км., NП = 130 различных позиций МР А). В качестве метода локальной оптимизации для определения локальных минимумов на ОУМ используется метод градиентного спуска с постоянным шагом Ах (таким же, как при последовательном поиске). Принят минимальный размер ОУМ г = 100 м, а также величина шага Ах = 12 м, которая обоснована выше.
В результате получены зависимости СКО ошибки видеопозиционирования от угловой ошибки выделения сигнатур (2.22).
Зависимость СКО ошибки позиционирования от угловой ошибки выделения сигнтаур значения СКО ошибки видеопозиционирования а =0.81 м при условии использования АВКРМ с приведенными выше характеристиками, что составляет достаточно близкую величину с исследованным выше в данном пункте алгоритмом, использующим на первом этапе только последовательный поиск. При этом сокращение шагов вычисления ЦФ (то есть вычислительных затрат на первом этапе) составило величину 12…41 % для различных участков местности.
Можно сделать вывод, что при использовании данного алгоритма сохраняется возможность применения заранее сформированной базы эталонов, ввиду применения фиксированного шага и обеспечивается некоторое уменьшение вычислительных затрат за счет использования априорной информации о свойствах ЦФ.
Алгоритм видеопозиционирования на основе контуров рельефа городской местности и цифровой карты с использованием информации о характеристиках движения мобильного роботизированного аппарата
В данном пункте рассматривается задача видеопозиционирования МРА при наличии следующих исходных данных: информации о контурах рельефа местности (СКРМ и СНН), полученной на основе изображений, снятых в определенные моменты движения МРА в некоторых точках зоны неопределенности (точках съемки); - оценки приращений координат между точками съемки (ТС); - оценки ориентации робота в ТС. Предполагается, что на некотором начальном участке траектории МРА двигается без видеопозиционирования, при этом осуществляются съемка изображений и получение сигнатур при использовании АВКРМ; расчет данных о приращениях координат и ориентации на основе СИН и одометра, которые входят в состав большинства современных МРА. Затем производится привязка пройденной траектории к глобальной системе координат и при дальнейшем движении МРА видеопозиционирование может осуществляться как с использованием информации из СИН [77], так и в автономном режиме.
Для рассматриваемого алгоритма видеопозиционирования предлагается использовать ЦФ следующего вида: fix, у) = X {6-Nf-NP NP,N/ ч (2.39) пр=0 п=\ где Nр - количество ТС, ф(пр), в(пр) - оценка азимута и угла возвышения и крена ВК в пр-й ТС при полученнии изображений соответственно, Sx(np), 8у(їір) - оценки приращений координат между пр-й и (пр-1)-й ТС (Sx(1) = 0, Sy(1) = 0). Представленная ЦФ имеет смысл суммы модулей разности СКРМ, полученных в различных ТС, и соответствующих ЭС, построенных с учетом приращений координат Sx(np), 8у(пр) при движении МРА между ТС. Данная функция аналогична по форме приведенной в пункте 2.2, однако за счет использования дополнительной информации ожидается некоторое увеличение площади зоны однозначного видеопозиционирования и точности оценки координат.
Для исследования свойств СВП рассматриваемого вида целесообразно выбрать более конкретные параметры алгоритма позиционирования. Рассматривается СВП, использующая информацию о движении МРА, полученную при помощи СИН при наличии 2-х точек съемки.
На рисунке 2.22 представлены экспериментально полученные зависимости количества ПЛМ от площади зоны неопределенности для различных типов застройки при использовании двух точек съемки с расстоянием / = 50 м, полученные в результате применения процедур, аналогичных изложенным в п. 2.3.2 (кривые 1 и 2 соответствуют первому и второму типу застройки).
Анализ приведенных зависимостей, показывает, что при использовании информации о движении МРА наблюдается значительно меньшее количество ПЛМ. Однако скорость роста количества ПЛМ изменяется с расстоянием меж ду точками съемки.
Как указанно в п. 2.3, зависимость количества ПЛМ от площади зоны неопределенности хорошо аппроксимируется линейным законом. На рисунке 2.23 представлена зависимость среднего количества ПЛМ на 1 кв. км kПЛМ , имеющая смысл углового коэффициента аппроксимирующей прямой, принятого на основе метода наименьших квадратов (зависимости 1 и 2 соответствуют первому и второму типу застройки).
Можно увидеть, что среднее количество ПЛМ на 1 кв. км возрастает с увеличением расстояния между точками съема (например, увеличение расстояния с 1р = 10 м до 1р = 30 м, приводит к росту коэфициента с =10 до кплм =4,8). Это объясняется тем, что контуры рельефа местности на ТИ, полученных из близко расположенных друг к другу точек, достаточно схожи и эффекта увеличения информации не происходит. В то же время при определенной величине расстояния / данный эффект проявляется все менее и величина кплм стабилизируется. В случае выбора расстояния / также следует учесть, что ошибки оценок, обеспечиваемых ИНС, пропорциональны времени работы системы. На основании сказанного выбирается значение расстояния между точками съемки 1р=50 м, котрому соответствуют значения кплм=4,12 для первого типа застройки и кплм = 16,5 - для второго. При этом СКО значения аппроксимированного количества ПЛМ от полученных экспериментально данных со 104 ставляет 7ПЛМ =37 и УПЛМ =12 соответственно для первого и второго типа застройки. В этом случае для современных ИНС среднего и низкого класса, используемых в составе МРА при комплексировании с одометром [78], точность измерения перемещения составляет величину в 1 % от пройденного пути и менее, что позволяет принебречь влиянием ошибок ИНС на работу СВП, использующей информацию о движении МРА.
Структура программного обеспечения микросхемы К1879ВЯ1Я при реализации захвата изображений
Наиболее затратной с точки зрения вычислительных ресурсов частью работы СВП является этап 1 алгоритма определения местоположения МРА на основе сигнатур, обеспеченных АВКРМ (п 2.2). На данном этапе производится поиск области непрерывности ЦФ, содержащей полезный максимум, путем вычисления значений ЦФ в каждой точке области Л, равномерно покрывающей область неопределенности с шагом Аг. Согласно формуле (2.6) расчет ЦФ включает вычисление ВКФ (циклической свертки) выделенных сигнатур с ЭС, с последующим определением максимального отсчета ВКФ Мс с его позицией пс и разности между циклически сдвинутой на пс отсчетов ЭС и СКРМ с учетом СНН.
В свою очередь основные вычислительные затраты при расчете значения ЦФ по формуле (2.6) соответствуют операции циклической свертки (ЦС). Известные процедуры ускоренного вычисления ЦС используют разложения исходных сигналов в различных базисах [88-96], причем выигрыш достигается при наличии быстрых алгоритмов, обеспечивающих данные преобразования. На рисунке 3.1 представлены зависимости количества операций умножения и сложения QB, требуемого для реализации ЦС двух последовательностей от двоичного логарифма их длины NB: nB=\og2(NB) при прямом вычислении ДПФ, быстрых преобразований Уолша [88, 94], быcтрых преобразований Хаара [96], использовании БПФ [90-92] (соответственно кривые 1, 2, 3, 4).
Можно увидеть, что при длине входных данных более 256 процедура быстрой свертки на основе БПФ требует наименьшего объема вычислений. Также можно отметить глубокое теоретическое развитие данных преобразований [90-92], и большое количество вариантов его реализации на различной элементной базе [90]. В связи с этим для технического исполнения СВП целесообразно использовать процедуру вычисления ЦС на основе БПФ.
Вместе с тем предлагается хранить в памяти СВП вместо эталонных сигнатур, используемых при вычислении ЦФ, опорные спектры, полученные при использовании преобразования Фурье. При этом ЭС, состоящей из N1=6-N действительных остчетов, сопоставляется N1 остчетов действительной части комплексного спектра и столько же отсчетов мнимой части. Однако согласно свойствам ДПФ для дискретного спектра действительного сигнала, представленного четным колличеством А остчетов, выполняется равенство: S(g) = (S(N1 /2 -д)) , п = 1,N1 /2. (3.1) Поэтому в памяти СВП можно хранить только по N1 /2 остчетов действительной и мнимой части комплексного спектра ЭС.
Можно увидеть, что основной вес спектра ЭС сосредоточен в окрестности нулевого отсчета, что позволяет хранить в памяти СВП усеченный комплексный спектр, содержащий только отсчеты мнимой и дейстивтельной части комплексного спектра ЭС, соответствующие номерам / —, где К 2-К р коэффициент усечения, который получается из формулы SBУ(z,j) = SB(z,j) при; 2. , (3.2) здесь SBУ(z,j), SB(z,j) - соответственно усеченный и полный комлексный спектр ЭС для z-й точке множества А с координатами (х у ): SB (z, j) = F(B(xz, yz, 360, T, 0,0,«)). (3.3) Впоследствии при вычислении ЦФ в определенной точке из памяти выгружается Npl(2-Kp) отсчетов усеченного спектра ЭС, после чего вычисляется опорный спектр где adit(SBУ,r) - функция дополнения нулями, вычисляемая по формуле: adit(SBУ (z, j),r, j) \SBУ(zj), j r; 0, r j N2-r; (SBУ(z,N-j)) , N2-r j N (3.5) здесь N2 - ближайшее к 6-N, число равное целой степени двойки (реализации алгоритмов БПФ в основном представлены для таких длин входных данных).
При вычислении ЦФ на основании данного опорного спектра возникают некоторые искажения, связанные с потерей информации при усечении спектра и проявляющиеся в увеличении уровня ПМ с последующим уменьшением площади однозначного видеопозиционирования. На основании пункта 2.2 примем, что JV = 480, соответственно N2 = 512, в этом случае зависимость уровня ПМ при поиске минимума ЦФ от коэффициента усечения представлена на рисунке 3.3.
Можно увидеть, что уровень ПМ возрастает при увеличении коэффициента усечения. Предлагается принять величину коэффициента усечения Кр=4, при которой обеспечивается UГ = 0,42, при этом согласно исследованиям, приведенным в предыдущей главе, уменьшение площади однозначного видеопозиционирования составит 8-21 %, что является приемлемым значением.
Ввиду необходимости хранения в запоминающем устройстве ЭС для точек площади зоны неопределенности объем памяти, требуемый для хранения усеченного спектра эталонных сигнатур, можно оценить по формуле: =(Хг.(Д)-6)/ , (3.6) где Ъ - объем памяти, требуемый для хранения одного остсчета ЭС, Ki =(l-kb)-S/Ar2 - количество итераций поиска, кь - доля площади зоны неопределенности, занятая зданиями. Данный параметр определяется процентом застроенности города и в среднем составляет кь =0,35. С учетом вышесказанного и параметров, приведенных в п. 2.2, примем S = 100 кв. км, Аг = 12 м, Ъ = 1 Б, количество итераций поиска определяется согласно выражению К, = (1 - 0,35) 100 106 /144 = 451389. Тогда, используя принятое значение коэффициента Кр=4, можно рассчитать объем памяти, требуемый для хранения усеченных спектров ЭС, который составит Wx = 55,1 МБ, при этом в отсутствие усечения (К = 1) данная величина равна Wx = 220,4 МБ.