A COMPARATIVE ANALYSIS OF ALGORITHMS FOR SURFACE RECONSTRUCTION FROM A POINT CLOUD

Реконструкция поверхности – это процесс создания трехмерного представления поверхности из набора дискретных точек, часто полученных с помощью технологий трехмерного сканирования или визуализации. Это фундаментальная задача появляется в различных областях. Так, например, в медицинской визуализации

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

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

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

Целью данной статьи является сравнение явных алгоритмов реконструкции поверхности: Ball-Pivoting (поворот шара)

Под подходящим алгоритмом будем подразумевать алгоритм, который удовлетворяет следующим критериям:

1. Критерий топологии. Все исходные точки, которые подавались на вход, после реконструкции должны оставаться на тех же местах;

2. Критерий овражности. Модель не должна иметь овражностей в своей геометрии, если так не было задумано;

3. Критерий непрерывности. Модель не должна иметь разрывов в своей геометрии, если так не было задумано;

4. Критерий точности. Модель должна соответствовать реальному объекту.

Работу фотограмметрии

I. Получение снимков объекта;

II. Получение 3D модели из серии фотографий;

III. Пост-обработка получившейся 3D модели.

На втором этапе выделяют 4 шага:

1. Сопоставление изображений;

2. Калибровка камер и получение разреженного облака точек;

3. Получение плотного облака точек;

4. Реконструкция поверхности из плотного облака точек.

Как видно, реконструкция поверхности происходит на четвертом шаге второго этапа процесса фотограмметрии.

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

– способность обрабатывать зашумленное облако точек;

–работа с плотностью точек 60%

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

Алгоритм Ball-Pivoting (поворот шара)

Алгоритм можно описать следующим образом: 

1. Инициализация. Сначала случайным образом выбирается начальная точка из входного облака точек;

2. Выбор шара. Шар с фиксированным радиусом помещается в начальную точку, и алгоритм пытается определить соседние точки в пределах шара, которые могут образовать треугольник с начальной точкой. Шар постепенно поворачивается для поиска потенциальных точек-кандидатов;

3. Формирование треугольника. Если в пределах шара найдена подходящая точка-кандидат, то формируется треугольник, соединяющий начальную точку, найденную точку-кандидат и произвольную точку из облака точек, находящуюся в шаре. Этот образованный треугольник добавляется к существующей сетке;

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

5. Создание новых треугольников. Шаги 2-4 повторяются итеративно, при этом поворотная точка становится новой начальной точкой.

Алгоритм Poisson Surface Reconstruction (реконструкции поверхности Пуассона)

Алгоритм можно описать следующим образом:

1. Предварительная обработка. Расчет нормалей облака точек при помощи алгоритма Point Cloud Normal Estimation (оценка нормалей облака точек)

2. Реконструкция Пуассона. Реконструкция Пуассона формулирует задачу реконструкции как задачу решения уравнения Лапласа с граничными условиями Дирихле, используя объемное представление, известное как знаковое поле расстояний (SDF)

3. Вычисление знакового поля расстояний SDF. Сначала облако точек описывается минимальным объемным примитивом (кубом). После этого куб равномерно разбивается на воксели. Далее для каждого вокселя или ячейки в объемном представлении алгоритм вычисляет знаковое расстояние от этого вокселя до ближайшей точки входного облака точек. Знак указывает на то, находится ли этот воксель внутри или вне реконструируемой поверхности;

4. Неявное выделение поверхности. Поле SDF используется для выделения неявной поверхности, представляющей реконструированную поверхность, как изоповерхность SDF. После этого при помощи алгоритма Marching Cubes

Алгоритм Power Crust (силовой корки)

Алгоритм можно описать следующим образом:

1. Построение диаграммы Вороного. Алгоритм начинает работу с построения диаграммы Вороного для входных точек. Диаграмма Вороного делит пространство на регионы на основе близости к каждой точке, создавая сеть ячеек вокруг каждой точки;

2. Создание двудольного графа. В двудольном графе вершины представляют собой ячейки диаграммы Вороного, а ребра – грани диаграммы Вороного;

3. Вычисление медиальной оси двудольного графа. Медиальная ось представляет собой центральное ядро или скелет облака точек, которые равноудалены от двух или более точек входа;

4. Построение начальной поверхности. Алгоритм покрывает все входное облако точек путем соединения точек медиальной оси. Получается начальная поверхность, образованная сетью тетраэдров;

5. Уточнение поверхности. Алгоритм производит уточнение поверхности с помощью следующих шагов:

5.1. Подразделение. Поверхность подразделяется на более мелкие тетраэдры;

5.2. Классификация. Каждый тетраэдр классифицируется, как находящийся внутри, снаружи или на поверхности облака точек;

5.3. Реконструкция поверхности. Алгоритм строит новую поверхность, которая аппроксимирует облако точек, соединяя точки медиальной оси тетраэдров, классифицированных как «находящиеся на поверхности»;

5.4. Завершение. Процесс уточнения завершается при достижении желаемого уровня точности;

6. Получение выходной поверхности.

В заключение следует отметить, что алгоритмы Ball-Pivoting, Poisson Surface Reconstruction и Power Crust представляют собой значительные достижения в области реконструкции поверхности, предлагая уникальные подходы к восстановлению моделей по облаку точек. Эти алгоритмы играют важную роль в различных областях, таких как компьютерная графика, компьютерное зрение и робототехника, позволяя создавать точные и детальные представления поверхностей, которые вносят вклад в широкий спектр приложений и исследований.

Проанализируем рассмотренные выше алгоритмы на основе некоторых известных сведений, теории и предположений о них (табл. 1)

Можно сделать следующие выводы:

1. Все алгоритмы имеют одинаковую вычислительную сложность 0 (n log n);

2. Алгоритм Poisson Surface Reconstruction не чувствителен к параметрам, однако имеет основной недостаток – недетерминированный выход;

3. У всех алгоритмов получается качественная сетка при качественном входе. Однако только алгоритм Ball-Pivoting способен обрабатывать облако точек, начиная с 40% плотности;

4. И, наконец, все алгоритмы способны обрабатывать зашумленное облако точек.

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

Для сравнения результатов работы алгоритма был проведен вычислительный эксперимент. Его суть заключалась в восстановлении поверхности модели из облака точек уже существующей модели и анализа получившегося результата. Входными данными вычислительного эксперимента были облака точек (вершины) разной плотности (40%, 60% и 80%) исходной модели низкополигонального стэнфордского кролика (Stanford Bunny)

Рисунок 1 - Входная модель

DOI:10.23670/IRJ.2023.138.202.2

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

Общее количество точек в плотном облаке точек модели – 2503.

Сначала эксперимент был проведен на незашумленных данных, а после – на зашумленных.

На рис. 2 (а-в) показано незашумленное облако точек с разными плотностями.

Рисунок 2 - Облако точек с плотностью 40% (а), 60% (б), 80% (в)

DOI:10.23670/IRJ.2023.138.202.3

А на рис. 3 (а-в) показано зашумленное облако точек с разными плотностями. Всего было добавлено 20% зашумленных точек от количества точек в текущем облаке. Шум был сгенерирован по нормальному закону распределения .

Рисунок 3 - Облако точек с плотностью 40% (а), 60% (б), 80% (в)

DOI:10.23670/IRJ.2023.138.202.4

Сравнение результатов работы алгоритмов производилось путем наложения полученной модели на исходную и нахождения расстояния между ними с помощью алгоритма Cloud to Mesh Signed Distances

[18]

.

Эксперимент состоял из трех этапов:

1. Оценка работы каждого алгоритма на трех облаках точек разных плотностей на незашумленных данных;

2. Сравнение работы всех алгоритмов на одинаковых плотностях и выбор алгоритма, который лучше всего подходит под критерии, описанные в постановке задачи;

3. Проведение этапов 1 и 2 для зашумленных данных.

Для проведения вычислительного эксперимента была написана программа на языке Python. В функционал программы входит управление запуском алгоритмов, поиск расстояний между моделями, добавление шума к облаку точек и создание тепловой карты наложения моделей друг на друга. Также в функционал программы входит проверка на пустые полигоны модели с помощью алгоритма «Ray Casting»

Алгоритмы Ball-Pivoting и Poisson Surface Reconstruction были взяты из библиотеки Open3D [20], а алгоритм Power Crust был взят с официального сайта разработчиков метода

В ходе проведения первого этапа вычислительного эксперимента были получены модели, представленные в табл. 2.

– входные точки остались на своих местах (программные показатели дают среднее расстояние между соответствующими точками в пределах e-5);

– модели не имеют овражностей (визуальная оценка);

– модели не имеют пустых полигонов (метод «Ray Casting»).

Таким образом, требования 1-3, указанные в постановке задаче, были выполнены для всех алгоритмов.

Результаты работы алгоритмов на зашумленных данных представлены в табл. 3.

– входные точки остались на своих местах (среднее расстояние между соответствующими точками в пределах e-3);

– модели не имеют овражностей (визуальная оценка);

– модели не имеют пустых полигонов (метод «Ray Casting» для поиска разрывов в полигональной сетке).

Таким образом, требования 1-3, указанные в постановке задаче, были выполнены для всех алгоритмов. Также все алгоритмы показали способность обрабатывать зашумленное облако точек, что является важным требованием в задаче фотограмметрии.

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

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

Рисунок 4 - Шкала расшифровки тепловых карт

DOI:10.23670/IRJ.2023.138.202.8

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

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

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

Исходя из анализа строк табл. 5 можно определить, что наилучший результат по среднему расстоянию достигается при наибольшей плотности (80%), что достаточно очевидно и отражает теоретический анализ алгоритмов (качественная сетка при качественном входе). Также при наибольшей плотности для всех алгоритмов максимальные значения отличаются от средних на один разряд. В то время как на меньших плотностях у алгоритма Power Crust они отличаются на два разряда.

Стоит отметить также высокое среднее значение при плотности 60% у алгоритма Power Crust. Данный факт требует дополнительного анализа и исследования, но не в рамках данной работы.

Исходя из этого, можно сделать вывод, что алгоритм Power Crust уступает двум другим рассматриваемым алгоритмам при работе на малых и средних плотностях.

 Теперь проанализируем столбцы табл. 5, то есть работу алгоритмов на одинаковых плотностях:

– на 40% плотности облака точек лучшим алгоритмом оказался Ball-Pivoting. Среднее расстояние составило 0,000578438, а максимальное – 0,00664158.

– на 60% плотности облака точек лучшим алгоритмом оказался Poisson Surface Reconstruction. Среднее расстояние составило 0,00041903, а максимальное – 0,00529197.

– на 80% плотности облака точек лучшим алгоритмом оказался Poisson Surface Reconstruction. Среднее расстояние составило 0,00034862, а максимальное – 0,00618712.

Подытоживая, можно сказать, что на малых значениях плотности лучшие показатели наблюдаются у алгоритма Ball-Pivoting, на средних – Poisson Surface Reconstruction и на больших значениях все алгоритмы показывают схожий результат. Это отражает теоретический анализ табл. 1. Заметим, что при 40% средние значения у алгоритмов Ball-Pivoting и Poisson Surface Reconstruction (0,00057843 и 0,00059747 соответственно) близки, но максимальное значение меньше у алгоритма Ball-Pivoting (0,00664158 против 0,00717853).

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

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

Исходя из анализа строк табл. 7 здесь также наилучший результат по среднему расстоянию достигается при наибольшей плотности (80%), что еще раз отражает теоретический анализ алгоритмов (качественная сетка при качественном входе). Также при наибольшей плотности для всех алгоритмов максимальные значения отличаются от средних на один разряд. В то время как на меньших плотностях у алгоритма Power Crust значения отличаются на два разряда.

Стоит отметить, что высокого среднего значения при плотности 60% у алгоритма Power Crust здесь не наблюдается. Однако и тут можно сделать вывод о том, что алгоритм Power Crust уступает двум другим рассматриваемым алгоритмам при работе на малых и средних плотностях.

Общий анализ табл. 7 дает следующие результаты:

– на 40% плотности облака точек лучшим алгоритмом оказался Ball-Pivoting. Среднее расстояние составило 0,000708876, а максимальное – 0,00759576.

– на 60% плотности облака точек лучшим алгоритмом оказался Poisson Surface Reconstruction. Среднее расстояние составило 0,00054058, а максимальное – 0,00509344.

– на 80% плотности облака точек лучшим алгоритмом оказался Poisson Surface Reconstruction. Среднее расстояние составило 0,00038608, а максимальное – 0,00454925.

Подытоживая, можно сказать, что на малых значениях плотности лучшие показатели наблюдаются у алгоритма Ball-Pivoting, на средних – Poisson Surface Reconstruction и на больших значениях все алгоритмы показывают схожий результат. Это отражает теоретический анализ табл. 1. То есть выводы получились, как и на незашумленных данных.

Таким образом, исходя из анализа табл. 5 и табл. 7, можно сделать следующие выводы:

1. Все алгоритмы дают качественный результат при качественном входе, то есть на плотности 80%;

2. Сравнительный анализ алгоритмов не зависит от зашумленности данных;

3. На малых плотностях рекомендуется использовать алгоритм Ball-Pivoting;

4. На средних плотностях – Poisson Surface Reconstruction;

5. На высоких плотностях – любой из трех алгоритмов.

И, наконец, сделаем вывод о применимости алгоритмов к задаче фотограмметрии. В задаче фотограмметрии используется облако точек плотности от 70%

В результате проведено сравнение алгоритмов Ball-Pivoting, Poisson Surface Reconstruction, Power Crust путем проведения вычислительного эксперимента, а также поиск наиболее подходящего алгоритма для задачи фотограмметрии. Суть вычислительного эксперимента заключалась в восстановлении поверхности модели из незашумленного и зашумленного облака точек разной плотности уже существующей модели и последующего анализа получившейся модели.

В результате сделан вывод о том, что лучшим алгоритмом на зашумленном и незашумленном облаке точек плотности 40% оказался алгоритм Ball-Pivoting. А лучшим алгоритмом на зашумленном и незашумленном облаке точек плотности 60% и 80% оказался алгоритм Poisson Surface Reconstruction.

Исходя из известных фактов о входных данных в задаче фотограмметрии, сделан вывод о применимости для работы с ней алгоритмов Ball-Pivoting и Poisson Surface Reconstruction.