'

Сжатие без потерь

Понравилась презентация – покажи это...





Слайд 0

1 Сжатие без потерь Дмитрий Ватолин Московский Государственный Университет CS MSU Graphics&Media Lab Version 2.2


Слайд 1

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 2 Материалы о сжатии В мае 2002 года на базе нашей лаборатории был создан сервер «Все о сжатии»: http://www.compression.ru/. Сейчас сайт содержит более 600Мб информации и является крупнейшим русскоязычным сайтом по сжатию. На сайте выложена книга Д.Ватолин, М.Смирнов, А.Ратушняк, В.Юкин «Методы сжатия данных», Диалог-МИФИ, 2002. Данный курс дополняет ее в областях сжатия аудио, изображений и 3D-видео.


Слайд 2

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 3 Цель лекций Целью данных лекций является рассказ об избранных базовых и новых технологиях, использующихся при сжатии звука, изображений и видео. Первыми рассказываются методы сжатия без потерь, базовые для остальных методов.


Слайд 3

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 4 Структура материала Введение Общие понятия сжатия Теорема Шеннона Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman


Слайд 4

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 5 Методы сжатия без потерь Методы сжатия без потерь разделяют на две категории: Методы сжатия источников данных без памяти (т.е. не учитывающих последовательность символов) Методы сжатия источников с памятью


Слайд 5

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 6 Методы сжатия источников без памяти Сжатие по Хаффману Самый известный и распространенный метод. Сдает позиции более мощному арифметическому сжатию. Арифметическое сжатие Наилучший на сегодня метод по степени сжатия. Имеет быструю реализацию, крайне гибок. Сжатие с кодами Райса-Голомба Используется как компромисс между методом Хаффмана и Арифметическим, когда есть ограничения на вычислительную сложность.. (также известны нумерующие кодирование, разделение мантисс и экспонент, коды Элиаса, Фибоначчи и др.)


Слайд 6

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 7 Методы сжатия источников с памятью Словарные методы сжатия (LZ, LZW. Давний универсальный метод (ZIP), используется для сжатия в GIF & PNG) Методы контекстного моделирования (PPM. Новый универсальный метод. Позволяет добиться максимальных результатов.) Сжатие с использованием преобразования Барроуза-Уилера и других сортирующих преобразований (BWT, ST. Используется в основном для текста.)


Слайд 7

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 8 Алгоритм Хаффмана Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины. Для сбора статистики требует двух проходов по изображению.


Слайд 8

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 9 Алгоритм Хаффмана-2


Слайд 9

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 10 Алгоритм Хаффмана-3 Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты). Использование: Практически не применяется в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах. Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных). Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).


Слайд 10

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 11 Теорема Шеннона Теорема о кодировании источника: Элемент si, вероятность появления которого равняется p(si), выгоднее всего представлять –log2 p(si) битами. Если при кодировании размер кодов всегда в точности получается равным –log2 p(si) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования.


Слайд 11

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 12 Энтропия источника Если распределение вероятностей F = {p(si)} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное: Это значение также называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.


Слайд 12

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 13 Структура материала Введение Общие понятия сжатия Теорема Шеннона Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman


Слайд 13

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 14 Арифметическое сжатие Основная идея: Мы представляем кодируемый текст в виде длинной дроби. Для этого берется интервал [0, 1) (0 — включается, 1 — нет), который разбивается на подынтервалы с длинами, пропорциональными вероятностям появления символов в потоке.


Слайд 14

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 15 AC: Пример Пусть мы сжимаем текст "КОВ.КОРОВА"


Слайд 15

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 16 AC: Визуальное представление Графически соответствующую процедуру можно представить так:


Слайд 16

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 17 АС: Пример Берем исходный интервал и кодируем текст: Изначально интервал [0, 1). Символ "К" [0.3; 0.5) получаем [0.3; 0.5). Символ "О" [0.0; 0.3) получаем [0.3; 0.36). Символ "В" [0.5; 0.7) получаем [0.33; 0.342). Символ "." [0.9; 1.0) получаем [0,3408; 0.342).


Слайд 17

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 18 АС: Процедура сжатия Если обозначить интервал символа c, как [a[c]; b[c]), а кодируемый интервал для i-го символа потока как [li, hi). То алгоритм компрессии запишется как: l0=0; h0=1; i=0; while(not DataFile.EOF()){ c = DataFile.ReadSymbol(); i++; li = li-1 + a[c]·(hi-1 - li-1); hi = li-1 + b[c]·(hi-1 - li-1); };


Слайд 18

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 19 АС: Процедура распаковки Алгоритм декомпрессии выглядит так: l0=0; h0=1; value=File.Code(); for(i=0; i<File.DataLength(); i++){ for(all symbols cj){ li = li-1 + a[cj]·(hi-1 - li-1); hi = li-1 + b[cj]·(hi-1 - li-1); if (li <= value < hi) break; }; DataFile.WriteSymbol(cj); };


Слайд 19

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 20 АС: Двоичные дроби Заметим, что мы можем приближать получающуюся дробь с помощью двоичной дроби


Слайд 20

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 21 АС: Бесконечное сжатие Пример: один бит "1" (двоичное число "0.1") для наших интервалов однозначно задает цепочку "ВОООООООООО…" сколь угодно большой длины.


Слайд 21

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 22 АС: Целочисленные вероятности Перейдем к целочисленным коэффициентам:


Слайд 22

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 23 АС: Пример нормализации Движение подынтервалов при реальном сжатии В выходной поток


Слайд 23

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 24 АС: Реальный пример процедуры сжатия l0=0; h0=65535; i=0; delitel= b[clast]; // =10 First_qtr = (h0+1)/4; Half = First_qtr*2; // = 16384 = 32768 Third_qtr = First_qtr*3; bits_to_follow =0; // = 49152, Сколько бит сбрасывать   while(not DataFile.EOF()) { c = DataFile.ReadSymbol(); // Читаем символ j = IndexForSymbol(c); i++ // Находим его индекс li = li-1 + b[j-1]*(hi-1 - li-1 + 1)/delitel; hi = li-1 + b[j ]*(hi-1 - li-1 + 1)/delitel - 1; for(;;) { // Обрабатываем варианты if(hi < Half) // переполнения bits_plus_follow(0); else if(li >= Half) { bits_plus_follow(1); li-= Half; hi-= Half; } else if((hi < First_qtr)&&(li >= Third_qtr)){ bits_to_follow++; li-= First_qtr; hi-= First_qtr; } else break; li+=li; hi+= hi+1; } }


Слайд 24

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 25 АС: Реальный пример процедуры сжатия (2) // Процедура сброса найденных бит в файл void bits_plus_follow (int bit) { CompressedFile.WriteBit(bit); for(; bits_to_follow > 0; bits_to_follow--) CompressedFile.WriteBit(!bit); }


Слайд 25

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 26 АС: Работа целочисленного алгоритма Пример сжатия цепочки:


Слайд 26

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 27 АС: Характеристики Характеристики арифметического сжатия: Позволяет сжимать несколько сильнее, чем алгоритм Хаффмана Работает медленнее, чем алгоритм Хаффмана Допускает как статическую, так и динамическую (адаптивную) реализацию


Слайд 27

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 28 АС: Сравнение с алгоритмом Хаффмана


Слайд 28

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 29 АС: Пример Пусть есть два символа a и b с вероятностями 253/256 и 3/256 Для арифметического сжатия мы потратим на цепочку из 256 байт –log2(253/256)·253–log2(3/256)·3 = 23.546, т.е. 24 бита. При кодировании по Хаффману мы закодируем a и b как 0 и 1, и потратим 1·253+1·3=256 битов, т.е. в 10 раз больше


Слайд 29

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 30 Повышение степени сжатия Методы повышения степени сжатия: Применение динамических таблиц Изменение агрессивности динамической подстройки Инициализация таблиц (несколько таблиц) Использование переключения между таблицами Увеличение точности вычислений (в int & double) Использование PPM


Слайд 30

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 31 Структура материала Введение Общие понятия сжатия Теорема Шеннона Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman


Слайд 31

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 32 PPM: Идея Классический PPM (prediction by partial matching) - это метод контекстно-зависимого моделирования ограниченного порядка, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Если для оценки вероятности используется контекст длины N, то мы имеем дело с контекстно-ограниченной моделью степени N или порядка N.


Слайд 32

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 33 PPM: Общая схема алгоритма Важно, что каждый новый символ кодируется на оценке его вероятности


Слайд 33

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 34 PPM: Пример модели 0 Простой пример – модель порядка 0: тогда вероятность следующего символа будет зависеть от того, как часто он встречался ранее.


Слайд 34

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 35 PPM: Пример модели 1 Простой пример – модель порядка 1: тогда вероятность следующего символа будет зависеть от предыдущего символа.


Слайд 35

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 36 PPM: варианты моделирования Статическое Используется фиксированная модель Полуадаптивное Модель сохраняется в файле Адаптивное (динамическое) Модель изменяется в процессе сжатия и распаковки Блочно-адаптивное Модель меняется сильно между блоками разных данных


Слайд 36

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 37 PPM: Выбор сложности модели Зависимости степени сжатия от длины модели для текстовых данных


Слайд 37

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 38 PPM: Принципы сжатия сигналов В модели сигнала - используются знания о важности частей сигнала для человека В модели коэффициентов используются знания об избыточности коэффициентов.


Слайд 38

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 39 PPM: Сжатие изображений Используется преобразование цветовых пространств и т.д. Модели сигнала: DCT Wavelets Fractals (Аффинное преобразование)


Слайд 39

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 40 PPM: Сжатие видео Используется преобразование цветовых пространств (избыточность по цвету). Используется компенсация движения (избыточность по времени). Модели сигнала: DCT Wavelet Object-oriented


Слайд 40

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 41 PPM: Сжатие звука Используется маскирование по частоте (избыточность по частоте). Используется маскирование по времени. Используется избыточность стерео-сигнала. Модели сигнала: MDCT DCT FFT Wavelets


Слайд 41

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 42 Задача: общая постановка Программа умеет получать на вход файл и по опции «с» - сжимать его, по опции «d» распаковывать его. Задается метод сжатия – арифметический (обязателен) и PPM. Язык реализации – консольное приложение на С или С++ Пример: compress c in_file.doc out_file.cmp ppm compress d out_file.cmp out_file.doc


Слайд 42

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 43 Задача: Требования Арифметическое сжатие – только классический алгоритм (методы его оптимизации разбирались) За использование чужих текстов или совместное написание – дисквалификация. Оцениваться будет степень сжатия файлов, отдаваемых на вход программы. Распакованный файл должен совпадать с паковавшимся!!!


Слайд 43

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 44 Задача: Улучшение результата Методы повышения степени сжатия: Применение динамических таблиц Изменение агрессивности динамической подстройки Инициализация таблиц (несколько таблиц) Использование переключения между таблицами Увеличение точности вычислений (в int & double)


Слайд 44

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 45 Задача: Сроки Срок начала задания – 15 октября Срок сдачи задания – 05 ноября Сдаются: Исходный текст в виде компилируемого проекта Пояснения (read_me) с указанием фамилии, группы и номера зачетной книжки Скомпилированная программа и пример Готовое задание высылается по адресу c-course-a1@compression.ru


Слайд 45

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 46 Структура материала Введение Общие понятия сжатия Теорема Шеннона Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman


Слайд 46

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 47 BWT / Идея BWT (Burrows-Wheeler Transform) – преобразование Бароуза-Уилера – предназначено для того, чтобы сделать сжатие потока данных более эффективным. Алгоритм опубликован в 1994 (разработан – в 1983). Мы переставляем символы выходного потока таким образом, что применяемый далее алгоритм становится более эффективен.


Слайд 47

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 48 BWT / Шаг 1 Пусть мы сжимаем строку символов «абракадабра». Подготовим все ее циклические перестановки. абракадабра бракадабраа ракадабрааб акадабраабр кадабраабра адабраабрак дабраабрака абраабракад браабракада раабракадаб аабракадабр


Слайд 48

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 49 BWT / Шаг 2 Пометим в получившейся матрице исходную строку и отсортируем все строки в соответствии с лексикографичес-ким порядком символов. 0 аабракадабр 1 абраабракад 2 абракадабра – исх. строка 3 адабраабрак 4 акадабраабр 5 браабракада 6 бракадабраа 7 дабраабрака 8 кадабраабра 9 раабракадаб 10 ракадабрааб


Слайд 49

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 50 BWT / Шаг 3 Выписываем символы последнего столбца и запоминаем номер исходной строки среди отсортированных. Получаем результат преобразования BWT: «рдакраааабб», 2  Длина результата и состав символов – как в исходной цепочке. аабракадабр абраабракад абракадабра - 2 адабраабрак акадабраабр браабракада бракадабраа дабраабрака кадабраабра раабракадаб ракадабрааб


Слайд 50

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 51 BWT / Суть «Фокус» BWT в том, что полученной цепочки «рдакраааабб» и числа 2 достаточно для воссоздания исходной цепочки. Зачем это нужно? Если мы преобразуем таким образом достаточно длинный текст, со словами the, The, then, when, that, то мы получим на выходе цепочку в которой будет столько t подряд, сколько слов the в исходной цепочке, потом будет идти столько T, сколько The и т.д. Происходит сортировка по «частоте сочетаний» ………… he ... t he ... t he ... t he ... t he ...T he ... t he ... t hen ... t hen ...w hen ... t hen ... t …………


Слайд 51

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 52 Обратное BWT / Шаг 1 Итак! Мы получили на вход In={рдакраааабб}, 2 Отсортируем полученную цепочку символов. Нам известно, что строки матрицы были отсортированы по порядку, начиная с первого символа. Поэтому в результате такой сортировки мы получили первый столбец исходной матрицы. 0 а 1 а 2 а 3 а 4 а 5 б 6 б 7 д 8 к 9 р 10 р


Слайд 52

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 53 Обратное BWT / Шаг 2 Поскольку последний столбец по условию задачи нам известен, добавим его в полученную матрицу. 0 а.........р 1 а.........д 2 а.........а 3 а.........к 4 а.........р 5 б.........а 6 б.........а 7 д.........а 8 к.........а 9 р.........б 10 р.........б


Слайд 53

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 54 Обратное BWT / Шаг 3 Строки матрицы были получены в результате циклического сдвига исходной строки. То есть, символы последнего и первого столбцов образуют друг с другом пары. И нам ничто не может помешать отсортировать эти пары, поскольку обязательно существуют такие строки в матрице, которые начинаются с этих пар. Заодно допишем в матрицу и последний столбец (рдакраааабб). 0 аа........р 1 аб........д 2 аб........а 3 ад........к 4 ак........р 5 бр........а 6 бр........а 7 да........а 8 ка........а 9 ра........б 10 ра........б


Слайд 54

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 55 Обратное BWT / Идея Заметим, что шаг 3 можно повторить еще раз, отсортировав уже тройки символов. Повторяем этот шаг столько раз, сколько необходимо для восстановления всей таблицы, а потом берем из нее строку с номером 2 в качестве исходной.


Слайд 55

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 56 Обратное BWT полностью


Слайд 56

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 57 Обратное BWT Быстрый вариант (1) Запишем порядок строк после сортировки и перед сортировкой.


Слайд 57

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 58 Обратное BWT Быстрый вариант (2) Полученный вектор T = { 2, 5, 6, 7, 8, 9, 10, 1, 3, 0, 4 }, содержит номера позиций символов, упорядоченных в соответствии с положением в алфавите, в строке, которую нам надо декодировать. Начинаем декодирование со второго элемента. T[2] = 6, T[6] = 10, T[10] = 4, T[4] = 8… Получаем цепочку: 6, 10, 4, 8, 3, 7, 1, 5, 9, 0, 2 А теперь, выписываем соответствующие символы из исходной цепочки (In[6], In[10]…). Получаем абракадабра 2 0 р 5 1 д 6 2 а 7 3 к 8 4 р 9 5 а 10 6 а 1 7 а 3 8 а 0 9 б 4 10 б


Слайд 58

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 59 BWT – Характеристики Характеристики BWT: Работает сравнительно медленно Требует достаточно много памяти Позволяющее значительно поднять степень сжатия, в особенности на текстовых данных.


Слайд 59

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 60 Метод MTF Метод MTF (Move To Front) – русское название «метод стопки книг» Идея крайне проста: Мы получаем из потока новый символ (название книги), Помещаем в выходной поток ее номер в стопке Кладем книгу в начало стопки ………… he ... t he ... t he ... t he ... t he ...T he ... t he ... t hen ... t hen ...w hen ... t hen ... t …………


Слайд 60

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 61 Метод MTF / Псевдокод N – число символов в алфавите. M[N]  – упорядоченный список символов. M[0] соответствует верхней книге стопки, M[N-1] — нижней. x – очередной символ   int tmp1, tmp2, i=0; tmp1 = M[i]; while( tmp1 != x ) { tmp2 = tmp1; i++; tmp1 = M[i]; M[i] = tmp2; } M[0] = x; Обработаем 'рдакраааабб': Получим '43243200040':


Слайд 61

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 62 Метод MTF / Пример Пусть есть цепочка: 'bbbbcccccdddddaaaaab' Если сжимать ее по Хаффману, то вероятность всех символов ? и потребуется 20*2 = 40 бит Предположим, что начальный упорядоченный список символов выглядит как {'a', 'b', 'c', 'd'}. bbbbcccccdddddaaaaab — исходная строка 10002000030000300003 — строка после MTF Получившуюся строку можно упаковать по Хаффману в 15*1 + 3*2 + 3 + 3 = 27 бит


Слайд 62

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 63 Метод MTF / Применение MTF наиболее эффективно применять на цепочках, получающихся после BWT. Общая схема алгоритма при этом выглядит как: BWT >> MTF >> RLE >> арифметич. сжатие Изредка MTF эффективен и просто перед словарными методами.


Слайд 63

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 64 Структура материала Введение Общие понятия сжатия Теорема Шеннона Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman


Слайд 64

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 65 LZ-Huffman Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев


Слайд 65

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 66 Модификация LZ77 LZ77 Деревья Хаффмана Масштабируемое окно LZX


Слайд 66

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 67 Деревья Хаффмана 1.0 0.4 0.3 0.1 0.2 0.3 0.6 1.Если два элемента имеют одинаковую длину пути, то элемент с меньшей частотой должен располагаться левее.


Слайд 67

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 68 Деревья Хаффмана 2.Если вершина имеет потомков, то все остальные вершины с той же длиной пути, лежащие левее, также должны иметь потомков. 3. Дерево должно содержать как минимум два элемента.


Слайд 68

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 69 Деревья, используемые в алгоритме Основное дерево (main tree). Дерево длин (length tree). Дерево выровненных смещений (aligned offset tree), pre-деревья (pre-tree), etc.


Слайд 69

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 70 LZ-Huffman Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев


Слайд 70

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 71 Repeated Offsets (LZ77 modifications) Идея: отдельно хранить три наиболее часто употребляемых смещения (вернее их коды (repeated offset codes)) в отдельном списке. Структура списка : R0 – самое последнее смещение R1 – предпоследнее смещение R2 – третье по счету.


Слайд 71

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 72 Работа со списком смещений


Слайд 72

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 73 LZ-Huffman Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев


Слайд 73

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 74 Алгоритм LZX Формат данных:


Слайд 74

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 75 Если первый бит равен 1, то имеется предварительная обработка. В таком случае за ним идет дополнительная информация о параметрах предварительного кодирования. Алгоритм LZX


Слайд 75

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 76 Содержание Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков данных Кодирование деревьев


Слайд 76

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 77 Предобработка Цель: Предварительная обработка для улучшения сжатия 32х-разрядных исполняемых файлов (.exe, .dll, .ocx, …)


Слайд 77

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 78 Предобработка Реализация: Замена во всех командах CALL (код E8h) относительного смещения на абсолютное. Остальные данные не меняются.


Слайд 78

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 79 Предобработка (Поясняющая диаграмма) Loop … E8 a11 a12 a13 E8 a21 a22 a23 E8 a31 a32 a33 До Loop … E8 a1 a2 a3 E8 a1 a2 a3 E8 a1 a2 a3 После


Слайд 79

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 80 Предобработка (Pseudocode) CALL byte sequence (E8 followed by 32 bit offset) E8 r0 r1 r2 r3 Performing the relative-to-absolute conversion relative_offset = r0 + (r1<<8) + (r2<<16) + (r3<<24); new_value = conversion_function(current_location, relative_offset); a0 = bits_0_7(new_value); a1 = bits_8_15(new_value); a2 = bits_16_23(new_value); a3 = bits_24_31(new_value); Translated CALL byte sequence E8 a0 a1 a2 a3


Слайд 80

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 81 LZ-Huffman Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков данных Кодирование деревьев


Слайд 81

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 82 Сжатие информации (кодирование символов) Блок Header Data Unmatched symbols Matched symbols Одиночные символы Подстановки


Слайд 82

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 83 Одиночные символы (unmatched symbols) Все 256 стандартных символов ASCII кодируются при помощи дерева Хаффмана. Что позволяет наиболее частые (для данного файла) символы кодировать меньшим количеством бит, а менее частые – большим. Символы представляются элементами 0…(NUM_CHARS-1) основного дерева Хаффмана (main tree).


Слайд 83

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 84 Кодирование подстановок Идея: Искать “большие” повторяющиеся последовательности. Записывать их один раз и давать им код. Далее ссылаться на них только по этому коду (несколько бит).


Слайд 84

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 85 Кодирование подстановок Match length Match offset Formatted offset Position slot Position footer Length header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2 Main tree 1 Aligned offset tree 4 OUTPUT


Слайд 85

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 86 Кодирование подстановок Подстановка задается двумя параметрами: длина подстановки (match length) cмещение подстановки (match offset) относительно текущей позиции


Слайд 86

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 87 Преобразование смещения Match length Match offset Formatted offset Position slot Position footer Length header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2 Main tree 1 Aligned offset tree 4 OUTPUT


Слайд 87

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 88 Преобразование смещения (Match offset ? Formatted offset) Converting a match offset to a formatted offset if (offset = = R0) formatted offset = 0; else if (offset = = R1) formatted offset = 1; else if (offset = = R2) formatted offset = 2; else formatted offset = offset + 2;


Слайд 88

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 89 Таблица смещений


Слайд 89

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 90 Преобразование смещения Match length Match offset Position slot Position footer Length header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2 Main tree 1 Aligned offset tree 4 OUTPUT Formatted offset


Слайд 90

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 91 Преобразование смещения (Formatted offset ? Position slot, Position footer) Position slot Position footer Форматированное смещение 0..17 bits


Слайд 91

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 92 Таблица преобразования смещения


Слайд 92

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 93 Определение значения величины position footer


Слайд 93

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 94 Вычисление значений position slot и position footer Calculating the position slot and position footer position_slot = calculate_position_slot(formatted_offset); position_footer_bits = extra_bits(position_slot); if (position_footer_bits > 0) position_footer = formatted_offset & ((1<<position_footer_bits)-1); else position_footer = null;


Слайд 94

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 95 Position footer Match length Match offset Formatted offset Position slot Length header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2 Main tree 1 Aligned offset tree 4 OUTPUT Position footer


Слайд 95

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 96 Position footer Position footer Verbatim bits Aligned offset bits Есть выравнивание? нет да


Слайд 96

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 97 Position footer (code) if (block_type = = aligned_offset_block){ if (formatted_offset <= 15){ verbatim_bits = position_footer; aligned_offset = null; } else{ aligned_offset = position_footer; verbatim_bits = position_footer >> 3; } } else{ verbatim_bits = position_footer; aligned_offset = null; }


Слайд 97

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 98 Преобразование длины смещения Match length Match offset Formatted offset Position slot Position footer Length header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2 Main tree 1 Aligned offset tree 4 OUTPUT


Слайд 98

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 99 Преобразование длины смещения (Match length ? Length header, Length footer) Pseudocode for obtaining the length header and footer if (match_length <= 8){ length_header = match_length-2; length_footer = null; } else{ length_header = 7; length_footer = match_length-9; }


Слайд 99

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 100 Пример


Слайд 100

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 101 Diagram of match sub-components Match length Match offset Formatted offset Position footer Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2 Main tree 1 Aligned offset tree 4 OUTPUT Length header Position slot


Слайд 101

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 102 Length header, Position slot ? Length / Position header len_pos_header = (position_slot << 3) + length_header


Слайд 102

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 103 Кодирование подстановки Match length Match offset Formatted offset Position slot Position footer Length header Length/Position header Aligned offset bits Length footer OUTPUT Verbatim position bits 3 Length tree 2 Main tree1 Aligned offset tree 4


Слайд 103

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 104 Кодирование подстановки (Encoding a match) Используется до 4-ех полей: 1. Output element (len_pos_header + NUM_CHARS) from the main tree 2. If length_footer != null, then output element length_footer from the length tree 3. If verbatim_bits != null, then output verbatim_bits 4. If aligned_offset_bits != null, then output element aligned_offset from the aligned offset tree


Слайд 104

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 105 LZ-Huffman Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков данных Кодирование деревьев


Слайд 105

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 106 Типы блоков Первые три бита блока указывают, к какому типу он относится. не определено сжатый блок без сжатия не определено выровненные смещения


Слайд 106

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 107 Блок без сжатия R0, R1, R2 – элементы списка смещений


Слайд 107

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 108 Сжатый блок


Слайд 108

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 109 Сжатый блок (диаграмма)


Слайд 109

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 110 Блок выровненных смещений


Слайд 110

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 111 Блок выровненных смещений (диаграмма)


Слайд 111

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 112 LZ-Huffman Основные идеи и понятия Деревья Хаффмана Repeated offsets Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев


Слайд 112

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 113 Кодирование деревьев (Encoding of trees) Основное дерево (main tree) кодируется в виде двух компонент:одно дерево для одиночных символов (unmatched symbols), другое для подстановок (matches). С учетом ограничений на дерево Хаффмана, достаточно кодировать только длину пути (path length) каждого элемента.


Слайд 113

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 114 Кодирование деревьев (Encoding of trees) 3. Для каждого блока – отдельное основное дерево: невыгодно кодировать заново лучше закодировать разницу между длиной пути в дереве первого блока и длиной пути в дереве следующего блока (для каждого элемента).


Слайд 114

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 115 Каждый элемент имеет длину пути от 0 до 16 включительно. Кодирование пути Сколько элементов имеют одинаковую длину пути ENCODING run length encoding один несколько Output Кодирование деревьев (Encoding of trees)


Слайд 115

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 116 Кодирование длины пути (диаграмма)


Слайд 116

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 117 Коды 0-16 применяются, если только один элемент имеет соответствующую длину пути. Коды 17-19 применяются для дополнительного преобразования Run-Length Encoding. В результате получаем 20 кодовых элементов, которые можно закодировать 5 битами. Но здесь также применяется оптимизация (вспомогательные деревья или pre-trees) Кодирование длины пути (пояснение)


Слайд 117

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 118 Сжатие деревьев при помощи вспомогательных деревьев 20 кодов основного дерева кодируются в зависимости от частоты их появления при помощи вспомогательного дерева (pre-tree). Структура самого вспомогательного дерева не кодируется и имеет фиксированный размер 80 бит (20 элементов по 4 бита).


Слайд 118

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 119 Вспомогательные деревья (pre-trees)


Слайд 119

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 120 Задания Задания по курсу расположены на странице курса: http://graphics.cs.msu.su/courses/mdc2004/


×

HTML:





Ссылка: