Презентация на тему: Информация и информационные процессы

Информация и информационные процессы
Что такое сжатие?
Коэффициент сжатия
Сжатие без потерь
Алгоритм RLE
Алгоритм RLE
Неравномерные коды
Префиксные коды
Код Шеннона-Фано
Код Шеннона-Фано
Код Шеннона-Фано
Алгоритм Хаффмана
Алгоритм Хаффмана
Сравнение алгоритмов
Сравнение алгоритмов
Алгоритм Хаффмана
Алгоритм LZW
Сжатие с потерями
Снижение глубины цвета
Сжатие JPEG
Сжатие JPEG
Сжатие JPEG
Сжатие рисунков с потерями и без
Сжатие звука ( MP3)
Сжатие видео
Сжатие: итоги
1/26
Средняя оценка: 4.2/5 (всего оценок: 55)
Код скопирован в буфер обмена
Скачать (452 Кб)
1

Первый слайд презентации: Информация и информационные процессы

§ 3. Сжатие данных 1

Изображение слайда
2

Слайд 2: Что такое сжатие?

2 Алфавит: A, B, C, Сообщение: А B А C А B А B А 8 0 битов в 8-битной кодировке! ! A  00 B  01 C  1 0  1 1 А B А C А B А B А  00 01 00 11 10 00 01 00 01 00 20 битов Как раскодировать? ? Словарь: 00 01 10 11 00000100 2 01000001 2 01000010 2 01000011 2 00100000 2 4 символа A ( код 65 ) B ( код 6 6) C ( код 67 ) пробел ( код 32)

Изображение слайда
3

Слайд 3: Коэффициент сжатия

3 Сообщение: 10240 символов Алфавит: A, B, C, Словарь: 5 байтов Длина кода: 10240 × 2 = 20480 битов = 2560 байтов Длина сжатого сообщения: 5 + 2560 = 2565 байтов Коэффициент сжатия – это отношение размеров исходного и сжатого файлов.

Изображение слайда
4

Слайд 4: Сжатие без потерь

4 Сжатие без потерь – это такое уменьшение объема закодированных данных, при котором можно восстановить их исходный вид из кода без искажений. За счёт чего сжимается сообщение? ? В данных должна быть избыточность! ! используются только 4 символа из 256

Изображение слайда
5

Слайд 5: Алгоритм RLE

5 RLE ( англ. Run Length Encoding, кодирование цепочек одинаковых символов ) A A … A B B … B 100 100 200 байтов Файл qq.txt Файл qq.rle ( сжатый ) 100 A 100 B 4 байта В чем состоит избыточность? ? сжатие в 5 0 раз! Сжатие с потерями или без ? ? Что в худшем случае ? ?

Изображение слайда
6

Слайд 6: Алгоритм RLE

6 8F 16 C0 16 02 16 C1 16 C2 16 1 0001111 2 11000000 2 0 0000010 2 11000001 2 11000010 2 повтор 15 A ( код 192) 2 Б ( код 193) В ( код 194) управляющие байты ААААААААААААААА БВ Распаковка: 15 2 Применение: сжатие рисунков *.bmp ( с палитрой ) один из этапов сжатия рисунков *.jpg 8F C0 02 C1 C2 16

Изображение слайда
7

Слайд 7: Неравномерные коды

7 Идея: кодировать часто встречающиеся символы более короткими кодовыми словами. Азбука Морзе: А И • • • – – – корень Н М Т Е Е • – Т И • – А • • Н – М • – – Проблема: разделить последовательность на кодовые слова! ! • • И ЕЕ Можно ли обойтись без разделителя? ?

Изображение слайда
8

Слайд 8: Префиксные коды

8 Префиксный код – это код, в котором ни одно кодовое слово не является началом другого кодового слова (условие Фано ). А И • • • – – – корень Н М Т Е Е • – Т И • – А • • Н – М • – – Это не префиксный код! ! Проблема: как построить префиксный код? ! не все символы в листьях!

Изображение слайда
9

Слайд 9: Код Шеннона-Фано

9 Алфавит: О, Е, Н, Т, Количество символов в сообщении: 1 40 О Н Е Т 68 68 64 60 На 2 группы с примерно равным числом символов: 140 E T H O 68 64 60 68 208 192 начинаются с 0 начинаются с 1 00 O 0 1 E 10 T Н 64 60 начинаются с 1 1 Т Н 110 111 в порядке невозрастания

Изображение слайда
10

Слайд 10: Код Шеннона-Фано

10 О Е Н Т 0 0 0 0 1 1 1 1 корень Это префиксный код ( все символы в листьях дерева ) ! ! Декодирование : 1110111101001011001111 111 01 111 01 0 0 10 11 0 01 111 Т O Т O Е Н О Т

Изображение слайда
11

Слайд 11: Код Шеннона-Фано

11 учитывается частота символов не нужен символ-разделитель код префиксный – можно декодировать по мере поступления данных нужно заранее знать частоты символов код неоптимален при ошибке в передаче сложно восстановить « хвост » не учитывает повторяющиеся последовательности символов

Изображение слайда
12

Слайд 12: Алгоритм Хаффмана

12 Дэвид Хаффман 140 Е Т Н О 68 64 60 68 По увеличению частоты: 140 Е Т Н О 68 68 124 140 Е О 136 Т Н 124

Изображение слайда
13

Слайд 13: Алгоритм Хаффмана

13 140 Е О Т Н 2 60 Т Н Е О 0 1 0 1 1 1 0 0 0 Т 10 0 Н 1 01 Код Хаффмана : Е 1 10 О 1 11

Изображение слайда
14

Слайд 14: Сравнение алгоритмов

14 Количество символов в сообщении: 140 О Н Е Т 68 68 64 6 0 Равномерное кодирование (8 -битный код): (140 + 68 + 68 + 64 + 60)  8 = 3200 битов Равномерное кодирование (3 -битный код): (140 + 68 + 68 + 64 + 60)  3 = 1200 битов + словарь! В чём избыточность? ?

Изображение слайда
15

Слайд 15: Сравнение алгоритмов

15 Количество символов в сообщении: 140 О Н Е Т 68 68 64 6 0 Код Шеннона-Фано: 00 О 01 Е 10 Н Т 110 111 ( 140 + 68 + 68)  2 + ( 64 + 60)  3 = 924 бита Код Хаффмана: 0 О 1 11 Е 1 10 Н Т 1 01 1 00 140 + ( 68 + 68 + 64 + 60)  3 = 9 20 бит Оптимален! !

Изображение слайда
16

Слайд 16: Алгоритм Хаффмана

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

Изображение слайда
17

Слайд 17: Алгоритм LZW

17 1977: А. Лемпел и Я. Зив, 1984: Т. Велч Идеи: кодировать не отдельные символы, а блоки последовательностям символов присваиваются числовые коды новая цепочка  занесение в словарь с новым кодом словарь строится по мере получения данных не нужны частоты символов  за один проход! Применение: сжатие рисунков *.gif, *.tif сжатие документов *.pdf

Изображение слайда
18

Слайд 18: Сжатие с потерями

18 Сжатие с потерями – это такое уменьшение объема закодированных данных, при которых распакованный файл может отличаться от оригинала. Применение: сжатие рисунков *.jpg, *.jpeg сжатие звука *.mp3, *.aac, *.ogg, … сжатие видео *.mpg, *.wmv, *.mov, … Идея: « отбросить » часть данных, которые не влияют на восприятие информации человеком (доп. размытие фотографий, частоты выше 20 кГц, …)

Изображение слайда
19

Слайд 19: Снижение глубины цвета

19 8 битов на пиксель (256 цветов) 4 бита на пиксель (16 цветов ) 2 бита на пиксель (4 цвета) размер  качество 

Изображение слайда
20

Слайд 20: Сжатие JPEG

20 RGB  Y Cb Cr яркость «синева» «краснота» Y = 0,299  R + 0,587  G + 0,114  B Cb = 128 – 0,1687  R – 0,3313  G + 0,5  B Cr = 128 + 0,5  R – 0,4187  G – 0,0813  B глаз чувствительнее к зелёному! Что для чёрно-белого (серого)? ? Cb = Cr = 128

Изображение слайда
21

Слайд 21: Сжатие JPEG

21 Идея: глаз наиболее чувствителен к яркости Y 1, Cb 1, Cr 1 Y 2, Cb 2, Cr 2 Y 3, Cb 3, Cr 3 Y 4, Cb 4, Cr 4 12 чисел например: Cb = Cb 1 + Cb 2 + Cb 3 + Cb 4 4 Cr = Cr 1 + Cr 2 + Cr 3 + Cr 4 4  Y 1, Y 2, Y 3, Y 4, Cb, Cr 6 чисел + дискретное косинусное преобразование, алгоритмы RLE и Хаффмана потери!

Изображение слайда
22

Слайд 22: Сжатие JPEG

22 качество 100 (8400 байтов) качество 50 (3165 байтов) качество 0 (1757 байтов) качество 0 (фрагмент) 40 3 0 20 1 0 0 BMP BMP( RLE ) GIF PNG JPEG (1 0 0) JPEG (50) JPEG (0) V, Кбайт Плавные переходы! ! Артефакты – заметные искажения из-за сжатия с потерями

Изображение слайда
23

Слайд 23: Сжатие рисунков с потерями и без

23 Большие области одного цвета! Чёткие границы! ! 12 0 10 0 8 0 40 0 BMP BMP( RLE ) GIF PNG JPEG (1 0 0) JPEG (50) JPEG (0) 6 0 2 0 V, Кбайт Что особенного? ? с потерями! без потерь!

Изображение слайда
24

Слайд 24: Сжатие звука ( MP3)

24 MP3 = MPEG-1 Layer 3, кодирование восприятия Битрейт – это число бит, используемых для кодирования 1 секунды звука. MP3: от 8 до 320 кбит/ c Без сжатия на CD (1 сек, 44 кГц, 16 бит, стерео): 2  88000 = 176 000 байт = 1 408000 бит = 1408 кбит C жатие MP3 ( 256 кбит / с):

Изображение слайда
25

Слайд 25: Сжатие видео

25 видео = изображения + звук Кодек (кодировщик / декодировщик ) – это программа для сжатия данных и восстановления сжатых данных. MJPEG, MPEG-4, DivX, Xvid, H.264, … Артефакты – заметные искажения из-за сжатия с потерями

Изображение слайда
26

Последний слайд презентации: Информация и информационные процессы: Сжатие: итоги

26 Сжатие уменьшает избыточность данных! ! Хорошо сжимаются : тексты ( *.txt ) документы ( *.doc ) несжатые рисунки ( *.bmp ) несжатый звук ( *.wav ) несжатое видео ( *. avi ) Плохо сжимаются : случайные данные сжатые данные в архивах ( *.zip, *.rar, *. 7 z ) сжатые рисунки ( *.jpg, *.gif, *.png ) сжатый звук ( *.mp3, *.aac ) сжатое видео ( *.mpg, *.mp4, *.mov ) Нужно ли стремиться к полному удалению избыточности? ?

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