Сжатие

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

По применению сжатие графических данных можно условно разделить на: Сжатие всего файла с графикой. Недостаток - новый файл нельзя использовать без предварительного восстановления. Сжатие, включенное в структуру файла. Многие (почти все) графические форматы файлов используют внутреннее сжатие данных. Применение методов сжатия

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

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

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

Классы изображений Класс 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 Худший, средний, лучший коэффициенты сжатия: 1000 – 4 – 0.7 Класс изображений: 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 и 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)