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

Дифференциальное кодирование

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

Покажем, какое преимущество может дать дифференциальное кодирование (кодирование разности между соседними отсчетами) в сравнении с простым кодированием (кодированием отсчетов независимо друг от друга).

Просканируем 8-битовое (256-уровневое) цифровое изображение, при этом десять последовательных пикселов имеют уровни:

144, 147, 150, 146, 141, 142, 138, 143, 145, 142.

Если закодировать эти уровни пиксел за пикселом каким-либо кодом без памяти, использующим 8 бит на пиксел изображения, получим кодовое слово, содержащее 80 бит.

Предположим теперь, что прежде чем подвергать отсчеты изображения кодированию, мы вычислим разности между соседними пикселами. Эта процедура даст последовательность:

144, 147, 150, 146, 141, 142, 138, 143, 145, 142.

ß ß ß ß ß ß ß ß ß ß

144, 3, 3, - 4, - 5, 1, - 4, 5, 2, -3.

Исходная последовательность может быть легко восстановлена из разностной простым суммированием:

144, 144+3, 147+3, 150–4, 146–5, 141+1, 142–4, 138+5, 143+2, 145-3

ß ß ß ß ß ß ß ß ß ß

144, 147, 150, 146, 141, 142, 138, 143, 145, 142.

Для кодирования первого числа из полученной последовательности разностей отсчетов, как и ранее, понадобится 8 бит, все остальные числа можно закодировать 4-битовыми словами (один знаковый бит и 3 бита на кодирование модуля числа).

Таким образом, в результате кодирования получим кодовое слово длиной 8 + 9*4 = 44 бита или почти вдвое более короткое, чем при индивидуальном кодировании отсчетов.

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

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

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

· без потерь информации (неразрушающие);

· с потерями информации (разрушающие).

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

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

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

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

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

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

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

Рассмотрим в качестве примера популярный метод сжатия изображений JPEG (“джипег”).

Дата добавления: 2014-01-07