Проектирование системы для навигации внутри здания со сложной иерархической структурой

Охотниченко Алексей Васильевич ORCID: 0000-0003-0463-7589 магистр, кафедра вычислительной техники и программирования, ФГБОУ ВО «Магнитогорский государственный технический университет им. Г.И. Носова» 455500, Россия, Челябинская область, г. Магнитогорск, ул. Ленина, 38 Okhotnichenko Aleksei Vasil'evich Master's Degree, the department of Computer Science and Programming, Nosov Magnitogorsk State Technical University 455500, Russia, Chelyabinskaya oblast', g. Magnitogorsk, ul. Lenina, 38 okhotnichenko.a.v@gmail.com

Кухта Юлия Борисовна кандидат технических наук доцент, кафедра вычислительной техники и программирования, ФГБОУ ВО «Магнитогорский государственный технический университет им. Г.И. Носова» 455500, Россия, Челябинская область, г. Магнитогорск, ул. Ленина, 38 Kukhta Iuliia Borisovna PhD in Technical Science Docent, the department of Computer Science and Programming, Nosov Magnitogorsk State Technical University 455500, Russia, Chelyabinskaya oblast', g. Magnitogorsk, ul. Lenina, 38 perfectumyuka@mail.ru

Введение

Университет МГТУ им. Г.И. Носова города Магнитогорска (далее – университет) создан 9 апреля 1934 года. За годы своего существования структура университета сильно изменилась. Первоначально было построено одно здание, состоящее из 5-ти этажей. Далее к нему было пристроено южное крыло и возведено два отдельных здания для строительного и технологического факультета. На сегодняшний момент университет состоит из более чем 15 зданий сложной иерархической структуры, в которых проводятся учебные занятия для студентов. Следует отметить, что каждый год в вузе меняется структура аудиторного фонда, например, меняется нумерация кабинетов, реструктуризируются деканаты и кафедры, что вносит изменения в существующую структуру и затрудняет поиск необходимых аудиторий не только первокурсникам, но и студентам старших курсов, а также преподавателям. Решить эту проблему поможет разработка мобильного приложения, позволяющего осуществлять навигацию внутри здания, т.е. поиск нужной аудитории или кабинета с учётом всех особенностей строения.

Согласно исследованиям большое количество образовательных учреждений не используют цифровые навигационные системы или используют только их бумажные версии ^{[1, 2]}. Это объясняется несколькими причинами. Во-первых, большими трудозатратами на оцифровку плана этажей зданий. Во-вторых, сложностью разработки системы навигации внутри здания со сложной иерархической структурой. В-третьих, отсутствие у бюджетной организации дополнительного финансирования на проведения указанных работ.

Следует отметить, что на текущий момент существуют разработанные системы, позволяющие решать проблемы поиска локации внутри здания. Чаще всего в них для навигации используют оцифрованные 2D-карты (планы этажей), что объясняется простотой реализации. В свою очередь, такой формат карты не очень удобен с точки зрения представления информации, затрудняя ее восприятие тем самым увеличивая время, требуемое пользователем на понимание нюансов структуры графического плана-чертежа внутреннего строения здания ^[3-8]. Следует отметить, что существующие навигационные системы не предоставляют дополнительную информацию об аудиториях, такую как местоположение на карте или текущий статус аудитории (аудитория для учебных занятий или служебный кабинет).

В большинстве вузах ориентироваться внутри здания помогают дверные таблички с нумерацией аудиторий, навигационные указатели для отображения направления движения, информационные стенды в холлах для размещения информации ^[9] и почти не используются электронные аналоги, хотя следует отметить, что среди существующего русскоязычного программного обеспечения, доступного в Play Market, найдено 14 мобильных приложений. Большая часть из которых обладает функцией построения маршрута между аудиториями и предоставляют возможность найти определенную локацию. При использовании приложений наиболее наглядным способом ориентации стал 2D и 3D формат представления карты университета. Сравнительный анализ функций приложений представлен в таблице 1.

Таблица 1

Сравнительный анализ функционала приложений по навигации внутри здания

Большинство рассмотренных мобильных приложений отображают карту в формате 2D, для этого разработчики преобразовали планы этажей в векторные изображения. Остальные представляют 3D-карту, построенную в виде виртуальной модели зданий на основе чертежей строения.

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

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

Проектирование структуры модуля должно учитывать следующие особенности:

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

- каждый 3D-объект будет получен из 2D-объекта с помощью аффинных преобразований ^[10].

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

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

• Bluetooth-маячки. Для покрытия значительной площади здания требуют больших материальных затрат, используют открытые протоколы, которые не могут обеспечить защиту данных ^[11-13];

• Wi-Fi. Для точного определения местоположения требуют большого количества роутеров ^{[3, 7, 12]};

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

• датчики мобильного устройства (акселерометр, магнетометр). Значительно ограничивают возможных пользователей, поскольку не во всех смартфонах есть эти датчики ^{[12, 14]};

• визуальные метки с машинным обучением. Модель требует времени на обучение и предъявляет повышенные требования к освещенности и к возможностям камеры смартфона, в условиях повышенной пропускной способности делают навигацию невозможной ^{[15, 16]}.

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

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

Существует множество алгоритмов определения кратчайшего маршрута. Особенность их заключается в следующем: они находят короткий путь между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь. Чаще всего в системах навигации используют следующие алгоритмы ^{[3, 4, 17-19]}:

• Алгоритм A* (Astar) или его модификации – алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (конечной);

• Алгоритм Флойда-Уоршелла – динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа;

• Алгоритм Беллмана-Форда – алгоритм поиска кратчайшего пути во взвешенном графе из одной вершины во все остальные.

С учётом особенностей решаемой задачи логичнее всего для поиска кратчайшего пути использовать модифицированный алгоритм A* (Astar), где связь между всеми графами (планы этажей) будет осуществляться через общие для всех них вершины – лестницы.

С учётом всего выше сказанного можно сформулировать цель работы – минимизация времени на поиск местоположения аудиторий в университете за счет создания мобильного приложения для навигации внутри зданий вуза с использованием 3D-карты этажей. Модуль навигации так же позволит построить маршрут от одной аудитории до другой.

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

1) выполнить теоретико-информационный анализ программных продуктов для поиска кратчайшего пути между объектами в пространстве и графического отображения этого маршрута в формате 3D;

2) осуществить синтез критериев эффективности функционирования модуля навигации;

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

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

Объектом исследования является система информатизации университета ФГБОУ ВО «МГТУ им. Г.И. Носова». Предметом исследования является программный модуль для поиска кратчайшего пути между объектами с возможностью визуализации результата.

Методы исследования

Следует отметить, что в условиях многоэтажности построение маршрута алгоритмом A* затруднительно, поскольку графы этажей не соединены между собой. Решить эту проблему можно связав графы через общие для всех вершины – лестницы. Таким образом, все этажи соединятся ребрами с положительными весами.

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

Основные этапы расчета алгоритма обнаружения краев Кэнни включают четыре аспекта:

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

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

3. Применяется метод двойного порога для определения возможной (потенциальной) границы.

4. Используется технология гистерезиса для отслеживания границ.

Результатом работы этого метода является массив с вершинами границ этажа (1). Координаты каждой вершины задаются двумя параметрами – x и y.

, (1)

где v – вершина границы этажа.

Для получения 3D-модели воспользуемся аффинными преобразованиями, а именно растяжением плоскости по оси Z (2). Для этого вершина будет задаваться тремя параметрами – x, y и z.

, (2)

где kz – коэффициент растяжения по оси z.

В результате получим двумерный массив, содержащий вершины одного этажа здания (3).

(3)

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

Рис. 1 Пример итоговой 3D-модели

Результаты проектирования

В соответствии с целями и требованиями создания система функционирует как платформа для:

- отображен формирования (в рамках выбранных пилотных маршрутов) 3D-моделей этажей;

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

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

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

Рис. 2 Схема функциональной структуры системы

Интерактивная система навигации содержит следующие подсистемы:

1. Подсистема формирования и настройки 3D-моделей: построение 3D-моделей и заполнение их информацией из источника данных.

2. Подсистема визуализации и анализа результатов навигации: обеспечивает работу графического пользовательского интерфейса (ГПИ), направленного на взаимодействие между конечным пользователем и подсистемой формирования и настройки 3D-моделей.

Система состоит из потоков (табл. 2), в которых:

- пользователь принимает непосредственное участие (q1-q2);

- проходящие без участия пользователя потоков (i1-i2).

Таблица 2

Описание управляющих взаимосвязей между объектами

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

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

Заключение

В результате работы:

1. Определена цель исследования и решаемые задачи.

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

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