Разработка и исследование методов сегментации и распознавания трехмерных объектов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Левашев Сергей Петрович

• Левашев Сергей Петрович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Левашев Сергей Петрович

Введение

1. Разработка и исследование методов сегментации объектов

по трехмерным лазерным данным

1.1. Получение данных лазерного сканирования

1.2. Метод предварительной регуляризации данных для сегментации

1.3. Метод семантической сегментации

1.3.1. Этапы выделения семантических классов

1.3.2. Алгоритм семантической сегментации

1.4. Метод сегментации на основе интенсивностей сканирования

1.4.1. Построение и сопоставление гистограмм распределения интенсивностей

1.4.2. Трехмерная фильтрация интенсивностей

1.4.3. Выделение объектов

1.4.4. Алгоритм сегментации с использованием интенсивностей

1.5. Результаты экспериментов

1.5.1. Наборы данных, детали реализации

1.5.2. Семантическая сегментация

1.5.3. Сегментация с использованием интенсивностей

1.6. Выводы

2. Разработка и исследование метода вычисления параметров сегментации

2.1. Постановка задач минимизации для вычисления параметров сегментации

2.2. Построение графа пересечений для оценки объема покрытия области сканирования

2.3. Оценивание объема покрытия на основе аппроксимации Монте-Карло

2.3.1. Алгоритм оценивания

2.3.2. Вычисление необходимого количества генерируемых

точек для аппроксимации

2.4. Вычисление параметров сегментации

2.4.1. Вычисление параметров оценивания объема покрытия

2.4.2. Исследование зависимости объема покрытия

от параметров сегментации и результаты экспериментов

2.5. Дополнительный критерий для вычисления параметров сегментации и результаты экспериментов

2.6. Выводы

3. Разработка и исследование методов распознавания объектов

по трехмерным лазерным данным на основе инвариантов

3.1. Метод распознавания на основе алгебраических инвариантов

3.1.1. Предварительная регуляризация данных

3.1.2. Дескрипторы на основе алгебраических инвариантов

3.2. Метод распознавания на основе спектральных и топологических инвариантов

3.2.1. Вычисление характеристик трехмерных лазерных данных

3.2.2. Построение взвешенного графа структуры объектов

3.2.3. Формирование комплексной матрицы смежности

3.2.4. Вычисление спектрального разложения

3.2.5. Дескрипторы на основе спектральных инвариантов

3.2.6. Дескрипторы на основе топологических инвариантов

3.2.7. Алгоритм распознавания

3.3. Эксперименты

3.3.1. Наборы данных

3.3.2. Распознавание на основе алгебраических инвариантов

3.3.3. Распознавание на основе спектральных и топологических инвариантов

3.4. Выводы

4. Разработка и исследование метода распознавания по

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

4.1. Вычисление спектральных инвариантов для данных в виде треугольных сеток

4.1.1. Непрерывный оператор Лапласа-Бельтрами

4.1.2. Дискретный оператор Лапласа-Бельтрами

4.1.3. Спектральное разложение оператора Лапласа-Бельтрами

4.2. Построение дескрипторов объектов на основе спектральных инвариантов

4.2.1. Дескриптор теплопроводности

4.2.2. Волновой дескриптор

4.2.3. Вейвлет-дескриптор

4.2.4. Построение сжатых дескрипторов в виде карт спектральных распределений

4.3. Агрегация дескрипторов на основе сверточной нейронной сети

4.3.1. Архитектура сети

4.3.2. Методики улучшения качества машинного обучения

4.4. Алгоритм распознавания

4.5. Результаты экспериментов

4.5.1. Детали реализации

4.5.2. Результаты

4.6. Выводы

Заключение

Список литературы

Приложение Л. Вычисление коэффициентов дискретного

оператора Лапласа-Бельтрами

Приложение В. Вычисления в сверточной нейронной сети

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов сегментации и распознавания трехмерных объектов»

Введение

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

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

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

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

Распознавание объектов по трехмерным данным — гораздо менее изученная область по сравнению с распознаванием по двумерным данным. Исследования в области сегментации и распознавания трехмерных объектов в основном начаты относительно недавно. Однако в последнее время имеются многочисленные примеры эффективных методов сегментации и распознавания трехмерных объектов. Перечислим основные из них.

Большое количество алгоритмов сегментации связано с нахождением геометрических признаков в облаке точек. В качестве таких признаков чаще всего выбираются параметры геометрических примитивов (линий, плоскостей, окружностей, сфер и т.п.). В работах [1,2] используется 3-Э преобразование Хафа [3] для сегментации и реконструкции плоских поверхностей в облаке точек. При помощи 3-Э преобразования Хафа определяется принадлежность точек к прямым в пространстве. Затем выполняется поиск замкнутых ломаных, образованных найденными прямыми. Замкнутые ломаные впоследствии объединяются в сегменты, которые образуют части плоских поверхностей.

В силу особенностей лазерного сканирования, облако точек часто содержит зашумления, которые представляют собой отклонения координат точек от сканируемой поверхности. Отклонения вызваны естественными причинами, например, такими как: колебания лазера, особенность сканируемой поверхности и т.п. Устойчивое к зашумлениям определение геометрических примитивов в массиве лазерных данных представлено алгоритмом RANSAC (RANdom SAmple Consensus) [4]. Зачастую поиск геометрических признаков связан с определением координат векторов нормалей к сканируемым поверхностям и последующей их обработкой. Применение RANSAC с использованием нормалей в локальных окрестностях точек для сегментации поверхностей крыш зданий описывается в [5]. Метод выделения фасадов зданий, более устойчивый к зашумлениям, предлагается авторами в [6], при этом также используется широко известный метод главных компонент PCA (Principal Component Analysis). Помимо объектов инфраструктуры часто ставится задача о выделении других классов объектов, например, таких, как деревья. В [7] представлено выделение деревьев при помощи линейного, плоскостного и объемного дескрипторов, вычисленных по методу PCA, описывающих формы поверхностей вокруг каждой из точек. С помощью морфологических фильтров точки объединяются в кластеры, описывающие деревья. Иной подход на основе вычисления вероятностей принадлежности точек деревьям, а также использования плотностей точек в окрестностях, представлен в [8].

В последнее время эффективно применяется машинное обучение при сегментации лазерных данных. В [9] предлагается метод, основанный на структуре неявных форм, которая позволяет выделять объекты на основе голосования с использованием признаков спин-изображений [10]. Сегментация лазерных данных с использованием неассоциативных марковских сетей предлагается в [11]. Облако точек разбивается на множества-воксели, в которых выделяются геометрические признаки. Над вокселями строится марковская сеть, на основе которой происходит обучение и классификация. Часто используются подходы с построением условных случайных полей CRF (Conditional Random Fields)

[12], представляющих собой модели с использованием графов для представления совместных распределений набора нескольких случайных переменных. Выделение групп объектов железнодорожной инфраструктуры c использованием CRF по морфологическим признакам предлагается в [13]. По лазерным данным строится граф, представляющий CRF, в котором задаются веса на основе пространственных признаков. Сегментация осуществляется при помощи GMM-EM классификатора [15], который строит гауссовскую модель смеси случайных распределений (Gaussian Mixture Model) и выполняет последующую оптимизацию (Expectation Maximization).

Современные технологии мобильного лазерного сканирования позволяют получать дополнительные характеристики, которые могут быть использованы для более эффективной обработки данных. Одними из таких характеристик являются значения интенсивностей отраженных импульсов лазерных лучей. Значения интенсивностей зависят как от особенностей сканирования (например, дальность излучения, отражательная способность объектов), так и от состояния окружающей среды (например, время года, погодные условия). Метод сегментации лазерных данных с вычислением изменений значений интенсивностей в локальных окрестностях точек приведен в [14]. Авторами рассматривается задача об определении принадлежности точек одному из четырех классов: ледников, снега, фирна и границ между ледниками. Вычисляются изменения значений интенсивностей для локальных окрестностей каждой из точек, а также векторы нормалей. Точки со значениями перепадов интенсивностей и углов между нормалями в пределах пороговых значений объединяются в сегменты при помощи диаграмм Вороного. Результаты экспериментов показали высокую точность предлагаемого метода. Для обработки лазерных данных часто используются цифровые модели облаков точек, которые представляют собой проекции трехмерных точек на плоскость с заполнением пустот точками со значениями интенсивностей ближайших соседей. Алгоритм выделения объектов по данным интенсивностей с использованием растровых моделей предлагается в [16].

Метод сегментации основан на определении принадлежности интенсивностей точек указанным диапазонам с использованием классификатора максимального правдободобия MLC (Maximum Likelihood Classification) и последующего преобразования точек в растровое изображение. Вычисления на основе описанного выше продемонстрировали меньшую точность классификации, чем в [15].

При сегментации данных на основе значений интенсивностей эффективно применяются вероятностные характеристики. В частности, в [17] предлагается метод классификации наземных и неназемных точек с использованием вероятностных моментов третьго и четвертого порядков, представляющих собой коэффициенты асимметрии и эксцесса. Для ближайших соседей каждой из точек вычисляются коэффициент асимметрии, характеризующий асимметричность распределения интенсивностей и коэффициент эксцесса, демонстрирующий меру остроты пика распределения интенсивностей точек. При вычислениях авторами применяются различные цифровые модели лазерных данных, которые часто используются на практике: цифровая модель рельефа DTM (Digital Terrain Model), построенная из наземных точек, цифровая модель поверхности DSM (Digital Surface Model), полученная из точек с максимальными значениями высот в сетках, разбивающих область сканирования и модель, полученная отделением точек DTM от DSM, которая называется моделью высоты навеса CHM (Canopy Height Model). Максимальные значения коэффициентов асимметрий и эксцесса интенсивностей в цифровых моделях в описанном авторами методе указывают на необходимость разделения точек. Результаты экспериментов продемонстрировали эффективность метода, однако при этом вычисления занимают продолжительное время.

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

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

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

Дескрипторы, основанные на скелетном представлении, описывают объекты при помощи скелетного утоньшения. Подход с использованием графа Риба [18], задающего структуру взаимного расположения замкнутых контуров на поверхности объекта [46-48], применяется авторами в [19]. В этом случае дескрипторы содержат информацию о смежности и форме контуров. Недостатком данного метода является неоднозначность выбора необходимого количества контуров для объектов различного масштаба и детализации. В [20] предлагается описывать объект при помощи скелетных графов, ребра которых являются геометрическими множествами центров вписанных внутрь объекта сфер, касающихся противоположных сторон. Дескрипторы получившихся объектов задаются в виде матрицы смежности графа, которая содержит информацию о длинах и направленности ребер. Данный метод инвариантен к трансформациям, потере небольшой части данных, однако не всегда устойчив к зашумлениям и наличию артефактов.

Другие подходы, использующие скелетное представление, связаны с применением так называемых медиальных поверхностей. Здесь, в отличии от предыдущих методов, объект описывается совокупностью полигонов, приближенных к скелету объекта. Медиальные поверхности могут быть найдены различными способами, например, через выделение областей Вороного [21] или с применением дифференциальных характеристик [22]. В альтернативном подходе [23] медиальные поверхности вычисляются по двумерным проекциям объекта. Их построение выполняется как с использованием вокселей, так и с помощью облаков точек. Дескрипторы, основанные на медиальных поверхностях, содержат больше информации о форме объекта и позволяют отделять классы более схожих объектов. Однако данные дескрипторы менее устойчивы к зашумлениям и потере некоторой части данных. Следует отметить также, что дескрипторы, основанные на скелетном представлении, являются инвариантными к афинным преобразованиям, таким, как: перенос, поворот или масштабирование.

Дескрипторы, связанные с поверхностным описанием, включают в себя признаки, вычисленные на поверхности объекта. В одном из первых подходов используются числовые характеристики распределения координат точек в локальных окрестностях. В частности, в [24] объект представляется с применением так называемых функций распределения формы, значения которых вычисляются измерением углов, расстояний, площадей, объемов по координатам случайно выбранных точек. Полученные значения используются в дескрипторах объектов, которые при сопоставлении объектов сравниваются между собой. Данный метод обладает важными свойствами инвариантности к масштабированию, переносу и повороту, а также робастностью, однако зависит от выбора случайных точек. В [25] используются трехмерные статистические моменты первого и второго порядков, которые также вычисляются по значениям координат точек. Моменты первого порядка характеризуют центры масс координат, второго — описывают углы поворота и коэффициенты масштабирования объекта. При этом дескрипторы вычисляются итерационно: матрица

моментов второго порядка нормируется на свои собственные значения с каждым шагом итерации. Итерационный процесс минимизирует различие между дескрипторами, состоящими из значений нормированных матриц моментов. Одним из недостатков данного подхода является необходимость выбора разного количества итераций в зависимости от тестовых данных. В работе [26] предлагается подход, в котором используется дискретное преобразование Фурье [27] сферических гармонических функций [28] координат объектов. Значения коэффициентов Фурье используются в дескрипторах. С увеличением количества Фурье-коэффициентов повышается детализация описания объекта и точность распознавания, однако при этом наблюдается существенный рост вычислительных затрат. Несколько иной подход был представлен авторами в [29]. Пространство, в котором находился объект, разбивалось на регулярные части угловыми цилиндрическими секторами. Каждый из секторов характеризовался матрицей ковариаций. В таком методе важно подбирать оптимальные параметры разбиения, задающие количество сегментов, поскольку объекты могут иметь различные размеры и степени детализации. В работе [30] объект предлагалось представлять совокупностью частей поверхности, каждая из которых характеризовалась геометрическими характеристиками. Особенность этого метода состоит в том, что при выделении частей поверхности используется метод опорных векторов Support Vector Machine (SVM) [31], который представляет собой алгоритм машинного обучения без учителя.

Часто используются эффективные подходы, связанные с представлением анализируемых объектов в виде графов. Впервые в распознавании образов графы начали использовать в 70-х годах XX века [32]. Граф, состоящий из ребер и соединенных ими вершин представляет собой удобную и эффективную структуру данных. При этом сравнение объектов осуществляется путем сопоставления графов. Схожие структуры объектов во многих случаях отвечают изоморфным графам. Основная проблема заключается в том, что поиск изоморфных графов является NP-трудной задачей [33], которая может быть решена только за экспоненциальное время. В связи с этим с середины 90-х годов предлагается

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

В последнее время высокое качество распознавания демонстрируют методы, использующие спектральные характеристики графов [34]. Данные методы основаны на предположении о важности собственных векторов и собственных значений взвешенных матриц смежностей графов. В частности, в [35] предлагается метод распознавания по дескрипторным описаниям объектов. Эти дескрипторы включают в себя собственные векторы и значения матрицы Лапласа [34], являющейся аналогом непрерывного оператора Лапласа, который определяется на графе. В этом случае поверхность объекта представляет собой триангуляцию облака точек, которая может быть построена различными способами, например такими, как в [36]. Матрица Лапласа — это взвешенная матрица смежности, элементы которой определяются в соответствии с геодезическим расстоянием [37] по поверхности объекта между соответствующими парами точек, соединенных ребрами. Дескрипторы, построенные по собственным значениям и векторам матрицы Лапласа обладают инвариантностью к переносу, масштабированию, повороту и робастностью. В недавно описанном методе показано [38], что для сопоставления объектов можно ограничиться несколькими собственными значениями матрицы Лапласа и соответствующими им собственными векторами, что также позволяет сократить время вычислений для обработки больших наборов данных без значительной потери точности.

Однако еще более высокую точность продемонстрировала группа методов, связанная использованием спектральных разложений оператора Лапласа-Бель-трами [40], описывающего процесс диффузии на поверхности объекта. В [89] было показано, что спектральное разложение Лапласа-Бельтрами обладает рядом замечательных свойств. В связи с этим появилось множество подходов к построению дескрипторов, использующих собственные значения и собственные векторы оператора Лапласа-Бельтрами. Дескриптор собственных значений Eigenvalue Descriptor (EVD) [35] продемонстрировал высокую производительность, поскольку при помощи EVD каждый из объектов представляется

вектором собственных значений Лапласа-Бельтрами и подходит при предварительном отборе объектов. Похожий подход предложен в [40]. Здесь представлен дескриптор Global Point Signature (GPS), включающий в себя более полное спектральное описание — используются как собственные значения, так и собственные векторы.

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

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

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

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

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

Для достижения поставленной цели необходимо решить следующие основные задачи:

1) разработать модифицированные методы семантической сегментации и сегментации на отдельные объекты;

2) разработать и исследовать метод определения параметров сегментации;

3) разработать методы распознавания объектов по облаку точек;

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

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

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

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

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

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

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

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

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

В сегментации на отдельные объекты используется предположение о важности интенсивности лазерного сигнала. Аналогичным образом осуществляется процедура выделения суперпикселей. Введены гистограммы распределения ин-тенсивностей для каждого из суперпикселей. Однако поскольку количество точек в суперпикселях может существенно различаться, то гистограммы задаются с разным количеством столбцов. Вводится ЕМЭ-расстояние, позволяющее сравнивать гистограммы распределения интенсивностей с разным количеством столбцов. Ставится задача линейного программирования для нахождения ЕМЭ-расстояния между гистограммами распределения интенсивностей. Для улучшения качества сегментации предложена трехмерная фильтрация интенсивностей лазерных данных с использованием низкочастотного фильтра Габора и способы определения параметров фильтра.

Для разных типов сегментации разработан единый метод выделения объектов или классов путем слияния-разделения суперпикселей при помощи

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

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

Список литературы диссертационного исследования кандидат наук Левашев Сергей Петрович, 2020 год

Список литературы

[1] Vosselman, G. Building reconstruction using planar faces in very high density height data / G. Vosselman // International Archives of Photogrammetry and Remote Sensing. — Vol. 32(3). — 1999. — P. 87-92.

[2] Vosselman, G. 3D building model reconstruction from point clouds and ground plans / G. Vosselman, S. Dijkman // International Archives of Photogrammetry and Remote Sensing. — Vol. 34(4). — 2001. — P. 37-43.

[3] Hough, P.V.C. Method and means for recognizing complex patterns / P. V. C. Hough // U.S. Patent 3.069.654. — 1962.

[4] Fischler, M.A. Random Sample Consensus: A paradigm for model fitting with application to image analysis and automated cartography / M. A. Fischler, R. C. Bolles // Communications of the ACM. Vol. 24(6). — 1981. — P. 381-395.

[5] Tarsha-Kurdi, F. Hough-transform and extended RANSAC algorithms for automatic detection of 3D building roof planes from lidar data / F. Tarsha-Kurdi, T. Landes, P. Grussenmeyer // IAPRS. — Vol. 35(3). — 2007. — P. 407-412.

[6] Deschaud, J.E. A fast and accurate plane detection algorithm for large noisy point clouds using filtered normals and voxel growing / J.-E. Deschaud, F. Goulette // Proc. Int'l Symp. 3D Data Processing, Visualization, and. Transmission (3DPVT). — 2010.

[7] Monnier, F. Trees detection from laser point clouds acquired in dense urban areas by a mobile mapping system / F. Monnier, B. Vallet, B. Soheilian //

ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. — Vol. 1(3). — 2012. — P. 245-250.

[8] Sirmacek. B. Automatic Classification of trees from laser scanning point clouds / B. Sirmacek, R. Lindenbergh // ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. — Vol. 2(3). — 2015. — P. 137-144.

[9] Velizhev, A. Implicit shape models for object detection in 3D point clouds / A. Velizhev, R. Shapovalov, K. Schindler // SPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. — Vol. 1(3). — 2012. — P. 179-184.

[10] Johnson, A.E. Using spin images for efficient object recognition in cluttered 3d scenes / A. E. Johnson, M. Hebert // IEEE T Pattern Anal. — Vol. 21(5). -1999. — P. 433-449.

[11] Shapovalov, R. Cutting-plane training of non-associative markov network for 3D point cloud segmentation / R. Shapovalov, A. Velizhev // IEEE International Conference on 3D Imaging, Modeling, Processing, Visualisation and Transmittion. Hangzhou, China,. — 2011. — P. 1-8.

[12] Lim, E.H. 3D terrestrial LIDAR classifications with super-voxels and multi-scale Conditional Random Fields / E. H. Lim, S. David// Computer-Aided Design. — Vol. 10. — 2009. — P. 701-710.

[13] Stauffer, C. Adaptive background mixture models for real-time tracking / C. Stauffer and W. E. L. Grimson //in IEEE Computer Society Conference on Computer Vision and Pattern Recognition. — Vol. 2. — 1999. — P. 246-252.

[14] Hofle, B. Glacier surface segmentation using airborne laser scanning point cloud and intensity data / B. Hofle, T. Geist, M. Rutzinger, N. Pfeifer // IAPRS. — Vol. 36(3). - 2007.

[15] Luo, C. Context based multiple railway object recognition from mobile laser scanning data / C. Luo, Y. Jwa, G. Sohn // IEEE Geoscience and Remote Sensing Society (IGRASS). - 2014. - P. 3602-3605.

[16] El-Ashmawyab, N. Raster vs. point cloud lidar data classification / N. El-Ashmawyab, A. Shaker // The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. — Vol. 40(7). — 2014. — P. 79-83.

[17] Bao, Y. Classification of lidar point cloud and generation of DTM from lidar height and intensity data in forested area / Y. Bao, G. Li, C. Cao et. al. // The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Science. — Vol. 37(3). — 2008. — P. 313-318.

[18] 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] / G. Reeb // Comptes Rendus Acad. Sciences. Paris, France. — 1946. — Vol. 222. — P. 847-849.

[19] Waleed, M. Reeb graph path dissimilarity for 3D object matching and retrieval / M. Waleed, A. Ben Hamza // The Visual Computer. Springer. — 2012. — Vol. 28. — P. 305-318.

[20] Macrini, D. From Skeletons to Bone Graphs: Medial Abstraction for Object Recognition / D. Macrini, K. Siddiqi, S. Dickinson // 26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR. Anchorage, Alaska, USA.

- 2008. — P. 1-8.

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

[22] Feng, C. C.A descriptor for voxel shapes based on the skeleton cut space / C. Feng, A. C. Jalba, A. C. Telea // Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval. — 2016. — Vol. 8(8). — P. 13-20.

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

[24] Osada, R. Matching 3D models with shape distributions / R. Osada, T. Funkhouser, B. Chazelle, D. Dobkin // Proceedings International Conference on Shape Modeling and Applications, Genova, Italy. — 2001. — P. 154-166.

[25] Elad, M. Content based retrieval of vrml objects — an iterative and interactive approach / M. Elad, A. Tal, S. Ar // Proceedings Sixth Eurographics Workshop Multimedia. — 2001. — P. 97-108.

[26] Vranic, D.V. Tools for 3d-object retrieval: Karhunen-loeve transformand spherical harmonics / D. V. Vranic, D. Saupe, J. Richter // IEEE MMSP 2001. — 2001. — P. 293-298.

[27] Brigham, E.O. The fast Fourier transform / E. O. Brigham, R. E. Morrow // in IEEE Spectrum. — 1967. — Vol. 4(12). — P. 63-70.

[28] Tanaka, K. 3D object representation using spherical harmonic functions / K. Tanaka, M. Sano, N. Mukawa, H. Kanek // Proceedings of 1993 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '93), Yokohama, Japan. — Vol. 3. — 1993. — P. 1873-1880.

[29] Ankerst, M. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases / M. Ankerst, G. Kastenmiller, H.-P. Kriegel, T. Seidl // Proc. 6th International Symposium on Spatial Databases (SSD'99), Hong Kong, China. — 1999.

[30] Ruiz-Correa, S. A new paradigm for recognizing 3-D objects from range data / S. S. Ruiz-Correa, L. Shapiro // Proceedings Ninth IEEE International Conference on Computer Vision, Nice, France. — Vol. 2. — 2003. — P. 1126-1133.

[31] Steinwart, I. Support Vector Machines / I. Steinwart and A. Christmann // Springer Publishing Company. — 2008.

[32] Conte, D. Thirty years of graph matching in pattern recognition / D. Conte, P. Foggia, C. Sansone, M. Vento // International journal of pattern recognition and artificial intelligence. — 2004. — Vol. 18(3). — P. 265-298.

[33] Cho, M. Learning graphs to match / M. Cho, K. Alahari, J. Ponce //in IEEE Interational Conference on Computer Vision (ICCV). — 2013. — P. 25-32.

[34] Chung, F.R.K. Spectral graph theory / F. R. K. Chung // American Mathematical Society. — 1997.

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

[36] Yang, L. k-edge connected neighborhood graph for geodesic distance estimation and nonlinear data projection / L. Yang // Proceedings of International Conference on Pattern Recognition(ICPR). — Vol.1. — 2004. — P. 196-199.

[37] Surazhsky, V. Fast exact and approximate geodesics on meshes / V. Surazhsky, T. Surazhsky, D. Kirsanov, S. J. Gortler, H. Hoppe // ACM Transactions on Graphics (TOG). — Vol. 24. — 2005. — P. 553-560.

[38] Ng, A. Y. On spectral clustering: analysis and an algorithm / A. Y. Ng, M. I. Jordan, Y. Weiss // Proceedings of Neural Information Processing Systems (NIPS). — Vol. 2(3). — 2002. — P. 857-864.

[39] Pinkall, U. Computing discrete minimal surfaces and their conjugates / U. Pinkall, S. D. Juni, K. Polthier // Experimental Mathematics. — Vol.2.

- 1993. — P. 15—36.

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

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

[42] Aubry, M. The wave kernel signature: a quantum mechanical approach to shape analysis / M. Aubry, U. Schlickewei, D. Cremers // IEEE International Conference on Computer Vision Workshops, ICCV. Barcelona, Spain. — 2011.

- P. 1626-1633.

[43] Hammond, D.K. Wavelets on graphs via spectral graph theory / D. K. Hammond, P. Vandergheynst, R. Gribonval // Applied and Computational Harmonic Analysis. — 2011. — Vol. 30(2). — P. 129-150.

[44] Каркищенко, А.Н., Мнухин В.Б., Распознавание объектов железнодороной инфраструктуры по данным лазерного сканирования / А.Н. Каркищенко, В.Б. Мнухин, А.А. Абраменко, И.А. Гречухин, С.П. Левашев // Интеллектуальные системы на транспорте: Материалы IV международной научно-практической конференции "Интеллект-Транс-2014". — 2014. — C. 134-141.

[45] Каркищенко, А.Н. Сегментация объектов инфраструктуры по данным лазерного сканирования / А.Н. Каркищенко, В.Б. Мнухин, А.А. Абраменко, И.А. Гречухин, С.П. Левашев // Сборник трудов III международной научно-технической конференции "ИСУЖТ-2014". — 2014. — C. 193-197

[46] Левашев, С.П. Анализ изображений сравнением замкнутых контуров с помощью Фурье-дескрипторов / С.П. Левашев, А.А. Абраменко // Анализ изображений сравнением замкнутых контуров с помощью Фурье-дескрипторов. В сб. докладов всероссийской научно-технической конференции "Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности". Таганрог: издательство ЮФУ. — 2015.

[47] Левашев, С.П. Использование Фурье-дескрипторов для идентификации объектов инфраструктуры по данным лазерного сканирования /С.П. Левашев, А.Н. Каркищенко, В.Б. Мнухин, А.А. Абраменко // Сборник трудов IV международной научно-технической конференции "ИСУЖТ-2015". -2015. — C. 178-181.

[48] Левашев, С.П. Классификация объектов по данным лазерного сканирования с робототизированной системы с применением фурье-дескрипторов на основе выделения контуров /С.П. Левашев // В сб. статей международной научно-практической молодежной конференции "Робототехника и системный анализ-2015". г. Пенза. — 2015. — C. 19-26.

[49] Левашев, О.П. Распознавание и анализ объектов по данным лазерного сканирования / С.П. Левашев, А.А. Абраменко // Неделя науки 2015, сборник тезисов. — Ростов-на-дону. — Издательство Южного федерального университета. — 2015. — С. 565-567.

[50] Абраменко. А.А. Распознавание объектов по данным мобильного лазерного сканирования на основе метода моментов / А.А. Абраменко, С.П. Лева-шев // В сб. докладов всероссийской научно-технической конференции "Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности". Таганрог: издательство ЮФУ. — 2015.

[51] Левашев, С.П. Распознавание объектов на основе сравнения структур кусочно-линейных аппроксимаций / С.П. Левашев // Сборник трудов V международной научно-технической конференции "ИСУЖТ-2016". -2016. — С. 202-206.

[52] Левашев, С.П. Детекция аппроксимирующих плоскостей на основе статистических оценок по данным лазерного сканирования / С.П. Лева-шев // В сб. докладов всероссийской научно-технической конференции "Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности". — 2017. — С. 266-269.

[53] Левашев, С.П. Распознавание объектов на основе числовых характеристик графов / С.П. Левашев // В сб. докладов всероссийской научно-технической конференции "Фундаментальные и прикладные аспекты компьютерных технологий и информационной безопасности". — 2017. — С. 269-273.

[54] Левашев, С.П. Распознавание плоскостей в объектах железнодорожной инфраструктуры по лазерным данным / С.П. Левашев, А.Н. Каркищенко // Сборник трудов VI международной научно-технической конференции "ИСУЖТ-2017". — 2017. — С. 212-216.

[55] Левашев, С.П. Автоматическая сегментация объектов по данным лазерного сканирования / С.П. Левашев // Сборник статей II Всероссийской научнотехнической конференции молодых ученых, аспирантов,

магистрантов и студентов "Информационные системы и технологии: фундаментальные и прикладные исследования". — 2017. — C. 85-89.

[56] Каркищенко, А.Н. Сегментация облаков лазерных точек на основе методов теории графов / А.Н. Каркищенко, С.П. Левашев, В.Б. Мнухин // Сборник трудов VII международной научно-технической конференции "ИСУЖТ-2018". — 2018. — C. 129-133.

[57] Левашев, С.П. Регуляризация лазерных данных и распознавание объектов с помощью инвариантных алгебраических дескрипторов / С.П. Левашев, А.Н. Каркищенко // Сборник трудов VII международной научно-технической конференции "ИСУЖТ-2018". — 2018. — C. 174-179.

[58] Левашев, С.П. Распознавание 3D объектов на основе спектральных инвариантов с использованием глубокого машинного обучения / С.П. Левашев // Известия ЮФУ. Технические науки, Таганрог. — № 3. — 2019. — C. 20-31.

[59] Левашев, С.П. Метод распознавания объектов по данным лазерного сканирования на основе спектральной теории графов / А.Н. Каркищенко, С.П. Левашев // Известия ЮФУ. Технические науки, Таганрог. — № 3.

- 2019. — C. 72-85.

[60] Papon, J. Voxel cloud connectivity segmentation — supervoxels for point clouds / J. Papon, A. Abramov, M. Schoeler, F. Worgotter // IEEE Computer Society Conference on Computer Vision and Pattern Recognition. — 2013. -P. 2025-2034.

[61] Nurunnabi, A. Robust methods for feature extraction from mobile laser scanning 3D point clouds / A. Nurunnabi, G. West, D. Belton // In: B. Veenendaal and A. Kealy (Eds.): Research@Locate'15, Brisbane, Australia. — 2015. — P. 109-120.

[62] Rubner, Y. The Earth Mover's Distance as a Metric for Image Retrieval / Y. Rubner, C. Tomasi, L. J. Guibas // International Journal of Computer Vision. — 2000. — P. 99-121.

[63] Канторович, Л.В. О перемещении масс / Л.В. Канторович // Доклады РАН СССР. — № 37. — 1942. — С. 199-201.

[64] Kruizinga, P. Comparison of texture features based on Gabor filters / P. Kruizinga, N. Petkov, S.E. Grigorescu // Proceedings of the 10th International Conference on Image Analysis and Processing. — 1999. — P. 142-147.

[65] Nixon, M. Feature Extraction and Image Processing / M. Nixon, A. Aguado // Academic Press. — 2008.

[66] Huertas, A. Detection of Intensity Changes with Subpixel Accuracy using Laplacian-Gaussian Masks / A. Huertas, G. Medioni // IEEE Trans. on PAMI.

- Vol. 8(1). — 1986. — P. 651-664.

[67] Manthalkar, R. Rotation invariant texture classification using even symmetric Gabor filters / R. Manthalkar, P. K. Biswas, B. N. Chatterji // Pattern Recognition Letter. — Vol. 24(12). — 2003. — P. 2061-2068.

[68] Bin, W. Automated extraction of ground surface along urban roads from mobile laser scanning point clouds / W. Bin, Y. Bailang, H. Chang, W. Qiusheng, W. Jianping // In: Remote Sensing Letters. — Vol. 7(2). — 2016. — P. 170-179.

[69] Choi, S. Robust ground plane detection from 3D point clouds / S. Choi, J. Park, J. Byun, W. Yu // ICCAS 2014. — Vol. 10. — 2014. — P. 1076-1081.

[70] Holz, D. Fast range image segmentation and smoothing using approximate surface reconstruction and region Growing / D. Holz, S. Behnke // in

Proceedings of the International Conference on Intelligent Autonomous Systems (IAS), eju Island, Korea. — 2012.

[71] Poppinga, J. Fast plane detection and polygonalization in noisy 3D range images / J. Poppinga, N. Vaskevicius, A. Birk, K. Pathak //in International Conference on Intelligent Robots and Systems, (IROS). — 2008. — P. 3378—3383.

[72] LAS Specification 1.4 - R14 // American Society for Photogrammetry and Remote Sensing (ASPRS). — 2019.

[73] Bentley, J.M. Multidimensional binary search trees used for associative searching / J. M. Bentley // Communication of the ACM. — Vol. 18. — 1975.

- P. 509-517.

[74] Хардле, В. Прикладная непараметрическая регрессия / В. Хардле // М.: Мир. — 1993. — 349 С.

[75] Ширяев, А. Вероятность / А. Ширяев // М.: МЦНМО, Кн.1. — 520 С.-(2004). — 520 C.

[76] Berger, M. Le Spectre d'une Variet'e Riemannienne / M. Berger, P. Gauduchon, E. Mazet // IEEE Lecture Notes in Math. — Vol 194. — Springer Verlag. — 1971.

[77] Levashev, S. Segmentation of a point cloud by data on laser scanning intensities / S. Levashev // Pattern Recognition and Image Analysis. — Vol. 29(1). — 2019.

- P. 144-155.

[78] Fishman, G.S. Monte Carlo: Concepts, Algorithms, and Applications / G. S. Fishman // Springer Series in Operations Research. — Springer Verlag.

- 1996.

[79] McKean, H. Curvature and the eigenvalues of the Laplacian / H. McKean, I. Singer // J. Differential Geometry. — Vol.1. — 1967. — P. 43-69.

[80] Hu, M.-K. Visual pattern recognition by moment invariants / M.-K. Hu // IRE Trans. Info. Theory. — 1962. — Vol. 8(2). — P. 179-187.

[81] van Leuken, R.H. Complex Fiedler Vectors for Shape Retrieval / R. H. van Leuken, O. Symonova, R. C. Veltkamp, R. De Amicis // Structural, Syntactic, and Statistical Pattern Recognition. — Vol. 5342. — 2008. — P. 167-176.

[82] Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофи-дес // М.: Мир. — 1978. — 432 С.

[83] Mohar, B. Isoperimetric numbers of graph / B. Mohar // Journal of Combinatorial Theory, Series B. — Vol.47(3). — 1989. — P. 274-291.

[84] Kolmogorov, V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision / Y. Boykov, V. Kolmogorov //in IEEE Transactions on Pattern Analysis and Machine Intelligence. — Vol. 26(9). -2004. — P. 1124-1137.

[85] Sitnik, R. Optimized point cloud triangulation for 3D scanning systems / R. Sitnik, M. Karaszewski // Machine Graphics and Vision. — 2008. — Vol. 17(4). — P. 349-371.

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

[87] Ioannides, M. From Point Clouds to Triangular Meshes / M. Ioannides // Photogrammetric Week '13 Dieter Fritsch (Ed.) Wichmann/VDE Verlag, Belin Offenbach. — 2013.

[88] Kim, W.H. Wavelet based multi-scale shape features on arbitrary surfaces for cortical thickness discrimination / W. H. Kim, et. al. // Advances in Neural Information Processing Systems 25 (NIPS 2012). — 2012. — p. 1241-1249.

[89] Курант, Р., Гильберт, Д. Методы математической физики // М.: Мир, т. 2. — 1951. — 1020 C.

[90] Bronshtein, A. SHREC 2010: robust feature detection and description benchmark / A. Bronshtein, et. al. // Proc. 3DOR. — 2010.

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

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

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

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

[95] McGill DATABASE. — URL: www.cim.mcgill.ca/shape/benchMark/.

[96] Kingma, D.P. Adam: A Method for Stochastic Optimization / D. P. Kingma // CoRR. — 2014.

[97] Dozat, T. Incorporating Nesterov Momentum into Adam / T. Dozat // Conference on Learning Representations, Workshop Track. — 2016.

Приложение A. Вычисление коэффициентов дискретного оператора Лапласа-Бельтрами

В дискретизации [91] показано, что независимость от степени регулярности дискретной сетки и перенос свойств непрерывного оператора Лапласа-Бельтрами на свойства дискретного обеспечивают котангенс-веса:

ctg аг] + ctg ßl3

WH =

2

где aij — угол между отрезками р~рг и p~pi, в которых р- — точка-сосед pi, находящаяся слева от отрезка pipj, а ßij — угол между отрезками p+pi и p+pi, в которых р++ — точка-сосед pi, находящаяся справа от отрезка pipj (рис. A.1). Нетрудно показать, что котангенсные веса ctg а^ и ctg ßij можно найти следующим образом:

pj *\J■ 'aij - .

i с,г v

•*Р

+

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

(.Р- - Рг,Р- - Рз )

ctg агз =

- Рг\?\\Р- - Рз У2 - (Pj - Рг ,Pj - Рз )

д (Р+ - Рг^Р+i - Рз)

Ctg Ргз = , .

у\\р+ - рг\\2\\р+ - Рз \\2 - (Р+ - Рг,Р'+ - Рз) Также в дискретизации [91] показано, что коэффициент усреднения следует задавать как аг = ^ а- + — площадь области Вороного с центром

Рз еЯ (Р i)

в точке рг и с вершинами в точках р~,р+,Урз е М(рг), являющихся радиусами описанных окружностей около треугольников А(рг,р~ ,pmj) и А(рг,р+ ,pmj) со-

рг + рз

ответственно. Точка pmj = —-—, — середина отрезка, соединяющего рг и рз.

2

Площади треугольников А(рг,р- ,Рт,з) и А(рг,Р+,Рт,з), ^Рз е Я (рг), из которых состоит область Вороного, можно найти по стандартным формулам из линейной алгебры. Однако в модификации [92] было показано, что площадь области Вороного аг можно найти проще, с использованием котангенсов:

Ctg агз + Ctg Ргз 2

а, = . J J II,., ^ II

Ectg и:гз + ctg ^гз и

8 \\Рг - Рз\

Рз еЯ (Pi)

ПРИЛОЖЕНИЕ В. Вычисления в сверточной нейронной сети

Рассмотрим каждую из составных частей сверточной сети подробнее на примере прохождения одной из карт спектральных распределений (рис. В.1).

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

Конволюционный блок 1. Вычисляются свертки векторов из X с ядрами = 1,... ,Р\ размерности 5x5. Результатами сверток является набор

Рис. В.1. Архитектура сверточной нейронной сети с промежуточными слоями для одного

входного канала.

матриц

X(1L. = X * J^1),p = 1,...,РЬ

conv ,p

Процедура pooling, представляющая собой сокращение размерности признаков проводится путем вычисления максимальных элементов Xc0nv,p в каждой из полученнных матриц. В результате получим матрицы X(p1Jolp еще меньшего размера.

На этапе нелинейности все элементы X(p1(jolp проходят фильтрацию при помощи функции активации ReLU: а(х) = шах(0,ж). В результате получим новый набор матриц Xp:) ,р = 1,... ,Р(1).

Конволюционный блок 2. Вычисления осуществляются аналогично блоку 1 для всех р = 1,... ,P\,q = 1,... ,Р2, ядра J^ имеют уже меньшую размерность 3 х 3 :

X« ^ х(2) •

p conv,p,qi

X(2) X(2)

conv,p,q p о о l,p,q">

X(2) X (2)

pool,p,q ' v vp,q •

Полносвязный блок. Входным слоем является вектор f, представляю-

(2)

щий собой конкатенацию векторов Xp,q ,р = 1,... ,P1 ,q = 1,... ,Р2:

f = ф Xp2.

p,q

Далее производится обучение полносвязного слоя путем нахождения матриц весов W(1),Ж(2) и векторов смещений 6(1),6(2) (индекс соответствует слою полносвязного блока), при которых суммарная ошибка классификации Q была бы минимальной:

N 2

Q = ^ ^ L(W(d), b(d) ,fi ,у) ^ min , i=i d=i

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

^(Ж(*\/г,у) = - ^уг Ыуг,).

3

В этом случае у представляется в виде матрицы размерности N х К каждый элемент у^^ которой равен вероятности принадлежности ¿-го объекта к классу ].

Обучение полносвязного слоя происходит при помощи метода обратного распространения ошибки (backpгop) и состоит из двух этапов: прямого хода и обратного.

В качестве прямого хода вычислим матрицы выходов из соотвествующих слоев:

у^ = ал(к((1)),(1 =1,2

где к(л"> = №ул~1 + Ь(л\у(0) = /, а функция активации вектора ац представляет собой softmax:

ы^а» = ^ = 1,...т.

г

В качестве обратного хода определим вектора коррекции смещений и матрицы коррекции весов АW(1), AW(2) :

= Щ), АЖ^ = АЬ(а) (у^АТ , <1 = 2,1.

Выходом из полносвязного слоя является вектор А/ :

А/ =(Ж (1))т АЬ(1),

который для вычисления коррекции матриц ядер конвертируется в матрицы:

А^^р<зо1,р,д = А1,

где Q определим как операцию, обратную к конкатенации. Следующими этапами решения задачи будут вычисления коррекций матриц ядер AJ^, AJp2 на основе операций, обратных к pooling и сверткам, поскольку выполняется обратный ход для конволюционных блоков. Новые значения весов после предъявления объекта из обучающей выборки с помощью метода стохастического градиента будут иметь вид:

w(d) ^ w(d) _ ^aw(d),d =1,2,

где ^ — параметр, задающий темп обучения. Вычисления новых значений для ядер Jj(1), J^ и смещений 6(1),6(2) проводятся аналогично.