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

На правах рукописи

Егоров Андрей Александрович

МОДЕЛИ И АЛГОРИТМЫ ОБРАБОТКИ БОЛЬШИХ ОБЪЕМОВ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ НА МОБИЛЬНЫХ УСТРОЙСТВАХ

05.01.01 - Инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

г і моя 2013

005539200

Нижний Новгород - 2013

005539200

Работа выполнена в ФГБОУ ВПО «Нижегородский государственный университет им. Н.И. Лобачевского»

Научный руководитель

доктор технических наук, профессор Васин Юрий Григорьевич

Официальные оппоненты:

Утробин Владимир Александрович, доктор технических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Нижегородский государственный технический университет им. Р.Е.Алексеева», профессор кафедры вычислительных систем и технологий,

Немирко Анатолий Павлович доктор технических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И.Ульянова (Ленина)», профессор кафедры биотехнических систем

Ведущая организация:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новгородский государственный университет имени Ярослава Мудрого»

Защита состоится «17» декабря 2013 г. в 13 час. 00 мин на заседании диссертационного совета Д 212.162.09 при ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет» по адресу: 603950, г. Нижний Новгород, ул. Ильинская, 65, корпус 5, ауд. 202.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет» Автореферат разослан «15» ноября 2013 года.

Ученый секретарь диссертационного совета

кандидат педагогических наук, доцент — Н.Д.Жилина

Общая характеристика работы

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

Современный рынок компьютерной техники становиться все более дифференцированным и достаточно большую его составляющую начинают занимать так называемые «мобильные» устройства с ограниченной памятью, вычислительными ресурсами центрального процессора и малым размером экрана. Подобные устройства применяются как широким классом пользователей - обычными людьми (смартфоны, карманные персональные компьютеры, навигаторы, умные очки и часы, и т.д.), так и для спецназначения (мобильные роботы, летательные и глубоководные подводные аппараты, передвижные диспетчерские центры, индивидуальные средства МЧС, ЗЦ навигация и т.д.). Однако созданное программное обеспечение этого класса вычислительной техники имеет узкую специализацию решаемых задач в рамках определенной предметной области, ограниченные размеры и мапое количество обрабатываемых графических документов, объектной составляющей, атрибутивных и пространственно-логических связей, отсутствие механизма быстрого поиска данных при реализации разнообразных сложноструктурированных запросов и т.д.

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

направленности, разных масштабов, проекций и систем координат, космо- и аэро-фото изображений, постановке задачи сбора данных 3D моделирования и 3D визуализации пространственных объектов (зданий, сооружений, отдельных поэтажных планов), навигации в закрытых помещениях на базе 3D моделирования окружающего пространства, выбора маршрута и контроля движения по нему в условиях труднодоступных и малоизученных районов. Указанные проблемы в своих работах рассматривали такие ученые, как Васин Ю.Г., Кетков Ю.Л., Ротков С.И., Сергеев В.В., Клименко C.B., Рябко Б.Я., Бурт П.Дж., Кунт М., Роберте М.Г., Клеари Дж.Г. и другие. Однако необходимо дальнейшее развитие моделей описания и структур представления, методов и алгоритмов обработки и сжатия больших объемов графической информации, повышение интеллектуальности инструментальных средств обработки ПРД (обеспечение работы в терминах проблемной области, а не в кодах), дальнейшее повышение удобства работы в разных проблемных областях, решение тематических задач (прокладка маршрута по бездорожью и др.) с учетом ограниченности емкостных и вычислительных ресурсов мобильных устройств. Вышесказанное определяет актуальность данной работы.

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

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

Цель работы — разработка и развитие моделей описания и структур представления большеформатных растровых изображений (БФРИ) и объектов ПРД, а также алгоритмов хранения, поиска и обработки больших объемов большеформатных графических данных на мобильных устройствах.

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

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

2) Разработка модели описания и структуры представления болынеформатных цифровых (векторных) графических документов (БЦГД) с учетом реализации быстрого поиска данных для решения разнообразных тематических задач.

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

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

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

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

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

Научная новизна состоит в том, что:

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

2) Разработана геометрическая модель описания болыпеформатных цифровых (векторных) графических документов (БЦГД), позволяющая осуществлять поиск данных при реализации разнообразных метрических и семантических запросов, включая сложно-структурированные запросы, а также работать в терминах любой предметной области, а не в кодах; отличающаяся

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

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

Практическая значимость научного исследования. В основу работы положены результаты, полученные автором в ходе исследований, проводимых по плану научно-исследовательской работы Министерства образования и науки Российской Федерации, научно-исследовательских и опытно-конструкторских работ по хоздоговорам с ЗАО «Транзас» и ООО «Чарт-пилот». Работа выполнена при финансовой поддержке РФФИ проект №05-01-00590, проект №10-07-00330, проект №11-07-12049-офи-М, проект №12.-07-33107 мол_а_вед.

Результаты диссертационной работы использованы ООО «Чарт-пилот» в автоматизированной системе передачи по сети общего пользования сжатых калек-вклеек и трейсинг-калек на суда гражданского флота, используются в составе ГИС «Терра», в научно исследовательском институте прикладной математики и кибернетики Нижегородского государственного университета им. Лобачевского, для решения широкого класса задач обработки большеформатных растровых изображений и ПРД на мобильных устройствах, а также в учебном процессе на факультете вычислительной математики и кибернетики (ВМК) Нижегородского государственного университета им. Н. И. Лобачевского, на кафедре интеллектуальных информационных систем и геоинформатики (ИИСГео).

Разработано и зарегистрировано в официальном реестре программ для ЭВМ (РФ) программное обеспечение «Программный комплекс обработки пространственно-распределенных данных и большеформатных изображений на малых платформах».

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на международной конференции «Pattern Recognition and Image Analysis: New Information Technologies» (Йошкар-Ола, 2007 г., Нижний Новгород, 2008 г., Санкт-Петербург, 2010 г., Самара, 2013 г.), на конференции «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2007 - 2010 гг.), на Всероссийской конференции с международным участием «Модели, методы и программные средства» (Нижний Новгород, 2007г.), на 8-м Открытом российско-немецком семинаре «Распознавание образов и понимание изображений» (Нижний Новгород, 2011 г.).

Основные положения, выносимые на защиту:

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

2. Геометрическая модель описания болыпеформатных цифровых (векторных) графических документов, структура их представления, а также алгоритмы поиска данных БЦГД.

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

Публикации. Основные результаты исследований опубликованы в 15 научных работах, 3 из которых опубликованы в изданиях, рекомендованных ВАК Минобрнауки России. Получено свидетельство о регистрации электронного ресурса №19291 от 24.06.2013 на разработанное программное обеспечение.

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

Основное содержание работы

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

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

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

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

Данная модель реализована в виде регулярной двумерной последовательности прямоугольных четырехугольников (блоков) одинакового размера, покрывающих исходные БФРИ. Каждый из блоков рекурсивно делится пополам на фрагменты р3'1 (прямоугольники и квадраты) (//-номер уровня рекурсивного деления, £-номер

фрагмента уровня /л) меньших

Рис. 1. Рекурсивное разбиение блока изображения и размеров (рис. 1) и положение отсчетов соответствующего уровня

представляется в виде иерархии (Р^ - номер отсчета в матрице представления

БФРИ)

иерархическои структуры '

1,1

р1.5

Р1.3

т

щ

т

Р5.1

р5,5

щ рЗЗ Щ рЗ,5

Щ т

р5.3 РУ

р1,4

г>!

ГА

Р5,2

1Ц

ТА

т

р3.4

Г)-4 р5,4

щ

бинарных деревьев (рис. 2). Указанные блоки хранятся и отображаются независимо друг от друга. Данная иерархическая структура формируется в результате работы

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

применением локальных однородных хорошо приспособленных восстанавливающих базисных функций (ЛОХПВБФ) (раздел 1.6). Далее полученная структура подвергается статкодированию на основе алгоритма арифметического кодирования. Обоснован выбор размера блоков изображения, обеспечивающего эффективное сжатие и скорость вычислений. Для решения проблемы межблочных разрывов разработана и реализована двухуровневая процедура формирования исходных, адаптивно сжатых и восстановленных отсчетов блоков регулярной сетки БРИ.

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

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

Р1,1; Р1,5;Р5,1;Р5,5

Р13; Р5,з

И,1;И,2 ИЗ Р4.1; Р4Д Р4.)

Р4.4

Рис. 2. Представление отсчетов блока рис. 1 в виде древовидной иерархической структуры

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

- идентификационная часть описания объекта (поле идентификатор);

- атрибуты (семантика) объекта (поле характеристики);

- межобъектные отношения (поле связей);

- структурированное описание объекта (поле прерываний);

- метрическое описание (метрика);

- текстовое описание;

- мультимедийная информация объекта.

Обязательным является лишь поле идентификатора. Идентификатор объекта состоит из многопозиционного кода объекта и номера объекта. Структура кода определяется классификацией объектов предметной области (рис. 3).

код описание

2 Гидрография и гидротехнические сооружения

2.1 Объекты шдрографической сети

2.1.1 Водные объекты

2.1.2 Территории затапливаемые водой (искусственно, сезонно и т.д.)

2.1.3 Рельеф дна водных объектов

2.2 Объекты суши, омываемые водой

2.2.1 Берега

2.2.2 Острова

2.2.2.1 Остров выр. в м.к.

Рис. 3. Пример классификационного кода объектов и его соответствия текстовому описанию в базе знаний

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

Для представления объектно-ориентированной топологической модели описания объектов ПРД используется динамическая структура позволяющая:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

взаимоположение отрезков (р1,р2) и (р2,рЗ) с отрезками - ребрами сформированного на данный момент графа в*. Возможны следующие ситуации (рис. 6):

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

2) В случае возникновения ситуаций, изобр£1женных на рисунке 6.1 и 6.2 - ребро [г1,г2] удаляется из графа

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

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

Рис. 5. Начальная стадия работы алгоритма

V"1 Г2 \ ^ г1 рЗ V"1 д* Р2 г1 2 г1

6.1) Ребро [г1,г2] графа С* пересекает отрезок (р1,рЗ) объекта множества Р* и точка г1 или г2 совпадает с точкой р2. 6.2) Тока г1 или г2 ребра [г1,г2] графа О* совпадает с тачкой р1 или р2 объекта множества Р*. 6.3) Ребро [г1,г2] графа О* пересекает отрезок (р1 ,р2) объекта множества Р+, но точка гЗ или г2 не совпадает с точкой р! или р2.

Рис. 6. Три ситуации, рассматриваемые в цикле алг оритма поис ка маршрута по бездорожью

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

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

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

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

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

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

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

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

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

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

Большеформатные цифровые графические документы

- модель описания ПРД в формате г" интегрального файла

- геометрическая модель описания БЦГД

- поиск по коду

- поиск по координатам

- поиск по характеристикам

Поиск пути по графу дорог

•Из точки в точку

•С обходом опасной зоны

•Преследование

•Семантика •Лист

•Коллекция

Классификатор предметной области

- работа в терминах, а не в кодах

- классификатор определяет предметную область

- возможность описывать объекты с точностью до характеристики

- возможность автоматического создания шаблона описания объекте

Большеформатные растровые изображения

- геометрическая блочно-иерархмческая модель описания БФРИ

- хранение

- отображение

Поиск пути по бездорожью ^ \

•Формирование объектов препятствий по классификатору •Работа с разнообразными графическими документам!, описывающими труднодоступные территории

Мобильное многофун кцмонал ьн ое ПО дпв обработки ПРД

А

Маршруты, Сопровождение

■Ручмсв построение •Ортодромия •Сопровождение с ЙЖШИШ» •Измерение

Заметки/Перевод

•Описание іаивткя. прзика •Прикрвппаине фото •Ашо-седдание шаблона описання характеристик •Оервоод надписей

30 визуализация

•Клмент-сереерная система ого£ра.»яния 30 изображения заданной точки •Наемга фія внутри .-дани*

Сбор данных

Щ \

•Огаизчмв произвольной характеристики объекта •Кллеит-сврвернзя система загзштического н, данными БД сервера

Поиск карт по коллекции

•На текущее мветоположентя •Соседнюю с имущей парі ой •Другого масштаба на отображаемую ы

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

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

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

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

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

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

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

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. -PP.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. -PP. 573-576.

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

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

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. - PP.213-216.

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

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

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

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

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

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

11. Egorov, А.А. 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. - PP.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. - PP.225-226.

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

14. Egorov, A.A. Autcmoomous 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. - PP.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,

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

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

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

Подписано в печать И- И, /3./7 Формат 60x90 1/16 Печать трафаретная. Бумага офсетная. Усл.печ.л. \,6 Тираж 100 экз. Заказ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Нижегородский государственный архитектурно-строительный университет» 603950, Н.Новгород, Ильинская, 65. Полиграфцентр ННГАСУ, 603950, Н.Новгород, Ильинская, 65

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования «Нижегородский государственный университет им. Н.И.Лобачевского»

На правах рукописи

04201450362 Егоров Андрей Александрович

МОДЕЛИ И АЛГОРИТМЫ ОБРАБОТКИ БОЛЬШИХ ОБЪЕМОВ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ НА МОБИЛЬНЫХ УСТРОЙСТВАХ

05.01.01 - Инженерная геометрия и компьютерная графика

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Ю.Г.Васин

Нижний Новгород, 2013

Аннотация

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

Содержание

Аннотация..............................................................................................................................................2

Содержание............................................................................................................................................3

Введение.................................................................................................................................................4

Глава 1. Модель описания и структура представления болынеформатнмх растровых изображений........................................................................................................................................12

1.1 Основные требования к моделям описания и структурам представления большсформатных изображений.................................................................................................12

1.2 Модели описания изображений.............................................................................................14

1.3 Структуры представления изображений............................................................................16

1.4 Блочно-иерархическая модель описания болынеформатных растровых изображений ............................................................................................................................................................18.

1.5 Выбор размера блоков разбиения.........................................................................................22

1.6 Интерполяционное моделирование......................................................................................24

1.7 Интерполяция и переход к разностному дереву................................................................28

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

1.9 Выводы.......................................................................................................................................33

Глава 2. Модель описания большсформатных цифровых (векторных) графических документов ПРД.................................................................................................................................35

2.1 Обзор существующих моделей описания и структур представления цифровых (векторных) графических документов.......................................................................................36

2.2 Структура объекта в формате интегрального файла.......................................................40

2.3 Геометрическая модель описания цифрового графического документа ПРД............44

2.4 Алгоритм построения индекса болынеформатного цифрового графического документа.........................................................................................................................................47

2.5 Алгоритм поиска объектов но коду......................................................................................51

2.6 Алгоритм поиска объектов по местоположению...............................................................52

2.7 Алгоритм поиска объектов по характеристикам..............................................................53

2.8 Сложноструктурированные запросы...................................................................................54

2.9 Классификатор.........................................................................................................................55

2.10 Индексный файл классификатора......................................................................................60

2.11 Алгоритм поиска описания объектов по индексному файлу классификатора.........63

2.12 Выводы.....................................................................................................................................63

Глава 3. Алгоритмы автоматической прокладки маршрута....................................................65

3.1 Краткий обзор существующих алгоритмов прокладки маршрута................................65

3.2 Задача прокладки маршрута при отсутствии графа дорожной сети.............................67

3.3 Алгоритм прокладки маршрута при отсутствии графа дорожной сети.......................69

3.4 Задача поиска маршрута по графу дорожной сети............................................................71

— 3.5 Алгоритм построения графа дорожной сети.......................................................................72

3.6 Выводы.......................................................................................................................................75

Глава 4. Программное обеспечение................................................................................................77

4.1 Структура программного комплекса...................................................................................77

4.2 Общее описание программных подсистем..........................................................................92

4.3 Применение утилит и библиотек..........................................................................................92

4.4 Выводы.......................................................................................................................................95

Заключение..........................................................................................................................................96

Список сокращений...........................................................................................................................98

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

Введение

В.1 Актуальность

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

Современный рынок компьютерной техники становиться все более дифференцированным и достаточно большую его составляющую начинают занимать так называемые «мобильные» устройства с ограниченной памятью, вычислительными ресурсами центрального процессора и малым размером экрана. Подобные устройства применяются как широким классом пользователей -обычными людьми (смартфоны, карманные персональные компьютеры, навигаторы, умные очки и часы, и т.д.), так и для спецназначения (мобильные роботы, летательные и глубоководные подводные аппараты, передвижные диспетчерские центры, индивидуальные средства МЧС, ЗБ навигация и т.д.). Однако созданное программное обеспечение этого класса вычислительной техники имеет узкую специализацию решаемых задач в рамках определенной

предметной области, ограниченные размеры и малое количество обрабатываемых графических документов, объектной составляющей, атрибутивных и пространственно-логических связей, отсутствие механизма быстрого поиска данных при реализации разнообразных сложно-структурированных запросов и т.д. [77,81-86,89-96].

Расширение сферы использования и усложнение решаемых задач привели к необходимости хранения и интегрированной обработки данных большого множества болынеформатных графических документов разной тематической направленности, разных масштабов, проекций и систем координат, космо- и аэрофото изображений, постановке задачи сбора данных 3D моделирования и 3D визуализации пространственных объектов (зданий, сооружений, отдельных поэтажных планов), навигации в закрытых помещениях на базе 3D моделирования окружающего пространства, выбора маршрута и контроля движения по нему в условиях труднодоступных и малоизученных районов. Указанные проблемы в своих работах рассматривали такие ученые, как Васин Ю.Г., Кетков Ю.Л., Ротков С.И., Сергеев В.В., Клименко C.B., Рябко Б.Я., Бурт П.Дж., Кунт М., Роберте М.Г., Клеари Дж.Г. и другие. Однако необходимо дальнейшее развитие моделей описания и структур представления, методов и алгоритмов обработки и сжатия больших объемов графической информации, повышение интеллектуальности инструментальных средств обработки ПРД (обеспечение работы в терминах проблемной области, а не в кодах), дальнейшее повышение удобства работы в разных проблемных областях, решение тематических задач (прокладка маршрута по бездорожью и др.) с учетом ограниченности емкостных и вычислительных ресурсов мобильных устройств. Вышесказанное определяет актуальность данной работы.

В.2 Цели и задачи

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

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

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

2) Разработка модели описания и структуры представления большеформатных цифровых (векторных) графических документов (БЦГД) с учетом реализации быстрого поиска данных для решения разнообразных тематических задач.

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

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

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

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

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

В.4 Научная новизна

Научная новизна диссертационной работы состоит в том, что:

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

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

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

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

В.5 Практическая ценность

В основу работы положены результаты, полученные автором в ходе исследований, проводимых по плану научно-исследовательской работы Министерства образования и науки Российской Федерации, научно-исследовательских и опытно-конструкторских работ по хоздоговорам с ЗАО «Транзас» и ООО «Чарт-пилот». Работа выполнена при финансовой поддержке РФФИ проект №05-01-00590, проект №10-07-00330, проект №11-07-12049-офи-М, проект №12-07-33107 мол_а_вед.

Результаты диссертационной работы использованы ООО «Чарт-пилот» в автоматизированной системе передачи по сети общего пользования сжатых калек-вклеек и трейсинг-калек на суда гражданского флота, используются в составе ГИС «Терра», в научно исследовательском институте прикладной математики и кибернетики Нижегородского государственного университета им. Лобачевского, для решения широкого класса задач обработки большеформатных растровых изображений и ПРД на мобильных устройствах, а также в учебном процессе на факультете вычислительной математики и кибернетики (ВМК) Нижегородского государственного университета им. Н. И. Лобачевского, на кафедре интеллектуальных информационных систем и геоинформатики (ИИСГео).

Разработано и зарегистрировано в официальном реестре программ для ЭВМ (РФ) программное обеспечение «Программный комплекс обработки пространственно-распределенных данных и большеформатных изображений на малых платформах».

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

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

В.6 Апробация полученных результатов

Результаты диссертационной работы докладывались и обсуждались на международной конференции «Pattern Récognition and Image Analysis: New Information Technologies» (Йошкар-Ола, 2007 г., Нижний Новгород, 2008 г., Санкт-Петербург, 2010 г., Самара, 2013 г.), на конференции «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2007 -2010 гг.), на Всероссийской конференции с международным участием «Модели, методы и программные средства» (Нижний Новгород, 2007г.), на 8-м Открытом российско-немецком семинаре «Распознавание образов и понимание изображений» (Нижний Новгород, 2011 г.).

Основные результаты исследований опубликованы в 15 научных работах, 3 из которых опубликованы в изданиях, рекомендованных ВАК Минобрнауки России. Получено свидетельство о регистрации электронного ресурса №19291 от 24.06.2013 на разработанное программное обеспечение.

В.7 Основные положения, выносимые на защиту

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

2. Геометрическая модель описания болыиеформатных цифровых (векторных) графических документов, структура их представления, а также алгоритмы поиска данных БЦГД.

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

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

В.8 Содержание работы

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

Диссертация состоит из четырех глав:

1. Модель описания и структура представления больше