'

Сжатие изображений

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





Слайд 0

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


Слайд 1

2 Часть вторая: СЖАТИЕ ИЗОБРАЖЕНИЙ


Слайд 2

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 3 Благодарности Автор выражает признательность Александру Жиркову (Graphics&Media Lab) за помощь в подготовке этих лекций (разделы Jpeg-2000 и сжатие текстур).


Слайд 3

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 4 Сжатие изображений Будут рассмотрены алгоритмы: RLE LZW Хаффмана (CCITT G3) JPEG JPEG-2000 фрактальный алгоритм


Слайд 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 Типы изображений Векторные Растровые Палитровые Безпалитровые В системе цветопредставления RGB, CMYK, … В градациях серого


Слайд 6

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 7 Восприятие цвета Чувствительность 400 нм 500 нм 600 нм 700 нм


Слайд 7

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 8 Пространство RGB RGB (Red, Green, Blue)


Слайд 8

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 9 Пространство CMYK CMYK (Cyan, Magenta, Yellow, blacK).


Слайд 9

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 10 Расчет RGB, CMYK, CMY RGB ? CMY С = 255 – R M = 255 – G Y = 255 – B. CMY?CMYK K = min(C,M,Y), C = C – K, M = M – K, Y = Y – K.


Слайд 10

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 11 Пространство HSV Модель HSV (Hue, Saturation, Value). Построена на основе субъективного восприятия цвета человеком.


Слайд 11

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 12 Модель YUV Y = 0.299R + 0.587G + 0,114B U = – 0.147R – 0.289G + 0,436B V = 0.615R + 0.515G + 0,100B = 0,877(R – Y) R = Y + 1.140V G = Y – 0.395U – 0.581V B = Y + 2.032U


Слайд 12

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 13 Модель YIQ Y = 0.299*R + 0.587*G + 0.114*B I = 0.596*R –  0.275*G –  0.321*B  Q = 0.212*R –  0.523*G + 0.311*B  R = Y + 0.956*I + 0.621*Q G = Y  –  0.272*I –  0.647*Q  B = Y  –  1.107*I + 1.704*Q 


Слайд 13

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 14 Модель YCbCr (SDTV) Y = 0.299*R + 0.587*G + 0.114*B Cb = – 0.172*R – 0.339*G + 0.511*B+128  Cr = 0.511*R –  0.428*G + 0.083*B +128 R = Y + 1.371( Cr – 128 ) G = Y  –  0.698( Cr – 128) – 0.336( Cb – 128)  B = Y  –  1.732(Cb – 128) 


Слайд 14

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 15 Классы изображений Класс 1. Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Плавные переходы цветов отсутствуют. Примеры: деловая графика — гистограммы, диаграммы, графики и т.п. Класс 2. Изображения, с плавными переходами цветов, построенные на компьютере. Примеры: графика презентаций, эскизные модели в САПР, изображения, построенные по методу Гуро. Класс 3. Фотореалистичные изображения. Пример: отсканированные фотографии. Класс 4. Фотореалистичные изображения с наложением деловой графики. Пример: реклама.


Слайд 15

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 16 Требования приложений к алгоритмам Высокая степень компрессии Высокое качество изображений Высокая скорость компрессии Высокая скорость декомпрессии Масштабирование изображений Возможность показать огрубленное изображение (низкого разрешения) Устойчивость к ошибкам Учет специфики изображения Редактируемость Небольшая стоимость аппаратной реализации. Эффективность программной реализации


Слайд 16

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 17 Критерии сравнения алгоритмов Невозможно составить универсальное сравнительное описание известных алгоритмов. Худший, средний и лучший коэффициенты сжатия. Класс изображений Симметричность Есть ли потери качества? Характерные особенности алгоритма


Слайд 17

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


Слайд 18

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 19 RLE – Первый вариант Initialization(...); do { byte = ImageFile.ReadNextByte(); if(является счетчиком(byte)) { counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=1 to counter) DecompressedFile.WriteByte(value) } else { DecompressedFile.WriteByte(byte) } while(ImageFile.EOF());


Слайд 19

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 20 RLE – Первый вариант (схема)


Слайд 20

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 21 RLE – Второй вариант Initialization(...); do { byte = ImageFile.ReadNextByte(); counter = Low7bits(byte)+1; if(если признак повтора(byte)) { value = ImageFile.ReadNextByte(); for (i=1 to counter) CompressedFile.WriteByte(value) } else { for(i=1 to counter){ value = ImageFile.ReadNextByte(); CompressedFile.WriteByte(value) } CompressedFile.WriteByte(byte) } while(ImageFile.EOF());


Слайд 21

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 22 RLE – Схемы вариантов


Слайд 22

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 23 Коэффициенты компрессии: Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты) Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Симметричность: Примерно единица. Характерные особенности: К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения. RLE – Характеристики


Слайд 23

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 24 Алгоритм LZW Название алгоритм получил по первым буквам фамилий его разработчиков — Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт.


Слайд 24

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 25 Схема алгоритма LZ


Слайд 25

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 26 LZW / Сжатие InitTable(); CompressedFile.WriteCode(СlearCode); CurStr=пустая строка; while(не ImageFile.EOF()){ //Пока не конец файла C=ImageFile.ReadNextByte(); if(CurStr+C есть в таблице) CurStr=CurStr+С; //Приклеить символ к строке else { code=CodeForString(CurStr); //code-не байт! CompressedFile.WriteCode(code); AddStringToTable (CurStr+С); CurStr=С; // Строка из одного символа } } code=CodeForString(CurStr); CompressedFile.WriteCode(code); CompressedFile.WriteCode(CodeEndOfInformation);


Слайд 26

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 27 LZW / Пример Пусть мы сжимаем последовательность 45, 55, 55, 151, 55, 55, 55. “45” — есть в таблице; “45, 55” — нет. Добавляем в таблицу <258>“45, 55”. В поток: <45>; “55, 55” — нет. В таблицу: <259>“55, 55”. В поток: <55>; “55, 151” — нет. В таблицу: <260>“55, 151”. В поток: <55>; “151, 55” — нет. В таблицу: <261>“151, 55”. В поток: <151>; “55, 55” — есть в таблице; “55, 55, 55” — нет. В таблицу: “55, 55, 55” <262>. В поток: <259>; Последовательность кодов для данного примера, попадающих в выходной поток: <256>, <45>, <55>, <55>, <151>, <259>.


Слайд 27

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 28 LZW / Добавление строк


Слайд 28

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 29 Таблица состоит из 4096 строк. 256 и 257 являются служебными. 258 … 4095 содержат непосредственно сжимаемую информацию. Таблица для LZW


Слайд 29

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 30 Кол-во считываемых байт: Пример – цепочка нулей Общее число считанных байт: Информация заносится в стр.: 1 1 -


Слайд 30

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 31 Степень сжатия цепочки нулей Рассчитываем арифметическую прогрессию:


Слайд 31

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 32 Наихудший случай ’13’ ’21’ Последовательность : 121314151617… Мы видим, что у нас нет одинаковых цепочек даже из 2 символов => сжатия не происходит.


Слайд 32

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 33 Степень сжатия наихудшего случая ’13’ ’21’ Происходит увеличение файла в 1.5 раза. Т.к. мы ни разу не встретили подстроку, которая уже есть в таблице.


Слайд 33

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 34 .. 1 13 2 45 0 0 2 3 7 76 9 32 Таблица дерево


Слайд 34

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 35 Пример Последовательность: 45, 55, 55, 151, 55, 55, 55. “45” – есть в таблице; “45, 55” – нет. В таблицу: <258>”45, 55”. В поток:<45> “55, 55” – нет. В таблицу: <259>”55, 55”. В поток:<55> “55, 151” – нет. В таблицу: <260>”55, 151”. В поток:<55> “151, 55” – нет. В таблицу: <261>”151, 55”. В поток:<151> “55, 55” – Есть в таблице; “55, 55, 55” – нет. В таблицу: <262>”55, 55, 55”. В поток:<295> Итого в потоке: <256>,<45>,<55>,<55>,<151>,<259>.


Слайд 35

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 36 Пример Последовательность: 45, 55, 55, 151, 55, 55, 55. Итого в потоке: <256>,<45>,<55>,<55>, <151>,<259>. ’55, 55’ ’45, 55’ ‘151, 55’ 261 ’55, 151’ 260 259 258 EndOfInformation 257 ClearTable 256 ‘255’ 255 … … ‘0’ 0 262 ’55, 55, 55’


Слайд 36

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 37 code=File.ReadCode(); while(code != СodeEndOfInformation){ if(code = СlearСode) { InitTable(); code=File.ReadCode(); if(code = СodeEndOfInformation) {закончить работу}; ImageFile.WriteString(StrFromTable(code)); old_code=code; } else { if(InTable(code)) { ImageFile.WriteString(FromTable(code)); AddStringToTable(StrFromTable(old_code)+ FirstChar(StrFromTable(code))); old_code=code; } else { OutString= StrFromTable(old_code)+ FirstChar(StrFromTable(old_code)); ImageFile.WriteString(OutString); AddStringToTable(OutString); old_code=code; } } } LZW / Декомпрессия


Слайд 37

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


Слайд 38

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


Слайд 39

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


Слайд 40

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


Слайд 41

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


Слайд 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 Алгоритм CCITT G3 Последовательности подряд идущих черных и белых точек заменяются числом, равным их количеству. Этот ряд сжимается по Хаффману с фиксированной таблицей. Каждая строка сжимается независимо, если строка начинается с черной точки, то считаем, что она начинается белой серией длиной 0.Например, последовательность длин серий 0, 3, 556,10,.. означает, что в строке идут сначала 3 черных, 556 белых, 10 черных точек и т.д.


Слайд 44

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 45 Алгоритм компрессии: For (по всем строкам изображения) { Преобразуем строку в набор длин серий; for (по всем сериям) { if (серия белая) { L = длина серии; while (L > 2623) { // 2623 = 2560 + 63 L -= 2560; Записать белый код для (2560); } if (L > 63) { L2 = МаксимальныйСостКодМеньшеL(L); L -= L2; Записать белый код для (L2) }; ЗаписатьБелыйКодДля(L); // код завершения } else { // аналогично для черных серий ...}


Слайд 45

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 46 В терминах регулярных выражений для каждой строки изображения выходной битовый поток вида: ((<Б-2560>)*[<Б-сст.>]<Б-зв>(<Ч-2560>)*[<Ч-сст>]<Ч-зв>)+[(<Б-2560>)*[<Б-сст.>]<Б-зв.>],где: ()* - повтор 0 или более раз, ()+ - повтор 1 или более раз, [] – включение 1 или 0 раз. Для примера 0, 3, 556, 10,… ,будет сформирован код: <Б-0><Ч-3><Б-512><Б-44><Ч-10> или Согласно таблице: 00110101 10011001 01001011 010000100 Для приведенной строки в 569 бит полусен код длиной в 33 бита, т.е. Коэфф сжатия – 17 раз Пример работы алгоритма


Слайд 46

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 47 Таблица кодов завершения


Слайд 47

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


Слайд 48

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 49 Проблемы при сжатии Пример факса (часть текста рекомендаций стандарта CCITT) на японском (?) языке.


Слайд 49

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


Слайд 50

51 Сжатие изображений с потерями


Слайд 51

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


Слайд 52

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 53 PSNR Базовые метрики – Y-PSNR, U-PSNR, V-PSNR Хорошо работают только на высоком качестве.


Слайд 53

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 54 Как интерпретировать PSNR Разные размеры кадров для разных алгоритмов Преимущество для синей линии Линия одинакового качества Чем выше, тем лучше


Слайд 54

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 55 Тестовое изображение «Барбара» Много полосок (высоких частот) в разных направлениях и разной толщины


Слайд 55

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 56 Тестовое изображение «Boat» Много тонких деталей и наклонных границ в разном направлении


Слайд 56

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


Слайд 57

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 58 Алгоритм JPEG Алгоритм разработан в 1991 году группой экспертов в области фотографии (JPEG — Joint Photographic Expert Group — подразделение в рамках ISO) специально для сжатия 24-битных изображений. Алгоритм основан на дискретном косинусном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов.


Слайд 58

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 59 Алгоритм JPEG / RGB в YUV Изначально при сжатии изображение переводится в цветовое пространство YUV. Упрощенно перевод можно представить с помощью матрицы перехода:


Слайд 59

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 60 Алгоритм JPEG


Слайд 60

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 61 Алгоритм JPEG / Примеры DCT


Слайд 61

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 62 Алгоритм JPEG / Примеры DCT


Слайд 62

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 63 Алгоритм JPEG / Характеристики Коэффициенты компрессии: 2-100 (Задается пользователем). Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). Симметричность: 1 Характерные особенности: В некоторых случаях, алгоритм создает “ореол” вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселов.


Слайд 63

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 64 Фрактальная компрессия — алгоритм с потерей информации, появившийся в 1992 году Он использует аффинные преобразования для построения изображений, что позволяет очень компактно задавать сложные структуры. Фрактальное сжатие


Слайд 64

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 65 Пример самоподобия Папоротник Барнсли Состоит задается четырьмя аффинными преобразованиями Изображение имеет четыре области, каждая из которых подобна изображению, и их объединение покрывает все изображение. (Стебель, Листья.)


Слайд 65

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


Слайд 66

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 67 Идея фрактального алгоритма Для перевода участков один в другой используется аффинное преобразование


Слайд 67

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 68 Аффинное преобразование Определение. Преобразование , представимое в виде где a, b, c, d, e, f действительные числа и называется двумерным аффинным преобразованием. Определение. Преобразование , представимое в виде где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и называется трехмерным аффинным преобразованием.


Слайд 68

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


Слайд 69

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 70 Изображение и IFS Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или Определение. Конечная совокупность W сжимающих трехмерных аффинных преобразований , определенных на областях, таких, что и , называется системой итерируемых функций (IFS).


Слайд 70

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


Слайд 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 Декомпрессор Читаем из файла коэффициенты всех блоков, и создаем изображение нужного размера (обычно черного цвета) Until(Изображение не перестанет изменятся){ For(every range (R)){ D=image->CopyBlock(D_coord_for_R); For(every pixel(i,j) in the block{ Rij = 0.75Dij + oR; } //Next pixel } //Next block }//Until end


Слайд 73

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 74 Декомпрессия: Шаг 1


Слайд 74

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 75 Декомпрессия: Шаг 2


Слайд 75

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 76 Декомпрессия: Шаг 3


Слайд 76

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 77 Декомпрессия: Шаг 4


Слайд 77

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 78 Декомпрессия: Шаг 5


Слайд 78

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 79 Примеры восстановления


Слайд 79

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 80 Пример восстановления Исходное изображение Первый шаг восстановления


Слайд 80

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 81 Фрактальное сжатие / Характеристики Коэффициенты компрессии: От 2 до 100 раз. Класс изображений: 24-битные и 8-битные grayscale изображения. Симметричность: Существенно несимметричен. Коэффициент несимметричности достигает 10000.


Слайд 81

82 СЖАТИЕ ИЗОБРАЖЕНИЙ JPEG-2000 Сравнение с JPEG


Слайд 82

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 83 JPEG 2000 Алгоритм JPEG 2000 разработан той же группой экспертов в области фотографии, что и JPEG. Формирование JPEG как международного стандарта было закончено в 1992 году. В 1997 стало ясно, что необходим новый, более гибкий и мощный стандарт, который и был доработан к зиме 2000 года.


Слайд 83

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 84 JPEG 2000 / Идея алгоритма Базовая схема JPEG-2000 очень похожа на базовую схему JPEG. Отличия заключаются в следующем: Вместо дискретного косинусного преобразования (DCT) используется дискретное вэйвлет-преобразование (DWT). Вместо кодирования по Хаффману используется арифметическое сжатие. В алгоритм изначально заложено управление качеством областей изображения. Не используется уменьшение разрешения цветоразностных компонент U и V. Кодирование с явным заданием требуемого размера на ряду с традиционным метод кодирования по качеству. Поддержка сжатия без потерь. Поддержка сжатия однобитных (2-цветных) изображений На уровне формата поддерживается прозрачность.


Слайд 84

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 85 JPEG 2000 / Схема Конвейер операций, используемый в JPEG-2000


Слайд 85

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 86 JPEG 2000 / RGB в YUV Этот шаг аналогичен JPEG (см. матрицы преобразования в описании JPEG), за тем исключением, что кроме преобразования с потерями предусмотрено также и преобразование без потерь.


Слайд 86

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 87 JPEG 2000 / DWT В одномерном случае применение DWT – это «обычная фильтрация». Из строки x мы получаем строку y по приведенным формулам. В двумерном случае мы сначала применяем эти формулы по всем строкам изображения, а потом по всем столбцам.


Слайд 87

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 88 JPEG 2000 / DWT коэффициенты коэффициенты ‘9/7’ DWT при сжатии с потерями


Слайд 88

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 89 JPEG 2000 / DWT коэффициенты (без потерь) Коэффициенты ‘5/3’ DWT при сжатии без потерь


Слайд 89

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 90 JPEG 2000 / DWT без потерь Поскольку большинство hL(i), кроме окрестности i=0, равны 0, то можно переписать приведенные формулы короче: А потом еще и упросить, как:


Слайд 90

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 91 JPEG 2000 / DWT – края Симметричное расширение изображения (яркости АБ…Е) по строке вправо и влево Применение DWT на краях изображения:


Слайд 91

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 92 JPEG 2000 / DWT – Пример Пусть мы преобразуем строку из 10 пикселов. Расширим ее значения вправо и влево и применим DWT преобразование: Получившаяся строка 1, 0, 3, 1, 11, 4, 13, -2, 8, -5 полностью и однозначно задает исходные данные. Обратное преобразование осуществляется по:


Слайд 92

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


Слайд 93

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 94 Сравнение этапа сжатия без потерь JPEG и JPEG-2000


Слайд 94

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 95 JPEG-2000 / Кодирование битовых плоскостей Разбиение DWT-пространства на одинаковые блоки, по умолчанию размером 64х64 Каждый блок кодируется не зависимо от других В отличие от EZW и SPIHT (set partitioning in hierarchical trees) межуровневые зависимости не учитываются Кодирование одной битовой плоскости одного блока осуществляется в три этапа: Кодирование старших бит Уточняющий проход Очищающий проход


Слайд 95

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 96 JPEG-2000 / Кодирование битовых плоскостей Для каждого прохода используется бинарное адаптивное арифметическое кодирование и контекстное моделирование: Арифметическое кодирование позволяет кодировать символы с произвольным распределением вероятности (не только равных степени двойки как у таблиц Хаффмана) Адаптивность позволяет задавать распределение вероятностей исходя из статистики уже закодированных данных Контекстное моделирование позволяет использовать закономерности между и внутри потоков данных, путем использования различных вероятностных таблиц для разных ‘контекстов’


Слайд 96

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 97 JPEG-2000 / Кодирование битовых плоскостей Кодирование старших бит Кодирование предсказанных и при подтверждении гипотезы, кодирование знака Контекст при кодирования значимости: значимость соседних 8-ми связанных коэффициентов Тип бэнда: LL,LH,HL,HH Контекст при кодирования знака: Значимость и знаки 4-х связанных коэффициентов 4-х и 8-ми связность


Слайд 97

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 98 JPEG-2000 / Кодирование битовых плоскостей Уточняющий проход: Кодирование существенных битов расположенных ниже первого Контекст для бита: ‘Это второй по важности бит?’ Значимость 8-ми связанных коэффицентов Очищающий проход: Кодирование не предсказанных, но существенных битов Порядок обхода


Слайд 98

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 99 JPEG-2000 / Кодирование: Внешний цикл Цель: записать в поток результаты кодирования битовых плоскостей Единица потока – пакет. Пакет – компрессированный проход одной битовой плоскости одного блока Сортировка пакетов в соответствии с выбранной стратегией: Слой-разрешение-компонента-позиция: возможность прогрессивной визуализации Разрешение-слой-компонента-позиция: прогрессивная восстановление по разрешению Другие три сценария


Слайд 99

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 100 JPEG-2000 / Изменение качества областей В JPEG-2000 используется неявное представление бинарной маски, внутри которой точность квантования коэффициентов другая нежели вне её. Метод представления и компрессии маски будет описан позже.


Слайд 100

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 101 JPEG-2000 / Алгоритм изменения качества областей Изменение качества выделенных областей При кодировании: Разделение битовой маски на выделенные и принадлежащие фону Достаточный сдвиг (умножение на степень двойки) выделенных коэффициентов на N, что бы биты выделенного изображения и фона не пересекались При декодировании: После распаковки, все коэффициенты большие 2^N сдвигаются направо на N Плюсы такого подхода: Нет необходимости явного хранения бинарной маски


Слайд 101

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 102 JPEG-2000 / Пресеты квантования Адаптированный пресет, лучше качество Стандартный пресет, больше PSNR


Слайд 102

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 103 JPEG 2000 / Отличия от JPEG Лучшее качество изображения при сильной степени сжатия. Поддержка кодирования отдельных областей с лучшим качеством. DCT преобразование заменено на DWT (плавное проявление изображения теперь изначально заложено в стандарт) Для повышения степени сжатия в алгоритме используется арифметическое сжатие. Кодирование с явным заданием требуемого размера на ряду с традиционным метод кодирования по качеству Поддержка сжатия без потерь (становится возможным использование JPEG для сжатия медицинских изображений, в полиграфии, при сохранении текста под распознавание OCR) Поддержка сжатия однобитных (2-цветных) изображений. На уровне формата поддерживается прозрачность.


Слайд 103

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 104 JPEG 2000 / Отличия от JPEG (2) на уровне формата поддерживаются включение в изображение информации о копирайте поддержка устойчивости к битовым ошибкам при передаче и широковещании


Слайд 104

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 105 JPEG / JPEG-2000: ‘Лена’ Сравнение JPEG & JPEG-2000 при сжатии в 30 раз


Слайд 105

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 106 JPEG / JPEG-2000: Сжатие в 130 раз JPEG: сохранено больше деталей JPEG-2000: отсутствие блочных артефактов


Слайд 106

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 107 Алгоритм JPEG-2000 / Характеристики Коэффициенты компрессии: 2-200 (Задается пользователем), возможно сжатие без потерь. Класс изображений: Полноцветные 24-битные изображения, изображения в градациях серого, 1-битные изображения (JPEG-2000 - наиболее универсален). Симметричность: 1 Характерные особенности: Можно задавать качество участков изображений.


Слайд 107

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


Слайд 108

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


Слайд 109

110 СЖАТИЕ ТЕКСТУР Специфика Обзор форматов S3TC, FXT1, CD, CTF-8, CTF-12


Слайд 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 Компрессия текстур: Алгоритм S3TC* Идея: Четыре цвета на блок 4х4, но хранения только двух базовых, остальные линейно интерполируются Преимущества: Шесть раз сжатие; достаточное качество; простой для аппаратной реализации алгоритм; стандарт де-факто Хранении базовых цветов в 16 битном формате, но возможно использование всех 16 млн *) SONICblue (originally S3 Inc.)


Слайд 112

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 113 Компрессия текстур: Алгоритм S3TC*


Слайд 113

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 114 Компрессия текстур: Формат FXT1* Идея/Цель Улучшение S3TC (альфа-канал, больше блок, несколько адаптивных алгоритмов) Алгоритм Для каждого блока 4х8 используется один из 4-х методов сжатия: MIXED: 2 бита/индекс, по два базовых цвета на подблок 4х4, 1 интерполируется между ними, 1 прозрачный HI: 3 бита/индекс, 2 базовых, 5 интерполируются, 1 прозрачный CHROMA: 2 бита/индекс, 4 базовых цвета ALPHA: 2 бита/индекс, 2 цвета по 20 бит (RGBA) *)3dfx Iterative Inc.


Слайд 114

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 115 Компрессия текстур: Оценка формата FXT1* Плюсы Большая степень компрессии чем у S3TC при компрессии 32-битовых изображений (8 против 6) Минусы На порядок большее время компрессии Не приемлемое качества, особенно для градиентных участков Не поддерживается большинством производителей *)3dfx Iterative Inc.


Слайд 115

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 116 Компрессия текстур: Формат CD* Идея: Использование зависимости между блоками 2-х битовая индексная плоскость, но в блоке хранится только 1 цвет, а три других берутся из соседних 3 трех блоков Плюсы 8 кратная компрессия против 6 у S3TC Минусы: Более одного обращения в память Использование только 16-битного цвета *) CGG (Computer Graphics Group)


Слайд 116

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 117 Компрессия текстур: Форматы CTF-8*, CTF-12* Идеи: Улучшение геометрии интерполяции палитры Адаптивное подразбиение блока 8х8 на 4 кластера *) MSU Graphics&Media Lab Палитра для СTF-12 Палитра для CTF-8 Примеры разбиений


Слайд 117

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 118 Компрессия текстур: Форматы CTF-8, CTF-12 Плюсы (vs S3TC): CTF-8 лучше по качеству (в среднем на 1-2 дБ) и имеет более высокую степень компрессии (8 vs. 6) CTF-12 в 2 раза больше степень сжатия при приемлемом визуальном качестве Минусы Медленный алгоритм компрессии (более чем на 2 порядка медленнее S3TC) Нет поддержки прозрачности


Слайд 118

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 119 24 бита 8 пикселей Индексы: Палитра: 8 цветов на блок 8х8, сжатие в 4.8 раза при достаточном качестве Исходный метод: простой и качественный


Слайд 119

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 120 Увеличение сжатие при сопоставимом качестве Базовые идеи: Сжатие индексов палитры (с потерями): Разбиение блока на 4 кластера, и использование меньших палитр для каждого из них Сжатие цветов палитры (с потерями): Хранение только базовых цветов и аппроксимация остальных


Слайд 120

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 121 4 кластера, 8/16 цветов в палитре, 4 цвета на текстель Метод CTF-8: 8-кратное сжатие


Слайд 121

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 122 2-х кратное сжатие цветов палитры 3 кратное сжатие индексов палитры Метод CTF-8: 12-кратное сжатие 4 кластера, 8 цветов в палитре, 2 цвета на текстель


Слайд 122

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 123 Палитризация и кластеризация Source block Local pallete CTF8: 16 color pallete 4 color in cluster CTF12: 8 color pallete 2 color in cluster


Слайд 123

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 124 Компрессия текстур: Форматы CTF-8, CTF-12 CTF-12: CTF-8:


Слайд 124

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 125 CTF-12: Два типа палитр Используется в однородных блока и во всех не цветных блоках Аппроксимация палитры – отрезок в пространстве между двумя базовым и цветами Хранятся уточняющие биты до формата RGB-565 Используется в блоках с резкими границами и в блоках с существенно разными хроматическими компонентами Аппроксимация палитры - 2 параллельных отрезка Цветовой формат отрезка – RGBY-4534 В палитре хранятся 2 базовых цвета C1 и С2, в формате RGB-453, в зависимости от “C1<C2”:


Слайд 125

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 126 Алгоритм декомпрессии для CTF-12


Слайд 126

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 127 Блочный эффект и цветовое распределение Исходный блок (12х12) CTF-8 (блоки 8х8) CTF-12 (блоки 8х8) S3TC (блоки 4х4)


Слайд 127

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 128 Граничный эффект Исходный JPEG (12раз) CTF-12 (12раз) S3TC (6раз)


Слайд 128

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 129 Сравнение S3TC с CTFs по объективным метрикам


Слайд 129

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 130 Тестовое изображение Source S3TC CTF-12


Слайд 130

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 131 Эффективность работы кэша при реальном алгоритме рендеринга Хранение всех мип-мэпов Генерация мип-мэпов ‘на лету’ Сжатые текстуры на шаре


Слайд 131

132 СЖАТИЕ ТЕКСТУР: Генерация текстур Наиболее компактный метод представления текстур – их генерация


Слайд 132

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


Слайд 133

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 134 Генерация мип-мэпов Требования: Реалистичность в не зависимости от типа и разрешения текстуры Высокая скорость и возможность аппаратной реализации Подход: вероятностная генерация Метод№1: фрактально-каскадная генерация с вероятностно-распределенным локальным коэффициентом подобия масштабных уровней Метод№2: генерация с вероятностным законом положения и расположения шаблонов


Слайд 134

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 135 A = ? B +?, ?= N(0,?), ?= N(0,?') После 8 итераций Рекурсивное фрактально-каскадное подразбиение Фрактально-каскадный метод генерации


Слайд 135

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 136 Фрактально-каскадный метод генерации Увеличение без применения генерации С генерацией 3-х дополнительных мип-мэпов


Слайд 136

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


Слайд 137

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


Слайд 138

CS MSU Graphics & Media Lab (Video Group) http://www.compression.ru/video/ 139 4n операций/текстель (n – количество масштабных уровней) Многомасштабная генерация с использованием шаблонов


Слайд 139

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


×

HTML:





Ссылка: