Source of information: http://psb.sbras.ru/ws/show_abstract.dhtml?ru+32+2781
В данном докладе описывается ERI97 - семейство быстрых высокоэффективных алгоритмов сжатия цифровой графической информации без потерь. Важнейшей частью ERI97 является сортировка параллельных блоков (Parallel Blocks Sorting, PBS). Поскольку она описывается впервые, о ней будет подробно рассказано отдельно. ERI97, как и PBS, - алгоритмы блочные, трансформирующие. Размер данных в результате применения ERI97 и PBS не изменяется.
Не будут рассмотрены следующие важные сопутствующие алгоритмы:
1. Анализ графического блока
2. Фрагментирование блока
3. Отделение шума
4. Выбор оптимальных параметров, задаваемых алгоритму ERI97
5. Сжатие результата работы алгоритма (здесь может быть применена любая комбинация других методов - RLE, LPC, MTF, DC, Huffman, Arithmetic, ENUC, SEM...)
Основные свойства описываемой группы алгоритмов:
1. Размер получаемых данных равен размеру задаваемых данных плюс A байт служебной информации (A зависит только от параметров, задаваемых алгоритму).
2. Скорость работы ERI97 сравнима со скоростью аналогов - JPEG, PNG, LOCO - но качество достигаемого cжатия - уже сейчас лучше на 10%-70% (не вариант JPEG-а без потерь, а именно JPEG с потерями, но лучшим качеством).
3. Алгоритм состоит из последовательности четырех независимых действий, причем
* каждое из них работает с каждым пикселом (элементом изображения);
* любые из них могут быть пропущены при прямой и затем при обратной трансформации;
* "сжимающая" трансформация (компрессор) осуществляет их в прямом порядке, а "разжимающая" трансформация (декомпрессор) - в обратном.
4. Скорость работы компрессора в общем случае равна скорости декомпрессора и зависит только от размера данных, но не от их содержания: Ск=O(размер)
5. Памяти требуется 2*(размер входных данных)+C.
6. В общем случае отсутствуют операции умножения и деления.
7. Число N компонент каждого пиксела, как и разрядность пикселов R, являются двумя из множества задаваемых параметров, и могут быть произвольными.
Алгоритм был реализован в компьютерной программе ERI32 в 1997-ом году и активно совершенствуется в течение последних четырех лет. В настоящее время ERI32 достигает лучших результатов среди всех известных аналогов по сжатию без потерь малошумных 24-битных изображений. Причем как по качеству сжатия, так и по общему суммарному показателю, учитывающему также и скорости сжатия и разжатия.
Основные отличия реализации - программы ERI32 (последняя версия на текущий момент - 15-е ноября 2001-го года - 4.19fre):
1. Примерно десять внешне задаваемых параметров.
2. В настоящее время поддерживается только режим N=3, R=8, то есть каждый пиксел состоит из трех 8-битных компонент.
3. Байт-ориентированность: операции над битами по возможности сведены к минимуму, что многократно увеличивает скорость работы, но немного ухудшает качество сжатия.
Почему именно 24 бита, то есть три восьмибитных компоненты?
1. Это самый распространенный формат, подавляющее большинство полноцветных изображений хранится, передается и обрабатывается именно в таком формате.
2. С точки зрения восприятия полноцветной графики человеком, 16-и битов явно недостаточно, а 32-х гораздо более чем достаточно, хотя и удобнее для обработки 32-битными процессорами семейства х86.
3. С точки зрения сжатия, каковы бы ни были компоненты - RGB, CMYK, HSB, YCrCb или иное, и каковы бы ни были R и N, - желательно чтобы произведение R*N было кратно трем (а поскольку чаще всего R - степень двойки, именно N должно быть кратно трем). Причина этого вот в чем: из всего множества 2^(R*N) возможных цветов в каждом изображении используется, как правило, менее одного процента цветов. Поэтому эти подмножества использованных цветов можно представлять себе как сгустки в N-мерном кубе с ребром длиной 2^R. Тогда, в "идеальном" для сжатия случае, эти D скоплений
1. не пересекаются, и
2. их проекции на ребра куба обладают свойствами:
(а) длины близки к степеням двойки: Lij= 2^Xij, i=1...D, j=1...N.
(б) их границы выровнены по длинам: Bij=K*2^Xij, i=1...D, j=1...N.
И тогда выгодно разделять и обрабатывать отдельно:
1. "детерминирующие" биты, т.е. указывающие на сектор с одним скоплением;
2. "детерминированные" биты, указывающие на положение скопления внутри сектора;
3. "шумовые" биты, указывающие на положение точки внутри скопления, их обычно нет, если изображение получено не оцифровкой, а синтезировано алгоритмом. Учитывая, что, как правило, каждый из N компонентов хранится в отдельном байте с уникальным адресом, хорошо, когда N кратно трем, и можно отвести по N/3 байтов под "детерминирующие", "детерминированные" и "шумовые" биты.
Четыре действия, из которых и состоит ERI97, компрессор выполняет в следующем порядке:
1. Первичная обработка
2. Контекстная обработка
3. Обход плоскости
4. PBS, Сортировка параллельных блоков
Первые три действия в том или ином виде присутствуют во всех аналогичных методах. Первые два действия не имеют отношения к PBS и могут совершаться отдельно, практически никак не ориентируясь на последующую PBS. Более того, каждое из них может выполняться параллельно, распадаясь на P процессов, причем возможные значения P - от 1 до S, где S - число пикселов в обрабатываемом блоке. Первое действие настолько тривиально, что в практической реализации легко может быть совмещено со вторым. Тем не менее, поскольку логически это разные действия, в описании алгоритма они идут отдельно.