Методы сжатия с потерями

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

Пусть имеется непрерывный периодический сигнал a (t) с периодом T. Его можно представить в виде:

.

Можно подобрать систему функций , s = 0, 1, …, N – 1, так, чтобы:

- ни одна из них не могла быть получена линейной комбинацией других:

;

- за скалярное произведение принимается

;

- они попарно ортогональны и нормированы:

.

Такой выбор системы функций , s = 0, 1, …, N – 1, позволяет представить сигнал a (t) в виде точки N -мерного функционального пространства с координатами a_s. Систему функций , s = 0, 1, …, N – 1, называют базисом пространства сигналов, каждую из функций – базисной, представление сигнала в форме композиции базисных функций – разложением по заданному базису. Координаты точки, соответствующие сигналу a (t), можно найти по формуле

.

Существует множество систем функций, обладающих свойствами базиса. В частности базис образует система функций вида:

.

Разложение сигнала по этому базису называют разложением Фурье, а нахождение коэффициентов разложения – преобразованием Фурье. Преобразование Фурье выполняется по формуле:

.

В дальнейшем будем рассматривать периодический сигнал, который принимает значения в дискретные моменты времени

,

где , N – количество разбиений интервала T. Тогда, непрерывный сигнал a (t) заменяется на последовательность отсчетов

a ((k + 0.5)D t) = a_k, k = 0, 1, …, N – 1,

взятых посредине отрезков разбиения D t, а формулы преобразования Фурье приобретают вид

. (6.1)

Формула (7.1) задает прямое ДКП, которое выполняется по базису

,

где c_s – нормировочный множитель, определяемый как

Данное преобразование обратимо, т.е. существует обратное ДКП. Оно задается формулой

. (6.2)

В выражении (7.2) элементы есть дискретные отсчеты базисных функций, где s – номер базисной функции, k – номер отсчета дискретизации базисной функции. Их значения образуют матрицу N ´ N, которую обозначим . Тогда прямое и обратное ДКП можно записать в матричной форме:

(6.3)

где a = (a ₀, a ₁, …, a_{N – 1}) ^T, a = (a ₀, a ₁, …, a_{N – 1}) ^T.

Описанные прямое и обратное ДКП являются одномерными преобразованиями. Однако их можно обобщить для двумерного сигнала, представленного в виде матрицы размера N ´ N. В результате ДКП над двумерным сигналом получается также матрица размера N ´ N коэффициентов разложения по базисным функциям:

, s = 0, 1, …, N – 1, r = 0, 1, …, N – 1.

Формулы в матричной форме для выполнения прямого и обратного двумерного ДКП имеют вид

(6.4)

Матрица F_N зависит только от N и может быть просчитана заранее. Например, при N = 8 она будет иметь вид.

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

f (x, y) = (r, g, b),

где x, y – координаты пикселя, r, g, b – яркости красной, зеленой и синей компонент цвета (считается, что любой цвет можно разложить на три указанные компоненты). При использовании методов сжатия, основанных на ДКП, последовательность пикселей разбивают на блоки размером 8 ´ 8 и обрабатывают эти блоки по отдельности. При этом из каждого блока выделяют матрицы яркостей красной, зеленой и синей компонент.

Предположим, что матрица яркостей одной из компонент какого-либо блока имеет вид

Теперь последовательно выполним следующие шаги.

1. Все данные смещаются на 128. Новое значение матрицы данных

a^СМ = a – 128:

.

2. Выполняются ДКП над смещенными данными: ; результаты округляются до целых значений:

.

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

где Q – параметр, задающий степень сжатия. Для рассматриваемого примера при Q = 4 получим

.

4. Кодирование данных. На этом шаге сначала полученные коэффициенты матрицы a ¹ представляют в виде линейной последовательности

,

т.е. в зигзагообразном порядке. Для нашего примера будет получена следующая последовательность:

18, 0, –4, –7, –4, –1, 0, 1, 4, –3, –4, –2, 0, 1, 0, 0, 0, –1, 0, –2, –3, –1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, –2, 1, –1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

Затем серии нулей кодируют методом RLE, что дает существенное сжатие (например, в приведенной последовательности имеется одна серия из 3 нулей, одна серия из 11 нулей и одна серия из 26 нулей). Кроме того, для улучшения сжатия дополнительно можно применить метод Хаффмена или арифметического кодирования.

Для восстановления данных выполняются обратные действия:

1. восстанавливается матрица a ¹;

2. восстанавливается матрица a:

;

3. восстанавливается матрица a^СМ:

;

4. восстанавливается матрица a:

a = a^СМ + 128.

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

Подчеркнем, что шаги компрессии и декомпрессии выполняются для всех компонент всех блоков графического файла.

Изложенный метод служит основой сжатия данных по известному стандарту JPEG. Он также является основой метода сжатия, применяемого при представлении видеоданных в стандарте MPEG. Аналогичные методы применяются также и для сжатия звуковых данных.