Кодирование по алгоритму Хаффмана.

Этот алгоритм разрабатывался для факсовых передач черно-белых изображений по телефонным каналам и сетям передачи данных. Этот алгоритм сжатия без потерь предложен был Дэвидом Хаффманом в 1952 г. В случае А4 степень сжатия от 5:1 до 8:1. Модификация алгоритма позволяет достичь степень сжатия 15:1.

Алгоритм не является форматом, а лишь включен в различные графические форматы. По алгоритму Хаффмана, сжимая файл, необходимо прочитать его полностью и посчитать сколько раз встречается каждый символ из набора ASCI кодов. После подсчёта частоты вхождения каждого символа формир-ся бинарное дерево по следующей схеме:

#имеется файл длиной в100 байт, имеющий 6 различных символов в себе.

C E B F A D -символ

30 25 20 10 10 5 -число

| |______| | |_____| вхождений

| | | 15

| 45 |_______|

| | 25

|__________|_______|

55 |

|___|

|

ROOT 100

Для построения дерева выбирается 2 символа с наименьшим числом вхождений: A или D. Формируют новый узел, частота входа для каждого = D+A=10+5=15. Если 2 символа имеют одинаковое число значений имеющего одинаковое числа, то из выбранных узлов формируется новый узел, частота вхождения которого = сумме частот входящих его элементов. После этого определяется новые 2 символа с самыми низкими числами вхождения. Такая операция выполняется до тех пор, пока все дерево не будет сформировано, т. е. все узлы не сольются в один узел ROOT со знанием 100. Процесс кодирования по дереву начинается всегда с корня ROOT. Каждый символ прослеживается вверх по дереву, при этом каждый левый поворот запоминается как 0, каждый правый- 1. При кодировании символы заменяются на полученные уникальные коды.

A- 0110 B- 11 C- 00 D- 0111 E- 10 F- 010

 

Модификация алгоритма Хаффмана. Изображение черно-белое сжимается этим алгоритмом достаточно хорошо, но коэффициент сжатия 3:1, поэтому существует модификация алгоритма Х. Group3 и Group4, которые на ряду с простым кодом Х. имеют еще терминальный код для описания последовательности пикселей. В этом алгоритме кодовые слова берутся из предопределенной таблицы значений и кодовые слова короче, чем исходные данные.

Сжатие с потерями JPEG

В настоящее время JPEG- стандартный формат файлов, а на основе метода сжатия JPEG создает новые и модифицированные существующие файловые форматы. JPEG не является просто алгоритмом – это целый набор методов сжатия, включенные в различные форматы. Более серьёзное кодирование элементов цветности, но не яркости. JPEG-сжатие сопровождается потерями. В процессе кодир-ния отбрасываются ненужные или невидимые человеком данные. Т.к. глазом человека плохо распознаются незначительные изменения цвета, а незначительные изменения яркости – гораздо лучше, то JPEG как раз использует эту способность цвето восприятия человеческого глаза, он бережно обращается с яркостью сост. изображения, но удал. измен. цвет. гамму. Схема JPEG специально разработана для сжатия цветных и полутоновых многоцветных изображений, т.е. фотографий, телевизионных заставок и т.п. Схема JPEG используется также для сжатия видеоизображений в стандарте MPEG.

Объем сжатых данных зависит от содержания исходного изображения и степень сжатия составляет 20:1 или 25:1 без заметной потери качества. JPEG используется только для изображений, имеющих пиксел-ую глубину более 5 – 6 битов на цветовой канал 68 тыс цветов. Пользователь может отрегулировать качество кодировщика JPEG, используя параметр Q-фактор – установка качества, кот измен от 1 до 100. Если Q = 1, создается сжатое изображение самого маленького размера и самого плохого качества. При Q =100 – размер сжатого JPEG – файла – максимальный и качество максимальное. Но JPEG не всегда является лучшей схемой сжатия, т. к. 1)не используется для черно- белых изобр 2)плохо сжимаются большие области одного цвета 3)схему JPEG реализовывать самостоятельно очень сложно.

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

Алгоритм сжатия JPEG

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

1). ПРЕОБРАЗОВАНИЕ ИЗОБРАЖЕНИЯ В ОПТИМАЛЬНОЕ ЦВЕТОВОЕ ПРОСТР-ВО: JPEG преобразовывает каждый компонент цветовой модели отдельно и обеспечивает полную независимость преобразования от модели цветового пространства. Причем преобразуются они в модель YUV или YCbCr, где Y – компонент яркости, а U(Cb) и V(Cr) – компоненты цветности.

Из RGB в YUV:

Y = 0.299R + 0.587G + 0.114B

U = -0.169R – 0.331G + 0.5B + 128

V = 0.5R – 0.419G – 0.081B + 128

(в лекции не было, на всякий случай):

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

YUV – RGB:

R = Y + 1.402(Cr - 128)

G = Y – 0.34414(Cb - 128) – 0.71414(Cr - 128)

B = Y + 1.772(Cb - 128)

2). СУБДИСКРЕТИЗАЦИЯ КОМП-ОВ ЦВЕТА субдискретизация осуществляется за счет уменьшения количества пикселей для каналов цветности. Для этого каждый пиксель яркости представляется в исходном виде, а для каждого пикселя цветности выбирается область 2:2 пикселя яркости. Для сохранения информации о четырех пикселях потратятся всего 6 пикселей значений вместо 12ти. 1)4 пикселя для яркости 2)по одному для каждого из 2х каналов цветности. Уменьшение объема изображения на 50 на качестве большинства изображений почти не сказывается. Стандарт JPEG предполагает несколько различных вариантов определения коэффициентов дискретизации. Канал яркости всегда остается с коэффициентом 1:1, для обоих каналов цветности производится субдискретизация 2:1 в горизонтальном направлении и 1:1 или 2:1 в вертикальном. Пиксель цветности после субдискрет-ии охватывает ту же область, что и блок 2:1 или 2:2 пикселей яркости. Эти процессы соответственно наз для 2*1- 2h1v -дискретизацией (4:2:2) или для 2*2- 2h2v – дискретизацией (4:2:0).

3). Дискретные косинус- преобразования (ДКП):

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

4). КВАНТОВАНИЕ кажд блока коэф-ов ДКП: прежде, чем отбросить определенный объем информации, компрессор делит каждое выходное значение ДКП на коэффициент квантования, округляя полученный результат до целого. Каждый из 64х позиций ДКП имеет свой коэффициент квантования. Коэффициент квантования – величина, обратная Q-фактору. Чем больше коэффициент квантования, тем больше данных теряется, т. к. реальные значения ДКП представляются менее точными. На этом этапе большинство JPEG компрессоров управляется установкой качества(Q- фактора). Компрессор имеет встроенную таблицу, насчитывающую на среднее качество и наращивание или уменьшение значения каждого элемента обратно пропорционально заданному Q-фактору.

5). КОДИРОВАНИЕ РЕЗУЛЬТИР-Х КОЭФФ-ОВ с применением алг Хаффмана: т.к. результирующие коэффициенты содержат значительный объем избыточных данных, сжатие по алгоритму Хаффмана позволяет без потерь удалить избыточность информации, уменьшив объем данных.

 

Фрактальная графика.

Этот способ воспроизведения графических изображений, отличен как от векторной, так и от растровой графики и основан на получении изображения по его алгоритмическому образу, записанному в виде некоторой программы. Фрактал состоит из подобных форм и рисунков, встречающихся во множестве различных размеров в одном изображении. Термин фрактал впервые ввел Бенуа Мандельброт в 1975 году для описания повторяющихся самоподобных структур.

Построение фрактала- это итерационный алгоритм, который определяет самоподобие фрактала – отдельные части похожи по форме на весь фрактал в целом. #“папоротник Барнсли”. Фракталы делятся на: геометрические, алгебраические и стохастические.

Геометрические фракталы являются самыми наглядными. Их получают с помощью некоторой ломаной (в трехмерном случае поверхности), называемой генератором. За один шаг алгоритма каждый из отрезков, составляющих ломаную, заменяется на ломаную- генератор в соответствующем масштабе. В результате бесконечного повторения этой процедуры получается геометрический фрактал. #Рассмотрим один из таких фрактальных объектов- триадную кривую Коха. Построение кривой начинается с отрезка единичной длины- это нулевое поколение кривой Кох. Далее каждое звено (в нулевом поколении единственное) заменяется на образующий элемент n=1, который состоит из 4 звеньев, каждое длиной по 1/3.Для получения следующего поколения каждое прямолинейное звено опять заменяется на уменьшенный образующий элемент, т.е. для получения каждого последующего поколения все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. При n стремящимся к бесконечности кривая Коха становится фракталом.

Алгебраические фракталы можно построить даже по алгебраической формуле y = x² + C. #Для построения такого фрактала выбирается точка x = a + bi на комплексной плоскости. На эту точку действуют отображением x₁ à x² + C, в результате чего точка перемещается на плоскости. На полученную точку повторно действуют отображением, и так несколько раз (несколько итераций. Если в результате этого точка «убегает» на бесконечность, то она красится в один (допустим белый) цвет, если «прыгает» вокруг исходного положения- красим в другой цвет (допустим черный). Такие действия повторяются для всех точек плоскости. Т. о. получается двухцветная картина, где черная фигура- это множество Жюлиа. Его форма меняется в зависимости от коэффициента С. Так же можно получить и многоцветный фрактал: точки не «убегающие» на бесконечность красим в цвет №1, «убегающие» за одну итерацию - в цвет №2, за две - в цвет №3 и т.д. По аналогичному алгоритму получается другой фрактал – множество Мандельброта. Но здесь каждая точка получается подстановкой в отображение x₁ à x² + C комплексного числа, как значения коэффициента С. Для того, чтобы построить фракталы по этому алгоритму можно воспользоваться программным продуктом Fractint.

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

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

Фрактальное сжатие.

На основе фрактального алгоритма разработан способ сжатия информации, называемый фрактальным сжатием.

Если сделать копию небольшого фрагмента однородного растрового изображения (например, пейзажа) и сравнить его с другими участками этого изображения, то обнаружится несколько областей, почти совпадающих по внешнему виду с выбранной копией. Слегка изменив копию путем масштабирования, поворота или зеркального отражения, становится видно, что она стала похожа еще на большее число участков исходного изображения. Обнаружив совпадения можно создать математическое описание выбранной копии. Обработав таким образом всю поверхность изображения, получим систему математических уравнений, называемых фрактальными кодами. Эти фрактальные коды затем используются для воссоздания исходного изображения. Фрактальное сжатие – это математический процесс, применяемый для кодирования растров, которые содержат реальное изображение, в совокупность математических данных, которые описывают фрактальные свойства изображения. Фрактальное кодирование основано на том факте, что все естественные и большинство искусственных объектов содержат избыточную информацию в виде одинаковых, повторяющихся рисунков, (т. е. фракталов). Этот алгоритм хорошо работает только с полноцветными 24 битными изображениями или изображения в градациях серого без резких переходов цветов. Для поиска фрактальных рисунков в изображении необходимы миллионы и даже миллиарды итераций. Декодирование фрактального изображения -процесс гораздо более простой. В процессе декодирования нужно лишь интерпретировать фрактальные коды, преобразовав их в растровое изображение. В процессе фрактального кодирования реализуются два существенных преимущества: 1) возможность масштабировать фрактальное изображение 2)размер физических данных, используемых для записи фрактальных кодов, значительно меньше размера исходных растровых данных.Фрактальное сжатие всегда сопровождается потерями, так как процесс сравнения фракталов не предусматривает поиска точного их соответствия. На степень фрактального сжатия заметное влияние оказывает содержимое и разрешение исходного растра. Параметрами сжатия можно управлять, доводя изображение до такого состояния, в котором оно визуально не имеет потерь. Фрактал сжатие применяется в БД изображений. Наиболее известные фрактал пакеты: Fractint, Fractal Transform.

 

 

MPEG сжатие.

Стандарт MPEG (Moving Picture Expert Group) начал разрабатываться в 1988г. Комитеты ISO MPEG и JPEG начинали свою работу как одна группа, ориентированная на две различные цели. Затем JPEG сконцентрировала свои усилия на сжатии неподвижных изображений, a MPEG — на кодировании и синхронизации аудио- и видеосигналов в едином потоке данных. Эти стандарты различны и предназначены для разных целей, хотя MPEG и использует метод покадрового сжатия данных, подобный тому, который применяет JPEG. Первоочередным направлением в построении алгоритмов всех стандартов MPEG является отыскание и устранение информации, избыточной с точки зрении субъективного восприятия человеком.

В MPEG применяется метод асимметричного сжатия, при котором процесс сжатия более сложен, чем распаковка. Формат особенно удобен при использовании приложениями, которые записывают данные лишь однажды, а читают их по многу раз.

В MPEG при обработке видеоданных применяются два типа сжатия: внутрикадровое и межкадровое кодирование.