Робот и холодильник

Есть комната, в которой стоят диван, стол со стульями и холодильник. И робот, которому очень надо к холодильнику. Комнату отсканировали с 6-ти локаций и получили шесть облаков точек: каждое в своей системе координат и со своим шумом.

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

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

Сбор данных

Считать данные с сенсора: лидар, RGB-D камера, МРТ/КТ или просто несколько фото с разных ракурсов

Предобработка

Убрать выбросы, проредить, вырезать нужное

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

Свести сканы с разных устройств в одну систему координат и склеить

Признаки

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

Облако точек

Работаем с точками как есть: XYZ и, может быть, цвет. Самое распространённое представление: в нём отдают данные лидары, с ним работают роботы и беспилотники

PointNet++

Нейросеть, которая работает прямо с облаком точек: для каждой точки смотрит на её соседей и по ним решает, что это за точка: стол, стул или пол

Меш из облака

Строим поверхность методом Пуассона: по облаку с нормалями получается гладкий меш

Воксели

Делим пространство ровной сеткой на маленькие кубики и отмечаем, в какие из них попали точки. Получается трёхмерная картинка: вместо пикселей кубики-воксели

3D U-Net

Нейросеть для вокселей: тот же U-Net, что для картинок, только свёртки трёхмерные. Её любят в медицине, например, чтобы распознать участки мозга на МРТ

Меш из вокселей

Строим поверхность алгоритмом Marching Cubes: смотрим на каждый кубик и его соседей и вписываем в него кусочек поверхности. Из кусочков складывается гладкий меш

Метрики

Понять, насколько промахнулись: IoU для детекции, Chamfer и Hausdorff для реконструкции

Откуда берутся 3D-данные

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

3D Computer Vision

Научитесь восстанавливать сцены по фото и видео и строить 3D-карты для роботов: SfM, SLAM, NeRF и Gaussian Splatting.

Лидар

лидары Velodyne, такие ставят на крышу беспилотника

облако точек вокруг беспилотника

Лидар это вращающийся лазер. Отправляет луч и по времени, за которое тот вернулся, считает расстояние до предмета. Крутится и снимает всё вокруг. Дорого, но точно.

RGB-D камера

RGBD-камера Intel RealSense

карта глубины: синее ближе к камере, красное дальше, чёрное сенсор не увидел

Камера глубины вроде Kinect или RealSense проецирует на сцену невидимую инфракрасную сетку и по тому, как сетка исказилась, восстанавливает расстояние до каждого пикселя. Получается обычный кадр плюс карта глубины. Дёшево, но работает вблизи и в помещении

МРТ и КТ

томограф

что из него получается: срезы и собранная из них модель головы

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

Фото с разных ракурсов

дом сняли с дрона по кругу: каждая рамка это одно фото, а в центре собранная из них модель

Если специального 3D-сенсора нет, то может помочь телефон: снимаем объект с разных сторон и пользуемся подходами Structure from Motion, чтобы реконструировать 3D-сцену

Облака, воксели, меши

С разных датчиков данные приходят в разном виде. Чаще всего это облако точек, но бывают воксели и меши. Разберём все три на Open3D, самой ходовой библиотеке для 3D на Python.

Облако точек

Облако точек это просто набор точек с координатами XYZ и, обычно, цветом. Облако не упорядочено. Если точки стоят в файле рядом, это не значит, что они рядом в пространстве.

Воксели

Пространство режут сеткой на кубики со стороной voxelsize. Кубик, куда попала хоть одна точка из облака, занят. Соседи вокселя известны сразу: это ячейки справа, слева, сверху и так далее. Поэтому по сетке можно гонять свёртку, как по картинке, только ядро не h×w, а h×w×d.

Меш

Меш это облако точек, где точки связаны гранями в треугольники. По сути, это индустриальный стандарт графики (Gaussian Splatting ещё не всё победил). Включите «треугольники» на сцене: из них и состоит Пепе. А ползунком поменяйте их число: на паре сотен Пепе гранёный, как герои игр девяностых, а на десятке тысяч гладкий. Чем больше треугольников, тем красивее, но тем тяжелее рендер.

Формат OBJ

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

вершина: точка в пространстве

нормаль: куда смотрит грань, по ней считают освещение

грань: треугольник из номеров вершин, считая с единицы

та же грань 1, 2, 4, но у каждой вершины ещё нормаль 2

Нормали можно не писать, тогда они вычислятся автоматически. Переключите рисунок, чтобы увидеть файл с ними. Ещё бывают vt для текстур и mtllib для материалов. Наведите на строку, и на рисунке подсветится то, что она задаёт.

Чистим скан от мусора

Каким бы дорогим ни был лидар, от стекла луч улетит куда-нибудь не туда. А в комнате мог прыгнуть кот и «сфотографироваться» шлейфом своих точек. В Open3D это лечится одной строкой: Давайте напишем её сами на numpy, чтобы понять, что внутри. Выброс это точка, которая сильно оторвалась от соседей. На сцене каждая точка Пепе покрашена по среднему расстоянию до двадцати ближайших соседей: синяя значит соседи рядом, красная значит далеко. Формально для каждой точки $pi$ считают среднее расстояние до её $k$ ближайших соседей, $k$ это nbneighbors: По всем точкам берут среднее $\mu$ и стандартное отклонение $\sigma$ этих расстояний. Точка считается выбросом, если $di \mu + \text{std\ratio} \cdot \sigma$. stdratio задаёт строгость: на сколько $\sigma$ точке можно отойти от среднего. Чем он меньше, тем больше точек уйдёт в мусор.

Пишем remove_outliers

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

Меньше точек

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

Farthest Point Sampling (FPS)

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

Воксели

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

Область интереса

Если интересна только часть облака, оставляем точки внутри ббокса, остальные отбрасываем.

Собираем комнату из шести сканов

У каждого сканера своя система координат. Чтобы получить комнату, переведём каждый скан в мировую систему, а затем склеиваем. Откуда берутся внешние параметры сканеров — это отдельная история. Здесь они уже известны: для каждого сканера мы знаем поворот $R$ (куда он смотрел) и положение $t$ (где стоял). Точка $p{\text{cam}}$ в координатах сканера переходит в мировые так: Обычно $R$ и $t$ хранят вместе, одной 4×4-матрицей camera-to-world $T$.

x world y world z world начало мира t — где стоит камера x cam y cam z cam T = r 11 r 21 r 31 r 12 r 22 r 32 r 13 r 23 r 33 t x t y t z 0 0 0 1 оси камеры (R) t Слева: у мира свои оси, у камеры свои. Справа: столбцы $R$ — это стрелки камеры, записанные в мировых координатах, а последний столбец $t$ — вектор от начала мира до камеры. Матрица camera-to-world собрана из поворота $R$ и сдвига $t$: Точку из системы сканера она переводит в мировую так: То же самое — одним умножением, если дописать к точке единицу (однородные координаты): Столбцы $R$ — это оси камеры $x{\text{cam}}, y{\text{cam}}, z{\text{cam}}$, записанные в мировых координатах; $z{\text{cam}}$ смотрит туда, куда направлен объектив. Те же цвета, что у стрелок на сцене: Поворот ничего не растягивает и не отражает, поэтому Обратная матрица переводит из мира в камеру. Если применить её вместо $T$, сканы уедут не туда: В numpy точки лежат строками матрицы $P$ размера $N \times 3$, поэтому поворот переезжает вправо и транспонируется: В коде это points @ R.T + t.

transform переводит скан из координат сенсора в мировые, а += дописывает его точки в общую комнату.

Пишем merge_scans

На сцене по 300 точек с каждого из шести сканов, как их записал сам сканер. У каждого ноль это он сам, а «вперёд» это куда он смотрел. Поэтому шесть кусков комнаты лежат друг на друге кашей. Когда функция заработает, каждый скан переедет на своё место, и сложится комната.

Нормализуем

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

Соседи и признаки

Следующая станция пайплайна: признаки. Роботу надо понять, какие точки относятся к холодильнику. По одной точке этого не сделать. Точка — это три числа x, y, z. Поэтому точка на дверце холодильника ничем не отличается от точки на стене. Но отличается то, что вокруг точки: стена плоская, у холодильника углы, спинка дивана плавно изгибается. Поэтому каждой точке приписывают вектор признаков: несколько чисел про её окрестность, например куда смотрит поверхность и насколько она изогнута. По признакам точки затем классифицируют, ищут одно и то же место на двух сканах или подают их на вход нейросети. Нейросети умеют считать признаки и сами, но нормали им часто дают готовыми. Ниже три шага, каждый опирается на предыдущий: соседи точки → нормаль → вектор признаков FPFH.

Дальше перейдём к нейросетям. Им «ручные» признаки по типу FPFH не нужны, они всё делают сами из «сырых» точек xyz. Но нормали часто добавляют к xyz: тода на точку приходится 6 чисел вместо 3. FPFH остаётся там, где нейросетей нет, например в классической склейке сканов.

k-d дерево: быстро ищем соседей

Облако не упорядочено, и перебирать все точки ради соседей каждой дорого. Поэтому их складывают в k-d дерево: режем пространство пополам, точки слева идут в левую ветку, справа в правую, потом режем половины, и так дальше. Чтобы найти соседей, спускаемся в нужный лист и смотрим только его. Нажимайте «разрезать» и кликайте по полю. В Open3D дерево строится само, им пользуются все функции ниже.

Нормали: плоскость по соседям

Берём соседей точки в радиусе radius, но не больше maxnn, и подбираем плоскость, которая ближе всего ко всем ним сразу. Перпендикуляр к ней и есть нормаль. У каждой точки теперь своя нормаль: pcd.normals, массив N×3 рядом с pcd.points. Дальше по нормалям считают FPFH, строят меш и, например, отличают пол от стен. Радиус подбирают под плотность облака. Если он маленький, соседей не хватит и нормаль не из чего посчитать. Если большой, плоскость ляжет на полголовы и сгладит мелкие детали вроде губ.

FPFH на плоскости: углы между нормалями

FPFH расшифровывается как Fast Point Feature Histograms: быстрые гистограммы признаков точки. Идею проще увидеть на плоскости. Возьмём точку и её соседей в радиусе. Для каждого соседа посмотрим, на сколько его нормаль повёрнута относительно нормали точки, и сложим эти углы в гистограмму. Похожие гистограммы значат похожие места: кликните по точке, и загорятся точки с похожей гистограммой. Эта гистограмма и есть вектор признаков точки: 12 чисел, по одному на бакет 15°. Он свой у каждой точки и выписан под столбиками. Похожие места находят, сравнивая векторы: чем меньше разница, тем больше места похожи.

FPFH: какие части похожи

В 3D то же самое, только взаимное положение двух нормалей описывают три угла, а не один. Поэтому гистограмм три, по 11 бакетов (11 — потому что «так исторически сложилось» из оригинальной статьи и дефолты везде теперь такие), всего 33 числа на точку. Кликните по точке на сцене: загорятся точки с похожими векторами. Например, глаз находит второй глаз. Зачем это нужно. Когда мы склеивали комнату, для каждого скана было известно, где стоял сканер и куда смотрел: матрица T. В жизни её часто нет. Тогда на двух сканах ищут точки с похожими векторами: скорее всего, это одно и то же место комнаты, например угол стола. По нескольким таким парам вычисляют, как повернуть и сдвинуть один скан, чтобы он лёг на другой. Это и есть T. Ещё векторы подают в классификатор, чтобы отличить холодильник от стены.

Нейросети: PointNet++ и 3D U-Net

Меши оставим в покое и будем считать их извращённым расширением облаков. Для облаков точек берут PointNet++, для вокселей 3D U-Net. Устроены они похоже: слои, которые извлекают признаки, и слои, которые понижают размерность. Как в обычном U-Net.

CV Rocket

Погрузитесь в продвинутый Computer Vision: от сложностей и корнер-кейсов в «обычных» задачах до мультимодальных моделей и дизайна CV-систем.

Архитектуры

PointNet++ (слева) и 3D U-Net (справа)

С вокселями всё просто: это U-Net, где свёртки трёхмерные, а пулинг идёт по трём осям. Математика та же, что для картинок, просто на одну размерность больше. У облака пулинга нет, но понижать размерность надо, то есть прореживать. А прореживать мы уже умеем: между слоями вставляют FPS.

Что внутри слоя

слева слой PointNet++: соседи → общий MLP → максимум; справа 3D-свёртка

Слева на картинке блок «KNN + MLP» со схемы PointNet++. Каждого соседа точки прогоняют через один и тот же MLP, и у каждого получается вектор. Потом MaxPooling собирает из них один: в каждой позиции берёт самое большое значение. Это новый вектор признаков точки. В FPFH правило, по которому он считается, было задано руками: углы между нормалями и гистограмма. Здесь правило задают веса MLP, и их подбирают при обучении, как веса любой другой сети. Справа то же для вокселей: обычная 3D-свёртка.

Где живут

лидар беспилотника, манипулятор, мозг, CAD-деталь

PointNet++ это самая популярная архитектура для облаков: лидары беспилотников, роботы-манипуляторы. 3D U-Net обожают медики: смоделировать имплант для повреждённого черепа, сегментировать участки мозга. И производство: представить CAD-модель вокселями и предсказать прочность детали в каждой точке.

Инференс

Нормировали, перевели в Torch, прогнали, взяли argmax. У каждой точки теперь есть класс. На сцене разметка комнаты: так выглядит хороший результат сети. Модель и её обучение лежат в репозитории воркшопа.

Учат такие сети так же, как двумерные. Есть открытые датасеты вроде ScanNet: помещения отсканированы, люди разметили, какая точка стол, а какая стул. Дальше обычный трейнлуп, оптимизатор и кросс-энтропия. Приятный бонус: 3D-данных не так много, поэтому модели компактные. Обычно хватает одной пользовательской видеокарты на 24 ГБ, не то что у ребят с LLM и их сотнями H100.

Постобработка: делаем меш

Модель предсказала что-то полезное на облаке точек или воксельной сетке. Прибегает заказчик: «Хочу меш». Делаем меш.

Poisson

Poisson не соединяет точки линией. Он строит функцию $\chi$: внутри фигуры она равна 1, снаружи 0. На границе $\chi$ резко растёт с 0 до 1, поэтому её градиент там смотрит внутрь, ровно против нормалей. Значит, нормали из скана и есть градиент $\chi$, только развёрнутый. По градиенту функцию и восстанавливают, это шаги 2 и 3. Поверхность это линия, где $\chi$ между нулём и единицей. Например, $\chi=0.5$. Поэтому Poisson затягивает дыры: функция есть и там, где точек нет. Переключите на «с пропуском» и проверьте. Название от уравнения Пуассона, которым ищут $\chi$ по нормалям: $\Delta \chi = \nabla \cdot V$.

Marching Cubes на плоскости

Marching Cubes превращает сетку в поверхность. Проще всего понять на плоскости. Узел сетки это воксель, а не точка облака. Белый значит воксель относится к объекту, например сеть отнесла его к классу «стул», тёмный значит нет. Берём квадратик из четырёх соседних узлов. Если все углы одного цвета, граница через него не идёт. Если цвета разные, ставим точку посередине каждой стороны, где белый угол соседствует с тёмным, и соединяем эти точки. Из таких кусочков в каждом квадратике и складывается контур. Кликайте по узлам и смотрите, как контур пересобирается.

Marching Cubes в 3D

15 вариантов кубика: отмеченные углы внутри поверхности, остальные снаружи

В 3D вместо квадратика кубик с восемью углами, а вместо отрезков треугольники. Белыми и тёмными углы можно раскрасить 256 способами, но поворотами и отражениями они сводятся к 15 на схеме. Для каждого из 15 случаев заранее нарисованы треугольники, как на схеме. Алгоритм смотрит, какие углы у кубика белые, и кладёт в кубик треугольники этого случая. Poisson для облака внутри тоже заканчивается Marching Cubes: так он вырезает поверхность из $\chi$. В Open3D отдельного Marching Cubes нет, он есть в scikit-image. Если про воксель известно только «занят или пуст», точку на стороне ставят посередине, и меш выходит ступенчатым, как контур на плоской схеме. Если у вокселя есть число, например вероятность класса от сети или сколько точек облака в него попало, точку сдвигают по стороне пропорционально, и поверхность получается гладкой.

Метрики: насколько мы промахнулись

Осталось понять, насколько хорошо получилось наше решение. Для детекции считают IoU: площадь пересечения боксов делим на площадь объединения. Близко к единице отлично. Далеко значит пора задуматься о своих жизненных решениях. Для реконструкции сравнивают облака: Chamfer distance показывает, насколько облака похожи в среднем, Hausdorff distance показывает, где самая большая ошибка.

IoU

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

Chamfer и Hausdorff

Для каждой точки одного облака ищем ближайшую в другом. И обязательно наоборот: синие точки наверху далеко от красных, а красным до синих близко, потому что рядом с ними есть одна синяя. В одну сторону расстояние большое, в другую маленькое. Расстояние от точки $p$ до облака $B$ это расстояние до ближайшей его точки: Chamfer складывает средние в обе стороны, Hausdorff берёт самое большое из всех расстояний, это жирная стрелка: Уведите наверх синюю точку, что стоит рядом с красными: теперь и красным далеко до синих, и Chamfer вырастет почти вдвое. А теперь нажмите «сначала» и опустите к красным все верхние синие, кроме одной: Chamfer станет маленьким, а Hausdorff останется большим из-за этой одной точки.

Пишем Chamfer и Hausdorff

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

Робот, к холодильнику!

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

Подытожим

3D Computer Vision

Научитесь решать 3D-задачи: восстанавливать сцены по фото и видео, строить карты для роботов, работать с лидарными данными. 13 лекций и 13 домашних заданий. Промокод {code} даёт 5% скидки.