МЕТОДЫ СЖАТИЯ ДАННЫХ
Методы сжатия данных основаны на поиске избыточной информации и последующем кодировании с целью получения минимального обьема.
Алгоритм Хаффмана (кодирование символами переменной длины)
Вместо представления символов по таблице 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
Основные этапы:
-
Перевод изображения из пространства RedGreenBlue в пространство XYZ, где по оси Z откладывается значение цветности пиксела, 75% которых отбрасывается в ходе прореживания.
-
Переход от пространственного представления к спектральному - ДКП.
Вполученной матрице коэффициентов низкочастотные компаненты (описывающие воспринимаемые на картинке графические образы) расположены ближе к левому верхнему углу, а высокочастотные - справа внизу. Таким образом можно будет пожертвовать частью матрицы, не внося серьезных изкажений в картинку.
Для увеличения производительности изображение разбивается на несколько матриц размером 8*8 (кр.того в разнесенныхчастях изображения часто мало подобия), после чего выполняется ДКП по формуле:
[ДКП]nn = [КП]nn * [Точки]nn * [КПт]nn
где КП - м-ца косинусного преобразования размером n*n
Точки - м-ца точек картинки
КПт - транспонированная м-ца КП
В результате сложность ДКП 2*n, где n - размер м-цы
-
Квантование - деление на м-цу квантования с округлением коэффициентов.
Существует разработанный ISO стандартный набор матриц округления, значения которых как правило растут от левого верхнего угла к правому нижнему. В результате определенная часть коэффициентов из высокочастотной области обнуляется.
-
Кодирование.
· Замена абсолютных значений к-тов относительными.
· Обход м-цы зигзагом (0.0 > 0.1 > 1.0 > 2.0 > 1.1 > 0.2 > 0.3 > 1.2 >...)
· Кодирование повторов (RLE).
· Кодирование энтропии (Арифметическое кодирование или Хаффмана).
СЖАТИЕ ЗВУКОВОЙ ИНФОРМАЦИИ
-
Психоакустика.
· Слышимый человеком звук лежит в диапазоне 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.
-
Простые методы сжатия.
· В звуковых файлах почти нет повторяющихся последовательностей кодов дискретизации.
· Если уровень звукового сигнала не перекрывает весь диапазон дискретизации АЦП, то значительную часть кодов не будет использована при записи (уместен алгоритм Хаффмана).
· LZSS - в ср. Уменьшает объем звукового файла на 15%.
· адаптивное кодирование Хаффмана - на 20-25%.
-
Методы сжатия с потерями.
· Сжатие тишины (преобразование в абсолютную тишину).
-
Определение уровня фона (относительной тишины), его начала и конца.
-
Сжатие по методу RLE
-
G/721 - ADPCM
-
кодирование разницы уровней двух последовательных элементов дискретизации сигнала.
-
“адаптированная квантизация”,т.е. масштабирование разрешения дискретизации по уровню сигнала : меньшему значению - меньше битов.
· LPC - Метод линейного предсказания речи - преобразует сигнал с помощью модели речевого тракта, затем манипулирует параметрами полученной модели. Зависит от мощности процессора.
-
Механический голос на 2.4 кбит/сек.
· CELP - Реализует алгоритм линейного предсказания речи , оперируя при этом кодом ошибки.
-
Качество аудио конференций при 4.8 кбит/сек.
-
Сжатие 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 канал)
-
Ди-Монофоническая (2 моно-канала), = стерео.
-
Стерео - для стереоканалов со смещением бит без совмещенного кодирования.
-
Ко-Стерео - с совмещенным кодированием для увеличения связи между стереоканалами.
· При сжатии 6:1 результат неотличим от оригинала при наивысших показателях ( 16 бит стерео на частоте 48 кГц в 256 кбит/сек).
Алгоритм:
-
Сворачивающими фильтрами делят сигнал на 32 полосы - по 12 отсчетов в каждом.
-
Определяется маскирующее значение для каждой полосы сравнением с соседними полосами на основе психоакустической модели. Если мощность звука (громкость) в полосе ниже маскирующего значения, то полоса не кодируется (опускается).
-
В противном случае определяется количество бит, необходимое для кодирования к-та полосы так, чтобы скрыть шум, внесенный при квантизации ( через эффект маскирования): на 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.
-
Формирование 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.
-
Размер Bit_alloc и уровни определяются по таблице. В уровнях возможен скачек : 2, 1, 16 бит и т.д.
-
Кодируются все Sij подряд, если встречаются близкие по значению - пишется одно - для этого введен SelectInj ( 2 бит) : 00 - 3Sij
01 - 2Sij
10 - 2Sij
00 - 1Sij
-
Группировка отсчетов: 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.
-
Фрейм для уровня 2:
-
При фильтрации обрабатываются сразу 3 фрейма - 1152 отсчета.
-
Реализован с учетом временного маскирования.
Уровень 3.
-
Более совершенный фильтр на основе “неэквивалентных частот”.
-
Реализован эффект временного маскирования.
-
Учитывается дублирование для стерео.
-
Используется алгоритм Хаффмана.
Эффективность 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 совместимость.