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

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

РГ6 од

2 2 Д5?; 2003

КУДИН Александр Владимирович

ТЕХНОЛОГИЯ ЭФФЕКТИВНОГО ХРАНЕНИЯ И ОПЕРАТИВНОГО ОТОБРАЖЕНИЯ КАРТОГРАФИЧЕСКОЙ РАСТРОВОЙ ИНФОРМАЦИИ

Специальность: 05.13.17 - Теоретические основы информатики

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

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

Работа выполнена в НИИ прикладной математики и кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского.

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

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

доктор технических наук, профессор Ю.Г.Васин

доктор технических наук, профессор В.В.Сергеев

доктор технических наук, профессор В.П.Гергель

Ведущая организация: Санкт-Петербургский государственный

электротехнический университет

< » ^влсаЬ^д 2000 г. в /Г"»

Защита состоится * )7 » (/(¡^МуЬ уУ 2000 г. в I > часов на заседании диссертационного совета СКК 063.43.01 научно-исследовательского института прикладной математики и кибернетики при Нижегородском госуниверситете им. Н. И. Лобачевского по адресу: 603005, Нижний Новгород, ул. Ульянова, д. 10.

С диссертацией можно ознакомиться в научной библиотеке НИИ прикладной математики и кибернетики.

/?» и&лЯ

Автореферат разослан * / * М^Ц/ОЬм 2000 г.

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

доктор технических наук, профессор ^ р Ю.Л.Кетков

О&У^У £ ЛЯ/, о

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

1. Растровые модели.

Изображение рассматривается как совокупность пикселов расположенных в прямоугольной области, называемой растров пикселов. Атрибут пиксела есть дискретизированное значена цветовой характеристики изображения в геометрическом центр пиксельной площадки. Иногда в целях устранения эффекто: дискретизации его заменяют интегралом цветовой характеристик] по пиксельной площадке. Под глубиной представления цвет, пиксела понимают разрядность атрибута пиксела. Являясь аппаратно-ориентированным, растровый подход 1 хранению изображений обеспечивает высокую скорость взаимо действия с устройствами ввода/вывода графической информации Однако, объем графической информации при таком подход традиционно велик.

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

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

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

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

Недостатком данного подхода является необходимость проведения растрирования векторной модели при визуализации изображения, что приводит к значительному снижению производительности выборки графической информации. Кроме того, векторизация изображений является достаточно сложным процессом, примыкающим к теории распознавания образов. А параметризация «живого» изображения практически невозможна. 3. Модели синтеза.

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

картинки и скорость ее генерации на порядки уступают растровому подходу.

Хотя для хранения графической информации применяются различные модели описания и представления, все же преобладающим большинством разработчиков в настоящее время используются растровые модели. Так, около 90% информации, представленной на WWW, занимают растровые изображения. Даже данные, первоначально имеющие инородную структуру, часто предлагаются пользователю в графическом виде. Это, например, всевозможные графики и диаграммы, сгенерированные на основе численной информации из электронных таблиц и баз данных. Для хранения изображений в справочных системах и мультимедийных средах, распространяемых на CD и DVD, также применяются растровые форматы хранения изображений. Сегодня существует огромное количество различных растровых форматов хранения и передачи графической информации. Однако, объем данных, представляющих растровое изображение, на практике оказывается слишком большим. Быстрый рост емкостей устройств хранения данных лишь стимулирует разработчиков на дальнейшее развитие средств мультимедиа. Следовательно, необходимо применять программно-аппаратные системы сжатия графической информации.

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

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

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

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

1. Разработаны технологии ГШЕ и РГОН сжатия без потерь графической растровой информации, эффективно сочетающие

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

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

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

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

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

статистические свойства данного потока и произведен отбор наилучших.

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

6. Создана программная система обеспечения технологии компактного хранения и оперативной выборки при работе с цифровыми и электронными картами.

Практическая ценность. В основу диссертационной работы положены результаты, полученные автором в ходе исследований, проводимых по плану НИОКР Федеральной службы геодезии и картографии России на 1995-1997 год, в рамках проведения ОКР «Экран» в НИИ ПМК при ННГУ.

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

Апробация полученных результатов. Полученные результаты внедрены в Федеральной службе России по геодезии и картографии в системе символизации картографического изображения на экранах коллективного и индивидуального пользования (ОКР «Экран») в подсистемах РАСТР и РАСТР-ЭКРАН; в Центральном картпроиз-водстве Военно-морского флота (280 ЦКП ВМФ); в НИИ ПМК (Н.Новгород) в объектно-ориентированной геоинформационной системе «Терра»; в НижНовЭнерго (Н.Новгород) в ГИС «Кабельные сети».

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

♦ факсимильное кодирование, блочное кодирование;

♦ моделирование длин серий;

♦ алгоритмы серии Лемпела-Зива;

♦ моделирование с предсказанием;

♦ иерархические (пирамидальные) методы представления;

♦ преобразования Фурье, Адамара, Хаара, Карунена-Лоэва, а также вейвлет-преобразования;

♦ локальные однородные хорошо приспособленные базисные функции и иерархически структурированное представление видеоинформации (бинарное усеченное разностное дерево существенных отсчетов);

♦ фрактальное сжатие.

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

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

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

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

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

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

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

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

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

Однако, развертка Гильберта-Пеано позволяет производить редукцию размерности только для квадратных растров, габариты которых совпадают со степенью числа 2. С целью преодоления

указанного недостатка в третьей главе дается алгоритм построения дискретного аналога кривой Пеано на базе рекурсивной конструкции Гильберта для прямоугольной области произвольного размера.

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

♦ смежные не только по горизонтали, но и по вертикали участки изображения оказываются близкими в генерируемом потоке информации;

♦ для квадратных областей со стороной 214 полученная кривая тождественно совпадает с конструкцией Гильберта;

♦ почти для всех пар смежных пикселов в полученной кривой соответствующие пикселы в растре являются четырехсвязными (т.е. касаются друг друга своими сторонами), а для ничтожной части остальных пар - восьмисвязными.

На нижеприведенном рисунке изображен пример такой специальной развертки для растра размером 10x9.

В четвертой главе даются два эффективных алгоритма сжатия графической растровой информации: РГОН (однопараметрический) и Ш1Е (двухпараметрический); приводятся их характеристики: расход памяти, производительность.

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

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

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

Рассмотрим этапы II, III, IV PIRH-кодирования более подробно. Этап II. Индексирование.

Пусть результирующий поток развертки Пеано состоит из символов алфавита А—{а^аг,...^^} (а, - суть атрибуты пикселов исходного изображения). Очевидно, что вероятность появления очередной буквы зависит от предыдущих букв и данный источник нельзя назвать Бернуллиевским. Вообще говоря, появление в

потоке символа a(t) зависит от предыстории {а(0),а(1).....a(t-l)}.

Рассмотреть такой источник довольно сложно. Однако, упрощение его до Марковского первого порядка вполне допустимо, т.к. существенную роль в вероятности появления a(t) играет a(t-l) в силу свойства кривой Пеано: a(t-l) и a(t) - смежные пикселы изображения.

Введем дискретную Марковскую цепь с конечным числом состояний а1,а2,...,а|Д|. Будем говорить об a(t) как об исходе испытания t, t>0; a(t) находится в состоянии i, если a(t)=ai-Вероятность попадания случайной величины a(t+l) в состояние j, если известно, что a(t) находится в состоянии i (одношаговая переходная вероятность), обозначим Pij(t-f-l), т.е.

Pii(t+1) = р { a(t+l) = aj | a(t) = }. Объединим Pij(t) в квадратные матрицы переходных вероятностей

plAlxlAl^).

P(t) =

j Ai (О />21(0

/>12 (О />22 (О

/>МС)

PiÂD

9

Р\А 1.(0 Р\А) 2(0 ••• Р\ЛМ |(0

, t>l.

Можно ли рассматривать данный Марковский процесс как стационарный, т.е. P(t) = Р ? Благодаря свойству кривой Пеано

группировать в результирующем потоке данные, относящиеся к тому или иному графическому объекту, матрица Р будет существенно зависеть от того графического объекта, коды которого преимущественно поступают на вход этапа II РГОН-компрессии, и, соответственно, зависеть от шага

Введем в рассмотрение конечный автомат К = ( А, 8=А, В, р, у ), где множество состояний Э дублирует входной алфавит А. В={ЬЬЬ2,...,Ь|А|} — выходной алфавит автомата Ь=у>(а,з) -

выходная функция автомата К. з'=^'(а,з) - переходная функция автомата К.

Определим закон «переработки» слов в алфавите А, подаваемых побуквенно на входной канал устройства с конечной памятью К, следующим образом: Уэ: \р(&,ъ) = а

Уз: р(а,8) = 0(а, рза(1;) ), а'=1,..., [А|, где д - некоторый функционал, зависящий от текущего входного символа а и от строки в матрицы переходных вероятностей Марковской цепи Р в момент времени

Цель второго этапа РШН-кодирования (обработка входного потока автоматом X) заключается в генерации результирующего потока символов алфавита В, удовлетворяющих в подавляющем большинстве случаев соотношению

Р(Ь1)»Р(Ь2)»...»Р(Ь|А|). (*)

Т.е. функционал # должен предсказывать появление символа а, ставя во взаимно однозначное соответствие ему символ Ь, индекс которого в алфавите В минимален.

Достичь поставленной цели можно следующим образом. Введем вектор Q=(qbq2.---,q|A|), где qj - элементы строки s матрицы P(t), упорядоченные по убыванию. Тогда # ( а , Q ) = Ь^, если qk=psa(t). Однако, на практике матрицы P(t) неизвестны. Построим адаптивный алгоритм, реализующий некоторое приближение функционала д. Для каждого состояния s конечного автомата К введем упорядоченный набор Vs:

Vs=(vis,v2s,...,v|A18), Vi8 е А,

V i*j: vts vjs.

При переходе автомата К из состояния s в состояние s' изменим Vs следующим образом. Пусть v4s = s'. Тогда:

Vjs (t+1) = Vjs (t), j < [Я-i] или j > i;

Vjs (t+1) = Vis(t), j = [Я-i];

Vjs (t+1) = v^8 (t), [A - i] < j < i. Здесь Я - параметр автомата К (экспериментальный выбор), 0<Я<1. И, наконец, приближенно определим i>: ^>(s',s) = bj. Заметим, что в частном случае при Я=0 автомат К в каждом отдельно взятом состоянии s производит трансляцию алфавита А в алфавит В по методу «сжатия с помощью стопки книг». Т.е. при Я=0 автомат К представляет собой Марковскую цепь из |А| методов «сжатия с помощью стопки книг». Практические исследования показали нецелесообразность Я=0 для сжатия технических изображений по развертке Пеано, так как стоимость PIRH-кодирования монотонно возрастает на интервале [О, Я0] и убывает на [ Я0, 1). Причем, в большинстве случаев Я°—1/2. Кроме того, при выборе Я=1/2 удобно вычислять [Я-i] при помощи операции битового сдвига. Автомат N¿=1/2 легко приспосабливается

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

Для полной определенности определим начальное состояние автомата X:

=

Щ, ./ = *

У = 1

Необходимо отметить основные различия между этапом индексирования и известным методом «сжатия с помощью стопки книг»:

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

На этапе индексирования символ всего лишь смещается к началу списка на величину, зависящую как от исходной его позиции, так и от параметра /.е[ОД), где к играет роль скорости адаптации. В двух крайних положениях X получим либо неадаптивный алгоритм (Я.=1), либо алгоритм Рябко (л=0). Если значение А. лежит достаточно близко к 1, перенастройка будет достаточно продолжительной.

2. В отличие от метода «сжатия с помощью стопки книг» на этапе индексирования (при А.=0) мы имеем несколько параллельно работающих алгоритмов Рябко, каждый из которых производит преобразование своего внутреннего состояния и запись в выходной поток только после появления во входном потоке

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

Совокупность таких алгоритмов с корректным механизмом переключения обладает большей памятью, не требует частой адаптивной перенастройки при изменениях частотных характеристик входного потока, чувствительна к изменениям условных вероятностных характеристик первого порядка. Этап III. Групповое кодирование.

Следующим шагом алгоритма PIRH-компрессии является кодирование длин серий символа алфавита В. Фактически, после проведения первых двух этапов PIRH-кодирования результирующее сообщение, состоящее из символов алфавита В, напоминает собой вырожденный случай из одних bj, что согласуется с соотношением ('•■)■ Для кодирования длин серий bj можно воспользоваться префиксным кодом Левенштейна записи натуральных чисел, так как обычная бинарная запись натуральных чисел не обладает свойством префиксности, а выделение ячейки с фиксированным числом двоичных разрядов неэффективно.

Пусть К - длина серии а Lev(K) - двоичная запись кода Левенштейна. Тогда:

log'"А-

Lev(K) = П ЯШ Ll0g<l0ga4'-°A-J,

(=1

где Bin*(x) - двоичная запись числа х с удаленной первой цифрой, всегда равной 1; log<M'(x) - функция, определенная следующим образом: log(1)(x)=j, если n<i)<x<nii+1); М - кратность выполнения данной операции; n(i) - функция, определенная индуктивно следующим

образом: п<°>=0, п<» = 2""'". Для длины кода Левенштейна справедливо:

| Lev(K) | = log К + log log К (1+0(1)). Этап IV. Устранение статистических колебаний частот кодов. Завершающим шагом алгоритма PIRH-компрессии является устранение статистических колебаний частот символов алфавита В. Классическое решение данной проблемы — использование методов кодирования по Хаффману. Стандартный алгоритм Хаффмана требует хранения вместе с кодами символов алфавита В информации об их частотах или, что более эффективно, информации о топологической структуре дерева Хаффмана. В тех случаях, когда техническое изображение разбито на небольшие фрагменты (для повышения производительности доступа к заданной части изображения), такое повышение стоимости кодирования оказывается неоправданным. Адаптивный алгоритм Хаффмана, хотя и не требует добавления к результирующему потоку какой-либо дополнительной информации, увеличивает число листьев на 1 и требует постоянной модификации дерева Хаффмана.

Заметим, что поток символов алфавита В по-прежнему в подавляющем большинстве случаев соответствует соотношению (*). Т.е. известна упорядоченность в алфавите В по вероятности, хотя

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

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

Пусть - множество монотонных источников, — избыточ-

ность универсального кодирования этого множества. Тогда:

2. Оптимальным с точностью до аддитивной единицы является код

Редкие нарушения соотношения (*) не оказывают значительного влияния на общую эффективность сжатия по РШН-технологии. Характеристика Р1ЯН -кодирования.

♦ Кодер и декодер полностью целочисленные.

♦ Средняя стоимость сжатия без потерь - менее 1 бита на пиксел (данная характеристика зависит от информационной насыщенности исходного изображения).

1оё 1 + 1оё 1оё | А | + 0(1).

Ч', для которого

♦ Расход памяти кодера/декодера — | А |2 X log | А |.

♦ Скорость работы кодера/декодера на изображении размера NxM с К-битной глубиной представления цвета - NxMx2K. Производительность эксплуатируемого в НИИ ПМК декодера в вычислительной системе на базе МП Pentium - не менее 1 Mb видеоданных в секунду.

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

В основе RRE-алгоритма (название было получено как сокращение от Rectangle Regions Encoding) лежит использование таких характеристик технического изображения, как ограниченность числа используемых в нем цветов (например, не более 256) и наличие в изображении сплошных однотонных заливок, покрывающих достаточно большие площади растра изображения. Существенное преобладание в картографических изображениях площадных объектов (по количеству занимаемых пикселов) определило основную идею RRE-кодирования.

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

♦ в пределах одной области встречаются пикселы только одного цвета,

♦ области образуют покрытие изображения.

Исследование различных методов генерации таких покрытий показало, что целесообразным является рассмотрение непересе-

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

Для выделения областей применяется следующий алгоритм:

1. Пометить все пикселы изображения как невыделенные.

2. Если все пикселы помечены как выделенные, то КОНЕЦ.

3. Среди невыделенных пикселов найти самые верхние, а среди них - самый левый. Обозначим его координаты (и).

4. Найти прямоугольник пикселов одного цвета с левым верхним углом в точке Цо) максимальной площади среди всех таких прямоугольников.

5. Записать данные прямоугольника (ширина, высота, цвет) и пометить его пикселы как выделенные.

6. Перейти к п.2.

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

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

объем представления графической информации до 4+30%, а применение кодов Хаффмана улучшает этот показатель еще примерно в три раза.

Однако, существует класс изображений, по характеристикам близкий к полутоновым изображениям (картографические изображения, полученные с применением механизма интерполяции цвета), для которого характерно наличие полутоновых переходов на границах областей и, как следствие, большое количество (до 15%) отдельных пикселов, неподдающихся объединению в прямоугольные области. Эффективное применение ГШЕ-кодирования для таких изображений основано на расширении вышеприведенного базового алгоритма следующими дополнениями. Во-первых, необходимо предусмотреть возможность особого кодирования прямоугольников 1x1 (отдельных пикселов), количество которых может составлять до 70% от общего числа прямоугольных областей, одним битом (вместо обычного ширина © высота). Использование в каждом конкретном случае особого кодирования определяется автоматически по собранным статистическим данным. Оно имеет смысл, если отдельные пикселы составляют не менее половины от общего числа прямоугольников. Во-вторых, так как последовательность атрибутов цвета подряд идущих прямоугольников сильно коррелированна, вводится некоторый аналог второго этапа (индексирование) РЮН-кодиро-вания для эффективной упаковки информации о цвете прямоугольников.

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

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

Продемонстрируем эффективность RRE-сжатия в сравнении с PIRH-кодированием на примере картографического изображения в разрешении 1693.367 DPI (межточечный интервал 15 микрон) с глубиной представления цвета 3-3-2. Характеристики исходного изображения: размер в пикселах — 23600x29001, размер атрибута пиксела в битах - 8, размер дампа изображения в байтах -684 423 600.

Формат Размер

RRE PIRH 12 788 100 14 722 034

Традиционные алгоритмы хранения растровой графической информации имеют существенно худшие коэффициенты сжатия. Например, размер GIF-файла в данном случае составляет 21 150 606, что на 65% больше размера файла в формате RRE.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

информации, для обеспечения которой:

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

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

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

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

электронными картами. ПО внедрено в различных организациях Российской Федерации.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Кудин A.B.

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

Распознавание образов и анализ изображений: Новые информационные технологии: III конф.: Тезисы докладов.

- Нижний Новгород, 1997.

2. Кудин A.B.

Эффективное хранение растровых картографических документов.

Распознавание образов и анализ изображений: Новые информационные технологии: III конф.: Тезисы докладов.

- Нижний Новгород, 1997.

3. Кудин A.B.

Алгоритм PIRH-кодирования технических изображений. Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление.

- Нижний Новгород: Изд-во Нижегородского ун-та, 1998. Вып. 1 (18).

4. Кудин A.B.

Построение дискретного аналога рекурсивной конструкции Гильберта в задачах компрессии растровых изображений. Методы и средства обработки сложной графической информации: V конф.: Тезисы докладов.

- Нижний Новгород, 1998.

5. Кудин A.B.

Организация доступа к сверхбольшим изображениям. Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление.

— Нижний Новгород: Изд-во Нижегородского ун-та, 1998. Вып. 2 (19).

6. Кудин A.B., Жерздев C.B.

Алгоритм RRE-кодирования технических изображений. Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление.

— Нижний Новгород: Изд-во Нижегородского ун-та, 1998. Вып. 2 (19).

7. Кудин A.B., Жерздев C.B., Жерздев A.B.

Свертка растра пикселов в последовательный образ в алгоритме PIRH-кодирования технических изображений. Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление.

— Нижний Новгород: Изд-во Нижегородского ун-та, 1999. Вып. 1 (20).

Введение

Глава I Классические методы компрессии и передачи графической растровой информации.

Глава II Обеспечение оперативного доступа к фрагментам болыпеформатных растровых документов.

Глава III Редукция размерности прямоугольного растра пикселов.

Глава IV Сжатие графической растровой информации.

Глава V Программное обеспечение поддержки технологии эффективного хранения и оперативного отображения картографических растровых документов.

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

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

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

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

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

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

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

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

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

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

Хотя для хранения графической информации применяются различные модели описания и представления, все же преобладающим большинством разработчиков в настоящее время используются растровые модели. Так, около 90% информации, представленной на WWW, занимают растровые изображения. Даже данные, первоначально имеющие инородную структуру, часто предлагаются пользователю в графическом виде. Это, например, всевозможные графики и диаграммы, сгенерированные на основе численной информации из электронных таблиц и баз данных. Для хранения изображений в справочных системах и мультимедийных средах, распространяемых на CD и DVD, также применяются растровые форматы хранения изображений.

Существует огромное количество различных растровых форматов хранения и передачи графической информации. Такое многообразие объясняется несколькими причинами. Во-первых, развитие аппаратных и алгоритмических средств машинной графики происходило в последнее время крайне интенсивно и, как следствие, разработчики не имели возможности согласовывать свои усилия. Во-вторых, многие программисты предпочитали использовать свои собственные форматы хранения графической растровой информации вместо соответствующей поддержки стандартных форматов. Частично это было оправдано. Например, прежде очень популярный формат PCX сегодня практически не используется. В-третьих, иногда удобные для работы форматы оказывались запатентованными. Так, например, с 1994 года фирма Unisys (владелец патента LZW) стала брать плату с разработчиков, использующих GIF. В-четвертых, во многих форматах не были поддержаны те технические возможности устройств ввода/вывода графики, которые реализовались лишь через несколько лет после утверждения формата на рынке программного обеспечения.

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

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

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

Проиллюстрируем вышесказанное. Всего лишь одно фотографическое изображение размером 1024x768 пикселов с 24-битной глубиной представления цвета требует для своего хранения 2 Мбайт памяти. Библиотека таких изображений легко займет все свободное пространство современного носителя информации.

В последние годы происходит становление новой высокотехнологичной отрасли. Речь идет о цифровых фотоаппаратах. В ближайшее время планируется запустить в массовое производство аппараты с разрешением до 4 мегапикселов по цене не более $500. При этом стоимость одной фотографии нулевая! Действительно, растровое изображение сохраняется в памяти компьютера и может быть впоследствии удалено. Использование высокоэффективных программно-аппаратных методов сжатия растров пикселов позволяет хранить в оперативной памяти цифрового фотоаппарата большее число снимков без записи во внешнюю память ЭВМ.

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

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

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

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

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

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

Научная новизна диссертационной работы заключается в следующем: Разработаны технологии 1ШЕ и РП1Н сжатия без потерь графической растровой информации, эффективно сочетающие взаимосогласованные модели развертки графической информации, алгоритмы и методы устранения корреляционной и статистической избыточности.

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

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

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

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

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

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

Создана программная система обеспечения технологии компактного хранения и оперативной выборки при работе с цифровыми и электронными картами.

Практическая ценность. В основу диссертационной работы положены результаты, полученные автором в ходе исследований, проводимых по плану НИОКР Федеральной службы геодезии и картографии России на 1995-1997 год, в рамках проведения ОКР «Экран» в НИИ ПМК при ННГУ.

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

Апробация полученных результатов. Полученные результаты внедрены в Федеральной службе России по геодезии и картографии в системе символизации картографического изображения на экранах коллективного и индивидуального пользования (ОКР «Экран») в подсистемах РАСТР и РАСТР-ЭКРАН; в Центральном картпроизводстве Военно-морского флота (280 ЦКП ВМФ); в НИИ ПМК (Нижний Новгород) в объектно-ориентированной геоинформадионной системе «Терра»; в НижНовЭнерго (Н.Новгород) в ГИС «Кабельные сети».

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

Практические результаты и выводы, сделанные при работе по теме диссертации, нашли свое отражение в 7 опубликованных печатных работах.

Содержание работы. Диссертация состоит из пяти глав:

1. Классические методы компрессии и передачи графической растровой информации.

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

2. Обеспечение оперативного доступа к фрагментам большеформатных растровых документов.

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

3. Редукция размерности прямоугольного растра пикселов.

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

Сжатие графической растровой информации.

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

Программное обеспечение поддержки технологии эффективного хранения и оперативного отображения картографических растровых документов.

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе создана технология эффективного хранения и оперативного отображения картографической растровой информации, для обеспечения которой:

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

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

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

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

1. Александров В.В., Горский Н.Д.

2. Представление и обработка изображений. Рекурсивный подход.- JI: Наука, 1985.2. Анденсон Т.

3. Введение в многомерный статистический анализ.- М: Наука, 1963.3. Ахмед Н., Pao K.P.

4. Ортогональные преобразования при обработке цифровых сигналов.- М: Связь, 1980.4. Бутаков Е.А. и др.

5. Обработка изображений на ЭВМ.- М: Радио и связь, 1987.5. Васильев В.Н., Гуров И.П.

6. Компьютерная обработка сигналов в приложении к интерферо-метрическим системам.- СПб: БХВ-Санкт-Петербург, 1998.6. Васин Ю.Г.

7. Диалоговые системы в задачах оптимизации и классификации.- Современное состояние теории исследования операций. Под ред. Н.Н.Моисеева.1. М: Наука, 1979.7. Васин Ю.Г.

8. Нерегулярные выборки отсчетов исходной информации и задача кодирования электрокардиографических данных.- Кибернетика и вычислительная техника: Сборник статей. К: Наукова Думка, 1978, вып. 41.8. Васин Ю.Г.

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

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

11. Васин Ю.Г., Бакараева В.П.

12. Адаптивное сжатие изображений с использованием кривой Пеано.- В кн.: Всесоюзная конференция «Обработка изображений и дистанционные исследования», тезисы докладов. Новосибирск, 1984.

13. Васин Ю.Г., Бакараева В.П.

14. Адаптивная фильтрация и сжатие изображений с использованием кривой Пеано.- Возможности исследования природных ресурсов дистанционными методами: сборник статей.1. Л: ЛГУ, 1986.

15. Васин Ю.Г., Бакараева В.П.

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

17. Алгоритмы приспособленного базиса в задачах распознавания образов.- Изв. АН СССР. Техническая кибернетика. 1971, №4.14. Васин Ю.Г., Неймарк Ю.И.

18. Об одном методе кодирования больших массивов информации в связи с задачами медицинской диагностики.- Изв. вузов. Радиофизика. 1968, Т.11, №7.

19. Васин Ю.Г., Неймарк Ю.И., Савина Т.В. Выделение ЭКГ-сигналов из миографического шума.- Начальные формы сосудистых заболеваний нервной системы. МЗ РСФСР, ГМИ, НИИ неврологии АМН СССР.1. Горький, 1977, вып. 82.16. Васин Ю.Г., Сорокин В.А.

20. Адаптивное сжатие линейной графической информации.- Оптимизация и математическое обеспечение САПР: Межвуз. сб.1. Горький: ГГУ, 1980.17. Ватанабе С.

21. Разложение Карунена-Лоэва и факторный анализ. Теория и приложения.- Автоматический анализ сложных изображений. М: Мир, 1969.18. Виттих В.А., Сергеев В.В.

22. Метод сжатия изображений с предсказанием и адаптивной дискретизацией.- Изв. вузов, Приборостроение, 1976, Т.19, №12.19. Кенцл Т.1. Форматы файлов Internet.- СПб: Питер, 1997.20. Климов A.C.

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

24. Коэндеринк Дж. Дж., ван Доорн А. Дж.

25. Новый способ растровой развертки, сохраняющий топологию изображения.- ТИИЭР, 1979, Т.67, №10.22. Кричевский P.E.

26. Сжатие и поиск информации.- М: Радио и связь, 1989.23. Кудин A.B.

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

28. Блочное кодирование графических материалов.- ТИИЭР, 1980, Т.68, №4.25. Левенштейн В.И.

29. Об избыточности и замедлении разделимого кодирования натуральных чисел.- Проблемы кибернетики. М: 1968, вып. 20.

30. Маслюк Л.Л. Дайджест вейвлет-анализа.- М: Компьютерра, 1998, №8(236).

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

32. Простые эффективные методы кодирования без потерь для передачи многоуровневых и двухуровневых изображений с постепенным воспроизведением.- ТИИЭР, 1980, Т.68, №7.

33. Орищенко В.И., Санников В.Г., Свириденко В.А. Сжатие данных в системах сбора и передачи информации.- М: Радио и связь, 1985.30. Павлидис Т.

34. Алгоритмы машинной графики и обработки изображений.- М: Радио и связь, 1986.31. Петухов А.П.

35. Периодические дискретные всплески.- Алгебра и анализ, 1996, №3.32. Плесков A.B.

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

37. Поспелов В.В., Кислицына М.А.

38. Использование преобразования Хаара для модификации алгоритма JPEG сжатия изображений.- Распознавание образов и анализ изображений: новые информационные технологии, III конф., тезисы докладов. Нижний Новгород, 1997.34. Претт У.

39. Цифровая обработка изображений.- М: Мир, 1982.35. Роджерс Д.

40. Алгоритмические основы машинной графики.- М: Мир, 1989.

41. Роджерс Д., Адаме Дж. Математические основы машинной графики.- М: Машиностроение, 1980.37. Романов В.Ю.

42. Популярные форматы файлов для хранения графических изображений на IBM PC.- М: Унитех, 1992.38. Рябко Б.Я.

43. Кодирование источника с неизвестными, но упорядоченными вероятностями.- Проблемы передачи информации, 1979, Т. 14, №2.39. Рябко Б.Я.

44. Сжатие информации с помощью стопки книг.- Проблемы передачи информации, 1980, Т. 16, №4.40. Сергеев В.В.

45. Обработка изображений с использованием развертки Гильберта-Пеано.- Автометрия, 1984, №2.41. Солодовников А.И.

46. Синтез полных систем ортонормированных функций, имеющих алгоритм быстрого преобразования.- Вопросы теории систем автоматического управления: Меж-вуз. сб.1. Л: ЛГУ, 1978, вып. 4.

47. Солодовников А.И., Канатов Н.И., Спиваковский A.M. Методы обобщенных спектральных преобразований в задачах оперативного сжатия информации.- Вопросы кибернетики: Автоматизация экспериментальных исследований.

48. М: Научный совет по комплекс, пробл. «Кибернетика» АН СССР, 1979.43. Стронгин Р.Г.

49. Численные методы в многоэкстремальных задачах.- М: Наука, 1978.

50. Трахтман A.M., Трахтман В.А.

51. Основы теории дискретных сигналов на конечных интервалах.- М: Сов. радио, 1975.45. Уинтц П.

52. Кодирование изображений посредством преобразований.- ТИИЭР, 1972, Т.60, №7.46. Фарков Ю.А.

53. Ортогональные всплески на локально компактных абелевых группах.- Функциональный анализ и его приложения, 1997, №4.

54. Фурман Я.А., Юрьев А.Н., Яншин В.В.

55. Цифровые методы обработки и распознавания бинарных изображений.- Красноярск: Изд-во Красноярского ун-та, 1992.48. Хантер Р., Робинсон А.Х.

56. Международные стандарты кодирования для цифровой факсимильной связи.- ТИИЭР, 1980, Т.68, №4.49. Хаффман Д.А.

57. Метод построения кодов с минимальной избыточностью.- Кибернетический сборник. М: 1961, вып. 3.50. Шильман С.В.

58. Адаптивная фильтрация временных рядов.- Н.Новгород: Изд-во ННГУ, 1995.51. Шлихт Г.Ю.

59. Цифровая обработка цветных изображений.- М: ЭКОМ, 1997.52. Эндрюс Г.

60. Применение вычислительных машин при обработке изображений.- М: Энергия, 1977.53. Яншин В.В.

61. Анализ и обработка изображений: принципы и алгоритмы.- М: Машиностроение, 1995.54. Ярославский Л.П.

62. Введение в цифровую обработку изображений.- М: Сов. радио, 1979.55. Ясуда Я.

63. Обзор методов цифрового кодирования факсимильных данных в Японии.- ТИИЭР, 1980, Т.68, №4.56. Burt P.J., Adelson E.H.

64. The Laplasian pyramid as a compact image code.- IEEE Trans. Comm., Vol. COM-31.57. Daubechies I.1. Ten Lectures on Wavelets.- SIAM, 1992.

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

66. Horovitz S.L., Pavlidis T.

67. Picture segmentation by a tree traversal algorithm.- ACM Journal, 1976, V.23, №4.

68. Hunter M., Steiglitz K. Operations on image using quadtrees.- IEEE Trans, on PAMI, 1, 1979.61. Kawaguchi E., Endo T.

69. On a method of binary picture representation and its application to data compression.- IEEE Trans, on PAMI, 2, 1979.

70. Pennebaker W.B., Mitchell J.L.

71. JPEG: Still Image Data Compression Standard.- International Thomson Computer Press, London, UK, 1993.63. Quinqueton J., Berthod M.

72. A locally adaptive Peano scanning algorithm.- IEEE Trans., 1981, Vol. PAMI-3, 4.

73. Roos R., Viergever M.A., Dikje M.C., Peters J.H. Reversible intraframe compression of medical images.- IEEE Trans.Medical.Imaging, 1988, vol.7.65. Samet H.

74. Data structures for quadtree approximation and compression.- Commun. ACM, 28, 9, 1985.66. Samet H.

75. The quadtree and related hierarchical data structures.- Comput. Surveys, 16, 2, 1984.67. Strobach P.1.age coding based on quadtree-structured recursive least squares approximation.- ICASSP-89, Int. Conf. Acoust. Speech and Signal Process, 3, 1989.1. АКТ

76. Зам. Начальника 280 ЦКIIВМФ Капита)опов

77. Утверждаю» Зам. директора НИИ ПМК по научной работе, д.ф.-м .п., профессор1. Попомарсико В.П.0{ » Н 2000 г.1. Акт