Библиотека TiLib



TiLib

TiLib (Tiny Library) - это библиотека для сжатия изображений с потерями. Алгоритм, использованный в TiLib, основан на применении дискретного вейвлетного преобразования и специального метода кодирования коэффициентов вейвлетного разложения.

За основу в библиотеке TiLib взято вейвлетное преобразование Баттерворта, описанное в статье В. А. Желудев, А. Б. Певный. Вейвлетное преобразование Баттерворта и его реализация при помощи рекурсивных фильтров // Ж. вычисл. мат. и матем. физ. 2002. Т. 42. N 4. С. 571-582. Кроме того, библиотека поддерживает вейвлетное преобразование Добеши 9/7, взятое за основу в новейшем стандарте для сжатия изображений JPEG2000.

В качестве алгоритма кодирования в библиотеке TiLib был выбран алгоритм SPIHT, описанный в статье Amir Said, William A. Pearlman. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees // IEEE Trans. on Circuits and Systems for Video Technology. 1996. V. 6. P. 243-250.

SPIHT

Алгоритм SPIHT (Set Partitioning in Hierarchical Trees) применяется на заключительной стадии для кодирования коэффициентов вейвлетного разложения изображения. Для большей эффективности SPIHT комбинируют с арифметическим кодированием.

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

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

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

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

Сравнение TiLib и JPEG

Вот уже на протяжении многих лет JPEG является настоящей "рабочей лошадкой" для сжатия изображений. За это время появилась масса грамотных реализаций этого стандарта: как программных, так и аппаратных. Создано множество электронных устройств, поддерживающих JPEG. Написаны тысячи программ. Сегодня можно с уверенностью сказать, что JPEG стал сандартом де-факто. Бесспорно, этот алгоритм прост, быстр и красив. Но время идет, и все меняется. То, что устраивало нас вчера, сегодня уже кажется недостаточным. Всегда хочется большего.

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

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

Для эксперимента возьмем цветное тестовое изображение simakov1.ppm размера 1024x1280 точек (3932177 байт). Сожмем это изображение до 8866 байт (степень сжатия 1:443) обеими программами. Это наименьший размер файла, который удалось получить при помощи JPEG (напомним у TiLib таких ограничений нет, так как заранее задается требуемая степень сжатия). При одинаковой степени сжатия JPEG получил 26.943 dB, а TiLib - 38.767 dB. Приведем фрагменты 100x100 точек полученных изображений.

TiLib Оригинал JPEG

Скачать

Библиотека TiLib доступна для скачивания и распространяется в соответствии с лицензией GNU GPL. На данный момент существует две версии: 0.9.0 и 0.9.1. В последней версии несколько повышена эффективность преобразования Баттерворта и исправлено несколько незначительных ошибок. Дистрибутив TiLib 0.9.1, в свою очередь, распространяется в двух видах: для unix-подобных систем (autoconf, automake и друзья) и для windows (файл проекта для Visual C++ 6.0).

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


Copyleft © 2003-2008 Александр Симаков
Хостинг предоставлен Министер Казино
Последнее обновление: 15 марта 2008