Методы сжатия информации в полиграфии

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

2. Полутоновое  изображение. Каждый пиксел такого  изображения может иметь   значений от 0 до  , обозначающих одну из   градаций серого (или иного) цвета. Число   обычно сравнимо с размером байта, то есть, оно равно 4, 8, 12, 16, 24 или другое кратное 4 или 8. Множество самых значимых битов всех пикселов образуют самую значимую битовую плоскость или слой изображения. Итак, полутоновое изображение со шкалой из   уровней составлено из   битовых слоев.

3. Цветное изображение.  Существует несколько методов  задания цвета, но в каждом  из них участвуют три параметра.  Следовательно, цветной пиксел  состоит из трех частей. Обычно, цветной пиксел состоит из  трех байтов. Типичными цветовыми  моделями являются RGB, HLS и CMYK.

4. Изображение  с непрерывным тоном. Этот тип  изображений может иметь много  похожих цветов (или полутонов). Когда  соседние пикселы отличаются  всего на единицу, глазу практически  невозможно различить их цвета.  В результате такие изображения  могут содержать области, в  которых цвет кажется глазу  непрерывно меняющимся. В этом  случае пиксел представляется  или большим числом (в полутоновом  случае) или тремя компонентами (в  случае цветного образа). Изображения  с непрерывным тоном являются  природными или естественными  (в отличие от рукотворных,  искусственных); обычно они получаются  при съемке на цифровую фотокамеру  или при сканировании фотографий  или рисунков.

5. Дискретно-тоновое  изображение (оно еще называется  синтетическим). Обычно, это изображение  получается искусственным путем.  В нем может быть всего несколько  цветов или много цветов, но  в нем нет шумов и пятен  естественного изображения. Примерами  таких изображений могут служить  фотографии искусственных объектов, машин или механизмов, страницы  текста, карты, рисунки или изображения  на дисплее компьютера. (Не каждое  искусственное изображение будет  обязательно дискретно-тоновым.  Сгенерированное компьютером изображение,  которое должно выглядеть натуральным,  будет иметь непрерывные тона, несмотря на свое искусственное  происхождение.) Искусственные объекты,  тексты, нарисованные линии имеют  форму, хорошо определяемые границы.  Они сильно контрастируют на  фоне остальной части изображения  (фона). Прилегающие пикселы дискретно-тонового  образа часто бывают одиночными  или сильно меняют свои значения. Такие изображения плохо сжимаются  методами с потерей данных, поскольку  искажение всего нескольких пикселов  буквы делает ее неразборчивой,  преобразует привычное начертание  в совершенно неразличимое. Методы  сжатия изображений с непрерывными  тонами плохо обращаются с  четкими краями дискретно-тоновых  образов, для которых следует  разрабатывать особые методы  компрессии. Отметим, что дискретно-тоновые  изображения, обычно, несут в себе  большую избыточность. Многие ее  фрагменты повторяются много  раз в разных местах изображения.

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

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

На настоящий  момент известны два наиболее широко распространенных алгоритма сжатия с потерей информации: JPEG и JPEG2000. Алгоритм JPEG имеет в своей основе дискретное косинусное преобразование (ДКП), которое применяется к неперекрывающимся  блокам изображения размером 8х8 пикселов. Данный метод сжатия изображений  был исследован в большом числе  работ [1-3]. К основным недостаткам  данного метода относятся: распад кодируемого  изображения на отдельные блоки  по 8х8 пикселов при больших коэффициентах  сжатия; появление ложных контуров; плохое описание нестационарного во времени сигнала коэффициентами Фурье-преобразования. Для преодоления  указанных недостатков был предложен  новый стандарт сжатия изображений JPEG2000, основу которого составляет вейвлет-преобразование. В этом случае все изображение  раскладывается по базисным вейвлет-функциям, локализованным как во временной, так  и в частотной областях. Это  дает возможность создавать алгоритмы  быстрого вейвлет-преобразования, а  также не разбивать изображение  на отдельные независимые блоки. Благодаря такому подходу в вейвлет-коэффициентах  образуются длинные цепочки подряд идущих нулей, которые эффективно сжимаются  энтропийными кодерами. 
 

2. Алгоритм RLE.

Алгоритм необычайно прост в реализации. Групповое  кодирование — от английского Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации  графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

В первом алгоритме  признаком счетчика служат единицы  в двух верхних битах считанного файла:

Соответственно  оставшиеся 6 бит расходуются на счетчик, который может принимать  значения от 1 до 64. Строку из 64 повторяющихся  байтов мы превращаем в два байта, т.е. сожмем в 32 раза.

Алгоритм рассчитан  на деловую графику — изображения  с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма  не так уж редка. Ее можно легко  получить, применяя групповое кодирование  к обработанным цветным фотографиям. Для того, чтобы увеличить изображение  в два раза, его надо применить  к изображению, в котором значения всех пикселов больше двоичного 11000000 и  подряд попарно не повторяются. Данный алгоритм реализован в формате PCX. 

Второй вариант  этого алгоритма имеет больший  максимальный коэффициент архивации  и меньше увеличивает в размерах исходный файл.

Признаком повтора  в данном алгоритме является единица  в старшем разряде соответствующего байта:

Как можно легко  подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в  худшем увеличивает на 1/128. Средние  показатели степени компрессии данного  алгоритма находятся на уровне показателей  первого варианта. Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.  

3. Алгоритм LZW

Название алгоритм получил по первым буквам фамилий  его разработчиков — Lempel, Ziv и Welch. Сжатие в нем осуществляется за счет одинаковых цепочек байт.  Процесс  сжатия выглядит достаточно просто. Мы считываем последовательно символы  входного потока и проверяем, есть ли в созданной нами таблице строк  такая строка. Если строка есть, то мы считываем следующий символ, а  если строки нет, то мы заносим в  поток код для предыдущей найденной  строки, заносим строку в таблицу  и начинаем поиск снова. LZW реализован в форматах GIF и TIFF.

Алгоритм LZW имеет  несколько особенностей своей реализации в формате сжатия изображений gif. Первая особенность – это переменный размер кода таблицы цепочек, который  не может превышать 12 бит, т.е. не превышать  числа 4095. Вторая особенность состоит  в использовании двух специальных  кодов – это код обновления (реинициализации) таблицы цепочек, и код завершения потока символов .

В самом начале своей работы алгоритм определяет количество цветов, используемых в изображении. В случае GIF их максимум может быть 256, т.к. любое изображение, даже с  большим набором цветов преобразуется  в 256 цветовое пространство. Минимум  может быть 2 цвета. Если используется только два цвета, то начальный размер кодов в таблице равен 3 битам. Причем коду 0 ставится цвет 0, а коду 1 – цвет 1. Коды 4 и 5 соответствуют  коду очистки таблицы и коду. При большем количестве цветов размер кода таблицы равен числу бит N, приходящихся на один пиксел. При этом специальные коды равны. Начальный размер кодов в таблице записывается в заголовок GIF файла.

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

Разработчики  формата GIF ограничили максимальный размер кодов в таблице 12 битами. Это  значит, что когда код достигает  значения, то размер увеличивать уже  нельзя. Но в то же время и размер кодов становится больше 12 бит. Как  разрешить данную ситуацию? Простым  решением является выполнить перегенерирование  таблицы последовательностей, после  чего она будет содержать только цепочки длины, равной 1, т.е. значения пикселей и плюс специальные коды. Таким образом, она перейдет в  то же состояние, в котором была на момент начала кодирования изображения. А для того, чтобы декодировщик знал, что в определенный момент произошло перегенерирование таблицы, кодировщик в выходной поток записывает код управляющего символа.  

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

Особенность LZW заключается в том, что для  декомпрессии нам не надо сохранять  таблицу строк в файл для распаковки. Алгоритм построен таким образом, что  мы в состоянии восстановить таблицу  строк, пользуясь только потоком  кодов. 

4. Алгоритм  ДИКМ и JPEG-LS

Данный метод  кодирования основывается  на предположении наличия корреляционной связи между соседними отсчетами изображения. В этом случае значение последующего отсчета   оценивается на основе предыдущих   Полученная оценка   используется для формирования разностного сигнала  , которая будет тем меньше, чем точнее построена текущая оценка. Можно доказать, что при наличии корреляционной зависимости между отсчетами сигнала, дисперсия ошибок оценивания   будет меньше дисперсии исходного сигнала  . Следовательно для представления   можно использовать меньше уровней, чем для сигнала  , т.е. каждый отсчет может быть представлен не 8 битами, а меньшим числом – обычно 4 битами.

В общем случае оценка элемента строится на основе линейной комбинации нескольких предыдущих отсчетов:

,

где   - набор весовых коэффициентов, которые выбираются из условия минимума дисперсии ошибки  : .

Вектор весовых  коэффициентов   можно найти путем дифференцирования данного выражения и приравнивания результат нулю.

Полученная ошибка подвергается равномерному квантованию  с шагом   согласно следующей формуле:

.

В результате возникает  шум квантования  . Для того, чтобы величина шума не накапливалась при восстановлении сигнала, оценки элементов   строят на основе восстановленных значений. Таким образом получаем следующую схему алгоритма кодирования.

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

Затем, полученные целочисленные разности сжимаются  кодами Хаффмана и формируется выходной файл сжатого изображения. Алгоритм ДИКМ строит прогноз на основе предыдущих значений отсчетов. Однако известно, что  лучший прогноз можно построить, если использовать не только предыдущие, но и последующие отсчеты в  изображении относительно оцениваемого. Алгоритм, использующий эту идею при  построении оценок прогноза пикселов изображения носит название «иерархическая сеточная интерполяция». 

5. Стандарт сжатия JPEG

Алгоритм разработан группой экспертов в области  фотографии (Joint Photographic Expert Group) специально для сжатия 24-битных и полутоновых  изображений в 1991 году. Этот алгоритм не очень хорошо сжимает двухуровневые  изображения, но он прекрасно обрабатывает изображения с непрерывными тонами, в которых близкие пикселы обычно имеют схожие цвета. Обычно глаз не в состоянии заметить какой-либо разницы при сжатии этим методом в 10 или 20 раз.

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