Алгоритмы сжатия изображений

Сжатие – представление информации в более эффективном виде, влекущее за собой уменьшение объема данных (как правило). В основном алгоритмы сжатия используют свойства графических данных: избыточность – группы одинаковых символов; предсказуемость – часто повторяющиеся одинаковые комбинации символов; необязательность – данные, мало влияющие на человеческое восприятие (цвет).

Классификация методов сжатия Сжатие без потерь кодирование информации меньшим числом битов без ее искажения Сжатие с потерями кодирование информации с потерей той ее части, которая несущественна для представления данных применимо не для любых данных

Оценки методов сжатия Степень сжатия Качество сжатия Скорость сжатия, в том числе отдельно компрессия и декомпрессия изображения Симметричность (по времени) Возможность масштабирования Устойчивость к ошибкам Учет специфики изображения Стоимость аппаратной реализации или/и эффективность программной реализации

Критерии сравнения различных методов сжатия Худший, средний, лучший коэффициенты сжатия Класс изображений Симметричность Потери качества Особенности алгоритма

Классы изображений Класс 1. Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Плавные переходы цвета отсутствуют. (деловая графика – гистограммы, диаграммы, графики) Класс 2. Изображения с плавными переходами цветов, построенные на компьютере (графика презентаций, САПР, векторные изображения 3d объектов) Класс 3. Фотореалистичные изображения.(Цифровые или отсканированные фотографии) Класс 4. Фотореалистичные изображения с наложением деловой графики (реклама)

Сжатие без потерь RLE (Run Length Encoding) LZW (Lempel, Ziv, Welch) Метод Хаффмана (Huffman)

Алгоритм группового кодирования RLE Изображение вытягивается в цепочку байт по строкам растра. Серия повторяющихся величин (значений пиксела) заменяется одной величиной и количеством ее повторений. Abbbbbbbccdddeeee – 1a7b2c3d4e Этот подход хорошо работает с длинными сериями повторяющихся величин, т.е. с изображениями с большими областями постоянной яркости (или цвета). Используется во многих форматах bitmap файлов – TIFF, GEM, PCX и других. Возможные проблемы могут быть связаны с порядком записи величины и количества повторений: 1a7b2c3d4e или a1b7c2d3e4.

Характеристики RLE Худший, средний, лучший коэффициенты сжатия: 32 – 2 – 0.5 Класс изображений: небольшое количество цветов (деловая и научная графика) Симметричность: 1 Особенности алгоритма: не требует дополнительной памяти при архивации и разархивации, быстро работает.

Алгоритм LZW Метод назван по первым буквам фамилий его разработчиков: Lempel, Ziv, Welch. Сжатие осуществлянтся за счет одинаковых цепочек байт (шаблонов). Алгоритм создает таблицу кодов, представляющих повторяющиеся пиксельные «узоры», начиная с простой таблицы и формирует более эффективную таблицу по мере своего продвижения – этот алгоритм является адаптивным. Включен в несколько форматов файлов: GIF, TIFF (с правом выбора). (словарный алгоритм)

Пример работы алгоритма LZW кукушкакукушонкукупилакапюшон

Характеристики LZW Худший, средний, лучший коэффициенты сжатия:0.7 – 4 –1000 Класс изображений: 8-битные изображения, построенные на компьютере. Симметричность: 1, при оптимальном построении.

Алгоритм Хаффмана Использует частоту появления исходных байт в изображении. При этом более короткие коды используются для часто повторяющихся величин, и наоборот. Присвоения хранятся в таблице перекодировки. Требует двух проходов по изображению. В первый проход создается статистическая модель, т.е. каждой величине ставится в соответствие число ее повторений; во второй проход – кодируются данные. Для кодировки используются алгоритмы построения бинарных деревьев.

Характеристики алгоритма Хаффмана Худший, средний, лучший коэффициенты сжатия: 8 – 1.5 – 1 (единственный алгоритм, который не увеличивает размер исходных данных в худшем случае, не считая хранения таблицы перекодировки) Класс изображений: практически не применяется непосредственно к изображениям, обычно используется как один из этапов компрессии по более сложной схеме, например, в JPEG Симметричность: 2 (за счет необходимости двух проходов)

Сжатие с потерями JPEG JPEG 2000 (Wavelet) Фрактальное сжатие

Оценка потерь качества Базовая метрика оценки качества сжатия – PSNR (peak-to-peak signal-to-noise ratio) Хорошо работает только на высоком качестве.

Алгоритм JPEG Разработан в 1991 г. группой экспертов в области фотографии (Joint Photographic Expert Group – подразделение в рамках ISO) специально для сжатия 24-битных изображений. Основу алгоритма составляет дискретное косинусное преобразование Фурье (DCT) Оперирует блоками 8 х 8, внутри которых яркость и цвет меняются сравнительно плавно.

1. RGB YUV Пересчет изображения в пространство Яркость-Цвет

2. Прореживание Изображение разбивается на прямоугольники 8 х 8 пикселов. Данные о цвете подвергаются прореживанию (как правило). Например, для каждых 4 значений Y берут по 1 значению U и V, что уже сокращает объем данных на 50% практически без потерь качества восприятия. Параметры прореживания зависят от требуемой степени сжатия и качества восстановленного изображения.

3. DCT (discrete cosine transform) DCT превращает исходные данные в частоты, содержащие информацию о том, насколько быстро меняются яркость и цвет пикселов. DCT раздельно применяется к цвету и яркости для прямоугольников 8 х 8 с нумерацией от (0,0) в левом верхнем углу (низкие частоты) до (7,7) в правом нижнем (высокие частоты). Плавные изменения цвета соответствуют низкочастотной составляющей, резкие скачки – высокочастотной.

Формула DCT :

4. Квантование Квантование устанавливает точность, с которой будет храниться каждая из величин. Каждое из значений DCT делится на фактор квантования и округляется до целого, при этом используется таблица факторов квантования 8 х 8.

В общем случае таблицы для Y и для U и V различны. Данные низкой частоты F(0,0) (без изменений) оказываются более важными, чем данные высокой частоты F(7,7). В соответствии с этим типичные таблицы имеют низкий фактор для F(0,0) – от 1 до 16 и высокий для F(7,7) – около 100. При декодировании исходные величины умножают на факторы квантования. Например, значения DCT от 120 до 135 и фактор 16 дают на выходе 8, а после восстановления преобразуются в 8 * 16 = 128 – аппроксимация входного значения.

5. Вытягивание в цепочку Высокочастотные компоненты после квантования, как правило, обращаются в ноль. Полученные значения вытягиваются в цепочку в зигзагообразном порядке, в начале компоненты самой низкой частоты: F(0,0) – F(0,1) – F(1,0) - … - F(6,7) – F(7,6) – F(7,7)

6. Свертывание и кодирование Свертывание полученного на предыдущем этапе вектора с помощью группового кодирования. В результате образуются пары типа (пропустить, число), где пропустить – счетчик пропускаемых нулей, число – значение, которое необходимо поставить в следующую ячейку. Например: вектор ( ) … будет свернут в пары (0,42) (0,3) (3,-2) (4,1) … Кодирование данных методом Хаффмана

Достоинства и недостатки JPEG Наилучшее сжатие для фотоизображений ввиду отсутствия там резких линий (букв) и больших областей однотонной окраски. Стандарт де-факто для хранения, обработки и передачи фотоизображений. Регулируемая степень сжатия. Резкие линии после обработки по алгоритму JPEG выглядят слегка размытыми, а в однотонной окраске появляются переливы (муар). При больших степенях сжатия возникает эффект блочности. Довольно медленная программная обработка. Существование несовместимых реализаций из-за необязательных дополнений в стандарте.

Характеристики алгоритма JPEG Степень сжатия: (задается пользователем) Класс изображений: полноцветные 24-битные изображения или изображения в градациях серого без резких переходов цветов (фотографии) Симметричность: 1 Характерные особенности: эффект блочности при высоких степенях сжатия и «ореолы» вокруг резких вертикальных и горизонтальных границ.

ПримерJPEG Фотография заката в формате JPEG с уменьшением степени сжатия слева направо

Сравнение JPEG и JPEG2000 Большая степень сжатия при том же качестве для высоких степеней сжатия Поддержка кодирования отдельных областей с лучшим качеством DCT заменено на DWT (wavelet-преобразование), что позволило избежать блочности и достичь плавного проявления изображения Вместо кодирования по методу Хаффмана используется более эффективное арифметическое кодирование Поддержка сжатия без потерь Поддержка сжатия 1-битных изображений Поддержка прозрачности при помощи отдельного канала

JPEG и JPEG2000 при сжатии в 30 раз

Характеристики алгоритма JPEG2000 Степень сжатия: (задается пользователем). Возможно сжатие без потерь Класс изображений: полноцветные 24-битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). 1-битные изображения Симметричность: Характерные особенности: эффект блочности при очень высоких степенях сжатия. Позволяет повышать качество в отдельных областях.

Фрактальное сжатие изображений Фрактальное сжатие – алгоритм с потерей информации, появившийся в 1992 году. Одним из важных свойств фракталов является самоподобие – отдельные части фракталов по форме похожи на весь фрактал в целом. На этом самоподобии основан алгоритм фрактального сжатия изображений.

Один из способов построения фракталов – с помощью системы итеративных функций (Iterated Functions System – IFS). Он заключается в последовательном итеративном расчете координат новых точек в пространстве: xk+1 = a*xk + b*yk + e = Fх(xk, yk) yk+1 = c*xk + d*yk + f = Fу(xk, yk) Функции F – аффинное преобразование, определяющее форму фрактала. Требуется только определить коэффициенты a,b,c,d,e,f. Задание фракталов при помощи IFS

Алгоритм со студентом даем студенту изображение; даем студенту компьютер; запираем студента в комнате; ждем, пока студент найдет систему преобразований; выпускаем студента из комнаты.

Базовые понятия фрактального сжатия Пусть - множество всех возможных изображений. Пусть также существует преобразование W:. W является объединением преобразований w i : W(D) = w i (s i ), где D – изображение, а s i – какие-либо (возможно перекрывающиеся) области изображения D. Каждое преобразование w i переводит s i в d i. Таким образом, W(D) = d i. Изображение можно представить в виде функции от двух переменных f(x,y). На множестве всех таких функций введем метрику (расстояние между изображениями) следующим образом: (f,g) = max (| f(x,y) – g(x,y)|) x,y

Доказано, что существует определенный класс преобразований, для которых существует константа с

Схема компрессии изображение D разбивают на участки d i, называемые доменами (непересекающиеся области, покрывающие все изображение). для каждого домена находят ранговую область s i и преобразование w i такие, что выполняются условия: s i по размерам больше d i. w i (s i ) имеет ту же форму, размеры и положение, что и d i. значение (w i (s i ), d i ) должно быть как можно меньше. запоминают коэффициенты аффинных преобразований w i, положение ранговых областей s i и разбиение изображения на домены.

Схема декомпрессии создать какое-либо (любое!!!) начальное изображение D 0 ; многократно применить к нему преобразование W (объединение w i ); так как преобразование W сжимающее, то после достаточного количества итераций, изображение придет к аттрактору и перестанет меняться. Аттрактор и есть исходное изображение после декомпрессии.

Декомпрессия

Характеристики фрактального алгоритма Степень сжатия: Класс изображений: полноцветные 24-битные изображения или 8-битные изображения в градациях серого. Симметричность: Существенно несимметричен, с коэфиициентом, достигающим Характерные особенности: эффект блочности при очень высоких степенях сжатия. Позволяет повышать качество в отдельных областях

Форматы графических файлов BMP (DIB, Device Independent Bitmap) JPEG GIF (Graphics Interchange Format) TIFF (Tag Image File Format) EPS (Encapsulated PostScript) CGM (Computer Graphics Metafile) DXF (Drawing Interchange Format) PNG (Portable Network Graphics)

Продолжение

Цветовые модели компьютерной графики

Свет – это электромагнитное излучение Цвет – это действие излучения на глаз человека

излучаемый свет отраженный свет поглощение света

Ц В Е Т получается в процессе излучения описывается с помощью цветовых моделей отражения RGB, CMY(K), HSL и др.

Аддитивная модель англ. add – «присоединять» RED – красный GREEN – зеленый BLUE – синий Цвет получается в результате суммирования трех цветов. Основными цветами являются:

Аддитивный – при увеличении яркости отдельных цветов результирующий цвет становится ярче. В палитре RGB каждый из цветов может менять свою интенсивность от 0 до – интенсивность цвета минимальна 255 – интенсивность цвета максимальна

Цветовой куб RGB-кодирования

Красный ЗеленыйСиний Цвет 000Черный 25500Красный 02550Зеленый 00255Синий 0255 Бирюзовый 255 0Желтый 2550 Пурпурный 255 Белый Таблица цветов RGB

Субтрактивная модель Cyan – голубой Magenta – пурпурный Yellow – желтый англ. subtract – «вычитать» Каждый из них поглощает (вычитает) определенные цвета из белого света, падающего на печатаемую палитру. Основными цветами являются:

Субтрактивный - при увеличении яркости отдельных цветов результирующий цвет становится темнее. В палитре CMY каждый из цветов может менять свою интенсивность от 0 до – интенсивность цвета минимальна 255 – интенсивность цвета максимальна

Из-за особенностей типографских красок смесь трех цветов дает не черный, а грязно – коричневый цвет. Поэтому к основным цветам добавляют еще и черный. Cyan – голубой; Magenta – пурпурный; Yellow – желтый; Black – черный. СMYKСMYK

Цветовой куб СMYK-кодирования

Голубой (нет красного) Пурпурный (нет зеленого) Желтый (нет синего) Цвет 000Белый 00255Желтый 02550Пурпурный 25500Голубой 0255 Красный 2550 Зеленый 255 0Синий 255 Черный Таблица цветов СMYK

Отличие в воспроизведении цветов в моделях RGB и СMYK

Цветовая модель HSB Hue цветовой тон Saturation насыщенность Brightness яркость При работе в графических программах с помощью этой модели очень удобно подбирать цвет, так как представление в ней цвета согласуется с его восприятием человеком.

Цвет представляется как комбинация параметров цвета: тона, насыщенности и яркости. Тон имеет 360 уровней, а цвет и яркость по 100 уровней.

Круговое расположение цветов модели HSB

Цвет на web – страницах кодируется в RGB и записывается в шестнадцатеричной системе: #RRGGBB, - где RR, GG и BB – яркости красного, зеленого и синего, записанные в виде двух шестнадцатеричных цифр; это позволяет закодировать 256 значений от 0 (0016) до 255 (FF16) для каждой составляющей. Код Цвет #FFFFFFБелый #000000Черный #FF0000Красный #00FF00Зеленый #0000FFСиний #FFFF00Желтый #FF00FFФиолетовый #00FFFFГолубой

CIE Lab & Adobe RGB vs sRGB