Описание алгоритма Kinect Fusion
На основе анализа кадров глубины, получаемых с сенсора Kinect (или аналогов) формируется детализированное 3D-представление обозреваемой сцены. Данные обрабатываются в реальном режиме. Высокая скорость и детализация достигается за счет использования для всех расчетов GPU, а также новаторским подходом к применению уже известных алгоритмов. В открытой реализации данного проекта в рамках библиотеке PCL поддержимаются лишь два последних поколения видео-карт (с расширенным набором инструкций и большим числом ядер) – архитектуры Fermi и Kepler (по спецификации NVidia – архитектуры 20 и 30 соответственно).
В память видео-карты помещается куб состоящий из множества вокселей – для эффективной обработки – данные куба хранятся в одном последовательном блоке памяти. В kinfu каждая его сторона – 512 вокселей (о них можно думать как об аналоге пикселя в 3D-пространстве). Нашу будущую сцену мы будем строить внутри этого куба. Перед началом работы указываем размеры сцены, которую будем “вписывать” в этот куб – по умолчанию это 3 метра. В каждой ячейке-вокселя куба будем хранить данные о текущем представлении сцены, и, по мере работы алгортма, постоянно обновлять эти данные. Основной цикл работы алгоритма включает в себя следующие шаги:
- преобразование показаний камеры глубины в трехмерное облако точек и нормалей к ним
- вычисление матрицы преобразования между двумя облаками точек, полученных с камеры глубины на текущей и предыдущей итерации, на основе этого преобразования определяется смещение камеры в глобальном пространстве, используя алгоритм ICP – Iterative Closet Point.
- обновление сцены – на основе полученных данных мы формируем новые значения функции TSDF, которая и содержит текущее представление о сцене
- используем значения функции TSDF для рендеринга (визуализации) сцены а также получаем сглаженные значения облака точек и нормалей к ним.
Судя по отзывам на www.pcl-developers.org – при известном желании возможно использовать топовые карты предыдущих поколений (архитектуры 13). В более старых моделях видео-карт отсутствует поддержка ряда операций над числами с плавающей точкой, что делает невозможным компиляцию. Эмуляция данных операций – теоретически возможна – но даже при условии успешной имплементации таковых, скорость обработки будет не удовлетворительной.
Очевидное ограничение на размер сцены присутствует в модуле KinFu. Расширение алгоритма Kinect Fusion – Kintinuous предлагает по мере приближения камеры к границам куба – выгружать часть сцены из памяти видео-карты во внутренее представление модели “всего мира”. Эта идея нашла свое отражение в модуле KinFu Large Scale.
А теперь все тоже самое, но по шагам:
Важный для понимания момент – осознать различие между координатным пространством глобальным (всей сцены) и текущим координатным пространством камеры (на основе карты глубины с текущего фрейма глубины). Глобальное пространство строится начиная с самого первого кадра глубины, на основе матрицы смещения 6DOF – 6 степеней свободы и матрицы калибровки камеры.
I Этап – подготовительный
Вычисление матрицы камеры. Также ее называют афинная калибровочная матрица или, говоря математически, матрица перспективной проекции. С ее помощью каждый пиксель из карты глубины может быть переведен в координатное пространство камеры (не путать с глобальным). В KinFu используется упрощенная модель – для преобразования координат используется только фокусное расстояние камеры, на основе которого вычисляются и основные (principal) точки.
II Этап – Бесконечный цикл работы ядра алгоритма Kinect Fusion, состоящий из четырех основных шагов
1) преобразование показаний камеры глубины
Каждый кадр глубины перед обработкой проходит фильтрацию (билатеральным фильтром) – для сглаживания. Преобразуем карту глубины в набор из 3D-вершин – (X,Y,Z) – облако точек (в координатном пространстве камеры – НЕ глобальном). Банально каждая точка из матрицы глубины перемножается с матрицей обратной для матрицы камеры на отдельном ядре GPU. Вычисляем нормали к ним (направление перпендикуляров к плоскости) используя данные о соседних с текущей вершинах.
Вершины и нормали вычисляются не только для полученных данных – полученную карту глубины несколько раз сжимают по ширине высоте инициализируя ее усредненными значениями, и для каждой полученной карты вычисляют свой набор вершин и нормалей.
Если этот шаг первый – инициируем глобальное координатное пространство начальными данными. Все следующие замеры карты глубины будем конвертировать к этим, стартовым показателям. Определяем положение камеры относительно сцены.
2) Определение смещения камеры в пространстве относительно предыдущего фрейма.
Для этого используем ICP – Iterative Closet Point алгоритм, обрабатывая два облака точек – с текущего и предыдущего кадров глубины, а также знание о предыдущей позиции камеры в глобальном пространстве. Здесь надо принять во внимание используемое упрощение – расхождение между двумя фреймами глубины будут не значительны из-за особенностей кинекта. Это позволяет использовать в ICP не облака точек, а их проективную проекцию на матрицу глубины (point-to-plane вместо point-to-point) – выгода очевидна – меньше данных для обработки – быстрее.
Алгоритм прост и распаралеливается на GPU:
- проецируем каждую вершину с предыдущего кадра глубины сначала в координатное пространство камеры, а затем на двумерную карту глубины – как будто бы, мы получили ее как очередной фрейм глубины
- проверяем – совпадает ли эта точка с пикселем кадра глубины на текущей итерации (т.е. не вылезли ли мы за край матрицы глубины?)
- если совпадает – вычисляем нормаль и координаты в координатном пространстве камеры для заданной точки из матрицы глубины, используя данные глубины, полученные на текущем шаге и матрицу, характеризующую позицию камеры в глобальном пространстве на текущем шаге (эта матрица постоянно обновляется при нахождении совпадений, а в начале работы используется целиком матрица с предыдущей позиции)
- если расхождения не превышают заданных пороговых значений – обновляем наше представление о позиции камеры в глобальном пространстве, если превышают – отбрасываем
В качестве результата на этом шаге мы получаем матрицу преобразования, характеризующую положение камеры в глобальном пространстве. Эта матрица аккумулирует в себе данные полученные не только с текущей карты глубины, но и ее масштабированных вариаций, полученных на первом шаге – т.е. ICP пробегается по всем вариантам матрицы глубины и аккумулирует данные в единой матрице преобразования. В реализации KinFu – это отдельно матрицы сдвига и вектор поворота.
3) интеграция полученных данных в общую сцену
Зная положение камеры в глобальном пространстве мы можем перевести показания камеры с текущего кадра глубины в нашу общую “картину мира” представляемую в Kinect Fusion в виде функции особого вида – TSDF.
Перед этим этапом производится проверка – изменила ли камера свое положение по сравнению с предыдущими замерами (небольшие сдвиги не принимаются во внимание – уровень сдвига регулируется задаваемым граничным значением) – на основе метода Родригеса и матриц преобразования на текущем и предыдущем шаге. Если камера переместилась в пространстве значительно – запускается следующий алгоритм:
- разбиваем наш воксельный куб на вертикальные слои толщиной в один воксель и анализируем каждый слой от дальнего ломтика к ближнему. Обработка каждого слоя (не вокселя) распаралеливается на GPU.
- каждый воксель конвертируем в вершину в глобальном пространстве – для этого используем матрицу смещения камеры, вычисленную с помощью ICP на предыдущем шаге – получаем вершину в координатном пространстве матрицы
- проецируем вершину в координатном пространстве матрицы на карту глубины матрицы в некоторый пиксель глубины
- если этот пиксель глубины попадает в нашу текущую область зрения (т.е. входит в множество значений карты глубины на текущей операции) вычисляем новое значения функции для этого вокселя и его вес.
В качестве результата имеем обновленное представление глобальной сцены в виде TSDF функции. Каждый воксель содержит значение этой функции и его вес – вероятность. Значение функции в каждом вокселе – усредненное (на самом деле – скользящее среднее) значение дельты расстояний до этой точки за все время работы. Дельта расстояний вычисляется между фактическими данными карты глубины и полученными математически, на основе координат вершины=вокселя в трехмерном пространстве и центра камеры, с помощью данных калибровочной матрицы. Знак значения функции (+ или -) характеризует расположение вокселя относительно поверхности – т.е. находится ли данный воксель перед обозреваемой поверхностью или за ней. Вес в каждом вокселе отображает вероятность этого значения функции – т.е. если из 100 полученных кадров глубины мы только один раз отметили в заданном вокселе некоторую поверхность – скорее всего это результат ошибки или какой-то динамики в кадре, и вероятность наличия там реальной поверхности мала.
4) восстановление общей сцены
Для рендеринга используется метод бросания лучей “ray casting“. Сцена строится на основе замеров пересечения лучей с визуализируемой поверхностью. Каждый луч – направление взгляда с определенной точки на воксельный куб. Каждое ядро GPU занимается поиском вокселя, сквозь который проходит луч, в котором, при этом, значения TSDF функции – меняет знак – т.е. там находится некоторая поверхность. Освещение сцены (тени, отражения) вычисляются на основе следующих, дополнительных проходов луча. Для теней – инициируется еще один луч направленный от точки поверхности к источнику свету – в случае пересечения луча с поверхностью – воксель, находящийся в точке нового пересечения затеняется. Для отражений направления луча изменяется на основе вычисленного значения нормали к найденной точке поверхности.
Данные полученные на этапе raycasting’a могут быть использованы для более точного позиционирования камеры в глобальном пространстве. Вычисляемые значения нормалей, а так же обратная проекция облака точек на карту глубины полученные на этапе бросания лучей на модель (а чем не аналог работы сенсора кинекта?) получаются более сглажеными и, за счет интеграции с общим представлением модели – более полными.
Размер вокселя (в проекции на реальное пространство), размер куба в вокселях, граничное значения для нормализации TSDF функции – все это те параметры, которые влияет на работу фильтров и, как следствие, на детализированность сцены.
Kinect Fusion и бесконечная сцена: Kintinuous, KinFu Large Scale и их некоторые различия
Из описания алгоритма очевидно что размер сцены ограничен размерами воксельного куба, а детализация – заданными размерами проецируемой области (KinFu – 3 метра). Для преодаления ограничений заложенных в алгоритм Kinect Fusion – в настоящее время существует два независимых расширения алгоритма: Kintinuous и KinFu Large Scale
Во время инициализации работы алгоритма – начальная позиция камеры рассчитывается как центр этого куба. Оба расширения предлагают задать некоторое граничное значение (расстояние от центра куба до текущего положения камеры в этом кубе), при достижении которого производится сдвиг сцены, хранимой в кубе. В KinFu Large Scale можно задать процент перекрытия двух соседних кубов – по умолчанию 2.5% от размера куба (в Kintinuous – 2 вокселя). Память видеокарты, в которой хранится куб – трехмерный массив из вокселей – трактуется как циклический буфер, таким образом модификация оригинального алгоритма KinFu сводится к дополнительным изменениям индексации этого массива во время обновления значений TSDF функции, описывающей сцену и этапа “бросания лучей”, для вычисления сдвига и поворота на основе полученных данных.
UPDATE от 22.08.2012 не верно был описан принцип использования FOVIS в Kintinuous
Дополнительно, в Kintinuous для работы со сценой содержащей обширные гладкие участки (стены/шкафы) с которыми алгоритм ICP, используемый для позиционирования камеры в пространстве, справлялся не лучшим образом – наблюдается частые потери в пространстве и, как следствие, “наслоение” карт глубины и смазанная сцена. В Kintinuous же карты глубины подаются в одну из реализаций методов визуальной одометрии – FOVIS, предоставляющую более стабильное определение местоположения камеры и минимизирующее число Reset’ов – ситуаций когда камера заплутается в пространстве. Причем используется какая-то реализация FOVIS на CPU.
Данные о сцене, которые выходят из области анализа (не попадают в сдвинутый куб) выгружаются в промежуточное представление. В Kintinuous это представление – pose-graph. Каждое новое положение (узел графа) содержит соответствующую поверхность, полученную для этого участка сцены, а также данные о положении текущего куба в рамках глобальной системы координат,и матрица поворота и вектор сдвига. В Kinfu Large Scale для этого используется особая структура, созданная на основе облака точек.
После этапа бросания лучей, облако точек, представляющее собой изученную поверхность, подвергается триангуляции (greedy mesh triangulation). В KinFu Large Scale для триангуляции используется алгоритм движущихся кубиков (marching cubes). При запросе накопленные данные интегрируются в общую модель глобальной сцены.
Существующие ограничения KinFu Large Scale: не терпит резких перемещений камеры, не всегда корректно производится вычисление нового положения камеры во время сдвига куба, работает не стабильно. Зато уже сейчас есть масса информации для экспериментов.
Создатели Kintinuous обещают в скором времени выложить свой код в открытй доступ, в состав PCL.
Используемые материалы
В основе статьи лежит анализ брошюр от Microsoft, а также материалы проекта PCL, в особенности, исходный код модулей KinFu и KinFu Large Scene из trunk, предлагающий свободную реализацию Kinect Fusion, а также вспомогательные работы по используемым алгоритмам.
KinectFusion: Real-Time Dense Surface Mapping and Tracking
KinectFusion: Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera
форумы библиотеки PCL – кладезь знаний о внутренностях реализации KinFu и не только:
www.pcl-developers.org
www.pcl-users.org
в качестве возможных вариаций для применения:
робот, использующий данный метод для локализации себя на неизвестной местности и составлении карты этой местности: http://code.google.com/p/ic2020/wiki/Installation
свободно распространяемая версия метода FOVIS: http://code.google.com/p/fovis/
http://developkinect.com/ – интересный сайт с обзором возможных применений kinect и смежных технологий
Рабочая (но закрытая) реализация Kinect Fusion на OpenCL. Отсканированные элементы сцены могут быть распечатаны на 3d-принтере – http://reconstructme.net/
Описание алгоритма Kinect Fusion простым языком (насколько это вообще возможно) на английском:
http://razorvision.tumblr.com/post/15039827747/how-kinect-and-kinect-fusion-kinfu-work
Любые поправки и уточнения горячо приветствуются! 🙂