Алгоритмы оперативно го отображения большеформатных цифровых карт
На правах рукописи
Матвеев Захар Александрович
алгоритмы оперативного отображения
большеформатных цифровых карт
05.01.01 – Инженерная геометрия и компьютерная графика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Нижний Новгород – 2011
Работа выполнена в ГОУ ВПО "Нижегородский государственный университет им. Н.И. Лобачевского"
Научный руководитель
доктор технических наук, профессор Кетков Юлий Лазаревич
Официальные оппоненты:
доктор технических наук, профессор Косяков Сергей Витальевич,
кандидат технических наук, доцент Жерздев Сергей Владимирович
Ведущая организация
ГОУ ВПО«Ижевский государственный технический университет»
Защита состоится "21" июня 2011 г. в 15 часов на заседании диссертационного совета ДМ 212.162.09 при ГОУ ВПО «Нижегородский государственный архитектурно-строительный университет» по адресу: 603950, г. Нижний Новгород, ул. Ильинская, 65, корпус 5, аудитория 202.
С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Нижегородский государственный архитектурно-строительный университет».
Автореферат разослан «18» мая 2011 г.
Ученый секретарь
диссертационного совета
кандидат педагогических наук, доцент Н.Д. Жилина
Общая характеристика работы
Актуальность работы. Современная экономическая, управленческая и исследовательская деятельность человека тесно связана с анализом пространственного положения объектов земной поверхности. Такого рода сведения необходимы при решении широкого спектра задач. Это – управление наземным, воздушным и водным транспортом, проектирование, разработка и эксплуатация различных коммуникаций, гражданское строительство и управление коммунальным хозяйством, землеустройство и экология, разведка полезных ископаемых, оборонная деятельность и многое другое.
На протяжении веков пространственные географические данные описывались с помощью разнообразных бумажных документов, сначала рукописных, а затем и типографских. В 50-х годах прошлого столетия были начаты исследования возможности хранения и обработки пространственной информации с помощью ЭВМ. Появляются первые географические информационные системы (ГИС), формируется геоинформатика – наука о принципах и методах цифрового моделирования объектов реальности в форме пространственных данных, а также производственная деятельность по научному обоснованию, проектированию, созданию, эксплуатации и использованию геоинформационных систем.
В настоящее время существует множество автоматических и автоматизированных картографических систем (АКС), использующих различного рода программные и аппаратные средства, ориентированные на работу с геоинформационными данными. Такие комплексы обеспечивают сбор, редактирование, хранение, оперативную визуализацию и распространение пространственной информации в виде электронных карт или их твердых копий. Описание цифровой карты на ту или иную территорию земной поверхности, хранящееся в специализированной базе картографических данных (СБКД), представляет собой совокупность сведений о пространственных объектах двух видов: геометрических (позиционных) и атрибутивных (семантических). Геометрическая часть отражает геометрию объекта (указание положения объекта, элементы графического оформления), а атрибутивная содержит характеристики объектов (их качественные или количественные параметры) и пространственно-логические связи между ними.
Одним из наиболее трудоемких этапов проектирования и эксплуатации любой ГИС является наполнение СБКД, анализ полноты представленной информации и ее достоверности. Здесь применяется автоматическое и автоматизированное сканирование существующих оригиналов картографических документов и аэрофотоснимков земной поверхности, корректируются искажения, возникающие в результате деформации или плохого качества исходных документов, учитываются данные геодезических измерений и др. Ряд проверок полноты и качества пространственной информации осуществляется в автоматическом режиме, но окончательное заключение о точности и качестве электронной карты принимается специалистом-редактором по результатам тщательного визуального контроля содержимого СБКД.
Электронные карты обладают рядом преимуществ по сравнению с традиционными бумажными документами. Они не подвержены механическим и климатическим воздействиям, их можно легко копировать без потери точности, подвергать различным масштабным преобразованиям (в т.ч. и изменению системы координат); из них можно напрямую извлекать информацию, используемую различными компьютерными приложениями. Однако в связи со стихийными бедствиями, в связи с воздействием человека на окружающую обстановку, – и те, и другие карты со временем перестают соответствовать тому участку земной поверхности или водной акватории, которую они описывают. Поэтому архивы цифровых карт, требующие для своего создания огромных затрат времени, средств и людских ресурсов, нуждаются в постоянном обновлении. Основным источником информации на этом этапе служат данные аэро- и космической съемки.
Правильность интерпретации, генерализации и согласования отображаемых объектов лежит на квалифицированных редакторах. Поэтому к подсистеме визуализации любой ГИС предъявляются повышенные требования как по скорости и точности отображения, так и по возможности оперативного масштабирования исследуемого фрагмента, по выводу отдельных слоев листа карты, по воспроизведению заданных объектов и их характеристик.
Объектом исследования является технология визуализации векторных графических описаний большеформатных листов электронных карт.
Предметом исследования являются алгоритмы и средства повышения производительности систем отображения графических файлов формата HP-GL.
Цель работы – создание импортозамещающего аналога лучших зарубежных визуализаторов графических изображений, подготовленных для издания малой серией полноцветных цифровых карт, а также разработка алгоритмов повышения скорости отображения таких изображений.
Для достижения поставленной цели требуется решение следующих основных научных и практических задач:
- Проведение анализа существующих систем отображения картографической информации и оптимальных классических алгоритмов решения типовых задач отображения графических примитивов.
- Исследование внутренних форматов и математических моделей местности, используемых для представления графических образов электронных карт.
- Разработка алгоритмов предварительной обработки исходного графического описания и индексирования групп графических операторов.
- Разработка алгоритмов масштабирования и плавной локальной навигации между смежными фрагментами цифровых карт.
- Применение оптимального алгоритма отсечения отрезков в задачах массовой обработки операторов линейного перемещения пишущего узла.
- Анализ возможностей распараллеливания вычислительного процесса визуализации.
- Реализация разработанных алгоритмов в виде программной подсистемы визуализации графических файлов формата HP-GL.
- Экспериментальное сравнение производительности разработанной подсистемы с зарубежными аналогами.
Методы исследования. Теоретические исследования выполнены с использованием методов дискретной математики (теории графов, математической логики), вычислительной геометрии, компьютерной графики.
Экспериментальные исследования выполнены с помощью разработанной подсистемы визуализации, ряда отечественных АКС и известных визуализаторов SPLOT32 и View Companion (Premium) for Windows.
Достоверность и обоснованность полученных в работе результатов и выводов подтверждаются положительными результатами проведенных экспериментальных исследований и опытной апробации подсистемы визуализации на ряде картографических документов, подготовленных в научно-исследовательском институте прикладной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (НИИ ПМК).
Научная новизна состоит в том, что:
- предложены алгоритмы предварительной обработки графического файла в формате HP-GL, обеспечивающие автоматическое создание иерархической кластерной модели исходного файла;
- разработан внутренний формат представления графических данных и серия алгоритмов его индексирования;
- предложен алгоритм плавной локальной навигации по смежным кадрам изображения, обеспечивающий повышение производительности процесса визуализации на 30%;
На защиту выносятся:
- Алгоритмы предварительной обработки исходного изображения.
- Внутренний формат графических данных и алгоритмы индексирования.
- Алгоритм плавной локальной навигации по смежным фрагментам изображения.
- Программная система визуализации графических файлов в формате HP-GL.
- Экспериментальное исследование предложенных технологий визуализации большеформатных картографических документов.
Практическая значимость научного исследования. В основу диссертационной работы положены результаты, полученные автором в ходе комплексных исследований НИИ ПМК, проводимых в рамках НИОКР Министерства образования и науки Российской Федерации, Федеральной службы геодезии и картографии России, Главного управления навигации и океанографии МО Российской Федерации. Работа выполнена при финансовой поддержке РФФИ (проект № 05-01-00590).
Реализация результатов работы. Результаты диссертационной работы были использованы при разработке ряда версий систем контроля и подготовки издательских материалов топографических и морских цифровых карт в НИИ ПМК.
Апробация работы. Материалы диссертации докладывались на следующих конференциях:
- научно-техническая конференция “ТЕКОМ-2004: Актуальные вопросы построения систем управления сложным распределённым оборудованием и предоставлением услуг” (Н. Новгород, Нижегородский гос. тех. ун-т, 2004),
- VIII Всероссийская научная конференция "Методы и средства обработки сложной графической информации" (Н.Новгород, Нижегородский гос. ун-т, 12-16 сентября 2005),
- Всероссийская научно-техническая конференция ИСТ-2005 "Информационные системы и технологии" (Н. Новгород, Нижегородский гос. тех. ун-т, 2005),
- Всероссийская конференция "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, Нижегородский гос. ун-т, 2006),
- Всероссийская конференция "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, Нижегородский гос. ун-т, 2007),
- Всероссийская научно-техническая конференция "Информационные технологии в учебном процессе" (Н. Новгород, Нижегородский гос. тех. ун-т, 2007),
- Международная научно-техническая конференция ИСТ-2007 "Информационные системы и технологии " (Н.Новгород, Нижегородский гос. тех. ун-т, 2007),
- седьмая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах" (Н. Новгород, Нижегородский гос. ун-т, 2007),
- 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies PRIA-9-2008 (Nizhni Novgorod, Nizhni Novgorod State University, Sept. 14-20, 2008),
- 20-я Международная конференция по компьютерной графике и зрению Графикон-2010 (Санкт-Петербург, Санкт-Петербургский гос. унт-т инф. технологий, механики и оптики, 21-25 сентября 2010).
Публикации. Результаты работы отражены в 16 научных публикациях, в том числе в трёх статьях, опубликованных в изданиях, рекомендованных ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы. Общий объем основного текста работы (без учёта списка литературы) – 134 машинописных страницы, список литературы включает 154 наименования.
Краткое содержание работы
Во введении дается общая содержательная постановка проблемы визуализации геоинформационных данных. Кратко изложены цели и содержание работы, перечислены результаты проведенных исследований, приведены данные об апробации и практическом использовании результатов.
Первая глава носит обзорный характер. В ней приводятся краткие исторические сведения о развитии отечественной картографии, описываются первые шаги, связанные с появлением цифровой картографии в нашей стране. Дается характеристика ведущих ГИС зарубежного и отечественного производства.
Среди ГИС, получивших во всем мире наибольшее распространение, отмечается продукция американской компании ESRI (Environmental Systems Research Institute), занимающейся разработкой серии таких программных продуктов, как ArcGis, ArcIMS, ArcInfo, ArcSDE, ArcView. К числу ГИС, наиболее популярных в России, относится MapInfo Professional, официальным представителем разработчика которой в нашей стране является компания "ЭСТИ МАП".
В разделах 1.1 и 1.2 вводятся основные понятия и определения, связанные со спецификой представления данных о пространственных объектах, приводится классификация картографических объектов, описываются этапы создания электронных карт и их графических образов. Приводятся сведения о форматах хранения, обмена и обработки картографических данных. Описываются характеристики растровых, векторных и гибридных графических форматов представления изображений цифровых карт.
Особое внимание уделено автоматизированным картографическим системам, разработанным в НИИ ПМК, т.к. результаты диссертационной работы имеют непосредственную связь с системами отображения и подготовки издательских оригиналов цифровых карт, создаваемыми в этих АКС. Особенностью большинства АКС НИИ ПМК является использование для формирования графического образа картографических документов подмножества языка Hewlett-Packard Graphics Language (HP-GL), являющегося промышленным стандартом de-facto для производителей практически всех большеформатных плоттеров.
Раздел 1.3 посвящен подсистемам визуализации цифровых карт, которые обеспечивают интерфейс с пользователями ГИС и особенно важны при наполнении специализированных баз данных, контроле полноты и качества их содержания и обновлении картографических данных. Сложность задач, решаемых визуализаторами, заключается в больших объемах графических данных (размер векторного графического файла достигает 100 Мб) и жестких временных ограничениях на работу алгоритмов фрагментации и масштабирования отображаемых участков цифровых карт (приемлемое время отображения одного кадра – порядка 1 секунды).
В разделе 1.4 рассматриваются классические задачи дискретной геометрии и оптимальные по числу операций алгоритмы двумерного отсечения на плоскости. Программа визуализации векторного изображения вынуждена решать подобную задачу довольно часто, чтобы ответить на вопрос, пересекает ли очередной отрезок прямой отображаемый фрагмент векторного изображения – прямоугольник со сторонами, параллельными координатным осям. Оптимальным алгоритмам решения этой задачи посвящено довольно много исследований, часто цитируемых в литературе по машинной графике. К числу самых известных методов отсечения отрезка относятся алгоритмы Коэна-Сазерленда, Цируса-Бека, Собкова-Поспишила-Янга и Лианга-Барски. Среди новых подходов, ориентированных на решение задачи отсечения в условиях массовой обработки ребер полигонов, отмечается алгоритм Ю.Л.Кеткова. Его основная идея заключается в том, что начало очередного ребра ломаной совпадает с концом предшествующего ребра, и результатами анализа предыдущего шага можно воспользоваться. Именно такая ситуация наблюдается в подавляющем большинстве графических команд языка HP-GL, используемого для формирования образов электронных карт.
Вторая глава посвящена методам и средствам повышения производительности визуализатора большеформатных графических документов, подготовленных в формате HP-GL.
В разделах 2.1 и 2.2 рассматриваются вопросы предварительной обработки графической информации. Важным этапом обработки исходного документа является изменение формата данных с целью сокращения объёма графической информации и повышения эффективности перебора графических записей в дальнейшем. На этом этапе двухбайтовые коды мнемонических графических команд заменяются "указателями" на входы в блоки обработки соответствующих процедур. Цепочки последовательных команд движения пишущего узла с указанием единственной точки назначения (команды PD x,y;) заменяются на одну команду со списком координат всех точек соответствующей ломаной. Команды перемещения "пера" вдоль опорных точек линейных знаков, сформированные в абсолютных координатах, заменяются цепочкой команд движения в относительных координатах. Однако наибольший эффект от преобразования исходного графического файла достигается за счет преобразования значений числовых параметров графических команд из символьного представления в соответствующие машинные форматы. При этом экономится не только объем исходной информации, но и сокращается число машинных тактов, затрачиваемое на ее последующую обработку.
Файл в формате HP-GL в общем случае не содержит явных указаний о сущности отображаемых объектов. Этот язык ориентирован только на управление траекторией пишущего узла. Отсутствие какой-либо структурированности, тематической зависимости графических данных в исходном файле существенно осложняет процесс обработки и визуализации электронной карты. Для преодоления этого ограничения автором вводится специальная классификация групп команд, позволяющая выполнить структурную реорганизацию данных на этапе предобработки.
Основная идея этого подхода сводится к созданию эквивалентной иерархической структуры прямоугольных кластеров, в которых сгруппированы последовательные цепочки графических команд. Формирование кластеров выполняется с учётом ряда закономерностей использования HP-GL команд (в частности специфики команды SP, формирующей некоторую разновидность цветового слоя). Для каждой группы команд вычисляются минимальные окаймляющие прямоугольники (MBR – Minimal Bounding Rectangle), определяющие границы кластера. По окончании процесса кластеризации формируется внутреннее представление пространственных данных, которое с формальной точки зрения является математической моделью местности, представленной в виде ориентированного графа со взвешенными вершинами. Использование этой модели существенно упрощает анализ взаимного положения объектов цифровой карты по отношению к окну просмотра, что в конечном счёте существенно влияет на скорость визуализации.
В целях дальнейшего развития идеи кластеризации предлагается использовать команду комментариев (код CO), появившуюся в версии HP-GL/2. Параметрами этой команды могут быть различные данные, предназначенные для идентификации отображаемых объектов, облегчающие и ускоряющие формирование MBR.
В разделах 2.3 и 2.6 показывается, что одним из радикальных средств, обеспечивающих повышение производительности визуализатора, является индексация графических данных, которая позволяет резко сократить время на поиск объектов, принадлежащих заданному окну отображения. В случае индексирования данных внутреннего формата отбор объектов может выполняться как динамически (при каждом изменении масштаба изображения), так и статически (заранее, однократно) на базе начального разбиения. Второй подход подразумевает, что при первоначальном открытии документа выполняется разбиение всей сцены на прямоугольные подобласти (ячейки) и последующее индексирование документа производится относительно каждой из ячеек сетки. В результате для каждого графического объекта строится список ячеек, содержащих фрагменты объекта, а для каждой ячейки – список объектов, пересекающихся с ней. При этом отбор объектов выполняется статически, однократно. При последующем масштабировании и навигации по документу отбор как таковой не выполняется. Вместо этого для каждого окна масштабирования определяется список инцидентных ячеек, и множество отображаемых объектов строится путём простого объединения списков объектов для каждой инцидентной ячейки.
В работе показано, что динамический подход представляется более адекватным для задач контроля качества большеформатных документов, т.к. именно динамический подход позволяет совмещать приемлемую точность визуализации с высокой производительностью и адаптируемостью по отношению к входным данным. Кроме того, реализованная в работе технология кластеризации позволяет в некотором роде совместить базовые преимущества как статического, так и динамического подходов за счёт применения иерархического индексирования. Принцип иерархической фрагментации является ещё одним базовым принципом индексирования, использованным в работе. Его суть заключается в том, что результаты анализа/индексирования крупномасштабного родительского объекта можно применить при индексировании его дочерних объектов меньшего размера (меньшей площади, периметра). Это позволяет существенно уменьшить вычислительные затраты на этапе индексирования. С точки зрения технической реализации иерархическое индексирование подразумевает организацию древовидной структуры данных таким образом, чтобы для каждого уровня структуры рекурсивно строился свой индекс. При этом индекс всего картографического документа может быть представлен как единая иерархическая многоуровневая древовидная система динамических индексных массивов.
Раздел 2.4 посвящен авторской модификации алгоритма массового отсечения ребер полигона, предложенного Ю.Л.Кетковым. Этот алгоритм позволяет значительно ускорить процедуру индексации самых элементарных примитивов – отрезков прямых. Показано, что за счет введения матрицы индексации областей изображения размерности 99, в 50 случаях из 81 возможного процедура индексации требует выполнения единственной операции сравнения. Лишь при анализе пересечения отрезка с горизонтальными и вертикальными прямыми требуется выполнить дополнительно восемь арифметических операций и 1-2 операции сравнения.
В разделе 2.5 отмечается, что система окаймляющих прямоугольников (MBR), формируемая на стадии предварительной обработки исходного файла, используется не только при формировании индексов различного уровня. Она упрощает принятие решений по поводу отображения тех или иных графических примитивов подобно некоторым операторам генерализации пространственных данных.
В разделе 2.8 описан алгоритм, позволяющий на 25-30% поднять производительность системы визуализации при плавном перемещении по соседним участкам карты. Он базируется на том факте, что редактор, оценивая полноту и качество электронной карты, выполняет регулярные перемещения по ее площади либо в горизонтальном, либо в вертикальном направлении. Поэтому при отображении смежного участка имеется возможность сохранить от 1/4 до 1/3 предшествующего изображения. Это сокращает время подготовки очередного кадра и приводит к более плавным переходам при навигации по смежным участкам цифрового изображения.
В связи с широким распространением ПК на базе многоядерных процессоров, немалый интерес представляют параллельные модификации алгоритмов визуализации. Этой области исследования посвящён раздел 2.9, где последовательно рассматривается два алгоритма с декомпозицией по данным и один алгоритм с функциональной декомпозицией процесса визуализации. Автором предлагается использовать конвейерную схему функциональной декомпозиции алгоритма, поскольку в отличие от других подходов “конвейерный” алгоритм эффективно функционирует независимо от целевой аппаратно-программной платформы и как правило не требует заметной реорганизации вычислений.
Третья глава посвящена вопросам проектирования и реализации визуализатора электронных карт в формате HP-GL. Главными требованиями, предъявляемыми к визуализатору PreVector, являются:
- четкое разделение функций главных модулей системы,
- ориентация на полное соблюдение правил и требований объектно-ориентированного подхода,
- адекватное применение объектно-ориентированных шаблонов проектирования,
- исследование узких мест, сдерживающих производительность системы с помощью лучших систем профилирования от ведущих производителей (AutomatedQA AQTime, Intel VТune Performance Analyzer),
- обеспечение масштабируемости компонент визуализатора и их переносимости на другие платформы (Windows Vista, Windows 7).
В современной версии визуализатора процесс обработки цифровой карты подразделяется на два основных этапа, выполняемых двумя функционально разными подсистемами. Первый этап, включающий предобработку исходных данных и формирование внутреннего формата представлений векторного описания электронной карты, выполняется подсистемой Parser. Второй этап, обеспечивающий различные уровни индексации элементов внутреннего формата и их визуализацию по заказу пользователя, выполняется подсистемой Process. Интерфейс между обеими подсистемами и интерактивное взаимодействие с пользователем обеспечивается третьей подсистемой – UserInterface (сокращенно – UI). Схема взаимодействия подсистем приведена на рисунке 1.
Рисунок 1 – Взаимодействие компонент системы PreVector
Подсистема UI реализована на основе технологии MVC (Model-View-Controller) с использованием графических элементов свободно распространяемой библиотеки шаблонов WTL (Windows Templates Library). В организации двух других подсистем – Parser и Process – существенную роль сыграли два момента. Во-первых, к моменту создания окончательной версии визуализатора устоялись и прошли серьезную апробацию внутренние форматы исходных данных и обслуживающие их классы. Во-вторых, в процессе проектирования подсистем были удачно подобраны шаблоны проектирования, обеспечивающие адекватное решение поставленных задач.
Основу подсистемы Parser составил шаблон проектирования Builder (Строитель), который позволил отделить процесс синтаксического анализа входных данных от процесса создания внутреннего представления сложного объекта. Шаблон "Компоновщик", также задействованный в процессе проектирования, обеспечил дополнительную гибкость программной системы, позволяя эффективно комбинировать различные приёмы индексирования в рамках одной структуры данных.
В ходе анализа производительности подсисетмы Parser, манипулирующей с огромными массивами исходных данных, было выявлено два "узких места". Одно из них было связано с преобразованием числовой информации в соответствующие машинные форматы. Второе узкое место было обусловлено многократными запросами на динамическое распределением памяти под обрабатываемые объекты, оперативно создаваемые в ходе построения внутреннего формата. Выявление и локализация обеих ситуаций обеспечивалась за счет использования упомянутых выше мощных средств профилирования.
С целью снижения накладных расходов, связанных с выделением динамической памяти под вновь создаваемые объекты, было введено жесткое правило – обработка объектов одного типа должна быть отделена от обработки другого типа. Это позволило избежать излишней фрагментации динамической памяти и кардинально снизить число затратных по времени системных вызовов. Для реализации этой идеи был создан специальный класс PreVAllocator, алгоритм работы которого использовал ряд эвристик, основанных на предварительном исследовании файла с исходными данными. Использование нестандартного распределителя памяти позволило существенно снизить время, затрачиваемое на построение внутреннего формата. По результатам профилирования до 80% времени работы основного модуля BuildMapSequence тратилось на обращение к оператору new. После внедрения класса PreVAllocator доля вычислительных затрат, связанных с динамическим распределением памяти, сократилась до 10 - 15%.
Четвёртая глава посвящена исследованию производительности разработанного визуализатора PreVector и сравнению его характеристик с возможностями зарубежных коммерческих разработок аналогичного плана. В качестве конкурирующих программных продуктов представлены пакет SPLOT32 (версии 4.10 и 5.01), приобретенный по лицензии и эксплуатируемый в НИИ ПМК в составе комплекса КАРТ-ДОК, и программное обеспечение ViewCompanion (полнофункциональная пробная версия Premium 5.30). В качестве типовых цифровых карт при оценке эффективности визуализаторов использовались топографическая карта Новгородской области и две морские навигационные карты побережья Северного моря. Дополнительная цель исследования заключалась в оценке влияния на общую производительность каждого из алгоритмов, представленных в диссертационной работе.
Основной эксплуатационный режим использования каждого визуализатора заключается в многократном просмотре редактором-картографом фрагментов цифровой карты при достаточно большом увеличении на экране дисплея. При этом для листа карты среднего размера (формат A1) в общей сложности приходится просматривать порядка 600 фрагментов с коэффициентом увеличения от 4 до 8. В связи с этим сеанс работы с визуализатором естественно распадается на две фазы. Первый этап связан с инициализацией – начальной обработкой исходного графического файла, формированием различных управляющих таблиц и созданием уменьшенной растровой копии просматриваемого документа на экране. После этого редактор приступает к методическому просмотру фрагментов запланированной области. Наиболее характерными операциями второй фазы являются перемещения по смежным фрагментам карты с возможным изменением коэффициента масштабирования (как в сторону увеличения, так и в сторону уменьшения). Для усреднения временных характеристик каждого эксперимента моделировалось по 100 запросов к каждому визуализатору.
В ходе экспериментального исследования стадию инициализации быстрее всех завершал пакет SPLOT32. Второе место по результатам экспериментов занял PreVector, опережая пакет ViewCompanion Premium примерно в 2–4 раза (рисунок 2, замеры выполнялись для нескольких навигационных карт различного объёма и сложности). Однако инициализация выполняется однократно и проигрыш на первом этапе не является определяющим.
В фазе интерактивной навигации по смежным фрагментам карты PreVector опередил аналоги с большим отрывом: время отклика на выполнение большинства массовых операций оказывалось на порядок меньше, чем у конкурентов. Некоторое представление о времени отклика при оперативной навигации с изменением масштабирующего коэффициента дают графики усредненных замеров, выполненные на одной из морских карт (рисунок 3). Конечно, к этим результатам следует относиться с некоторой осторожностью, поскольку невозможно провести абсолютно точное сравнение программных продуктов, два из которых являются "черными ящиками" (исходные коды фирмы-разработчики не предоставляют).
Результаты второго этапа исследования производительности визуализатора можно сформулировать следующим образом.
- Пространственная индексация (с использованием метода окаймляющих прямоугольников) позволяет существенно ускорить визуализацию при коэффициенте масштабирования более 2 за счёт быстрого отсечения протяжённых объектов, обеспечивая повышение производительности более чем в 5 раз.
- Алгоритм генерализации обеспечивает прирост производительности только при малых коэффициентах масштабирования за счёт исключения небольших пространственных объектов, различимых лишь при трёхкратном или большем увеличении.
Рисунок 2 – Время отклика при первоначальном открытии изображения.
Рисунок 3 – Время отклика при интерактивной навигации и оперативном изменении масштабирующего коэффициента.
- Вклад иерархической индексации проявляется при всех значениях масштабного коэффициента. Однако заметную роль иерархическая индексация играет лишь для масштабных коэффициентов в диапазоне от 1.5 до 3. При больших значениях основную роль начинает играть способность алгоритма к быстрому отбору мелкомасштабных объектов, обеспечиваемая пространственной индексацией.
Распараллеливание визуализации позволяет дополнительно повысить эффективность алгоритма визуализации на 10% – 25% практически при всех масштабных коэффициентах. Однако при 8-кратном увеличении полученный выигрыш уравновешивается накладными расходами, связанными с организацией многопоточных вычислений.
Основные результаты
- Разработана иерархическая кластерная модель внутреннего представления большеформатных цифровых карт на языке HP-GL, обеспечивающая компактное представление пространственной информации и повышающая оперативность ее последующей обработки. Предложен метод построения кластерной модели и формирования на её основе внутреннего формата графических данных.
- Предложены алгоритмы иерархической, статической и динамической индексации категорий графических объектов и исследовано их влияние на производительность системы оперативного отображения электронных карт.
- Исследованы классические и разработаны оригинальные алгоритмы, повышающие на 30-50% скорость выполнения графических операций, определяющих оперативное отображения цифровых карт.
- Разработан импортозамещающий программный продукт – система визуализации цифровых карт, представленных в формате промышленного стандарта Hewlett-Packard Graphics Language. По оперативности отображения разработанный визуализатор не уступает лучшим зарубежным аналогам, а по ряду показателей существенно их превосходит.
Публикации по теме диссертационной работы
Статьи, опубликованные в изданиях, рекомендованных ВАК
- Матвеев, З. А. Методы повышения эффективности систем воспроизведения картографических документов / З. А. Матвеев, Ю. Л. Кетков // Вестник Нижегородского университета им. Н. И. Лобачевского. – Н. Новгород, 2008. – № 2. – C. 138-146.
- Матвеев, З. А. Автоматическое создание кластерной модели графического образа электронных карт в формате HP-GL / З. А. Матвеев, Ю. Л. Кетков // Приволжский научный журнал. – Н. Новгород, 2011. – № 1. – C. 37-41.
- Матвеев, З. А. Разработка и исследование алгоритмов визуализации цифровых карт в векторном формате / З.А Матвеев, Ю.Л. Кетков // Приволжский научный журнал. – Н. Новгород, 2011. – № 2. – C. 45-49.
Другие публикации
- Матвеев, З. А. Решение задачи оптимизации просмотра файлов в векторном формате HPGL / З. А. Матвеев // ТЕКОМ-2004: Актуальные вопросы построения систем управления сложным распределённым оборудованием и предоставлением услуг : материалы науч.-тех. конф. / Нижегор. гос. техн. ун-т. – Н. Новгород, 2004. – C. 59-60.
- Матвеев, З. А. О некоторых алгоритмах просмотра цифровых карт в формате HPGL / З. А. Матвеев // Труды Нижегородского государственного университета. – Н. Новгород, 2005. – Т. 56. – С. 56-62.
- Матвеев, З. А. Использование алгоритмов индексирования при работе с цифровыми картам / З. А. Матвеев // Методы и средства обработки сложной графической информации : тез. докл. VIII Всерос. науч. конф. / Нижегор. гос. ун-т им. Н. И. Лобачевского. – Н. Новгород, 2005. – C. 84-87.
- Матвеев, З. А. Решение задачи оптимизации просмотра электронной карты в векторном формате HPGL / З. А. Матвеев // ИСТ-2005 "Информационные системы и технологии" : тез. докл. Всерос. науч.-техн. конф. / Нижегор. гос. техн. ун-т. – Н. Новгород, 2005. – C. 147.
- Матвеев, З. А. О некоторых задачах разработки программного обеспечения просмотра электронных карт / З. А. Матвеев // Известия Академии инженерных наук им. А. М. Прохорова. Бизнес-Информатика. – 2006. – Т. 17. – C. 3-10.
- Матвеев, З. А. Применение внутренних форматов хранения графических данных при решении задачи просмотра точных электронных карт / З. А. Матвеев // Технологии Microsoft в теории и практике программирования : материалы Всерос. конф. / Нижегор. гос. ун-т им. Н. И. Лобачевского. – Н. Новгород, 2006. – С. 210-213.
- Матвеев, З. А. Проектирование и принципы построения приложений предназначенных для обработки электронных карт / З. А. Матвеев // Технологии Microsoft в теории и практике программирования : материалы Всерос. конф. / Нижегор. гос. ун-т им. Н. И. Лобачевского. – Н. Новгород, 2007. – C. 176-177.
- Матвеев, З. А. Разработка программного обеспечения просмотра электронных карт в рамках изучения и создания отечественных геоинформационных систем / З. А. Матвеев // Информационные технологии в учебном процессе и активные методы обучения : материалы Всерос. науч.-методич. конф. / Нижегор. гос. техн. ун-т. – Н. Новгород, 2007. – С. 81-85.
- Матвеев, З. А. Особенности программной архитектуры приложений, предназначенных для обработки большеформатных графических документов / З. А. Матвеев // ИСТ-2007 "Информационные системы и технологии" : материалы междунар. науч.-тех. конф. / Нижегор. гос. техн. ун-т. – Н. Новгород, 2007. – С. 159-161.
- Матвеев, З. А. О некоторой параллельной модификации алгоритма отображения фрагмента электронной карты / З. А. Матвеев // Высокопроизводительные параллельные вычисления на кластерных системах : материалы 7-й междунар. конф.-семинара / Нижегор. гос. ун-т им. Н. И. Лобачевского. – Н. Новгород, 2007. – С. 392-397.
- Матвеев, З. А. Иерархическое индексирование электронных карт как отражение процесса моделирования предметной области / З. А. Матвеев // Модели, методы и программные средства : тр. конф. учеб.-науч. инновац. комплекса / Нижегор. гос. ун-т им. Н. И. Лобачевского. – Н. Новгород, 2007. – С. 279-281.
- Matveev, Z. Indices Organization as Visualization System Performance Improvements Means / Z. Matveev // 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies PRIA-9-2008 : conf. proceedings. – N. Novgorod, 2008. – Vol. 2. – P. 15-17.
- Матвеев, З. А. Анализ алгоритмов оптимизации времени отображения электронных карт в формате HP-GL / Ю. Л. Кетков, З. А. Матвеев // Графикон-2010 : тр. 20-й междунар. конф. по компьютерной графике и зрению / С.-Петерб. гос. ун-т информ. технологий, механики и оптики. – СПб., 2010. – С. 246-252.
