Способ формирования архитектуры нейросети для классификации объекта, заданного в виде облака точек, способ ее применения для обучения нейросети и поиска семантически схожих облаков точек
METHOD OF FORMATION OF NEURAL NETWORK ARCHITECTURE FOR CLASSIFICATION OF OBJECT TAKEN IN CLOUD OF POINTS, METHOD OF ITS APPLICATION FOR TEACHING NEURAL NETWORK AND SEARCHING SEMANTICALLY ALIKE CLOUDS OF POINTS

ОБЛАСТЬ ТЕХНИКИ
[0001] Заявленное техническое решение относится к области обработки цифровых данных, применяющихся, в частности, в области нейросетевых технологий для формирования структур нейросетей, предназначенных для распознавания объектов, описываемых облаками точек.
УРОВЕНЬ ТЕХНИКИ
[0002] В настоящее время распознавание и анализ геометрических 3D-моделей является важной функцией обработки цифровой информации. Глубокие сверточные сети (сверточные нейросети) [1] хорошо проявили себя при выполнении аналогичной задачи по распознаванию для наборов двумерных изображений. Поэтому естественно, что в данный момент существует необходимость адаптации глубоких сверточных сетей применимо к 3D-моделям [2, 3, 4].
[0003] Такая адаптация нетривиальна. Одним из приемов создания сверточных сетей применительно к 3D-данным является растеризация 3D-моделей на равномерные воксельные сетки. Однако такой подход приводит к чрезмерному потреблению памяти и к увеличению длительности обработки, что в результате приводит к использованию маленьких пространственных разрешений (например, 64×64×64), которые явно меньше типичных для обработки двумерных данных разрешений и недостаточны для решения задач распознавания, требующих внимания к мелким деталям моделей.
[0004] Для решения существующих задач в данной области было предложено огромное количество индексирующих структур, масштабируемых гораздо лучше, чем равномерные сетки, например, Kd-деревья [5], октодеревья [6], деревья двоичного разбиения пространства [7], R-деревья [8], конструктивная блочная геометрия [9] и др.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
[0005] Для решения существующих недостатков применения структур нейросетей для целей анализа цифровых 3D-данных необходимо создать индексирующую структур для формирования базы для глубоких архитектур, подобно тому, как равномерные сетки используются для организации вычислений, выравнивания данных и связывания параметров внутри сверточных сетей.
[0006] Для решения этой задачи предлагается использовать индексирующую 3D-структуру в виде Kd-дерева с созданием глубокой архитектуры нейросети (Kd-сети), которая во многом подражает сверточной сети, но использует Kd-дерево для формирования вычислительного графа, связывания обучаемых параметров и вычисления последовательности иерархических представлений в процессе прямого распространения.
[0007] Kd-сети по уровню точности операций распознавания, таких как классификация, поиск похожих объектов и сегментация частей аналогичны сверточным сетями в ряде воплощающих применений превосходят их. В то же время Kd-сети задействуют меньше памяти и вычислительно более эффективны во время обучения и тестирования, благодаря лучшей способности Kd-деревьев индексировать и структурировать 3D-данные по сравнению с равномерными воксельными сетками.
[0008] Техническим результатом является повышение скорости поиска схожих объектов по облакам точек с помощью архитектуры Kd-сети.
[0009] Заявленный результат достигается за счет способа формирования архитектуры нейросети для классификации объекта, заданного в виде облака точек, при котором:
D
получают облако точек размера N=2, описывающее объект, где D - параметр глубины;
формируют Kd-дерево Т глубины D для полученного облака точек, причем дерево содержит корневой узел, листовые узлы и нелистовые узлы;
генерируют для каждой точки облака вектор признаков, описывающий упомянутую точку;
рекуррентно вычисляют вектора параметров признаков, описывающие нелистовые узлы дерева, причем каждый вектор параметров вычисляется путем композиции поэлементного нелинейного преобразования и мультипликативного преобразования векторов признаков дочерних узлов с матрицей и свободным членом, определяемыми глубиной узла и направлением разбиения, соответствующим узлу в Kd-дереве;
вычисляют вектор признаков, описывающий корневой узел дерева;
применяют к вычисленному на предыдущем шаге вектору признаков, описывающему корневой узел, линейный или нелинейный финальный классификатор, предсказывающий вектор вероятностей отнесения объекта к тому или иному семантическому классу.
[0010] В частном варианте осуществления способа вектор признаков содержит 3D-координаты, цвет, или направление нормали.
[0011] В другом предпочтительном варианте заявленного решения представлен способ обучения нейросети, выполненной по вышеуказанной архитектуре, для классификации объектов, описываемых облаками точек, при котором на вход нейросети подается множество размеченных облаков точек, в котором матрицы и свободные члены преобразований на каждом уровне Kd-дерева и для каждого возможного направления разбиения, а также параметры финального классификатора обучаются при помощи алгоритма обратного распространения ошибки.
[0012] Еще в одном предпочтительном варианте реализации представлен способ поиска семантически схожих облаков точек с помощью вышеуказанной архитектуры нейросети, обученной вышеупомянутым способом, в которой упомянутая нейросеть применяется для вычисления векторных признаков, описывающих корневые узлы кд-деревьев, построенных по облакам точек, причем семантическая схожесть облаков точек определяется на основании расстояния между упомянутыми векторными признаками.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
[0013] Фиг. 1 иллюстрирует последовательность этапов формирования структуры Kd-сети.
[0014]
[0015] Фиг. 2 иллюстрирует пример Kd-дерева, построенного на основании облаков точек
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
D
[0016] На Фиг. 1 представлен процесс формирования архитектуры нейросети для классификации объекта (100). На первом шаге (101) получают входное облако точек размера N=2, где D - параметр глубины. Облако точек описывает трехмерный объект. Для полученных точек дополнительно может определяться такие свойства, как: цвет, отражательная способность, направление нормали.
D
[0017] Далее выполняется построение Kd-дерева (102) по полученному набору точек. Новая глубокая архитектура (Kd-сеть) работает с Kd-деревьями, построенными для облаков 3D-точек. Kd-дерево строится рекурсивно в нисходящей манере путем выбора координатной оси с наибольшим диапазоном (разбросом) координат точек и разделением множества точек на два подмножества равного размера с последующей рекурсивной работой над ними. В результате порождается сбалансированное Kd-дерево глубины D, содержащее N-1=2-1 нелистовых узлов.
[0018] Каждый нелистовой узел Vi связан с одним из трех направлений разделения di (вдоль оси x, у или z, т.е. di ∈ x, у, z) и с определенной позицией разделения (порогом) τi. Узел дерева также характеризуется уровнем li ∈ {1,…,D-1} с li=1 для корневого узла и li=D для узлов, содержащих отдельные 3D-точки. Предполагается, что узлы в сбалансированном дереве пронумерованы в стандартной нисходящей манере - корневой узел является первым, а i-тый узел имеет потомков с номерами c1 (i) = 2i и с2 (i) = 2i + 1.
[0019] Далее для каждой точки из полученного облака формируется вектор признаков (103) - векторные представления vi, соответствующие каждому узлу дерева. Для листовых узлов эти представления задаются как k-мерные векторы, описывающие отдельные точки, соответствующие данным листьям. Представления, соответствующие нелистовым узлам, вычисляются в восходящей манере.
[0020] Далее выполняется определение (вычисление) векторов признаков узлов дерева (этап 104). Рассмотрим нелистовой узел i уровня l(i) с потомками (дочерними узлами) c1 (i) и c2 (i) на уровне l(i) + 1, для которых уже были вычислены представления vc1 (i) и vc2 (i). Векторное представление vi вычисляется следующим образом:
Или в сокращенной форме выражения (1)
i
i
[0021] Здесь ϕ некоторая нелинейность (например, блок линейной ректификации (ReLU) ϕ(а)=max (а, 0)), а квадратные скобки обозначают конкатенацию. Линейное (аффинное) преобразование в (1) определяется обучаемыми параметрами  слоя l. Таким образом, в зависимости от направления разделения d узла, применяется одно из трех аффинных преобразований с последующим применением простой нелинейности.
1
2
D
l
l+1
l
[0022] Размерность матриц и векторов смещения определяется размерностями m, m,…, m представлений на каждом уровне дерева. Таким образом, матрицы ,  и  на уровне l имеют размерность m×2m, а векторы смещения  размерность m.
[0023] С помощью выражения (1) выполняется рекуррентное вычисление вектора параметров признаков, описывающие нелистовые узлы дерева и каждый вектор параметров вычисляется путем композиции поэлементного нелинейного преобразования и мультипликативного преобразования векторов признаков дочерних узлов с матрицей и свободным членом, определяемыми глубиной узла и направлением разбиения, соответствующим узлу в Kd-дереве.
[0024] Применив преобразования (1) в восходящем порядке, получается представление корня v1 (Т) для тестового образца. К нему также можно применить несколько дополнительных линейных и нелинейных преобразований ("полностью связанные слои"). Линейные классификаторы обучаются, непосредственно используя представление v1 (Т) на входе. В данном случае классифицирующая сеть выводит вектор ненормированных вероятностей класса:
0
0
где W и b - параметры финального линейного многоклассового классификатора.
[0025] С помощью выражения (3) на этапе (105) осуществляется вычисление вектора признаков, описывающий корневой узел дерева, на основании которого с помощью применения линейного или нелинейного финального классификатора, предсказывающего вектор вероятностей отнесения объекта, описываемого облаком точек, к тому или иному семантическому классу.
[0026] Далее рассмотрим более подробно принцип обучения нейросети с помощью архитектуры KD-дерева.
[0027] Для классификации объектов, описываемых облаками точек, на вход нейросети поступает множество размеченных облаков точек, в котором матрицы и свободные члены преобразований на каждом уровне Kd-дерева и для каждого возможного направления разбиения, а также параметры финального классификатора обучаются при помощи алгоритма обратного распространения ошибки.
j
j
j
j
j
j
0
0
[0028] Kd-сеть - это нейронная сеть прямого распространения с обучаемыми параметрами {W, W, W, b, b, b}, где на каждом из D-1 нелистовых узлов j∈{2..D-1} и обучаемыми параметрами {W, b} конечного (финального) классификатора.
0
[0029] Стандартный метод обратного распространения ошибки обучения (backprop) может применяться для вычисления градиента функции потерь относительно параметров сети. Таким образом, параметры сети могут быть получены из набора размеченных Kd-деревьев с использованием стандартных алгоритмов стохастической оптимизации и стандартных функций потерь, таких как перекрестная энтропия на выходе сети v (T) (3).
[0030] Как было указано выше на этапе (105), при определении вектора признаков корневого узла с помощью выражения (3) осуществляется вычисление вектора признаков заданной размерности, который применяется для семантического определения объекта, в частности по схожести форм, что впоследствии используется для поиска схожих объектов с помощью KD-сети.
[0031] Параметры KD-сети могут быть получены с помощью обратного распространения ошибки обучения с использованием любой функции потерь обучения представлений, которая наблюдает примеры сочетающихся (например, принадлежащих одному классу) и несочетающихся (например, принадлежащих разным классам) форм. Для этого может применятся гистограммная функция потерь [32], либо сиамская [5, 8] или триплетная функции потерь [27].
[0032] На Фиг. 2 представлен пример Kd-дерева, построенного на облаке точек, состоящем из восьми точек, и соответствующая Kd-сеть, построенная для классификации на основе дерева.
[0033] Узлы нумеруются в Kd-дереве от корня к листьям. Поэтому листовые узлы, соответствующие исходным точкам, нумеруются, начиная с Р1. Стрелки обозначают поток информации в процессе прямого прохода (вывод). Крайние слева прямоугольники соответствуют листовым представлениям (точек). Крайние справа прямоугольники соответствуют выведенным классовым апостериорным вероятностям v0. Круги соответствуют линейным (аффинным) преобразованиям с обучаемыми параметрами. Цвета кругов обозначают общность параметров, так как группы одного типа (одинаковая ориентация, одинаковый уровень в дереве - три "зеленых" группы в данном примере) имеют общие параметры преобразования.
[0034] На Фиг. 3 представлен пример Kd-деревьев для облаков точек на основе базы MNIST. Визуализация облаков 2D-точек для базы данных MNIST осуществлялось с помощью построенных Kd-деревьев. Тип разбиения кодируется цветом, и для каждого примера под его изображением ниже приведены типы разбиений для первых четырех уровней дерева. Структура Kd-дерева описывает форму (например, для "единиц" преобладают вертикальные разбиения, а "нули" обнаруживают вертикальные и горизонтальные разбиения, т.к. Kd-дерево проходит от корня к листу).
[0035] Kd-дерево, лежащее в основе сети, играет двойную роль в процессе обработки данных Kd-сетью. Во-первых, Kd-дерево определяет, какие листовые представления комбинируются/соединяются и в каком порядке. Во-вторых, структура Kd-дерева может сама по себе рассматриваться как описатель формы, что представлено на Фиг. 2 и, таким образом, служить источником информации, независимо от того, каковы листовые представления. Kd-сеть затем выступает в качестве механизма для извлечения информации о форме, содержащейся в структуре Kd-дерева.
j
j
j
j
j
j
x
y
z
x
y
z
[0036] Подобно сверточным сетям, KD-сети обрабатывают входные данные, применяя к ним ряд параллельных пространственно-локализованных мультипликативных операций, чередующихся с нелинейностями. Важно, что, как в сверточных сетях мультипликативные параметры для локализованных перемножений (ядра свертки) являются общими для различных пространственных положений, так в KD-сетях мультипликативные параметры {W, W, W, b, b, b} являются общими для всех узлов на уровне j дерева.
[0037] Сверточные сети используют восходящую обработку и вычисляют последовательность представлений, которые соответствуют постепенно все большим частям изображений. Процедура иерархична в том смысле, что представление пространственного положения на определенном слое получается из представлений множества окрестных положений на предшествующем слое с помощью линейных и нелинейных операций. Все это воспроизводится и в Kd-сетях, единственное отличие состоит в том, что воспринимающие поля двух различных узлов одного уровня Kd-дерева не пересекаются.
[0038] За счет сформированной архитектуры KD-сети, обученной вышеуказанным способом, осуществляется поиск семантически схожих облаков точек. Работа нейросети заключается в вычислении векторных признаков, описывающих корневые узлы кд-деревьев, построенных по облакам точек, причем семантическая схожесть облаков точек определяется на основании расстояния между упомянутыми векторными признаками. Указанным расстоянием может, например, является Евклидово расстояние, которое определяется про нормированным векторам признаков.
[0039] Далее рассмотрим результаты работы KD-сети для поиска похожих форм и сегментирования частей. Для классификации оценивается несколько вариаций и усечений Kd-сетей.
[0040] В Таблице 1 приведены результаты классификации на контрольных задачах ModelNet. Сравнение точности Kd-сетей (глубины 10 и 15) с передовыми достижениями. Kd-сети превосходят все архитектуры с единичными моделями, но уступают ансамблям VRN.
[0041] В Таблице 2 представлено сравнение Точности классификации для исходных данных и различных дополнений. Итоговые точности для базовой модели, усеченной модели с тривиальными листовыми представлениями, а также для Kd-сетей, обученных с использованием различных дополнений к данным. DT = детерминированные Kd-деревья, RT = рандомизированные Kd-деревья, ТА = добавление сдвига, SA = добавление анизотропного масштабирования. Все сети имеют глубину 10.
[0042] Для классификации 3D-форм используются вариации ModelNet [35] из 10 и 40 классов (ModelNet10 и ModelNet40), содержащие 4899 и 12311 моделей соответственно. Эти наборы данных разделены на обучающий (3991 и 9843 моделей) и тестовый (909 и 2468 моделей соответственно) наборы. В данном случае облака 3D-точек вычислялись следующим образом: сначала заданное число граней выбирается с вероятностью, пропорциональной их площади поверхности. Затем для выбранной грани берется случайная точка. Таким образом, вся процедура отбора близко аппроксимирует равномерную выборку поверхностей модели.
[0043]
СПИСОК ЛИТЕРАТУРЫ
1) Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324, 1998.
2) Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proc. CVPR, pages 1912-1920, 2015.
3) D. Maturana and S. Scherer. Voxnet: A 3d convolutional neural network for real-time object recognition. In Proc. IROS, pages 922-928. IEEE, 2015.
4) A. Brock, T. Lim, J. Ritchie, and N. Weston. Generative and discriminative voxel modeling with convolutional neural networks. arXiv preprint arXiv : 1608.04236, 2016.
5) J.L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975.
6) D.J. Meagher. Octree encoding: A new technique for the representation, manipulation and display of arbitrary 3-d objects by computer. Electrical and Systems Engineering Department Rensseiaer Polytechnic Institute Image Processing Laboratory, 1980.
7) R.A. Schumacker, B. Brand, M.G. Gilliland, and W.H. Sharp. Study for applying computer-generated images to visual simulation. Technical report, DTIC Document, 1969.
8) A. Guttman. R-trees: a dynamic index structure for spatial searching, volume 14. ACM, 1984.
9) A.A. Requicha and H.B. Voelcker. Constructive solid geometry. 1977.