Подсистема энтропийного кодирования при сжатии информации

Содержание

Слайд 2

Схема работы GDCT кодека

Исходное изображение

1. Прямое GDCT

2. Квантование

3. Энтропийное кодирование

Сжатое представление изображения

Восстановленное

Схема работы GDCT кодека Исходное изображение 1. Прямое GDCT 2. Квантование 3.
изображение

Обратное GDCT

Деквантование

Энтропийное декодирование

Слайд 3

Сжатие информации

Сжатие информации

Слайд 4

Стратегии сжатия

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

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

Слайд 5

Классификация методов сжатия

Классификация методов сжатия

Слайд 6

Расшифровка названий методов

CM (Context modeling) – контекстное моделирование.
DMC (Dynamic Marcov compression) –

Расшифровка названий методов CM (Context modeling) – контекстное моделирование. DMC (Dynamic Marcov
динамическое марковское сжатие
(частный случай СМ)
PPM (Predictio by partial match) –предсказание по частичному совпадению (частный случай СМ).
LZ* (LZ77, LZ78, LZH, LZW) – методы Зива – Лемпеля.
HUFFMAN ( Huffman coding) – кодирование Хаффмана.
RLE (Run length encoding) – кодирование длин повторов.
SEM (Separate exponents and mantissas) – разделение экспонент и мантисс
(представление целых чисел).
UNIC (Universal coding) – универсальное кодирование
(частный случай SEМ).
ARIC (Arithmetic coding) – арифметическое кодирование.
RC (Range coding) – интервальное кодирование
(вариант арифметического кодирования).

Слайд 7

Расшифровка названий методов

DC (Distance coding) – кодирование расстояний.
IF (Inversion frequencies) – «обратные

Расшифровка названий методов DC (Distance coding) – кодирование расстояний. IF (Inversion frequencies)
частоты» (вариант DC).
MTF (Move to front) – «сдвиг к вершине», «перемещение стопки книг».
ENUC (Enumerate coding) – нумерующее кодирование.
DFT (Discrete Fourier transform) – ДПФ- дискретное преобразование Фурье
DCT (Discrete cosine transform) – ДКП – дискретное косинусное преобразование
DWT (Discrete wavelet transform) – дискретное вейвлет – преобразование.
LPC ( Linear prediction coding) – кодер линейного предсказания.
PBS (Parallel blocks sorting) – сортировка параллельных блоков.
ST (Sort transformation) – частичное сортирующее преобразование
(частный случай PBS)
BWT (Burrows – Wheeler transform) – преобразование Барроуза – Уиллера (частный случай SТ)

Слайд 8

Характеристики сжатия

а) фактор сжатия r= FS/F0,
б) коэффициент сжатия k=F0/FS=1/r ,
в)

Характеристики сжатия а) фактор сжатия r= FS/F0, б) коэффициент сжатия k=F0/FS=1/r ,
качество сжатия η=100(1-r)=100(F0-FS)/FS.
Здесь F0 и FS – размеры исходного и выходного (сжатого файлов).
Очевидно, что при r<1, k>1 происходит сжатие выходного файла. Параметр η<100 показывает относительное уменьшение в процентах сжатого файла по сравнению с исходным файлом.

Слайд 9

Энтропия сообщения по К.Шеннону – bps (bit per symbol)

Энтропия сообщения по К.Шеннону – bps (bit per symbol)

Слайд 10

Теоретический предел длины сжатого сообщения

Теоретический предел длины сжатого сообщения

Слайд 11

Пример расчета энтропии сообщения длины сжатого сообщения и коэффициента сжатия

Сообщение :
Длинношеее животное
Частоты символов
Число

Пример расчета энтропии сообщения длины сжатого сообщения и коэффициента сжатия Сообщение :
символов n=19
Энтропия H=3.221 bps
Длина сжатого сообщения L’=n⋅H=61.201 bit
Длина исходного сообщения L=n⋅8=152 bit
Коэффициент сжатия k=2.484

Слайд 12

Пример расчета энтропии сообщения длины сжатого сообщения и коэффициента сжатия

Сообщение :
2718281828
Частоты символов
Число символов

Пример расчета энтропии сообщения длины сжатого сообщения и коэффициента сжатия Сообщение :
n=10
Энтропия H=1.846 bps
Длина сжатого сообщения L’=n⋅H=18.46 bit
Длина исходного сообщения L=n⋅8=80 bit
Коэффициент сжатия k=4.33

Слайд 13

Некоторые методы сжатия без потерь

Кодирование Хаффмана

Арифметическое кодирование

Кодирование длин
непрерывных
Последовательностей
(RLE)

Энтропийное кодирование

Некоторые методы сжатия без потерь Кодирование Хаффмана Арифметическое кодирование Кодирование длин непрерывных Последовательностей (RLE) Энтропийное кодирование

Слайд 14

Кодирование длин непрерывных последовательностей (RLE)

« a a a a a b b

Кодирование длин непрерывных последовательностей (RLE) « a a a a a b
c c c »




,,

Слайд 15

Алгоритм кодирования Хаффмана

«aabac»

= 00 00 01 00 10

10 бит

Таблица вероятностей:

L’=6.855 бит

Построение дерева

Алгоритм кодирования Хаффмана «aabac» = 00 00 01 00 10 10 бит
Хаффмана

a

b

c

0.6

0.2

0.2

0.4

1.0

Слайд 16

a

b

c

0.6

0.2

0.2

0.4

1.0

Дерево Хаффмана

«0»

«1»

‘a’

- «0»

‘b’

- «10»

‘c’

- «11»

«a a b a c»

0

0

0

10

11

7

a b c 0.6 0.2 0.2 0.4 1.0 Дерево Хаффмана «0» «1»
бит (L’=6,855 бит)

Коды Хаффмана

Кодирование Хаффмана

0 - движение по левой ветви
1 - движение по правой ветви

Слайд 17

a

b

c

0.6

0.2

0.2

0.4

1.0

Дерево Хаффмана

«0»

«1»

Декодирование Хаффмана

0 0 1 0 0 1 1

Последовательность кодов Хаффмана:

0 -

a b c 0.6 0.2 0.2 0.4 1.0 Дерево Хаффмана «0» «1»
a

0 - a

1 0 - b

0 - a

1 1 - c

Сообщение восстановлено
«a a b a c»

0 - движение по левой ветви
1 - движение по правой ветви

Слайд 18

Дерево Хаффмана – 1 вариант

Код
0
10
111
1101
1100
Энтропия Н=2.2 bps дисперсия длин кодов 1.36

Дерево Хаффмана – 1 вариант Код 0 10 111 1101 1100 Энтропия

Слайд 19

Дерево Хаффмана – 2 вариант

Код
11
01
00
101
100
Энтропия Н=2.2 bps, Дисперсия длин кодов 0.16

Дерево Хаффмана – 2 вариант Код 11 01 00 101 100 Энтропия

Слайд 20

Дисперсия длин кодов

Средняя длина кода
li - длина i-го кода в
битах
Дисперсия кода
В

Дисперсия длин кодов Средняя длина кода li - длина i-го кода в
стандартах используют готовые коды VLC
(коды переменной длины)

Слайд 21

Арифметическое кодирование

«aabc»

Таблица вероятностей:

Результат:
Любая двоичная дробь
из интервала [0,171875; 0.1875)
Например, 0.171875

L’=6

x=0.171875

Арифметическое кодирование «aabc» Таблица вероятностей: Результат: Любая двоичная дробь из интервала [0,171875;

Слайд 22

Арифметическое кодирование

«aabc»

Таблица вероятностей:

Выходной поток: 0.171875d=0.001011b=«001011»

Результат:
Любая двоичная дробь
из интервала [0,171875; 0.1875)
Например, 0.171875

Арифметическое кодирование «aabc» Таблица вероятностей: Выходной поток: 0.171875d=0.001011b=«001011» Результат: Любая двоичная дробь

Слайд 23

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

VLC – удобны для реализации, не универсальны, средняя длина отлична от

Сравнение кодов VLC – удобны для реализации, не универсальны, средняя длина отлична
энтропии
Двухпроходные коды Хаффмана – средняя длина кода близка к энтропии, информация о дереве должна присоединяться к сжатой информации.
Просты в программировании
Адаптивные коды Хаффмана не требуют априорных сведений о вероятностях символов, компрессор и декомпрессор должны быть идентичными
Арифметический кодер – средняя длина кода практически равна энтропии. Достаточно сложен в программировании. Требования априорных сведений , как у кода Хаффмана. Дерево кодирования-декодирования однозначно

Слайд 24

Исходное изображение «Masha»

Исходное изображение «Masha»

Слайд 25

Результат восстановления

RLE: 14953 байт (сжатие: 25,29)
RLE+Huffman: 11047 байт (сжатие: 34,24)
RLE+Arithm: 11022 байт

Результат восстановления RLE: 14953 байт (сжатие: 25,29) RLE+Huffman: 11047 байт (сжатие: 34,24)
(сжатие: 34,32)
PSNR(Y)=20,578 дБ, сжатие: 34,32
Имя файла: Подсистема-энтропийного-кодирования-при-сжатии-информации.pptx
Количество просмотров: 44
Количество скачиваний: 0