Способ формирования архитектуры нейросети для классификации объекта, заданного в виде облака точек, способ ее применения для обучения нейросети и поиска семантически схожих облаков точек Российский патент 2018 года по МПК G06N3/04 G06N3/08 G06F17/30 

ОБЛАСТЬ ТЕХНИКИ

[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] Заявленный результат достигается за счет способа формирования архитектуры нейросети для классификации объекта, заданного в виде облака точек, при котором:

получают облако точек размера N=2^D, описывающее объект, где D - параметр глубины;

формируют Kd-дерево Т глубины D для полученного облака точек, причем дерево содержит корневой узел, листовые узлы и нелистовые узлы;

генерируют для каждой точки облака вектор признаков, описывающий упомянутую точку;

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

вычисляют вектор признаков, описывающий корневой узел дерева;

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

[0010] В частном варианте осуществления способа вектор признаков содержит 3D-координаты, цвет, или направление нормали.

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

[0012] Еще в одном предпочтительном варианте реализации представлен способ поиска семантически схожих облаков точек с помощью вышеуказанной архитектуры нейросети, обученной вышеупомянутым способом, в которой упомянутая нейросеть применяется для вычисления векторных признаков, описывающих корневые узлы кд-деревьев, построенных по облакам точек, причем семантическая схожесть облаков точек определяется на основании расстояния между упомянутыми векторными признаками.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0013] Фиг. 1 иллюстрирует последовательность этапов формирования структуры Kd-сети.

[0014]

[0015] Фиг. 2 иллюстрирует пример Kd-дерева, построенного на основании облаков точек

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

[0016] На Фиг. 1 представлен процесс формирования архитектуры нейросети для классификации объекта (100). На первом шаге (101) получают входное облако точек размера N=2^D, где D - параметр глубины. Облако точек описывает трехмерный объект. Для полученных точек дополнительно может определяться такие свойства, как: цвет, отражательная способность, направление нормали.

[0017] Далее выполняется построение Kd-дерева (102) по полученному набору точек. Новая глубокая архитектура (Kd-сеть) работает с Kd-деревьями, построенными для облаков 3D-точек. Kd-дерево строится рекурсивно в нисходящей манере путем выбора координатной оси с наибольшим диапазоном (разбросом) координат точек и разделением множества точек на два подмножества равного размера с последующей рекурсивной работой над ними. В результате порождается сбалансированное Kd-дерево глубины D, содержащее N-1=2^D-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)

[0021] Здесь ϕ некоторая нелинейность (например, блок линейной ректификации (ReLU) ϕ(а)=max (а, 0)), а квадратные скобки обозначают конкатенацию. Линейное (аффинное) преобразование в (1) определяется обучаемыми параметрами слоя l_i. Таким образом, в зависимости от направления разделения d_i узла, применяется одно из трех аффинных преобразований с последующим применением простой нелинейности.

[0022] Размерность матриц и векторов смещения определяется размерностями m¹, m²,…, m^D представлений на каждом уровне дерева. Таким образом, матрицы , и на уровне l имеют размерность m^l×2m^l+1, а векторы смещения размерность m^l.

[0023] С помощью выражения (1) выполняется рекуррентное вычисление вектора параметров признаков, описывающие нелистовые узлы дерева и каждый вектор параметров вычисляется путем композиции поэлементного нелинейного преобразования и мультипликативного преобразования векторов признаков дочерних узлов с матрицей и свободным членом, определяемыми глубиной узла и направлением разбиения, соответствующим узлу в Kd-дереве.

[0024] Применив преобразования (1) в восходящем порядке, получается представление корня v1 (Т) для тестового образца. К нему также можно применить несколько дополнительных линейных и нелинейных преобразований ("полностью связанные слои"). Линейные классификаторы обучаются, непосредственно используя представление v1 (Т) на входе. В данном случае классифицирующая сеть выводит вектор ненормированных вероятностей класса:

где W⁰ и b⁰ - параметры финального линейного многоклассового классификатора.

[0025] С помощью выражения (3) на этапе (105) осуществляется вычисление вектора признаков, описывающий корневой узел дерева, на основании которого с помощью применения линейного или нелинейного финального классификатора, предсказывающего вектор вероятностей отнесения объекта, описываемого облаком точек, к тому или иному семантическому классу.

[0026] Далее рассмотрим более подробно принцип обучения нейросети с помощью архитектуры KD-дерева.

[0027] Для классификации объектов, описываемых облаками точек, на вход нейросети поступает множество размеченных облаков точек, в котором матрицы и свободные члены преобразований на каждом уровне Kd-дерева и для каждого возможного направления разбиения, а также параметры финального классификатора обучаются при помощи алгоритма обратного распространения ошибки.

[0028] Kd-сеть - это нейронная сеть прямого распространения с обучаемыми параметрами {W^j, W^j, W^j, b^j, b^j, b^j}, где на каждом из D-1 нелистовых узлов j∈{2..D-1} и обучаемыми параметрами {W⁰, b⁰} конечного (финального) классификатора.

[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-дерева.

[0036] Подобно сверточным сетям, KD-сети обрабатывают входные данные, применяя к ним ряд параллельных пространственно-локализованных мультипликативных операций, чередующихся с нелинейностями. Важно, что, как в сверточных сетях мультипликативные параметры для локализованных перемножений (ядра свертки) являются общими для различных пространственных положений, так в KD-сетях мультипликативные параметры {W^j_x, W^j_y, W^j_z, b^j_x, b^j_y, b^j_z} являются общими для всех узлов на уровне 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.

Изобретение относится к области обработки цифровых данных. Технический результат заключается в повышение скорости поиска схожих объектов по облакам точек. Заявленный результат достигается за счет получения облака точек размера N=2^D, описывающего объект, где D - параметр глубины; формирования kd-дерева Т глубины D для полученного облака точек, причем дерево содержит корневой узел, листовые узлы и нелистовые узлы; генерирования для каждой точки облака вектора признаков, описывающего упомянутую точку; рекуррентного вычисления вектора параметров признаков, описывающих нелистовые узлы дерева, причем каждый вектор параметров вычисляется путем композиции поэлементного нелинейного преобразования и мультипликативного преобразования векторов признаков дочерних узлов с матрицей и свободным членом, определяемыми глубиной узла и направлением разбиения, соответствующим узлу в kd-дереве; вычисляют вектор признаков, описывающий корневой узел дерева; применения к вычисленному вектору признаков линейного или нелинейного финального классификатора, предсказывающего вектор вероятностей отнесения объекта к тому или иному семантическому классу. 3 н. и 1 з.п. ф-лы, 3 ил.

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

- получают облако точек размера N=2^D, описывающее объект, где D - параметр глубины;

- формируют kd-дерево дерево Т глубины D для полученного облака точек, причем дерево содержит корневой узел, листовые узлы и нелистовые узлы;

- генерируют для каждой точки облака вектор признаков, описывающий упомянутую точку;

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

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

2. Способ по п. 1, характеризующийся тем, что вектор признаков содержит 3D-координаты, цвет или направление нормали.

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

4. Способ поиска семантически схожих облаков точек с помощью архитектуры нейросети по п. 1, обученной способом по п. 3, в которой упомянутая нейросеть применяется для вычисления векторных признаков, описывающих корневые узлы kd-деревьев, построенных по облакам точек, причем на основании расстояния между упомянутыми векторными признаками определяют семантическую схожесть облаков точек.