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

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

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

08/19/2023
Сжатие изображений
Будут рассмотрены алгоритмы:
RLE
LZW
Хаффмана (CCITT G3)
JPEG
JPEG-2000
фрактальный алгоритм

08/19/2023
Типы изображений
Изображения
Растровые
Векторные
В

08/19/2023
Типы изображений
Векторные
Растровые
Палитровые
Безпалитровые
В системе цветопредставления
RGB, CMYK, …
В градациях серого

08/19/2023
Восприятие цвета
Чувствительность
400 нм
500 нм
600 нм
700 нм

08/19/2023
Пространство RGB
RGB (Red, Green, Blue)

08/19/2023
Пространство CMYK
CMYK (Cyan, Magenta, Yellow, blacK).

08/19/2023
Расчет 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.

08/19/2023
Пространство HSV
Модель HSV (Hue, Saturation, Value). Построена на основе субъективного восприятия цвета человеком.

08/19/2023
Модель 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

08/19/2023
Модель 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

08/19/2023
Модель 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)

08/19/2023
Классы изображений
Класс 1. Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Плавные переходы цветов отсутствуют. Примеры: деловая графика — гистограммы, диаграммы, графики и т.п.
Класс 2. Изображения, с плавными переходами цветов, построенные на компьютере. Примеры: графика презентаций, эскизные модели в САПР, изображения, построенные по методу Гуро.
Класс 3. Фотореалистичные изображения. Пример: отсканированные фотографии.
Класс 4. Фотореалистичные изображения с наложением деловой графики. Пример: реклама.

08/19/2023
Требования приложений к алгоритмам
Высокая степень компрессии
Высокое качество изображений
Высокая скорость компрессии
Высокая скорость декомпрессии
Масштабирование изображений
Возможность показать огрубленное изображение (низкого разрешения)
Устойчивость к ошибкам
Учет специфики изображения
Редактируемость
Небольшая стоимость аппаратной реализации. Эффективность программной реализации

08/19/2023
Критерии сравнения алгоритмов
Невозможно составить универсальное сравнительное описание известных алгоритмов.
Худший, средний и лучший коэффициенты сжатия.
Класс изображений
Симметричность
Есть ли потери качества?
Характерные особенности алгоритма

08/19/2023
Алгоритм RLE
Данный алгоритм необычайно прост в реализации. Групповое кодирование — от английского Run Length Encoding (RLE). Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

08/19/2023
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());

08/19/2023
RLE – Первый вариант (схема)

08/19/2023
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());

08/19/2023
RLE – Схемы вариантов

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

08/19/2023
Алгоритм LZW
Название алгоритм получил по первым буквам фамилий его разработчиков — Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт.

08/19/2023
Схема алгоритма LZ

08/19/2023
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);

08/19/2023
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>.

08/19/2023
LZW / Добавление строк

08/19/2023
Таблица состоит из 4096 строк.
256 и 257 являются служебными.
258 … 4095 содержат непосредственно сжимаемую информацию.
Таблица для LZW

08/19/2023
Кол-во считываемых байт:
Пример – цепочка нулей
Общее число считанных байт:
Информация заносится в стр.:
1
1
-

08/19/2023
Степень сжатия цепочки нулей
Рассчитываем арифметическую
прогрессию:

08/19/2023
Наихудший случай
’13’
’21’
Последовательность :
121314151617…
Мы видим, что у нас нет одинаковых цепочек даже из 2 символов => сжатия не происходит.

08/19/2023
Степень сжатия
наихудшего случая
’13’
’21’
Происходит увеличение файла в 1.5 раза. Т.к. мы ни разу не встретили подстроку, которая уже есть в таблице.

08/19/2023
..
1
13
2
45
0
0
2
3
7
76
9
32
Таблица дерево

08/19/2023
Пример
Последовательность: 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>.

08/19/2023
Пример
Последовательность:
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’

08/19/2023
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 / Декомпрессия

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

08/19/2023
Алгоритм Хаффмана
Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины. Для сбора статистики требует двух проходов по изображению.

08/19/2023
Алгоритм Хаффмана-2

08/19/2023
Алгоритм Хаффмана-3
Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты).
Класс изображений: Практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах.
Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).
Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

08/19/2023
CCITT Group 3
Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.

08/19/2023
Примеры факсов

08/19/2023
Алгоритм CCITT G3
Последовательности подряд идущих черных и белых точек заменяются числом, равным их количеству.
Этот ряд сжимается по Хаффману с фиксированной таблицей.
Каждая строка сжимается независимо, если строка начинается с черной точки, то считаем, что она начинается белой серией длиной 0.Например, последовательность длин серий 0, 3, 556,10,.. означает, что в строке идут сначала 3 черных, 556 белых, 10 черных точек и т.д.

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

08/19/2023
В терминах регулярных выражений для каждой строки изображения выходной битовый поток вида:
((<Б-2560>)*[<Б-сст.>]<Б-зв>(<Ч-2560>)*[<Ч-сст>]<Ч-зв>)+[(<Б-2560>)*[<Б-сст.>]<Б-зв.>],где:
()* - повтор 0 или более раз, ()+ - повтор 1 или более раз, [] – включение 1 или 0 раз.
Для примера 0, 3, 556, 10,… ,будет сформирован
код: <Б-0><Ч-3><Б-512><Б-44><Ч-10> или
Согласно таблице:
00110101 10011001 01001011 010000100
Для приведенной строки в 569 бит полусен код длиной в 33 бита, т.е. Коэфф сжатия – 17 раз
Пример работы алгоритма

08/19/2023
Таблица кодов завершения

08/19/2023
Проблемы при сжатии
Пример, когда часть страницы идет под косым углом + разворот книги темный

08/19/2023
Проблемы при сжатии
Пример факса (часть текста рекомендаций стандарта CCITT) на японском (?) языке.

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

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

08/19/2023
Качество изображений
Не существует метода оценки качества изображения, полностью адекватного человеческому восприятию

08/19/2023
PSNR
Базовые метрики –
Y-PSNR, U-PSNR, V-PSNR
Хорошо работают только на высоком качестве.

08/19/2023
Как интерпретировать PSNR
Разные размеры кадров для разных алгоритмов
Преимущество для синей линии
Линия одинакового качества
Чем выше, тем лучше

08/19/2023
Тестовое изображение «Барбара»
Много полосок (высоких частот) в разных направлениях и разной толщины

08/19/2023
Тестовое изображение «Boat»
Много тонких деталей и наклонных границ в разном направлении

08/19/2023
Задача тестовых наборов
Основные задачи тестовых наборов
Обеспечить единую базу сравнения разных алгоритмов (в статьях и т.п.)
Обеспечить выявление разных типов артефактов в алгоритмах

08/19/2023
Алгоритм JPEG
Алгоритм разработан в 1991 году группой экспертов в области фотографии (JPEG — Joint Photographic Expert Group — подразделение в рамках ISO) специально для сжатия 24-битных изображений.
Алгоритм основан на дискретном косинусном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов.

08/19/2023
Алгоритм JPEG /
RGB в YUV
Изначально при сжатии изображение переводится в цветовое пространство YUV. Упрощенно перевод можно представить с помощью матрицы перехода:

08/19/2023
Алгоритм JPEG

08/19/2023
Алгоритм JPEG / Примеры DCT

08/19/2023
Алгоритм JPEG / Примеры DCT

08/19/2023
Алгоритм JPEG / Характеристики
Коэффициенты компрессии: 2-100 (Задается пользователем).
Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии).
Симметричность: 1
Характерные особенности: В некоторых случаях, алгоритм создает “ореол” вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселов.

08/19/2023
Фрактальная компрессия — алгоритм с потерей информации, появившийся в 1992 году
Он использует аффинные преобразования для построения изображений, что позволяет очень компактно задавать сложные структуры.
Фрактальное сжатие

08/19/2023
Пример самоподобия
Папоротник Барнсли
Состоит задается четырьмя
аффинными преобразованиями
Изображение имеет четыре области,
каждая из которых подобна
изображению, и их объединение
покрывает все изображение.
(Стебель, Листья.)

08/19/2023
Идея фрактального алгоритма
Сжатие осуществляется за счет поиска самоподобных участков в изображении

08/19/2023
Идея фрактального алгоритма
Для перевода участков один в другой используется аффинное преобразование

08/19/2023
Аффинное преобразование
Определение. Преобразование , представимое в виде
где a, b, c, d, e, f действительные числа и называется двумерным аффинным преобразованием.
Определение. Преобразование , представимое в виде
где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и называется трехмерным аффинным преобразованием.

08/19/2023
Аттрактор и теорема о сжимающем преобразовании
Определение. Пусть — преобразование в пространстве Х. Точка такая, что называется неподвижной точкой (аттрактором) преобразования.
Определение. Преобразование в метрическом пространстве (Х, d) называется сжимающим, если существует число s: , такое, что
Теорема. (О сжимающем преобразовании)
Пусть — сжимающее преобразование в полном метрическом пространстве (Х, d). Тогда существует в точности одна неподвижная точка этого преобразования, и для любой точки последовательность сходится к .

08/19/2023
Изображение и IFS
Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или
Определение. Конечная совокупность W сжимающих трехмерных аффинных преобразований , определенных на областях, таких, что и , называется системой итерируемых функций (IFS).

08/19/2023
Мы записываем в файл коэффициенты
Если размер коэффициентов меньше размера исходного файла, мы получаем алгоритм сжатия
Существенный недостаток — большое время сжатия. Т.е. на сжатие рисунка уходят часы на мощных компьютерах.
Идея фрактального алгоритма

08/19/2023
Поиск соответствий

08/19/2023
Декомпрессор
Читаем из файла коэффициенты всех блоков,
и создаем изображение нужного размера
(обычно черного цвета)
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

08/19/2023
Декомпрессия: Шаг 1

08/19/2023
Декомпрессия: Шаг 2

08/19/2023
Декомпрессия: Шаг 3

08/19/2023
Декомпрессия: Шаг 4

08/19/2023
Декомпрессия: Шаг 5

08/19/2023
Примеры восстановления

08/19/2023
Пример восстановления
Исходное изображение Первый шаг восстановления

08/19/2023
Фрактальное сжатие / Характеристики
Коэффициенты компрессии: От 2 до 100 раз.
Класс изображений: 24-битные и 8-битные grayscale изображения.
Симметричность: Существенно несимметричен. Коэффициент несимметричности достигает 10000.

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

08/19/2023
JPEG 2000
Алгоритм JPEG 2000 разработан той же группой экспертов в области фотографии, что и JPEG. Формирование JPEG как международного стандарта было закончено в 1992 году. В 1997 стало ясно, что необходим новый, более гибкий и мощный стандарт, который и был доработан к зиме 2000 года.

08/19/2023
JPEG 2000 /
Идея алгоритма
Базовая схема JPEG-2000 очень похожа на базовую схему JPEG. Отличия заключаются в следующем:
Вместо дискретного косинусного преобразования (DCT) используется дискретное вэйвлет-преобразование (DWT).
Вместо кодирования по Хаффману используется арифметическое сжатие.
В алгоритм изначально заложено управление качеством областей изображения.
Не используется уменьшение разрешения цветоразностных компонент U и V.
Кодирование с явным заданием требуемого размера на ряду с традиционным метод кодирования по качеству.
Поддержка сжатия без потерь. Поддержка сжатия однобитных (2-цветных) изображений
На уровне формата поддерживается прозрачность.

08/19/2023
JPEG 2000 / Схема
Конвейер операций, используемый в JPEG-2000

08/19/2023
JPEG 2000 / RGB в YUV
Этот шаг аналогичен JPEG (см. матрицы преобразования в описании JPEG), за тем исключением, что кроме преобразования с потерями предусмотрено также и преобразование без потерь.

08/19/2023
JPEG 2000 / DWT
В одномерном случае применение DWT – это «обычная фильтрация».
Из строки x мы получаем строку y по приведенным формулам.
В двумерном случае мы сначала применяем эти формулы по всем строкам изображения, а потом по всем столбцам.

08/19/2023
JPEG 2000 /
DWT коэффициенты
коэффициенты ‘9/7’ DWT при сжатии с потерями

08/19/2023
JPEG 2000 /
DWT коэффициенты (без потерь)
Коэффициенты ‘5/3’ DWT при сжатии без потерь

08/19/2023
JPEG 2000 /
DWT без потерь
Поскольку большинство hL(i), кроме окрестности i=0, равны 0, то можно переписать приведенные формулы короче:
А потом еще и упросить, как:

08/19/2023
JPEG 2000 / DWT – края
Симметричное расширение изображения
(яркости АБ…Е) по строке вправо и влево
Применение DWT на краях изображения:

08/19/2023
JPEG 2000 /
DWT – Пример
Пусть мы преобразуем строку из 10 пикселов. Расширим ее значения вправо и влево и применим DWT преобразование:
Получившаяся строка 1, 0, 3, 1, 11, 4, 13, -2, 8, -5 полностью и однозначно задает исходные данные. Обратное преобразование осуществляется по:

08/19/2023
JPEG 2000 /
Изменение качества областей
Когда практически достигнут предел сжатия изображения в целом и различные методы дают очень небольшой выигрыш, мы можем существенно (в разы) увеличить степень сжатия за счет изменения качества разных участков изображения.

08/19/2023
Сравнение этапа сжатия без потерь JPEG и JPEG-2000

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

08/19/2023
JPEG-2000 / Кодирование битовых плоскостей
Для каждого прохода используется бинарное адаптивное арифметическое кодирование и контекстное моделирование:
Арифметическое кодирование позволяет кодировать символы с произвольным распределением вероятности (не только равных степени двойки как у таблиц Хаффмана)
Адаптивность позволяет задавать распределение вероятностей исходя из статистики уже закодированных данных
Контекстное моделирование позволяет использовать закономерности между и внутри потоков данных, путем использования различных вероятностных таблиц для разных ‘контекстов’

08/19/2023
JPEG-2000 / Кодирование битовых плоскостей
Кодирование старших бит
Кодирование предсказанных и при подтверждении гипотезы, кодирование знака
Контекст при кодирования значимости:
значимость соседних 8-ми связанных коэффициентов
Тип бэнда: LL,LH,HL,HH
Контекст при кодирования знака:
Значимость и знаки 4-х связанных коэффициентов
4-х и 8-ми
связность

08/19/2023
JPEG-2000 / Кодирование битовых плоскостей
Уточняющий проход:
Кодирование существенных битов расположенных ниже первого
Контекст для бита:
‘Это второй по важности бит?’
Значимость 8-ми связанных коэффицентов
Очищающий проход:
Кодирование не предсказанных, но
существенных битов
Порядок обхода

08/19/2023
JPEG-2000 /
Кодирование: Внешний цикл
Цель: записать в поток результаты кодирования битовых плоскостей
Единица потока – пакет. Пакет – компрессированный проход одной битовой плоскости одного блока
Сортировка пакетов в соответствии с выбранной стратегией:
Слой-разрешение-компонента-позиция: возможность прогрессивной визуализации
Разрешение-слой-компонента-позиция: прогрессивная восстановление по разрешению
Другие три сценария

08/19/2023
JPEG-2000 /
Изменение качества областей
В JPEG-2000 используется неявное представление бинарной маски, внутри которой точность квантования коэффициентов другая нежели вне её. Метод представления и компрессии маски будет описан позже.

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

08/19/2023
JPEG-2000 / Пресеты квантования
Адаптированный пресет,
лучше качество
Стандартный пресет,
больше PSNR

08/19/2023
JPEG 2000 /
Отличия от JPEG
Лучшее качество изображения при сильной степени сжатия.
Поддержка кодирования отдельных областей с лучшим качеством.
DCT преобразование заменено на DWT (плавное проявление изображения теперь изначально заложено в стандарт) Для повышения степени сжатия в алгоритме используется арифметическое сжатие.
Кодирование с явным заданием требуемого размера на ряду с традиционным метод кодирования по качеству
Поддержка сжатия без потерь (становится возможным использование JPEG для сжатия медицинских изображений, в полиграфии, при сохранении текста под распознавание OCR) Поддержка сжатия однобитных (2-цветных) изображений.
На уровне формата поддерживается прозрачность.

08/19/2023
JPEG 2000 /
Отличия от JPEG (2)
на уровне формата поддерживаются включение в изображение информации о копирайте
поддержка устойчивости к битовым ошибкам при передаче и широковещании

08/19/2023
JPEG / JPEG-2000: ‘Лена’
Сравнение JPEG & JPEG-2000 при сжатии в 30 раз

08/19/2023
JPEG / JPEG-2000:
Сжатие в 130 раз
JPEG: сохранено больше деталей JPEG-2000: отсутствие блочных артефактов

08/19/2023
Алгоритм JPEG-2000 / Характеристики
Коэффициенты компрессии: 2-200 (Задается пользователем), возможно сжатие без потерь.
Класс изображений: Полноцветные 24-битные изображения, изображения в градациях серого, 1-битные изображения (JPEG-2000 - наиболее универсален).
Симметричность: 1
Характерные особенности: Можно задавать качество участков изображений.

08/19/2023
Сравнение алгоритмов (1)

08/19/2023
Сравнение алгоритмов (2)

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

08/19/2023
Компрессия текстур:
Специфика
Требования:
Прямой доступ к пикселям (текселям) из сжатого представления
Эффективность аппаратной реализация
Распространенный подход:
Блочная компрессия с локальной палитризацией
Фиксированный коэффициент сжатия

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

08/19/2023
Компрессия текстур:
Алгоритм S3TC*

08/19/2023
Компрессия текстур:
Формат 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.

08/19/2023
Компрессия текстур:
Оценка формата FXT1*
Плюсы
Большая степень компрессии чем у S3TC при компрессии 32-битовых изображений (8 против 6)
Минусы
На порядок большее время компрессии
Не приемлемое качества, особенно для градиентных участков
Не поддерживается большинством производителей
*)3dfx Iterative Inc.

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

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

08/19/2023
Компрессия текстур:
Форматы CTF-8, CTF-12
Плюсы (vs S3TC):
CTF-8 лучше по качеству (в среднем на 1-2 дБ) и имеет более высокую степень компрессии (8 vs. 6)
CTF-12 в 2 раза больше степень сжатия при приемлемом визуальном качестве
Минусы
Медленный алгоритм компрессии (более чем на 2 порядка медленнее S3TC)
Нет поддержки прозрачности

08/19/2023
24 бита
8 пикселей
Индексы:
Палитра:
8 цветов на блок 8х8, сжатие в 4.8 раза при достаточном качестве
Исходный метод:
простой и качественный

08/19/2023
Увеличение сжатие при сопоставимом качестве
Базовые идеи:
Сжатие индексов палитры (с потерями):
Разбиение блока на 4 кластера, и использование меньших палитр для каждого из них
Сжатие цветов палитры (с потерями):
Хранение только базовых цветов и аппроксимация остальных

08/19/2023
4 кластера, 8/16 цветов в палитре, 4 цвета на текстель
Метод CTF-8:
8-кратное сжатие

08/19/2023
2-х кратное сжатие цветов палитры
3 кратное сжатие индексов палитры
Метод CTF-8:
12-кратное сжатие
4 кластера, 8 цветов в палитре, 2 цвета на текстель

08/19/2023
Палитризация и кластеризация
Source block
Local pallete
CTF8:
16 color pallete
4 color in cluster
CTF12:
8 color pallete
2 color in cluster

08/19/2023
Компрессия текстур:
Форматы CTF-8, CTF-12
CTF-12:
CTF-8:

08/19/2023
CTF-12: Два типа палитр
Используется в однородных блока и во всех не цветных блоках
Аппроксимация палитры – отрезок в пространстве между двумя базовым и цветами
Хранятся уточняющие биты до формата RGB-565
Используется в блоках с резкими границами и в блоках с существенно разными хроматическими компонентами
Аппроксимация палитры - 2 параллельных отрезка
Цветовой формат отрезка – RGBY-4534
В палитре хранятся 2 базовых цвета C1 и С2, в формате RGB-453, в зависимости от “C1

08/19/2023
Алгоритм декомпрессии для CTF-12

08/19/2023
Блочный эффект и цветовое распределение
Исходный блок
(12х12)
CTF-8
(блоки 8х8)
CTF-12 (блоки 8х8)
S3TC
(блоки 4х4)

08/19/2023
Граничный эффект
Исходный
JPEG
(12раз)
CTF-12
(12раз)
S3TC
(6раз)

08/19/2023
Сравнение S3TC с CTFs по объективным метрикам

08/19/2023
Тестовое изображение
Source
S3TC
CTF-12

08/19/2023
Эффективность работы кэша при реальном алгоритме рендеринга
Хранение
всех
мип-мэпов
Генерация
мип-мэпов
‘на лету’
Сжатые
текстуры
на шаре

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

08/19/2023
Типы генерации текстур
Процедурные текстуры:
Алгоритмическая генерация текстур
Для каждой физической модели свой алгоритм
Генерация мип-мэпов:
Универсальный алгоритм, не зависит от типа текстуры
Дополняет алгоритм компрессии текстур
Проблема: памяти акселератора всегда мало, даже если компрессировать текстуры
Выход: не хранить, а генерировать самые детализированные мип-мэпы уровни

08/19/2023
Генерация мип-мэпов
Требования:
Реалистичность в не зависимости от типа и разрешения текстуры
Высокая скорость и возможность аппаратной реализации
Подход: вероятностная генерация
Метод№1: фрактально-каскадная генерация с вероятностно-распределенным локальным коэффициентом подобия масштабных уровней
Метод№2: генерация с вероятностным законом положения и расположения шаблонов

08/19/2023
A = α B +β,
α= N(0,σ), β= N(0,σ')
После 8 итераций
Рекурсивное
фрактально-каскадное подразбиение
Фрактально-каскадный метод генерации

08/19/2023
Фрактально-каскадный
метод генерации
Увеличение
без применения
генерации
С генерацией
3-х дополнительных
мип-мэпов

08/19/2023
Примеры

08/19/2023
Многомасштабная генерация с использованием шаблонов
Многомасштабные
Шаблоны
Различные уровни детализации
сгенерированных текстур

08/19/2023
4n операций/текстель (n – количество масштабных уровней)
Многомасштабная генерация с использованием шаблонов