Главная
страница 1страница 2 ... страница 14страница 15


Ватолин Дмитрий Сергеевич


Методы
сжатия изображений



Определения. Аббревиатуры и классификации методов сжатия 2

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

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

Методы сжатия без потерь 5

Канонический алгоритм Хаффмана 6

Арифметическое сжатие 8

Классический вариант алгоритма 8

Интервальное кодирование 14

Литература 19

Словарные методы сжатия данных 19

Идея словарных методов 19

Классические алгоритмы Зива-Лемпела 20

Алгоритм LZ77 21

Алгоритм LZSS 24

Алгоритм LZ78 26



Литература 28

Список архиваторов и компрессоров 29

Методы контекстного моделирования 29



Классификация стратегий моделирования 31

Контекстное моделирование 32

Терминология 33

Виды контекстного моделирования 34

Алгоритмы PPM 36

Пример работы алгоритма PPM 38

Пример реализации PPM-компрессора 40

Оценка вероятности ухода 43

Априорные методы 44

Адаптивные методы 45

Метод Z 45



Алгоритмы сжатия изображений 46

Введение 46



Классы изображений 47

Классы приложений 48

Примеры приложений, использующих алгоритмы компрессии графики 48

Требования приложений к алгоритмам компрессии 49

Критерии сравнения алгоритмов 50

Вопросы для самоконтроля 51

Алгоритмы архивации без потерь 52



Алгоритм RLE 52

Первый вариант алгоритма 52

Второй вариант алгоритма 52

Алгоритм LZW 53

Алгоритм LZ 53

Алгоритм LZW 54

Алгоритм Хаффмана 57

Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3 57



JBIG 60

Lossless JPEG 60

Заключение 60

Вопросы для самоконтроля 61

Проблемы алгоритмов архивации с потерями 62

Алгоритм JPEG 63

Как работает алгоритм 63



Фрактальный алгоритм 66

Идея метода 66

Построение алгоритма 69

Схема алгоритма декомпрессии изображений 71

Оценка потерь и способы их регулирования 71

Рекурсивный (волновой) алгоритм 72

Алгоритм JPEG 2000 74

Идея алгоритма 74

Области повышенного качества 78

Заключение 80

Вопросы для самоконтроля 80

Различия между форматом и алгоритмом 82

Литература 84



Литература по алгоритмам сжатия 84

Литература по форматам изображений 84

Алгоритмы сжатия видео 85

Введение 85

Основные понятия 85

Требования приложений к алгоритму 85

Определение требований 86

Обзор стандартов 87

Базовые технологии сжатия видео 88



Описание алгоритма компрессии 88

Общая схема алгоритма 89

Использование векторов смещений блоков 90

Возможности по распараллеливанию 90

Другие пути повышения степени сжатия 91

Motion-JPEG 92

MPEG-1 92

H.261 93


H.263 93

MPEG-2 94

MPEG-4 95

Сравнение стандартов 97

Вопросы для самоконтроля 97

Литература 98



Ссылки на программы и реализации алгоритмов 98


Благодарности

Автор выражает искреннюю и огромную признательность Максиму Смирнову, без которого этот материал не мог бы появиться на свет, а если бы появился, то содержал бы большее количество ошибок и неточностей. Также автор весьма признателен Вадиму Юкину, Александру Ратушняку за серьезную помощь в подготовке этих материалов. Также автор весьма признателен Максиму Смирнову, Вадиму Юкину и других коллег за помощь в ведении сервера http://www.compression.ru/, ставшего благодаря вкладу всех его участников самым крупным ресурсом по сжатию на русском языке, и, наконец, автор выражает большую признательность лаборатории компьютерной графики ВМиК МГУ и ее основателю Юрию Матвеевичу Баяковскому за всяческую поддержку работ по сжатию в течении последних 10 лет.

Определения. Аббревиатуры и классификации методов сжатия

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


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

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

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

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

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



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

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

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

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

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



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

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

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

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

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

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


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

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

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

Конечную последовательность элементов назовем словом, а количество элементов в слове — длиной слова. Иногда используются синонимы: строка и фраза. В общем случае слово построено из 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, а Unicode — 216=65536. Это две самые распространенные таблицы символов.
Источник данных порождает поток либо содержит блок данных. Вероятности порождения элементов определяются состоянием источника. У источника данных без памяти состояние одно, у источника с памятью — множество состояний, и вероятности перехода из одного состояния в другое зависят от совокупности предыдущих и последующих (еще не реализованных, в случае потока) состояний.

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



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

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

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

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

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

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



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

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

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

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

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


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


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

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

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

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) — Субполосное кодирование

VQ (Vector Quantization) — Векторное квантование



следующая страница >>
Смотрите также:
Литература 19 Словарные методы сжатия данных 19 Идея словарных методов 19 Классические алгоритмы Зива-Лемпела 20
2114.32kb.
15 стр.
Л. Н. Никитин Алгоритмы сжатия изображений и стандарты цифрового кодирования
1086.9kb.
5 стр.
Асни методов сжатия полутоновых изображений без потерь
80.48kb.
1 стр.
Учебное пособие по дисциплине «Структуры и алгоритмы обработки данных» для специальностей «Программное обеспечение информационных технологий»
1959.7kb.
12 стр.
Алексей Жоров гр. 14-502 Обязательное задание к практической работе №1 «Алгоритмы сжатия двоичной информации»
206.71kb.
1 стр.
Место теории измерений в методах анализа данных
266.06kb.
1 стр.
Отчет о лаботарорной работе методы и средства анализа данных по теме: «Система анализа данных weka»
383.87kb.
2 стр.
Магистерские программы
18.28kb.
1 стр.
Новый способ архивирования данных
197.13kb.
1 стр.
Программ а экзамена по дисциплине «Структуры и алгоритмы обработки данных» осенний семестр для студентов 2 курса специальности 1-400101 «Программное обеспечение информационных технологий» № п/п
106.9kb.
1 стр.
Словарные слова с непроверяемыми гласными 1 Формат 68х98 см
21.63kb.
1 стр.
Методы и алгоритмы выделения контуров изображений в радиотехнических системах с использованием дискретной вейвлет-фильтрации 05. 12. 04 Радиотехника, в том числе системы и устройства телевидения
326.58kb.
1 стр.