Содержание к диссертации
Введение
Глава 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 Классификатор
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
Список литературы
- Модели описания изображений
- Структура объекта в формате интегрального файла
- Алгоритм поиска объектов по характеристикам
- Алгоритм прокладки маршрута при отсутствии графа дорожной сети
Введение к работе
Актуальность работы. В настоящее время остается актуальной проблема продуктивного использования пространственно-распределенной информации о ключевых объектах производственной, коммунальной и социальной сфер деятельности. Для решения этой проблемы используют геоинформационные системы (ГИС), которые прочно вошли в список обязательных инструментов профессионалов различных направлений: геологов, геофизиков, инженеров-нефтяников, инженеров по обслуживанию объектов и различных коммуникаций, землемеров, юристов, экологов, спасателей, управленцев и т.д. Цифровое графическое представление пространственно-распределенных данных (ПРД) - это большое число болыпеформатных графических документов различной тематической направленности. Примерами таких документов могут служить цифровые топографические и морские навигационные карты, поэтажные планы зданий и сооружений, тематические карты различной направленности: по геологии, землевладению, экологии, хозяйственной инфраструктуре и пр., а также связанные с ними базы данных, результаты полевых исследований и измерений, материалы космической и аэрофотографической съемки.
Современный рынок компьютерной техники становиться все более дифференцированным и достаточно большую его составляющую начинают занимать так называемые «мобильные» устройства с ограниченной памятью, вычислительными ресурсами центрального процессора и малым размером экрана. Подобные устройства применяются как широким классом пользователей - обычными людьми (смартфоны, карманные персональные компьютеры, навигаторы, умные очки и часы, и т.д.), так и для спецназначения (мобильные роботы, летательные и глубоководные подводные аппараты, передвижные диспетчерские центры, индивидуальные средства МЧС, 3D навигация и т.д.). Однако созданное программное обеспечение этого класса вычислительной техники имеет узкую специализацию решаемых задач в рамках определенной предметной области, ограниченные размеры и малое количество обрабатываемых графических документов, объектной составляющей, атрибутивных и пространственно-логических связей, отсутствие механизма быстрого поиска данных при реализации разнообразных сложноструктурированных запросов и т.д.
Расширение сферы использования и усложнение решаемых задач привели к необходимости хранения и интегрированной обработки данных большого множества болыпеформатных графических документов разной тематической
направленности, разных масштабов, проекций и систем координат, космо- и аэро-фото изображений, постановке задачи сбора данных 3D моделирования и 3D визуализации пространственных объектов (зданий, сооружений, отдельных поэтажных планов), навигации в закрытых помещениях на базе 3D моделирования окружающего пространства, выбора маршрута и контроля движения по нему в условиях труднодоступных и малоизученных районов. Указанные проблемы в своих работах рассматривали такие ученые, как Васин Ю.Г., Кетков Ю.Л., Ротков СИ., Сергеев В.В., Клименко СВ., Рябко Б.Я., Бурт П.Дж., Кунт М., Роберте М.Г., Клеари Дж.Г. и другие. Однако необходимо дальнейшее развитие моделей описания и структур представления, методов и алгоритмов обработки и сжатия больших объемов графической информации, повышение интеллектуальности инструментальных средств обработки ПРД (обеспечение работы в терминах проблемной области, а не в кодах), дальнейшее повышение удобства работы в разных проблемных областях, решение тематических задач (прокладка маршрута по бездорожью и др.) с учетом ограниченности емкостных и вычислительных ресурсов мобильных устройств. Вышесказанное определяет актуальность данной работы.
Объектом исследования являются модели и методы обработки пространственно-распределенных данных и большеформатных изображений на мобильных устройствах.
Предметом исследования являются модели описания и структуры представления, алгоритмы хранения и обработки пространственно-распределенных данных и большеформатных изображений на мобильных устройствах.
Цель работы - разработка и развитие моделей описания и структур представления большеформатных растровых изображений (БФРИ) и объектов ПРД, а также алгоритмов хранения, поиска и обработки больших объемов большеформатных графических данных на мобильных устройствах.
Для достижения поставленной цели требуется проведение анализа существующих моделей и структур представления объектов ПРД, алгоритмов хранения и обработки больших объемов большеформатных графических данных, анализ прикладных задач обработки ПРД и алгоритмов их решения, а также решение следующих основных задач:
1) Разработка модели описания большеформатных растровых изображений и структуры их представления для эффективной организации их хранения, визуализации и масштабирования.
-
Разработка модели описания и структуры представления болыпеформатных цифровых (векторных) графических документов (БЦГД) с учетом реализации быстрого поиска данных для решения разнообразных тематических задач.
-
Разработка для мобильных устройств алгоритма прокладки маршрута движения по бездорожью на основе информации БЦГД.
-
Разработка алгоритма построения матрицы переходов, используемой в алгоритме Дейкстры, для решения задач прокладки маршрута движения по графу дорожной сети на мобильных устройствах.
-
Разработка и создание универсального программного обеспечения для мобильных устройств, реализующего разработанные модели, структуры, алгоритмы и позволяющего решать широкий класс задач обработки болыпеформатных графических документов на мобильных устройствах.
Методы исследования. В диссертационной работе используются методы дискретной математики, теории графов, математической логики, вычислительной геометрии и математического анализа, теории информации, математического моделирования.
Достоверность и обоснованность полученных в работе результатов и
выводов обеспечиваются корректным применением аппарата компьютерной
геометрии и графики, теории графов, математического моделирования и
подтверждается положительными результатами проведенного
экспериментального тестирования алгоритмов и программ и опытной эксплуатации разработанного программного обеспечения.
Научная новизна состоит в том, что:
-
Разработана блочно-иерархическая модель описания болыпеформатных растровых изображений графических документов (БРИГД), позволяющая избежать независимого дополнительного хранения и сжатия последних столбцов и строк соседних блоков, избежать геометрических артефактов, связанных с межблочными разрывами изображений; отличающаяся способом формирования независимых блоков, высоким коэффициентом сжатия, меньшей сложностью вычислений при масштабировании и визуализации изображения без межблочных разрывов.
-
Разработана геометрическая модель описания большеформатных цифровых (векторных) графических документов (БЦГД), позволяющая осуществлять поиск данных при реализации разнообразных метрических и семантических запросов, включая сложно-структурированные запросы, а также работать в терминах любой предметной области, а не в кодах; отличающаяся
иерархической структурой представления БЦГД, использованием иерархического семантического описания объектов ПРД и наличием прямоугольников, описывающих метрику отдельных объектов, что обеспечивает более высокое быстродействие алгоритмов поиска данных.
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 г.).
Основные положения, выносимые на защиту:
-
Блочно-иерархическая модель описания болыпеформатных растровых изображений, структура их представления для эффективной организации хранения, визуализации и масштабирования.
-
Геометрическая модель описания болыпеформатных цифровых (векторных) графических документов, структура их представления, а также алгоритмы поиска данных БЦГД.
-
Алгоритм прокладки маршрута движения по бездорожью на основании информации цифровых болыпеформатных графических документов, с использованием разработанной геометрической модели описания цифровых графических документов, содержащих ПРД. Алгоритм построения матрицы переходов, используемой в алгоритме Дейкстры, для решения задач прокладки маршрута движения по графу дорожной сети с использованием выбранной модели описания объектов ПРД.
Публикации. Основные результаты исследований опубликованы в 15 научных работах, 3 из которых опубликованы в изданиях, рекомендованных ВАК Минобрнауки России. Получено свидетельство о регистрации электронного ресурса №19291 от 24.06.2013 на разработанное программное обеспечение.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы - 111 машинописных страниц, список литературы включает 97 наименований.
Модели описания изображений
Чрезвычайно остро проблема эффективной организации видеоинформации проявляется в задачах геоинформационных систем (ГИС), в силу большого объема и разнородности обрабатываемой информации и высоких требований к оперативности, и при работе в глобальных вычислительных сетях (ГВС), в силу низкой скорости и/или высокой стоимости передачи информации.
Существенной особенностью ГИС по сравнению с другими предметными областями является очень широкое разнообразие типов данных, подлежащих хранению и обработке на различных этапах работы с пространственно-распределенной информацией: сканированные и программно-формируемые географические карты, планы, аэрофотоснимки и космические снимки, фотографические изображения объектов, а также матрицы высот, уровней затопления, карты концентрации химических веществ в атмосфере, температурных распределений и других пространственно-распределенных данных. Ко всем этим типам данных предъявляются различные требования по уровню детализации, динамическому диапазону и допустимой точности представления. Тем не менее, все они обладают растровой организацией данных и в процессе хранения, передачи и доступа могут рассматриваться как растровые изображения с различными классами атрибутов пикселей.
Специфика изображений ГИС проявляется, в первую очередь, в относительно больших размерах и высоких требованиях к уровню детализации. Объем информации, содержащейся на таких документах, имеющих размер порядка ста сантиметров по горизонтали и по вертикали, составляет от сотен мегабайт до единиц и десятков гигабайт. Таким образом, непосредственная работа с такими большеформатными изображениями, в том числе и оперативная визуализация, существенно затруднена без эффективной технологии хранения и доступа. Кроме того, к картографическим документам предъявляются жесткие требования по точности представления объектов топокарт и топопланов. Практические задачи и технологии обработки картографических и графических данных накладывают дополнительное, но немаловажное требование высокой скорости распаковки данных, обеспечивающей приемлемую производительность всех модулей обработки картографических растровых документов (например, модуля визуализации). Технология хранения изображения должна обеспечивать достижение заданной скорости распаковки изображения при наличии большой степени его сжатия. Производительность доступа к фрагментам изображения не должна зависеть от размеров растра или от расположения требуемого фрагмента внутри растра. Суммируя вышесказанное, требуется разработать единую технологию построения моделей описания и структуры представления растровых данных различной природы: фотографические и технические изображения (монохромные, полутоновые и полноцветные в произвольном цветовом пространстве, изображения с механизмом индексации цвета), матрицы пространственно-распределенных данных. При этом, модели описания и структуры представления должны удовлетворять следующим требованиям: высокая степень компрессии; целочисленные алгоритмы сжатия/восстановления; высокое качество изображения, что, как правило, означает сжатие без потерь и/или с контролем погрешности по метрике Чебышева; высокая скорость построения модели описания и структуры представления; высокая скорость восстановления отсчетов изображения по заданной модели описания и структуре представления; оперативный доступ к заданному фрагменту изображения, т.е. производительность доступа к фрагментам изображения должна зависеть от объема получаемого фрагмента, но не от размеров всего растра или от расположения требуемого фрагмента внутри растра; масштабирование изображений, данное требование подразумевает возможность изменения размеров изображения без существенных вычислительных затрат и потерь качества изображения. В ГИС видеоинформация используется для принятия различных управленческих решений, поэтому необходимо формировать эффективную структуру представления информации для обеспечения эффективных методов и алгоритмов обработки в задачах принятия решений.
Решению проблемы эффективного хранения и обработки изображений способствует применение адекватной модели описания и представления графической информации. Выделим основные классы подобных моделей.
Растровые модели.
В рамках растровой модели изображение рассматривается как совокупность пикселей, т.е. элементарных элементов изображения, расположенных в некоторой (обычно прямоугольной) области, называемой растром пикселей. Атрибут пикселя есть дискретизированное значение цветовой характеристики изображения в геометрическом центре пиксельной площадки. Иногда, в целях устранения эффектов дискретизации, его заменяют интегралом цветовой характеристики по пиксельной площадки. Под глубиной представления цвета пикселя понимают разрядность атрибута пикселя.
Растровый подход к представлению изображений, обеспечивая достаточно производительную выборку графической информации, позволяет любое изображение хранить сколь угодно точно. Действительно, каждое изображение можно разбить прямоугольной сеткой с необходимой точностью. Адекватность цветового представления каждого полученного пикселя определяется глубиной представления цвета. Любое необходимое количество полутонов можно достичь выбором соответствующей разрядности атрибутов пикселей.
Структура объекта в формате интегрального файла
ИДЕНТИФИКАТОР - идентификатор объекта является первичным ключом для его поиска в базе. Он состоит из многопозиционного кода объекта и номера объекта. Структура кода определяется классификацией объектов предметной области в соответствии с принятым информационно-терминологическим обеспечением. Каждая позиция кода соответствует определенному уровню в иерархии этой классификации. Для идентификации разных объектов с одинаковым кодом применяется номер объекта. Каждому объекту из группы объектов с одинаковым кодом присваивается уникальный (в данной группе объектов) номер. Таким образом, пара значений кода и номера однозначно идентифицирует объект. Также идентификатор может содержать набор характеристик типа Да/Нет (например, признак замкнутости метрики объекта) и ключ (уровень) доступа к объекту, с помощью которого осуществляется разграничение доступа к объекту и защита от несанкционированного доступа к нему. Идентификационная часть является единственной обязательной частью объекта в формате интегрального файла.
ХАРАКТЕРИСТИКИ - это поле содержит семантическое описание объекта. Каждая характеристика имеет свой тип (например, текст, географическая координата, число, сложная характеристика - включает в себя другие характеристики и т.д.), классификационный код характеристики (аналог кода объекта) и значение.
СВЯЗИ - это поле предназначено для описания произвольных пространственно - логических и топологических связей объекта в пределах базы данных. Каждая связь представляет собой ссылку на другой объект (его код и номер).
ПРЕРЫВАНИЯ — это поле содержит связи второго типа — прерывания (физические связи между объектами, требующие их метрического описания). Оно используется для: заимствования метрики из других объектов; описания структурных компонент данного объекта или «привязанных» к данному объекту в целях его целостного описания (например, отметки уреза воды у рек, мосты на дорогах и т.п.); для структурирования объекта по характеристике (например, выделение участков загрязнения дороги); для описания составных объектов, при котором нужен учет порядка следования их компонентов; для описания физических разрывов в контуре объекта.
Каждое прерывание имеет код и номер объекта, связанного с данным объектом и номер точки прерывания в метрике объекта.
МЕТРИКА - это поле содержит метрическое описание объекта - линейную совокупность координат точек в системе листа.
КВАДРАТЫ - это поле содержит список заранее (на этапе ввода) определенных районов на карте (квадратов). Каждый район имеет список (код, номер, адрес в интегральном файле) объектов содержащихся в нем. Содержимое поля квадратов не контролируется средствами СУБГД, соответственно теоретически в нем можно хранить любые данные.
ТЕКСТ - поле пользуется для хранения любой текстовой информации объекта Текстовое описание объекта может содержать любой набор символов ASCII и должно заканчиваться нуль-символом \0 .
МУЛЬТИМЕДИА - поле предназначено для хранения различной дополнительной информации об объекте, например, растрового изображения объекта в каком-либо графическом формате, звукового сопровождения, видеофильма, специального представления объекта для быстрого его отображения и т.п.
Главной особенностью объекта в формате интегрального файла является его динамическая структура, позволяющая: иметь переменный размер всех полей объекта; хранить объект в базе данных в любом сочетании его полей; выдавать пользователю объект из базы данных в любом сочетании его полей; эффективно реализовывать структурированное описание объектов, учитывая пространственно-логические и топологические отношения между объектами ПРД.
Для организации эффективного поиска объектов по координатам и кодам, а также отбора объектов по характеристикам разработана геометрическая модель описания цифрового графического документа ПРД и структура его представления, основанная на R-деревьях (рис. 10). [25, 55, 80]. Дерево или древовидная структура данных - это связанный граф, не содержащий циклы. Узлы графа являются узлами дерева. Один из узлов обозначается как корень дерева. Корень не имеет узлов - «родителей», только потомки. Узлы, которые не имеют потомков, называются листьями дерева. Формально дерево можно описать в виде структуры T={t,{Tl,T2...Tn}}, где t - корень дерева, а подмножество {Т1,Т2...Тп} содержит указатели на все поддеревья, корнями которых являются потомки корня t.
Разработанная модель описания цифрового графического документа ПРД основана на регулярной иерархии прямоугольных четырехугольников и геометрических вычислениях принадлежности объектов одному из них и организована следующим образом:
1) корень древовидной структуры содержит ссылки на все объекты. графического документа, а также координаты углов прямоугольника, описывающего эти объекты;
2) узлы содержат ссылки на подмножество объектов своего родителя и координаты углов прямоугольника, описывающего эти объекты. Также, узлы содержат список значений первых позиций кода своих объектов и часть кода, являющуюся одинаковой у всех объектов группы (при наличии), например, у кодов 5.2.2.3 и 5.2.6.3 эта часть будет 5.2, т.е. первые две позиции. На каждом уровне иерархии, каждый объект находится лишь в одном узле;
3) листья содержат код, номер, адрес объекта в базе данных (БД), а также координаты углов описывающего данный объект прямоугольника;
4) разбиение объектов по группам осуществляется в соответствии с распределением объектов к одному из четырех ближайших углов описывающего все объекты родителя прямоугольника - объект попадает в одну из четырех групп, которая соответствует ближайшему к центру масс объекта углу;
5) объекты, не имеющие метрического описания, заносятся в отдельное дерево, которое строится в соответствии с древовидным представлением кодов объектов и в конце подцепляется к корню дерева.
Алгоритм поиска объектов по характеристикам
Любая программа, позволяющая осуществлять навигацию, обязательно должна уметь отвечать на два вопроса: «где я» и «куда мне идти». Это то, для чего была изначально придумана карта и то, для чего большинство людей обращается к ней за помощью и сегодня. На вопрос «где я» успешно отвечают такие функции как - отображение карт и определение местоположения по GPS[39], а вот вопрос «куда мне идти» не так прост, но помочь пользователю ответить на него помогает работа с маршрутами.
Современные коммерческие приложения уже достаточно давно не мыслимы без автоматической прокладки маршрута по дорожной сети[77,81-86,89-96]. Примером может служить простейшая графовая задача отыскания кратчайшего пути из точки в точку по дорожной сети, она решается практически в любом навигационном программном обеспечении (ПО). Но как только выделить такой граф становится невозможно, по какой либо причине (морские сообщения, движение по пустыне, по открытой местности и т.д.), работа с маршрутами в таких приложениях становится невозможной. Навигация по бездорожью (при отсутствии графа дорожной сети) - значительный класс задач, который не решается ни в одном навигационном ПО, даже в морских навигаторах. В настоящий момент примитивные методы используются в играх и развиваются в робототехнике [36,40,49,56,57,61,62,75,78,79,87,97].
На практике часто возникает необходимость проложить курс от пункта А в пункт Б в заданной области, содержащей зоны препятствий. Типичной проблемой в поиске пути является обход зон препятствий.
Многие геоинформационные задачи удобно решать с помощью теории графов. Хотя простейшие техники обхода препятствий (такие как «игнорирование препятствий до столкновения с ними» или «трассировка вокруг препятствия» и Д-Р- [97]) часто могут проделать допустимую или даже адекватную работу, существуют ситуации, в которых единственно разумный подход это планирование всего пути перед началом перемещений. На сегодняшний день примером таких алгоритмов могут служить алгоритмы поиска в ширину и в глубину, двунаправленный поиск в ширину, алгоритм Дейкстры, алгоритм «лучший-первый», алгоритм А и т.д.[78,79,87,97]. Но наиболее распространенным из них, учитывающий стоимость пути и не более требовательный к системным ресурсам, чем другие алгоритмы, является алгоритм Дейкстры [2,32,41,47].
Все приведенные выше методы поиска предполагали, что пространство дискретно (например, разбито на квадратные или шестиугольные ячейки, как в большинстве компьютерных игр). Но что, если позиции и объектов и препятствий представлены в виде пиксельных координат экрана, а информации о точках между ними нет? Рисунок 12А показывает примерное расположение объектов.
Для ответа на эти условия поиска, можно заглянуть в область робототехники и увидеть какие подходы используются для мобильных роботов. Не удивительно, что многие подходы находят способы для сведения непрерывного пространства к нескольким дискретным вариантам. После этого, они обычно используют алгоритм Дейкстры для поиска желаемого пути.
Все известные подходы такие как, например, разбитие на ячейки (рис. 12В), точки видимости (рис. 12С), выпуклые полигоны (рис. 12D), квадро-деревья (рис. 12Е), обобщенные цилиндры (рис. 12F), потенциальные поля и многие другие [36,40,49,56,57,61,62,75,78,79,87,97] имеют свои плюсы и минусы при решении определенных задач. Они нашли свое применение в играх, в задачах поиска пути на настольных компьютерах. Но если говорить о задачах ГИС на мобильных устройствах, то следует отметить тот факт, что все эти методы предполагают, либо постоянное хранение информации о переходе из одной точки в другую (для всех точек), либо наличие полной информации об объектах препятствий перед началом вычислений (при каждом новом поиске). Чтение всех объектов карты, зачастую неоднократное, это достаточно долгий процесс, требующий значительных вычислительных ресурсов.
В задаче поиска маршрута по бездорожью заданы две точки (рис. 13): А - точка старта и В - точка назначения в заданной области, содержащей зоны препятствий (объекты препятствия Р ) представленными соответственно модели описания БЦГД. Между этими двумя точками следует проложить маршрут из точки А в точку В, Ри"сЛЗ Начальная стадия работы огибающий области препятствий. алгоритма
Ориентированность данной задачи идет именно на мобильные устройства -поэтому следует помнить об ограниченности вычислительных ресурсов. Например, прочитать данные метрики всех объектов перед или во время выполнения задачи подобно алгоритмам, применяемым в играх, нет возможности - чтение всех точек метрики всех объектов займет несколько минут (возможно, десятки). Построить граф переходов из каждой точки в каждую невозможно, во-первых, по той же причине - нет информации о всех объектах препятствиях, а во-вторых, недостаточно памяти для хранения этого графа, ведь размеры карты достигают нескольких тысяч точек лишь в одном измерении.
Описанный ниже алгоритм предполагает изначально лишь наличие двух точек - начала и конца маршрута. Алгоритм основан на использовании разработанной геометрической модели описания цифрового графического документа ПРД. В процессе выполнения, алгоритм считывает метрику только тех объектов, которые непосредственно лежат на прокладываемом маршруте. В основе работы алгоритма заложен итеративный процесс построения графа возможных промежуточных маршрутов движения при обходе очередного встреченного объекта-препятствия, с плавным его обтеканием (рис. 14), и решение оптимизационной задачи по алгоритму Дейкстры. Данный подход g позволяет решать задачу поиска маршрута между двумя точками по бездорожью в Рис. 14 Принцип работы условиях ограниченных ресурсов мобильных алгоритма прокладки маршрута по бездорожью устройств и избежать получения неадекватных результатов при вытянутых и загибающихся препятствиях, присущих некоторым существующим алгоритмам, а также не требует выделения больших объемов оперативной памяти для хранения всех контуров объектов-препятствий и проведения вычислений на графах большой размерности.
Алгоритм прокладки маршрута при отсутствии графа дорожной сети
В главе дается описание созданного программного обеспечения, разработанного на базе предложенных моделей, структур и алгоритмов для мобильных устройств. Описывается структура программного комплекса, функционал, интерфейс, модули, утилиты и библиотеки. Также приводится описание разработанных алгоритмов поиска карт по их коллекции в памяти устройства, алгоритм автоматического сопровождения на маршруте и технология автоматического построения шаблона описания указанного объекта ПРД.
Разработанное программное обеспечение позволяет обрабатывать большеформатные растровые и векторные графические документы, работать в любой предметной области в терминах, а не в кодах, и решать широкий спектр прикладных задач для работы с графическими документами, объектами ПРД, маршрутами и навигацией. Заключение
В данной диссертационной работе разработана блочно-иерархическая модель описания большеформатных растровых изображений графических документов, позволяющая избежать независимого дополнительного хранения и сжатия последних столбцов и строк соседних блоков, избежать геометрических артефактов, связанных с межблочными разрывами изображений. Выбраны эффективный размер блока разбиения изображения в модели описания большеформатного растрового изображения и эффективные параметры функции интерполяции. Это позволило существенно снизить временную и емкостную. сложность вычислений в задачах оперативного отображения, масштабирования, хранения и обработки больших объемов большеформатных графических данных на мобильных устройствах. Представление блоков разбиения изображения в виде иерархической структуры позволило осуществлять визуализацию изображения на этапе загрузки с постепенным улучшением детализации, а также выполнять масштабирование изображения, используя данные до определенного уровня иерархической структуры представления (без необходимости выполнения дополнительных вычислений). Приведенные в работе результаты экспериментальной апробации описанной модели подтвердили ее превосходство. над существующими распространенными форматами.
Разработаны геометрическая модель описания большеформатных цифровых (векторных) графических документов, структура их представления, а также алгоритмы поиска данных цифрового графического документа на мобильных устройствах. Экспериментальные апробации на разработанном программном обеспечении для мобильных устройств подтвердили их эффективность. Выбранная модель описания объектов позволяет строить высокоэффективные алгоритмы решения различных прикладных задач, работать в терминах предметной области пользователя, а также с высокой эффективностью осуществлять поиск данных и выполнять сложно-структурированные запросы на мобильных устройствах.
Разработан алгоритм поиска маршрута движения по бездорожью. В отличие от известных методов, разработанный алгоритм не требует выделения оперативной памяти для хранения всех контуров объектов-препятствий и проведения вычислений на графах большой размерности, позволяет избежать получение неадекватных результатов при вытянутых и загибающихся препятствиях, присущих некоторым существующим алгоритмам, работать с большеформатными цифровыми документами, содержащими большое число объектов препятствий (тип которых можно указать непосредственно перед началом поиска), в режиме реального времени и в условиях оіраниченньїх ресурсов мобильных устройств. Для решения задач прокладки маршрута движения по графу дорожной сети разработан алгоритм построения матрицы переходов, используемой в алгоритме Дейкстры. Разработанный алгоритм позволяет решать задачи прокладки маршрутов на мобильных устройствах как при наличии дорожной сети, так и по бездорожью в труднодоступных районах.
Разработан программный комплекс для мобильных устройств, реализующий предложенные модели, структуры и алгоритмы. Программный комплекс может использоваться для визуализации болыпеформатных растровых изображений, обработки и поиска данных на БЦГД, поиска маршрута по графу дорожной сети и по бездорожью.
