Фрактальный алгоритм

Алгоритм JPEG

Алгоритмы сжатия с потерями

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

Алгоритмы статистического кодирования

Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.

Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.

В целом алгоритм основан на дискретном косинусоидальном преобразовании – ДКП (Discrete-Cosine Transform – DCT), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

Существенными положительными сторонами алгоритма является то, что:

1. Задается степень сжатия.
2. Выходное цветное изображение может иметь 24 бита на точку.

Отрицательными сторонами алгоритма является то, что:

1. При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно.
2. Проявляется эффект Гиббса – ореолы по границам резких переходов цветов.

Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме – с помощью коэффициентов системы итерируемых функций (Iterated Function System – далее по тексту как IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований, в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

Сжатие на основе волнового (билиблет преобразование)

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

25. Дайте определение фрактала. Охарактеризуйте алгоритм фрактального сжатия.

Фракта́л (лат. fractus — дроблёный, сломанный, разбитый) —геометрическая фигура, обладающая свойством самоподобия, то есть составленная из нескольких частей, каждая из которых подобна всей фигуре целиком. Фрактальное сжатие изображений — алгоритм сжатия изображений c потерями. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры — до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (англ. range subimages) и определяется множество перекрывающихся доменных подизображений (англ. domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок.

Характеристики фрактального алгоритма:

Коэффициенты компрессии: 2-2000 (Задается пользователем).

Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). Желательно, чтобы области большей значимости (для восприятия) были более контрастными и резкими, а области меньшей значимости — неконтрастными и размытыми.

Симметричность: 100-100000

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

26. Охарактеризуйте алгоритм сжатия на основе волнового преобразования.

Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Идеален для картинок типа рентгеновских снимков. Коэффициент сжатия задается и варьируется в пределах 5-100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется “лестничный эффект” — ступеньки разной яркости размером в несколько пикселов. Идея алгоритма заключается в том, что мы сохраняем в файл разницу — число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0. Так два числа a _{2 i} и a _{2 i+1} всегда можно представить в виде b¹_i =(a _{2 i} + a _{2 i+1} )/2 и b²_i =(a _{2 i} - a _{2 i+1} )/2. Аналогично последовательность a_i может быть попарно переведена в последовательность b^1,2_i. Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл. Такое преобразования можно делать до 6 раз. Характеристики волнового алгоритма: Коэффициенты компрессии: 2-200 (Задается пользователем).

Класс изображений: Как у фрактального и JPEG.

Симметричность: ~1.5

Характерные особенности: Кроме того, при высокой степени сжатия изображение распадается на отдельные блоки.

27. Назовите основные файловые форматы растровых графических данных. Кратко характеризируйте их.

BMP, GIF, PNG, JPEG, TIFF

28. Назовите основные файловые форматы векторных графических данных. Кратко характеризируйте их.

(AI, XAR, SVG) - 2D, (STL, X3D, VRML) - 3D

29. Опишите внутреннюю структуру файла в формате ВМР.

Данные в формате BMP состоят из трёх основных блоков различного размера:

· Заголовок из структуры BITMAPFILEHEADER и блока BITMAPINFO. Последний содержит:

1. Информационные поля.

2. Битовые маски для извлечения значений цветовых каналов (опциональные).

3. Таблица цветов (опциональная).

· Цветовой профиль (опциональный).

· Пиксельные данные.

При хранении в файле все заголовки идут с самого первого байта. Пиксельные данные могут находиться на произвольной позиции в файле (она указывается в поле OffBits структуры BITMAPFILEHEADER), в том числе и в удалении от заголовков. Опциональный цветовой профиль появился в версии 5 и он так же может свободно располагаться, но его позиция указывается от начала BITMAPINFO (в поле ProfileData).

В данном формате можно хранить только однослойные растры. На каждый пиксель в разных файлах может приходить разное количество бит (глубина цвета). Microsoft предлагает битности 1, 2, 4, 8, 16, 24, 32, 48 и 64. В битностях 8 и ниже он указывается индексом из таблицы цветов (палитры), а при больших: непосредственным значением. Цвет же в любом случае можно задать только в цветовой модели RGB (как при непосредственном указании в пикселе, так и в таблице цветов), но в битностях 16 и 32 можно получить Grayscale с глубиной до 16 и 32-ух бит соотвественно. Частичная прозрачность реализована альфа-каналом различных битностей, но при этом прозрачность без градаций можно косвенно получить RLE-кодированием.

30.

Дата добавления: 2015-06-27