Метод компрессии картографических изображений на основе иерархической переиндексации Баврина Алина Юрьевна

Содержание к диссертации

Введение

1. Задача компрессии палитровых изображений . 15

1.1. Основные характеристики методов компрессии изображений 15

1.2. Обоснование необходимости разработки метода компрессии 17

1.2.1. Краткий обзор методов безошибочной компрессии изображений... 17

1.2.2. Оценка степени пригодности методов безошибочной компрессии изображений для ГИС 23

1.3. Общая схема метода компрессии 26

1.3.1. Идея метода 26

1.3.2. Компрессия изображения 27

1.3.3. Декомпрессия изображения 29

1.4. Задачи, возникающие при разработке Метода компрессии на основе иерархической переиндексации 30

1.4.1. Задача выбора количества иерархических уровней 30

1.4.2. Задача выбора способа формирования иерархических уровней 30

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

1.4.4. Задача статистического кодирования списков уровней 32

1.4.5. Задача выбора размеров блоков 32

1.4.6. Задача разработки архивного формата 32

1.4.7. Задача выбора размеров фрагментов, обрабатвтаемых независимо 33

1.4.8. Задача проведения вычислителвного эксперимента 33

1.5. Ввтводы и резулвтаты 37

2. Алгоритмы, реализующие метод компрессии на основе иерархической переиндексации 39

2.1. Выбор количества иерархических уровней 39

2.2. Алгоритмы формирования иерархических уровней 40

2.2.1. Базовый алгоритм 40

2.2.2. Использование общего индекса для однократно встречающихся блоков 42

2.2.3. Обеспечение работоспособности для длинных списков 45

2.2.4. Адаптивный выбор параметра Г 47

2.3. Алгоритмы обработки цветовых плоскостей 52

2.3.1. Использование взаимосвязей между цветовыми плоскостями 54

2.3.2. Порядок рассмотрения цветовых плоскостей 58

2.3.3. Кодирование контурных цветовых плоскостей 61

2.4. Алгоритм статистического кодирования данных уровня 66

2.5. Выбор размеров блоков 69

2.6. Выводы и результаты 70

3. Программная реализация и экспериментальное исследование метода на основе иерархической переиндексации 71

3.1. Архивный формат 71

3.2. Исследовательский программный комплекс 73

3.2.1. Организация программного обеспечения 73

3.2.2. Консольная программа компрессии изображения 75

3.3. Экспериментальные исследования 76

3.3.1. Выбор размеров фрагментов 76

3.3.2. Сравнение эффективности компрессии методом на основе иерархической переиндексации и другими методами 82

3.4. Выводы и результаты 85

Заключение 86

Список использованных источников

• Обоснование необходимости разработки метода компрессии
• Задача представления данных изображения для эффективного применения метода компрессии
• Использование общего индекса для однократно встречающихся блоков
• Консольная программа компрессии изображения

Введение к работе

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

Актуальность темы

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

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

1) слабость средств отображения векторной графики Wcb-браузера клиента (распространенные Web-браузеры не могут, к примеру, нарисовать полигон по координатам его вершин и заполнить его площадь некоторым условным знаком или регулярной текстурой);

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

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

Требования к методу компрессии и к структуре компрессированных данных определяются способом использования картографических изображений в ГИ.С: при удаленном доступе к картографическим данным (через Интернет).

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

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

1) высокая степень компрессии (позволяет значительно сократить время передачи компрессированных данных по сети и уменьшить дисковое пространство, необходимое для хранения этих данных);

2) высокая скорость декомпрессии (обеспечивает отсутствие ощутимой задержки при декомпрессии изображения на клиенте).

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

Картографические изображения обладают рядом особенностей:

1) небольшое количество цветов (обычно 4-30);

2) отсутствие плавных изменений цвета;

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

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

К настоящему времени разработано много методов компрессии изображений [12, 18, 19, 26, 45, 68]: статистические, словарные методы, методы кодирования с преобразованием, методы кодирования с предсказанием, методы с сегментацией, фрактальные методы и др. Изучению различных аспектов проблемы компрессии посвящены труды российских ученых: Д. С. Лебедева, Н. Н. Красилы-шкова, Ю. М. Штарькова, В.В.Сергеева, Ю.Г.Васина и др., а также зарубежных: Р. Грехема (R. Graham), Дж. О. Лимба (J. О. Limb), У. Претта (W. К. Pratt), А. Джайна (А. К. Jain), M. Кунта (М. Kunt). Однако известные методы не в полной мере учитывает специфику картографических изображений.

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

Работы по тематике диссертации были поддержаны грантами Российского фонда фундаментальных исследований (проект № 04-01-96507), Министерства образования РФ и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02), Министерства образования и науки Самарской области (проект 266Е2.3 К).

Цель и задачи исследований

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

1. Анализ известных методов безошибочной компрессии изображений и их характеристик. Определение этапов разработки и исследования НОЙОГО метода безошибочной компрессии.

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

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

Методы исследований

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

Научная новизна работы

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

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

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

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

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

Практическая ценность работы

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

Реализация результатов работы

Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в Институте систем обработки изображений РАН и ЗАО «Самара-Информспутник», что подтверждено актами внедрения (см. Приложение 2).

Апробация работы

Основные результаты диссертации докладывались на следующих конференциях:

- на международной конференции «Automation, Control and Information Technologies» (ACJT), Новосибирск, 2005;

- на 3-й летней школе по дифракционной оптике и обработке изображений, Самара, 2005; - на 12-ой Всероссийской конференции «Математические методы распознавания образов» (ММРО), Москва, 2005;

- на научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» (ПИТ), Самара, 2006.

Публикации

По теме диссертации опубликовано шесть работ. Работа [6] выполнена автором единолично. В работах [3, 37] автору принадлежит формальное описание метода компрессии и алгоритмов формирования иерархических уровней. В работах [4, 5, 7] кроме формального описания метода компрессии и алгоритмов формирования уровней автору принадлежат алгоритм выбора порядка обработки цветовых плоскостей и алгоритмы обработки цветовых плоскостей. Во всех работах автору принадлежат программная реализация и экспериментальные исследования метода и входящих в его состав алгоритмов. 

Ниже в тексте диссертации ссылки на работы автора помечены звездочками ( ).

Структура диссертации

Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и двух приложений. Она изложена на 90 страницах машинописного текста (без приложений), содержит 26 рисунков, 10 таблиц, список использованных источников из 82 наименований.

Краткое содержание диссертации

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

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

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

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

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

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

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

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

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

На защиту выносятся

1. Новый метод безошибочной компрессий картографических изображений на основе иерархической переиндексации.

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

3. Алгоритмы обработки цветовых плоскостей: алгоритм выбора порядка обработки цветовых плоскостей, алгоритмы предварительной обработки цветовых плоскостей, алгоритм обработки преимущественно контурных цветовых плоскостей.

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

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

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

Обоснование необходимости разработки метода компрессии

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

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

Также следует отметить, что некоторая часть методов компрессии без потерь разработана для двухуровневых (черно-белых) изображений. Эти методы могут быть применены к палитровому изображению, если произвести его разбиение на битовые плоскости и обрабатывать каждую битовую плоскость независимо. Эффективность компрессии может быть повышена, если для получения битовых плоскостей использовать рефлексные коды Грея [26, 48], так как два последовательных числа в кодах Грея отличаются только в одном бите.

Статистические методы

Статистические методы компрессии основаны на использовании неравномерности распределения вероятностей исходных данных. Широко используются такие статистические методы, как кодирование Хаффмана [27, 67], кодирование длин серий (КДС или RLE) [9, 19, 22, 28, 31], арифметическое кодирование [67, 71, 77] и др.

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

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

Тем не менее, статистические методы успешно используются совместно с другими методами для сокращения избыточности преобразованных данных. КДС используется в формате TIFF, TGA, PCX. Модификация кода Хаффмана реализована в формате TIFF и методе Lossless JPEG [42]. Арифметический кодер используется в стандарте JBIG [52], JPEG-2000 [50]. КДС используется совместно с Хаффманом в алгоритме CCITT-3 [40] для факсимильной компрессии двухуровневых изображений.

Словарные методы

Словарные методы основаны на замене некоторых последовательностей символов на коды, трактуемые как индексы некоторого словаря. Большинство словарных методов основано на методе Зива:Лемпеля (LZ) [81].

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

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

На LZ основаны многие архиваторы: ZIP, ARJ, WinRAR, 7-Zip и др,, а также графический формат GIF. Широко распространенный графический формат TIFF опционально включает в себя компрессию методом LZ.

Методы кодирования с преобразованием

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

Использование большинства известных дискретных спектральных преобразований [2, 22, 33, 43] делает, принципиально невозможным организацию компрессии без потерь.

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

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

Такой подход позволяет учитывать взаимосвязи между цветовыми плоскостями, причем способ этого учета специфичен для метода компрессии. Например, при контекстном моделировании, статистика уже обработанных цветовых плоскостей может быть использована для улучшения предсказания на обрабатываемой цветовой плоскости [54]. Следует заметить, что эффективность компрессии также зависит от порядка рассмотрения цветовых плоскостей.

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

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

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

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

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

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

Для исследования разработанных алгоритмов, метода в целом и сравнения его с другими методаминеобходимо проведение вычислительного эксперимента. Эта задача в основном решается в п. 3.3, но по мере необходимости и на протяжении второго раздела.

Работа метода компрессии и алгоритмов, входящих в состав метода, проверялась и исследовалась на двух типах картографических изображений: изображения области и изображении города. Изображения были получены из векторных карт Самары и Самарской области средствами ГИС ИнГЕО. Для иллюстрации работы алгоритмов и сравнения их эффективности использовались небольшие изображения, размером 256x256 (рис. 1.1, 1.2). Для проведения экспериментов по сравнению эффективности разработанного метода с другими использовались изображения большого размера (рис. 1.3, 1.4).

Использование общего индекса для однократно встречающихся блоков

В п. 1.4.2 был в общем виде описан алгоритм формирования каждого следующего иерархического уровня. Опишем его еще раз для важного частного случая: Мх-Ы2=2 и 6 = 8.

Для произвольного уровня / по матрице уровня х формируется и упорядочивается по числу встречаемости И7 } (в порядке убывания) список различных блоков С( размера 2x2. Вектор списка с индексом к состоит из четырех элементов: cf =(С (о\С (\),С (2ІС (3)), к = О М, где К{1) - длина списка. Матрица следующего уровня JT + формируется из индексов к, соответствующих блокам матрицы х в списке С(-1 (частный случай формулы 1,1): х ]\пип2) = к, к: хи\2пи2п2) = СР(0), х{1\2пь2п2+1) = С)?(\), (/)(2771+l,2/72) = Cf(2), [ JCW (2n, +1,2 +1) = СР (3), ї ., _n N2 где и(=0,—-у-1, н2=0,—- --1, 1-0,1-2. Размеры матрицы уровня (/ + 1) меньше размеров матрицы уровня / вдвое по каждой координате. На рисунке 2.1 показан пример работы данного алгоритма для изображения размером 8x8. Матрица х представляет исходное изображение; матрицы х , х получены с помощью правила (2.1). С помощью стрелок и рамок на рисунке показано формирование матрицы следующего уровня. На матрице xw выделен блок размера 2x2, левый верхний угол которого имеет координаты (4,6). Этот блок соответствует вектору списка С, -1 = (2,2,2,2) и встречается на изображении W = 3 раза. Соответствующий элемент матрицы следующего уровня равен индексу к блока в списке, то есть х (2,3) = 1. 4 3 2б 5 21 3 7 1 1 и 24 (1) Ж ДО) 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 2 2 0 0 0 1 1 2 2 2 0 0 1 2 2 2 2 2 D 1 2 2 2 2 2 с(о) wm к 0 о D 0 5 3 2 2 1 1 1 1 2 2 2 2 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 01 12 12 2 2 C(l) Q 4 0 0 2 5 0 2 0 3 3 7 6 ± 1 1 Уровень „(2) 0 1 2 3 і I Уровень Уровень Q Рис. 2.1. Пример кодирования изображения базовым алгоритмом для Nl - N2 = 8 Рассмотрим алгоритм декомпрессии. Производится декодирование матрицы старшего уровня и списков уровней, после чего последовательно восстанавливаются матрицы всех остальных уровней, используя формулу (2.1) в обратном направлении: (/)(2n1(2B7) = Cf(0), (2,,,2 1) (,), ест П2) = к, х{І)(2щ+12п2+\) = СР(3), , N, Nj - Описанный базовый алгоритм имеет следующие недостатки. Во-первых, существует ограничение на длину списков. При использовании восьмибитного формата записи элементов матриц и списков уровней оно выглядит следующим образом: /0 256,/ = 0,1-2.

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

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

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

Пусть !Р - число векторов списка О с числом встречаемости более единицы, т.е. W{- () = 1, к г . При формировании матрицы х 1 блоки матрицы х , встречающиеся один раз, будут кодироваться индексом Т-К

Тогда формирование матрицы следующего уровня х1-+ будет происходить Следующим образом: \кл т{1) х м\пип2) = \ Т,к Т(1) /V, л N Аг = ОэЛГ(0 -1, / = 0,1-2. Такой способ формирования матрицы следующего уровня позволяет смягчить ограничение на длину списков уровней:

Консольная программа компрессии изображения

ИГЖ организован в виде консольной программы компрессии изображений. Параметры метода компрессии передаются консольной программе через командную строку. Приведем описание вызова консольной программы. J) Компрессия: hri.exe a Image Archive VFragment HFragmenl ColorPlaneFlag NeighbourNum ChainLen, где hri. exe - имя программы a - ключ режима компрессии Image - имя изображения Archive - имя архива VFragment - размер фрагмента по вертикали ColorPlaneFlag - флаг использования разделения на цветовые плоскости NeighbourNum - значение параметра Ты (см. п. 3.3.3) ChainLen - значение параметра Ть (см. п. 3.3.3)

Обязательными являются параметры hri.exe, a, Image, Archive. Остальные параметры являются необязательными и при их отсутствии соответствующим переменным присваиваются значения по умолчанию.

2) Декомпрессия: hri.exe е Image Archive, где е - ключ режима декомпрессии.

Для проведения экспериментальных исследований был использован разработанный исследовательский программный комплекс.

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

Исследовалась зависимость коэффициента компрессии от размера фрагмента. Эта зависимость для изображений «Карта области» и «Карта города» показана на рисунках 3.3 и 3.4 соответственно.

На рисунках пунктирной линией показаны коэффициенты компрессии, полученные с использованием теоретической оценки (энтропии) объема статистически кодированных данных списков. Из рисунков видно, что при использовании разделения на цветовые плоскости коэффициент компрессии уменьшается с уменьшением размеров фрагментов. Разделение на цветовые плоскости перестает быть эффективнее применения метода компрессии непосредственно к изображению при размерах фрагментов, меньших 128 для изображения «Карта области» и 256 для изображения «Карта города». Для изображения «Карта города» размеры фрагментов, равные 512, обеспечивают максимальный коэффициент компрессии в случае, когда разделение на цветовые плоскости не производится.

Проанализируем причины снижения эффективности компрессии с уменьшением размеров блоков.

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

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

На рис. 3.5 и 3.6 показаны количественные оценки снижения эффективности компрессии, вызванные недостаточной эффективностью статистического кодера и необходимостью сохранения в архиве служебной информации. Снижение эффективности статистического кодирования вычислялось как процент разницы объема архива УА и объема архива, полученного с помощью теоретической оценки статистически кодированных VA-Vmo данных списков V от объема архива ("Стат. кодер" = --100%). vA теор Снижение эффективности, вызванное наличием в архиве служебной информации, вычислялось как процент объема этой информации Усл от 100%). объема архива VA ("Служебная информация