Методы сжатия данных без потерь с помощью сортировки параллельных блоков тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Ратушняк, Олег Александрович

• Ратушняк, Олег Александрович
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Ратушняк, Олег Александрович

ВВЕДЕНИЕ.

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

2. Общие сведения: определения, аббревиатуры, классификации.

Базовые определения.

Названия и аббревиатуры методов.б

Карта групп методов сжатия.

Базовые стратегии сжатия.

3. Цель работы.

4. Задачи исследования.

5. Методы исследования.

6. Научная новизна результатов работы.

7. Практическая ценность результатов.

8. Реализация и внедрение результатов.И

9. Апробация работы и публикации.

10. Структура работы.

ГЛАВА 1. КОДИРОВАНИЕ ИСТОЧНИКОВ ДАННЫХ ТИПА «АНАЛОГОВЫЙ СИГНАЛ»

Линейно-предсказывающее кодирование.

Прямое преобразование.

Обратное преобразование.

Пути увеличения скорости сжатия.

Увеличение скорости разжатия.IV

Пути улучшения степени сжатия.

Субполосное кодирование.

Прямое преобразование.

Обратное преобразование.

Пути улучшения степени сжатия.

ГЛАВА 2. МЕТОДЫ ОБХОДА ПЛОСКОСТИ.

Змейка (зигзаг-сканирование).

Обход строками.

Строками с разворотами.

Обход полосами.

Полосами с разворотами.

Обход решетками.

С учетом значений элементов.

Контурный обход.

С неизвестными контурами.

Другие методы.

Квадратная змейка».

По спирали.

Общее для всех случаев.

Прямоугольных.

Сложной формы.

ГЛАВА 3. ОБОБЩЕННЫЕ МЕТОДЫ СОРТИРУЮЩИХ ПРЕОБРАЗОВАНИЙ

Сортировка параллельных блоков.

Основной алгоритм преобразования.

Обратное преобразование.

Пути увеличения скорости сжатия.

Увеличение скорости разжатия.

Пути улучшения сжатия.

Фрагментирование.

Основной алгоритм преобразования.

Пути улучшения скорости.

Пути улучшения сжатия.

ГЛАВА 4. КОДИРОВАНИЕ ИСТОЧНИКОВ ДАННЫХ БЕЗ ПАМЯТИ.

Разделение мантисс и экспонент.

Прямое преобразование.

Обратное преобразование.

Пути увеличения степени сжатия.

Пути увеличения скорости сжатия и разжатия.

Нумерующее кодирование.

Векторное квантование.

Прямое преобразование.

Увеличение скорости сжатия.

ГЛАВА 5. МЕТОДЫ СЖАТИЯ ИЗОБРАЖЕНИЙ БЕЗ ПОТЕРЬ С ПОМОЩЬЮ СОРТИРОВКИ

ПАРАЛЛЕЛЬНЫХ БЛОКОВ.

Первичная обработка.

Поворот.

Перестановка компонент.

Сдвиг нуля.

Преобразование компонент.

Контекстная обработка.

Улучшенное преобразование компонент.

Субполосное Кодирование (СК).

Линейно-Предсказывающее Кодирование (ЛПК).

Перестановка битов.

Обход плоскости.

PBS, Сортировка параллельных блоков.

ВЫВОДЫ.

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

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

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

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

2. Общие сведения: определения, аббревиатуры, классификации

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

Базовые определения

Бит — это «атом» цифровой информации: переменная, которая может принимать ровно два различных значения:

• "1" (единица, да, истина, существует)

• "О" (ноль, нет, ложь, не существует)

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

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

Данные — информация в цифровом виде.

Объем данных измеряется в битах, но может быть и рациональным числом, а не только целым.

R-битный элемент — совокупность R битов — имеет 2R возможных значений-состояний. Большинство источников цифровой информации порождает элементы одного размера R. А в большинстве остальных случаев — элементы нескольких размеров: Rb R2, R3. (например, 8, 16 и 32).

Байт — это 8-битный элемент: совокупность восьми битов.

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

Блок — конечная последовательность цифровой информации.

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

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

Используют и такие пары терминов: компрессия/декомпрессия, кодирование/декодирование, упаковка/распаковка.

Под просто сжатием будем далее понимать сжатие без потерь (lossless compression).

Сжатие с потерями (lossy compression) — это два разных процесса:

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

2) собственно сжатие, без потерь.

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

Конечную последовательность битов назовем кодом, а количество битов в коде — длиной кода.

Конечную последовательность элементов назовем словом, а количество элементов в слове— длиной слова. Иногда используются синонимы: строка и фраза. В общем случае слово построено из R-битных элементов, а не 8-битных. Таким образом, код — это слово из 1 -битных элементов.

Например, в блоке из 14-и элементов «кинчотсихыннад» одно слово длиной 14 элементов, два слова длиной 13, и так далее, 13 слов длиной 2 и 14 слов длиной 1. Аналогично в блоке из семи битов «0100110» один код длиной 7 битов, два кода длиной 6, и так далее, семь кодов длиной 1.

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

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

ASCII (American Standard Code for Information Interchange— Американский Стандартный Код для Обмена Информацией) каждому значению байта ставит в соответствие символ. Но чтобы построить однозначное соответствие для всех необходимых символов из множества национальных алфавитов народов мира, требуется больше: по крайней мере 16 битов на символ (что и обеспечивает стандарт Unicode).

Множество всех различных символов, порождаемых некоторым источником, называется алфавитом, а количество символов в этом множестве— размером алфавита. Источники данных порождают только элементы, но физические источники информации — символы или элементы.

Размер алфавита таблицы ASCII равен 28=256, a Unicode— 21б=65536. Это две самые распространенные таблицы символов.

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

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

• учет значений соседних элементов (контекста) улучшает сжатие, то есть имеет смысл трактовать данные как слова;

• поток данных выглядит как поток слов.

В первом же случае имеем дело с перестановкой элементов, и рассматривать данные как слова нет смысла.

Кавычки показывают, что это условные названия способов интерпретации входных данных: "слова", "элементы", "биты ".

По традиции бинарный источник без памяти называют обычно «источник Бернулли», а важнейшим частным случаем источника данных с памятью является «источник Маркова» (N-ro порядка): состояние на i-ом шаге зависит от состояний HaN предыдущих шагах: i-1, i-2,., i-N.

Третья важнейшая применяемая при сжатии данных математическая модель — «аналоговый сигнал»:

• данные считаются количественными;

• источник данных считается источником Маркова 1-го порядка.

Если использовать модель «аналоговый сигнал» с N > 1, то при малых N эффективность сжатия неизменна или незначительно лучше, но метод существенно сложнее, а при дальнейшем увеличении ^эффективность резко уменьшается.

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

Еще две важных характеристики алгоритма сжатия — объемы памяти, необходимые для сжатия и для разжатия (для хранения данных, создаваемых и/или используемых алгоритмом).

Названия и аббревиатуры методов

CM (Context Modeling) — Контекстное моделирование

DMC (Dynamic Markov Compression) — Динамическое марковское сжатие (является частным случаем СМ)

PPM (Prediction by Partial Match) — Предсказание по частичному совпадению (является частным случаем СМ)

LZ-методы — методы Зива-Лемпела, в том числе LZ77, LZ78, LZH и LZW

PBS (Parallel Blocks Sorting) — Сортировка параллельных блоков

ST (Sort Transformation) — Частичное сортирующее преобразование (является частным случаем PBS)

BWT (Burrows-Wheeler Transform) — Преобразование Барроуза-Уилера (является частным случаем ST)

RLE (Run Length Encoding) — Кодирование длин повторов HUFF (Huffman Coding) — кодирование по методу Хаффмана SEM (Separate Exponents and Mantissas) — Разделение экспонент и мантисс (Представление целых чисел)

UNIC (Universal Coding) — Универсальное кодирование (является частным случаем SEM)

ARIC (Arithmetic Coding) — Арифметическое кодирование

RC (Range Coding) — Интервальное кодирование (вариант арифметического)

DC (Distance Coding) — Кодирование расстояний

IF (Inverted Frequences) — «Обратные частоты» (вариант DC)

MTF (Move To Front) — «Сдвиг к вершине», «Перемещение стопки книг»

ENUC (Enumerative Coding) — Нумерующее кодирование

FT (Fourier Transform) — Преобразование Фурье

DCT (Discrete Cosine Transform) — Дискретное Косинусное Преобразование, ДКП (является частным случаем FT)

DWT (Discrete Wavelet Transform) — Дискретное Вэйвлетное Преобразование,

Двп

LPC (Linear Prediction Coding) — Линейно-Предсказывающее Кодирование, ЛПК (к нему относятся Дельта-кодирование, ADPCM, CELP и MELP) SC (Subband Coding) — Субполосное кодирование YQ (Vector Quantization) — Векторное квантование

Карта групп методов сжатия

Статистические Трансформирующие

Поточные Блочные Поточные Блочные для "слов ", модель «Источник с памятью» CM, DMC, все РРМ CMBZ, preconditioned PPMZ Все LZ, в т.ч. LZH и LZW ST, в т.ч. BWT для "элементов", модели «Источник без памяти» или «Аналоговый сигнал» адаптивны й HUFF статически й HUFF SEM, VQ, MTF, DC, SC, DWT DCT, FT, Фрактальн ые методы для "элементов" или "битов" адаптивны й ARIC статически й ARIC RLE, LPC, в т.ч. Дельта PBS, ENUC

Каждая группа (ветвь, семейство) содержит множество методов. Исключением является блочно-ориентированный СМ— это относительно мало исследованная область. Автору не известны другие практические реализации, кроме компрессоров СМ Булата Зиганшина и "pre-conditioned PPMZ" Чарльза Блума.

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

1 Относительная частота элемента X в блоке Z — это количество элементов со значением X, деленное на количество всех элементов в блоке Z: relfreq(X)=count(X) / length(Z).

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

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

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

Не все методы для потоков R-битных "элементов" применимы к "битам" (только те, которые в третьей строке «карты»).

Очевидно, что невыгодно применять методы для "элементов"— к "словам" или "битам". Менее очевидно, что невыгодно и обратное: применять методы для потоков "слов" к данным без значимых вероятностных взаимосвязей, к "элементам " или "битам ".

Базовые стратегии сжатия

Базовых стратегий сжатия три:

1) Трансформация потока («Скользящее окно-словарь»).

Описание поступающих данных через уже обработанные. Сюда входят LZ-методы [51,52,46,44,16,20,24,26,28,34,35,37,39] для потоков "слов", т.е. когда комбинации поступающих элементов предсказуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF [10], VQ, SEM [25,27,32] , Subband Coding, Discrete Wavelet Transform, — для потоков "элементов", т.е. когда не имеет смысла рассматривать комбинации длиной два и более элемента, или запоминать эти комбинации, как в случае Linear Prediction Coding.

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

2) Статистическая стратегия. а) Адаптивная (поточная).

Вычисление вероятностей для поступающих данных на основании статистики по уже обработанным данным. Кодирование с использованием этих вычисленных вероятностей. Семейство РРМ-методов [11,14,15,17, 18,21,22,29,36,38,45,47-49] — для потоков "слов", адаптивные варианты методов Хаффмана [30,31] и Шеннона-Фано, арифметического кодирования [50]— для потоков "элементов". В отличие от первого случая, давно собранная статистика имеет тот же вес, что и недавняя, если метод не борется с этим специально, что гораздо сложнее, чем в случае LZ. Кроме того, считаются вероятными все комбинации, даже те, которые еще не встречались в потоке, и, скорее всего, никогда не встретятся. б) Блочная.

Отдельно кодируется и добавляется к сжатому блоку его статистика. Статические варианты методов Хаффмана, Шеннона-Фано и

Арифметического Кодирования — для потоков "элементов ". Статическое

СМ для "слов".

3) Трансформация блока.

Входящие данные разбиваются на блоки, которые затем трансформируются целиком, а в случае блока однородных данных лучше брать весь блок, который требуется сжать. Это методы сортировки блоков ("BlockSorting''-методы: ST, BWT [19,2,12,13,33], PBS), а также Fourier Transform, Discrete Cosine Transform, фрактальные преобразования, Enumerative Coding [23].

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

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

• чем больше и однороднее данные и память1, тем эффективнее блочные методы;

• чем меньше и неоднороднее данные и память, тем эффективней поточные методы;

• чем сложнее источник, тем сильнее улучшит сжатие оптимальная трансформация;

• чем проще источник, тем эффективней прямолинейное статистическое решение (математические модели «источник Бернулли» и «источник Маркова»).

3. Цель работы

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

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

Качеству сжатия также уделялось пристальное внимание. В некоторых случаях допускалось ухудшение качества на 0.5-1.5%, если это ускоряло алгоритм в 1.5-2 раза.

4. Задачи исследования

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

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

Особое внимание уделено методам сортировки, разработанным автором и описываемым впервые:

• сортировка параллельных блоков;

• фрагментирование.

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

5. Методы исследования

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

6. Научная новизна результатов работы

Автором разработаны и исследованы методы решения описанных задач и алгоритмы их реализации.

Как правило, при разработке алгоритмов использовался тот факт, что длина сжимаемых данных естественным образом ограничена сверху: например, ввиду ограниченных объемов носителей информации длина кодируемой последовательности заведомо меньше 264 «1.6*1019.

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

На защиту выносятся следующие результаты.

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

2. Разработан и исследован новый метод (обратимой) сортировки данных с целью уменьшения контекстной избыточности: сортировка параллельных блоков. Показано, что все известные методы сортировки, в том числе полная (BWT) и частичная (ST) являются частными случаями сортировки параллельных блоков (PBS).

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

4. Разработаны и исследованы новые варианты улучшения сжатия хорошо известных методов: разделения экспонент и мантисс (SEM), линейно-предсказывающего кодирования (LPC), субполосного кодирования (SC), методов обхода плоскости. Показано, как эти методы (а в перспективе и некоторые другие, в частности векторное квантование (VQ) и нумерующее кодирование (ENUC)) могут быть применены для сжатия изображений без потерь.

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

7. Практическая ценность результатов

Все разработанные новые методы и новые варианты существующих методов позволяют существенно улучшить как степень сжатия данных, на которые они ориентированы, так и общую эффективность сжатия таких данных современными вычислительными машинами, в среднем на 5.20% по сравнению с лучшими из существующих в настоящее время аналогов, и на 10.90% по сравнению с современными промышленными стандартами (в первую очередь ZIP и PNG).

8. Реализация и внедрение результатов

Большинство алгоритмов и методов сжатия, описанных в данной работе, реализованы автором в компьютерной программе сжатия данных ERI (около 10 ООО строк на языке Си).

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

Совершенствование методов, алгоритмов и программы продолжается.

9. Апробация работы и публикации

Результаты работы были опубликованы автором в местной и центральной печати [1, 5-9] (все публикации кроме первой — без соавторов).

Работа была апробирована на семинарах Института систем информатики им. А. П. Ершова СО РАН.

Некоторые результаты, в частности самые важные, были опубликованы (на английском языке) в Интернете, в группе новостей comp.compression, регулярно читаемой практически всеми авторитетами в области сжатия данных. Выпуски сравнительных тестов автора «Art Of Lossless Data Compression» публикуются в Интернете более четырех лет, с конца 1997-го года ( http.7/go.to/artest , http://artst.narod.ru/ ) и являются лучшими по многим параметрам, в частности по числу и общему объему файлов, на которых производится тестирование программ сжатия, доступности и читабельности наборов команд, тестирующих компрессоры (файлы скриптов: *.ВАТ), и многим другим параметрам.

Результаты работы используются в книге «Методы сжатия данных» (авторы -Ратушняк, Ватолин, Юкин, Смирнов), публикуемой издательством «Диалог-МИФИ» в мае 2002-го года, электронный вариант книги можно увидеть в Интернете по адресу http://compression.graphicoix.ru/ и http://compression.graphicon.ru/tmp/.

10. Структура работы

Диссертационная работа состоит из вводной части, пяти глав и четырёх приложений.

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

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

Главы 1 -4 работы посвящены описанию новых разработанных автором методов, а также новых вариантов существующих методов. В частности, впервые показано, что

• разработанный автором класс ЛПК-фильтров оказывается на практке выгоднее, чем несколько фильтров, используемых в алгоритмах PNG и LOCO-I и являющихся лишь частными случаями из множества ЛПК-фильтров описываемого класса;

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

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

• многие методы, не считавшиеся принадлежащими к группе методов «Представление целых чисел» (в частности DAKX исследователя Д.А.Копфа и «структурная модель» Фенвика) реально используют ту же идею (разделение мантисс и экспонент) и принадлежат одному из четырех основных вариантов;

• использование векторного квантования и нумерующего кодирования являются очень перспективными направлениями исследований, в частности в задаче сжатия изображений без потерь;

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

• оптимизированные варианты методов PBS и фрагментирования существенно лучше «демонстрационных» по скорости и требованиям к объему рабочей памяти.

В каждом случае изложение метода делается поступательно: от самого простого варианта к достаточно сложному.

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

В приложениях даны результаты сравнения работы программы ERI с другими программами, сжимающими полноцветные изображения: лучшие из изветных программ, а также программы, реализующие промышленные стандарты (PNG, LOCO-I/JPEG-LS, baseline JPEG). Сравнение с алгоритмом JPEG, сжимающим изображения с потерями, приведено только для общего сведения.

Работа заканчивается списком использованной литературы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Ратушняк, Олег Александрович

Выводы

В работе показано, что

• разработанный автором класс ЛПК-фильтров оказывается на практке выгоднее, чем несколько фильтров, используемых в алгоритмах PNG и LOCO-I и являющихся лишь частными случаями из множества ЛПК-фильтров описываемого класса;

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

• разработаны и впервые описаны обощенные методы сортировки; оптимизированные варианты методов PBS и фрагментирования существенно лучше «демонстрационных» по скорости и требованиям к объему рабочей памяти.

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

• многие методы, не считавшиеся принадлежащими к группе методов «Представление целых чисел» (в частности DAKX исследователя Д.А.Копфа и «структурная модель» Фенвика) реально используют ту же идею (разделение мантисс и экспонент) и принадлежат одному из четырех основных вариантов;

• использование векторного квантования и нумерующего кодирования являются очень перспективными направлениями исследований, в частности в задаче сжатия изображений без потерь;

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

Список литературы диссертационного исследования кандидат физико-математических наук Ратушняк, Олег Александрович, 2002 год

1. Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин. Методы сжатия данных. Учебное пособие. // Москва, «Диалог-Мифи» - 2002. 384 стр.

2. Кадач А.В. Эффективные алгоритмы неискажающего сжатия текстовой информации. — Диссертация на соискание ученой степени к.ф-м.н. — Институт систем информатики им. А.П.Ершова, 1997.

3. Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь. 1989.

4. Марков А. А. Введение в теорию кодирования. М.: Наука. 1982.

5. Ратушняк О.А. Методы фрагментирования, анализа структуры и сжатия импульсно-сигнальной информации, а также устройство для их реализации. Патент РФ No. 96103325

6. Ратушняк О.А. О сжатии информации. // КомпьютерПресс. 2000. - №.5 -стр. 160-163.

7. Ратушняк О.А. Сжатие мультимедийной информации. // Hard'n'Soft. 2001. - №.4 - стр. 78-79.

8. Ратушняк О.А. Высокоэффективные алгоритмы сжатия изображений без потерь. // Сборник материалов 5-й Международной Конференции "Распознавание-2001", Курск 2001-стр. 155-158.

9. Ратушняк О.А. Алгоритмы сжатия изображений без потерь с помощью сортировки параллельных блоков. // Тезисы докладов конференции молодых учёных по математике, мат. моделированию и информатике, Новосибирск, 46 декабря 2001 г. стр. 48-49.

10. Рябко Б. Я. Сжатие данных с помощью стопки книг //Проблемы передачи информации. 1980. Т. 16, Вып. 2, с. 16-21.

11. Шкарин Д. Повышение эффективности алгоритма РРМ // Проблемы передачи информации, Т. 34, Вып. 3, с.44-54,2001.

12. Arnavut Z., Magliveras S. S. Block sorting and data compression// Proc. IEEE Data Compression Conference. Snowbird, Utah. 1997. P. 181-190.

13. Balkenhol В., Kurtz S., Shtarkov Y.M. Modifications of the Burrows and Wheeler Data Compression Algorithm // Proceedings of Data Compression Conference, Snowbird, Utah, IEEE Computer Society Press, 1999, pp. 188-197.

14. Bell Т. C., Cleary J. G., Witten I. H. Text compression. Prentice Hall. N.Y.rEnglewood Cliffs. 1990

15. Bell T.C., Witten I.H., Cleary, J.G. Modeling for text compression // ACM Computer Surveys, 24(4), pp.555-591, 1989.

16. Bender P.E., Wolf J.K. New asymptotic bounds and improvements on the Lempel-Ziv data compression algorithm // IEEE Transactions on Information Theory. Vol. 37(3), pp. 721-727. May 1991.

17. Bloom C. Solving the problems of context modeling // California Institute of Technology, 1996.

18. Bunton S. On-Line Stochastic Processes in Data Compression // PhD thesis, University of Washington, 1996.

19. Burrows M., Wheeler D. J. A block-sorting lossless data compression algorithm//Tech. Rep. Digital System Research Center. Palo Alto, CA, USA. 1994. N124.

20. Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching // IEEE Transactions on Communications, Vol. 32(4), pp.396-402, April 1984.

21. Cleary J.G., Teahan W.J. Unbounded length contexts for PPM // The Computer Journal, 40 (2/3), pp. 67-75. 1997.

22. Cormack G.V., Horspool R.N. Data compression using dynamic Markov modelling // The Computer Journal 30(6), pp.541-550. Dec. 1987.

23. Cover Т. M. Enumerative source encoding// IEEE Trans. Inform. Theory. 1973.V. IT-19, N1. P. 73-77.

24. Deutsch L.P. (1996) DEFLATE Compressed Data Format Specification v. 1.3 (RFC1951)

25. Elias P. Universal codeword sets and representations of integers// IEEE Trans. Inform. Theory. 1975. V. IT-21, N2. P. 194-203.

26. Fiala E.R., Greene D.H. Data compression with finite windows. Commun // ACM Vol. 32(4), pp.490-505. Apr. 1989.

27. Golomb S. W. Run length encoding// IEEE Trans. Inform. Theory. 1966. V.IT-12, N4. P. 399-401.

28. Hoang D.T., Long P.M., Vitter J.S. Multiple-dictionary compression using partial matching // Proceedings of Data Compression Conference, pp.272-281, Snowbird, Utah, March 1995.

29. Howard P.G. The design and analysis of efficient lossless data compression systems //PhD thesis, Brown University, Providence, Rhode Island. 1993.

30. Huffman D. A. A method for the construction of minimum-redundancy codes//Proc. IRE 1952. V. 40, N10, P. 1098-1101.

31. KnuthD. E. Dumamic Huffman coding//J. Algorithms, 1985. V. 6. P. 163-180.

32. Krichevsky R. E., Trofimov У. K. The performance of universal encoding//IEEE Trans. Inform. Theory. 1981. V. IT-27, N2. P. 199-207.

33. Kurtz S. Space efficient linear time computation of the Burrows and Wheeler Transformation // Proceedings of Data Compression Conference. 2000.

34. Langdon G.G. A note on the Ziv-Lempel model dor compressing individual sequences // IEEE Transactions on Information Theory, Vol. 29(2), pp.284-287. March 1983.

35. Larsson J., Moffat A. Offline dictionary-based compression // Proceedings IEEE, Vol. 88(11), pp.1722-1732, Nov. 2000.

36. Lelewer D.A., Hirschberg D.S. Streamlining Context Models for Data Compression. // Proceedings of Data Compression Conference, Snowbird, Utah, pp.313-322, 1991.

37. Matias Y., Rajpoot N., Sahinalp S.C. Implementation and experimental evaluation of flexible parsing for dynamic dictionary based data compression // Proceedings WAE'98, 1998.

38. Moffat A. Implementing the PPM data compression scheme // IEEE Transactions on Communications, Vol. 38(11), pp.1917-1921, Nov. 1990.

39. Moffat A. M. Word based text compression// Software | Practice and Experience. 1989. V. 19, N2, P. 185-198.

40. Nevill-Manning C.G., Witten I.H. Linear-time, incremental hierarchy inference for compression // Proceedings of Data Compression Conference, J.A. Storer and M. Cohn (Eds.), Los Alamitos, CA: IEEE Press, pp.3-11.1997.

41. Rissanen J.J., Langdon G.G. Universal modeling and coding // IEEE Transactions on Information Theory, Vol. 27(1), pp.12-23, Jan. 1981.

42. Shannon C.E. A mathematical theory of communication // The Bell System Technical Journal, Vol. 27, pp. 379-423, 623-656, July, October, 1948.

43. Schmidhuber J. Sequential neural text compression // IEEE Transactions on Neural Networks, Vol. 7(1), pp. 142-146. 1996.

44. Storer J.A., Szymanski T.G. Data compression via textual substitution // Journal of ACM, Vol. 29(4), pp.928-951, Oct. 1982.

45. Teahan W.J. Probability estimation for PPM // Proceedings of the New Zealand Computer Science Research Students Conference, 1995. University of Waikato, Hamilton, New Zealand.

46. Welch T.A. A technique for high-performance data compression // IEEE Computer, Vol. 17(6), pp.8-19, June 1984.

47. Willems F.M.J., Shtarkov Y.M., Tjalkens T.J. The context-tree weighting method: Basic properties // IEEE Transactions on Information Theory, Vol. 41(3): pp. 653664, May 1995.

48. Witten I.H., Bell T.C. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression // IEEE Transactions on Information Theory, Vol. 37(4), pp. 1085-1094. July 1991.

49. Witten I.H., Bray Z., Mahoui M., Teahan B. Text mining: a new frontier for lossless compression// University of Waikato, NZ, 1999.

50. Witten I. H., Neal R. M., Cleary J. G. Arithmetic coding for data compression//Commun. ACM. 1987. V. 30, N6. P. 520-540.

51. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory, Vol. 23(3), pp.337-343, May 1977.

52. Ziv J. and Lempel A. Compression of individual sequences via variable-rate coding // IEEE Transactions on Information Theory, Vol. 24(5), pp.530-536, Sept. 1978.