Одномерное дискретное косинусное преобразование

Дискретное косинусное преобразование

Лекция 10. Сжатие c потерями

ЗАДАНИЕ

Построить код LZ77 для произвольной последовательности из нулей и единиц длинной 32 символа, используя скользящий буфер предистории и упреждающий буфер с длинами по 8 символов каждый.

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

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

Дискретное косинусное преобразование (Discrete Cosine Transform, DCT) представ­ляет собой преобразование массива пикселов в массив значений пространственной частоты. Это преобразование обратимо с точностью до ошибок округления. Дискретное косинусное преобразование не производит сжатия, но преобразует информацию об изображении в форму, более удобную для сжатия.

Предположим, что у нас есть одномерное изображение, представляющее собой линейный массив из N пикселов, каждый из которых обозначается некоторым зна­чением яркости р(х) (0 < х < N). Таким образом, р(х) представляет собой простран­ственную функцию (а не функцию времени). Это изображение можно представить в виде суммы пространственно-частотных компонентов с частотами, изменяющи­мися

от 0 до N-1:

(10.1)

Это напоминает представление непрерывной функции в виде ряда Фурье. В данном случае мы представляем дискретную функцию р(х), а частотные компо­ненты определены только для дискретных значений частот.

Чтобы получить формулу (10.1), нужно вычислить коэффициенты {S(f), 0<f<N}. Обратите внимание на то, что первое слагаемое формулы (10.1) пред­ставляет собой компонент с нулевой частотой, то есть постоянную составляющую. Это слагаемое должно быть равно среднему значению р(х). Поэтому:

Общая формула для S(f) выглядит следующим образом:

(10.2)

Формула (10.2) называется одномерным дискретным косинусным преобразо­ванием функции р(х), а формула (10.1) представляет собой обратное дискретное косинусное преобразование функции S(f).