четверг, 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/

пятница, 22 апреля 2011 г.

Встраиваемый лабиринт на Lua + C

Введение

Lua - интересный скриптовый язык специально разработанный для встраивания в приложения, написанные на других языках программирования, в основном C и C++. История Lua начинает свой отсчёт в 1993 году. Язык разрабатывается в стенах Католического университета Рио-де-Жанейро (Pontifical Catholic University of Rio de Janeiro in Brazil) силами Роберто Иерусалимского (Roberto Ierusalimschy), Вальдемара Селеса (Waldemar Celes), Луис Энрике ди Фигейреду (Luiz Henrique de Figueiredo), а также страниями сообщества Lua-программистов.

Первое, что бросается в глаза при знакомстве с Lua - это крайний минимализм синтаксиса и встроенных библиотек. Позиция авторов в этом вопросе вполне понятна - распухни Lua до размеров Perl-а, Python-а или Ruby - не занять ему той ниши, которую он так прочно удерживает в мире языков программирования. Однако чрезмерный аскетизм приводит к интересным эффектам: вот, к примеру, wiki-страница с одного из центральных сайтов Lua-сообщества, на которой приводится 10 (!) различных реализаций функции split() на Lua. Все реализации немного отличаются друг от друга: есть ли поддержка регулярных выражений или нет, допускается ли пустой разделитель или нет, возвращается ли результат или сохраняется по ссылке, что идёт первым аргументом - сама строка или разделитель. Хочется надеяться, что http://luaforge.net - своего рода аналог CPAN-а для Perl, решит эту проблему и сообщество наконец-таки определится с функцией split().

Поддержка ООП в Lua очень напоминает Perl, в том смысле, что в самом языке эта возможность не заложена, а реализуется подручными средствами - таблицами. Таблица в Lua - это по сути хеш, который при необходимости может притворяться массивом или списком. Тот факт, что конкретная реализация ООП отдана на откуп программистам открывает простор для творчества. Аналогичная ситуация и для Perl: на CPAN-е без труда можно найти более десятка различных ООП-фреймворков.

Пример

Лёгкость встраивания Lua в C и наоборот - просто поражает! Пример, который приводится ниже, состоит из двух частей: Lua и C. Lua-часть - maze_dfs.lua генерирует лабиринт (алгоритм Depth-First-Search) заданной ширины и высоты, а C-часть - maze_generator.c выводит его на экран. Для полноты картины, maze_generator.c предоставляет функцию external_rand_function(), которую Lua-часть программы вызывает для получения случайных чисел. Таким образом, С и Lua-код вызывают друг друга в рамках одной и той же программы.

Всё взаимодействие с Lua происходит через стек. C-код вначале помещает в него имя вызываемой функции, а затем и её аргументы. При вызове функции указывается сколько аргументов было передано и сколько ожидается результатов. Наверняка Форт-программисты найдут этот механизм очень знакомым!

Отмечу, что хоть лабиринт и возвращается в виде ASCII-картинки (строки), Lua позволяет передавать в обе стороны структуры произвольной сложности.
Если в вашей системе ещё не установлен Lua (в том числе development-часть) самое время сделать это прямо сейчас. Вот пример для Debian Lenny (см. примечание):
sudo apt-get install lua5.1 liblua5.1-0-dev
Примечание: для того чтобы установить Lua 5.1 в Debian Lenny потребуется добавить в /etc/apt/sources.list репозиторий с backport-ами:
deb http://backports.debian.org/debian-backports lenny-backports main
Компиляция программы:
gcc -o maze_generator -Wall `pkg-config lua5.1 --libs --cflags` maze_generator.c
Запуск:
./maze_generator ./maze_dfs.lua 15 10
Результат:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | | |
+ + + + + + +---+---+---+ + +---+---+---+ +
| | | | | | | | | |
+---+---+---+---+ + +---+ +---+ + + + + + +
| | | | | | | | |
+ +---+---+ +---+---+ +---+ +---+ +---+---+ +---+
| | | | | | | |
+---+---+ + +---+ + + +---+ +---+ +---+---+ +
| | | | | | | | |
+ +---+---+---+ +---+---+---+ + +---+---+ +---+ +
| | | | | | | |
+ +---+---+ +---+ + + + + + + +---+ + +
| | | | | | | | |
+ + +---+---+---+---+ +---+---+---+---+---+ +---+---+
| | | | | | | | |
+ +---+ + +---+ + + + + +---+ + + + +
| | | | | | | | | | |
+---+ + +---+ +---+---+ + + + +---+---+---+ +
| | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Понятно, при условии неизменности интерфейса, Lua-часть можно редактировать не меняя C-программы. К примеру, можно реализовать другой алгоритм генерации лабиринта и передать его в качестве аргумента вместо maze_dfs.lua

Заключение

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

На русскоязычной wiki-странице, посвященной Lua приводится список проектов в которых активно используется Lua. Список впечатляет. Есть и очень известный проект, название которого стало чуть ли ни вторым именем для Lua и по этой причине порядком набило оскомину.

Ссылки