четверг, 28 апреля 2011 г.

Параллельный вейвлетный компрессор изображений EPSILON

EPSILON - это параллельный вейвлетный компрессор изображений. Программа поддерживает более 30 различных вейвлетных фильтров и имеет механизм для добавления новых. Кроме того, EPSILON поддерживает очень большие изображения (больше 4Gb) и позволяет точно задавать желаемую степень сжатия заранее.

К настоящему моменту имеются три механизма для распараллеливания:
  • POSIX threads
  • MPI (Message Passing Interface)
  • Собственное кластерное решение на базе TCP/IP
Метод распараллеливания задаётся опцией во время компиляции (имеются HOW-TO по запуску MPI и кластерной версии). Можно также собрать и простую, последовательную версию программы.

Архитектурно EPSILON состоит из двух частей: библиотеки libepsilon и программы epsilon, которая использует данную библиотеку. Таким образом, libepsilon может использоваться (и фактически используется) независимо.

Программа epsilon поддерживает два графических формата: PGM и PPM. Сжатое изображение сохраняется в собственном формате PSI. PSI-файл состоит из последовательности блоков, соответствующих блокам исходного изображения. Каждый блок абсолютно независим от остальных и имеет свой заголовок и CRC. Таким образом, даже если все блоки в файле кроме одного будут полностью испорчены или утрачены, то этот единственный блок распакуется без проблем и встанет на своё место в изображении.

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

Уже сжатое изображение можно дополнительно усечь (дожать). Благодаря технологии известной как embedded wavelet coding, алгоритм усечения выглядит следующим образом: пробежаться по всем сжатым блокам и усечь (буквально) каждый до необходимого размера. Единственное дополнительное действие - пересчёт CRC усечённого блока. Интересно отметить, что сжатое, а затем усечённое изображение ничем не будет отличаться от изначально сжатого до размера усечённого.

Начиная с версии 0.9.1 в EPSILON появился свой тестовый фреймворк, написанный на Perl. К настоящему моменту имются два теста: быстрый - quick.t и полный - verification.t

Полный тест для каждого из тестовых изображений перебирает все 4 версии EPSILON (generic, pthreads, cluster, mpi), все вейвлетные фильтры, все поддерживаемые размеры блоков и все допустимые режимы работы. Для каждой полученной комбинации (на данный момент их 7680) производится сжатие, распаковка и расчёт PSNR между исходным и восстановленным изображениями. Если полученный PSNR меньше ожидаемого, то тест сохраняет для дальнейшего анализа полученные файлы и список использованных опций.

EPSILON используется в составе OpenSource GIS-библиотеки GDAL: http://www.gdal.org/frmt_epsilon.html

Пример использования EPSILON на реальной спутниковой фотографии: http://www.gaia-gis.it/raster_benchmark/color-ortho-epsilon.html

EPSILON распространяется по лицензии GPL3 или LGPL3 (по выбору).
Страница проекта: http://epsilon-project.sourceforge.net/

7 комментариев:

  1. Я правильно понимаю, что изображение в 4 гига - это что-то типа 32000x32000 при 32-х битах на точку?

    ОтветитьУдалить
  2. Почему-то ссылки на графические форматы PGM и PPM ведут на какой-то .Net и managing workflows. 8-0

    ОтветитьУдалить
  3. Этот труд - результат твоей работы или чисто хобби такое - кластерные сжиматели писать?

    ОтветитьУдалить
  4. Сейчас один из тимлидов опять заикнулся, что хотел бы тебя в свою команду, и я рассказал ему про твою вейвлетную сжималку. Правда, немного соврал насчёт размера изображений. У меня в голове почему-то отложилось 2000x2000 px. Поэтому как бы я эту статью снова посмотрел для себя.

    PS. А зачем премодерация сообщений даже для залогинившихся пользователей?

    ОтветитьУдалить
  5. EPSILON - это часть моей дипломной и аспирантской работы, ну и хобби конечно тоже. Сейчас программа начала потихоньку жить своей собственной жизнью, что не может не радовать :)

    При 32-х битах на точку да, но EPSILON умеет обрабатывать только 3 канала, поэтому исходить надо из расчёта 24-х битов на точку. Получается примерно 37000 x 37000

    По поводу форматов PGM и PPM - вот правильная ссылка: http://netpbm.sourceforge.net/

    ОтветитьУдалить
  6. Я тут потыкал. В одном из jpeg'ов тоже есть какой-то вейвлетный компрессор. Это твой или параллельная разработка? Патентованная ли это технология, знаешь что-нибудь на эту тему?

    ОтветитьУдалить
  7. > PS. А зачем премодерация сообщений даже для
    > залогинившихся пользователей?

    Одно время стали появляться рекламные сообщение в постах, добавленные ботами.

    ОтветитьУдалить