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

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

 

 

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

А) кодирование длин серий;

Заменим для простоты значения цвета буквами. Если в документе, скажем, имеется такая последовательность "АААААВВВВВВВСССССС", ее можно сжать таким образом: 5А7В6С. В результате вместо 18 символов в документе достаточно хранить всего 6.

Недостатки: необходимость различать собственно данные и числа повторений, а также возможное увеличение объема файла, если в документе мало повторений.

Б) метод Хаффмана;

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

Заменим также для простоты значения цвета буквами. Например, в следующей последовательности букв ААСАААВАВАВВАВСАСВСАСААССС заметно, что чаще всего встречается символ А (12 раз), затем символ С (9 раз) и, наконец, символ В (5 раз). Следовательно, символ А можно заменять кодом 0, символ С — кодом 1, а символ В — кодом 00. И так далее, если элементов для кодирования больше.

В) алгоритм LZW.

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

Пусть сжимается последовательность символов АВВСВВВ…в результате в документе окажется следующая последовательность кодов [256][А][В][В][С][259], что короче исходной последовательности.

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

Наиболее известным методом компрессии с потерями является JPEG-компрессия(Joint Photographic Experts Group). Метод компрессии основан на особенности человеческого восприятия: глаз достаточно четко различает яркость объекта и цветовые контрасты, а плавные изменения в светах и тенях значительно меньше. Для этого обработка изображения происходит в несколько этапов. Сначала изображение конвертируется в особое цветовое пространство, в котором один канал сохраняет яркостные характеристики, а в остальных двух цветовых каналах уменьшается разрешение.

Затем изображение разбивается на фрагменты квадратной формы со стороной в 8 пикселей. Каждый фрагмент подвергается достаточно сложным математическим преобразованиям. Записывается два типа информации — усредненная информация о блоке и информация о его деталях, далее, в зависимости от выбранной степени сжатия, удаляется то или иное количество дополнительной информации. Чем меньше будет размер файла, тем хуже будет его качество.

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

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

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

 

Алгоритм сжатия аудиоданных

 Аудиофайлы без сжатия занимают большой объём памяти (1мин занимает примерно10 Мб). Поэтому применяют сжатие. Все звуковые форматы можно разбить на три группы:

· аудиоформаты без сжатия (WAV, AIFF) Звук в файлах хранится без какого-либо сжатия и изменений. Применяется лишь в профессиональных аудио и видео приложениях. Хранение обычных музыкальных композиций в таком виде является неоправданной расточительностью

· С о сжатием без потерь (APE, FLAC) работают по принципу обычных архиваторов, уровень сжатия (от 40 до 60%), не влияют на качество звука. Используются МДКП и алгоритм Хафмана

· С применением сжатия с потерями (mp3, ogg) самая популярная группа алгоритмов обеспечивают степень сжатия звука до 10 раз и даже более. Для определения качества оцифрованного звука наиболее часто применяется такой показатель, как битрейт – скорость звукового потока, получившаяся после сжатия и измеряемая в килобитах в секунду (kbps). Несжатый аудиофайл имеет битрейт примерно 1400 кбит/c. Файл практически не отличимый по звучанию 320 кбит/c.

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

· частотное (одноврЕменное) маскирование

· временнОе (неодноврЕменное) маскирование

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

Маскирование во временной области характеризует динамические свойства слуха, показывая изменение во времени относительного порога слышимости (порог слышимости одного сигнала в присутствии другого), когда маскирующий и маскируемый сигналы звучат не одновременно.

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

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