Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Компрессия данных.DOC
Скачиваний:
23
Добавлен:
01.05.2014
Размер:
1.09 Mб
Скачать

МЕТОДЫ СЖАТИЯ ДАННЫХ

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

Алгоритм Хаффмана (кодирование символами переменной длины)

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

Пример: В английском тексте для E, T, A примем 3-битовые последовательности, для J, Z, Q - 8-битовые.

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

RLE-алгоритм

Основан на сжатии последовательностей одинаковых символов.

Принцип:

ААААИИИИСССВВВВ преобразуем в 4А4И3С4В

т.е. в пары <N,C> , где N - кол-во повторов

C - символ.

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

LZSS

Кодирует текст в упорядоченное дерево подстрок, что приводит к значительному сжатию.

Формат:

<0, Незакодированный байт>

<1, 12 битов - Смещение, 4 бита - Длина совпадения>

LZM

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

Форматы маркеров:

<00, 6 байт - Длина> < Несжатые данные >

Поле Длина содержит значение от 1 до 63.

<00, 6 байт - 000000> < 8 байт - Кол-во повторов, Символ> // см. RLE - алг.

<01, 2 байт - Длина несж., 3 байт - Длина совпад., 9 байт -Смещен.назад> // см. LZSS

Поле Длина несж. содержит кол.-во незакодированных символов, следующих сразу за маркером (то 0 до 3).

Длина совпад. - от 3 до 10 символов

Смещен.назад - смещение назад от текущей позиции - от 0 до 511.

<10, 2 байт - Длина совпад., 12 байт -Смещен.назад>

Длина совпад. - от 3 до 6 символов

Смещен.назад - смещение назад от текущей позиции.

<11, 4 байт - Длина несж., 2 байт - Длина совпад.1, 13 байт -Смещен.назад., 3 байт - Длина совпад.2>

Поле Длина несж. содержит кол.-во незакодированных символов, следующих сразу за маркером (то 0 до 15).

Длина совпад.1 -Длина совпад.2 - ???? - от 0 до 31.

Смещен.назад. - от 0 до 8191.

Модель данных LZM

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

Ф-ция хеширования:

ХЕШ-КОД = 0

ХЕШ-КОД = Первый_Символ

ХЕШ-КОД =ХЕШ-КОД << 2 (* Побитовый сдвиг *)

ХЕШ-КОД = ХЕШ-КОД xor Второй_Символ

ХЕШ-КОД = ХЕШ-КОД << 2

ХЕШ-КОД = ХЕШ-КОД xor Третий_Символ

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

Хеширование существенно ускоряет кодирование по сравнению с LZSS, но приводит к некоторой неполноте сжатия в среднем на 25%.

На файлах различных СУБД и .BMP сжатие 5:1

.TXT - 3-2:1

.EXE и .COM - 1,5:1

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

  • Алгоритмы сжатия без потерь на форматах GIF, PCX, BMP и др. уменьшают размер файла на 10 - 90 %.

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

  • При кодировании по строкам (LZSS, LZW) не учитывается подобие в столбцах.

  • Из-за погрешности дискретизации одинаковые фрагменты становятся различными.

Сжатие с потерями - алгоритм JPEG

Основные этапы:

  1. Перевод изображения из пространства RedGreenBlue в пространство XYZ, где по оси Z откладывается значение цветности пиксела, 75% которых отбрасывается в ходе прореживания.

  2. Переход от пространственного представления к спектральному - ДКП.

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

    Для увеличения производительности изображение разбивается на несколько матриц размером 8*8 (кр.того в разнесенныхчастях изображения часто мало подобия), после чего выполняется ДКП по формуле:

    [ДКП]nn = [КП]nn * [Точки]nn * [КПт]nn

    где КП - м-ца косинусного преобразования размером n*n

    Точки - м-ца точек картинки

    КПт - транспонированная м-ца КП

    В результате сложность ДКП 2*n, где n - размер м-цы

  3. Квантование - деление на м-цу квантования с округлением коэффициентов.

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

  4. Кодирование.

· Замена абсолютных значений к-тов относительными.

· Обход м-цы зигзагом (0.0 > 0.1 > 1.0 > 2.0 > 1.1 > 0.2 > 0.3 > 1.2 >...)

· Кодирование повторов (RLE).

· Кодирование энтропии (Арифметическое кодирование или Хаффмана).

СЖАТИЕ ЗВУКОВОЙ ИНФОРМАЦИИ

  1. Психоакустика.

    · Слышимый человеком звук лежит в диапазоне 20Гц - 20 кГц, наиболее чуткий - 2 - 4 кГц.

    · Динамаческий диапазон (тихо-громко) - ок. 96 дБ.

    · Нормальный голос лежит в диапазоне от 500 Гц до 2кГц.

  • низкие частоты - гласные и звонкие согласные

  • высокие частоты - глухие согласные и шипящие

    · Эффект временного маскирования :

  • после громкого звука тихий воспринимается (слышен) после некоторой паузы. Например: звук 60 дБ на 1кГц маскирует звук 40 дб на 1,1кГц.(ок. 5 мсек).

    · Эффект частотного маскирования :

  • Близкий по частоте менее громкий звук маскируется более громким (не слышен). Например: звук 60 дБ на 1кГц маскирует звук 40 дб на 1,1 кГц, при увеличении громкости он становится слышен.

    · Основа цифровой обработки звука - дискретизация (sampling), кот. состоит в периодическом измерении амплитуды сигнала, ее масштабировании и сохранении.

  • 8-битовый АЦП конвертирует диапазон уровней сигнала [ -500mV, 500mV ] в коды в диапазоне [ -128, +127 ].

  • Разрешение дискретизации - показатель точности измерения уровня сигнала, всегда кратен 4-м ( отсюда ошибки дискретизации при округлении). Для данного АЦП оно равно 4mV.

  • Частота дискретизации (Найквиста) - для качественного воспроизведения исходного сигнала должна больше чем в 2 раза превышать частоту исходного сигнала.(телефон - 8 кГц, аудио - 44кГц).

  • Полоса - ширина основной (несущей ?) волны, ед.изм. 1 Bark.

  1. Простые методы сжатия.

    · В звуковых файлах почти нет повторяющихся последовательностей кодов дискретизации.

    · Если уровень звукового сигнала не перекрывает весь диапазон дискретизации АЦП, то значительную часть кодов не будет использована при записи (уместен алгоритм Хаффмана).

    · LZSS - в ср. Уменьшает объем звукового файла на 15%.

    · адаптивное кодирование Хаффмана - на 20-25%.

  2. Методы сжатия с потерями.

· Сжатие тишины (преобразование в абсолютную тишину).

  • Определение уровня фона (относительной тишины), его начала и конца.

  • Сжатие по методу RLE

  • G/721 - ADPCM

  • кодирование разницы уровней двух последовательных элементов дискретизации сигнала.

  • “адаптированная квантизация”,т.е. масштабирование разрешения дискретизации по уровню сигнала : меньшему значению - меньше битов.

· LPC - Метод линейного предсказания речи - преобразует сигнал с помощью модели речевого тракта, затем манипулирует параметрами полученной модели. Зависит от мощности процессора.

  • Механический голос на 2.4 кбит/сек.

· CELP - Реализует алгоритм линейного предсказания речи , оперируя при этом кодом ошибки.

  • Качество аудио конференций при 4.8 кбит/сек.

  1. Сжатие mpeg-audio (Musicam) .

· MPEG-1 : 1,5Мбит/сек для видео + аудио ( 1,2 + 0,3 ) Мбит/сек.

(на несжатом CD аудио представлено как 44,100 отсчетов/сек * 16 бит/отсчет * 2 канала по 1,4 Мбит/сек.

· К-т сжатия в диапазоне от 2.7 до 24.

· Поддерживает 16 бит, частоты 32, 44,1 и 48 кГц.

· Поддерживает 1 или 2 аудио канала и любую из 4-х моделей:

  1. Монофоническая (1 канал)

  2. Ди-Монофоническая (2 моно-канала), = стерео.

  3. Стерео - для стереоканалов со смещением бит без совмещенного кодирования.

  4. Ко-Стерео - с совмещенным кодированием для увеличения связи между стереоканалами.

· При сжатии 6:1 результат неотличим от оригинала при наивысших показателях ( 16 бит стерео на частоте 48 кГц в 256 кбит/сек).

Алгоритм:

  1. Сворачивающими фильтрами делят сигнал на 32 полосы - по 12 отсчетов в каждом.

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

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

    Анализируются соотношения Mask-to-Noise-Ratio (рис.1) и Signal-to-Noise-Ratio - шум квантования. Чем выше частота, тем ощутимее погрешность, тем больше необходимо выделить бит.

    рис.1

    Алгоритм распределения бит:

    while ( N доступных бит ³ 0 )

    { ищем max(SMR);

    для соотвествующей полосы ++ бит;

    для соотвествующей полосы нов.значен. SMR=SMR-SNR;

    }

    где SMR=MNR-SNR - чем больше N бит, тем больше SNR (находится по таблице Musicam), тем меньше SMR.

  4. Формирование Bit-stream.

    Получается массив Bit_alloc[32], элементы которого длиной 4 бита содержат N бит для кодирования соответствующей полосы:

    0000 - 1

    0001 - 2

    0010 - 3

    ...

    1111 - 16

    Для кодирования с плавающей точкой числа спектра разбиваются на порядок Sij и мантиссу Mant.

    Для каждой полосы находится Sig - max из 12 отсчетов. Все Sij кодируются в 6 бит по таблице Musicam. Все отсчеты i-полосы делятся на Sig ( приближение к единице). Каждый из 12 отсчетов пакуется в N бит, определенных для полосы.

    Создается фрейм - код 384 отсчетов исходного звука (рис.2):

рис.2. Здесь Fd - к-нт сжатия.

Декодирование выполняется в обратном порядке.

Пример:

После анализа уровень сигнала в первых 16 полосах:

Полоса

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Уровень, дБ

0

8

12

10

6

2

10

60

35

20

15

2

3

5

3

1

Т.к. уровень полосы 8 - 60 дБ , то она маскирует полосы 7 и 9, громкость которых 10 и 35 дБ соответственно. Ошибка квантизации составит до2 бит (=12 дБ).

Уровни MPEG-Audio

Уровень 1. Описан выше.

Уровень 2.

  1. Размер Bit_alloc и уровни определяются по таблице. В уровнях возможен скачек : 2, 1, 16 бит и т.д.

  2. Кодируются все Sij подряд, если встречаются близкие по значению - пишется одно - для этого введен SelectInj ( 2 бит) : 00 - 3Sij

01 - 2Sij

10 - 2Sij

00 - 1Sij

  1. Группировка отсчетов: 3 мантиссы могут группироваться в 5, 7 или 9 бит.

Для 5 бит: закодируем каждую из них в 2 бита, всего 6 бит. Если ни одна из них не равна 11, а может быть 00, 01, 10, то

Rez = x + 3y + 9z,

max(Rez) = 2 + 3 * 2 + 9 * 2 = 26 - кодируется в 5 бит

Для 7 бит:

Rez =x + 5y + 25z.

  1. Фрейм для уровня 2:

  2. При фильтрации обрабатываются сразу 3 фрейма - 1152 отсчета.

  3. Реализован с учетом временного маскирования.

Уровень 3.

  1. Более совершенный фильтр на основе “неэквивалентных частот”.

  2. Реализован эффект временного маскирования.

  3. Учитывается дублирование для стерео.

  4. Используется алгоритм Хаффмана.

Эффективность MPEG audio

Уровни

Выходной поток

К-нт сжатия

Качество при 64 кбит

Качество при 128 кбит

Теоретическая задержка, min

1

192 кбит

4:1

---

---

19 ms

2

128 кбит

6:1

2.1 - 2.6

4+

35 ms

3

64 кбит

12:1

3.6 - 3.8

4+

59 ms

Реальная задержка составляет ок. трех теоретических.

5 - прекрасно

4 - почти без замечаний

3 - несколько неприятный

2 - раздражающий

1 - противный

Поддерживается двухсторонняя между всеми тремя уровнями MPEG audio совместимость.