Распознавание 3D объектов на основе спектральных инвариантов с использованием глубокого машинного обучения

УДК 004.93'12 DOI 10.23683/2311-3103-2019-3-20-31

С.П. Левашев

РАСПОЗНАВАНИЕ 3D ОБЪЕКТОВ НА ОСНОВЕ СПЕКТРАЛЬНЫХ ИНВАРИАНТОВ С ИСПОЛЬЗОВАНИЕМ ГЛУБОКОГО МАШИННОГО

ОБУЧЕНИЯ

Предлагается метод распознавания трехмерных объектов с применением глубокого машинного обучения. В вычислительных системах объекты часто представляются 3D моделями в виде совокупности полигонов или поверхностей, описывающих геометрическую форму. Поиск релевантных объектов путем распознавания на основе таких данных без предварительного сжатия является неэффективным. Кроме того, при распознавании на основе попарного сопоставления объектов друг с другом зачастую сложно систематизировать результаты. Предложенный метод распознавания нацелен на решение данных проблем. В распознавании применяются спектральные дескрипторы с использованием характеристик, описывающих различные физические процессы на поверхности. Данные дескрипторы используют спектральное разложение дискретного аналога оператора Лапласа-Бельтрами для объектов, поверхность которых аппроксимирована треугольной сеткой. Каждый из предъявляемых объектов представлен тремя дескрипторами. Предлагается способ сжатия информации о форме объекта, представленной дескрипторами при помощи введенных карт спектральных распределений. Особенность данного способа сжатия состоит в том, что при его использовании: возможно сравнивать объекты различного уровня детализации, ускоряется процесс распознавания, а также сохраняются важные свойства устойчивости к зашумлениям и инвариантности к различным преобразованиям формы, которыми обладают спектральные дескрипторы. Затем выполняется распознавание объектов с применением глубокого машинного обучения, в котором используется сверточная нейронная сеть с несколькими каналами. Входными данными для каждого из каналов нейронной сети являются карты спектральных распределений. Распознавание выполняется путем вычислений в предварительно обученной нейронной сети и последующим определением класса, к которому принадлежит объект. Проведена серия вычислительных экспериментов с применением различных конфигураций спектральных дескрипторов. Результаты экспериментов демонстрируют высокую точность распознавания для трехмерных объектов с различными преобразованиями формы.

Распознавание образов; дескриптор; инвариантность; спектр графа; глубокое машинное обучение.

S.P. Levashev

RECOGNITION OF 3D OBJECTS BASED ON SPECTRAL INVARIANTS USING DEEP MACHINE LEARNING

The paper proposes a method for recognition of three-dimensional objects using deep machine learning. In computing systems, objects are often represented by 3D models as a set of polygons or surfaces describing a geometric shape. Search for relevant objects by recognizing on the basis of such data without compression is ineffective. In addition, when recognizing on the basis of pairwise comparison of objects with each other, it is often difficult to systematize the results. The proposed recognition method is aimed at solving these problems. In recognition, spectral descriptors are applied using characteristics that describe various physical processes on the surface. These descriptors use the spectral decomposition of a discrete analogue of the Laplace-Beltrami operator for objects whose surface is approximated by a triangular grid. Each of the presented objects is represented by three descriptors. A method of compressing information about the shape of an object represented by descriptors using the entered spectral distribution maps is proposed. The peculiarity of this compression method is that when it is used it: is possible to compare objects of different levels of detail, the recognition process is accelerated, and the important properties of resistance to noise and invariance to various form transformations possessed by spectral de-

scriptors are preserved. Object recognition is then performed using deep machine learning, which uses a convolutional neural network with several channels. The input data for each channel of the neural network are maps of spectral distributions. Recognition is performed by computing in a pre-trained neural network and then determining the class to which the object belongs. A series of computational experiments using various configurations of spectral descriptors was carried out. Experimental results demonstrate high recognition accuracy for three-dimensional objects with various shape transformations.

Pattern recognition; descriptor; invariance; spectrum graph; deep machine learning.

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

Дескрипторы, основанные на скелетном представлении, описывают объекты при помощи скелетного утоньшения. Подход с использованием графа Риба [1], задающего структуру взаимного расположения замкнутых контуров на поверхности объекта, применяется авторами в [2]. В методе [3] предлагается описывать объект при помощи скелетных графов, ребра которых являются геометрическими множествами центров вписанных внутрь объекта сфер. Другие подходы связаны с применением медиальных поверхностей [4-6] в виде совокупности приближенных к скелету объекта полигонов. Методы, основанные на скелетном представлении инвариантны к изометрическим преобразованиям и потере небольшой части данных, однако не всегда устойчивы к зашумлениям.

Дескрипторы, связанные с поверхностным описанием, включают в себя признаки, вычисленные на поверхности объекта. В последнее время интенсивно развиваются методы, связанные со спектральным разложением [8] : матрицы Лапласа [7] и матрицы Лапласа-Бельтрами [9]. В [10] было показано, что спектральное разложение матрицы Лапласа-Бельтрами обладает рядом замечательных свойств. Наиболее высокие результаты в последнее время продемонстрировали дескрипторы с использованием спектрального разложения оператора Лапласа-Бельтрами, содержащие информацию о форме объекта, полученную при помощи числовых характеристик, описывающих физические процессы на поверхности. Дескриптор теплопроводности Heat Kernel Signature (HKS) [11] состоит из значений решения уравнения теплопроводности в точках на поверхности объекта в различные моменты времени. Волновой дескриптор Wave Kernel Signature (WKS) [12] основывается на решении уравнения Шредингера. Его особенность состоит в том, что точки на поверхности рассматриваются как кванты, а значениями WKS являются вероятности состояния квантов при воздействии различными значениями энергии. Вейвлет-дескриптор, основанный на спектральном вейвлет-преобразовании на графе Spectral Graph Wavelet Transform (SGWT) [13] состоит из значений сверток собственных значений Лапласа-Бельтрами с высокочастотными и низкочастотными вейвлетными функциями в точках на поверхности объекта в различные моменты времени.

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

Рис. 1. Пример треугольной сетки объекта.

Пусть поверхность рассматриваемого объекта в пространстве М3 аппроксимирована треугольной сеткой ^ = (Р, Т), в которой Р = {р - множество точек-

вершин с декартовыми координатами р. = (х1.у;.г,) еК3,а Т = {/(} - множество треугольников, с элементами в виде упорядоченных троек индексов точек-вершин = , , ) . Будем говорить, что две вершины р и р . являются

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

Дискретный оператор Лапласа-Бельтрами. Оператор Лапласа-Бельтрами имеет немаловажное значение в дифференциальной геометрии [18, 19]. Его дискретные аналоги нашли применение во многих задачах описания и обработки поверхностей: сегментация, реконструкция, поиск симметрии, распознавание и т.п. Оператор Лапласа-Бельтрами А1В, действующий на непрерывную дважды дифференцируемую функцию определяется как дивергенция div от градиента grad этой функции Д / = &у(§гш!(/)). В трехмерном пространстве А1В имеет важный физический смысл. Уравнение диффузии, описывающее процесс переноса вещества или иных объектов в трехмерном пространстве, использует оператор Лапласа-Бельтрами.

В нашем случае функция (: Р —» К. является дискретной и определенной на

множестве вершин Р сетки $ . Таким образом, рассмотрим дискретную аппроксимацию оператора Лапласа-Бельтрами. Дискретизация [20] вместе с модификацией [21] лучшим образом сохраняет важные свойства непрерывного оператора: симметричность и положительную определенность. Опишем данные методы дискретизации.

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

Для каждой из точек р обозначим через N (р¿) множество точек-соседей, при этом р с точками-соседями соединяется отрезком без промежуточных точек. Точка р является центром области Вороного в виде многоугольника (см. рис. 2). Вершины полученного многоугольника, согласно триангуляции, являются центрами описанных около треугольников окружностей. Для треугольной сетки $ дискретный оператор Лапласа-Бельтрами определяется как сумма по всем соседям из N ( р г) , деленная на вес при вершине а :

^ьв/(рг) = 1 I ^ (/(рг) -/(р])),

а р, ^

в которой wjj - вес ребра, соединяющего вершины р и р..

Зачастую треугольная сетка $ не является регулярной. Следовательно, коэффициенты и а необходимо задавать такими, чтобы дискретный оператор Лапласа-Бельтрами как можно меньше зависел от степени регулярности сетки. В дискретизации [20] показано, что таким свойством для обладают котангенс-

ctg а.. + ctgД] - -веса ж.. =----, где а - угол между отрезками рр и РР, в кото] 2 ] ] ] ]

рых р- — точка-сосед р слева от отрезка рр;, а ( - угол между отрезками

р+ р и р+ р , в которых р+ - точка-сосед р, справа от рр; .

Также в дискретизации [20] показано, что коэффициент усреднения следует задавать как а = I а- + а+ - площадь области Вороного с центром в точке р и и ^^^ и и

^еМ

с вершинами в точках = М(р)|. Точка рт1.= (р1,+р.)/2 -сере-

дина отрезкарр,. В модификации [21] было показано, что площадь области Во-

роного a можно найти тоже с использованием котангенсов:

_ ctg «j. + <Agßij\\ ..2

a = Ъ -Ö-h — PA •

P, eN(p,) 8

Спектр Лапласа-Бельтрами. Для получения спектрального разложения строится матрица Лапласа-Бельтрами. Рассмотрим матрицу W, элементы w^ которой являются котангенсными весами, определенными выше. Размерность W будет равна N X N. Пусть D — диагональная матрица с элементами D = Ъ w .

и ij

Сформируем диагональную матрицу А = diag(al3a2,.. -,aN) из значений ai., i = 1,..., N. Тогда матрица Лапласа-Бельтрами LB представляется как L = A- (D — W) . Элементы LB (i, j) будут задаваться следующим образом:

♦ LB (i, j) = w / a , если p и p. смежны;

♦ lb j) = a—1ъ wj, если z' = j;

i * j

♦ LB (i, j) = 0, если p и p . не смежны.

Спектральное разложение LB = ФЛФГ полученной матрицы является спектральным разложением оператора Лапласа-Бельтрами. Оно включает в себя диагональную матрицу собственных значений А = diag( Л,, Я2,..Av) и матрицу

А = (^ Ф2  ф-;) и! собственных векторов-столбцов. Как показано в [7],

наибольшую информацию о геометрической форме объекта несут первые П < N собственных значений, упорядоченные по невозрастанию0 < Л^ < Л2 < ...< Лп .

Число n можно интерпретировать как степень детализации описания объекта при помощи спектрального разложения.

Спектральные дескрипторы. Дескриптор теплопроводности (HKS) [11], волновой дескриптор (WKS) [12] и вейвлет-дескриптор (SGWT) [13] используют спектральное разложение дискретного оператора Лапласа-Бельтрами и описывают форму объектов при помощи моделирования распространения следующих характеристик соответственно: тепла, волнового воздействия и импульсного сигнала. В [11-13] показано, что указанные дескрипторы по сравнению с дескриптором, использующим только спектр оператора Лапласа-Бельтрами [7, 10], более устойчивы к изометрическим преобразованиям и способны передавать больше информации о форме объекта. Применение трех дескрипторов обусловлено тем, что существуют изменения формы объектов, не сохраняющее расстояние между точками, для которых использование одного из указанных дескрипторов позволяет распознавать объекты более точно, чем использование остальных.

1. Дескриптор теплопроводности HKS фиксирует информацию о рассеивании тепла на поверхности объекта с течением времени. Дескриптор HKS основывается на экспоненциальном ядре функции-решении уравнения теплопроводности и определяется как матрица, элементами которой для точек р е i5 в различные моменты времени t = /mm,... 1тах для первых fl собственных векторов и собственных значений дискретного оператора Лапласа-Бельтрами являются:

HKS(p, t) = £ в^'ф2 (p), Vp e P.

k=1

В силу присутствия экспоненты рассматривается логарифмическое время: t = log т, т = Т  ,...Т

о > * min? max

2. В волновом дескрипторе WKS, точка p на поверхности рассматривается как волна-квант. Основная идея построения дескриптора заключается в том, что информация о форме объекта описывается колебаниями каждой из точек-квантов при воздействии различными уровнями энергии. Также в отличие от HKS дескриптор WKS строится на основе другого дифференциального уравнения Шредин-гера. Дескриптор WKS для первых n собственных значений Я и собственных векторов ф дискретного оператора Лапласа-Бельтрами определяется следующим образом:

, n (в-ЬЯ )2

WKS( p, в) = -— £ в 2-2 ф2^), Vp e P,

где ¿j(e) = £ e 2°2 — нормировочный коэффициент, обеспечивающий инвари-

k =1

антность к масштабированию и к небольшим преобразованиям, а

е = In £, £ = omm,..., £тях — логарифмическая энергия (в силу экспоненты).

3. В отличие от HKS и WKS вейвлет-дескриптор SGWT использует не фундаментальные решения дифференциальных уравнений, а основывается на свертках высокочастотных и низкочастотных вейвлет-ядер с преобразованием Фурье некоторого сигнала, воздействующего на поверхность объекта. Данный дескриптор позволяет более точно описывать небольшие части поверхности основывается на

высокочастотной функции Fh и низкочастотной F.

Функция Fh использует высокочастотное финитное вейвлет-ядро g , в котором g (0) = 0, lim g (x) = 0:

x^w

n

Fh{p,t) = YJg{tXkyj>l{p\ VpeP, t = t]mn,...tm^.

k=1

В качестве высокочастотного вейвлет-ядра g в [13] предлагается рассматривать финитный сплайн:

x, x < 1

g (x) =

-5 + 11x - 6x2 + x3,1 < x < 2. 2 x_1, x > 2

Низкочастотная вейвлет-функция Fl использует низкочастотное вейвлет-ядро h, удовлетворяющее условиям: g(0) > 0, lim g(x) = 0:

x^w

n

F: (p) = £ h(Яk ^2(p), Vp e P.

(e-ln Як )2

n

к=1

В качестве низкочастотного вейвлет-ядра может рассматриваться обратная

экспонента 4-й степени h(x) = ye °'бЛтш1 где у — значение минимума функции g ( x) на промежутке [ x; x2 ].

Дескриптор на основе SGWT для треугольной сетки S определяется как набор значений F и F :

SGWT(p,t) = [Fh(p, t))t=^ ^{Fl (p)}, Vp e P.

Карты спектральных распределений. Данные, представленные дескрипторами являются разреженными и имеют различную размерность в зависимости от количества точек объектов. Предложим следующий способ сжатия данных, представленных дескрипторами. Будем рассматривать не совокупность значений дескрипторов в каждой из точек с течением времени или энергии, а распределение значений дескрипторов по всем точкам в указанные моменты времени или энергии. Для сжатия данных о геометрии объекта, определяемых дескрипторами HKS, WKS и SGWT введем матрицы размерности ND х ND—DH , D и Ds соответственно. Данные матрицы назовем картами спектральных распределений. Эти карты состоят из векторов-столбцов распределения значений дескрипторов в определенный момент времени или энергии.

Обозначим через d^ вектор-столбец, представляющий собой распределение значений HKS в момент времени т. по всем вершинам p e P . Тогда структура карты DH будет определяться следующим образом:

DH=(d% ...

Аналогичным образом определим структуру матрицы Dw :

— ... d^ D ).

Поскольку в вейвлет-дескрипторе SGWT добавляется низкочастотная информация о форме объектов, то для сохранения размерности ND х ND определим

структуру матрицы Ds в виде первых ND — 1 векторов-столбцов распределений по времени dtls , i = 1,...,ND — 1 высокочастотной функции Fh и присоединенным вектором-столбцом d l , описывающим распределение значений низкочастотной функции F :

Ds={d^ ... d^ d's).

Сверточная нейронная сеть. В последнее время особую популярность получили так называемые сверточные нейронные сети, впервые представленные авторами в [14] для распознавания рукописных цифр. Рост применения сетей данного типа связан с победой сети AlexNet [15] для классификации 2D изображений на международном конкурсе ImageNet в 2012 году. Успех применения сверточных нейронных сетей к задачам классификации изображений обеспечивает возможность их применения к другим задачам и типам данных. В нашей работе предлагается использовать архитектуру сверточной нейронной сети для классификации 3D объектов.

4

Построим архитектуру, состоящую из ^оя входных данных (Input data), двух последовательно расположенных сверточных блоков (Convolutional Ывск)и полносвязного слоя (Full layer) (рис. 3).

Рис. 3. Архитектура сверточной нейронной сети для классификации трехмерных

объектов

Входными данными для сети является объект, представленный тремя картами спектральных распределений Он , Ош и . Каждая карта подается на свою

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

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

Рис. 4. Основные этапы предложенного метода распознавания

1. Вычисление спектра Лапласа-Бельтрами. На основе входных данных предъявляемого объекта, заданного поверхностью S со множеством вершин P и треугольников T вычислить коэффициенты a и w^ и построить матрицу .

Затем вычислить собственные значения Я и собственные векторы ф матрицы .

2. Построение карт спектрального распределения. По найденным Я и ф вычислить значения дескрипторов HKS, WKS и SGWT для всех точек p е P и, соответственно, для всех заданных значений х, e и t. Затем вычислить карты спектральных распределений DH , Dw и Ds .

3. Распознавание сверточной нейронной сетью. Выполняются вычисления, связанные с прохождением каждой из карт DH , Dw и Ds по каналам предварительно обученной сверточной сети.

Эксперименты. Реализация представленного метода распознавания проводилась на двух датасетах, которые включали в себя 457 трехмерных объектов из базы McGill Database [22]. Количество вершин каждого из объектов менялось в диапазоне от 5 до 40 тысяч точек, количество треугольников - от 10 до 80 тысяч. В первом датасете содержались объекты 10 классов с артикуляцией: в каждом из классов один и тот же объект подвергался изометрическим преобразованиям (рис. 5,a). Во втором классе - объекты 9 классов без артикуляции, с присутствием различающихся по форме объектов (рис. 5,б). Каждый из датасетов разделялся на обучающую и тестовую выборки в примерном соотношении 3 к 1 соответственно.

глг

В Humane ' Octopuses pliers

о* г

Snakes Spectacle.

т

б

Рис. 5. Визуализация объектов из датасетов с указанием классов (из каждого класса выбрано по три объекта): а - с артикуляцией, б - без артикуляции, с присутствием различающихся объектов

При вычислении спектральных дескрипторов использовались первые n = 300 собственных значений и векторов дискретного оператора Лапласа-Бельтрами. Диапазон значений времени в дескрипторе теплопроводности в зависимости от каждого объекта: от = 4ln10/ Я до г = 4ln10/ Я, энергии в

волновом дескрипторе: от emn = 4 ln smn + 2а до emax = 4 ln ^max - 2a, a = 0.5 ,

времени в вейвлет-дескрипторе: от = 2/ Хп до = 2/ Я . Размерность для

всех карт спектральных распределений была равной ND = 132.

Реализована введенная выше сверточная нейронная сеть для классификации объектов. Для каждого из трех каналов оптимальное количество сверточных ядер для первого блока было выбрано 48, для второго 96. Функция активации во всех сверточных блоках - ReLU, на первом слое полносвязной сети - sigmoid, на последнем - softmax. Нейронная сеть минимизировала функцию потерь перекрестной энтропии. Для ускорения обучения использовалась батч-нормализация входного слоя. Для защиты от переобучения применялось dropout-прореживание полносвязного слоя с вероятностью 0.5. Веса нейронной сети обновлялись с использованием адаптивного обучения nadam.

Объективная оценка качества распознавания основывалась на использовании трех критериев, вычисляемых по тестовой выборке: Precision (точность), Recall (полнота), а также их взвешенное среднее гармоническое, так называемая, Fscore-мера.

a

Таблица 1

Значения критериев качества в зависимости от используемых карт спектральных распределений

Dataset 1 Dataset 2

Input Precision Recall Fscore Accuracy Precision Recall Fscore Accuracy

DH 0.9451 0.9348 0.9334 0.9348 0.8088 0.7638 0.7737 0.7857

Dw 0.8949 0.8696 0.8663 0.8696 0.8310 0.8194 0.8214 0.8252

Ds 0.9178 0.8982 0.8971 0.8982 0.8696 0.8333 0.8456 0.8511

All 0.9744 0.9710 0.9706 0.9710 0.9143 0.8889 0.9011 0.9014

Для первого и второго датасетов использование всех трех карт спектральных распределений DH , Dw и Ds позволяет получить более высокую точность, чем

использование одной из карт (табл. 1). Также можно заметить, что DH , соответствующая дескриптору теплопроводности лучше справляется с датасетом с артикуляцией. Вместе с этим, со вторым датасетом лучше справляются карты Dw и D5 .

Распознавание объектов на первом датасете оказалось более точным, поскольку в нем имеются пары классов, в которых объекты имеют настолько высокое сходство, что их можно было бы объединить в один класс, например пары клас-сов:airplanes и birds, dolphins и fishes, four-limbs и dinosaurs на рис. 5,б). Тем не менее, во втором датасете также демонстрируется достаточно высокая точность, что подтверждает эффективность предлагаемого подхода.

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

БИБЛИОГРАФИЧЕСКИМ СПИСОК

1. Reeb G. Sur les points singuliers dune forme de Pfaff complitement integrable ou dune function numerique [On the Singular Points of a Completely Integrable Pfaff Form or of a Numerical Function] // Comptes Rendus Acad. Sciences. - Paris, France, 1946. - Vol. 222. - P. 847-849.

2. WaleedM., Ben Hamza A. Reeb graph path dissimilarity for 3D object matching and retrieval // The Visual Computer. - Springer, 2012. - Vol. 28. - P. 305-318.

3. Macrini D., Siddiqi K., Dickinson S. From Skeletons to Bone Graphs: Medial Abstraction for Object Recognition // 26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR. - Anchorage, Alaska, USA, 2008. - P. 1-8.

4. Ringler T., Randall D. A Potential Enstrophy and Energy Conserving Numerical Scheme for Solution of the Shallow-Water Equations on a Geodesic Grid // American Meteorological Society. - 2002. - Vol. 130. - P. 1397-1410.

5. Chuang J., Tsai C., Ko M. Skeletonization of three-dimensional object using generalized potential field // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2000.

- Vol. 22 (11). - P. 1241-1251.

6. Местецкий Л.М., Зимовнов А.В. Построение криволинейного скелета трехмерной модели по плоским проекциям // Вестник ТвГУ. Серия: Прикладная математика. - 2016.

- № 3. - C. 67-83.

7. Varun J., Zhang H. A spectral approach to shape-based retrieval of articulated 3D models // Computer-Aided Design. - 2007. - Vol. 39 (5). - P. 398-407.

8. Chung F.R.K, Spectral graph theory // American Mathematical Society. - 1997.

9. Reuter M., Wolter F.-E., Peinecke N. Laplace-spectra as fingerprints for shape matching // Proceedings of the Ninth ACM Symposium on Solid and Physical Modeling. - Cambridge, Massachusetts, USA, 2005. - P. 101-106.

10. Rustamov M. Laplace-Beltrami eigenfunctions for deformation invariant shape representation // Proceedings of symposium on geometry processing. - Barcelona, Spain, 2007. - P. 225-233.

11. Sun J., Ovsjanikov M., Guibas L.J. A concise and provably informative multi-scale signature based on heat diffusion // Comput. Graph. Forum. - 2009. - Vol. 28 (5). - P. 1383-1392.

12. Aubry M., Schlickewei U., Cremers D.The wave kernel signature: a quantum mechanical approach to shape analysis // IEEE International Conference on Computer Vision Workshops, ICCV. - Barcelona, Spain, 2011. - P. 1626-1633.

13. HammondD.K., VandergheynstP., GribonvalR. Wavelets on graphs via spectral graph theory // Applied and Computational Harmonic Analysis. - 2011. - Vol. 30 (2). - P. 129-150.

14. LeCun Y., Bottou L., Bengio Y., Hafner P. Gradient-based learning applied to document recognition // Proceedings of the IEEE. - 1999. - Vol. 86 (11). - P. 2278-2324.

15. KrizhevskyA., Sutskever I., Hinton G.E. ImageNet classification with deep convolutional neural networks // NIPS'12 Proceedings of the 25th International Conference on Neural Information Processing Systems. - Lake Tahoe, USA, 2012. - P. 1097-1105.

16. SitnikR., Karaszewski M. Optimized point cloud triangulation for 3D scanning systems // Machine Graphics and Vision. - 2008. - Vol. 17 (4). - P. 349-371.

17. Kobbelt L.P., Botsch M. An Interactive Approach to Point Cloud Triangulation // Computer Graphics Forum. - 2000. - Vol. 19 (3). - P. 479-487.

18. Курант Р., Гильберт Д. Методы математической физики. Т. 2. - М.: Изд-во "Мир", 1951. - 1020 c.

19. Chavel I. Riemannian Geometry: A Modern Introduction // Cambridge University Press, Cambridge, 2006. - Vol. 98. - P. 471.

20. Meyer M., Desbrun M., Schroder P., Barr A.Discrete differential geometry operators for triangulated 2-manifolds // In Proceedings of Visual Mathematics. - 2002. - P. 35-57.

21. Xu G. Discrete Laplace-Beltrami operator on sphere and optimal spherical triangulations // Int. J. Comput. Geometry Appl. - 2006. - Vol. 16 (1). - P. 75-93.

22. McGill DATABASE. - URL: www.cim.mcgill.ca/~shape/benchMark/.

REFERENCES

1. Reeb G. Sur les points singuliers dune forme de Pfaff complitement integrable ou dune function numerique [On the Singular Points of a Completely Integrable Pfaff Form or of a Numerical Function], Comptes Rendus Acad. Sciences. Paris, France, 1946, Vol. 222, pp. 847-849.

2. WaleedM., Ben Hamza A. Reeb graph path dissimilarity for 3D object matching and retrieval, The Visual Computer. Springer, 2012, Vol. 28, pp. 305-318.

3. Macrini D., Siddiqi K., Dickinson S. From Skeletons to Bone Graphs: Medial Abstraction for Object Recognition, 26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR. Anchorage, Alaska, USA, 2008, pp. 1-8.

4. Ringler T., Randall D. A Potential Enstrophy and Energy Conserving Numerical Scheme for Solution of the Shallow-Water Equations on a Geodesic Grid, American Meteorological Society, 2002, Vol. 130, pp. 1397-1410.

5. Chuang J., Tsai C., Ko M. Skeletonization of three-dimensional object using generalized potential field, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, Vol. 22 (11), pp. 1241-1251.

6. Mestetskiy L.M., Zimovnov A.V. Postroenie krivolineynogo skeleta trekhmernoy modeli po ploskim proektsiyam [Construction of a curvilinear skeleton of a three-dimensional model on flat projections], Vestnik TvGU. Seriya: Prikladnaya matematika [Herald of Tver State University. Series: Applied Mathematics], 2016, No. 3, pp. 67-83.

7. Varun J., Zhang H. A spectral approach to shape-based retrieval of articulated 3D models, Computer-Aided Design, 2007, Vol. 39 (5), pp. 398-407.

8. Chung F.R.K, Spectral graph theory // American Mathematical Society, 1997.

9. ReuterM., Wolter F.-E., Peinecke N. Laplace-spectra as fingerprints for shape matching, Proceedings of the Ninth ACM Symposium on Solid and Physical Modeling. Cambridge, Massachusetts, USA, 2005, pp. 101-106.

10. RustamovM. Laplace-Beltrami eigenfunctions for deformation invariant shape representation, Proceedings of symposium on geometry processing. Barcelona, Spain, 2007, pp. 225-233.

11. Sun J., Ovsjanikov M., Guibas L.J. A concise and provably informative multi-scale signature based on heat diffusion, Comput. Graph. Forum., 2009, Vol. 28 (5), pp. 1383-1392.

12. Aubry M., Schlickewei U., Cremers D.The wave kernel signature: a quantum mechanical approach to shape analysis, IEEE International Conference on Computer Vision Workshops, ICCV. Barcelona, Spain, 2011, pp. 1626-1633.

13. HammondD.K., VandergheynstP., GribonvalR. Wavelets on graphs via spectral graph theory, Applied and Computational Harmonic Analysis, 2011, Vol. 30 (2), pp. 129-150.

14. LeCun Y., Bottou L., Bengio Y., Haffner P. Gradient-based learning applied to document recognition, Proceedings of the IEEE, 1999, Vol. 86 (11), pp. 2278-2324.

15. KrizhevskyA., Sutskever I., Hinton G.E. ImageNet classification with deep convolutional neural networks, NIPS'12 Proceedings of the 25th International Conference on Neural Information Processing Systems. Lake Tahoe, USA, 2012, pp. 1097-1105.

16. Sitnik R., Karaszewski M. Optimized point cloud triangulation for 3D scanning systems, Machine Graphics and Vision, 2008, Vol. 17 (4), pp. 349-371.

17. Kobbelt L.P., Botsch M. An Interactive Approach to Point Cloud Triangulation, Computer Graphics Forum, 2000, Vol. 19 (3), pp. 479-487.

18. KurantR., Gil'bertD. Metody matematicheskoy fiziki [Methods of mathematical physics]. Vol. 2. Moscow: Izd-vo "Mir", 1951, 1020 p.

19. Chavel I. Riemannian Geometry: A Modern Introduction, Cambridge University Press, Cambridge, 2006, Vol. 98, pp. 471.

20. Meyer M., Desbrun M., Schroder P., Barr A.Discrete differential geometry operators for triangulated 2-manifolds, In Proceedings of Visual Mathematics, 2002, pp. 35-57.

21. Xu G. Discrete Laplace-Beltrami operator on sphere and optimal spherical triangulations, Int. J. Comput. GeometryAppl., 2006, Vol. 16 (1), pp. 75-93.

22. McGill DATABASE. Available at: www.cim.mcgill.ca/~shape/benchMark/.

Статью рекомендовал к опубликованию д.ф.-м.н., профессор А.Н. Каркищенко.

Левашев Сергей Петрович - Южный федеральный университет; e-mail:

serzh.levashev@yandex.ru; 347928, г. Таганрог, ул. Чехова, 22; аспирант.

Levashev Sergey Petrovich - Southern Federal University; e-mail: serzh.levashev@yandex.ru;

22, Chekhova street, Taganrog, 347928, Russia; graduate student.