Методы сжатия с потерей информации
Лекция 15
Тема 9. Методы кодирования со сжатием и с потерями информации..
Дифференциальное кодирование
Лекция 02
Работа дифференциального кодера основана на том факте, что для многих типов данных разница между соседними отсчетами относительно невелика, даже если сами данные имеют большие значения. Например, нельзя ожидать большой разницы между соседними пикселами цифрового изображения например для пейзажной, бытовой или жанровой фотографии. Другое дело, если мы фотографируем штрих-код или стадо зебр.
Следующий простой пример показывает, какое преимущество может дать дифференциальное кодирование (кодирование разности между соседними отсчетами) в сравнении с простым кодированием без памяти (кодированием отсчетов независимо друг от друга).
Просканируем 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 (за исключением случаев кодирования данных с высокой степенью повторяемости одинаковых участков и т.п.).