Введение к работе
Актуальность темы. Теоретические исследования и инженерные приложения в области прикладной математики повсеместно связаны с необходимостью визуализации тех или иных процессов и явлений реальной действительности как на этапе ввода исходной информации, так и при получении и анализе численных результатов математического моделирования. Необходимость графического представления исследуемых объектов присутствует в таких областях человеческой деятельности, как автоматическое проектирование (САПР и АСНИ), архитектура, издательское макетирование, обработка статической и динамической видеоинформации. Интерактивное моделирование является также основной компонентой авторизованного и дистанционного обучения. Кроме этого, компьютерная графика позволяет экспериментатору наблюдать в процессе моделирования те процессы и явления, которые не воспринимаются человеческим глазом (полет электрона в электрическом поле, динамика движения земной коры и т.п.).
Вышесказанное обусловило бурное развитие аппаратуры ввода/вывода графической информации и, соответственно, теории компьютерной геометрии и машинной графики. По сути дела, появился неизвестный ранее мультимедийный инструментарий, позволяющий решать новые задачи интерактивного информационного взаимодействия с пользователем. Это и гипертекстовые мультимедийные возможности операционных систем с графическим интерфейсом, и глобальная компьютерная сеть Internet с базовым протоколом передачи гипермедийной информации HTTP. Известно, что доля графической информации в таких информационных системах является превалирующей. Объем хранилищ
графической информации год от года неуклонно увеличивается. Н( постоянно существует дилемма: чем большая емкость хранилищ* обеспечивается инженерами и программистами, тем большш требования возникают на объем этого хранилища у пользователей Таким образом, возникает проблема организации эффективное хранения графической информации. Эффективность хранение определяется требованиями, предъявляемыми к объему хранилищ скоростью поиска и выборки требуемой графической информации.
Модели описания и представления графической информации имеющие отношение к решению проблемы эффективного храненш изображений, существуют различные. Выделим основные из них.
1. Растровые модели.
Изображение рассматривается как совокупность пикселов расположенных в прямоугольной области, называемой растрої» пикселов. Атрибут пиксела есть дискретизированное значенні цветовой характеристики изображения в геометрическом центр пиксельной площадки. Иногда в целях устранения эффекто: дискретизации его заменяют интегралом цветовой характеристик] по пиксельной площадке. Под глубиной представления цвет; пиксела понимают разрядность атрибута пиксела. Являясь аппаратно-ориентированным, растровый подход і хранению изображений обеспечивает высокую скорость взаимо действия с устройствами ввода/вывода графической информации Однако, объем графической информации при таком подход традиционно велик.
2. Векторные модели.
Другим подходом к эффективному хранению графическо: информации является задание не растра пикселов, а матемг тического описания объектов изображения. Так, на этапе ввод
и/или при последующем хранении изображений возникает необходимость векторизации или аналитической параметризации исходной матрицы пикселов. В случае небольшого количества объектов изображения такой подход оказывается наиболее эффективным. Дальнейшая обработка графической информации и базовые алгоритмы машинной графики базируются на сложно структурированном представлении графических данных и обусловливают традиционно большие объемы графической информации.
Хотя в названии данного подхода и присутствует термин векторный», предполагается использование не только кусочно-линейных моделей представления объектов изображения. Например, одним из способов описания графических данных является задание границ объектов всевозможными сплайновыми кривыми или локальными однородными хорошо приспособленными базисными функциями.
Недостатком данного подхода является необходимость проведения растрирования векторной модели при визуализации изображения, что приводит к значительному снижению производительности выборки графической информации. Кроме того, векторизация изображений является достаточно сложным процессом, примыкающим к теории распознавания образов. А параметризация «живого» изображения практически невозможна. 3. Модели синтеза.
Синтез изображений присутствует в задачах виртуальной реальности (тренажеры, игры). Математическая модель таких изображений - наиболее компактная форма представления графических данных. Однако, реалистичность создаваемой
картинки и скорость ее генерации на порядки уступают растровому подходу.
Хотя для хранения графической информации применяются различные модели описания и представления, все же преобладающим большинством разработчиков в настоящее время используются растровые модели. Так, около 90% информации, представленной на WWW, занимают растровые изображения. Даже данные, первоначально имеющие инородную структуру, часто предлагаются пользователю в графическом виде. Это, например, всевозможные графики и диаграммы, сгенерированные на основе численной информации из электронных таблиц и баз данных. Для хранения изображений в справочных системах и мультимедийных средах, распространяемых на CD и DVD, также применяются растровые форматы хранения изображений. Сегодня существует огромное количество различных растровых форматов хранения и передачи графической информации. Однако, объем данных, представляющих растровое изображение, на практике оказывается слишком большим. Быстрый рост емкостей устройств хранения данных лишь стимулирует разработчиков на дальнейшее развитие средств мультимедиа. Следовательно, необходимо применять программно-аппаратные системы сжатия графической информации.
Чрезвычайно остра проблема организации эффективного хранения графической информации в ГИС. В силу большого формата географических карт, специфики представления картографического растра и особенностей хранения графической информации в ЭВМ картографическим растровым документам присущи огромные размеры. Объем таких документов, имеющих формат порядка нескольких десятков сантиметров по горизонтали и по вертикали,
составляет сотни мегабайт. Это затрудняет эффективную организацию хранения и обработки картографических растровых документов, в том числе и оперативную визуализацию. Кроме того, к картографическим документам предъявляются жесткие требования по точности представления объектов топокарт и топопланов. Это обусловливает нежелательность использования методов сжатия графической информации с потерями, имеющих, как правило, высокий коэффициент компрессии данных. Хотя в настоящее время обратимые (без потерь) методы сжатия информации сильно развиты, в случае компрессии растрового представления графической информации обнаруживается целый ряд особенностей у исходных данных, исследование и использование свойств которого дает путь для разработки и дальнейшего развития специализированных алгоритмов и методов для сжатия графической растровой информации.
Целью диссертационной работы является развитие технологий эффективного хранения и оперативного отображения графической информации, включая развитие методов компрессии/декомпрессии графической растровой информации без потерь, разработку методов обеспечения оперативного доступа к большеформатным растровым документам и применение их для решения прикладных задач по организации компактного хранения растровых изображений карт и обеспечению оперативной выборки и отображения фрагментов электронных карт.
Научная новизна диссертационной работы заключается в следующем:
1. Разработаны технологии RRE и PIRH сжатия без потерь графической растровой информации, эффективно сочетающие
взаимосогласованные модели развертки графической информации, алгоритмы и методы устранения корреляционной и статистической избыточности.
Модель изображений в RRE-технологии - сплошные однотонные заливки, образующие покрытие растра. В отличие от методов разбиения области на регулярные иерархические структуры (квадродеревья и т.п.) используется нерегулярное разбиение с последующим применением статистических методов для хранения топологической информации о произведенном разбиении. Модель изображений в PIRH-технологии — растры коррелированных пикселов. Более того, предложенная технология сжатия может быть применена к произвольному автокоррелированному потоку данных, полученному из любого внешнего источника, как дополнительный финальный компрессор, адаптивно настраивающийся на любой вид сжимаемой информации.
-
В качестве модели редукции размерности растра пикселов использована развертка по кривой Пеано. В отличие от известных алгоритмов в работе предложен алгоритм построения дискретного аналога кривой Пеано на основе рекурсивной конструкции Гильберта для проведения развертки дискретных прямоугольных областей произвольного размера.
-
С целью лучшего устранения корреляционной избыточности развит метод «сжатия с помощью стопки книг»: разработана новая схема адаптации, разработан механизм декомпозиции входного потока информации на подпотоки, каждый из которых обрабатывается независимо.
-
С целью устранения статистической избыточности полученного потока информации проанализирована возможность ориентации существующих алгоритмов и методов сжатия информации на
статистические свойства данного потока и произведен отбор наилучших.
-
Разработана технология представления большеформатных растровых документов с возможностью прямого доступа к фрагментам хранимого изображения.
-
Создана программная система обеспечения технологии компактного хранения и оперативной выборки при работе с цифровыми и электронными картами.
Практическая ценность. В основу диссертационной работы положены результаты, полученные автором в ходе исследований, проводимых по плану НИОКР Федеральной службы геодезии и картографии России на 1995-1997 год, в рамках проведения ОКР «Экран» в НИИ ПМК при ННГУ.
Полученные в диссертационной работе результаты могут быть использованы при проектировании программно-аппаратных систем, связанных с обработкой изображений и видеоинформации, а также при организации хранилищ графической растровой информации.
Апробация полученных результатов. Полученные результаты внедрены в Федеральной службе России по геодезии и картографии в системе символизации картографического изображения на экранах коллективного и индивидуального пользования (ОКР «Экран») в подсистемах РАСТР и РАСТР-ЭКРАН; в Центральном картпроиз-водстве Военно-морского флота (280 ЦКП ВМФ); в НИИ ПМК (Н.Новгород) в объектно-ориентированной геоинформационной системе «Терра»; в НижНовЭнерго (Н.Новгород) в ГИС «Кабельные сети».
Результаты диссертационной работы докладывались и обсуждались на VIII Всероссийской научно-практической конференции по графическим информационным технологиям, на V Всероссийской конференции по методам и средствам обработки сложной графической информации, на III Всероссийской конференции по распознаванию образов и анализу изображений. Практические результаты и выводы, сделанные при работе по теме диссертации, нашли свое отражение в 7 опубликованных печатных работах.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы. Объем основного текста работы - 111 машинописных страниц. Список литературы включает 71 наименование.
