Модели и алгоритмы обработки больших объемов графической информации на мобильных устройствах тема диссертации и автореферата по ВАК РФ 05.01.01, кандидат наук Егоров, Андрей Александрович

• Егоров, Андрей Александрович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Егоров, Андрей Александрович

Содержание

Аннотация

Содержание

Введение

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

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

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

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

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

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

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

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

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

1.9 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

2.12 Выводы

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

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

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

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

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

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

3.6 Выводы

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

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

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

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

4.4 Выводы

Заключение

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

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

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы обработки больших объемов графической информации на мобильных устройствах»

Введение

В.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. Модель описания и структура представления большеформатных растровых изображений.

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

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

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

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

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

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

4. Программное обеспечение.

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

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

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

Чрезвычайно остро проблема эффективной организации видеоинформации проявляется в задачах геоинформационных систем (ГИС), в силу большого объема и разнородности обрабатываемой информации и высоких требований к оперативности, и при работе в глобальных вычислительных сетях (ГВС), в силу низкой скорости и/или высокой стоимости передачи информации.

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

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

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

• высокая степень компрессии;

• целочисленные алгоритмы сжатия/восстановления;

• высокое качество изображения, что, как правило, означает сжатие без потерь и/или с контролем погрешности по метрике Чебышева;

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

• высокая скорость восстановления отсчетов изображения по заданной модели описания и структуре представления;

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

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

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

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

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

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

Являясь аппаратно ориентированным, растровый подход к хранению изображений обеспечивает высокую скорость взаимодействия с устройствами

ввода/вывода графической информации соответствующего типа. Однако объем графической информации при таком подходе традиционно велик.

Векторные модели.

К векторным относятся модели изображений, использующие описание изображения в виде набора графических примитивов, т.е. объектов из заранее определенного множества. Атрибутами графического примитива могут быть параметры аффинного преобразования, задающие положение и размеры объекта, а также цвет и, возможно, другие характеристики. Хотя в названии данного подхода и присутствует термин «векторный», предполагается использование не только кусочно-линейных моделей представления объектов изображения. Например, одним из способов описания графических данных является задание границ объектов всевозможными сплайновыми кривыми или локальными однородными хорошо приспособленными базисными функциями (ЛОХПБФ).

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

Модели синтеза.

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

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

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

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

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

Матричное представление данных. Простейшая структурная модель растрового изображения - представление его непосредственно матрицей атрибутов пикселей. Основное достоинство матричного представления -сохранение структуры исходного изображения (пространственной организации и цвета). Иногда такое представление графических данных называют прямым; оно позволяет легко реализовать последовательную и параллельную обработку всего изображения. Поскольку классические алгоритмы кодирования требуют одномерного входного потока, практически всегда матричное представление данных сочетается с редукцией размерности, путем применения того или иного метода развертки [1,27,28,29,30,37].

Иерархическое представление данных. Иерархическое представление данных основывается на применении иерархических структур, таких как двоичные деревья, квадродеревья, деревья квадрантов и т.д. При этом изображение представлено иерархическим набором матриц атрибутов пикселей -упорядоченной последовательностью нескольких изображений различного разрешения, сходящихся к исходному [1,5,7,8, 9,20,21,33,35,46].

В памяти ЭВМ хранится двухмерный массив отчетов к-го уровня (исходного изображения, прореженного в 2к раз по каждой из координат), и набор ошибок интерполяции, позволяющих получить массивы отсчетов уровней к-1, к-2,...прореженные соответственно в 2Ы, 2к~2,...раз, вплоть до нулевого уровня — полного изображения. На каждом иерархическом уровне массив отсчетов вместе с ошибками интерполяции используется для получения пропущенных отсчетов следующих, более детальных уровней.

С целью уменьшения поуровневых ошибок интерполяции используют различные интерполирующие функции. В работах [5,7,8,9] предложено в качестве интерполирующих функций использовать локальные однородные хорошо приспособленные сглаживающие ГЛ и восстанавливающие Кд функции.

Стандартные растровые форматы хранения изображений (BMP, GIF, JPEG, PCX, TARGA, TIFF и др.) основаны на последовательной записи графической информации при помощи построчной развертки растра [28]. Однако встречаются некоторые вариации построчной развертки. Так, одна из модификаций формата GIF [50] использует построчную развертку с четырехпроходным чередованием строк для ускорения адаптивной настройки алгоритма LZW [76]. В формате JPEG [59] построчной развертке подвергаются прямоугольные блоки данных размером 8x8 пикселей, к которым применяется дискретное косинусное преобразование.

Пусть размер растра сверхбольшого изображения равен N*M. Рассмотрим задачу получения фрагмента сверхбольшого изображения размером n*m, левый верхний угол которого расположен в точке (Х,У). В случае сверхбольшого изображения (N»n, M»m) при использовании формата хранения с построчной разверткой растра необходимо полностью распаковать Y+m строк изображения. Следовательно, процесс предварительной распаковки предшествующих строк (с О по Y-1) приведет к многократному уменьшению производительности чтения фрагмента изображения. Т.е. такой формат хранения изображений реализует только последовательный (построчный) доступ к пикселям сверхбольшого изображения, что во многих случаях недопустимо.

Список литературы диссертационного исследования кандидат наук Егоров, Андрей Александрович, 2013 год

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

1. Александров В.В. Представление и обработка изображений. Рекурсивный подход. / Александров В.В., Горский Н.Д. - JL: Наука, 1985.

2. Ахо A.B. Структуры данных и алгоритмы / Ахо A.B., Ульман Д.Д. -Москва, 2000.

3. Васин Ю.Г. Кодирование ЭКГ неравномерными отсчетами. / Васин Ю.Г., Савина Т.В. // Сборник «Биологическая и медицинская кибернетика» - М., 1974 - 4.4. -С.73-74.

4. Васин Ю.Г. Сжатие исходного описания ЭКГ-сигналов. / Васин Ю.Г. // «Теория и практика разработки автоматизированных медицинских информационных систем» Труды Республиканской конференции - Киев, 1975. -С.69-75

5. Васин Ю.Г. Рекуррентные алгоритмы адаптивного сжатия с использованием хорошо приспособленных локальных восстанавливающих функций. / Васин Ю.Г., Бакараев В.П. // Математическое обеспечение САПР: Межвуз. сб. - Горький: ГГУ, 1978, - вып. 1.

6. Васин Ю.Г. Хорошо приспособленные базисы и задачи обработки экспериментальной информации: учебное пособие. / Васин Ю.Г. - Горький: ГГУ, 1979.

7. Васин Ю.Г. Оптимизация описания исходных данных в диалоговых системах решения задач классификации. / Васин Ю.Г. // «Современное состояние теории исследования операций» - М.: Наука, 1979 - С.424-450.

8. Васин Ю.Г. Хорошо приспособленные локальные однородные методы обработки графической информации. / Васин Ю.Г. // Автоматизация обработки сложной графической информации: Межвуз. сб. науч. тр. Под ред. Ю.Г.Васина -Горьк. гос. ун-т, Горький, 1984 - с. 131

9. Васин Ю.Г. Эффективность различных стратегий обработки видеоинформации на базе локальных однородных рекуррентно-рекурсивных

функций / Васин Ю.Г. // Методы и средства обработки графической информации: Межвуз. сб. науч. тр. Под ред. Ю.Г.Васина - Горький, 1986 - с.4-47.

10. Васин Ю.Г. Рекурсивные структуры представления видеоинформации и их использование в задачах выделения линий перепадов и построения изолиний. / Васин Ю.Г., Плесков A.B. // Автоматизация обработки сложной графической информации, изд-во Горьковского госуниверситета (ГГУ) - г. Горький, 1988г. -с.4-28.

11. Васин Ю.Г. Система управления базами видеоданных / Васин Ю.Г., Ясаков Ю.В. // Методы и средства обработки графической информации: Межвуз. сб. науч. тр. Горьк. Гос. Ун-т - Горький, 1989 - с.93-115.

12. Васин Ю.Г. База знаний по лесоустройству и ее реализация в автоматизированной картографической системе / Васин Ю.Г., Кобрин Р.Ю., Короткое В.М. // НТИ, сер.2. Информационные процессы и системы - 1990 - №9 -с.6-14.

13. Васин Ю.Г. Сжатие цветных изображений на основе бинарных иерархических структур. / Васин Ю.Г., Плесков A.B., Игнатьева В.П. // Вестник Нижегородского государственного университета. - Изд-во ННГУ, 2000 г. - вып. 1(22)-с. 50-58.

14. Васин Ю.Г. Технология иерархического кодирования видеоинформации / Васин Ю.Г., Жерздев C.B. // Тезисы 12-й Международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002 -Н.Новгород: Изд-во НГАСУ, 2002 - с.326-333.

15. Васин Ю.Г. Иерархический доступ к болынеформатным изображениям по сети Интернет / Васин Ю.Г., Жерздев C.B., Шишляев М.В. // Тезисы VIII Всероссийской научной конференции «Методы и средства обработки сложной графической информации» - Н.Новгород, 2005 - С. 18-19.

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

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

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

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

20. Гашников М.В. Информационная технология компрессии изображений в системах оперативного дистанционного зондирования. / Гашников М.В., Глумов Н.И., Сергеев В.В. // Известия Самарского научного центра РАН, 1999 -№1 - с.99-107.

21. Гашников М.В. Программная оболочка компрессии и визуализации изображений на основе алгоритма иерархической сеточной интерполяции / Гашников М.В., Глумов Н.И., Мясников В.В., Сергеев В.В., Farberov Е. // Труды 5-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-5-2000)» - Самара: ИПО СГАУ, 2000 -том 4 - с.710-713.

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

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

24. Жерздев C.B. Разработка алгоритмов адаптивного сжатия видеоинформации на основе иерархических структур для задач оперативного отображения. — Диссертация на соискание ученой степени кандидата технических, наук - Н.Новгород, 2004.

25. Захаров А.Ю. Построение пространственного индекса с использованием квадро- и R-деревьев / Захаров А.Ю. // Исследования по информатике: Сб. тр. / ИПИ АН РТ. — 2001. — Вып. 3. — С. 133-138

26. Золотов В. А. Современные методы поиска и индексации многомерных данных приложениях моделирования больших динамических сцен. / Золотов В.А., Семенов В.А. / Труды Института системного программирования РАН 2013 - Вып. 24 - С.381-416

27. Кенцл Т. Форматы файлов Internet. / Кенцл Т. - Спб: Питер, 1997.

28. Климов A.C. Форматы графических файлов. / Климов A.C. - К: НИПФ «ДиаСофт Лтд.», 1995.

29. Кудин A.B. Алгоритм PIRH-кодирования технических изображений. / Кудин A.B. // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. - Нижний Новгород: Изд-во Нижегородского ун-та, 1998. - Вып.1 (18).

30. Кудин A.B. Свертка растра пикселов в последовательный образ в алгоритме PIRH-кодирования технических изображений. / Кудин A.B., Жерздев C.B., Жерздев A.B. // Вестник Нижегородского государственного университета.-Математическое моделирование и оптимальное управление - Н. Новгород: Изд-во ННГУ, 1999 - Вып.1 (20) - С.219-225.

31. Кудин A.B. Технология эффективного хранения и оперативного отображения картографической растровой информации. - Диссертация на соискание ученой степени кандидата технических наук - Н.Новгород, 2000.

32. Левитин А. В. Глава 9. Жадные методы: Алгоритм Дейкстры / Левитин А. В. // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms — M.: «Вильяме», 2006. — С. 189—195.

33. Методы компьютерной обработки изображений / Под ред. В.А.Сойфера. - М.: Физматлит., 2001 - 784 с.

34. Неймарк Ю.И. Кодирование больших массивов информации в связи с задачами распознавания образов. / Неймарк Ю.И., Васин Ю.Г. // Изв. Вузов. Радиофизика, 1968 - С. 1081-1085

35. Нетравали А.Н. Кодирование изображений: обзор. / Нетравали А.Н., Лимб Дж.О. // ТИИЭР, 1980 - т.68 - №3

36. Нильсон Н. Искусственный интеллект / Нильсон Н. - Москва, 1973

37. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на IBM РС./ Романов В.Ю. - М.: Унитех, 1992.

38. Рябко Б.Я. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами. / Рябко Б.Я., Фионов А.Н. // Проблемы передачи информации - 1999 - Т.35 - Вып. 4 - С.95-108.

39. Серапинас Б.Б. Спутниковые системы позиционирования: учебное издание / Серапинас Б.Б. - Москва:ИКФ «Каталог», 2002 г. - 106 с.

40. Старцев Ю.В. Нечеткое управление подвижным объектом при обходе препятствий. / Старцев Ю.В., Головацкий К.Э. // В кн. "Труды 1 международной конференции новые технологии управления движением технических объектов" -Ставрополь, СГТУ, 1999г. - с. 94-95.

41. Томас X. Кормен Алгоритмы: построение и анализ = Introduction to Algorithms. / Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — М.: <<Вильяме», 2006. - 2-е изд - С. 1296.

42. Юсов Е.А. Модели и алгоритмы многомасштабного представления данных для высокопроизводительной визуализации геоповерхностей. Диссертация на соискание ученой степени кандидата технических наук - ННГУ, г. Н.Новгород, 2011 г.

43. Abel D. J. A B+-tree structure for large quadtrees, / Abel D. J. // Computer Vision, Graphics, and Image Processing, July 1984 - vol. 1 - no. 27 - pp. 19-31.

44. Bayer R. Organization and maintanence of large ordered indexes / Bayer R., McCreight E. M. // Acta Informática, 1972 - vol. 3 - no. 1 - pp. 173-189.

45. Beckmann N. The R* tree: An Efficient and Robust Access Method for Points and Rectangles / Beckmann N., Kriegel H., Schneider R., Seeger B. // ACM, 1990-p. 322-331.

46. Burt P.J. Tree and Pyramid Structures for Coding Hexagonally Sampled Binary Images. / Burt P.J. // CGIP(14), 1980 - No.3 - pp.271-280.

47. Dijkstra E. W. A note on two problems in connexion with graphs. / Dijkstra E. W. //Numerische Mathematik, 1959 - V. 1 - P. 269-271

48. Egorov, A.A. The structure of a multi-functional mobile GIS / A.A.Egorov // PATTERN RECOGNITION and IMAGE'UNDERSTANDING: 8th Open German Russian Workshop OGRW-8-2011. - N. Novgorod, 2011. - PP. 48-52.

49. Fujimura K. Path planning among moving obstacles using spatial indexes /• Fujimura K., Samet H. // Proc. of IEEE 1989 International Conference on Robotics and Automation - pp. 1662-1667.

50. GIF Graphics Interchange Format: A standard defining a mechanism for the storage and transmission of bitmap-based graphics information. — Columbus, OH, USA, 1987.

51. Gisli R. Hjaltason Distance Browsing in Spatial Databases / Gisli R. Hjaltason, Hanan Samet // ACM Transactions on Database Systems, June 1999 - 24 - 2 -pp. 265-318

52. Gisli R. Hjaltason Speeding Up Construction of Quadtrees for Spatial Indexing / Gisli R. Hjaltason and Hanan Samet - 1999

53. Golomb S.W. RunLength Encodings / Golomb S.W. // IEEE Trans. Inform. Theory IT, Jul. 1966 - 12 - pp.399-401.

54. Greene D. An Implementation and Performance Analysis of Spatial Data Access Methods. / Greene, D, // Proceedings of the 5th International Conference on Data Engineering, 1989 - pp.606-615.

55. Guttman A. R-trees: A Dynamic Index Structure For Spatial Searching // Proc. ACM SIGMOD Int. Conf. on Management of Data - 1984. - p. 47-57.

56. Jacobs P. Planning smooth paths for mobile robots / Jacobs P., Canny J. // IEEE 1989 International Conference on Robotics and Automation - pp.2-7.

57. Kanayama Y. Vehicle path specification by a sequence of straight lines / Kanayama Y. // IEEE Journal of Robotics and Automation, 1988 - Vol. 4 - no. 3

58. Langdon G.G. An introduction to arithmetic coding./ Langdon G.G. // IDM J.Res.Dev. 28, 2 (Mar. 1984) - pp.135-149.

59. Pennebaker W.B. JPEG: Still Image Data Compression Standard. / Pennebaker W.B., Mitchell J.L. // International Thomson Computer Press, London, UK,. 1993.

60. Rubin F. Arithmetic stream coding using fixed precession registers./ Rubin F. // IEEE Trans.Inf.Theory IT-25, 6 (Nov. 1979) - pp.672-675.

61. Shiller Z. On computing the global time-optimal motion of robotic manipulators in the presence of obstacles / Shiller Z., Dubowsky S. // IEEE Trans. Rob. And Autom., 1991 - 7 - N6 - pp.785-797.

62. Steer B. Trajectory planning for a mobile robot. / Steer B. // International Journal of Robotics Research, Oct. 1989 - Vol. 8 - no. 5 - pp. 3-14

63. Vasin Yu.G. Information Techniques for Hierarchical Image Coding / Vasin Yu.G., Zherzdev S.V. // Pattern Recognition and Image Analysis, 2013 - Vol.13 -No.3 - pp.539-548.

64. Vasin Yu.G. GIS Terra: A graphic database management system / Vasin Yu.G., Yasakov Yu.V. // Pattern recognition and image analysis, 2004 - Vol. 14 - No. 4 - pp.579-586.

65. Vasin Ju.G. Technology of remote raster images access / Vasin Ju.G., Zherzdev S.V., Shishlyaev M.V. // Proc. of 7-th international conference on Pattern recognition and image analysis: New information technologies . St.Petersburg, 2004 -pp.956-958

66. Vasin Yu.G. 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.

67. Vasin Yu.G. 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.

68. Yasin Yu.G. Mobile Geoinformation system/, S.V.Zherzdev, A.A.Egorov // Pattern Recognition and Image Analysis. - 2009. - Vol. 19, No. 2. - PP.342-348.

69. Vasin Yu.G. 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.

70. Vasin Yu.G. 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.

71. Vasin Yu.G. 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.

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

- PP.476-478.

73. Vasin Yu.G. 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.

74. Witten I.H. Arithmetic coding for data compression. Commun. / Witten I.H., Neal R., Cleary J.G. // ACM 30,6; Jun.1987 - pp.520-540.

75. Xia K. Obstacle avoidance path planning of a manipulator / Xia K., Jiang S., L u L., // Proc. IEEE Int. Conf. Rob. and Autom., Philadelphia, Pa., Apr., 24-29. 1988 - Vol. 1 - Washington (D.C.), 1988 - pp. 646-647.

76. Ziv J. A universal algorithm for sequential data compression./ Ziv J., Lempel A. // IEEE Transactions on Information Theory - 1977. - Vol.23, 3 - pp.337343.

77. Автоспутник [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. — Режим доступа: www.autosputnik.com

78. Алгоритмы обхода препятствий [Электронный ресурс]: статья -электрон, текстовые дан. - Режим доступа: http://pmg.org.ru/

79. Алгоритмы поиска пути в играх [Электронный ресурс]: статья -электрон, текстовые дан. - Режим доступа: http://gamesdevandmath.blogspot.com

80. Боресков, Алексей. Пространственные индексы (spatial index) и их использование [Электронный ресурс]/Боресков А.В.: статья - электрон, текстовые дан. - Режим доступа: steps3d.narod.ru/tutorials/spatial-index-tutorial.html

81. Бортовые информационные системы Мирком [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. — Режим доступа: www.mircom.ru

82. ГИС «Нева ПК» [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. — Режим доступа: nevapk.bushnev.ru

83. Козлов, Игорь. Софт для КПК на любой вкус [Электронный ресурс]/И. Козлов - электронный журнал «Компьютер-информ» - 2006 г. - №19 - Режим доступа: www.ci.ru

84. Козлов, Игорь. Софт для КПК на любой вкус (часть 2) [Электронный ресурс]/И. Козлов - электронный журнал «Компьютер-информ» - 2006 г. - №20 -Режим доступа: www.ci.ru

85. Козлов, Игорь. Софт для КПК на любой вкус (часть 3) [Электронный ресурс]/И. Козлов - электронный журнал «Компьютер-информ» - 2006 г. - №21 -Режим доступа: www.ci.ru

86. Макаров, Игорь. Дополнительная информация по навигаторам Garming и навигационным программам [Электронный ресурс]/И.Макаров -электрон, текстовые дан. - Режим доступа: postman.ru/~makarov/pclink/gps.htm

87. Обход препятствий [Электронный ресурс]: статья - электрон, текстовые дан. - Режим доступа: http://www.gaze.narod.ru/

88. Протокол обмена NMEA 0183 v4.00 [Электронный ресурс]: протокол -электрон, текстовые дан. - Режим доступа: - http://nvs-gnss.ru

I 108 1J

89. Сити Гид [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.probki.net

90. Талка-ГИС [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.talka2000.ru

91. Универсальные и автомобильные GPS - навигаторы, Garmin [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.gps-rus.ru

92. ArcGIS [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.dataplus.ru

93. Chart Cruise [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. — Режим доступа: chartpilot.ru

94. Map-Info [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.esti-map.ru

95. Pocket Navigator [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.pocketnavigator.ru

96. PocketGPS Pro [Электронный ресурс]: документация на программное обеспечение - электрон, текстовые дан. - Режим доступа: www.pocketgps.ru

97. Stout В. Smart Moves: Intelligent Pathfínding [Электронный ресурс]/ Stout В.: статья - электрон. текстовые дан. - Режим доступа: http://www.gamasutra.com,