- PVSM.RU - https://www.pvsm.ru -
В мире существует множество технологий 3D сканирования. На базе каждой из них созданы десятки моделей сканеров. Какие-то сканеры умеют сканировать только мелкие объекты, какие-то предназначены для сканирования людей. Другие могут отсканировать дом или комнату. Одно только перечисление всевозможных вариаций сканеров заняло бы целую статью.
В этой статье я расскажу об одном из перспективных направлений сканирования — о том как делаются роботизированные 3D сканеры.
Сканирование трёхмерного объекта это не мгновенный процесс. Он требует от человека производить постоянный анализ текущей ситуации и, в зависимости от результатов, корректировку своих действий. Сканирование больших объектов может занять некоторый период времени.
Примеры можно посмотреть тут [1] и тут [2].
Если нужно сканировать много объектов (например, для решения задачи контроля качества или для оцифровки ассортимента магазина), то лучше всего конечно же избавить себя от рутины и использовать робота. Может это и не сильно ускоряет процесс, зато делает результат стабильным, повторяемым и избавляет оператора от физического труда.
(На самом деле главный аргумент – это конечно же: потому что это круто! Человекоподобные роботы и все дела!)
Когда сканирует человек, он видит всё: что отсканировано плохо, что – не до конца, где в сканируемом объекте дырка. Глаза – это независимый сканер, который позволяет проверить качество поступающих данных и сказать «АГА! Вот тут ты не доглядел!». Но когда сканирует робот, то такие решения должен принимать он сам. И единственная информация для принятия таких решений — данные, полученные со сканера. А данные зачастую выглядят так:
Тут приведён результат того, что будет, если поводить сканером секунд 15-20 около объекта.
Все сканеры при сканировании выдают либо облако точек, либо облако полигонов, либо карту глубин. Любой вид информации может содержать дырки. Дырки могут появляться по целому ряду причин:
Но робот-сканер не знает причин. Он не знает, закончился ли объект, или он бликует. Робот не имеет независимых средств контроля. Он познаёт окружающий мир только через сканер.
Первый и самый простой способ – набрать избыточное количество данных или попросту постараться отсканировать объект со всех возможных сторон. Например, вот так:
У такого подхода есть ряд минусов:
(кадр из видео выше, видны ошибки внутри втулки)
Второй подход – заранее просчитанная траектория. Разумеется, это можно сделать только в ограниченном количестве сценариев, когда форма объекта примерно известна. Например, на производстве для решения задачи контроля качества изготовленного изделия.
Третий, самый разумный и интересный способ — в зависимости от наблюдаемого объекта выбрать минимальное количество видов и оптимальную траекторию движения руки со сканером таким образом, чтобы добиться максимального покрытия объекта.
По получаемым данным строится замкнутая поверхность. После чего итеративно наблюдаются области по которым самая низкая достоверность (поверхность есть, но точек, её подтверждающих — нет). Наблюдаем область — > пересчитываем модель — >наблюдаем область. В итоге получается целая серия последовательных сканов в результате которой робот “познаёт” объект
Дело осталось за малым: взять математику, которая позволит строить поверхность. Добавить модуль оценки достоверности построенной поверхности. Запустить в цикле.
Наиболее интересная и красивая математика, решающая проблемму построения поверхности по неполным данным — “восстановление Пуассона”. Основное предположение — мы рассматриваем один объект. Тогда мы можем вообразить себе «скрытую» функцию f(p) от позиции в пространстве. Положительное значение – вне объекта, отрицательное – внутри. На искомой поверхности объекта функция будет нулевой.
Понятно, что градиент f(p) на поверхности – это и есть вектор нормали к искомой поверхности объекта.
При обработке первичных данных от сканера мы уже оцениваем нормали к сканируемой поверхности. Тогда входными данными для поиска функции f(p) будет набор точек в пространстве и нормали к поверхности объекта в этих точках: (p,n)i Обычно при сканировании более менее сложного объекта таких точек сотни тысяч.
Смысл этой функции f(p) и нормалей проще всего понять в 2D. Слева – нормали к 2D объекту, справа –значение функции f (показано третьей координатой), синий цвет – вне объекта, оранжевый – внутри.
Точки (p,n)i лежат на поверхности. В идеале:
где перевернутый треугольник – оператор Набла (вектор градиента).
Естественно, нормали в точках и сами позиции точек содержат ошибки измерения, поэтому не найдется такой функции f, да и не стоит ее искать. В этой ситуации вводят поле нормалей v(x) и требуют минимума:
Решается эта минимизационная задача как раз с помощью уравнения Пуассона:
Кому интересно более подробно почитать про вывод и математику: статья [3] автора придумавшего метод.
А решив это уравнение (есть много способов решить задачу, но придется, конечно, перейти к разностной задаче, а затем и к огромному линейному уравнению), нужно будет найти изоповерхность с нулевым значением f, и с помощью алгоритма марширующих кубов [4] построить полигональную модель.
Тут, кстати, появляется сразу несколько проблем, которые приходится преодолевать:
Но со всех остальных сторон этот математический подход хорош и надежно применим в реальности (хоть и не быстрый процесс вычисления).
Единственное, т.к. плотность точек pi в пространстве очень переменна, то целесообразно разбить весь объем с помощью октодерева и решать итоговое разностное уравнение с учетом разбиения на кубики разного размера.
Можно, либо задать самый мелкий уровень разбиения, либо дробить пространство до тех пор, пока в каждой клетке останется не больше чем одна точка с нормалью. В итоге, количество кубиков будет сопоставимо с количеством точек, полученных при сканировании.
Есть еще один подход, предложенный [5] F. Calakli and G. Taubin в 2011г., который дает такой же качественный результат, а при определенных условиях даже лучше, как и метод с решением уравнения Пуассона, но несколько доступней для понимания и программирования. В википедии же эти два метода просто путают [6].
Аналогично ищем функцию f(p), которая отрицательна внутри объекта, а положительна вне его. Точно также градиент f(p) хотим приблизить к нормалям в заданных позициях, которые мы получили при сканировании. Но будем искать минимум:
Выглядит довольно громоздко, но на самом деле мы лишь просим, чтобы функция в точках Pi была бы поменьше (первый член), чтобы градиент ее был поближе к нормалям в тех же точках (второй член), и чтобы во всем объеме у нее вторые производные были поменьше, точнее – Гессиан функции (третий член). Требование на вторые производные, довольно важное, т.к. очень хочется, чтобы уйдя за границы объекта, функция не начала осциллировать, и не получилось таких кошмарных картинок:
Т.е. все минимизировали, но уйдя подальше от точек, которые мы промерили сканером, функция f(p) не повела себя произвольно.
И, заметьте, что каждый член – квадрат. Это не просто так, т.к. именно для квадратичных форм несложно аналитически получить экстремум (для форм A*A-2*b*A+c локальный минимум в точке A=b). Только запишем все в разностном виде, т.е. заменим частные производные на разности на границах маленьких кубиков, а потом в матричном, чтобы воспользоваться фокусом с минимумом квадратной формы. И в итоге получим линейную систему уравнений, неизвестные в котором – значения функции f(p) внутри кубиков. А кубики, также как и в описанном выше методе реконструкции, стоит брать неравномерно, а строить октодерево. Кому интересно подробный вывод, текст [5] статьи.
Работает по скорости примерно также, как и метод, основанный на уравнении Пуассона. Есть одно маленькое преимущество в том, что не нужно «размазывать» нормали по пространству, чтобы иметь возможность получить дивергенцию от векторного поля нормалей, теряя при этом точность и излишне сглаживая объект. С другой стороны, если сканер довольно грубо оценивает нормали, то это преимущество может стать недостатком метода.
Сам по себе алгоритм Пуассона не говорит нам, что видно, а что нет. Нужно придумать некоторую меру качества для оценки достоверности результата. Самая простая мера — пройти вдоль поверхности небольшими кубиками и посмотреть как много попало точек в каждый из них:
Чем больше точек — тем больше достоверность, тем более красного цвета. Такая мера качества будет весьма репрезентативной. Действительно, мы не можем доверять областям, где ничего не видели. А уж если видели, то, наверное, там действительно что-то есть.
Теперь вроде всё понятно. Нам нужно выбрать такие точки дальнейшего сканирования, с которых сделать следующую серию кадров, которую замерджить в основную модель.
Для этого мы разметим окружающее пространство. Каждую его точку проверим, определив сколько недостоверных точек фигуры мы увидим из неё. Чем больше таких точек — тем выгоднее смотреть.
Остаётся найти локальные максимумы и запускать наблюдения:
Потом опять выполняется Пуассон, потом опять выполняется дополнительное сканирование. И так по кругу, пока не появится готовая модель.
Может можно отсканировать хорошо, чтобы всё было и так? Зачем усложнять кучей математики? Вот простой пример. Три картинки. Скан был сделан сканером Artec Spider. Первый — сырая информация со сканера, по сути облако точек. Второй — алгоритм «Fusion», который просто делает усреднение и контроль положения. Третий — алгоритм Пуассона. И ведь разница на лицо!
А вот так этот дракоша будет выглядеть целиком:
В итоге, алгоритм сканирования поверхности роботом выглядит следующим образом:
Более подробно про такую схему сканирования можно почитать, например, здесь [7].
Или посмотреть как всё это дело работает:
P.S. Робот в видео крутит головой просто так, к сканированию это не имеет отношения
P.S.S. Спасибо Vasyutka [8] за помощь в написании статьи и команде Артека [9] за многочисленные правки и доведение до ума!
Автор: Artec 3D
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/3d/113351
Ссылки в тексте:
[1] тут: http://www.youtube.com/watch?v=Ye_ORnuOwWU
[2] тут: https://www.youtube.com/watch?v=lBS1xOV0VHQ
[3] статья: http://www.cs.jhu.edu/~misha/MyPapers/SGP06.pdf
[4] марширующих кубов: https://ru.wikipedia.org/wiki/Marching_cubes
[5] предложенный: http://mesh.brown.edu/ssd/pdf/Calakli-pg2011.pdf
[6] путают: https://en.wikipedia.org/wiki/Poisson%27s_equation
[7] здесь: http://www.cs.tau.ac.il/~dcor/articles/2014/quality-driven.pdf
[8] Vasyutka: https://habrahabr.ru/users/vasyutka/
[9] Артека: http://artec-group.com/
[10] Источник: https://habrahabr.ru/post/277885/
Нажмите здесь для печати.