Картографирование при помощи монокулярной камеры

  • Вид работы:
    Дипломная (ВКР)
  • Предмет:
    Информационное обеспечение, программирование
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
  • Опубликовано:
    2019-05-23
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Картографирование при помощи монокулярной камеры

Оглавление

1.   Введение. 3

1.1 Цель работы.. 4

1.2.1 Камеры RGBD.. 5

1.2.2 Искусственное зрение в роботах. 6

1.2.3 Области применения. 7

1.2.4 Визуальное расположение. 9

2.   Математическая часть алгоритмов. 10

2.1   Визуальное расположение на основе геометрии. 10

2.1.1 Фильтр Кальмана. 12

2.2 Модель Маркова. 14

2.1.1 Марковское Местонахождение. 14

2.2 Метод Монте Карло. 15

2.1.1   Использование метода. 15

3.   Алгоритмы SLAM. Поиск детекторов и дескрипторов. 16

3.1 Поиск детекторов. 16

3.1.1 Алгоритм FAST. 16

4.   Картографирование на неизвестной карте. 24

4.1 Алгоритм SDVL. 24

4.1.1 Поиск 3D точек. 25

4.1.2 Расчет 3D позиции. 27

4.2 Совпадение точек между изображениями. 28

4.3 Картографирование. 31

4.3.1 Инициализация на карте. 32

4.3.2 Обновление неопределенности. 34

4.4 Локализация. 36

4.4.1 Выравнивание. 37

2.   Практическая часть. Построение карт. 38

5.1 Экспериментальный анализ алгоритма. 38

5.1.1 Описание практики. 38

5.1.2 Анализ алгоритма. 40

5.2 Точность и временная эффективность в комнате. 42

5.3  Случаи ошибок. 43

5.4 Глобальная оценка алгоритма 46

5.5 Сравнение с другими алгоритмами SLAM... 47

5.5.1 Сравнение точности. 48

5.5.2 Сравнение темпоральной эффективности. 49

6. Экономическая часть. 49

6.1 Введение. 49

6.2 Организация и планирование работ по теме. 50

6.3.1 Организация и планирование работ по теме. 51

6.3.2 График проведения работ: 52

6.3.3Определение договорной цены. 52

6.4 Оценка экономической целесообразности проведения работ по теме  56

6.5 Заключение экономической части. 58

7.   Литература. 59





1. Введение


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

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



 

 

 

Рис. 1.1:Использование роботов в жизни

 

 



1.1 Цель работы

В настоящее время позиционирование мобильных роботов внутри

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

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

SLAM (одновременная локализация и картирование) является очень хорошо изученным алгоритмом в последние годы. Он был впервые поднят на

Конференции по робототехнике и автоматизации IEEE в Сан-Франциско в 1986 году, и с тех пор было разработано множество методов, направленных на решение проблем позиционирования в интерьерах с различными вариантами алгоритма.

Целью этого проекта является проведение анализа различных решений для позиционирования внутри помещений на основе SLAM, которые были разработаны в последние годы. Во-первых, стратегии, разработанные несколькими методами, основанными на SLAM, будут проанализированы с целью проведения широкого изучения современного уровня техники SLAM.

Впоследствии, серия экспериментов, которые претендуют на изучение надежности методов, анализируемых при генерации карт и позиционирования. Хотя SLAM может выполняться с различных типов датчиков, все методы, используемые в настоящей работе, используют датчики зрения для получения данных об окружающей среде, однако в некоторых методах это будет монокулярное зрение, а в других - датчики, которые состоят из камеры и датчика глубины.

1.2.1 Камеры RGBD

Классические камеры предоставляют уникальную информацию о цвете для каждого из пикселей. Однако, в последние годы появился новый тип датчика, так называемые RGBD камеры, которые вместе с цветом передают и расстояние.

                                    Рис 1.2: Камера RGBD.

 

Бум этого датчика начался в 2010 году с выпуском Kinect (Рис. 1.2), устройство, проданное для использования с игровой приставкой Xbox 360. Хотя первоначально он был предназначен для индустрии видеоигр, его низкая цена и потенциальное использование заставили других производителей вывести аналогичные устройства на рынок и с тех пор они широко используются во многих областях исследований.

Первая версия Kinect определяла расстояние, при помощи света в инфракрасном диапазоне и распознавая, как этот рисунок появляется на инфракрасном изображении. Второе поколение Kinect, выпущенное в 2014 году, использует технологию времени полета (TOF) для вычисления расстояния до каждого объекта.

Эти типы устройств все чаще используются в приложения для компьютерного зрения, в основном для реконструкции сцен в 3D, для отслеживания людей или я движения.

1.2.2 Искусственное зрение в роботах

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

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

Многие роботы используют камеры в качестве основного датчика. Это относится к автономным автомобилям.

Существуют также роботы на основе визуального местоположения, такие как пылесосы из последнего поколения Dyson или iRobot (Roomba 980). Эти пылесосы используют визуальную локализацию для локализации внутри дома и могут определить свое местонахождение (рис.1.3).












                (А)                                                                                               (Б)

Рис 1.3: Пылесос марки Dyson (а) Карта, основанная на локализации Roomba 980 ( б).

1.2.3 Области применения

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

Ниже приведены некоторые примеры реальных приложений, использующих компьютерное зрение в роботах.

-Восприятие предметов: роботы могут воспринимать с помощью камер объекты в среде. На рисунке 1.6(a) показана одна из проблем Darpa Robotics Challenge, робот должен быть в состоянии обнаружить дверь и открыть ее.

          -Визуальный контроль: в соответствии с данными, полученными с камер, роботы моделируют поведение.

          -Навигация: информация с камер служит руководством для робота для безопасного перемещения в среде, обнаруживая потенциальные препятствия. Уже сегодня разработаны автономные автомобили различных марок, которые могут ездить без человека(рис. 1.4 (Б)).

          -Визуальная самопроверка: робот может непрерывно вычислять свою позицию в среде вокруг него через одну или несколько камер.

-Построение карт: благодаря перемещению, которое могут выполнять роботы, мобильные телефоны, камеры могут использоваться для создания 3D-карт окружающей среды.

-Визуальное внимание: в этом случае камеры робота служат основой для принятия решения в каких частях окружающей среды сосредоточить внимание робота, которое может быть использовано для отслеживания объектов или поиска зон в необработанной среде




(А)                                                                       (Б)

Рис 1.4: Робот (а). Google автомобиль (б).

1.2.4 Визуальное расположение

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

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

1. Робот имеет карту окружающей среды вокруг него и знает свое начальное положение.

2. Робот имеет карту своего окружения, но не знает первоначальное положение.

3. Среда неизвестна, и исходное положение может быть предположено в любом.

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

Расположение робота можно вычислить в двух или в трех измерениях, в зависимости от конкретной задачи. В средах, где используются роботы, достаточно вычислить положение робота в двух измерениях (так как его высота и ориентация известны). Однако при использовании беспилотных летательных аппаратов или свободных камер  нужно рассчитать местоположение с шестью степенями: три для вашего перемещения и три для его руководства.

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

Проблема локализации тесно связана с реконструкцией карты. Без точного местоположения невозможно создать карту среды, а без этой карты невозможно найти робота в в абсолютных координатах. Эта проблема была решена в двух различных областях исследований искусственного зрения, где она известна под названием Structrure From Motion, или же  SLAM (Simultaneous Localization And Mapping).

2. Математическая часть алгоритмов

2.1Визуальное расположение на основе геометрии

 Локализация, основанная на геометрии, заключается в определении позиции робота в определенный момент из его полученной информации. Для этого мы будем использовать камеру Pin-Hole.

                                                                         Рис2.1: камера Pin-Hole

В этой работе используется модель камеры Pin-Hole (рис. 2.1); эта модель предполагает, что все лучи света проходят через одну и ту же точку (фокус) и влияют на плоскость формирования изображение. Расстояние, которое отделяет фокусную плоскость и плоскость изображения является фокусным расстоянием, от которого зависит размер объектов, наблюдаемых на изображении. Эта модель работает с текущими камерами, потому что идеальные тонкие линзы способны концентрировать лучи света в одну точку.

Внутренние параметры камеры определяют условия формирования изображения и позволяют связать пространственную информацию с изображениями через матрицу калибровки. Матрица калибровки K состоит из фокусного расстояния в каждой оси(fx и fy) и положение оптического центра на изображении (u0 и v0), такие как показано в уравнение 2.1:

2.1.jpg

Эта модель камеры также имеет параметры положения и ориентация камеры в среде, и они, как правило, определены с помощью матрицы вращения-перемещения (RT) 3x4, такую, как в формуле (2.2).

2.2.jpg

Другой способ заключается в преобразовании 3D-точки (X, Z) в абсолютных координатах (x, z) в координаты относительно камеры (формула 2.3), а затем выполнить проекцию с использованием матрицы K, при условии, что z отличается от 0 (формула 2.4).

2.34.jpg

2.1.1 Фильтр Кальмана

Фильтр Кальманом (KF) - это вероятностный алгоритм, разработанный Рудольфом Кальманом, он позволяет оценить состояние динамической системы из наблюдений, которые могут содержать шум. KF может применяться только с линейными системами с несколькими измерениями если эти условия соблюдены, фильтр может предложить оценку состояния системы и меру неопределенности с которой была проведена оценка.

Фильтры Кальмана основаны на динамических системах, дискретизированных во времени. Состояние системы является N-мерной переменной xt. Кроме того, наблюдение за системой в каждой итерации является переменной zt, которая зависит только от xt. Чтобы использовать KF, необходимо указать ряд параметров (массивов) для адаптирования его к проблеме:

Ft: Модель перехода состояния.

Ht: Модель наблюдения.

Qt: Ковариация шума процесса.

Rt: Ковариация шума наблюдения.

Фильтр Кальмана предполагает, что фактическое состояние xt развивается в (t-1) с помощью уравнений 2.5:

2.5.jpg

Ft является моделью перехода состояния, который применяется к предыдущему состоянию xt-1 и wt шум процесса с ковариацией Qt.

Кроме того, предполагается, что ZT-наблюдение в итерации t фактического состояния xt выполняется в соответствии с формулой 2.6:2.6.jpg

где Ht - модель наблюдения, которая преобразует пространство состояния в пространство наблюдения, в то время как vt представляет шум наблюдения с Ковариацией Rt. KF является рекурсивным оценщиком, то есть используется только для оценки состояния предыдущей итерации и текущего наблюдения, независимо от предыдущего состояния.

Вектор состояния xt следует Гауссовскому распределению Nˆxt с массивом ковариация P. В свою очередь, вектор наблюдения, который имеет ковариационную матрицу S.

Оценка состояния на каждой итерации выполняется в два этапа: первый шаг известен как " предсказание” и отвечает за предсказание состояния и его ковариации, в то время как второй шаг известен как "обновление", где используется наблюдение для уточнения расчетного состояния.








2.2 Модель Маркова


Модели Маркова являются вероятностными алгоритмами, которые сохраняют дискретное рабочее пространство FDP со всеми возможными решениями. Это стохастический процесс, в котором только следующее состояние XT + 1 зависит от текущего состояния Xt. Это достигается тем, что система не имеет памяти, как это было достигнуто в Xt (формула 2.7):

2.7.jpg

2.1.1 Марковское Местонахождение


Для оценки местоположения робота в среде с использованием моделей Маркова. Он делит мир на сетку с ячейками с каждой из возможных позиций робота, где каждая ячейка(i, j) имеет связанную вероятность P (i, j), представляющую вероятность того, что робот находится в этом положении, а сумма вероятности всех ячеек равны 1 (Рис.2.3).

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

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

23.jpg 

Рис 2.3: двухмерная вероятностная сетка для оценки положения робота.4


2.2 Метод Монте Карло

Методы Монте-Карло- вероятностные алгоритмы, использующие случайность для поиска оптимального решения эффективно, представляя FDP в режиме выборки.  Алгоритмы Монте-Карло работают итеративно и должны иметь два основных механизма:

-Вероятностная модель наблюдения: механизм, используемый для оценки каждой части, что приводит к вероятности от 0 до 1.

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

2.1.1   Использование метода


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

11111111111.jpg

поскольку вероятность каждой части вычисляется с помощью функции стоимости. С помощью значения веса обновляются на каждой итерации. Эти веса изначально стоят 0 и изменяют их значение с помощью уравнений 2.9 и 2.10:

11111111111.jpg

количество PA частей, распределяются случайным образом в итерацию, дается уравнением 2.11:

11111111111.jpg

3. Алгоритмы SLAM. Поиск детекторов и дескрипторов

               3.1 Поиск детекторов

3.1.1 Алгоритм FAST

FAST, впервые предложенный в 2005 году , был одним из первых эвристических методов поиска особых точек, который завоевал большую популярность из-за своей вычислительной эффективности. В этом методе рассматривается яркость пикселей на окружности с центром в точке С и радиусом 3 (Рис.3.1)[21;5]










Рис. 3.1: Рассматриваемая окрестность точки  FAST детектора

Сравнивая яркости пикселей окружности с яркостью центра C, получаем для каждого три возможных исхода (светлее, темнее, похоже). Формула (12)


                                                                                                                                                                                      ( 12)

Где, I – яркость пикселей, t – некоторый заранее фиксированный порог по яркости.

Точка помечается как особая, если на круге существует подряд n=12 пикселей, которые темнее, или 12 пикселей, которые светлее, чем центр.

Как показала практика, в среднем для принятия решения нужно было проверить около 9 точек. Для того чтобы ускорить процесс, авторы предложили сначала проверить только четыре пикселя под номерами: 1, 5, 9, 13. Если среди них есть 3 пикселя светлее или темнее, то выполняется полная проверка по 16 точкам, иначе – точка сразу помечается как «не особая». Это сильно сокращает время работы, для принятия решения в среднем достаточно опросить всего лишь около 4 точек окружности.

У оригинального FAST есть следующие недостатки:

· Несколько рядом расположенных пикселей могут быть помечены как особые точки. Нужна какая-то мера «силы» особенности.

· Быстрый 4-точечный тест не обобщается для n меньше 12. Так, например, визуально наилучшие результаты метода достигаются при n=9, а не 12.



3.1.2Детектор Моравеца

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

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

Далее выполняется отсечение пикселей со степенью правдоподобности, меньшей некоторого порога. Для оставшихся точек принимается, что они являются особыми.

Детектор Моравеца является самым простым детектором углов. Автор данного детектора предлагает измерять изменение интенсивности пикселя (x;y) посредством смещения небольшого квадратного окна на один пиксель в каждом из восьми принципиальных направлений (2 горизонтальных, 2 вертикальных и 4 диагональных). Размер окна обычно выбирается равным: 3 на 3 , 5 на 5 или 9 на 9 пикселей. Детектор работает в несколько шагов[21;5]:

1.           Для каждого направления смещения  (13):

                                                                                                                                  (13)

вычисляется изменение интенсивности (14):

                                                                                                                                                                                               (14)

где  – интенсивность пикселя с координатами  в исходном изображении.

2. Строится карта вероятности нахождения углов в каждом пикселе изображения посредством вычисления оценочной функции (15)

(15)

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

3.   Отсекаются пиксели, в которых значения оценочной функции ниже некоторого порогового значения.

4.   Удаляются повторяющиеся углы с помощью процедуры NMS (non-maximal suppression). Все полученные ненулевые элементы карты соответствуют углам на изображении.

Основными недостатками рассматриваемого детектора являются отсутствие инвариантности к преобразованию "поворот" и возникновение ошибок детектирования при наличии большого количества диагональных ребер. Очевидно, что детектор Моравеца обладает свойством анизотропии в 8 принципиальных направлениях смещения окна.

3.1.3 Детектор MSER's

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

Рассмотрим идею алгоритма для случая черно-белого изображения. Представим все возможные отсечения изображения. В результате получим набор бинарных изображений при разных значениях

порога  (пиксель, интенсивность которого меньше порога считаем черным, в противном случае, белым). Таким образом, строится пирамида, у которой на начальном уровне, соответствующем минимальному значению интенсивности, находится белое изображение, а на последнем уровне, отвечающем максимальному значению интенсивности, – черное. Если в некоторый момент происходит движение, то на белом изображении появляются черные пятна, соответствующие локальным минимумам интенсивности. С увеличением порога пятна начинают разрастаться и сливаться, в конечном итоге образуя единое черное изображение. Такая пирамида позволяет построить множество связных компонент, соответствующих белым областям, – регионов с максимальным значением интенсивности. Если инвертировать бинарные изображения в пирамиде, то получим набор регионов с минимальным значением интенсивности. Схема алгоритма состоит из нескольких этапов:

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

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

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

3. Выполним для всех компонент поиск локальных минимумов (находим пиксели, которые присутствуют в данной компоненте, но не входят в состав предыдущих). Набор локальных минимумов уровня соответствует экстремальному региону на изображении.

3.2 Дескрипторы

3.2.1 Дескриптор SIFT

Для формирования дескриптора SIFT (Scale Invariant Feature Transform) сначала вычисляются значения магнитуды и ориентации градиента в каждом пикселе, принадлежащем окрестности особой точки размером 16 на 16 пикселей. Магнитуды градиентов при этом учитываются с весами, пропорциональными значению функции плотности нормального распределения с математическим ожиданием в рассматриваемой особой точке и стандартным отклонением, равным половине ширины окрестности (веса Гауссова распределения используются для того, чтобы уменьшить влияние на

итоговый дескриптор градиентов, вычисленных в пикселях, находящихся дальше от особой точки)[21;4].

В   каждом квадрате размером 4 на 4 пикселя вычисляется гистограмма ориентированных градиентов путем добавления взвешенного значения магнитуды градиента к одному из 8 бинов гистограммы. Чтобы уменьшить различные "граничные" эффекты, связанные с отнесением похожих градиентов к разным квадратам (что может возникнуть вследствие небольшого сдвига расположения особой точки) используется билинейная интерполяция: значение магнитуды каждого градиента добавляется не только в гистограмму, соответствующую квадрату, к которому данный пиксель относится, но и к гистограммам, соответствующим соседним квадратам. При этом значение магнитуды добавляется с весом, пропорциональным расстоянию от пикселя, в котором вычислен данный градиент, до центра соответствующего квадрата.

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

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

3.2.2Дескриптор GLOH

Дескриптор GLOH (Gradient location-orientation histogram) является модификацией SIFT-дескриптора, который построен с целью повышения надежности. По факту вычисляется SIFT дескриптор, но используется полярная сетка разбиения окрестности на бины (рис. 3.2): 3 радиальных блока с радиусами 6, 11 и 15 пикселей и 8 секторов. В результате получается вектор, содержащий 272 компоненты, который проецируется в пространство размерности 128 посредством использования анализа главных компонент (PCA).[20;2]










                                                  Рис. 3.2:Полярная сетка разбиения на бины

3.2.3 Дескриптор DAISY

DAISY изначально вводится для решения задачи сопоставления изображений (matching) в случае значительных внешних изменений, т.е. данный дескриптор в отличие от ранее рассмотренных работает на плотном множестве пикселей всего изображения. При этом авторы DAISY в работе показали, что дескриптор работает в 66 раз быстрее, чем SIFT, запущенный на плотном множестве пикселей. В DAISY использованы идеи построения SIFT и GLOH дескрипторов.

Аналогично GLOH выбирается круговая окрестность особой точки, при этом бины представляются не частичными секторами, а окружностями (Рис 3.3).[20;1]






Рис. 3.3: Сетка построения бинов для центрального пикселя

Для каждого такого бина выполняется та же последовательность действий, что и в алгоритме SIFT, но взвешенная сумма магнитуд градиентов заменяется сверткой исходного изображения с производными Гауссова фильтра, взятыми по 8 направлениям. Авторы показали, что построенный дескриптор обладает инвариантностью, как и SIFT, и GLOH, при этом для решения задачи сопоставления (matching) в случае, когда все пиксели считаются особыми, требует меньших вычислительных затрат.

 

4.   Картографирование на неизвестной карте


4.1 Алгоритм SDVL

Алгоритм SDVL следует философии PTAM и делится на два отдельных потока двумя основными задачами алгоритмов SLAM: с одной стороны, он вычисляет смещение камеры, а с другой-управляет картой среды.

На рис. 4.1 показана общая схема алгоритма; он имеет в качестве входных изображений камеры и в качестве выходных данных 3D-оценку с течением времени.

11111111111.jpg

Рис. 4.1: Схема алгоритма

Поток Mapping отвечает за создание, обслуживание и обновление карты среды робота. Для этого, P точек в 3D хранятся в K изображений (наблюдений), из которых эти точки наблюдаются. Не все наблюдения становятся частью карты, но только кадры, которые соответствуют определенным характеристикам, добавляются на карту (ключевые кадры или Keyframes).

Начальная карта создается на основе двух наблюдений с достаточным смещением между ними, которые становятся первыми двумя ключевыми фреймами карты. После этого новые 3D-точки добавляются в области карты, которые ранее не были изучены. Эти новые 3D-точки не рассчитываются непосредственно триангуляцией, как это происходит в PTAM, но инициализируются с учетом неопределенности в их глубине и сходятся по мере того, как робот перемещается и собирает новые наблюдения.

Поток Tracking отвечает за вычисление смещения камеры между двумя наблюдениями с использованием 3D-карты и самих наблюдений. Для расчета этого смещения было выбрано использование технологии hıbrida, основанной как на характерных pıxeles, так и на прямых методах.

Кроме того, система Tracking имеет систему отбраковки спурий (RDE) для удаления неправильно расположенных 3D-точек или движущихся элементов.

4.1.1 Поиск 3D точек

Самая простая параметризация для представления точки в 3 измерениях-это сохранение ее координат (X, Y, Z). Эта параметризация используется большинством алгоритмов SLAM (например, ранние версии MonoSLAM или PTAM). Однако его основной недостаток заключается в том, что он не позволяет точно представлять неопределенность в позиции точки в пространстве, особенно в ее глубине, когда она получена из изображений.

С учетом двух наблюдений, из которых видна одна и та же точка в 3D, можно вычислить положение этой точки с помощью триангуляции при условии, что смещение между наблюдениями относительно глубины точки является достаточным. Другими словами, угол, образующий 3D-точку относительно двух наблюдений (параллакс), должен быть достаточно широким, чтобы иметь возможность получить надежную оценку глубины.

Однако некоторые точки могут быть настолько далеки, что для достаточного параллакса может потребоваться большое смещение или, в худшем случае, могут существовать объекты в “бесконечности”, для которых никогда не будет достаточного параллакса (например, при инициализации точки со звездой).

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

Для реализации SDVL был использован метод, разработанный с адаптацией, предложенной представлять точки в бесконечности.  Таким образом, расчетная глубина каждой точки моделируется с помощью распределения вероятностей, используя каждое новое наблюдение для обновления распределения с помощью байесовского вывода алгоритма SVO. Исходный метод принимает в качестве входных данных набор мер x1· * * * xn, поступающих из датчика глубины. Этот датчик может производить два типа измерений: проверенную меру (inlier), с вероятностью π, обычно распределенную вокруг фактической глубины Z, и неправильную меру (outlier), с вероятностью 1−π в результате равномерного распределения в интервале [Zmin, Zmax]. С помощью этих данных следующая гауссово + равномерная смешанная модель описывает распределение вероятности измерения xn:

11111111111.jpg

Вероятность этой модели приближается с помощью гауссовского распределения для глубины Z и бета-распределения для вероятности:


В реализации алгоритма SDVL вместо прямого использования значений глубины Z и σ2 Z используется обратная глубина ρ = 1 Z и связанная с ней дисперсия σ2 ρ. Эта обратная параметризация облегчает представление точек в бесконечности, которая возникает, когда ρ равно 0.

4.1.2 Расчет 3D позиции


Из параметризации 3D точек с неопределенностью можно в любое время выполнить преобразование для расчета декартовой позиции 3D (X,Y,Z) в пространстве, хотя это преобразование может быть ошибочным, когда неопределенность высока.

Для расчета этой позиции 3D используется уравнение 6.4.

Где ρ-обратная глубина, TF и RF-это положение и ориентация в мире кадра, в котором обнаружена точка 3D, а (vx,vy,vz) - луч обратной проекции в координатах относительно камеры на изображении, где была первоначально обнаружена точка 3D (рис.4.1).

Рис.4.1

4.2 Совпадение точек между изображениями


Одним из фундаментальных элементов алгоритмов SLAM, основанных на характеристиках, является сопряжение точек между двумя наблюдениями. Учитывая два кадра F1 и F2 и точку X в 3D-пространстве, которая видна с обоих кадров, цель спаривания-найти пары p1 и p2, в которых X будет наблюдаться с каждого кадра.

Если вы точно знаете положение кадров и точки 3D, просто проецируйте X на каждый кадр, чтобы получить pıxeles p1 и p2. Тем не менее, из-за ошибок в наблюдениях и неопределенности в позиции 3D X, необходимо выполнить поиск, чтобы попытаться найти спаривание между pıxeles.

В SDVL точка всегда инициализируется с кадра F1, а позиция 2D p1, из которой она была впервые замечена, считается фиксированной, поэтому поиск выполняется на изображениях последовательных кадров (F2), в которых X виден. При инициализации новой 3D-точки глубина точно не известна, поэтому из F1 можно сделать вывод только о обратной проекции p1,которая содержит все точки в пространстве X1, X2,·**, xn, которые проецируются на p1.

Рис 4.2: Эпиполярная прямая, полученная при проецировании каждой точки Xi на плоскость изображения F2

Некоторые из этих точек X1, X2,·**, Xn будут видны из F2, и проекция каждой из этих точек образует прямую линию на плоскости изображение F2, которое принимает имя эпиполярной прямой (рис.4.2 )

Поиск выполняется только на участке эпиполярной прямой, соответствующей глубине в пределах интервала:

В случае, если ρ-2σρ меньше или равно 0, в качестве значения будет установлено достаточно небольшое положительное значение (например, 10-10), чтобы избежать деления на 0.

Поиск 3D-точки в новом наблюдении выполняется вдоль полученной эпиполярной прямой, предполагая погрешность вокруг этого (рис. 4.3 (a)). Погрешность вокруг эпиполярной прямой настраивается, но ее значение сильно влияет на конечное вычислительное время алгоритма.

Рис 4.3: Точки, выбранные для сопряжения 3D-точки: диапазон поиска вокруг эпиполярной прямой (a); обнаруженные характерные точки (зеленые), проверенные (оранжевые) и используемые в сопряжения (красные) (b).

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

Поскольку точки, полученные с помощью алгоритма FAST, сортируются по строкам и столбцам, не нужно проверять все обнаруженные точки, А достаточно их подмножества. На рисунке 6.6 (b) показано, как из всех точек FAST, обнаруженных на изображении (зеленый цвет), необходимо только проверить положение на изображении тех точек, которые разделяют строку и столбец с эпиполярной прямой (оранжевый).

Алгоритм FAST подробно рассмотрен в главе 3.



4.3 Картографирование


Поток Mapping отвечает за управление картой среды, в которой находится робот. Эта карта обновляется с каждым наблюдением и служит основой для расчета отслеживания камеры.

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

Чтобы определить, когда кадр хранится на карте как Keyframe, проверяются два условия:

1. Количество прошедших итераций: в случае создания Keyframe необходимо дождаться числа итераций по умолчанию, прежде чем можно будет создать другой. По умолчанию это значение имеет значение 30 итераций (1 в секунду).

2. Количество потерянных точек: количество видимых 3D точек сравнивается с теми, которые вы видите при создании последнего Keyframe. Если это число меньше, это означает, что очки были потеряны, и новый Keyframe будет создан, когда потеряно не менее 10% очков.

Для создания нового Keyframe эти два условия должны выполняться одновременно. Однако при очень резких перемещениях (особенно при поворотах) точки могут быть быстро потеряны, и эта процедура может привести к потере робота. Таким образом, если количество точек, потерянных после последнего Keyframe, превышает 30%, создается новый Keyframe, даже если с момента последнего не прошло достаточно итераций.

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

3D-точки, из которых состоит карта, - это те, которые были обнаружены одним или несколькими текущими ключевыми фреймами и доступны через каждый Keyframe, следуя схеме на рисунке 6.2.

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

4.3.1 Инициализация на карте


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

Во-первых, с помощью алгоритма FAST вы получаете характерные точки каждого нового наблюдения. Для того, чтобы использовать наблюдение, необходимо, по крайней мере, обнаружить 50 точек на изображении, хотя обычно алгоритм обычно получает более 300.

Первое наблюдение, которое соответствует этому условию, хранится как первый Keyframe алгоритма и служит основой для создания начальной карты. В последующих наблюдениях вычисляется смещение каждой точки, обнаруженной в первом Keyframe, с помощью оптического потока Лукаса-Канада.

Эта процедура повторяется до тех пор, пока среднее расстояние всех обнаруженных точек не превысит пороговое значение, и в этот момент считается, что между изображениями достаточно смещения, чтобы вычислить начальную карту, и последнее наблюдение сохраняется в качестве второго Keyframe карты.

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

Рис 4.4: Инициализация

После того, как первые два Keyframes доступны, начальная карта рассчитывается с использованием 5-точечного алгоритма. Предполагая, что оба наблюдения содержат доминирующую плоскость и с использованием алгоритма RANSAC, вы получаете H гомографию, который определяет преобразование перспективы между обоими изображениями (рис. 4.4), так что ошибка повторного выбора каждой пары точек минимизируется:



4.3.2 Обновление неопределенности


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

Для точек, наиболее близких к камере, смещение позволит достичь достаточного параллакса, уменьшив неопределенность в глубине и сближая значение обратной глубины с ее фактическим положением. Этап обновления каждой точки также является дорогостоящим и не стоит продолжать выполнять его, как только неопределенность будет достаточно небольшой. Чтобы определить, когда точка сходится в ее реальном 3D-положении и, следовательно, больше не нуждается в обновлении, используется предлагаемое условие конвергенции в, вычисление линейности L с помощью уравнений 6.7 и 6.8:

D расстояние от точки в 3D до текущего положения камеры и α параллакс точки 3D относительно первого и последнего наблюдения.

При таком уравнении, когда параллакс низкий, отклонение будет высоким. Будет близка к одному, получая высокое значение L. В то время как по мере увеличения параллакса оба σρ уменьшаются и, как следствие, значение L будет низким. Точка считается сходившейся, когда значение L меньше 0.1, значение, которое было экспериментально установлено.

Рис. 4.5: Конвергенция 3D точек после итераций.

На рис. 4.5 показан пример того, как 3D-точки сходятся с прохождением итераций. Первоначально все инициализированные точки имеют высокую неопределенность и поэтому их глубина неизвестна (красные прямые), но как только смещение камеры достаточно, некоторые из точек соответствуют условию конвергенции и фиксируют их глубину (синие точки).

Каждый раз при получении нового кадра (независимо от того, является ли он Keyframe) список кандидатов на карте просматривается, и они пытаются обновить свои позиции. Во-первых, проверяется, видна ли точка с текущего положения камеры, и в этом случае выполняется поиск точки по методу. Если точка находится, ее позиция в пространстве треугольника с использованием текущего кадра и исходного Keyframe, в котором этот кандидат впервые обнаружен. Это приводит к новой глубине, которая служит для обновления распределения вероятностей 3D-точки. Кроме того, проверяется, сходилась ли точка, чтобы продолжить в этом случае ее удаление из списка кандидатов.

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

4.4 Локализация


Другой основной поток выполнения алгоритма SDVL отвечает за отслеживание. Этот поток использует информацию, хранящуюся на карте, и наблюдения камеры, чтобы вычислить смещение робота от последней итерации, то есть постепенно. Кроме того, вы должны выполнить эту задачу, выполнив временные ограничения эффективности для работы в режиме реального времени. Исходя из положения и ориентации камеры в моменте t−1 (xt−1), вычисление конечной позиции в моменте t (xt) выполняется в четырех разных шагах:

1. Предполагая модель постоянной скорости, позиция текущего кадра XTI инициализируется с учетом позиции предыдущего кадра xt-1 и скорости, с которой камера перемещалась в последней итерации.

2. Текущее изображение выравнивается с изображением предыдущего кадра с помощью прямых методов, чтобы получить первое оценочное положение текущего кадра xte.

3. На 3D-карте проецируются доступные точки, и некоторые из этих точек сопоставляются с текущим изображением.

4. Наконец, результат спаривания точек учитывается для настройки конечного положения текущего кадра xt .

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

Ниже подробно описаны шаги 2, 3 и 4 для оценки положения кадра в потоке отслеживания.

4.4.1 Выравнивание

После применения модели движения к текущему кадру информация об интенсивности изображения используется для оценки первой позиции кадра xte, которая впоследствии будет уточнена. Из двух изображений Ft и Ft−1, которые наблюдают одну и ту же точку 3D X, остаток интенсивности δF определяется как фотометрическая разница между пикселями каждого кадра, в котором наблюдается X. позиция 2D в каждом кадре определяется проекцией X в каждом изображении, учитывая предполагаемую глубину 3D-точки. (рис. 4.6)

Рис 4.6

Это нелинейная проблема квадратов, которая может быть эффективно решена с помощью итеративного алгоритма Гаусса-Ньютона.

Остаток интенсивности δF рассчитывается с помощью патча 4x4 точки из изображения, в котором вы проецировали каждую точку 3D, следуя формулировке алгоритма обратного компонента, как это предлагается в. В этом случае патчи не преобразуются перед сравнением, так как предполагается, что смещение между каждым кадром будет небольшим.

Как следует из вышеизложенного, не пытайтесь выровнять изображения, используя все их точки, но с целью повышения временной эффективности используются только те pıxeles предыдущего кадра, которые связаны с 3D-точкой и видны из текущего кадра.

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

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

2. Практическая часть. Построение карт


5.1 Экспериментальный анализ алгоритма.

5.1.1 Описание практики

 

Эти эксперименты стремятся объективно охарактеризовать качество визуального самопроверки 3D с помощью алгоритма SDVL, анализируя, среди прочего, его прочность, точность и временную эффективность.

Алгоритм SDVL имеет несколько параметров настройки, которые влияют на конечный результат. Значения по умолчанию были экспериментально установлены для работы в большинстве сценариев. Наиболее важными параметрами являются:

1. Начальная прокрутка: смещение, необходимое для вычисления начальной карты. Слишком малое значение может привести к недостаточному параллаксу, а вычисленная карта ошибочна; обычно достаточно установить значения от 10 до 20 пикселей.

2. Число Keyframes: максимальное число Keyframes, что влияет на временную эффективность алгоритма. Если это число велико, сгенерированная карта будет содержать больше точек 3D, а временная эффективность будет меньше как в трекинге, так и в картографировании.

3. Коэффициент потерянных очков: максимальный процент потерянных очков с последнего Keyframe. Если это значение будет превышено, будет создан новый Keyframe, даже если с момента последнего удаления не прошло достаточно итераций.

4. Количество сопряжений: максимальное количество сопряжений, используемых в трекинге. Высокое число улучшит точность, но ухудшит временную эффективность в мгновенной оценке позиции 3D, что может глобально ухудшить качество оценки.

5. Отклонение спуска (RDE): включение или отключение отклонения спуска во время отслеживания.

6. Дескрипторы ORB: использование дескрипторов ORB, а не патчей, для выполнения спаривания точек.

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

Работа алгоритма представлена на рисунке 5.1 карта, преобразованная из видеоролика в 3D карту. Белые точки находятся на месте опорных точек, полученных по методу ORB. Именно эти точки представляют собой карту. 

https://pp.userapi.com/c851120/v851120021/11c9d1/BWTCVOO0G3U.jpg

Рис 5.1: Выведенная карта

5.1.2 Анализ алгоритма


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

Интерфейс этого алгоритма состоит из двух окон. Первый из них -это изображенный на рисунке 5.2, на нем отображается текущий кадр камеры. В нижней части окна отображается информация о состояние алгоритма:

· Режим. На фотографии мы видим, что он находится в режиме SLAM.

· Количество ключевых кадров.

· Количество точек на карте.

· Количество найденных ассоциаций.

· Положение в x и точка, в которой курсор находится над окном.

Рис. 5.2: Окно алгоритма

Второе окно-это окно, показанное на рис. 19. Оно содержит карту точекиз исследуемой среды. В нем есть несколько окон, которые позволяют нам отслеживать, какая информация должна отображаться на экране, и переключать режим функционирование. Кроме того, в центральной части отображается карта, созданная при навигации робота по окружающей среде. На карте отображаются следующие элементы:

·   Зеленый прямоугольник: текущее положение камеры.

·   Синие прямоугольники: Keyframes

·   Красные точки: точки текущей локальной карты.

·   Черные точки: точки карты.

Рис 5.3: Второе окно алгоритма

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

5.2 Точность и временная эффективность в комнате


Для этого эксперимента используется последовательность Office Room 3 (OR3)испытательного стенда ICL-NUIM. Эти видео выполнены с помощью свободной камеры, которая выполняет круговое движение вокруг комнаты. Окружающая среда характеризуется небольшим размером и небольшим количеством текстур, поэтому количество точек на карте не будет очень высоким.

Точность алгоритмов была оценена с использованием абсолютной ошибки траектории (ATE), которая измеряет разницу между каждой оцененной позицией и абсолютной истиной с учетом временных меток; для этого сначала выстраиваются траектории, выполняя разложение на единичные значения (SVD), а затем вычисляется расстояние между каждой парой точек.

На рисунке 5.1 показана сгенерированная карта и ошибка, полученная в отношении абсолютной истины при первой настройке.

Рис 5.1: Сгенерированные карты

5.3  Случаи ошибок

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

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

·   Очень быстрое перемещение: очень быстрое перемещение приводит к ошибкам в спаривании главным образом по двум причинам: 3D-точки могут выходить из диапазона поиска изображения, а изображения обычно не имеют достаточной резкости из-за этого типа смещения, что приводит к неправильному сопряжению точек и потере алгоритма. Кроме того, это также затрудняет создание новых точек, не будучи замеченным в достаточном количестве кадров, чтобы быть инициализированным с garantıas.

·   Вращение без перемещения: вращение без перемещения создает новые 3D-точки с высокой неопределенностью и служит только руководством для оценки ориентации робота. Это приводит к тому, что переносы не рассчитываются правильно, а карта теряет согласованность с реальностью.

·   Сценарии с очень удаленными точками: в сценариях, где все обнаруженные точки находятся вдали, происходит что-то похожее на предыдущий случай; точки На карте будут иметь большую неопределенность и перенос не будет рассчитан должным образом, что приведет к ошибочному местоположению.

·   Похищения в новые области карты: если робот потерян или происходит похищение, он может быть перенесен только в том случае, если он вернется в ранее известную позицию; если это не произойдет, робот будет потерян на неопределенный срок.

·   Неправильно рассчитанная начальная карта: генерация начальной карты с помощью homografıa в значительной степени влияет на точность алгоритма, загрязняя все последующие оценки позиции. Во-первых, инициализация является частью основы того, что доминирующая плоскость существует в сцене, где находится часть обнаруженных точек, которая не должна возникать. Даже в том случае, если это произойдет, выбор начальной точки может привести к неправильному вычислению начальной плоскости (рис. 5.2), что приведет к тому, что алгоритм будет первоначально поддерживаться в 3D-точках, позиция которых ошибочна.

Рис 5.2: начальная конфигурация с использованием различных пороговых значений FAST

5.4 Глобальная оценка алгоритма

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

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

·   Bundle Adjustment: несмотря на временную потерю эффективности, которая возникает в потоке сопоставления при использовании BA, его использование является необходимым условием, если высокая точность необходима в больших сценариях. В любом случае это не влияет на эффективность отслеживания, которая является потоком, который должен работать в режиме реального времени.

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

Короче говоря, как BA, так и RdE оказались незаменимыми, если вы хотите иметь алгоритм с высокой точностью и надежностью. Со своей стороны, использование дескрипторов ORB имеет преимущества (более точность) и недостатки (меньшая эффективность отслеживания), поэтому его использование зависит от практического применения алгоритма SDVL.

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



5.5 Сравнение с другими алгоритмами SLAM


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

Методы, с которыми он сравнивал: PTAM, SVO, LSD-SLAM и ORBSLAM, которые считаются наиболее иллюстративными и интересными. Они использовали эталонные реализации авторов этих алгоритмов, с некоторыми адаптациями, чтобы предоставить им те же входные данные и гомогенизировать их выходные результаты. Параметры настройки этих алгоритмов были изменены в каждом случае, чтобы получить наилучшие результаты, и отображаемые результаты - это те, которые получили большую точность после 3 прогонов.

 


 


 

5.5.1 Сравнение точности


Точность, полученная (RMSE в метрах) в каждом из проведенных экспериментов, показана ниже:

Эксперименты с “X” - это те, которые не смогли отслеживать робота в течение как минимум 30% времени, в то время как результаты со звездочкой-это те, которые частично отслеживали (от 30 до 70%). Эксперименты, которые не завершили последовательность, отмечены красным цветом, а синими, которые получили лучший результат в каждом из них.

Алгоритм с более высокой точностью в большинстве экспериментов был ORB-SLAM, особенно в сценариях с широкими траекториями. Со своей стороны, SVO также очень точен в некоторых сценариях, но в конечном итоге теряется в 3 из 6 экспериментов. LSD-SLAM и PTAM были наименее точными в этом сравнении, первый из которых имеет самую большую ошибку локализации в большинстве экспериментов, а второй-потому, что ему удалось закончить последовательность только в одном из них.

Что касается алгоритма, разработанного в этом тезисе, полученная точность была расположена в промежуточной зоне по сравнению с другими алгоритмами, причем почти во всех экспериментах версия алгоритма с дескрипторами ORB более точна. На рисунке 7.9 показаны траектории, оцененные алгоритмом ORB-SDVL, и ошибка в отношении абсолютной истины четырех последних сценариев.

5.5.2 Сравнение темпоральной эффективности


Время выполнения (в МС) потока отслеживания экспериментов было следующим:

В этом случае алгоритм с более высокой временной эффективностью был SVO, с отличными результатами в несколько миллисекунд. С другой стороны, ORB-SLAM был с самым большим временем вычислений, в некоторых случаях немного выше значений, необходимых для работы в режиме реального времени. Что касается LSD-SLAM, время было в промежуточном значении между двумя предыдущими алгоритмами, тогда как в PTAM трудно сделать выводы, поскольку он быстро потерял себя в самых сложных сценариях.

Предлагаемый алгоритм был несколько сокращен, располагаясь между временной эффективностью SVO и эффективностью LSD-SLAM. В этом случае эффективность настройки без ORB была намного лучше, чем с ORB, с временами, близкими к 40% ниже.

6. Экономическая часть                                           

6.1 Введение

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

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

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

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

6.2 Организация и планирование работ по теме.

В составе работы задействовано 3 человека:

1) руководитель – отвечает за грамотную постановку задачи, контролирует отдельные этапы работы, вносит необходимые коррективы и оценивает выполненную работу в целом;

2) инженер – реализация всех поставленных задач, в том числе подготовка проектной документации.

3) тестировщик – контрагенты, ответственные за проведение тестирования готового продукта.

В табл.1 представлен расчет времени, необходимый на каждый этап разработки.

№ п/п

Наименование этапа

Срок выполнения, дней

1

Разработка технического задания

2

2

Согласование ТЗ

1

3

Разработка ТЭО

2

4

Анализ исходных данных и требований, постановка задачи

10

5

Разработка структуры программы и логической структуры базы данных. Разработка алгоритма

10

6

Согласование разработок с требованиями Заказчика

2

7

13

8

Отладка ПО

5

9

Тестирование

2

10

Разработка и оформление эксплуатационных документов

9

Итого дней:

56

Табл.1

6.3.1 Организация и планирование работ по теме.

В табл.2  представлены организационные этапы работ с указанием трудоемкости и продолжительности работ для каждого исполнителя на каждом этапе.

Название этапа

Исполнитель

Кол-во дней

Занятость на этапе, чел/дни

1

Разработка технического задания

Руководитель

2

1

Разработчик

1

2

Согласование ТЗ

Руководитель

1

1

Разработчик

1

3

Разработка ТЭО

Руководитель

2

1

Разработчик

1

4

Анализ исходных данных и требований, постановка задачи

Разработчик

10

10

5

Разработка структуры программы и логической структуры базы данных. Разработка алгоритма

Разработчик

10

10

6

Согласование разработок с требованиями Заказчика

Руководитель

2

1

Разработчик

2

7

Разработка ПО

Разработчик

13

13

8

Отладка ПО

Разработчик

5

5

9

Тестирование

Руководитель

2

1

Тестировщик

2

10

Разработка и оформление эксплуатационных документов

Руководитель

9

1

Разработчик

9

Итого

56

60

Табл.2

     

6.3.2 График проведения работ:

Календарный график исполнения работы представлен на рисунке 6.1. Из рисунка 1 так же видно, что общий срок разработки составит 56 дней.

 Рис.6.1

6.3.3Определение договорной цены.

Цена договорная = себестоимость + прибыль + НДС



себестоимость

 
1 статья «Материалы, покупные изделия и полуфабрикаты + ТЗР» (15%) от ∑ итого по материалам

2 статья «Специальное оборудование» - как правило, затрат нет

3 статья «Основная заработная плата»

4 статья «Дополнительная заработная плата» 20% от основной заработной платы

5 статья «Страховые отчисления» - 30% от ФОТ

6 статья «Командировочные расходы» - как правило, затрат нет

7 статья «Контрагентские услуги» - как правило, затрат нет

8 статья «Накладные расходы» - 250% от ОЗП

9 статья «Прочие расходы» - затрат нет

10 статья «Налог на добавленную стоимость(НДС)»

6.3.3.1 «Материалы, покупные изделия и полуфабрикаты + ТЗР»

Расходы по 1 статье представлены в табл.3

№ пп

Наименование

материалов

Единицы измерения

Количество

Цена за единицу (руб)

Стоимость (руб)

1

microSDHC-32ГБ

Шт

1

800

800

2

Бумага А 4

Пачка

1

220

220

3

Картридж для принтера

Шт

1

1700

1700

Итого материалов

2720

Транспортно-заготовительные расходы

408

Итого

3128

Табл.3

6.3.3.2 «Специальное оборудование»

Расходов нет.

 

 

6.3.3.3«Основная заработная плата»

Расчет основной заработанной платы представлен в табл. 5

Исполнитель

Мес.оклад, руб

Занятость на этапе, чел/дни

Оплата за день, руб

Оплата за этап, руб

1

Руководитель

50000

1

2272

2272

Разработчик

30000

1

1363

1363

2

Руководитель

50000

1

2272

2272

Разработчик

30000

1

1363

1363

3

Руководитель

50000

1

2272

2272

Разработчик

30000

1

1363

1363

4

Разработчик

30000

10

1363

13630

5

Разработчик

30000

10

1363

13630

6

Разработчик

30000

2

1363

2726

Руководитель

50000

1

2272

2272

7

Разработчик

30000

13

1363

17719

8

Разработчик

30000

5

1363

6815

9

Руководитель

50000

1

2272

2272

Разработчик

30000

9

1363

12267

Итог

82236

Табл.5

6.3.3.4 «Дополнительная заработная плата»

 Дополнительная заработная плата составляет 20% от суммы основной заработной платы.

ДЗП = 82236 х 0,2 = 16447,2 руб.

Дополнительная заработная плата научного и производственного персонала составляет по проекту 16447,2  руб.

6.3.3.5 «Страховые отчисления»

Отчисления на социальные нужды составляют 30% (22% - взносы в Пенсионный фонд, 5,1% - фонд обязательного
медицинского страхования, 2,9% - взносы в фонд социального страхования) от фонда оплаты труда (ФОТ), который состоит из основной и дополнительной заработной платы.

ФОТ = ОЗП + ДЗП = 82236 + 16447,2 = 98683,2  руб.

СВ = ФОТ х 30% = 98683,2 х 0,3 = 29604,96  руб.

6.3.3.6 «Командировочные расходы»

Расходы по данному разделу отсутствуют.

6.3.3.7 «Контрагентские услуги»

В процессе разработки данного проекта были использованы услуги тестировщика. Оплата производилась по договору и составила 7000.



6.3.3.8 «Накладные расходы»

1

Цифровая камера Альтами SCMOS02000KPA

шт

1

6790

6790


2

Микрокомпьютер Raspberry Pi 3 model B


шт


1


4990


4990

Итого оборудования

11780

Транспортно-заготовительные расходы

1767

Итого

13547

Накладные расходы:

НР = (ОЗП+О) х 250% = (82236+13547) * 2,5 = 239457,5 руб.

6.3.3.9 «Прочие расходы»

По статье «прочие расходы» затрат нет.

6.3.3.10 «Налог на добавленную стоимость (НДС)»

Разработка ведется на базе кафедры информационных систем института кибернетики МИРЭА-Российский технологический университет, поэтому НДС не взымается.

В табл.6 представлен расчет полной себестоимости проекта.

№ пп

Номенклатура статей расходов

Затраты (руб)

1

Материалы, покупные изделия и полуфабрикаты (за вычетом отходов)

3 128

2

Специальное оборудование для научных (экспериментальных) работ

-

3

Основная заработная плата научного и производственного персонала

82236

4

Дополнительная заработная плата научного и производственного персонала

16447,2

5

Страховые взносы в социальные фонды

29604,96

6

Расходы на научные и производственные командировки

-

7

Оплата работ, выполненных сторонними организациями и предприятиями

7000

8

Накладные расходы

239457,5

9

Прочие прямые расходы

-

10

НДС

-

Итого

385120,66

Табл.6

Норма прибыли составляет 30% от стоимости разработки.

прибыль будет равна:

П = 351253,16* 30% = 105376 руб.

Разработка ведется для коммерческой  организации, данный вид работы облагается налогом на добавочную стоимость (НДС) в размере 20%:

НДС = (С+П)х20% = (385120,66+105376)х0,2= 98 099,332 руб.

Таким образом, договорная цена будет представлять собой:

ДЦ = С+П + НДС =385120,66+105376+ 98 099,332 = 588596 руб.

6.4 Оценка экономической целесообразности проведения работ по теме

1.   Данное ПО позволяет строить карты и может быть использовано во всех сферах жизни человека. Начиная, от робопылесоса, заканчивая построением карт в местах, где человек не может находится в виду различных причин

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

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

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


Картограф, разработанный нами

Metaphase Pro Photoscan

Необходимая конфигурация

•ОС Windows XP или более поздняя (32 или 64 бит), Mac OS X Snow Leopard или более поздняя, Debian / Ubuntu (64 бит)

 • Процессор Intel Core 2 Duo или более мощный

• 2 Гб оперативной памяти

• Windows XP или более поздняя (64 бит), Mac OS X Snow Leopard или более поздняя, Debian / Ubuntu (64 бит)

• Процессор Intel Core i7

•12 Гб оперативной памяти

Скорость

Вычисления на графических процессорах (GPU), ускоряющих работу программы. Поддерживаемые устройства:

NVidia GeForce серии 8xxx и более поздних.

ATI HD серии 5xxx и более поздних.

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

Интерфейс

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

Сложный интерфейс.
Программа заточена для работы профессионалов, обладающих достаточными знаниями.

Оборудование

Для работы необходима обычная камера с расширением больше 5МП

Необходимо купить и установить дорогостоящие лидары.


6.5 Заключение экономической части

В результате выполнения экономического раздела выпускной квалификационной работы были выполнены следующие задачи:

·   Разработка основных  бизнес-плана, включающего описание продукта, анализ рынка сбыта, определение конкурентоспособности, создание плана маркетинга, создание плана производства и выделение основных этапов разработки макета устройства.

·   Организация и планирование проведения работ по теме. В данном разделе вычислена трудоёмкость и продолжительность работы для каждого исполнителя в каждом этапе и создана таблица для удобства представления данных.

·   Определение договорной цены, включает в себя расчет себестоимости по десяти статьям, расчет НДС и учитывает прибыль.

·   Оценка экономической целесообразности, включает в себя обоснование создания макета устройства.

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

7. Литература


1. Лохин В.М., Манько С.В., Романов МЛ., Александрова Р.И. и др. Универсальная бортовая система управления для автономных мобильных объектов ВВТ // Материалы III научно-практической конференции «Перспективные системы и задачи управления»

2. Романов МЛ., Гарцеев И.Б. Интеллектуальная система навигации для малоразмерных подвижных объектов ВВТ // Материалы III научно-практической конференции

3. Castellanos J.A., Neira J., Tardos J.D. Limits to the consistency of the EKF-based SLAM. In Intelligent Autonomous Vehicles 

4. Durrant-Whyte, Hugh. Localization, Mapping, and the Simultaneous Localization and Mapping Problem. Australian Center for Field Robotics. 

5. Montemerlo M., Thrun S., Koller D., Wegbreit B. Fastslam: A factored solution to the simultaneous localization and mapping problem. 

6. Benjamin E.F. Opportunities to increase the accuracy of positioning technologies simultaneously positioning and mapping (SLAM).

7. Bailey T., Nieto J., Guivant J., Stevens M., Nebot E. Consistency of the EKF-SLAM algorithm. 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems.

8. Bailey T., Durrant-Whyte H. Simultaneous localization and mapping (SLAM): Part II. IEEE Robotics & Automation Magazine.

9. Rasmussen C., Hager G.D. Probabilistic data association methods for tracking complex visual objects. IEEE Transactions on Pattern Analysis and Machine Intelligence

10. Guivant J.E., Nebot E.M. Optimization of the simultaneous localization and map-building algorithm for real-time implementation. IEEE Transactions on Robotics and Automation

11. Neira J., Tardos J.D. Data association in stochastic mapping using the joint compatibility test. IEEE Transactions on Robotics and Automation

12. Davey S.J. Simultaneous localization and map building using the probabilistic multi-hypothesis tracker. IEEE Transactions on Robotics

13. Sun F., Wang T., Lu W. A data association method based on simulate anneal arithmetic for mobile robot SLAM. 2008 IEEE International Conference on Automation and Logistics 

14. Zhang S., Xie L., Adams M. An efficient data association approach to simultaneous localization and map building. The International Journal of Robotics Research

15. Bailey T., Nebot E.M., Rosenblatt J.K., Durrant-Whyte H.F. Data association for mobile robot navigation: A graph theoretic approach. 2000 Proceedings of IEEE International Conference on Robotics and Automation 

16. Karpenko A.P., Sinyagovskaya O.A. Global optimization with the use of a biogeography-based method. Nauka i obrazovanie MGTU im. N.E. Baumana

17. Karpenko A.P., Chernobrivchenko K.A. Multimemeev modified hybrid ant algorithm for HCIAC continuous optimization. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU

18. Pareek N.K., Patidar V., Sud K.K. Image encryption using chaotic logistic map. Image and Vision Computing.

19. Платоное АЖ., Зуева ЕМ., Киртьченко А.А., Соколов СМ. Формальные подходы к проектированию алгоритмов информационного обеспечения мобильных систем (выбор пути, навигация, надёжность).

20. Богуславский А.А., Киртьченко А.А., Платонов АЖ., Соколов СМ., Трифонов О.В., Ярошевский B.C. Построение описания внешней среды в системах информационного обеспечения мобильных робототехнических комплексов 

21. Обеспечения систем технического зрения реального времени // Труды II Всероссийской научной конференции "Методы и средства обработки информации". 

22. Sokolov S.M., Boguslavsky A.A., Kuftin F.A. Vision System for Relative Motion Estimation from Optical Flow // Proc. 13th Intern. Conf on Systemics, Cybernetics and Informatics (WMSCI 2009)

23. Александрова А А., Ахтёров А.В., Воронин AM., Киртьченко А А., Соколов СМ., Швай-ковский ЕМ. Основы теоретической робототехники. Теория толерантных пространств (обзор) 

24. Платоное АЖ., Соколов СМ., Сазонов В.В., Богуславский А.А., Трифонов ОМ., Куфтин ФА., Васильев А.И., Моксин КА. Программно-аппаратный комплекс средств навигации мобильных систем // Вопросы оборонной техники. Сер. 9. Специальные системы управления, следящие приводы и их элементы. 

26. Block-based vanishing line and vanishing point detection for 3d scene reconstruction. In 2006 / Y. M. Tsai, Y. L. Chang, L. G. Chen 

27. Ashutosh Saxena, Sung H Chung, and Andrew Y Ng. 3-d depth reconstruction from a single still image. 

28. Battiato Sebastiano, Curti Salvatore, La Cascia Marco, Tortora Marcello, Scordato Emiliano. Depth map generation by image classification.

29. Everett H.R. Sensors for Mobile Robots: Theory and Application.

30. Ulrich I., and Nourbakhsh. Appearance-Based Obstacle Detection with Monocular Color Vision. Proceedings of the AAAI National Conference on Artificial Intelligence 











Похожие работы на - Картографирование при помощи монокулярной камеры

 

Не нашел материал для своей работы?
Поможем написать качественную работу
Без плагиата!