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

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

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

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

CS MSU Graphics & Media Lab (Video Group) Типы изображений Изображения РастровыеВекторные В

CS MSU Graphics & Media Lab (Video Group) Типы изображений u Векторные u Растровые Палитровые Безпалитровые u В системе цветопредставления RGB, CMYK, … u В градациях серого

CS MSU Graphics & Media Lab (Video Group) Восприятие цвета Чувствительность 400 нм500 нм600 нм700 нм

CS MSU Graphics & Media Lab (Video Group) Пространство RGB RGB (Red, Green, Blue) Red (1,0,0) Green (0,1,0) Blue (0,0,1) Magenta (1,0,1) Cyan (0,1,1) Yellow (1,1,0) Black (0,0,0) White (1,1,1)

CS MSU Graphics & Media Lab (Video Group) Пространство CMYK CMYK (Cyan, Magenta, Yellow, blacK). Red (1,0,0) Green (0,1,0) Blue (0,0,1)Magenta (1,0,1) Cyan (0,1,1) Yellow (1,1,0) Black (0,0,0) White (1,1,1)

CS MSU Graphics & Media Lab (Video Group) Расчет 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. Red (1,0,0) Green (0,1,0) Blue (0,0,1)Magenta (1,0,1) Cyan (0,1,1) Yellow (1,1,0) Black (0,0,0) White (1,1,1)

CS MSU Graphics & Media Lab (Video Group) Пространство HSV Модель HSV (Hue, Saturation, Value). Построена на основе субъективного восприятия цвета человеком. Red (1,0,0) Green (0,1,0) Blue (0,0,1) Magenta (1,0,1) Cyan (0,1,1) Yellow (1,1,0) Black (0,0,0) White (1,1,1) S H V

CS MSU Graphics & Media Lab (Video Group) Модель YUV Y = 0.299R G + 0,114B U = – 0.147R – 0.289G + 0,436B V = 0.615R G + 0,100B = 0,877(R – Y) R = Y V G = Y – 0.395U – 0.581V B = Y U

CS MSU Graphics & Media Lab (Video Group) Модель YIQ Y= 0.299*R *G *B I= 0.596*R – 0.275*G – 0.321*B Q= 0.212*R – 0.523*G *B R = Y *I *Q G = Y – 0.272*I – 0.647*Q B = Y – 1.107*I *Q

CS MSU Graphics & Media Lab (Video Group) Модель YCbCr (SDTV) Y= 0.299*R *G *B Cb= – 0.172*R – 0.339*G *B+128 Cr= 0.511*R – 0.428*G *B +128 R = Y ( Cr – 128 ) G = Y – 0.698( Cr – 128) – 0.336( Cb – 128) B = Y – 1.732(Cb – 128)

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) 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());

CS MSU Graphics & Media Lab (Video Group) RLE – Первый вариант (схема)

CS MSU Graphics & Media Lab (Video Group) 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());

CS MSU Graphics & Media Lab (Video Group) RLE – Схемы вариантов

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

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

CS MSU Graphics & Media Lab (Video Group) Схема алгоритма LZ

CS MSU Graphics & Media Lab (Video Group) 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);

CS MSU Graphics & Media Lab (Video Group) LZW / Пример Пусть мы сжимаем последовательность 45, 55, 55, 151, 55, 55, есть в таблице; 45, 55 нет. Добавляем в таблицу 45, 55. В поток: ; 55, 55 нет. В таблицу: 55, 55. В поток: ; 55, 151 нет. В таблицу: 55, 151. В поток: ; 151, 55 нет. В таблицу: 151, 55. В поток: ; 55, 55 есть в таблице; 55, 55, 55 нет. В таблицу: 55, 55, 55. В поток: ; Последовательность кодов для данного примера, попадающих в выходной поток:,,,,,.

CS MSU Graphics & Media Lab (Video Group) LZW / Добавление строк

CS MSU Graphics & Media Lab (Video Group) … EndOfInformation 257 ClearTable …… 00 Таблица состоит из 4096 строк. 256 и 257 являются служебными. 258 … 4095 содержат непосредственно сжимаемую информацию. Таблица для LZW

CS MSU Graphics & Media Lab (Video Group) Кол-во считываемых байт: Пример – цепочка нулей Общее число считанных байт: Информация заносится в стр.: 4095 … EndOfInformation 257 ClearTable ……

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

CS MSU Graphics & Media Lab (Video Group) Наихудшийслучай Наихудший случай … EndOfInformation 257 ClearTable …… 00 Последовательность : … Мы видим, что у нас нет одинаковых цепочек даже из 2 символов => сжатия не происходит.

CS MSU Graphics & Media Lab (Video Group) Степень сжатия наихудшего случая … EndOfInformation 257 ClearTable …… 00 Происходит увеличение файла в 1.5 раза. Т.к. мы ни разу не встретили подстроку, которая уже есть в таблице.

CS MSU Graphics & Media Lab (Video Group) Таблица дерево

CS MSU Graphics & Media Lab (Video Group) Пример Последовательность: 45, 55, 55, 151, 55, 55, – есть в таблице; 45, 55 – нет. В таблицу: 45, 55. В поток: 55, 55 – нет. В таблицу: 55, 55. В поток: 55, 151 – нет. В таблицу: 55, 151. В поток: 151, 55 – нет. В таблицу: 151, 55. В поток: 55, 55 – Есть в таблице; 55, 55, 55 – нет. В таблицу: 55, 55, 55. В поток: Итого в потоке:,,,,,.

CS MSU Graphics & Media Lab (Video Group) Пример Последовательность: 45, 55, 55, 151, 55, 55, 55. Итого в потоке:,,,,,. 55, 55 45, , , EndOfInformation 257 ClearTable …… , 55, 55

CS MSU Graphics & Media Lab (Video Group) 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 / Декомпрессия

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

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

CS MSU Graphics & Media Lab (Video Group) Алгоритм Хаффмана-2

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

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

CS MSU Graphics & Media Lab (Video Group) Примеры факсов

CS MSU Graphics & Media Lab (Video Group) Алгоритм CCITT G3 u Последовательности подряд идущих черных и белых точек заменяются числом, равным их количеству. u Этот ряд сжимается по Хаффману с фиксированной таблицей. u Каждая строка сжимается независимо, если строка начинается с черной точки, то считаем, что она начинается белой серией длиной 0.Например, последовательность длин серий 0, 3, 556,10,.. означает, что в строке идут сначала 3 черных, 556 белых, 10 черных точек и т.д.

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

CS MSU Graphics & Media Lab (Video Group) В терминах регулярных выражений для каждой строки изображения выходной битовый поток вида: (( )*[ ] ( )*[ ] )+[( )*[ ] ],где: ()* - повтор 0 или более раз, ()+ - повтор 1 или более раз, [] – включение 1 или 0 раз. Для примера 0, 3, 556, 10,…,будет сформирован код: или Согласно таблице: Для приведенной строки в 569 бит полусен код длиной в 33 бита, т.е. Коэфф сжатия – 17 раз Пример работы алгоритма

CS MSU Graphics & Media Lab (Video Group) Длина серии Код белой подстроки Код черной подстроки строки Таблица кодов завершения

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

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

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

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

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

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

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

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

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) Алгоритм JPEG

CS MSU Graphics & Media Lab (Video Group) Алгоритм JPEG / Примеры DCT

CS MSU Graphics & Media Lab (Video Group) Алгоритм JPEG / Примеры DCT

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) Идея фрактального алгоритма Для перевода участков один в другой используется аффинное преобразование

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) Поиск соответствий …

CS MSU Graphics & Media Lab (Video Group) Декомпрессор Читаем из файла коэффициенты всех блоков, и создаем изображение нужного размера (обычно черного цвета) 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

CS MSU Graphics & Media Lab (Video Group) Декомпрессия: Шаг 1

CS MSU Graphics & Media Lab (Video Group) Декомпрессия: Шаг 2

CS MSU Graphics & Media Lab (Video Group) Декомпрессия: Шаг 3

CS MSU Graphics & Media Lab (Video Group) Декомпрессия: Шаг 4

CS MSU Graphics & Media Lab (Video Group) Декомпрессия: Шаг 5

CS MSU Graphics & Media Lab (Video Group) Примеры восстановления

CS MSU Graphics & Media Lab (Video Group) Пример восстановления Исходное изображение Первый шаг восстановления

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

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

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

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) JPEG 2000 / DWT коэффициенты коэффициенты 9/7 DWT при сжатии с потерями Коэффициенты при упаковке iНизкочастотные коэффициенты h L (i) Высокочастотные коэффициенты h H (i) ± ± ± ± Другие i00

CS MSU Graphics & Media Lab (Video Group) JPEG 2000 / DWT коэффициенты (без потерь) Коэффициенты 5/3 DWT при сжатии без потерь При упаковкеПри распаковке iНизкочастотн ые коэффициент ы h L (i) Высокочаст отные коэффициен ты h H (i) Низкочастотн ые коэффициент ы g L (i) Высокочаст отные коэффициен ты g H (i) 06/ /8-1/21/2-2/8 2 -1/800

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) JPEGJPEG-2000 Структура разбиенияпространственнаячастотная Проход по коэффициентам частотныйпространственный Кодирование коэффициентов групповое кодирование не нулевых проходы по соответствующим битам коэффициентов Сравнение этапа сжатия без потерь JPEG и JPEG-2000

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

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

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

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

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

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

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) JPEG / JPEG-2000: Лена Сравнение JPEG & JPEG-2000 при сжатии в 30 раз

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

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

CS MSU Graphics & Media Lab (Video Group) Сравнение алгоритмов (1)

CS MSU Graphics & Media Lab (Video Group) Сравнение алгоритмов (2)

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

CS MSU Graphics & Media Lab (Video Group) Компрессия текстур: Специфика Требования: Прямой доступ к пикселям (текселям) из сжатого представления Эффективность аппаратной реализация Распространенный подход: Блочная компрессия с локальной палитризацией Фиксированный коэффициент сжатия

CS MSU Graphics & Media Lab (Video Group) Компрессия текстур: Алгоритм S3TC* Идея: Четыре цвета на блок 4х4, но хранения только двух базовых, остальные линейно интерполируются Преимущества: u Шесть раз сжатие; достаточное качество; простой для аппаратной реализации алгоритм; стандарт де-факто u Хранении базовых цветов в 16 битном формате, но возможно использование всех 16 млн *) SONICblue (originally S3 Inc.)

CS MSU Graphics & Media Lab (Video Group) Компрессия текстур: Алгоритм S3TC*

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

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

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

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

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

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

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

CS MSU Graphics & Media Lab (Video Group) 4 кластера, 8/16 цветов в палитре, 4 цвета на текстель 2-х кратное сжатие цветов палитры 1.5/2 кратное сжатие индексов палитры Метод CTF-8: 8-кратное сжатие

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

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

CS MSU Graphics & Media Lab (Video Group) Геометрия палитр и разбиение на кластеры Исходный блок Компрессия текстур: Форматы CTF-8, CTF-12 CTF-12: CTF-8:

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

CS MSU Graphics & Media Lab (Video Group) Алгоритм декомпрессии для CTF-12 Компрессированный блок 128 bit 32b Палитра 8b Номер подразбиения блока Plane[8][8]x1b Битовая плоскость Ind[4][2] x 3b Локальная палитра Декодирование 8-цветовой палитры Библиотека разбиений PartLib[256][8][8]x2b PartDsp Выбранная [8][8]x2b палитра Pal[8]x24b Полно-цветная палитра Генерация текстелей на основе вложенной индексации Bitmap[x][y] = Pal[ Ind[ PartDsp[x][y] ] [ Plane[x][y]] ] Декомпрессированный блок 8x8x24b = 1536 bit

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

CS MSU Graphics & Media Lab (Video Group) Граничный эффект Исходный JPEG (12раз) CTF-12 (12раз) S3TC (6раз)

CS MSU Graphics & Media Lab (Video Group) /1.5 Степень компресси и индексов /6 Степень компрес- сии палитры b16/8 8 CTF Степень компрес- сии b4 S3TC RED ( % ) GREEN b8 CTF-12 Коли- чество цветов на блок LUV-метрика на PortraitПараметры Размер палитры MAXLUV MAXRGB BLACK PSNR Сравнение S3TC с CTFs по объективным метрикам

CS MSU Graphics & Media Lab (Video Group) Тестовое изображение Source S3TCCTF-12

CS MSU Graphics & Media Lab (Video Group) Эффективность работы кэша при реальном алгоритме рендеринга Хранение всех мип-мэпов Генерация мип-мэпов на лету Сжатые текстуры на шаре

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

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

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

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

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

CS MSU Graphics & Media Lab (Video Group)

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

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

CS MSU Graphics & Media Lab (Video Group) Задания u Задания по курсу расположены на странице курса: u Следующая тема - сжатие аудиоданных