6172

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

Для создания эффективных алгоритмов реализации различных видов поиска объектов ПРД в базе данных, а также эффективных методов обработки данных БЦГД, разработана геометрическая модель описания цифрового

одинаковой у всех объектов группы (при наличии), например, у кодов 5.2.2.3 и 5.2.6.3 эта часть будет 5.2, т.е. первые две позиции. На каждом уровне иерархии каждый объект находится лишь в одном узле. Листья содержат код, номер, адрес объекта в БД, а также координаты углов, описывающего данный объект прямоугольника.

Описание алгоритма построения разработанной древовидной структуры приведено в разделе 2.4.

В работе реализованы следующие типы поиска: по коду, по координатам, по характеристикам, а также выполнение сложноструктурированных запросов.

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

11

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

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

3)Поиск по характеристикам организован аналогично поиску по коду, отличие состоит в том, что в найденных по коду объектах осуществляется последовательный поиск по заданным характеристикам с определенными фильтрами (больше, меньше, равно, не равно, входит строка, совпадает строка). Алгоритм поиска объектов по характеристикам описан в разделе 2.7.

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

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

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

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

12

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

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

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

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

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

13

Взадаче выбора маршрута по бездорожью заданы две точки: А - точка старта и B - точка назначения в заданной области, содержащей зоны препятствий (объекты препятствия P*) представленными соответственно модели описания БЦГД. Между этими двумя точками следует проложить маршрут из точки А в точку В, огибающий области препятствий.

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

Вначале работы алгоритма граф G* состоит из одного ребра, соединяющего две точки A и B. На

каждой итерации алгоритма ищутся

взаимоположение отрезков (p1,p2) и (p2,p3) с отрезками - ребрами сформированного на данный момент графа G*. Возможны следующие ситуации

(рис. 6):

1)Отсутствует геометрическое взаимодействие (пересечение, совпадение) отрезков. Корректировка графа G* не требуется;

2)В случае возникновения ситуаций, изображенных на рисунке 6.1 и 6.2

–ребро [r1,r2] удаляется из графа G*;

3)В случае возникновения ситуации, изображенной на рисунке 6.3, ребро [r1,r2] удаляется из графа G*, и в него добавляются ребра [r1,P1], [r1,P2], [r2,P1], [r2,P2].

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

14

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

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

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

Экспериментальная апробация показала, что разработанные и реализованные на мобильных устройствах алгоритмы позволяют решать задачу прокладки маршрута по бездорожью на реальных цифровых морских навигационных картах (ЦМНК), при ограниченных вычислительных и емкостных ресурсах, в пределах нескольких секунд, а по графу дорожной сети на цифровых топографических картах (ЦТК) за несколько миллисекунд. При этом матрица переходов для решения задач поиска маршрутов по графу

15

дорожной сети строится лишь при открытии карты и занимает порядка 3-5 секунд.

Четвёртая глава посвящена описанию, созданного для мобильных устройств программного обеспечения, реализующего предложенные модели описания и структуры представления объектов ПРД, БРИГД, БЦГД, а также алгоритмы решения, на их основе, различных тематических задач, связанных с обработкой больших объемов графической информации.

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

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

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

-алгоритм построения шаблона описания объектов в заметках.

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

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

16

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

Взаключении приведены основные результаты работы, которые состоят

вследующем:

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

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

17

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

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

4)Разработан программный комплекс для мобильных устройств, реализующий предложенные модели, структуры и алгоритмы. Программный комплекс может использоваться для визуализации большеформатных растровых изображений, обработки и поиска данных на БЦГД, поиска маршрута по графу дорожной сети и по бездорожью.

Публикации по теме диссертационной работы

Статьи, опубликованные в изданиях, рекомендованных ВАК:

1.Egorov, A.A. Mobile Geoinformation system/ Yu.G.Vasin, S.V.Zherzdev, A.A.Egorov // Pattern Recognition and Image Analysis. – 2009. - Vol. 19, No. 2. - РР.342-348.

2.Egorov, A.A. An Algorithm for Off-Road Routing of Vehicles/ Yu.G.Vasin, A.A.Egorov// Pattern recognition and Image analysis. - 2010. - Vol.4. - РР. 573-576.

3.Егоров, А.А. Многофункциональное программное обеспечение для обработки пространственно-распределенных данных/ А.А.Егоров// Вестник Нижегородского университета им. Н.И. Лобачевского. – 2012. - №5(2). - С.330337.

Статьи в сборниках научных трудов и сборниках конференций:

4.Egorov, A.A. Mobile Geoinformation system/ Yu.G.Vasin, S.V.Zherzdev, A.A.Egorov // Pattern recognition and Image analysis. - Yoshkar-Ola, 2007. - Vol.2.

–РР.213-216.

18

5.Егоров, А.А. Иерархическая структура хранения пространственнораспределенной информации/ Ю.Г.Васин, С.В.Жерздев, А.А. Егоров// Модели, методы и программные средства: сб. тез. докл. конф. – Н. Новгород, 2007. - С. 70-72.

6.Егоров, А.А. Мобильный программный картографический комплекс «BigViewer CE»/ А.А. Егоров// Технологии Microsoft в теории и практике программирования: сб. тез. докл. конф. – Н. Новгород, 2008. - С. 137-140.

7.Egorov, A.A. Mobile sea navigated system/ Yu.G.Vasin, S.V.Zherzdev, A.A.Egorov // Pattern recognition and Image analysis. – N. Novgorod, 2008. - Vol.2.

-РР.276-278.

8.Егоров, А.А. Решение задач на графах в мобильном программном картографическом комплексе «BigViewer CE»/ Ю.Г.Васин, А.А. Егоров// Технологии Microsoft в теории и практике программирования: сб. тез. докл.

конф. – Н. Новгород, 2009. - С.55-61.

9.Егоров, А.А. Реализация на малых платформах алгоритма прокладки маршрута транспортных средств по бездорожью (при отсутствии дорожной сети)/ Ю.Г.Васин, А.А. Егоров// Технологии Microsoft в теории и практике программирования: сб. тез. докл. конф. – Н. Новгород, 2010. - С. 134-136.

10.Егоров, А.А. Сравнение функциональных возможностей существующих ГИС для малых платформ и «BigViewer CE»/ Ю.Г.Васин, А.А. Егоров// Технологии Microsoft в теории и практике программирования: сб. тез. докл. конф. – Н. Новгород, 2010. - С. 137-140

11.Egorov, A.A. An Advance of the Geoinformation System for Handheld Computers (PDAs)/ Yu.G.Vasin, A.A.Egorov// Pattern recognition and Image analysis. - Saint Petersburg, 2010. - Vol.2. - РР.57-58.

12.Egorov, A.A. An Algorithm for Off-Road Routing of Vehicles/ Yu.G.Vasin, A.A.Egorov// Pattern recognition and Image analysis. - Saint Petersburg, 2010. - Vol.2. - РР.225-226.

13.Egorov, A.A. The structure of a multi-functional mobile GIS/ A.A.Egorov// Pattern recognition and Image understanding: 8th Open German Russian Workshop OGRW-8-2011. – N. Novgorod, 2011. - РР. 48-52.

14.Egorov, A.A. Autonoomous indoor navigation based on 3D-modeling/ Yu.G.Vasin, M.P.Osipov, A.A.Egorov, E.A.Kustov, Yu.V.Yasakov// Pattern recognition and Image analysis: new information technologies. - Samara, 2013. - Vol.2. - РР.476-478.

15.Egorov, A.A. Client-server data acquisition subsystem for 3D modeling and subsequent 3D visualization on handheld computers/ Yu.G.Vasin, A.A.Egorov,

19

Yu.V.Yasakov// Pattern recognition and Image analysis: new information technologies. - Samara, 2013. - Vol.2. - РР.754-756.

Свидетельства о регистрации программ для ЭВМ:

16. Егоров, А.А. Программный комплекс обработки пространственнораспределенных данных и большеформатных изображений на малых платформах/ Ю.Г.Васин, А.А.Егоров, С.В.Жерздев, Ю.В. Ясаков // Свидетельство о регистрации электронного ресурса №19291 от 24.06.2013.

20