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

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

"У7Й

БАВРИНА Алина Юрьевна

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

Специальность 05.13.18 -

Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

САМАРА - 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П.Королева»

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

Ведущее предприятие:

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

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

кандидат технических наук, старший научный сотрудник О. Л. Куляс

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

Защита состоится " 1 " декабря 2006 г. в

10

часов

на заседании диссертационного совета Д 212.215.05 при Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П.Королева» по адресу: 443086, Самара, Московское шоссе, 34.

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

Автореферат разослан "31 " октября 2006 г.

Ученый секретарь

диссертационного совета А.А. Калентьев

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

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

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

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

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

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

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

К настоящему времени разработано много методов компрессии изображений: статистические, словарные, методы кодирования с преобразованием, кодирования с предсказанием, методы с сегментацией, фрактальные методы и др. Изучению различных аспектов проблемы компрессии посвящены труды российских ученых: Д. С. Лебедева, Н. Н. Красильникова, Ю. М. Штарькова, В. В. Сергеева, Ю. Г. Васина, а также зарубежных: Р. Грехема (R. Graham), Дж. О. Лимба

(J. О. Limb), У. Претта (W. К. Pratt), А. Джайна (А. К. Jain), М. Кунта (М. Kunt). Однако известные методы не в полной мере учитывают специфику картографических изображений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- на 3-й летней школе по дифракционной оптике и обработке изображений, Самара, 2005;

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

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

Публикации

По теме диссертации опубликовано шесть работ.

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

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

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

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

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

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

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Предлагаемый метод компрессии на основе иерархической переиндексации заключается в последовательном формировании иерархических уровней представления изображения (см. рис. 1). Иерархический уровень с номером I состоит из матрицы х^'К списка С^ и вектора . Матрица х^ разбивается регулярной сеткой на непересекающиеся блоки размера А/] хМ2. Список С^'' формируется из различных блоков (каждый элемент списка представляет собой вектор С/р, компонентами которого являются значения блоков матрицы индексов д;^, упорядоченные в соответствии

г« Ст

О •■»«+!)

Уровень/

Стат. кодирование

1

Архив

Рис. 1. Схема метода компрессии

с некоторой разверткой). Вектор

цгС)

состоит из чисел встречаемости этих блоков

на матрице. Список

с<0

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

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

*(/+1)("1>"2) = *. к-.х^\Мхп1+1,М1П2+Л = С(1\1М1+]), (1)

где i = 0,Му —1, ] = 0,М2 — 1 - индексы внутри блока.

Статистически кодированный список

С(0

сохраняется в архив. Далее те же действия производятся над матрицей в архив сохраняется статистически

кодированный список и т.д. Матрицей младшего уровня х^ является

матрица изображения х. На последнем уровне формирование списка не производится и в архив сохраняется статистически кодированная матрица (£ - количество иерархических уровней).

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

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

К^ <2\ / = 0,1,-2. (2)

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

При декомпрессии из архива извлекаются и декодируются данные списков С^,/ = 0,£ —2 и матрица старшего уровня . Далее последовательно

формируются матрицы х", 1 = 0,£ —2 с использованием

С( 0

и х(1+1>, применяя

формулу (1) в обратном направлении. Матрица я:*-0-1 представляет собой искомую матрицу декомпрессированного изображения.

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

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

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

= minilog^ N{ -,logMl N2), где jV] и N2 - размеры изображения.

Объем архива VA можно представить как сумму объемов статистически кодированных списков уровней У {Сматрицы старшего уровня и

вспомогательной информации Vecn (L):

УА (L) = zV(C(,)) + Vix^ ) + Vvcn (L). 1=0

Значение количества уровней, оптимальное с точки зрения эффективности компрессии, может быть получено разбиением на максимально возможное число уровней и выбором Lopt из условия минимума объема архива:

Lop, = arg min VA(L).

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

В первом алгоритме для кодирования однократно встречающихся блоков используется общий индекс. Вводится параметр (порог) Т^ — индекс первого элемента списка С^ с единичным числом встречаемости, т.е. W^ = 1, к > . При формировании матрицы блоки матрицы х(1), встречающиеся один раз,

будут кодироваться индексом Т^:

*(/+1)("1,«2Н ' ,П> к:х('Нм1п1+1,М2П2+Л=с11)(гМ1+Л, (3)

[Г, к 2. Г(/)

где j = 0,Af]-1, j = 0,M2-l, k = Q,Kw -1, К{1) -длинасписка С(,).

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

Г(,) <2\ / = 0,1-2. (4)

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

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

необходимости (если значение элемента х*-'"1"1' равно 7*^) с учетом количества уже обработанных однократно встречающихся блоков:

х(1\Мхпх +i,M2n2 + /) = Cf'O'M, + /), к =

m m ,;с('+1>(л„»2), л('+1)(«,,и2) < Г(0

где р - количество обработанных индексов матрицы (п^ , гъ), равных

пороговому значению Т^, р = 0,(К(1> — Г''' —1).

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

Далее предлагается алгоритм, позволяющий обеспечить работоспособность алгоритма компрессии для длинных списков (когда существует / такое, что уЧО > 2й, т.е. условие (4) не выполняется). Для таких списков применяется «размножение» векторов к = 2Ь — — 1, заключающееся в их

многократной записи в список. В матрице следующего уровня блоки, соответствующие этим векторам будут кодироваться индексом Т^ (согласно формуле (3)). В этом случае искусственно устанавливается значение порога Г(,) = 2Ь -1.

Следующий алгоритм выбора способа формирования иерархических уровней основан на адаптивном выборе значения Пусть Тх - индекс первого вектора списка СО с единичным числом встречаемости. Варьируя Т^ в диапазоне = [0;тт{24 —1,7!}] и используя «размножение» векторов , оптимальное

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

Ф(Г(0) = -

2¿V«(oin

v/=o

г (О Лс

/=0

JJ

—> min, (5)

rC)

где W^P и - вектора, являющиеся «ненормированными гистограммами»

данных в списке

и матрице соответственно (содержат числа

встречаемости соответствующих значений векторов), К ¿P =Ki')MlM2, К(Ш) = NjN2

(M,M2)W '

Вычислительная сложность прямой реализации данного способа выбора порога высока. Действительно, для каждого Т^ необходимо формирование С^ с использованием «размножения» векторов, формирование матрицы составление W^ и

и вычисление значения критерия по формуле (5).

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

формуле (5) для максимального значения Г^. Для остальных Т^ пересчитываются некоторые значения вектора W^ (количество таких значений не превышает M¡M2) и значения Ф(Г^) вычисляются рекуррентно. Формирование и не производится.

Алгоритм с адаптивным выбором Т ^ не накладывает ограничение на длину списков. Эксперименты показали, что его эффективность выше эффективности других алгоритмов формирования иерархических уровней (см. таблицу 1).

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

Рис. 1. Изображение «Область»

Алгоритм К

Базовый алгоритм 6,50

Алгоритм с порогом Т^ 8,25

Приведение длинных списков к 2Ч')=2Й_1 10,23

Адаптивный выбор Т^ 10,30

Для всех алгоритмов формирования уровней приводятся их частные случаи при размерах блоков = М2 = 2 и восьмибитном формате записи элементов матриц и списков всех иерархических уровней (Ь = 8). Именно эти значения параметров имеют практическое значение при компрессии картографических изображений.

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

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

[0, иначе

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

д е ж з

Рис. 2. Изображения цветовых плоскостей для изображения «Область»: а-г — преимущественно площадные, д-з - преимущественно контурные цветовые плоскости (черным показаны единицы цветовой плоскости, белым — нули)

Такая схема декомпрессии дает возможность на этапе компрессии на каждой рассматриваемой цветовой плоскости заменять нули единицами при условии, что эти нули «покроются» единицами следующих цветовых плоскостей. Нулевой элемент цветовой плоскости В* (п\,п2~) можно сделать единичным, если найдется такой, что и В5 (^[,«2) = 1. Разработано два алгоритма такой

предварительной обработки цветовой плоскости.

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

С(0)

и вектор чисел

встречаемости этих блоков (упорядоченные по убыванию чисел

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

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

1) состоит из нулей;

2) состоит из единиц;

3) состоит из нулей и единиц, но путем замены нулей на единицы может быть приведен ко второму типу (при условии, что все нули «покрываются» единицами на следующих цветовых плоскостях);

4) состоит из нулей и единиц и не может быть приведен ко второму типу.

В случае принадлежности квадранта к типам 1, 2, 3, переходим к рассмотрению следующего квадранта (заменив нули на единицы в случае третьего

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

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

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

Цветовая плоскость относится к преимущественно площадной, если

=Попе-Пт!х>0,

где попе — количество блоков на цветовой плоскости, полностью состоящих из

а б в

Рис. 3. Примеры работы алгоритмов предварительной обработки цветовой плоскости: а — до предобработки, б — результат обработки первым алгоритмом, в — результат обработки вторым алгоритмом (с несколькими шагами разбиения на квадранты)

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

Плоскости, отнесенные к преимущественно площадным, обрабатываются алгоритмом на основе квадродерева, а к преимущественно контурным — алгоритмом уменьшения индекса.

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

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

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

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

должны быть следующими: с}рх= 0,6 (отклонение р1 от р), ф2 = 0,2 (отклонение р2 от р{). Очевидно, что Р1 должно выбираться таким образом, чтобы с1рх было минимальным, и для выбранного следует выбирать р2 также из условия минимальности (¡рг. Данный алгоритм устраняет разрывы в одну точку между цепочками, что продемонстрировано на рис. 4.

/

1 X Рг

р А

Рис. 4. Пример устранения разрыва цепочки (серым цветом показаны единицы на цветовой плоскости, штриховкой - нуль, заменяемый на единицу)

Таблица 2. Коэффициенты компрессии К

алгоритмов (изображение

для разработанных преобразования данных

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

С точки зрения повышения степени компрессии были выбраны следующие размеры блоков: М! = М2 = 2.

В таблице 2 приведены коэффициенты компрессии К при последовательном добавлении разработанных алгоритмов.

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

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

Алгоритм К

Без разделения на цветовые плоскости 10,30

С разделением на цветовые плоскости, без предварительной обработки плоскостей 3,32

С предварительной обработкой плоскостей 11,53

С цепным кодированием 13,00

С соединением цепочек 13,13

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

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

> Л ( \ ., /с г/Л" Ах ^ .

■— ; „ -Л

Рис. 5. Изображения «Карта области» (размер 2480x1754) и «Карта города» (размер 2953x2362)

40

К

♦ С разделением на цветовые плоскости — в — Без разделения на цветовые плоскости

128 256 512 1024 2048'

I, с

* С разделением на цветовые плоскости — в — Без разделения на

цветовые плоскости

64 128 256 512 1024 2048

Рис. 6. Зависимости коэффициента компрессии (а) и времени декомпрессии (б) от размера фрагментов (изображение «Карта области»)

Далее приводится сравнение эффективности разработанного метода с известными методами безошибочной компрессии (GIF, PNG, JPEG-LS, ИСИ, WinRAR, JBIG и др.). Эксперименты показывают (см. табл. 3) преимущество нового метода перед другими в степени компрессии (для режима высокой степени компрессии). Для режима быстрой декомпрессии скорость декомпрессии выше, чем у других методов, дающих сравнимый коэффициент компрессии.

Таблица 3. Средний коэффициент компрессии и суммарное время декомпрессии для изображений «Карта области» и «Карта

Метод (стандарт) компрессии 'ram > С

PNG 7,9 6

GIF 9,8 5

ИСИ 10,6 13

JPEG-LS 10,7 8

WinRAR 13,4 8

JBIG 15,2 18

Новый метод (режим высокой степени компрессии) 17,2 51

Новый метод (режим быстрой декомпрессии) 13,1 6

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие основные результаты:

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

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

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

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

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

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

Основные положения диссертации отражены в следующих публикациях:

1. БавринаА.Ю., Глумов Н.И., Сергеев В.В., Тимбай Е.И. Метод иерархической компрессии индексных изображений // Компьютерная оптика, 2005, вып. 26, с. 125-129.

2. A. Yu. Bavrina, N. I. Glumov, V. V. Sergeyev, E. I. Timbay Hierarchical compression method for palettized images // Proceedings of international conference ACIT-SIP, Novosibirsk, Russian Federation, 20-24 June 2005, pp. 83-87.

3. Баврина А.Ю., Глумов Н.И., Сергеев B.B., Тимбай Е.И. Метод иерархической компрессии индексных изображений с разбиением на цветовые плоскости // Сборник докладов 12-й Всероссийской конференции «Математические методы распознавания образов» (ММРО-12), 2005, с. 256-258.

4. Баврина А.Ю., Глумов Н.И. Метод иерархической компрессии индексных изображений с разбиением на цветовые плоскости // Сборник тезисов докладов третьей летней школы молодых ученых по дифракционной оптике и обработке изображений, Самара, 7 июля 2005, с. 21-23.

5. Баврина А.Ю. Использование взаимосвязей между цветовыми плоскостями для повышения эффективности компрессии картографических изображений // Труды научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» (ПИТ-2006), Самара, 2006, том 2, с. 72-76.

6. Баврина А.Ю., Глумов Н.И., Сергеев В.В., Тимбай Е.И. Метод иерархической компрессии картографических изображений // Автометрия, 2006, том 42, № 5, с. 35-44.

Подписано в печать 10.10.2006 Формат 60x84 1/16 Отпечатано с готовых оригинал-макетов Типография СГАУ 443086, Самара, Московское шоссе, 34 Бумага офсетная. Печать оперативная. Тираж 100 экз.

ВВЕДЕНИЕ.

1. ЗАДАЧА КОМПРЕССИИ ПАЛИТРОВЫХ ИЗОБРАЖЕНИЙ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. АЛГОРИТМЫ, РЕАЛИЗУЮЩИЕ МЕТОД КОМПРЕССИИ НА ОСНОВЕ ИЕРАРХИЧЕСКОЙ ПЕРЕИНДЕКСАЦИИ.

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

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

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

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

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

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

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

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

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

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

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

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

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

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДА НА ОСНОВЕ ИЕРАРХИЧЕСКОЙ ПЕРЕИНДЕКСАЦИИ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А. К. Jain), М. Кунта (М. Kunt). Однако известные методы не в полной мере учитывает специфику картографических изображений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- на 3-й летней школе по дифракционной оптике и обработке изображений, Самара, 2005;

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

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

Публикаций

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

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

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

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

Основные результаты диссертационной работы

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

2. Ахмед Н., Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов. Пер. с англ. М.: Связь, 1980, 248 с.

3. БавринаА. Ю., Глумов Н. И., Сергеев В. В., ТимбайЕ. И. Метод иерархической компрессии индексных изображений // Компьютерная оптика, Самара, 2005, вып. 26, с. 125-129.

4. БавринаА.Ю., Глумов Н.И., Сергеев В.В., ТимбайЕ.И. Метод иерархической компрессии . картографических изображений // Автометрия, 2006, том 42, № 5, с. 35-44.

5. Балашов К.Ю. Сжатие информации: анализ методов и подходов. Минск, 2000, 42 с.

6. Блох Э.Л. О передаче бинарной последовательности равномерным кодом //Проблемы передачи информации, № 5, 1960, с. 12-22.

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

8. Васин Ю.Г., Жерздев С.В. Эффективное кодирования усеченных двойчных деревьев в задаче сжатия изображений // 6-я Всероссийская конференция "Методы и средства обработки сложной графической информации ", г. Нижний Новгород, 25-27 сентября 2001, с.31-33.

9. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: Диалог-МИФИ, 2002, 384 с.

10. Введение в контурный анализ; приложения к обработке контурных изображений и сигналов. Под ред. Фурмана Я.А. 2-е изд., исп. - М.: ФИЗМАТЛИТ, 2003, 592 с.

11. ВиттихВ.А., Сергеев В.В., СойферВ.А. Обработка изображений в автоматизированных системах научных исследований. М.: Наука, 1982, 214с.

12. Воробьев В.И., ГрибунинВ.Г. Теория и практика вейвлет-преобразования. С.-Петербург: ВУС, 1999, 204 с.

13. ГонсалесР., Вудс Р. Цифровая Обработка Изображений. М.: Техносфера, 2005, 1072 с.

14. ЗейлерМ. Моделирование нашего мира. Пер. с англ. Redlands: ESRI, 1999, 254 с.

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

16. Методы передачи изображений. Сокращение избыточности ПрэттУ.К., Сакрисон Д.Д., Мусманн Х.Г.Д. и др. М.: Радио и связь, 1983, 264 с.

17. Основы геоинформатики: Кн. 1 :Учебное пособие для студ. вузов; под ред. Тикунова B.C. М.: Издательский центр «Академия», 2004, 352 с.

18. Павлидис Т. Алгоритмы машинной графики и обработки изображений. Пер. с англ. М.: Радио и Связь, 1986.

19. ПрэттУ.К. Цифровая обработка изображений. Пер. с англ. М.: Мир, 1982, кн. 2, 480 с.

20. Сергеев В.В., Сойфер В.А. Имитационная модель изображения и метод сжатия данных // Автоматика и вычислительная техника, №3, 1978, с.76-78.

21. Субботин Д., http://www.compression.ru/sh/aridemo6.rar.

22. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера 2004, 368 с.

23. Хаффмен Д.А. Метод построения кодов с минимальной избыточностью // Кибернетический сборник, Москва, 1961, вып. 3.

24. Шеннон К. Работы по теории информации и кибернетике. М.: Изд-во иностр. лит-ры, 1963.

25. Шкарин Д. BMF утилита беспотерьного сжатия изображений, http://compression.graphicon.ru/ds/bmfl10.rar.

26. Шкарин Д. PPMd, http://www.compression.ru/download/sources/cm/ ppmdil.rar.

27. Штарьков Ю.М., Бабкин В.Ф. Кодирование длин серии в условиях априорной неизвестности // Аппаратура для космических исследований. Кодирование, сжатие данных, М.: Наука, 1973, с.3-9.

28. Ageenko Е., Franti P. Lossless compression of large binary images in digital spatial libraries // Computers & Graphics, 24 (1), Elsevier Science, February 2000, pp.91-98.

29. Allen J.D. An approach to fast transform coding in software // Signal Processing: Image Communication, 1996, vol. 8, issue 1, pp. 10-15.

30. AusbeckP. Context models for palette images // Proceedings Data Compression Conference, March 1998, IEEE Press, Los Alamitos, California, pp. 309-318.

31. Ausbeck P. The Piecewise-Constant Image Model // Proceedings of the IEEE, vol. 88, no. 11, 2000, pp. 1779-1789

32. Battiato S., Gallo G., Impoco G., Stanco F. An Efficient Re-Indexing Algorithm for Color-Mapped Images // IEEE Transactions on Image Processing, vol. 13, no. 11, November 2004, pp. 1419-1423.

33. Bavrina A.Yu., GlumovN.L, Sergeyev V.V., TimbayE.I. Hierarchical compression method for palettized images // Proceedings of international conference ACIT-SIP, Novosibirsk, Russian Federation, 20-24 June 2005, pp. 83-87.

34. Bockstein I.M. A method of lossless image compression // Pattern Recognition and image analysis, vol. 3, №2, 1993, pp. 92-98.

35. Calderbank A.R., Daubechies Ingrid, Sweldens Wim, Boon-Lock Yeo Wavelet transforms that map integers to integers // Appl. Comput. Harmon. Anal., vol. 5, no. 3, 1998, pp. 332-369.

36. CCITT, Standardization Of Group 3 Facsimile Apparatus For Document Transmission, ITU Recommendation T. 4, 1980

37. ClearyJ.G., Wittenl.H. Data compression using adaptive coding and partial string matching // IEEE Transactions on 'Communications, vol. 32(4), April 1984, pp.396-402.

38. Digital compression and coding of continuous tone still images Requirements and guidelines //ISO/IEC 10918-1, ITU T.81, Sept. 1993.

39. Ersoy О. K. Transform image enhancement // Optical Engineering, vol. 31, no 3, 1992, pp. 614-626.

40. Gashnikov M.V., Glumov N.I., Sergeyev V.Y. Compression Method for RealTime Systems of Remote Sensing // Proceedings of 15th International Conference on Pattern Recognition, Barselona 2000, September 3-7, vol.3, pp. 232-235.

41. Glen G., LangdonJr. Lossless Image Compression General Overview // cmpe 263 Winter 2001.

42. Golomb S.W. Run-length encodings // IEEE Trans. Inform. Theory, vol. IT-12, July 1966, pp. 399-401.

43. Gormish M.J.Compression of palettized images by color // Proc. IEEE Int. Conf. Image Processing, 1995, Washington D.C., pp. 274-277.

44. Gray F. Pulse code communication, March 17, 1953, U.S. Patent 2,632,058.

45. Ichiro Matsuda, Hirofumi Mori, Susumu Itoh. Lossless coding of still images using minimum-rate predictors // Proceedings of 2000 IEEE International Conference on Image Processing (ICIP 2000), Vol.1, Sep. 2000, pp. 132-135.

46. Information technology JPEG 2000 image coding system // ISO/IEC FCD15444-1,2000.

47. Information technology Lossless and near-lossless compression of continuous-tone still images // ISO/IEC 14495-1, ITU T.87, 1999.

48. JBIG, Progressive Bi-level Image Compression, ISO/IEC International Standard 11544, ITU Recommendation T.82, 1993.

49. KocherM., KuntM. A contour-texture approach to image coding // ICASSP Proc, vol. 7, 1982, pp. 436-440.

50. Kopylov P, Franti P. Context tree compression of multi-component map images // Proceedings of the Data Compression Conference, Snowbird Utah, March 2003, pp. 212- 221.

51. Kortman C.M. Redundancy Reduction A Practical Method of Data Compression // IEEE, Vol. 55, No. 3, 1967, pp. 253-263.

52. Kuhn Marlcus JBIG-KIT library, http://www.cl.cam.ac.uk/~mgk25/jbigkit/.

53. Kuroki N, Nomura T, Tomita, Hirano K. Lossless Image Compression by Two-Dimensional Linear Prediction with Variable Coefficients // IEICE Trans. Fundamentals, vol. E75-A, no. 7, 1992, pp. 882-889.

54. LiX., Orchard M.T. Edge Directed Linear Prediction for Lossless Compression of Natural Images // Proc. IEEE ICIP'99, pp. 147-151.

55. Limb J.0. Picture Coding: The use of a Viewer Model in Source Encoding //The Bell System Technical Jornal, vol. 52, no. 6, 1973.

56. LOCO-I/JPEG-LS Home Page, HP Labs, http://www.hpl.hp.com/loco.

57. LuraTech, http://www.luratech.com.

58. Mallat S.G. A Theory for multiresolution signal decomposititon: the wavelet representation // IEEE Trans, on Pattern Anal, and Mach. Intell, vol. 11, no. 7, 1989, pp. 674-693.

59. Martin G.N. Range encoding: an algorithm for removing redundancy from a digitised message // Video & Data Recording Conference, Southampton, 1979, pp. 24-27.

60. Martins В., Forchhammer S. Tree coding of bilevel images // Image Processing, IEEE Transactions, vol. 7, issue 4, April 1998, pp. 517-528.

61. MemonN., Venlcateswaran A. On ordering color maps for lossless predictive coding // IEEE Tran. Image Proc., vol. 5, no. 11, Nov. 1996, pp. 1522-1527.

62. Moffat A., Bell Т., Witten I. Lossless Compression for Text and Images // International Journal of High Speed Electronics and Systems, 8(1), March 1997, pp. 179-231.

63. Moffat A., NealR., Witten I.H, Arithmetic coding revisited // ACM Transactions on Information Systems, July 1998, 16 (3), pp. 256-294.

64. Netravali A.N., Limb J.O. Picture Coding: A. Review // Proceedings of the IEEE, vol. 68, no. 3, pp. 366-406.

65. Penrtebaker W.B., Mitchell J.L., Langdon G.G., Arps R.B. An overview of the basic principles of the Q-coder adaptive binary arithmetic coder // IBM Journal of Research, Development, 32 (6), pp. 717-726.

66. Rissanen J. Fast universal coding with context models // IEEE Trans. Inform. Theory. 1999, 45,no.4, pp. 1065-1071.

67. Rissanen J.J., Langdon G.G. Arithmetic coding // IBM Journal of Research, Development 23: 146-162.

68. Sweldens W. The lifting scheme: A construction of second generation wavelets // Technical Report 1995:6, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1995.

69. Sweldens W. The lifting scheme: A custom-design construction of biorthogonal wavelets // Appl. Comput. Harmon. Anal., 3(2), 1996, pp. 186200.

70. Ueno I., Ono F. "Proposed modification of LOCO-I for its improvement of the performance" ISO/IEC JTC1/SC29/WG1 doc. N297, Feb. 1996.

71. Weinberger M.J, Seroussi G, Sapiro G., From LOCO-I to the JPEG-LS Standard // Proc. 1999 Int. Conf. Image Processing, Kobe, Japan, Oct. 1999, pp. 68-72.

72. Weinberger M.J, Seroussi G, Sapiro G. LOCO-I: A Low Complexity, Context-Based Lossless Image Compression Algorithm // Proc. IEEE Data Compression Conference, Snowbird, UT, 1996, pp. 140-149.

73. Witten I.H, Neal R.M, Cleary J.G. Arithmetic coding for data compression // Communications of the ACM, vol. 30, № 6, 1987, pp. 520-540.

74. Wu X, Barthel K.U. Piecewise 2D Autoregression for Predictive Image Coding // Proc. IEEE ICIP'98, pp. 901-904.

75. Ye H, Deng G, Devlin J.C. Adaptive linear prediction for lossless coding of greyscale images // Proc. IEEE International Conference on Image Processing, vol. 1, (Vancouver, Canada), Sept. 2000, pp. 128-131.

76. Zeng W, Li J, LeiS. An efficient color re-indexing scheme for palette-based compression // Proc. IEEEInter. Conf. Image Proc, Vancouver, Canada, 2000, vol III, pp. 476-479.

77. Ziv J, LempelA. A universal algorithm for sequential compression //IEEE Trans. Inf. Theory, vol. 23, no. 3, 1977, pp. 337-343.82. 7-zip file archiver, http://www.7-zip.org/.