Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Сжатие с потерей информации

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

X ® Квантователь ® X q ® Неразрушающий кодер ® B ( Xq ) ® Декодер ® X*

Как и в предыдущей схеме, X = ( x 1 , x 2 ,… xn ) - вектор данных, подлежащих сжатию. Восстановленный вектор обозначим как X * = ( x 1 , x 2 ,… xn ). Отметим наличие в этой схеме сжатия элемента, который отсутствовал при неразрушающем сжатии, - квантователя.

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

Далее кодер подвергает неразрушающему сжатию вектор квантованных данных Xq таким образом, что обеспечивается однозначное соответствие между Xq и B ( Xq ) (для Xl q = Xm q выполняется условие B ( Xl q ) = B ( Xm q )). Однако система в целом остается разрушающей, поскольку двум различным векторам X может соответствовать один и тот же вектор X * .

Разрушающий кодер характеризуется двумя параметрами - скоростью сжатия R и величиной искажений D , определяемых как

R = k / n ,

D = (1/ n ) ∑( xi - xi )2 .                                                                          (14)

Параметр R характеризует скорость сжатия в битах на один отсчет источника, величина D является мерой среднеквадратического различия между X * и X .

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

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

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