Кодирование, классификация, методы сжатия (rle, Хаффман, jpeg).

Алгоритмы сжатия выбираются исходя из класса изображения.

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

Классы изображений:

1. изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом

2. изображения, с использованием плавных переходов, построенные на компьютере(САПР,презентации)

3. фотореалистичные изображения(скан)

4. фотореалистичные изображения с наложением деловой графики

5. некачественно отсканированные в 256 градаций серого цвета страницы журналов или растровые изображения топографических карт

Критерии оценки алгоритмов

1. Худший(доля, на которую возрастет размер изображения, если исходные данные будут наихудшими), средний(некий среднестатистический коэффициент для того класса изображений, на который ориентирован алгоритм) и лучший коэффициенты сжатия(показывает степень сжатия наилучшего (как правило, абсолютно черного) изображения)

2. Симметричность(ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важными являются два коэффициента: отношение времени кодирования ко времени декодирования и требования на память.)

3. Качество разжатия : Оч. Хороший(разницу между исходным и разжатым не отличить на глаз)

Хороший (исходное и разжатое можно отличить совместив их)

Методы сжатия растровой информации делятся на две большие группы: сжатие с потерями и сжатие без потерь. Методы сжатия без потерь дают более низкий коэффициент сжатия, но зато сохраняют точное значение пикселей исходного изображения. Методы с потерями дают более высокие коэффициенты сжатия, но не позволяют воспроизвести первоначальное изображение с точностью до пикселя.

Групповое кодирование - Run Length Encoding (RLE). Алгоритм сжатия без потерь.Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары "счетчик, значение" уменьшает избыточность данных. Лучший, средний и худший коэффициенты сжатия - 1/32, 1/2, 2/1. Он не требует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР.

LZW(Lempel-Ziv & Welch). Один из самых распространенных кодов сжатия без потерь. Используется в TIFF и GIF. Коэффициенты сжатия: 1/1000, 1/4, 7/5. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселей.

Алгоритм Хаффмана.

Используется на последнем этапе сжатия JPEG. Коэффициенты сжатия: 1/8, 2/3, 1.

Кодирование Хаффмана работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление - алфавит ASCII - использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.

Использует только частоту появления одинаковых байт в изображении, сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины, и напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требует двух проходов по изображению.

JPEG.

1) Прежде всего, программа делит изображение на блоки - матрицы размером 8х8 пикселей.

2) Схема YUV использует три компоненты, Y – яркость (может быть использована как чёрно – белое изображение), U – голубизна, V – краснота. Перевод из RGB осуществляется по схеме:

Y = 0.299R + 0.587G + 0.114B

U = 0.1687R - 0.3313G + 0.5B

V = 0.5R - 0.1187G + 0.0813B

Это преобразование, в принципе, не имеет потерь, но на практике вводится ошибка округления, обусловленная необходимостью округления результата до целого. Так как глаз человека более чувствителен к первой компоненте, чем к двум другим, то в JPEG допускает дискретизацию различных компонент с различной частотой. Наиболее общий случай – использование одной выборки U и V для четырёх выборок Y. Это позволяет сохранять лишь 50% используемого объёма при практически неизменном качестве изображения. Технология дискретизации, при которой некоторые компоненты оцифровываются с меньшей частотой, чем другие, называется поддескритизацией.

3) К значениям пикселей применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform - DCT). DCT переводит матрицу значений пикселей 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний - высоким.

Дискретное косинусоидальное преобразование (DCT) превращает массив данных интенсивности в массив данных частоты, который содержит информацию о том, как быстро изменяется интенсивность. В JPEG применяется DCT для квадратов 8*8 данных о пикселях для каждого компонента цвета. Точки в каждом блоке нумеруются от (0,0) в верхнем левом до (7,7) в нижнем правом углах. F(x,y) есть значение данных в точке (x,y). Создаётся новый блок по формуле:

Обратное преобразование имеет вид:

По физическому смыслу преобразование сводится к представлению изображения в виде суммы (ко)синусоидальных гармоник (волн). Значения F определяют амплитуды гармоник, u,v – их частоты. F(u,v) указывает на степень изменения величин для каждой из множества частот. Значение F(0,0) указывает что уровень значения не изменился, F(7,7) определяет наиболее быстрое изменение величины в обоих направлениях. Более высокие частоты “отвечают” за передачу более “тонких” деталей изображения.

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

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

Далее программа, двигаясь по матрице зигзагообразно, считывает элементы матрицы и кодирует их последовательно методами без потерь.