2.3 Алгоритмы сжатия без потерь полутоновых изображений
Спектральный метод сжатия лежит в основе алгоритма JPEG 2000, который, являясь, вообще говоря, алгоритмом сжатия изображений с потерями, предусматривает также режим сжатия без потерь. Он основан на представлении сжатого изображения в виде его вейвлет-спектра, т. е. набора параметров его вейвлет-составляющих, полученных посредством специального целочисленного вейвлет-преобразования [16].
Алгоритм JPEG-XR (HD Photo) основан на JPEG и использует высокопроизводительное обратимое преобразование цветового пространства, обратимое биортогональное преобразование и расширенную схему неарифметического энтропийного кодирования [17]. Алгоритм поддерживает сжатие без потерь и серые изображения. Поскольку все используемые образования обратимы, кодек поддерживает режим сжатия с потерями и без, используя один алгоритм.
Алгоритм CREW (compression with reversible embedded wavelets) основывается на вейвлет-преобразованиях с использованием так называемой «обратимой» аппроксимации одного из лучших вейвелет-фильтров. Обратимые вейвлеты – линейные фильтры с нелинейным округлением, которые реализуют точное восстановление. Реализация алгоритма в свободном доступе отсутствует. [Error: Reference source not found].
К алгоритмам сжатия с предсказанием относятся далее перечисленные алгоритмы.
Алгоритм FELICS строится на основе последовательного сканирования изображения слева направо, сверху вниз, с предсказанием интенсивности каждого последующего пикселя на основе интенсивностей уже закодированных двух предыдущих.
Алгоритм JPEG-LS (lossless JPEG) основан на методе LOCO-I (Low Complexity Lossless Compression for Images). Алгоритм сжатия без потерь LOCO-I, принятый за основу при разработке стандарта JPEG-LS, предусматривает не только режим «lossless», но и «near lossless» (сжатие с ограниченными, задаваемыми пользователем потерями).
Lossless JPEG использует предсказание интенсивности пикселя, используя интенсивности трех ближайших соседних пикселей: верхнего, левого и верхнего левого пикселей, а для сжатия разницы интенсивностей пикселей используется энтропийное сжатие
Алгоритм PWC (Piecewise-Constant Image Mode) – алгоритм сжатия палитровых изображений. Основывается на использовании предсказании неизвестных цветов палитры за счет вычисления вероятности появления неизвестного цвета на основе известных соседних цветов [19].
Алгоритм Glicbawls использует одиночный линейный предиктор (предсказатель), веса которого пересчитываются для каждого пикселя с применением алгоритма наименьших квадратов, принимая во внимание все предыдущие пиксели. Вклад каждого пикселя в алгоритм наименьших квадратов взвешивается фактором, рассчитываемым по определенным правилам [20].
Алгоритм TMW использует модель, использующую, в отличие от алгоритма Glicbawls, не одиночный предиктор, а набор линейных предикторов, включающих в себя [21]: пиксель-предикторы, предсказывающие значение пикселей, основанное на значениях случайных соседних пикселей; сигма-предикторы, предсказывающие величину ошибки прогноза пиксель-предиктора, основанную на величине прогноза ошибки пиксель-предиктора случайных соседних пикселей; смешанные предикторы, которые прогнозируют, насколько корректно определенный пиксель-предиктор прогнозирует параметры пикселя, в зависимости от ошибок предсказания случайных соседних пикселей. В настоящее время не существует корректной реализации данного алгоритма.
Алгоритм MRP основывается на использовании, основанных на квадродереве адаптивных предикторов с минимальным рейтингом и улучшенным механизмом взвешивания ошибок предсказания [22].
Алгоритм WLS базируется на методе взвешенных наименьших квадратов для адаптивных предикторов. Каждому наблюдению присваивается определенный вес, в соответствии с уровнем информации, которую оно несло. Вес назначается в соответствии со схожестью текущего пикселя и особенностями исследуемых пикселей [23]. В настоящее время полного описания алгоритма в свободном доступе нет. Алгоритм WLS по сжатию в сравнении с алгоритмом MRP дает результаты ниже в среднем на 10%.1
Алгоритм EDP (Edge-Directed Prediction) основан на схеме адаптивного предсказания на наименьших квадратах [24] В основе идеи алгоритма лежит улучшение lossless-JPEG локальной оптимизацией коэффициентов предсказания. За счет увеличения расхода памяти на хранение коэффициентов предиктора достигается уменьшение вычислительной сложности, позволяющей решать задачу компрессии на обычном ПК.
Алгоритм APT основывается на комбинации предсказания и энтропийного кодирования. Он состоит в последовательном выполнении следующих операций [25]: упорядочивания данных (отсчетов интенсивностей пикселей) в мультикомпонентной бинарной пирамиде, применяющей эмпирически оптимизированный нелинейный предиктор; устранения межкомпонентной избыточности; кодирования с использованием HEX-деревьев; адаптивного кодирования длин серий/кодирования Хаффмана [25].
Алгоритм CALIC также основывается на комбинации предсказания и энтропийного кодирования, которое может быть реализовано арифметическим кодированием или кодированием Хаффмана [26]. При этом алгоритмы CALIC и APT схожи по производительности, однако, на некоторых классах изображений APT уступает CALIC[25].
Алгоритм PGF использует комбинацию обратимого вейвлет-преобразования, поддерживая режим сжатия с потерями и без потерь и кодирования длин серий. Включает: преобразование цветового пространства, дискретное вейвлет-преобразование [27].
Алгоритм DPCM основывается на импульсно-кодовой модуляции, но использует дополнительные возможности компактного кодирования на основе прогноза отсчетов сигнала [14]. Корректной реализации алгоритма не существует [28].
Алгоритм BTPC базируется на комбинации бинарного представления изображения, кодировании Хаффмана, кодировании с предсказанием [14,29].
На комбинации энтропийного кодирования и контекстного кодирования базируется алгоритм CTW (взвешивание с применением контекстных деревьев). Данный алгоритм основывается на представлении последовательности двоичных слов, описывающих сжимаемое изображение, последовательностью кодов переменной разрядности, являющейся функцией от вероятности появления того или иного слова в исходном двоичном описании кодируемого изображения. Указанные вероятности при этом оцениваются посредством структур, именуемых контекстными деревьями [7, 30].
Алгоритм GraLIC также основывается на энтропийном кодировании и контестном предсказании. Подробное описание алгоритма отсутствует [31].
Алгоритм EIDAC(embedded image-domain adaptive compression) основывается на на контекстном моделировании и арифметическом кодировании. Использует бинарный многслойный контекст, который определяется соседними с текущей битовой картой значениями пикселей. Используется только для простых изображений и неэффективен для использования в области диагностических изображений. Алгоритм имеет качественное математическое обоснование, но не имеет практически применимой реализации. [Error: Reference source not found]
На контекстном моделировании основывается алгоритм PAQ, использует смешивание контекстов, в котором вероятность появления следующего символа вычисляется на основе взвешенной комбинации большого числа моделей, зависящих от разных контекстов. Строго говоря, алгоритм PAQ является алгоритмом для сжатия любых данных, однако, для изображений BMP алгоритм имеет специализированные модели сжатия [32].
Отдельно нужно выделить алгоритмы сжатия BMF и ERI. Эти алгоритмы, по-сути, не являются алгоритмами сжатия изображений, однако, достигают высокой степени компрессии, в том числе и изображений.
Для алгоритма BMF не существует открытого описания [33]. Известно, тем не менее, что алгоритм является алгоритмом сжатия без потерь для изображений. Поддерживается широкий спектр входных форматов изображений. Алгоритм дает хороший, по сравнению с другими методами, результат сжатия [34].
Алгоритм ERI основывается сортировке параллельных блоков. Заключается в последовательном разбиении изображения на блоки и подсчете пикселей в каждом из них. Заявлено, что алгоритм достигает мирового рекорда при сжатии 24-битных изображений [35].
На рисунке 2 .3 приведена классификация алгоритмов сжатия без потерь полутоновых изображений.
Рисунок 2.1 – Классификация алгоритмов сжатия без потерь полутоновых изображений
Необходимо заметить, что такие параметры, как формат входного изображения, разрядность, возможность использования шифрования и автопрофилирование зависят от реализации алгоритма. В таблице 1 приведем реализации, доступные в интернет, тех или иных алгоритмов и их характеристики.
Таблица 2.2 – Параметры алгоритмов сжатия без потерь полутоновых изображений
Алго-ритм
|
Формат входного изображения
|
Бит на пиксель вх. изобр.
|
Исп. ли шиф-ро-вание
|
Алго-ритм за-щиты
|
Авто-
профили-рование
|
Параметры профиля
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
APT
|
PBM, PPM, PGM
|
1-16
|
нет
|
–
|
нет
|
–
|
BMF
|
BMP, TGA, PNM, RAS,
GIF, RAW
|
1-32
|
нет
|
–
|
нет
|
использовать ли фильтры;
качество выбранного фильтра;
использовать медленную эффективную компрессию.
|
BTPC
|
PBM, PPM, PGM
|
1-24
|
нет
|
–
|
нет
|
–
|
CALIC
|
DAT, IMG,
PPM
|
8-16
|
нет
|
–
|
нет
|
использовать ли бинарный режим
|
CREW
|
–
|
–
|
–
|
–
|
–
|
–
|
CTW
|
|
|
нет
|
–
|
|
максимальная глубина дерева;
максимальное число префиксных деревьев;
максимальное число узлов;
запрет образования дерева;
взвешивать ли корневые узлы;
использовать оценщик Кричевского-Трофимова.
|
DPCM
|
–
|
–
|
–
|
–
|
–
|
–
|
EIDAC
|
–
|
–
|
–
|
–
|
–
|
–
|
ERI
|
|
|
|
|
|
метод компрессии;
размер основного блока;
размер разделяемого блока;
уменьшить шум
|
FELICS
|
PGM
|
8
|
нет
|
–
|
нет
|
максимальный показатель кода Райса.
|
GraLIC
|
PNM
|
8
|
нет
|
–
|
нет
|
–
|
JPEG-2000
|
PGM, PGX
|
1-32
|
Воз-мож-но2
|
AES
|
нет
|
количество слоев декомпозиции3.
|
Окончание таблицы 2.1
1
|
2
|
3
|
4
|
5
|
6
|
7
|
JPEG-LS
|
PPM, PGM
|
8-16
|
нет
|
–
|
час-тич-ное
|
Ta (пороговое значение пиксела предсказания);
Tb;
Tc;
интервал сброса;
режим для мультикомпонентных изображений;
максимально разрешенные потери на символ;
использовать таблицу отображения;
интервал перезапуска.
|
JPEG-XR
|
BMP, TIFF, HDR
|
1– 32
|
нет
|
–
|
час-
тич-ное4
|
размер кодируемого блока;
качество выходного изображения;
формат входного изображения;
хроматическая субдискретизация;
уровень перекрытия;
частотный порядок битового потока;
макро-блоки по строкам;
макро-блоки по столбцам;
количество макро-блоков;
формат альфа-канала;
качество плоского альфа-канала;
степень отсечения флексбитов;
пропуск подзон.
|
MRP
|
PGM
|
8
|
нет
|
–
|
пол-ное
|
число предикторов;
порядок предсказания;
точность коэффициентов предсказания;
число вероятностных моделей;
точность моделей;
число итераций.
|
PAQ
|
*
|
*
|
нет
|
–
|
нет
|
количество используемой памяти.
|
PWC
|
PBM, PGM, BMP
|
8–16
|
нет
|
–
|
нет
|
максимальное число lps;
принимать ли Q2 решения;
принимать ли Q5 решения;
является ли палитра серой;
режим форсирования;
кодирование снизу вверх.
|
TMW
|
PGM
|
8–16
|
–
|
–
|
–
|
–
| |
