Алгоритмы регистрации облаков точек (Point cloud registration algorithms)

Автор: | 09.12.2020

Введение
Алгоритм RANSAC для регистрации облаков точек
Алгоритм итерации ближайшей точки (ICP)
Выделение плоскостей в облаке точек
Регистрация облаков точек через преобразование  в 2D-изображения
Нейронная сеть MaskNet для маскировки  точек-выбросов
3D-регистрация облаков точек по алгоритму TEASER++
Классификация алгоритмов регистрации облаков точек
Полезные ссылки

Введение

Регистрация облаков точек – процесс совмещения нескольких облаков точек одного объекта в единую систему координат. Цель регистрации — найти преобразование, которое оптимально позиционирует два облака. Пример алгоритма регистрации:

  1. Найти соответствующие особые точки облаков на основе данных из файлов 1.obj и 2.obj (или файлов других форматов).
  2. Оценить меру соответствия точек и по наиболее надежным точкам определить параметры преобразования.
  3. Преобразовать координаты всех точек 2-го облака в глобальную СК на основе системы линейных уравнений с полученными параметрами преобразования (см. п.2).
  4. Создать новый OBJ файл, в который добавлены точки 2-го облака.

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

«Регистрация — это то, что позволяет нам интегрировать 3D-данные из разных источников в общую систему координат». Задача регистрации облаков актуальна в области построения трехмерного окружающего пространства (панорамное фото или фотограмметрия) – например, для определения местоположения роботов и планирования их оптимального пути. При помощи 3D-сканирования или других технологий строится 3D-модель части сцены (локальная реконструкция), полученной из определенной точки. Затем полная модель создается посредством объединения локальных реконструкций. Таким образом, получается трехмерная модель всего окружающего пространства робота, в котором уже рассчитывается оптимальный путь.

Алгоритм RANSAC для регистрации облаков точек

Перевод и обработка статьи   Random sample consensus (RANSAC)

RANSAC  (Random Sample Consensus — консенсус случайной выборки ) — это метод, который случайным образом выбирает минимальный набор точек (в 2D — 2 точки, в 3D — 3точки) в одном облаке, находит соответствующие точки в другом облаке, по ним определяет параметры преобразования.  Если исходное и преобразованное изображение  совпали в достаточной степени, то результат принимается, в противном случае определяется новый набор соответствий, и процесс повторяется.

RANSAC — итерационный метод для определения параметров математической модели с помощью множества наблюдаемых данных, которые содержат точки — выбросы, не удовлетворяющие модели (outliers). Поэтому RANSAC также может быть назван методом для определения выбросов. Это недетерминированный алгоритм в том смысле, что он возвращает приемлемый ответ только с определенной вероятностью, и с увеличением этой вероятности при росте числа затрачиваемых итераций. Базовое предположение метода заключается в том, что данные состоят из модельных примеров и выбросов, которые не описываются математической моделью. При этом распределение модельных примеров может быть некоторым множеством параметров.

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

Первый шаг каждой итерации k <N (N — максимальное количество итераций) — это случайный выбор трех точек из исходного облака S.

На следующем шаге необходимо найти три соответствующие точки в целевом облаке. Это делается путем вычисления дескрипторов точек в  исходном облаке и поиск наиболее похожих на них в целевом облаке. Наилучшим соотношением уникальности дескриптора к требуемому времени вычислений является FPFH (Fast Point Feature Histograms).

Метод, основанный на PFH дескрипторах, используется для регистрации соответствий между моделями. Он основан на вычислении особенностей в окрестности специфических точек. Под особенностями понимаются, например, нормали и кривизна поверхностей. На основе полученных данных строятся гистограммы, позволяющие выбрать среди всех точек те, которые похожи друг на друга. Помимо обычного алгоритма PFH, существует быстрый алгоритм: Fast PFH (FPFH). Методы PFH и FPFH реализованы в библиотеке PCL.

Третий шаг — определение матрицы преобразования с заданными тремя парами точек.

Минимальное количество соответствующих точек, которое необходимо для 3D преобразования из одной системы координат в другую равно трем. По ним можно составить 9 уравнений. Для нахождения 6 независимых параметров Евклидового преобразования (3 угла и 3 перемещения) достаточно 6 уравнений. Три уравнения составляются на основе координат 1-й точки (фиксированная  3D точка), 2 уравнения на основе координат 2-й точки (текущая точка линии) и одно уравнение на основе  координат 3-й точки (текущая точки плоскости). См. Выделение параметров формы и положения.

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

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

Четвертый шаг — преобразование исходного облака по оценочной матрице и проверка, сколько целевых точек имеют точку из исходного облака в целевом облаке.  Чтобы найти ближайшую точку в метрическом пространстве, в библиотеке PCL (Point Cloud Library) используется структура октодерева.

Алгоритм останавливается на итерации, в которой отношение inliers больше определенного порога.

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

Избранные расширенные версии

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

  1. неравномерный выбор выборки на самом первом этапе каждой итерации;
  2. оптимизация проверки гипотез.

Ниже приводится краткое описание одного представителя первой группы и трех представителей второй

Lo-RANSAC

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

Polygon test

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

Td,d test

Перед преобразованием всего исходного облака предлагают выполнить проверку случайно выбранного подмножества d точек модельного облака (где d | S |). Соотношение оставшихся точек можно было проверить сразу после теста Td, d — вероятность отклонения верной гипотезы мала, но полученный выигрыш п времени может быть заметен.

Visibility test

Гипотеза, отвергающая использование знаний о видимых и скрытых областях наблюдаемой сцены. Если целевое облако захватывается датчиками RGBD, такими как устройство Microsoft Kinect, то напрямую указывается, какие части сцены пусты, где границы объекта и где скрытая область. Visibility test вводит другое соотношение подсчета очков: только точки в пустом пространстве между наблюдаемым объектом и камерой обрабатываются как выбросы, поскольку неизвестно, являются ли точки в скрытой области отклонениями или выбросами.

Алгоритм итерации ближайшей точки (ICP)

Целью алгоритма (Iterated closest point, ICP) является нахождение матрицы геометрических преобразований, которые выравнивают облака точек 𝑋 ={𝑥1, 𝑥2, … , 𝑥𝑛} и 𝑌 = {𝑦1, 𝑦2, … , 𝑦𝑛}, и для которых ошибки между преобразованным первым облаком точек и ближайшими точками второго облака являются минимальными.

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

Базовый алгоритм ICP состоит из следующих шагов:

  • Для каждой точки из облака 𝑋 определяется пара из облака 𝑌, используя критерий поиска ближайшего соседа согласно некоторой функции близости.
  • Осуществляется преобразование путем смещения и поворота одного из облаков точек, а также расчет и оценка среднеквадратичного расстояния между парами точек.
  • Шаги повторяются до тех пор, пока среднеквадратичное расстояние не станет меньше некоторого значения ɛ.

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

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

На рисунке три итерации алгоритма ICP:

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

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

Возможные варианты выбора точек:

  1. Выбрать все точки;
  2. Единая подвыборка;
  3. Случайная выборка;
  4. Выборка на основе признаков (использует некоторые наборы точек с очевидными функциями для регистрации, например, точки принадлежат плоскостям)

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

Весовой коэффициент (Weighting) может назначаться согласно Евклидовому расстоянию между парой соответствующих точек.

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

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

Откуда брать начальные параметры преобразования? При соединении 2 облаков точек приблизительно известно взаимное расположение камер,  из которых происходила съемка панорамных кадров.  Следовательно, по их расположению приблизительно можно определить взаимное положение облаков и, соответственно, начальные параметры преобразования для их совмещения.

Выделение плоскостей в облаке точек

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

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

Автоматически это выполняется в два этапа:

  1.  Выделение потенциальных плоскостей в облаке точек.
  2. Определение точки пересечения 3-х плоскостей.

Подход на основе параллельных плоскостей еще упрощает задачу. Простое выражение плоскости: a x + b y + c z + d = 0, где n(a,b,c,) — вектор нормали, а d — смещение. Все точки на параллельных плоскостях  имеют одинаковое n и разные d.

Как правило, необработанное облако точек сцены содержит от 5 до 8 миллионов точек, что может занять более 8 минут для задачи грубого выравнивания. Поскольку на этом этапе мы стремимся только к грубому извлечению, исходный набор точек субдискретизируется примерно до 1–2 миллионов точек, чтобы обеспечить быстрое и точное решение. Чтобы извлечь выступающие плоскости из набора точек с пониженной дискретизацией, необходимо выбрать точки, принадлежащие потенциальным плоскостям.

Регистрация облаков точек через преобразование  в 2D-изображения

Для улучшения базового ICP предлагается использовать особые точки, полученные на основе так называемых BA изображений  (Bearing Angle image, BA).

Алгоритм регистрации облаков точек на основе BA изображений:

  • На вход подаются 2 облака 3D точек
  • Каждая 3D точка облака преобразуется в 2D точку, которая описывается в файле двумерного изображения с оттенками серого, в нем пиксель определяется одним байтом  (градации серого цвета от о до 255). Уровень серого пикселя BA изображения  определяется как угол между лазерным лучом и вектором от точки до следующей точки.

где: 𝑝𝑖𝑗 – значение 𝑗 точки из 𝑖 отсканированного слоя;
𝑝(𝑖−1,𝑗−1) – значение (𝑗 − 1) точки из (𝑖 − 1) отсканированного слоя;
𝑑𝜑 – соответствующий угловой шаг.

  • Производится поиск соответствующих пикселей для этих двух BA изображений, например, с помощью метода SURF.

  • Cоответствующие пиксели используются для определения соответствующих пар 3D точек двух облаков.

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

Нейронная сеть MaskNet для маскировки  точек-выбросов

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

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

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

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

Код доступен по адресу https://github.com/vinits5/masknet, к сожалению, у меня не запустился.

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

Конвейер регистрации: облако точек шаблона X  и облако точек источника Y,  обрабатываются предварительно обученной MaskNet. Маска C,
полученная из сети, применяется к шаблону X для получения частичного облака точек
X1 = C X , которое обрабатывается вместе с Y алгоритмом регистрации. В результате создается матрица преобразований T.

⊗ — оператор произведения точечных пространств.

Удаление выбросов, повышает точность регистрации облаков точек популярных подходов на основе глубокого обучения, таких как PointNetLK, и Deep Closest Point (DCP).

MaskNet  можно также использовать для обнаружения шума и удаления выбросов из заданного облака точек. Для объяснения этого переформулируем задачу:

Вместо того, чтобы удалять точки из X, маска C может применяться как маска для удаления выбросов, присутствующих в наборе Y. Полученное облако точек Y1= CY. Другими словами, мы меняем местами в алгоритме  X и Y.

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

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

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

В верхнем ряду показаны связи между облаками которые не подвергались обработке MaskNet. В рядах посредине показаны связи между облаками с обработкой X1 = C X и  Y1= CY.  В нижнем ряду показаны связи между частями облаков, которые могут быть получены в результате двойной MaskNet обработки.

Последовательность двойной MaskNet обработки облаков точек:

Тот же результат можно получить на основе следующей последовательности MaskNet обработки облаков точек:

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

3D-регистрация облаков точек по алгоритму TEASER++

Перевод аннотации к статье «TEASER: Fast and Certifiable Point Cloud Registration«:

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

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

Для достижения этой цели мы сначала переформулируем проблему регистрации, используя оценку усеченных наименьших квадратов (Truncated Least Squares, TLS), которая делает оценку нечувствительной к большой части ложных соответствий. Затем мы предоставляем общую теоретико-графическую основу для разделения масштабирования, поворота и  перемещения, что позволяет каскадное решение трех преобразований. Несмотря на то, что каждая подзадача (масштаб, поворот и перемещение)  невыпуклая и комбинаторная по своей природе, мы показываем, что:

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

Назовем получившийся алгоритм TEASER (Truncated least squares Estimation And SEmidefinite Relaxation) — усеченная оценка по методу наименьших квадратов и полуопределенная релаксация. Решив, что решение больших проблем SDP обычно происходит медленно, мы развиваем быстрый и сертифицируемый алгоритм под названием TEASER ++, который устраняет необходимость решать SDP и выполняется за миллисекунды.

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

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

Более того, мы тестируем их работоспособность на стандартных тестах, наборах данных обнаружения объектов и наборе данных сопоставления сканирования 3DMatch и показываем, что оба алгоритма доминируют в современных технологиях (например, RANSAC, Branch-&-bound, эвристики) и устойчивы к более чем 99% выбросов когда масштаб известен.  TEASER ++ может работать за миллисекунды и
в настоящее время это самый быстрый и надежный алгоритм регистрации. TEASER ++ настолько надежен, что может решать проблемы без соответствий (например, выдвигая гипотезу «все для всех» соответствий), где он значительно превосходит ICP и точнее, чем Go-ICP при этом оказывается на порядки быстрее. Реализация TEASER ++ выпускается с открытым исходным кодом на C ++.

Мы проверяем TEASER с помощью стандартных тестов регистрации, показывающих, что алгоритм превосходит RANSAC и надежные методы локальной оптимизации и выгодно отличается от методов Branch-and-Bound, будучи алгоритмом с полиномиальным временем.

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

(а) Набор данных кролика (исходное облако синим цветом и целевое облако пурпурным) с 95% выбросов (показано красными линиями) и 5% вставок (показаны зелеными линиями). Существующие алгоритмы, такие как RANSAC (b), могут давать неверные оценки без предварительного уведомления даже после выполнения 10 000 итераций. Сертифицированный алгоритм TEASER в основном превосходит современные по надежности и точности, а быстрая реализация, названная TEASER ++ (c), вычисляет точные оценки в миллисекунды даже при экстремальных выбросах и находит небольшой набор соответствующих точек (показаны зелеными цветом). Беспрецедентная надежность TEASER ++ позволяет решение задач бесконтактной регистрации (d), где ICP (e) терпит неудачу без правильного начального задания параметров преобразования, в то время как TEASER ++ (f) завершается успешно, не требуя первоначального задания параметров преобразования. TEASER ++ тестируется в сложной локализации объекта (g-h) и сопоставление сканирования (i-j) набора данных RGB-D с использованием обеих традиционных функций определения соответствующих точек, (например, FPFH) и функций на основе Deep Learning   (например, 3DSmoothNet).

Классификация алгоритмов регистрации облаков точек

An application independent review of multimodal 3D registration methods

Deep learning based point cloud registration: an overview

Target-less registration of point clouds: A review

Полезные ссылки:

 

Автор: Николай Свирневский