Статья 'Проектирование системы для навигации внутри здания со сложной иерархической структурой' - журнал 'Программные системы и вычислительные методы' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > Требования к статьям > Политика издания > Редакция > Порядок рецензирования статей > Редакционный совет > Ретракция статей > Этические принципы > О журнале > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала
ГЛАВНАЯ > Вернуться к содержанию
Программные системы и вычислительные методы
Правильная ссылка на статью:

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

Охотниченко Алексей Васильевич

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

DOI:

10.7256/2454-0714.2021.4.37012

Дата направления статьи в редакцию:

01-12-2021


Дата публикации:

31-12-2021


Аннотация: На текущий момент существует множество систем, позволяющих ориентироваться в пространстве, т.е. определять точные координаты местонахождения объекта с возможностью построения маршрута с учётом заданных параметров. Однако, такие системы не пригодны для использования внутри здания. Это, прежде всего, связано с отсутствием открытого доступа к планам этажей. В связи с чем, актуальным является решение задачи по минимизации времени на поиск местоположения конкретного объекта, в том числе и внутри здания сложной иерархической структурой. Для решения поставленной задачи был выполнен анализ теоретических и практических разработок в области навигации, представлен их сравнительный анализ, который показал необходимость в проектировании и разработке модуля для навигации внутри многоэтажного строения с учётом особенностей его планировки. В результате авторами выполнена работа по проектированию структуры модуля навигации внутри здания сложной иерархической структурой с применением теории графов для поиска кратчайшего маршрута и алгоритмов аффинных преобразований для отображения графического представления плана строения на примере главного корпуса ФГБОУ ВО «МГТУ им. Г.И. Носова». Представлено описание подсистем и ее блоков, а также инструментов для определения геолокации объекта. Определены дальнейшие перспективы разработки системы с учётом особенностей создания электронных планов зданий с применением теории графов, а также разработки алгоритма редактирования параметров существующих 3D-объектов. В результате полной реализации проекта будет спроектирована и разработана система, позволяющая с помощью мобильного приложения ориентироваться в многоэтажном здании со сложной иерархической структурой, легко находить требуемые локации и строить кратчайший путь до их местоположения.


Ключевые слова:

кратчайший маршрут, навигация, аффинные преобразования, теория графов, здание сложной структуры, алгоритм визуализации 3D-объектов, алгоритм определения геолокации, планирование пути, алгоритм A-star, 3d моделирование

Abstract: There is currently a wide variety of navigation system, which allow determining the exact GPS coordinates and building a route taking based on the specified parameters. However, such systems are not suitable for indoor use, mostly due to no access to the floor plans. In view of this, it is relevant to minimize the time of searching for the location of a particular object, including in a building with complex hierarchical structure. The article examines the theoretical and practical developments in the sphere of navigation, conducts their comparative analysis, which indicated the need for designing the module for indoor navigation in a multi-storey building, considering the peculiarities of its floor plan. As a result, the authors designed the structure of the indoor navigation module in a building with complex hierarchical structure using the graph theory for detecting the shortest route and affine transformation algorithms for graphical representation of floor plan of a building on the example of the main building of the Nosov Magnitogorsk State Technical University. The article provides the description of its subsystems and blocks, as well as instruments for determining geopositioning of the object. The authors outline the prospects for the development of indoor navigation system, taking into account the peculiarities of creating electronic floor plans of a building based on the graph theory, as well as development of the algorithm for modification of the parameters of the existing 3D-objects. As a result of full implementation of the project, there will be designed the system of indoor navigation in a multi-storey building with complex hierarchical structure using a mobile app; it will help to easily find the geopositioning of the object and shortcuts.


Keywords:

shortest route, indoor navigation, affine transformations, graph theory, complex hierarchical building, 3D object visualization algorithm, geolocation algorithm, path planning, a-star algorithm, 3d modeling

Введение

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

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

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

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

Таблица 1

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

Мобильное приложение

Формат представления карты университета

Построение маршрута между аудиториями

Поиск аудитории

ПГНИУ Карты

2D

-

+

MY PGUPS

2D

-

+

Расписание политех

Псевдо-3D (2.5D)

-

-

РГГУ

2D

+

+

Спутник ГУАП

Псевдо-3D (2.5D)

+

+

Карта ПБ

2D

-

-

YUGU Guide

2D

+

-

RUND Ordoho map

3D

+

-

Навигация политеха AR

AR/3D

+

+

POLYNAVI

2D

+

+

PolyLook

Псевдо-3D (2.5D)

-

-

Navigator X

3D

+

+

Nav-In

2D

-

+

КубГУ навигатор

2D

+

-

Большинство рассмотренных мобильных приложений отображают карту в формате 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

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

Обозначение

Описание

q1

Управление блоком моделирования

q2

Управление блоком визуализации

i1

Системные данные

i2

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

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

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

Заключение

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

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

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

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

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

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

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

Предметом исследования в рецензируемом материале является проектирование системы навигации внутри здания для минимизации времени на поиск местоположения аудиторий в университете и построения маршрутов от одной аудитории к другой за счет с использования 3D-карты этажей.
Методология исследования базируется на использовании теории графов, методов анализа изображений для получения оцифрованной версии планов этажей, использовании стратегии вычислений.
Актуальность исследования обусловлена тем, что большинство образовательных учреждений не используют цифровые навигационные системы или используют только их бумажные версии, а существующие навигационные системы не предоставляют такой дополнительной информации об аудиториях, как местоположение на карте и текущий статус аудитории (учебная аудитория, компьютерный класс или служебный кабинет).
К научной новизна результатов представленного исследования, по мнению рецензента, можно отнести предложенную схему функциональной структуры навигационной системы для ориентации внутри здания со сложной иерархической структурой и реализацию спроектированной системы.
В статье выделены следующие разделы: Введение; Описание особенностей проектирования системы навигации внутри здания со сложной иерархической структурой; Методы исследования; Результаты проектирования; Заключение; Библиография.
Во введении кратко изложена необходимость и суть проводимого исследования, его предмет и проведен сравнительный анализ функционала 14 приложений по навигации внутри здания. В следующем разделе статьи изложены особенности проектирования системы навигации внутри здания; освещены инструменты и технологии, наиболее часто используемые для геолокации текущей позиции объекта внутри здания, а также алгоритмы определений кратчайшего маршрута: Astar, Флойда-Уоршелла, Беллмана-Форда. Здесь же сформулирована цель работы и решаемые задачи, определены предмет и объект исследования. Далее в самостоятельном разделе отражены методы исследования и приведен пример итоговой 3D модели. В разделе «Результаты проектирования» дана схема функциональной структуры системы и описаны подсистемы интерактивной системы навигации, а также управляющие взаимосвязи между объектами. В «Заключении» подведены итоги исследования.
Библиографический список статьи включает 20 наименований на русском и английском языках, на приведенные источники в тексте имеются ссылки, наличие которых свидетельствует об апелляции к оппонентам.
По рецензируемой статье следует высказать некоторые замечания.
Во-первых, представляется, что цель и задачи, а также предмет, объект и методы исследования стоит отразить намного раньше по тексту – во введении, а не отодвигать изложение этих элементов методологического аппарата исследования чуть ли не в середину статьи.
Во-вторых, некоторые ссылки даны не на конкретный источник заимствования, а на целый их перечень, например, «[3-8]», включающий до шести наименований публикаций, в которых, судя по их названиям, рассматриваются всё-таки различные аспекты решаемой проблемы.
В-третьих, размер шрифта на рисунке 2 излишне крупный.
Представленный материал соответствует тематике журнала «Программные системы и вычислительные методы», содержит оригинальные разработки, ориентированные на совершенствование навигации внутри зданий со сложной иерархической структурой путём разработки мобильного приложения. Статья рекомендуется к опубликованию.
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.