1 Сжатие изображений (введение) Дмитрий Ватолин Московский Государственный Университет CS MSU Graphics&Media Lab Version 3.3 Лекция 14 12 мая 2006. - презентация

1

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

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

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

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

6 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)

7 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)

8 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)

9 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

10 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

11 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

12 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)

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

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

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

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

17 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());

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

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

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

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

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

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

24 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);

25 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. В поток: ; Последовательность кодов для данного примера, попадающих в выходной поток:,,,,,.

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

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

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

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

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

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

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

33 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. В поток: Итого в потоке:,,,,,.

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

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

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

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

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

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

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

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

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

43 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 { // аналогично для черных серий...}

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

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

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

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

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