Опрос

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

Новички

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

Критерии сравнения алгоритмов

Заметим, что характеристики алгоритма относительно некоторых требо­ваний приложений, сформулированные выше, зависят от конкретных усло­вий, в которые будет поставлен алгоритм. Так, степень компрессии зависит от того, на каком классе изображений алгоритм тестируется. Аналогично скорость компрессии нередко зависит от того, на какой платформе реализо­ван алгоритм. Преимущество одному алгоритму перед другим может дать, например, возможность использования в вычислениях алгоритма техноло­гий нижнего уровня, типа ММХ, а это возможно далеко не для всех алго­ритмов. Так, JPEG существенно выигрывает от применения технологии ММХ, a LZW нет. Кроме того, нам придется учитывать, что некоторые ал­горитмы распараллеливаются легко, а некоторые нет.

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

Так, например, еще в 1994 г., интерес к показу огрубленного изобра­жения, используя только начало файла (требование 6), был чисто абстракт­ным. Реально эта возможность практически нигде не требовалась, и класс приложений, использующих данную технологию, был крайне невелик. Со взрывным распространением Интернета, который характеризуется пере­дачей изображений по сравнительно медленным каналам связи, использование Interlaced GIF (алгоритм LZW) и Progressive JPEG (вариант алгоритма JPEG), реализующих эту возможность, резко возросло. То, что новый алго­ритм (например, wavelet) поддерживает такую возможность, существен­нейший плюс для него сегодня.

В то же время мы можем рассмотреть такое редкое на сегодня требова­ние, как устойчивость к ошибкам. Можно предположить, что в скором времени (через 5-10 лет) с распространением широковещания в сети Ин­тернет для его обеспечения будут использоваться именно алгоритмы, ус­тойчивые к ошибкам, даже не рассматриваемые в сегодняшних статьях и обзорах.

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

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

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

Симметричность. Отношение характеристики алгоритма кодирования к аналогичной характеристике при декодировании. Характеризует ресурсоем-кость процессов кодирования и декодирования. Для нас наиболее важной явля­ется симметричность по времени: отношение времени кодирования ко времени декодирования. Иногда нам потребуется симметричность по памяти.

Есть ли потери качества? И если есть, то за счет чего изменяется сте­пень сжатия? Дело в том, что у большинства алгоритмов сжатия с потерей информации существует возможность изменения степени сжатия.

Характерные особенности алгоритма и изображений, к которым его применяют. Здесь могут указываться наиболее важные для алгоритма свой­ства, которые могут стать определяющими при его выборе.

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


Прежде чем непосредственно начать разговор об алгоритмах, хотелось бы сделать оговорку. Один и тот же алгоритм часто можно реализовать раз­ными способами. Многие известные алгоритмы, такие, как RLE, LZW или JPEG, имеют десятки различающихся реализаций. Кроме того, у алгоритмов бывает несколько явных параметров, варьируя которые можно изменять ха­рактеристики процессов архивации и разархивации. (См. примеры в подраз­деле о форматах). При конкретной реализации эти параметры фиксируются, исходя из наиболее вероятных характеристик входных изображений, требований на экономию памяти, требований на время архивации и т. д. Поэтому у алгоритмов одного семейства лучшая и худшая степени сжатия могут отличаться, но качественно картина не изменится.