11.5. Другие алгоритмы

Векторное квантование. Метод сжатия посредством предварительного разбиения изображения на небольшие блоки и представления этих блоков в виде векторов. Такие векторы кодируются с использованием уникальных кодовых слов из словаря этих слов, так что передаче (или хранению) подлежат не сами векторы, а их коды. Очевидно, что словарь кодов (или кодовая книга) должен передаваться вместе с кодовыми последовательностями.

Фрактальный алгоритм. Фрактальная архивация основана на представлении изображения в компактной форме с помощью коэффициентов системы итерируемых функций (Iterated Function System - IFS [11.7]). IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое (машина Барнсли). В процессе итераций получается изображение, которое перестает изменяться. Это изображение называется «неподвижной точкой» (или аттрактором) данной IFS. Соответствующая теория гарантирует наличие ровно одной неподвижной точки для каждой IFS. Более того, система итерируемых функций задает фрактал (в определенном смысле самоподобный математический объект). Фактически фрактальное сжатие - это поиск самоподобных областей в изображении и определение для них Ваметров аффинных преобразований, что требует чрезвычайно много времени. Поэтому исследования сейчас направлены на решение данной проблемы.

Достаточно давно велась работа по стандартизации сжатия изображений. The Joint Photographic Experts Group (JPEG) - подразделение в рамках ISO — Международной организации по стандартизации разработало международный стандарт для полноцветных (24-битовых) изображений [11.8]. Этот стандарт - JPEG — один из мощных алгоритмов сжатия. Для него реализованы четыре варианта сжатия:

- последовательное, основанное на ДКП, сжатие;

- прогрессивный вариант ДКП-сжатия, использующий пирамидальное представление изображений;

- последовательное, основанное на предсказании сжатие без потерь (JPEG-Losless);

- иерархическое сжатие, соответственно с потерями и без потерь.

Оперирует алгоритм областями 8x8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при разложении матрицы такой области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты. Кроме того, система цветового восприятия человека слабо распознает определенные частоты (цветовое изменение картинки). Поэтому можно аппроксимировать некоторые коэффициенты более грубо без заметной потери качества изображения, используя для этого квантование коэффициентов. При таком преобразовании теряется часть информации, но могут достигаться большие коэффициенты сжатия.

Рассмотрим поэтапно основные процедуры алгоритма, считая, что сжимается 24-битовое изображение [11.2].

Этап 1. Переводим изображение из цветового пространства RGP с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета пиксела, в цветовое пространство YCrCb (иногда называют YUV). В нем Y — яркостная составляющая, a Cr, Сb - компоненты, отвечающие за цвет (хроматический красный и хроматический синий). За счет того, что человеческий глаз менее чувствителен к вариациям цветовой компоненты, чем к яркости, появляется возможность архивировать массивы для Сr и Сb составляющих с большими потерями и соответственно большими коэффициентами сжатия. Подобное преобразование уже давно используется в телевидении.

Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить так:

.

Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу.

.

Этап 2. Разбиваем исходное изображение на матрицы 8x8. Формируем из каждой три рабочие матрицы ДКП — по 8 бит отдельно для каждой компоненты. При больших коэффициентах сжатия этот шаг может выполняться чуть сложнее.

Этап 3. Применяем ДКП к каждой рабочей матрице. При этом получаем матрицу, в которой коэффициенты в левом верхнем углу соответствуют низкочастотной составляющей изображения, а в правом верхнем — высокочастотной.

Этап 4. Производим квантование коэффициентов. В принципе это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае задаем свою матрицу квантования (МК),  например для :

.

На этом шаге осуществляется управление степенью сжатия и происходят самые большие потери. Понятно, что, задавая МК с большими коэффициентами, получаем больше нулей и, следовательно, большую степень сжатия. В стандарт JPEG включены рекомендованные разработчиками МК, построенные опытным путем. Матрицы для большего или меньшего коэффициентов сжатия получают путем умножения исходной матрицы на некоторое (рекомендованное) число gamma.

С квантованием связаны и специфические эффекты алгоритма. При больших значениях числа gamma потери в низких частотах могут быть настолько велики, что восстановленное изображение распадется на квадраты 8x8 . Потери в высоких частотах могут проявиться в так называемом эффекте Гиббса, когда вокруг контуров с резким переходом цвета образуется своеобразный «нимб».

Этап 5. Переводим матрицу квантованных коэффициентов 8х8 в 64-элементный вектор при помощи «зигзаг»-сканирования, когда берутся элементы с индексами В результате, в начале вектора получаем трансформанты, соответствующие низким частотам, а в конце — высоким.

Этап 6. Свертываем вектор с помощью алгоритма группового кодирования (RLE). При этом получаем Вы типа (пропустить, число), где пропустить является счетчиком пропускаемых нулей, а число — значением, которое необходимо поставить в следующую ячейку. Так, вектор 42 3000-2 0000 1 ... будет свернут в Вы .

Этап 7. Свертываем получившиеся Вы кодированием по Хаффману с фиксированной кодовой таблицей.

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10... 15 раз без серьезных потерь.