Точность. Помехи и искажения. Приближенное восстановление

Методы сжатия с потерей информации

Лекция 15

Тема 9. Методы кодирования со сжатием и с потерями информации..

Как уже ранее отмечалось, существуют два типа систем сжатия данных:

· без потерь информации

· с потерями информации

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

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

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

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

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

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

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

Для того, чтобы понять, на чем основана высокая эффективность систем сжатия с потерями и почему кодирование преобразований оказывается значительно более эффективным, нежели кодирование исходных данных, рассмотрим в качестве примера популярный метод сжатия изображений JPEG (“джипег”), который содержит в себе все необходимые признаки системы сжатия с потерями. Не будем сейчас вдаваться в формульные дебри, главное – понять идею кодирования преобразований.

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

(a) 15.5 Кодирование преобразований. Стандарт сжатия JPEG

Популярный стандарт кодирования изображений JPEG (Joint Photographers Experts Group) является очень хорошей иллюстрацией к объяснению принципов сжатие с потерями на основе кодирования преобразований.

Для сжатия графической информации с потерями в конце 1980-х установлен один стандарт - формат JPEG (Joint Photographic Experts Group - название объединения его разработчиков). В этом формате можно регулировать степень сжатия, задавая степень потери качества.

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

ДПФ и простое уменьшение разрядности. Если же подвергнуть сигнал преобразованию Фурье (или какому-либо другому подобному линейному преобразованию), разделить его на две составляющие – НЧ и ВЧ, продискретизовать, подвергнуть квантованию каждую из них и отбросить половину двоичных разрядов только в высокочастотной составляющей сигнала, то результирующая объем кода уменьшится на одну треть, а потеря информации составит всего 5%.

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

Рассмотрим работу алгоритма сжатия JPEG при кодировании черно-белого изображения, представленного набором своих отсчетов (пикселов) с числом градаций яркости в 256 уровней (8 двоичных разрядов). Это самый распространенный способ хранения изображений - каждой точке на экране соответствует один байт (8 бит - 256 возможных значений), определяющий её яркость. 255 - яркость максимальная (белый цвет), 0 - минимальная (черный цвет). Промежуточные значения составляют всю остальную гамму серых цветов (рис. 15.1).

Рис. 15.1

Работа алгоритма сжатия JPEG начинается с разбиения изображения на квадратные блоки размером 8х8 = 64 пиксела. Почему именно 8х8, а не 2х2 или 32х32? Выбор такого размера блока обусловлен тем, что при его малом размере эффект сжатия будет небольшим (при размере 1х1 – вообще отсутствует), а при большом - свойства изображения в пределах блока будут сильно изменяться и эффективность кодирования снова снизится.

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

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

Дискретное косинусное преобразование от изображения IMG (x, y) может быть записано следующим образом:

где N = 8, 0 < i < 7, 0 < j < 7,

Дата добавления: 2013-12-11