Дескриптивное представление 3D моделей. Визуальный поиск

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

В машинном обучении есть понятие признакового описания объекта — вектора, состоящего из некоторых измеренных характеристик объекта. Наличие признакового описания еще не гарантирует, что с его помощью мы сможем эффективно решать озвученные выше задачи. Обычно, когда необходимо найти компактное и информативное описание объектов, говорят о задаче обучения представлениям (representation learning). Различные техники обучения представлениям позволяют выделять т.н. вектора скрытых переменных (latent space vectors), которые можно использовать для порождения новых данных, решения задач классификации и многих других задач.

3D ML. Часть 1: формы представления 3D-данных

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

Так что же это такое? Дескриптором можно назвать любой набор чисел, которые можно каким либо образом извлечь из объекта, и в дальнейшем использовать их в самых разных задачах вместо самих данных. Основными требованиями, которые обычно накладывают на дескрипторы [1] являются:

• кросс-модальность — для возможности работать в рамках одной задачи с различными типами данных (например в [3], авторы работают одновременно с изображениями объектов и с их 3D моделями);
• способность уникальной идентификации — различные объекты должны иметь различные дескрипторы;
• масштабируемость — размер дескрипторов должен зависеть только от способа его определения, а не от размера самого объекта данных;
• способность к полному или частичному восстановлению исходных данных.

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

Так, недавно были получены способы эффективного дескриптивного представления динамических процессов, протекающих в жидкостях и газах [4], и также были определены корректные метрики качества для таких полей [5].

Рис.1 а) поле скоростей жидкости, полученное в результате классического численного моделирования (вычислительно емкий и сложный процесс); б) натурный эксперимент; в) поле скоростей, восстановленное из дескриптивного представления [4].

Рис.2 Концептуальная схема дескриптивного описания мультимедийных данных [2].

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

Из всех типов данных нас больше всего интересуют 3D модели. Каждая модель обладает рядом разноплановых характеристик: текстура, форма, заданная динамическая анимация и многое другое. Рассмотрим одну из наиболее сложных и актуальных модальностей — форму объекта. Исчерпывающей работой, посвященной построению дескрипторов для форм трехмерных объектов, является диссертация [2].

Рис.3 Таксономия визуальных дескрипторов по стандарту MPEG-7 [1].

Если мы будем учитывать специфику формата трехмерных данных, то на их дескрипторы можно наложить следующие дополнительные свойства:

• инвариантность к ориентации модели и масштабу;
• нечувствительность (робастность) к замкнутости меша или наличию “висячих” вершин;
• робастность к степени детализации модели;
• инвариантность к перенумерованию вершин в меше.

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

Рис.4 Различный меш может представлять одни и те же сущности в контексте конкретной задачи [2].

Рассмотрим основные способы и принципы построения трехмерных дескрипторов.

а) Дескрипторы, основанные на распространении пучка лучей (ray cast descriptors):

Рис.5 Визуализация распространения пучка лучей из геометрического центра модели с различным разрешением, и полученные векторы дескриптивного представления. [2].

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

• Модель окружают правильным многогранником (т.н. икосферой) и из каждого полигона этого многогранника пускают луч. В качестве вектора дескриптивного описания используют расстояния, которые лучи проходят до столкновения с полигонами модели.
• Внутри модели выбирается точка — источник, из которой вдоль выделенных направлений распространяются лучи. В качестве вектора дескриптивного представления используют длину отрезков на этих направлениях, крайние точки которых — точки пересечения лучей с полигонами модели (Рис.5).

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

Ray Casting Visual Search (RCVS). Простой и быстрый алгоритм поиска схожих по геометрии 3D моделей

б) Дескрипторы, основанные на множестве двумерных силуэтов (Silhouette-Based Feature Vectors)

Рис.6 Визуализация набора контрастных силуэтов для трехмерной модели самолета [2].

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

в) Дескрипторы, основанные на картах глубины (Depth Buffer-Based Feature Vector)

Рис.7 Визуализация набора карт глубины для трехмерной модели самолета (верхний ряд) и их двумерного преобразования Фурье (нижний ряд) [2].

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

г) Дескрипторы, основанные на объемах моделей (Volume-Based Feature Vector)

Рис.8 Визуализация разбиения трехмерной модели коровы на набор полигональных объемов [2].

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

д) Воксельные дескрипторы (Voxel-Based Approach)

Рис.9 Визуализация трехмерной модели автомобиля и вокселизаций, полученных различными алгоритмами на набор полигональных объемов [2].

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

е) Дескрипторы, полученные разложением модели по функциональному базису на сфере (Describing 3D-Shape with Functions on a Sphere)

Рис.10 Визуализация восстановления трехмерной модели автомобиля из дескриптора — набора сферических гармоник [2].

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

Говоря проще, представим, что мы умеем эффективно описывать ряд простых форм в пространстве (сфера, эллипсы, плоскости и т.д.), и из математики нам известно, как правильно выбирать эти примитивные формы, чтобы с помощью “сложения” их друг с другом получить произвольную, сколь угодно сложную форму, тогда в качестве дескриптора будет выступать вектор из чисел — весов, которые показывают, какие элементарные базисные формы образуют данную.

ж) Дескрипторы, основанные на глубинных сферических слоях (Feature Vectors Based on Layered Depth Spheres)

Рис.11 Визуализация исходной трехмерной модели самолета (слева), ее вокселизованной версии (посередине) и разбиение вокселизованной версии на сферические слои [2].

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

з) Моментные дескрипторы (Moments-Based Feature Vector)

Рис.12 Визуализация восстановления трехмерной модели космического корабля с помощью трехмерных моментов Цернике с разными значениями порядка [6].

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

В качестве отдельного типа дескриптивного представления рассматривают также комбинации дескрипторов, рассмотренных выше. Так, например, в [2] автор, после многочисленных экспериментов и сравнений различных комбинаций дескрипторов в задаче классификации форм, пришел к выводу, что лучше всего себя показывает в большинстве тестовых примеров комбинация из дескрипторов, описанных в пунктах а), б) и в).

3D Zernike descriptors

Рис.13 Графики значений многочленов Цернике в единичном круге.

Рассмотрим подробнее моментный подход, описанный в пункте з). На сегодняшний день одним из самых перспективных и наиболее универсальных представителей данного класса методов является подход, получивший название трехмерные дескрипторы Цернике [6].

Как и свойственно данному подходу, необходимо определить функции моментов для трехмерной модели:

Функция f под интегралом может определять поверхность модели в трехмерном пространстве. Здесь:

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

Например, функции Цернике могут служить примером такого базиса. С помощью моментов Церинке можно восстановить исходную функцию:

где омега — это моменты Цернике, Z — это функция Цернике. О том, как вычисляются моменты и значения индексов, более подробно описано в статье [6].

Поскольку для точного восстановления исходной поверхности пришлось бы использовать бесконечное число моментов, что невозможно в реальной жизни, мы используем конечное число моментов, а влияние отброшенных слагаемых в сумме считаем пренебрежимо малыми. Для вычисления моментов необходимо считать интегралы, в которых участвует функция, для которой мы хотим найти разложение. В реальных задачах аналитическое представление функции может быть неизвестно. Например, полигональная модель в большинстве случаев не описывается аналитическими функциями при хранении. Поэтому прибегают к вокселизации модели. Это позволяет получить некоторую кусочно-постоянную функцию, которая приближённо описывает форму исходной модели. Например, функция принимает только два значения: 1, если ячейка на воксельной сетке заполнена, или 0, если она свободна. Тогда для вычисления моментов вместо процедуры интегрирования достаточно просуммировать объемы “кубиков”, из которых состоит модель после вокселизации (далее выписана формула для вычисления геометрических моментов по воксельной сетке, с помощью которых рассчитываются моменты Цернике):

N- это размер воксельной сетки, f- это значение функции в ячейке воксельной сетки, x, y, z- это координаты ячеек. Как правило, они нормированы так, чтобы их значения принадлежали отрезку [0;1] или [-1;1].

Глобально, алгоритм построения дескрипторов Цернике можно разделить на следующие этапы:

1. Помещение полигональной модели в единичную сферу.
2. Вокселизация модели.
3. Расчет геометрических моментов.
4. Расчет моментов Цернике из полученных на предыдущем этапе геометрических моментов.
5. Построение вектора дескриптивного описания из полученных на предыдущем шаге моментов.

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

Дескрипторы определяются через моменты Цернике как норма вектора:

Пример прикладной задачи: 3D shape based visual search.

Имея на вооружении дескриптивное представление данных, можно решать широкий спектр задач. Задачи могут прямо использовать дескрипторы, как например в работах [7,9], где дескрипторы Цернике используются в качестве функции расстояния между отдельными моделями и целыми сценами из трехмерных объектов. Косвенное использование дескрипторов чаще всего встречается в задачах глубокого обучения, где они выступают в качестве промежуточной переменной, подаваемой на вход очередному слою нейронной сети.

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

Проблема автоматизации процесса поиска трехмерных моделей сегодня становится все более актуальной. С увеличением количества 3D наборов данных моделей и широким распространением игровых движков, процесс быстрого поиска готовых моделей по референсам, собранным из геометрических примитивов, как никогда раньше важен для разработчиков и 3D художников. Так у Unity3D имеется бесплатный плагин, решающий данную задачу.

Рис.14 Внешний вид Unity visual search.

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

Для самостоятельной реализации алгоритма поиска объекта с наиболее похожей геометрией мы доработали оригинальную реализацию алгоритма построения дескрипторов Цернике, реализованную на языке C++. В качестве тестового набора данных был выбран собственный набор 3D моделей из наших проектов. Ранжирование поисковой выдачи основано на расстоянии в пространстве L2 между дескриптивными представлениями моделей. Для выполнения быстрого поиска необходимо решить задачу поиска “ближайшего соседа”. Существуют различные подходы как для точного решения этой задачи, так и для приближенного. В нашем случае использовался поиск по KD-дереву, которое строилось на основе дескриптивного представления моделей. Визуализация была написана с использованием библиотеки nanoflann на C++, и позже переписана на языке Python с использованием KD-дерева из scipy. На видео представлен результат поиска среди 490 моделей. Референсная модель — это самый первый объект. Числа показывают расстояние между дескрипторами референсной модели и текущей.

Автор

Вадим Кондаратцев

vadim@phygitalism.com

Источники

[1] MPEG-7 Requirements Group, “MPEG-7 Requirements Document,” V.15. ISO/IEC N4713, MPEG-7, Sydney, July 2001

[2] Vranic, D.V. and Saupe, D., 2004. 3D model retrieval (Doctoral dissertation, University of Leipzig)

[3] Kohl, G., Um, K. and Thuerey, N., 2020. Learning Similarity Metrics for Numerical Simulations. arXiv preprint arXiv:2002.07863.

[4] Сухарев, Т.Ю. and Ревизников, Д.Л., 2018. Описание гидродинамических полей с использованием разложений по модам. Гидродинамика больших скоростей и кораблестроение(pp. 121–126).

[5] Li, Y., Su, H., Qi, C.R., Fish, N., Cohen-Or, D. and Guibas, L.J., 2015. Joint embeddings of shapes and images via cnn image purification. ACM transactions on graphics (TOG), 34(6), pp.1–12.

[6] Novotni M., Klein R. Shape retrieval using 3D Zernike descriptors // Computer-Aided Design. 2004. № 11 (36). C. 1047–1062. DOI: 10.1016/j.cad.2004.01.005.

[7] Berjón, Daniel & Morán, Francisco. (2012). Fast human pose estimation using 3D Zernike descriptors. Proceedings of SPIE — The International Society for Optical Engineering. 8290. 19-. 10.1117/12.908963.

[8] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rich 3d model repository. arXiv preprint arXiv:1512.03012, 2015 [project page]

[9] Fisher, M., Savva, M. and Hanrahan, P., 2011. Characterizing structural relationships in scenes using graph kernels. In ACM SIGGRAPH 2011 papers (pp. 1–12).