Модифицированный ICP алгоритм для несопоставленных 3D облаков
Ознакомление с традиционной схемой вычислений в алгоритме. Рассмотрение особенностей схемы обработки снимков двух стереопар. Определение погрешностей локализации при вычислении траектории алгоритмами. Исследование специфики визуальной одометрии.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 30.08.2021 |
| Размер файла | 3,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Институт автоматики и процессов управления ДВО РАН
Модифицированный ICP алгоритм для несопоставленных 3D облаков
В.А. Бобков, д-р техн. наук,
А.П. Кудряшов, канд. техн. наук,
И.К. Проценко
Владивосток
Предложен модифицированный ICP алгоритм для независимо генерируемых 3D облаков, основанный на неявном сопоставлении точек. В экспериментах с виртуальными сценами получены сравнительные оценки эффективности с аналогами. Вычислительные эксперименты проведены с использованием имитационного моделирующего комплекса для автономных подводных роботов.
Ключевые слова: 3D облака, ICP алгоритм, камера, сопоставление особенностей, матрица локального геометрического преобразования, триангуляционная поверхность.
Введение
Одной из важных задач компьютерного зрения в решении проблемы восстановления структуры и движения по изображениям является задача геометрического выравнивания 3D моделей. Она заключается в оптимальном совмещении двух 3D поверхностей, заданных каждая в своей системе координат. Применяемый сегодня для ее решения так называемый ICP (Iterative Closest Point) алгоритм был впервые предложен Chen and Medioni[1] and Besl and McKay[2]. Алгоритм ICP должен обеспечивать вычисление соответствующего геометрического преобразования в матричной форме, которое служит ключевым элементом решения задачи визуальной навигации автономного робота.
Основным требованием традиционной схемы решения алгоритма является предварительное явное сопоставление точек двух 3D облаков, представляющих сравниваемые поверхности. Такое сопоставление, как правило, делается сначала на уровне идентификации 2D особенностей на снимках с помощью известных программ - детекторов (например, SURF) и трекеров (например, KLT). По множеству сопоставленных особенностей строятся уже непосредственно сопоставленные 3 D облака. Однако в некоторых практических задачах необходимо совмещение поверхностей без использования явного сопоставления исходных измерений. Прежде всего это относится к использованию получающих сегодня распространение лазерных дальномеров (или профильных лазеров, генерирующих линии сканирования на видимых поверхностях), которые производят независимые измерения в отдельные моменты времени. Преимущество лазерных дальномеров в том, что они дают плотные измерения, не зависящие от освещения, которое меняется с изменением позиции камеры.
Существуют и другие практические приложения, в которых задача совмещения поверхностей должна решаться без использования сопоставления измерений. Поэтому разработка алгоритма ICP без сопоставления исходных данных является актуальной.
В такой постановке рассматривается модификация алгоритма ICP, предлагаемая в настоящей статье. С обзором и некоторыми известными результатами в части развития ICP алгоритмов можно познакомиться в [3 - 7].
Традиционная схема вычислений в алгоритме ICP
В классической схеме исходными данными для работы ICP алгоритма служат два сопоставленных множества 3D точек (3D облака), непосредственно измеренных или полученных в результате обработки изображений. Они рассматриваются как геометрические модели видимых поверхностей. Под двумя сопоставленными точками понимаются образы одной и той же реальной точки объекта сцены, видимой и координированной (измеренной) в двух разных системах координат. Как было отмечено выше, при обработке снимков, относящихся к разным моментам времени наблюдения сцены, такое сопоставление обеспечивается с помощью методов/алгоритмов, генерирующих и идентифицирующих точечные особенности на изображениях (рис. 1).
Рис. 1. Схема обработки снимков двух стереопар.
По выделенному единому множеству 2D особенностей строятся пространственные точки с помощью алгоритма триангуляции лучей, который использует калибровочные данные камер.
Задача состоит в поиске такого геометрического преобразования H, которое бы минимизировало расхождение двух 3 D облаков (моделей), совмещенных в едином координатном пространстве. Типичная вычислительная схема реализуется методом минимизации квадратичных расхождений между сопоставленными точками двух 3 D облаков. Вычислительный процесс носит итерационный характер, - на каждом шаге итераций с помощью вариации параметров матрицы задается текущая матрица, которая используется для преобразования координат точек. В качестве параметров оптимизации используются три координаты вектора переноса и четыре координаты кватерниона вращения в матрице H. Ограничение задается условием - норма кватерниона равна единице.
Целевая функция
где к - номер точки в облаке; О- множество точек в первом облаке; - сопоставленное множество точек во втором облаке. Данная вычислительная схема может быть реализована с применением оптимизационной процедуры библиотеки MATLAB.
Алгоритм ICP без сопоставления 3D облаков
Недостаток рассмотренной выше традиционной вычислительной схемы - большие вычислительные затраты на сопоставление (работа детектора / трекера) и выделение единого множества особенностей. Другой существенный недостаток - невозможность использования измерений, получаемых независимо в каждой позиции камеры (без сопоставления). Также следует учитывать неизбежность ошибок сопоставления особенностей, которые в конечном счете снижают точность локализации камеры/робота.
В предлагаемом методе исключается этап непосредственного сопоставления особенностей между изображениями двух позиций и используются два независимых 3D облака (тем самым мы устраняем указанные основные недостатки). Метод вычисления матрицы преобразования в целом остается тот же, что и в классической схеме - итерационный поиск матрицы геометрического преобразования с целевой функцией, минимизирующей расхождение сравниваемых множеств точек. Но в этом случае применяется схема косвенного (неявного) сопоставления. Для каждой точки Р2 второго облака, помещенной с помощью матрицы H текущей итерации в систему координат (СК) первого облака - (Р2)', в качестве сопоставленной точки рассматривается соответствующая ей точка M на триангуляционной поверхности S1, построенной по множеству точек первого облака (рис. 2).
Рис. 2. Неявное сопоставление точек двух 3D облаков, относящихся к позициям 1 и 2. Точка Р2 отображается преобразованием H в точку (Р2)'. Точка M, полученная пересечением луча R (проходящего через (Р2)') с триангуляционной поверхностью S1, ставится в соответствие точке Р2.
Точка M является точкой пересечения луча из центра проекций через точку (Р2)'. Такое геометрическое построение интуитивно понятно, - при правильном геометрическом преобразовании (из СК2 в СК1) точки ( Р2)' и M должны совпадать, если триангуляционная поверхность достаточно точно отображает видимую камерой поверхность.
Тогда целевая функция на очередной итерации i будет
где - множество точек во втором облаке; Иг - матрица преобразования на итерации i; M\ - точка пересечения луча с поверхностью S1.
Несмотря на внешнюю простоту метода, здесь возникает алгоритмическая трудность, связанная с неявным сопоставлением. Она состоит в том, что при произвольном преобразовании (генерируемом на очередном итерационном шаге) возможны ситуации, когда точка пересечения луча с триангуляционной поверхностью отсутствует. И при этом неясно, по какой из двух возможных причин это произошло. Первая причина - неправильное преобразование, при котором точка Р2 отображается таким образом, что луч через (Р2)' не пересекает S1. Вторая причина - возможны ситуации, когда точка P2 не видна из позиции 1 (т.е. не находится в зоне общей видимости). В этом случае пересечения соответствующего луча с поверхностью S1 при правильной матрице преобразования из СК2 в СК1 в принципе быть не должно. Стандартная обработка в этих ситуациях, как подтвердили эксперименты, может приводить к нахождению ошибочных локальных минимумов. одометрия стереопара алгоритм
Поэтому предлагается следующее решение - будем исключать ситуации с отсутствием перекрытия и, соответственно, обрабатывать только те точки второго облака, для которых заведомо известно, что они видимы из обеих позиций камеры. Другими словами, при «правильной» матрице пересечение для них должно находиться. А если его нет, то это однозначно «плохая» матрица. Возможны два способа это сделать. Оба предполагают предварительное вычисление грубого приближения матрицы - И0,.
Первый способ заключается в вычислении такой матрицы по трем сопоставленным точкам (т.е. применяем детектор для сопоставления особенностей). Это небольшие, допустимые вычислительные затраты.
Второй способ основывается на предположении, что перемещение камеры (соответственно вектор смещения в матрице преобразования) эквивалентно перемещению центра облака, т.е., пренебрегая вращением камеры, вычисляем матрицу И°2 из соотношения:
где центры Pц1ентр и Pц2ентр вычисляются как средние по облаку.
Теперь, имея матрицу грубого приближения (полученную одним из двух способов), строим для каждого облака в своей системе координат 3 D оболочку - параллелепипед по minmax значениям точек в облаке - соответственно, Vх и V2. Проецируем Vх в пространство второго облака
и берем пересечение . Во втором облаке ищутся точки, входящие в пересечение: перебор по всем точкам облака 2 и проверка каждой точки на принадлежность . Только эти точки включаются в целевую функцию и для них вычисляются пересечения луча с поверхностью S1.
Таким образом, мы исключаем указанные выше ситуации неоднозначности. Другой важный аспект - одновременное использование данных работы детектора / трекера (сопоставленные особенности) и независимых измерений (множество не сопоставленных точек). Чтобы реализовать эту возможность, предлагается вычислительная схема, объединяющая работу предложенного и классического алгоритмов. Тогда целевая функция будет состоять из двух слагаемых, относящихся к обработке точек первого и второго типа.
где - множество точек во второй позиции, не сопоставленных с точками первой позиции; - сопоставленные облака; - точки пересечения луча с поверхностью S1; Иг - матрица преобразования на итерации i.
Применение RANSAC метода.
Альтернативой применению рассмотренного выше метода оптимизации при вычислении матрицы H является реализация RANSAC-подхода. В этом случае рассматривается множество матриц - гипотез H, каждая из них вычисляется по трем точкам , которым сопоставлены точки Для каждой гипотезы оценивается суммарное расхождение:
по всем точкам второго облака (с ограничениями, рассмотренными выше). В качестве решения H выбирается вариант с минимальным расхождением.
Результаты вычислительных экспериментов
Эффективность предложенной модификации алгоритма ICP оценивалась на виртуальных сценах в среде моделирующего комплекса [8], одна из которых показана на рис. 3. Оценивалась локальная и абсолютная погрешность локализации камеры/робота при расчете траектории.
Локальная погрешность вычисляется как разность между истинным перемещением камеры за один шаг и вычисленным перемещением (в метрических единицах). Абсолютная погрешность - разность между истинным положением камеры в мировой системе координат и вычисленным положением. Заметим, что для визуальной одометрии характерно увеличение абсолютной погрешности со временем из-за накопления ошибок локальных вычислений.
Рис. 3. Сцена: разрешение снимков 600x400, fps = 25; база стерео = 40 см; высота траектории над дном в среднем 2м; шаг между расчетными позициями на траектории - 8 кадров.
Предложенный алгоритм (без сопоставления точек двух 3D облаков) сравнивался с:
А) алгоритмом ICP с сопоставлением точек двух 3D облаков (авторская реализация классической схемы);
Б) аналогом - алгоритмом ICP из библиотеки Open3D (без сопоставления точек двух 3D облаков). Этот алгоритм был выбран для сравнения, поскольку он показал лучший результат в сравнении с аналогом из библиотеки PCL.
На рис. 4 показаны графики локальной и абсолютной погрешности, сравниваемых алгоритмов в варианте А).
Графики построены по измерениям для 36 шагов движения камеры/робота по траектории (длина последовательности ~ 300 кадров).
Как видно из графиков, точность вычисляемой локализации для алгоритма без сопоставления точек незначительно уступает точности, получаемой при работе алгоритма с сопоставлением точек. Локальная погрешность в среднем составляет 1.5 мм против 0.3 мм, а абсолютная погрешность на последнем шаге - 3.1 см против 2.6 см. Это приемлемый результат для решения поставленной задачи по использованию не сопоставленных 3D облаков.
В варианте Б) были выполнены два вычислительных эксперимента на указанной сцене с алгоритмом из библиотеки Open3D. В первом эксперименте обрабатывалась последовательность длиной 100 кадров. Локальная погрешность изменялась от 3 мм до 20 мм, абсолютная погрешность на последнем шаге (накопленная ошибка) = 8.9 см. Во втором эксперименте обрабатывалась вся круговая траектория (длина последовательности = 490 кадров). Локальная погрешность, как и следовало ожидать, была такой же, как и в первом эксперименте, а абсолютная погрешность (накопленная ошибка к концу траектории) увеличилась до 78 см.
Рис. 4. Погрешности локализации при вычислении траектории алгоритмами с сопоставлением 3D облаков и без сопоставления: а) локальная погрешность, алгоритм без сопоставления; б) локальная погрешность, алгоритм с сопоставлением 3D облаков; в) абсолютная погрешность, алгоритм без сопоставления 3D облаков; г) абсолютная погрешность, с сопоставлением 3D облаков.
Эксперимент с одновременной обработкой сопоставленных и не сопоставленных 3D точек показал, что предложенная объединяющая вычислительная схема дает незначительное улучшение точности в сравнении с алгоритмом без сопоставления, уступая при этом алгоритму с сопоставлением 3D облаков.
Заключение
Вычислительные эксперименты подтвердили эффективность применения предложенного метода неявного сопоставления в алгоритме ICP с использованием не сопоставленных 3D облаков. Полученные оценки точности локализации показали преимущество предложенного алгоритма перед сравниваемыми аналогами и сопоставимость эффективности с традиционной вычислительной схемой, использующей предварительное сопоставление двух 3D облаков. Разработанный алгоритм может применяться в приложениях, где в качестве исходных данных используются независимые измерения двух видов объекта без предварительного сопоставления наблюдаемых точек.
Литература
1. Chen Y. & Medioni G. Object modeling by registration of multiple range images // IEEE International Conferenceon Robotics and Automation. - 1991. - 3, 2724-9.
2. Besl P.J. & McKay N.D. A method for registration of 3-D shapes // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1992. - 14(2), 239-56.
3. Rusinkiewicz S. & Levoy M., Efficient variants of the ICP algorithm // Proceedings of the 3rd International Conference on 3-D Digital Imaging and Modeling. Quebec, Canada. - 2001, 145-52.
4. Gelfand N., Ikemoto L., Rusinkiewicz S. and Levoy M. Geometrically stable sampling for the ICP algorithm // Fourth International Conference on 3D Digital Imaging and Modeling (3DIM). - 2003. - Р. 260-267.
5. Leslie I., Gelfand N. and Levoy M. A Hierarchical Method for Aligning Warped Meshes // In 3DIM. - 2003. - P. 43.
6. Marani R., Ren'o V., Nitti M., D'Orazio T. & Stella E. A Modified Iterative Closest Point Algorithm for 3D Point Cloud Registration // Computer-Aided Civil and Infrastructure Engineering. - 2016. - Vol. 31, Iss. 7. - P. 515-534.
7. Бобков В.А., Мельман С.В., Морозов М.А., Тарасов Г.В. Моделирующий комплекс для подводного робота на распределенной архитектуре с использованием кластера // Информатика и системы управления. - 2017 - №4 (54). - С. 32-42.
Размещено на Allbest.ru
Подобные документы
Определение понятия "алгоритм". Изображение схемы алгоритма. Разработка схемы действий и этапы решения задач. Рассмотрение функции разрабатываемого приложения. Распределение исходного кода по файлам проекта. Контрольный пример и описание результатов.
реферат [695,9 K], добавлен 28.09.2014Технологии распределённой обработки данных, в которой компьютерные ресурсы и мощности предоставляются пользователю как Интернет-сервис. Виды облаков, достоинства и недостатки "облачных" вычислений. Компании, которые предоставляют "облачные" сервисы.
контрольная работа [28,1 K], добавлен 10.03.2012Разработка компьютерных игр как зрелищная и наиболее сложная отрасль программирования. Рассмотрение основных особенностей конструирования классов CGame и Players, а также алгоритмов вычисления траектории полета снаряда. Анализ алгоритма PassivePlayer.
курсовая работа [5,1 M], добавлен 22.02.2013Команды, используемые при вычислении обыкновенных и частных производных аналитического выражения по одной или нескольким переменным в системе вычислений Maple, при интегрировании аналитических выражений и при вычислении пределов, сумм, рядов функций.
лабораторная работа [62,1 K], добавлен 15.07.2009Параллельная машина как процессоров, памяти и некоторые методы коммуникации между ними, сферы применения. Рассмотрение особенностей организации параллельности вычислений. Анализ типовых схем коммуникации в многопроцессорных вычислительных системах.
курсовая работа [669,3 K], добавлен 07.09.2015Основные модели вычислений. Оценки эффективности параллельных алгоритмов, их коммуникационная трудоемкость. Последовательный алгоритм, каскадная схема и способы ее улучшения. Модифицированная каскадная схема. Передача данных, классификация операций.
презентация [1,3 M], добавлен 10.02.2014Запись результатов измерений в память микроконтроллера. Определение времени измерения и расчет погрешностей системы. Обоснование алгоритма сбора измерительной информации и метода ее обработки. Разработка временных диаграмм, отражающих работу системы.
курсовая работа [1,6 M], добавлен 18.11.2011Разработка программной базы для исследований в области распознавания речи и поиска ключевых слов в ней. Расчет mel-фильтров. Скрытые марковские модели. Применение в алгоритме сверточного декодирования Витерби. Методы визуализации и обработки аудиоданных.
курсовая работа [1,1 M], добавлен 01.06.2015Инициализация переменных архитектурным элементам микропроцессора КР580ВМ80А и портам ввода-вывода в общем алгоритме. Составление карты памяти микропроцессорной системы для реализации программы. Анализ соответствия временных и точностных характеристик.
курсовая работа [217,6 K], добавлен 27.11.2012Микропроцессорные системы обработки данных. Специальные алгоритмы-планировщики для распределения операторов параллельных алгоритмов по процессорам вычислительной сети. Алгоритм построения и уплотнения нитей. Интерфейс программы, результаты работы.
курсовая работа [1,8 M], добавлен 22.02.2011
