Методы снижения ресурсоемкости алгоритмов построения 3D-моделей объектов сложной формы в комплексах многоракурсного сканирования тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Гайдук Игорь Олегович

• Гайдук Игорь Олегович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Гайдук Игорь Олегович

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРОЦЕССОВ ГЕНЕРАЦИИ ЕДИНОЙ 3D-МОДЕЛИ НА ОСНОВАНИИ МНОГОРАКУРСНОГНО СКАНИРОВАНИЯ

1.1. Основные проблемы генерации трехмерных моделей

1.2. Методы совмещения нескольких облаков точек в единую трехмерную модель

1.3. Средства генерации трехмерных моделей на основе данных многоракурсного сканирования

1.4. Постановка задач диссертационного исследования

Выводы по главе

ГЛАВА 2. ФОРМАЛИЗАЦИЯ ПРОЦЕССА НАХОЖДЕНИЯ ОПОРНЫХ ОБЪЕКТОВ ДЛЯ ГЕНЕРАЦИИ ЕДИНОЙ 3D-МОДЕЛИ

2.1. Формализация процесса генерации единой трехмерной модели

2.2. Формальное представление процесса определения опорных объектов

2.3. Формализация процесса обхода графа

Выводы по главе

ГЛАВА 3. РАЗРАБОТКА МЕТОДИКИ И АЛГОРИТМОВ СОВМЕЩЕНИЯ ОБЛАКОВ ТОЧЕК НА ОСНОВЕ ПОИСКА УНИКАЛЬНЫХ КОНТУРАХ НА СРЕЗЕ ОБЛАКА ТОЧЕК

3.1. Разработка методики определения опорных объектов

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

3.3. Разработка модифицированного алгоритма определения опорных

объектов

Выводы по главе

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ РЕШЕНИЙ В РАМКАХ СОЗДАНИЯ ПРОГРАММНО-АППАРАТНОГО

КОМПЛЕКСА ДЛЯ МНОГОРАКУРСНОГО СКАНИРОВАНИЯ

4.1. Разработка структурной схемы

4.2. Программная реализация разработанных методики и алгоритмов

4.3. Экспериментальные исследования достоверности предложенных

решений

Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ

Введение диссертации (часть автореферата) на тему «Методы снижения ресурсоемкости алгоритмов построения 3D-моделей объектов сложной формы в комплексах многоракурсного сканирования»

Введение

Актуальность проблемы. По данным института анализа инвестиционной политики объем мирового рынка 3D сканирования в 2021 году составил $1,8 млрд. Эксперты прогнозируют данному сегменту рынка очень высокие темпы роста вплоть до 22% в год до 2025 года. Ключевым продуктом отрасли являются системы SD-сканирования, которые обеспечивают создание SD-модели объекта в автоматическом режиме. Подобные системы представляют собой программно-аппаратные комплексы, состоящие из аппаратной части, оборудованной разнообразными датчиками для получения информации об окружающей среде, и программной части, предназначенной для обработки данных датчиков и склейки их в единое облако точек.

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

Проблемы и методы автоматизированного слияния образов, методы фильтрации результатов сканирования, сегментация облаков точек, выявление характеристических особенностей глубоко исследованы и широко представлены в современной научной литературе. Всесторонней проработкой этой тематики занимались как зарубежные, так и отечественные специалисты в области SD-моделирования и цифровой обработки сигналов: F. Bernardini, D.A. Guttentag, Kai Liu, R. Mayer, Y. Wang, S. Zhang, В.А.

Богданович, А.Г. Вострецов, А.С. Глинченко, С.В. Умняшкин, Д.М. Клионский, М.Н. Рычагов, А.И. Солонина, Д.В. Ошкин, Е.С. Янакова. Однако, единого подхода к совмещению нескольких 3D-моделей не существует.

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

Целью диссертационной работы является снижение временных и вычислительных ресурсов на составление единой 3D-модели при трехмерном сканировании на основе методики и алгоритмов совмещения моделей в комплексах многоракурсного 3D-сканирования.

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

- аналитический обзор методов и средств генерации единой 3D-модели на основании данных многоракурсного сканирования;

- формализация задачи генерации единой 3D-модели;

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

- разработка алгоритма построения срезов облака точек;

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

- программная реализация предложенных методики и алгоритмов в виде программно-аппаратного комплекса (ПАК) для многоракурсного трехмерного сканирования;

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

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

Научная новизна. Диссертационная работа представляет собой совокупность научно обоснованных технических разработок, направленных на снижение временных и вычислительных ресурсов, необходимых для составления единой 3D-модели при сканировании объектов на основе предложенных методики и алгоритмов в комплексах многоракурсного 3D-сканирования.

В процессе исследований получены следующие новые научные результаты.

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

2. Предложено формализованное представление задачи генерации единой 3D-модели.

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

4. Разработан алгоритм выбора секущих плоскостей и построения срезов облаков точек.

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

6. Осуществлена программная реализация разработанных методики и алгоритмов в виде программно-аппаратного комплекса (ПАК) для многоракурсного 3D-сканирования.

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

Результаты работы подтверждены свидетельствами об официальной регистрации программы для ЭВМ «Программа обучения физическим процессам на основе генерации виртуальных объектов// Свидетельство о регистрации программы для ЭВМ RU 2017662888, 20.11.2017 и «Программа "сотр1еат" для формирования знаний на этапе конструкторско-технологической подготовки производства// Свидетельство о регистрации программы для ЭВМ RU 2015616138, 01.06.2015.

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

В результате применения разработанного в ходе исследований программно-аппаратного комплекса (ПАК) для многоракурсного 3D-сканирования временные и вычислительные ресурсы на составление единой 3Э-модели снизились на 18% .

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

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

• алгоритм выбора секущих плоскостей и построения срезов облаков точек;

• модифицированный алгоритм определения опорных объектов с помощью аппарата искусственных нейронных сетей, работающий на основе разработанной методики;

• программная реализация разработанных методики и алгоритмов в виде программно-аппаратного комплекса (ПАК) для многоракурсного 3D-сканирования.

Практическая значимость подтверждена актами внедрения результатов диссертационной работы в ООО «РАДИАНТ ТЕХ» и в учебный процесс МИЭТ.

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

1. Проведен обзор современных методов и средств генерации единой 3Э-модели на основании данных многоракурсного сканирования.

2. Предложено формализованное представление задачи генерации единой 3D-модели.

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

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

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

6. Предложенные алгоритмы и методика реализованы в виде программно-аппаратного комплекса для многоракурсного 3D-сканирования.

7. Проведена верификация результатов диссертационных

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

Реализация полученных результатов.

Диссертационная работа выполнялась в соответствии с планом научно -технических исследований Института системной и программной инженерии и информационных технологий Национального исследовательского университета «МИЭТ», являлась составной частью исследовательских мероприятий в рамках проекта Фонда содействия инновациям №256ГР/19315 "Разработка и изготовление трехмерного сканера, построенного на принципах лазерной дальнометрии".

Все работы по разработке и модификации алгоритмов и методики, а также программной реализации средств совмещения облаков точек проводились под руководством или при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе Института системной и программной инженерии и информационных технологий НИУ «МИЭТ» в материалах курсов «Визуализация в научных исследованиях», «Моделирование в среде AnyLogic», «Большие данные».

В результате проведенных исследований получены и выносятся на защиту следующие основные научные результаты:

1. Формализованное представление задачи генерации единой 3D-модели.

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

3. Алгоритм построения срезов облака точек.

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

Апробация работы и публикации.

Основные положения диссертации докладывались и обсуждались на конференциях:

1. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, г. Москва. 2018.

2. Всероссийская межвузовская научно-практическая конференция «Актуальные проблемы информатизации в науке и образовании», г. Москва. 2015, 2017.

3. IX Международная научно-практическая конференция «Технологии разработки информационных систем ТРИС-2019», г. Таганрог. 2019.

4. XII Международная конференция «Управление развитием крупномасштабных систем (MLSD'2019)», г. Москва. 2019.

5. X Международная научно-практическая конференция «Технологии разработки информационных систем ТРИС-2020», г. Таганрог. 2020.

6. XXIII Международная научная конференция «Инжиниринг предприятий и управление знаниями», г. Москва. 2020.

По результатам исследований опубликовано 17 работ, из них 2 из перечня ВАК.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложений, содержащих листинги программ и акты о внедрении результатов работы. Общий объем диссертационной работы 128 страниц машинописного текста, в работе содержится 6 таблиц и 31 рисунок. Список литературы содержит 102 наименования.

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

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

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

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

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

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

В приложениях приведены листинги программной реализации комплекса генерации единой 3D-модели, а также акты внедрения результатов диссертационной работы.

Глава 1. Обзор современного состояния процессов генерации единой 3Б-модели на основании многоракурсногно сканирования

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

1.1. Основные проблемы генерации трехмерных моделей

Основная сложность процесса сканирования состоит в том, что любые объекты, как микро, так и макроуровня невозможно полностью отсканировать с одного ракурса. Результатом такого сканирования, проведенного только с одного ракурса, является набор координат поверхности объекта относительно сканирующего устройства - некоторая часть модели с низкой точностью. Однако итогом сканирования объекта должна выступать единая 3D модель, для получения которой нужно провести слияние облаков точек, получаемых с разных ракурсов, в единое облако, которое в результате триангуляции станет точной трехмерной моделью. Этот процесс слияния является сложной и ресурсоемкой математической задачей [6]. На данный момент разработано множество методик сканирования,

позволяющих снизить вычислительную сложность и ресурсоемкость операции слияния.

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

Составление единой трехмерной модели на основе данных, полученных при многоракурсном сканировании, происходит в несколько этапов (рис.1.1).

Рис. 1.1. Этапы составления единой трехмерной модели [5]

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

снижения вычислительной сложности. Этот шаг может выполняться как вручную, так и автоматически с использованием специальных алгоритмов. Третьим, и самым объемным, этапом является объединение всех полученных облаков точек в единую модель. В зависимости от конструкции и характеристик сканера решение данной задачи может быть как обособленным, так и использовать некоторую информацию, генерируемую в процессе сканирования. После слияния всех облаков точек в единое облако модель нуждается в постобработке [9]. Заключаться такая обработка может как в сглаживании части точек на границах склейки разных фрагментов сканируемого объекта, так и в закрытии «белых пятен» на скане различными интерполяционными методами. На последнем этапе итоговая 3D-модель конвертируется в необходимый формат, например: STL, OBJ или COLLADA. Кроме этих форматов есть и другие, но они менее распространены или являются узкоспециализированными. Таким образом, представление итоговой BD-модели с помощью одного из вышеперечисленных форматов позволяет утверждать, что модель будет прочитано практически любым программным обеспечением, связанным с трехмерной графикой [10].

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

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

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

1.2. Методы совмещения нескольких облаков точек в единую

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

метод не является методом объединения облаков точек в принципе, он лишь постоянно добавляет по одной точке в уже существующее облако [13].

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

Рис. 1.2. Процесс контактного сканирования

Из-за перечисленных недостатков метод контактного сканирования в настоящее время имеет очень ограниченную сферу использования, хотя по -

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

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

Совмещение с применением геолокации. Наименее используемым методом на данный момент является совмещение облаков точек по геолокации, изображенный на рис. 1.3. Сама идея в основе метода проста и весьма заманчива. Она заключается в том, что если узнать положение сканирующего устройства в некотором пространстве и «закрепить» его, то для создания трехмерной модели нужно будет только сместить матрицу координат облака точек сканируемого объекта на вычисленные (ХД,7) координаты и повернуть их в соответствии с показаниями встроенного гироскопа или компаса относительно начала координат [14]. Ключевой проблемой данного метода стала точность геолокации: если метод выравнивания дает ошибку мминимум в несколько метров, сканирование

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

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

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

г

Камера

Поверхность земли

У

Рис. 1.3. Схема сканирования с применением геолокации

устройства в момент получения данных. Одним из наиболее важных преимуществ данного метода является время его работы. Это связано с тем, что общее облако создается сразу в процессе сканирования без дополнительных временных и вычислительных затрат на совмещение [18]. Однако это справедливо только для объектов простой формы и с размерами, не превышающими габариты установки [19].

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

Список литературы диссертационного исследования кандидат наук Гайдук Игорь Олегович, 2022 год

источников источников Backpack

Алгоритмы обработки «белых пятен» Интерполяция краевых значений «пятна» Интерполяция краевых значений «пятна» Широкий выбор алгоритмов устранения. Выбирается пользователем Широкий выбор алгоритмов устранения. Применяется автоматически

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

Точность получаемой модели Низкая, отклонение больше 55 Средняя, отклонение в пределах от 35 до 55 Высокая, отклонение меньше 35 Высокая, отклонение меньше 35

Низкая, Средняя, Высокая, Низкая,

Сложность доступный большое большое большое

освоения интерфейс с количество количество количество

пользовате- малым настроек и настроек, настроек, но

лем количеством смежного скрытые выставляются

настроек функционала атрибуты автоматически

Продолжение таблицы 1.2.

Нижние предельные размеры сканируемых объектов Сантиметры (микрометры с дополнительным оборудованием) Нанометры Нанометры Миллиметры

Верхние предельные размеры сканируемых объектов Метры Километры Километры Метры

На основе проведенного исследования предметной области и характеристик существующих средств генерации трехмерной модели необходимо произвести постановку задачи диссертационного исследования. 1.4. Постановка задачи диссертационного исследования

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

Цель диссертационной работы - снижение временных и вычислительных ресурсов на составление единой 3D-модели при трехмерном сканировании на основе методики и алгоритмов совмещения моделей в комплексах многоракурсного сканирования.

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

• провести формализацию задач нахождения опорных объектов на облаках точек и генерации единой 3D-модели;

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

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

• разработать модифицированный алгоритм определения опорных объектов с помощью аппарата искусственных нейронных сетей;

• реализовать предложенные методику и алгоритмы в виде программно-аппаратного комплекса (ПАК) для многоракурсного трехмерного сканирования;

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

Выводы по главе 1

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

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

3. Проведен анализ современных средств генерации единой 3D-модели на основе данных многоракурсного сканирования. Сформулированы основные требования к разрабатываемому решению.

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

Глава 2. Формализация процесса нахождения опорных объектов для генерации единой 3Б-модели

Для упрощения понимания и оценки результатов исследования следует провести формализацию процесса сканирования.

2.1. Формализация процесса генерации единой трехмерной модели

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

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

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

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

Таким образом, при сопоставлении двух облаков точек формально решается задача минимизации стоимости составления единой модели (2.1):

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

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

где в - Вычислительная сложность слияния; р - коэффициент

горизонтальной масштабируемости алгоритма слияния; М - количество вычислительных кластеров.

Как уже говорилось выше, вычислительная сложность рассчитывается в основном на базе используемого алгоритмического аппарата и размеров облаков точек. Кроме того, под размером облаков точек, в данном случае, понимается не просто количество точек в каждом облаке, но и общее число облаков для слияния, а также площадь их пересечения (2.3) [47]. Причем, если сложность алгоритма, количество облаков точек и их размер достаточно предсказуемо влияют на изменение общего значения [69], то площадь пересечения обладает сложной зависимостью. Характеризуется она тем фактом, что при площади наложения сканов более 50%, в составе друг друга будут просчитываться не только соседние облака точек.

и = F( т, о) ^ тт

(2.1)

(2.2)

в =

' О X Ц х (1 + 4ш), при 0 < ш < 0.5; О х (1 + 2—), при 0.5 < ш < 1.

V V 1—ш/

(2.3)

где О - сложность алгоритма, ^ - размер ьго облака точек, N -количество исходных облаков точек; ш - площадь пересечения сканов.

Наконец для расчета точности слияния используется формула (2.4), которая представляет из себя аппарат для расчет среднеквадратичного расстояния между точками различных облаков, лежащими на одном луче, проведенном из взвешенного центра слияния. Под взвешенным центром слияния понимается точка пространства равноудаленная от центров двух облаков, участвующих в слиянии[49]. Также стоит отметить тот факт, что провести один луч и вычислить расстояния между точками на нем не является достаточным, так как случайно проведенный луч может пройти по слепой зоне одного из облаков, следовательно, используется среднее квадратичное от отклонения между облаками на N лучах[50].

где - координаты ьой точки первого облака, х? - координаты ьой точки эталонного облака, N - количество лучей, построенных для расчетов. 2.2. Формальное представление процесса определения опорных объектов

Классическим способом определения опорных объектов является

характеристических примитивов на облаке точек. Происходит данное определение в два шага.

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

• те же облака точек, но разделенные по морфологической принадлежности;

• цифровые модели рельефа;

• ортофотомозаика;

(2.4)

использование математического аппарата для нахождения

• распознанные топографические объекты;

• их модели в трехмерном представлении.

Второй шаг - выделение фрагментов плоскостей, представляющих собой контуры поверхностей характеристических объектов. Наиболее обще этот этап можно описать, как выбор некоторого количества смежных треугольников и попытку по их вершинам построить плоскость, аппроксимирующую исследуемую поверхность [54]. Если по результатам проверки методом наименьших квадратов общее число треугольников, попавших на плоскость, не превышает пороговое значение, то данный фрагмент исключается из дальнейшего рассмотрения[55]. Пороговое значение выбирается в зависимости от ряда параметров, таких, как плотность облака точек, точность сканирования и подобных, и обычно составляет от 70% и выше. Поскольку данный алгоритм имеет сходную конструкцию как для плоскостей, так и для участков более сложной формы, рассмотрим выделение на триангуляционной модели объектов таких фигур, как сфера, цилиндр, конус и т.д.

В общем виде алгоритм можно разбить на следующие этапы [56]:

• строится граф топологической связности граней. Две грани (вершины графа) имеют ребро, если одной грани принадлежит треугольник 7\, смежный треугольнику Т2, принадлежащему другой грани;

• выбирается некоторое количество связных граней, чье количество достаточно для однозначного определения типа поверхности (поверхность должна быть выпуклой);

• для полученного набора граней строится в первом приближении фигура;

• по точкам выбранных граней итеративно строится новое приближение фигуры с использованием метода наименьших квадратов;

• по полученному приближению проверяется принадлежность других граней этой фигуре (рис. 2.1). На графе топологической смежности,

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

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

Включение треугольника в фигуру при положительном результате проверки точки

Игнорирование треугольника при отрицательном результате проверки точки

Рис. 2.1. Проверка принадлежности граней искомой фигуре Для каждого типа фигур дальнейшая реализация немного разнится. Чтобы однозначно выделить сферу, потребуется четыре плоскости, для конуса и цилиндра - три, причем для цилиндра две из них должны будут пересекаться с третьей под прямым углом. Рассмотрим дальнейшие действия для сферы, как для наиболее трудоемкого случая.

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

систему линейных уравнений, каждое из которых определяет расстояние от плоскости до центра предполагаемой сферы. Расстояние от плоскости, заданной уравнением Ах + Ву + Сг + О = 0, до точки Р0 = (х0,у0,г0) вычисляется по формуле (2.5).

¿ = Ахо+ Вуо + Сго + Р = <А2+В2 + С2 (2.5)

где й - расстояние, учитывающее не только величину, но и знак. Оно

будет положительным, если точка Р0 и начало координат лежат по одну сторону от плоскости. Так как коэффициенты всех четырех плоскостей известны, то в формуле (2.5) можно вычислить знаменатель и поделить на него, что даст нам г - расстояние от плоскости до центра сферы без учета знака.

г = 1Лхо + ВУо + С^о + Ог (2.6)

Чтобы избавиться от модуля в формуле (2.6) обозначим знак перед радиусом г после раскрытия модуля через Е" и получим следующее уравнение:

А^х0 + Ву0 + Сг0 - Е> = -Р. (2.7)

Приведя все уравнения к виду (2.7), получим систему:

(А -у В1 Сц Ец \ А2 В2 С2 Е2

А3 В3 С3 Е3

*0\ /-¿г

Уо | _ -¿2

) -¿3

г '

(2.8)

(А4 В4 С4 Е4)

Решением системы (2.8) будет точка Р0 = (х0,у0,го) - центр сферы, которой касаются четыре плоскости, а также ее радиус. На основе полученных данных можно делать окончательный вывод о правильности определения фигуры.

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

карта, которая служит для сопоставления двух и более облаков точек друг с другом [57].

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

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

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

2.3. Формализация процесса обхода графа

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

Количество данных для обработки и их способ хранения в памяти, в первую очередь диктуют определенные требования к структуре данных представления графа в памяти. Основными способами представления графа £ = (У,Е) в памяти являются: матрица смежности, список связанных вершин. Исследуем мы ориентированный или неориентированный граф не играет особой роли, так как обе структуры предполагают хранение любого типа объекта[59].

В задаче исследования графа, состоящего из вершин треугольников триангулированной модели облака точек, использование матрицы смежности не является оптимальным, так как предполагает хранение большого объема избыточных данных. В рамках представления облака точек в виде набора смежных треугольников максимальное количество связей каждой вершины обычно не выходит за пределы десяти, а вот количество точек, то есть вершин графа, может достигать значений в несколько миллионов [60]. Таким образом, получается, что для представления данных о десяти связанных вершинах будет выделяться память под (106)2 значений. Подобный метод хранения хорош для применения в случае плотных графов, так как позволяет быстро установить факт связи двух вершин. Данное представление чаще всего используется в задачах определения кратчайшего пути на графе[61].

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

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

Абсолютное большинство операций над графами предполагают его обход, то есть посещение всех вершин и ребер графа в той или иной последовательности[62]. Самыми известными и широко используемыми алгоритмами для проведения обхода графа являются поиск в ширину, поиск в глубину и обобщенный поиск.

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

Рис. 2.2. Основные понятия поиска на графе.

• неоткрытая - состояние вершины по умолчанию (непросмотренная вершина), на момент завершения работы алгоритма таких вершин остаться не должно;

• открытая - вершина (в накопителе), в которую хотя бы один раз алгоритм попадал, при этом, для нахождения в данном

непросмотренная вершина

Ч I

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

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

Поиск в ширину. В процессе осуществления обхода графа будет происходить перебор всех вершин, находящихся на расстоянии к от начальной вершины. Все эти вершины будут переходить в состояние открытых и одновременно с этим переходом заноситься в список исследуемых. Пока есть хотя бы одна вершина, удаленная от начальной на расстояние k, переход к k+1 не будет произведен. Как только все вершины, доступные из текущей, станут открытыми, она перейдет в состояние «обработанная» и будет удалена из списка. Процесс осуществляется до тех пор, пока список на обработку не станет пустым (рис. 2.3).

Используемый в данном алгоритме список для хранения вершин обладает реализацией классической очереди со схемой first-in-first-out (FIFO). То есть все вершины будут просмотрены в том порядке, в котором они поступали на вход алгоритма для рассмотрения.

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

состоянием открытая, и дальнейшее исследование уже будет проводиться для нее.

Рис. 2.3. Реализация поиска в ширину.

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

Рис. 2.4. Реализация поиска в глубину.

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

В отличие от поиска в ширину, поиск в глубину для хранения порядка прохода по вершинам использует хранилище типа last-in-first-out (LIFO),

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

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

7-1 «-Э 4-5 6-2

Рис. 2.5. Алгоритм обобщенного поиска.

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

На рисунке 2.6. представлены деревья поиска, которые будут построены на одном и том же графе различными алгоритмами.

ОРБ ВРБ обобщенный

(поиск в глубину) (поиск в ширину) поиск

Рис. 2.6. Работа различных алгоритмов поиска на графе.

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

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

Алгоритмическая сложность алгоритмов поиска в глубину и в ширину совпадает и равняется 0(п + т)[65], где п - количество вершин, т -количество ребер в случае хранения графа в виде списка связности вершин, и 0(п2) при использовании матрицы смежности, так как для каждой из п вершин будут рассматриваться все возможные связи с (п-1) прочими вершинами [66].

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

Выводы по главе 2

1. Рассмотрены теоретические основы процесса слияния нескольких облаков точек.

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

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

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

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

Глава 3. Разработка методики и алгоритмов совмещения облаков точек на основе поиска уникальных контуров на срезе облака точек

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

3.1. Разработка методики определения опорных объектов

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

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

Триангуляция облака точек является весьма ресурсоемкой математической операцией, которая вносит один из наибольших вкладов в рост итогового времени обработки данных [67]. Данный этап необходим для обнаружения опорных объектов, так как существующие алгоритмы поиска работают только с поверхностями, то есть облаком точек, прошедшим этап обработки, но не с сырыми данными[68]. Поиск опорных объектов осуществляется для каждой области использования собственным образом, так как характер объектов, которые можно принимать за опорные, отличается в зависимости от контекста составляемой модели. Характеристическая карта

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

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

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

• определение сектора пересечения облаков точек;

• осуществление выборки характеристических точек;

• вычисление среднеквадратичного отклонения.

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

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

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

Верификация полученного результата происходит на основе вычисления среднеквадратичного отклонения точек одного облака относительно другого. При превышении некой предельной величины отклонения 5 объединение облаков точек считается недействительным и происходит возврат к поиску опорных объектов на первом этапе (рис. 3.1). В зависимости от области исследования величина 5 может колебаться в достаточно широком диапазоне.

Рис. 3.1. Методика совмещения облаков точек по опорным объектам Исходя из формального представления задачи слияния, можно заключить, что наиболее ресурсоемким этапом является триангуляция исходных облаков точек[69], которая позволяет находить опорные объекты на скане. С целью сокращения ресурсозатрат, необходимых для реализации

этого этапа, предлагается осуществлять поиск характеристических объектов без использования алгоритмов триангуляции [70].

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

Подобное решение позволит значительно уменьшить алгоритмическую сложность процесса слияния [71], что положительным образом скажется на общей ресурсоемкости задачи. Происходит это благодаря значительному уменьшению мощности множества, подвергаемого обработке. Если в исходном варианте методики происходило прямое отображение множества треугольников Т в множество опорных объектов Я, то в усовершенствованной методике отображение д идет из множества В, являющегося подмножеством А: В с А (3.1).

Рис. 3.2. Усовершенствованная методика распознавания опорных объектов

на необработанных данных

д-в^я, (3.1)

где g - функция определения опорных объектов на множестве срезов.

Это по своей сути является классическим определением операции сужения и приводит к уменьшению алгоритмической сложности операции отображения.

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

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

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

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

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

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

Рис. 3.3. Схема алгоритма построения срезов облаков точек.

После построения секущих плоскостей производится анализ того, какие точки лежат в непосредственной близости от данных плоскостей. При попадании точек внутрь доверенного диапазона 5 они добавляются в массив интересующих нас объектов. Если в область 5 от плоскости попадает недостаточное количество точек, то необходимо провести дополнительное исследование [72].

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

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

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

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

3.3. Разработка модифицированного алгоритма определения

опорных объектов

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

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

В отличие от классической методики совмещения с использованием триангуляции [73], не требуется организовывать сложный перебор графа объектов для поиска геометрических примитивов [74]. Достаточно будет передать на анализ участки изображения линии границы исследуемого объекта обученной ИНС. За счет регулирования размера окна детектора и передачи на анализ только участков, содержащих данные о границах, получаем значительную экономию вычислительных ресурсов [75].

Рис. 3.4. Схема модифицированного алгоритма определения опорных

объектов.

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

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

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

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

На следующей стадии происходит перебор всех срезов и потенциальных объектов на них. Целью данного этапа является сопоставление уникальных контуров на разных уровнях срезов для выделения области возможного объекта, с целью триангуляции данной области в дальнейшем [76].

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

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

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

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

Следует обратить внимание на тот факт, что на данный момент проверка соответствия части трехмерной поверхности заданному шаблону по-прежнему осуществляется с помощью модели, состоящей из треугольников [77, 78]. Исходя из этого факта, этап триангуляции обязан присутствовать в любой методике, пусть и на гораздо меньшем объеме облака точек. Хотя, в марте 2021 года вышла статья, авторы которой предполагают использование сверточных нейронных сетей для поиска заданных объектов на необработанном облаке точек.

Авторы работы [79], в первую очередь, ориентировались на обнаружение объектов системами автопилотирования. Для автономных транспортных средств первостепенной задачей является оценка состояния семи степеней свободы окружающих объектов [80]. В число упомянутых семи степеней входят данные о местоположении, размере объекта и его ориентации в пространстве. В качестве прибора, проводящего измерения, был применен LiDAR, так как он позволяет с высокой скоростью получать данные об окружающем пространстве в трех измерениях [81, 82]. Однако, как уже говорилось ранее, в отличие от методов извлечения данных из

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

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

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

Рис. 3.5. Выделение признаков на необработанном облаке точек.

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

в режиме реального времени. Но следует обратить внимание на тот факт, что область применения подобного подхода жестко регламентирована. Проявляется это в том, что формы окружающих объектов известны и не отличаются большим разнообразием [85, 86]. Кроме того, подобная детекция не требует высокой точности, так как определить вектор движения автомобиля или пешехода можно без построения высокодетализированной модели объекта [87].

Выводы по главе 3

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

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

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

4. Проведен анализ существующих методов получения информации из массива необработанных данных.

5. Разработан модифицированный алгоритм детектирования границ предполагаемого опорного объекта на сыром облаке точек без использования триангуляции.

Глава 4. Программная реализация разработанных решений в рамках создания программно-аппаратного комплекса для многоракурсного сканирования

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

4.1. Разработка структурной схемы

В рамках реализации программно-аппаратного комплекса должны быть разработаны следующие программные модули:

• модуль определения линии горизонта (опционально);

• программный модуль корректировки линии горизонта на облаках точек;

• программный модуль фрагментации данных;

• программный модуль определения предметной области исследования (опционально);

• программный модуль построения двумерных срезов;

• программный модуль детекции потенциальных опорных объектов на срезах;

• программный модуль верификации опорных объектов;

• программный модуль корректировки сдвигов облаков точек;

• программный модуль сборки итоговой трехмерной модели. Входящие в состав программно-аппаратного комплекса аппаратные

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

• сканирующий модуль, который обеспечивает весь комплекс данными в виде облаков точек;

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

• камера для определения предметной области сканируемого объекта. Может быть заменена программным модулем.

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

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

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

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

После корректировки всех облаков точек их итоговый набор поступает в модуль фрагментации данных. В целях обеспечения максимальной правдоподобности получаемой необходимо определить область наложения сканов друг на друга. Для определения оптимального значения области наложения сканов определим целевую функцию стоимости (4.1, 4.2):

^стоимости^подготовки» ^вычислений} ^ ШШ (4>1)

Г = а1 ^ + ^ ^ +^3 ^ (4.2)

Ок

^опт

Где: а1 -а3, весовые коэффициенты для отнормированных на оптимум значений о, О соответственно:

- реальное, усредненное по группе, значение точности слияния. ¿я - время выполнения слияния, усредненное по группе. Од - вычислительная сложность.

^опт, £опт, ^опт - усредненные экспертные оценки оптимальных значений.

Для вычисления значения функции стоимости были получены данные от группы экспертов на предмет оптимальных значений точности, времени выполнения и вычислительной сложности слияния. Также для каждого значения выводились весовые коэффициенты, сумма которых равна единице (табл. 4.1).

Таблица 4.1. Значения экспертных оценок параметров функции стоимости

Эксперт ^опт ^опт ^опт «2 «3

1 0,005 23 750 0,4 0,4 0,2

2 0,008 25 650 0,35 0,35 0,3

3 0,004 27 800 0,5 0,3 0,2

4 0,004 29 600 0,45 0,25 0,3

5 0,006 28 650 0,4 0,3 0,3

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

График функции стоимости Стоимости^подготовки' ^вычислений) в

соответствии с площадью пересечения облаков точек(табл. 4.2) приведен на рисунке 4.2.

Функция стоимости

0,3 0,25

0,2 0,15 ОД 0,05

0 4

20 30 40 50 60 70 80 90 %

Процент пересечения облаков точек

Рис. 4.2. зависимость функции стоимости от площади наложения облаков

точек

Таблица 4.2. Значение параметров функции стоимости для групп

экспериментов

Группа экспериментов Процент пересечения сканов а ^работы алгоритма, мин Вычислительная сложность О, кол-во операций

1 20 0,020 68 1450

2 30 0,012 57 780

3 40 0,008 40 640

4 50 0,005 24 560

5 60 0,004 20 540

6 70 0,004 25 2670

7 80 0,004 28 7630

8 90 0,003 31 12000

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

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

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

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

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

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

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

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

4.2. Программная реализация разработанных методики и

алгоритмов

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

[91]. Класс сверточных нейронных сетей выбран в связи с тем, что он показал себя наиболее удачным с точки зрения распознавания визуальных образов

[92].

Самой известной и широко используемой архитектурой сверточной нейронной сети является VGG-19. Она содержит 19 слоев глубинного обучения, что позволяет добиться высокого шанса выделения характерных признаков на изображении. Архитектурно, данная сеть повторяет принципы построения своего предшественника - УОО-16 (рис. 4.3). После каждых нескольких сверточных слоев в ней включены слои субдискретизации для выделения и акцентирования внимания на наиболее выдающихся признаках изображения [93]. Итоговую классификацию проводят слои классической полносвязной сети, которые получают в качестве входных данных набор коэффициентов соответствия тем или иным признакам. Существует множество предобученных вариантов весов этой сети, что позволяет использовать ее без длительного этапа обучения, но, учитывая специфичность решаемой задачи, ни один из данных вариантов не подходит в чистом виде.

Рис. 4.3. Архитектура сверточной нейронной сети VGG-16 В качестве второй наиболее популярной архитектуры была выбрана сеть ResNet, в основу которой положен принцип исключения слоев. Residual Network, что дословно можно перевести, как остаточная нейронная сеть, имеет в своем составе остаточные слои, которые могут быть проигнорированы, если они не вносят дополнительной пользы в дело обнаружения признаков объектов [94]. Благодаря такому подходу можно добиться двух важных моментов. Во-первых, сводится к минимуму вероятность проявления эффекта переобучения, так как в случае незначительных изменений весов, слои будут постепенно выбрасываться из общей архитектуры [95]. Во-вторых, время обработки сетью каждого отдельного случая значительно меньше по сравнению с классическими жесткими архитектурами [96]. Среди представителей данной архитектуры есть реализации на 18, 34, 50, 101 и 152 слоя. Реализации с двумя уровнями глубины (18 и 34) показали недостаточную точность на тестовых данных, а реализации на 101 и 152 слоя свою избыточность в рамках решаемой задачи, поэтому представителем данного семейства для более подробного изучения характеристик стала ResNet-50 (рис. 4.4).

Рис. 4.4. Архитектура ResNet-50 Третьим семейством, участвующим в рассмотрении стали сети класса Inception. Данное семейство характеризуется наличием в числе своих слоев

блоков inception (рис. 4.5). Данный блок характерен набором фильтров различного размера, что позволяет с большей вероятностью находить ключевые признаки на изображении [97], но, в свою очередь, негативно сказывается на быстродействии всей сети в целом, так как на выходе из каждого подобного блока необходимо производить сопоставление результатов всех используемых ветвей [98]. На момент проведения исследования самой последней стабильно работающей версией данной архитектуры выступало четвертое поколение реализации - Inception v.4.

Рис. 4.5. Визуальное представление блока Inception.

Наконец, в качестве четвертого участника сравнения выступила архитектура графовых сверточных нейронных сетей GCNN, представленная на рисунке 4.6. Графовые нейронные сети относительно молодой инструмент, о котором впервые широко заговорили в начале 10-х годов XXI-го века. На данный момент графовые нейронные сети широко используются в биологии для решения задач межклеточного взаимодействия, в социологии для построения достоверных рекомендательных моделей и при

проектировании больших интегральных схем. Ключевой особенностью данного семейства нейронных сетей является концентрация на структуре взаимодействия объектов, их связей и взаимного расположения в пространстве [99,100].

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

Рис. 4.6. Архитектура GCNN.

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

Результатом работы классификатора является решение о принадлежности объекта тому или иному классу. Подобное решение может соотноситься с действительным положение положением вещей по одному из четырех сценариев:

1. True Positive (TP) - истинно-положительное решение, когда нейронная сеть относит объект к определенному классу и это решение совпадает с заранее проставленной меткой;

2. True Negative (TN) - истинно-отрицательное решение, когда объект классифицируется сетью в качестве объекта другого класса, что совпадает с меткой;

3. False Positive (FP) - ложно-положительное решение, когда нейронная сеть ошиблась при простановке положительной метки принадлежности;

4. False Negative (FN) - ложно-отрицательное решение, когда сеть ставит отрицательную метку истинному объекту класса.

Отношения величин, разобранных выше, характеризуют различные аспекты качества работы модели, что представлено в следующих формулах (4.3 - 4.6).

. tp+TN

Accuracy =--(4.3)

J TP+TN+FP+FN v '

TP

Precision =--(4.4)

TP+FP v '

TP

Pecaii = (4.5)

TP+FW v '

„ 2*PreciSion*Pecaii , .

F score = --(4.6)

PreciSion+Pecaii

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

Accuracy с = 1С;С (4.7)

¿/=1 ¿.¿=1^1,7 д

Precision с = (4.8)

¿¿ = 1 ЛС,1

д

Reca.lL = ^ с,с

с У™ А ■

(4.9)

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

Рис. 4.7. Матрица неточностей для мультиклассового классификатора Измерения точности методов проводились после того, как кривая обучения в каждом из методов прекращала рост и стабилизировалась на

каком-либо значении. Результаты измерений представлены на рисунке 4.8. Наилучшими показателями среди рассмотренных методов обладают графовая нейронная сеть и сеть с блоком Inception. После них по качеству распознавания идет остаточная нейронная сеть. Самыми худшими показателями среди представленных архитектур обладает VGG-19.

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

_Accuracy, Precision, Recall, F-score_

99 98 97 96

VGG-19 ResNet-50 GCNN Inception v.4

Рис. 4.8. Сравнение точности работы нейросетевых аппаратов Для проведения подобного исследования был сформирован набор из 50 облаков точек с заранее определенными объектами и передан на анализ всем архитектурам, включая классическую с использованием триангуляции. Особенностью данного эксперимента стало добавление в датасет нескольких облаков со сложно детектируемыми объектами[101].

Как можно видеть из рисунка 4.9 и таблицы 4.3, облака точек под номерами 8, 28 и 37 содержали объекты сложной формы. Распознать данные объекты большинству методов оказалось не под силу и эти облака проседают по проценту найденных уникальных контуров. Наилучшим инструментом для поиска контуров любой сложности оказалась ОСКЫ.

Таблица 4.3. Процент детектируемых объектов на облаке точек в

зависимости от используемой архитектуры

Номер облака точек Процент детектированных объектов, %

Триангуляция УСС-19 Кеэ^-50 1пеер1юп у.4 ССЖ

0 96 95.98 97.46 98.92 99.54

1 96 96.33 97.38 98.76 99.32

2 95 96.6 96.97 98.82 99.01

3 95 95.97 98.57 99.42 99.55

4 95 95.77 96.99 98.95 99.48

5 95 95.68 97.38 98.76 99.11

6 95 95.75 98.27 99.45 99.45

7 95 95.94 98.35 98.85 99.64

8 88 89.18 92.67 98.9 99.63

9 95 95.74 98.1 98.79 99.36

10 95 96.38 98.82 99.09 99

11 96 96.33 97.2 99.12 98.97

12 95 95.69 97.43 99.45 99.39

13 96 95.77 98.46 99.36 98.87

14 95 96.06 97.09 99.39 99.68

15 96 96.42 98.25 99.35 99.45

16 95 95.94 98.7 99.44 99.17

17 95 95.93 97.72 99.07 99.51

18 95 96.36 98.66 98.78 99.09

Продолжение таблицы 4.3.

19 95 96.06 96.95 98.77 99.38

20 95 96.4 96.91 98.8 99.65

21 96 95.67 98.27 99.25 99.11

22 96 96.62 98.7 99.29 98.83

23 96 96.25 98.81 98.94 99.59

24 96 96.59 97.39 99.47 99.66

25 96 96.23 98.74 99.17 99

26 96 95.8 97.9 98.86 99

27 95 95.74 97.01 99.11 98.96

28 75 78.82 83.58 93.66 98.99

29 96 96.38 98.31 99.18 99.37

30 95 96.62 97.79 98.95 99.5

31 96 96.27 98.54 99.15 98.9

32 96 96.11 97.2 98.83 99.58

33 95 96.12 97.51 99 99.12

34 95 96.03 98.65 98.85 99.42

35 95 96.19 98.27 98.81 98.85

36 95 96.51 98.02 99.32 99.68

37 82 84.01 89.54 96.79 99.24

38 96 96.35 98.63 99.48 99.42

39 95 96.23 97.32 98.98 99.73

40 95 96.38 96.99 99.5 98.97

41 95 96.3 97.82 98.99 99.35

42 96 96.43 98.48 98.93 99.38

43 96 95.98 98.06 98.8 99.52

44 95 95.8 97.73 99.14 99.33

45 96 96.27 98.78 98.81 99.04

Продолжение таблицы 4.3.

46 96 96.43 96.97 99.31 98.95

47 96 96.17 98.67 99.2 99.26

48 96 96.27 97.33 98.77 99.63

49 96 96.28 98.78 99.04 98.8

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

О 10 20 30 40 50

Порядковый номер эксперимента

Рис. 4.9. Процент детектируемых объектов Две оставшиеся архитектуры показывают результаты близкие друг к другу и классическому методу. Незначительно из этой тройки выбивается нейронная сеть ResNet-50 за счет контроля эффекта переобучения с помощью исключения части слоев в процессе работы.

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

8" 2000 4000 6000 8000 10000

Количество сканирований

Рис. 4.10. Зависимость временных затрат от количества сканирований Кривые временной сложности представлены на рисунке 4.10. На представленном графике приведена зависимость времени затрачиваемого на каждое отдельное сканирование от их количества. Так как метод с использованием триангуляции не нуждается в предобучении, время необходимое на каждое конкретное сканирование остается неизменным независимо от номера эксперимента. В случае же нейронных сетей, первые п экспериментов будут очень серьезно зависеть от затраченного на обучение времени. Количество экспериментов, после которого график того или иного

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

Самой простой в обучении получается ResNet за счет исключения части слоев в случаях, когда они являются излишними, уже в районе проведения 500 сканирований она начинает выигрывать у классической триангуляции. Архитектуры VGG-19 и Inception преодолевают это порог в районе 2500 и 3000 соответственно. А графовая нейронная сеть только к отметке в 10 тысяч экспериментов начинает окупать свое использование.

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

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

4.3. Экспериментальные исследования достоверности предложенных решений

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

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

Значение функции стоимости рассчитывалось как среднее арифметическое взвешенное значение времени сканирования с вкладом, рассчитываемым от точности сканирования по формуле 4.10.

(4.10)

¿4 = 1