Алгоритмы сжатия

Потоки информации, с которыми приходится иметь дело компьютеру, как правило, содержат повторяющиеся цепочки символов. Самый яркий пример — текст, в котором неоднократно употребляются те или иные слова. Если развернуть изображение по строкам, то можно увидеть не только цепочки одинаковых чисел, но и повторяющиеся последовательности. Напрашивается мысль: заменить подобные цепочки одним символом, а в начале файла поместить таблицу замен, по которой можно восстановить информацию. Но если наш мозг позволяет быстро извлечь из текста слова, даже если они не разделены пробелами, то для компьютера эта задача является довольно сложной. И только в 1977 г. два израильских математика, А. Лемпел и Я. Зив, разработали новый класс алгоритмов сжатия без потерь, получивший название метод Лемпела–Зива. Одновременно с публикацией общих идей исследователи обнародовали и основанный на этих идеях алгоритм LZ77. Через год алгоритм был усовершенствован, новый вариант стал известен как LZ78. на основе этих разработок впоследствии было создано множество методов сжатия информации, получивших по первым буквам фамилий создателей общее название LZ — алгоритмы. Примерами реализации LZ — алгоритмов являются Zip — архиваторы и протокол V.42bis.

Недостатком классического варианта алгоритма LZ является то, что он эффективен лишь для повторяющихся цепочек длиной не менее 5 байт. При сжатии текстов это приемлемо, но при сжатии изображения глубиной цвета 8 бит классический LZ становится неэффективным. В 1983 г. сотрудник компании Unisys Т. Уэлч нашел способ усовершенствовать классический LZ таким образом, что становится выгодным работать с повторяющимися цепочками, начиная с 2 байт — этот вариант алгоритма получил название Лемпела–Зива–Уэлча (LZW). Представим, что найдена цепочка символов А, которая содержит уже найденную цепочку В и больше ее всего на один символ С. В классическом алгоритме LZ цепочки А и В будут записаны и обрабатываться отдельно или же будет взята большая из них, т.е. А. В алгоритме LZW последовательность А будет записана как «С, ссылка на В». Таким образом, не только уменьшается объем сохраняемой в файле информации, но и значительно повышается быстродействие. В отличие от классического LZ, который стал общедоступен, алгоритм LZW был запатентован компанией Unysys.

Алгоритм LZW появился очень своевременно и сразу же стал применяться в самых разнообразных целях, но особенно удачным оказалось его использование для сжатия изображений, передаваемых по компьютерным сетям. На основе LZW в компании CompuServe, которая владела одной из крупнейших компьютерных сетей США, в 1987 г. был создан графический формат Graphics Interchange Format (GIF). Среди преимуществ GIF — поддержка т.н. чересстрочной развертки, благодаря чему в процессе загрузки можно увидеть изображение в полном размере, но с пониженной четкостью и принять решение, стоит ли загружать его дальше. По мере загрузки новых данных четкость изображения повышается.

Формат GIF быстро завоевал популярность среди пользователей CompuServe, в 1989 г. была принята его новая версия.

1. PNG

За разработку нового формата, который был бы не хуже, чем GIF, но при этом не требовал лицензионных отчислений, интернетовская общественность взялась всем миром. Точкой отсчета истории PNG можно считать 4 января 1995 г., когда Т. Боутелл послал в ряд конференций Usenet свои предложения о графическом формате Portable Bitmap Format (PBF).

Первый вариант нового формата был, как GIF, 256- цветным и еще не был привязан к определенному методу сжатия, но уже содержал некоторые черты современного PNG. События развивались стремительно. 23 января 1995 г. новый формат получил современное название Portable Network Graphics (PNG), что в переводе на русский язык означает «переносимый графический формат». Темпы, которыми шла разработка формата, иллюстрирует следующий факт: к моменту переименования, т.е. менее, чем через три недели после размещения описания алгоритма в Usenet, было разработано уже четыре его версии.

В основе PNG лежит LZ-алгоритм, который, обладая преимуществами LZW, является лицензионно чистым. Графический формат PNG поддерживает глубину цвета до 48 бит, но в отличие от большинства графических форматов в PNG нет четкого деления между типами изображений по глубине цвета. В графический файл формата PNG записывается описание всей палитры цветов, используемой в изображении, что позволяет гибко подстраиваться под реальное число цветов в изображении и обеспечивает более высокую степень сжатия, чем GIF. Как и GIF, формат PNG поддерживает возможность чересстрочной развертки, причем в PNG она является двумерной. Среди других приятных особенностей формата PNG — возможность выбора компрессии либо по критерию быстроты распаковки изображения, либо по максимально высокому коэффициенту сжатия.

Формат PNG поддерживается Netscape Communicator, начиная с версии 4.0, Microsoft Internet Explorer начиная с версии 4.01 — всеми версиями браузера Opera, а также почти всеми современными графическими редакторами. Однако встретить изображение в формате PNG на Web-страницах до сих пор практически невозможно. Причина в том, что формат GIF со сжатием без потерь используется на WEB-страницах главным образом для мелких элементов навигации и управления. В формате PNG размер файла не может быть меньше 1 Кбайт, поскольку именно столько занимает описание палитры. Таким образом, для маленьких изображений размер файла в формате PNG может быть больше, чем у GIF, а иногда больше, чем у BMP.

2. JPEG

Методы сжатия с потерями применяются для изображения с глубиной цвета 24 бита. Возможен вариант их использования для изображения с 256 оттенками серого. С одной стороны, именно для полноцветных изображений нужны эффективные методы сжатия: изображение 800×600 точек с глубиной цвета 24 бита в формате BMP занимает 1,4 Мбайт! С другой стороны, при глубине 8 бит изменение цвета хотя бы на один бит в младшем разряде хорошо заметно глазу, а ведь при сжатии с потерями искажения непременно возникают. Если глубина цвета 24 бита, то ошибка в одном-двух младших битах будет малозаметна.

Формат JPEG (Joint Photographic Expert Group) был разработан в 1991 г. одноименным подразделением в рамках ISO — международной организации по стандартизации. Суть его заключается в следующем. Изображение делится на участки размером 8х8 точек. В пределах каждого участка над массивом точек осуществляется дискретное преобразование Фурье. В полученном спектре более высоким частотам будут соответствовать более мелкие детали. Как правило, чем выше частота, тем меньше амплитуда (частота и амплитуда являются более общими понятиями, применимыми и к изображению). В зависимости от требуемой степени сжатия записываются коэффициенты для частот от нуля до определенного значения. Интересно, что по своему принципу работы JPEG отдаленно напоминает алгоритм сжатия звуковой информации МР3, что еще раз свидетельствует о единстве законов природы.

Искажения изображения при использовании алгоритма JPEG проявляются в размывании резких цветовых границ и исчезновений мелких деталей. При очень сильном сжатии изображение начинает выглядеть как мозаика, каждый элемент которой имеет размер 8х8 точек. При сжатии задается показатель качества, выраженный в процентах, — чем он больше, тем меньше степень сжатия. Для хорошего качества сжатие фотографического изображения по сравнению с BMP составляет 10–20 раз.

Алгоритм JPEG положен в основу одноименного формата, поддерживающего прогрессивную развертку (в отличие от телевидения и компьютерных мониторов, где термины «чересстрочная развертка» и «прогрессивная развертка» имеют прямо противоположное значение, в данном случае они близки по смыслу; прогрессивная развертка, также как и чересстрочная, обеспечивает постепенную прорисовку изображения), а также используется в форматах TIFF и QuickTime.