Одномерное дискретное косинусное преобразование
Дискретное косинусное преобразование
Лекция 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).