3.6. Прогрессирующее сжатие изображений

Большинство современных методов сжатия изображений являются прогрессирующими (поступательными) или они легко делаются такими. Это особенно важно, если сжатое изображение передается по каналам связи, а затем декодируется и наблюдается получателем в режиме реального времени (например, это делается браузерами всемирной паутины). Когда такое изображение принимается и разжимается, декодер способен очень быстро показать всю картинку в формате с низким качеством, а затем постепенно улучшать качество по мере приема остальной части сжатого изображения и его декодирования. Пользователь, наблюдая на экране развитие образа, может распознать все особенности этого изображения после декодирования всего 5-10% от его размера.

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

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

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

Образование - это прогрессирующее обнаружение нашего невежества.
- Уил Дюрант

Мы уже упоминали прогрессирующее сжатие изображений в связи с алгоритмом JPEG (стр. 185). Этот алгоритм использует DCT для разделения образа на пространственные частоты и начинает сжатие с низкочастотных компонентов. Поэтому декодер может быстро показать соответствующую им грубую картинку. Высокочастотные компоненты содержат детали изображения.

Кроме того, полезно представлять себе прогрессирующее декодирование как процесс улучшения качества изображения во времени. Это можно сделать тремя путями:

1. Закодировать пространственные частоты изображения прогрессирующим образом. Наблюдатель, следящий за декодированием, увидит такое изображение изменяющимся от расплывшегося до резкого. Методы, которые работают подобным образом, имеют среднюю скорость кодирования и медленную скорость декодирования. Этот тип сжатия часто называется прогрессирующим по соотношению сигнал/шум, или прогрессирующим по качеству изображения.

2. Начать с черно-белого полутонового изображения, а потом добавить цвет и тени. При декодировании зритель с самого начала увидит изображение со всеми деталями, которые будут улучшаться по мере добавления цветов и красок. Метод векторного квантования применяет этот принцип компрессии. Такие алгоритмы отличаются медленным кодированием и быстрым декодированием.

Рис. 3.45. Последовательное декодирование.

3. Кодировать изображение по слоям, где ранние слои состоят из нескольких пикселов большого разрешения. Наблюдатель заметит постепенную детализацию картинки во времени при ее декодировании. Такой метод добавляет все новые детали по мере разжатия файла. Этот путь прогрессирующего сжатия называется пирамидальным или иерархическим кодированием. Большинство методов сжатия используют этот принцип, поэтому в этом параграфе обсуждаются общие идеи осуществления пирамидального кодирования. Рис. 3.46 иллюстрирует три принципа прогрессирующего сжатия, перечисленные выше. Они контрастируют с рис. 3.45, на котором изображены этапы последовательного декодирования.

Предположим, что изображение состоит из  пикселов. Простейший метод прогрессирующего сжатия, который приходит в голову, состоит в вычислении каждого пиксела слоя  в виде среднего группы 2х2 пикселов слоя . Значит, слой  - это исходное изображение ( пикселов размера 1), слой  состоит из  пикселов размера 2х2, и так далее до слоя  из одного большого пиксела размера , который представляет все изображение. Если изображение не слишком велико, то все слои можно сохранить в памяти компьютера. Затем слои записываются в файл в обратном порядке, начиная со слоя 1. Единственный пиксел слоя 1 является «родителем» четырех пикселов слоя 2, каждый из которых порождает по 4 пиксела слоя 3 и так далее. Этот процесс породит прогрессирующий файл образа, но без сжатия, поскольку общее число пикселов этой пирамиды равно

,

что на 33% больше размера исходного числа!

Простой метод приведения числа пикселов пирамиды к исходному числу  состоит в сохранении только трех пикселов слоя  из четырех и в вычислении четвертого с помощью трех его «братьев» и одного родительского пиксела этой группы из предыдущего слоя .

Пример: На рис. 3.47с дано изображение размера 4х4, которое является третьим слоем прогрессирующего сжатия. Второй слой показан на рис. 3.47b, где, например, пиксел 81.25 является средним значением четырех пикселов 90, 72, 140 и 23 из третьего слоя. Единственный пиксел первого слоя приведен на рис. 3.47а. Сжатый файл будет содержать только числа

54.125, 32.5, 41.5, 61.25, 72,23, 140, 33, 18, 21, 18, 32, 44, 70, 59, 16

(конечно, правильно закодированные) из которых легко восстановить недостающие пикселы. Например, отсутствующий пиксел 81.25 вычисляется из уравнения .

Проблема заключается в том, что среднее значение целых чисел может быть нецелым числом. Если мы хотим, чтобы пикселы оставались целыми, то придется или смириться с потерей точности, или сохранять все более и более длинные целые числа. Например, если исходные пикселы имеют 8 разрядов, то сложение четырех 8-ми битовых чисел дает 10-ти битовое число. Деление этого числа на 4 для вычисления среднего и округление до целого вновь приводит к 8 разрядам, но с возможной потерей точности.

Рис. 3.46. Прогрессирующее декодирование.

Если потеря точности нежелательна, то можно представить наш пиксел второго слоя в виде 10-ти битовых чисел, а пиксел первого слоя - с помощью 12 разрядов. На рис. 3.47d,e,f показан результат округления, при котором происходит некоторая потеря информации. Содержимым сжатого файла будет последовательность

54, 33, 42, 61, 72, 23, 140, 33, 18, 21, 18, 32, 44, 70, 59, 16.

Первый отсутствующий пиксел 81 второго слоя можно вычислить из уравнения . Получится число 80 с небольшой ошибкой.

Рис. 3.47. Прогрессирующее сжатие образа.

Лучшее решение заключается в использовании родителя группы при вычислении его четырех потомков. Это можно делать, вычисляя разность между родителем и его потомками и записывая эту разность (после подходящего кодирования) в слой  сжатого файла. Декодер восстанавливает разность и использует родителя из слоя  для вычисления значений четырех пикселов. Для кодирования разностей можно применять метод Хаффмана или арифметическое кодирование. Если все слои вычислены и находятся в памяти, то можно найти статистическое распределение этих разностей, которое можно использовать для достижения наилучшего статистического сжатия.

Если в памяти нет места для всех слоев, можно применить простую адаптивную модель. Она начинается присвоением счетчика 1 каждому значению разности (чтобы избегнуть проблему нулевой вероятности, см. [Salomon 2000]). После вычисления очередной разности, ей присваивается некоторая вероятность, и она кодируется, исходя из ее счетчика. После чего счетчик обновляется. Неплохо делать увеличение счетчика не на единицу, а на большее число. Тогда исходные единичные значения счетчиков быстро станут незначимыми.

Некоторого улучшения можно достигнуть, если использовать родительский пиксел при вычислении трех его потомков, а затем этих трех потомков и родителя использовать при вычислении четвертого пиксела данной группы. Если четыре пиксела группы равны а, b, с и d, то их среднее равно . Это среднее становится частью слоя , а слой  может содержать лишь три разности ,  и . После того как декодер прочтет и декодирует эти три разности, он может вычислить все четыре пиксела группы с помощью значения  из предыдущего слоя. Вычисление  с помощью деления на 4 все еще означает потерю двух битов, но эту двухбитовую величину можно выделить до деления и кодировать ее отдельно вслед за тремя разностями.

Родительский пиксел не обязан быть равен среднему значению группы. Можно, например, выбрать в качестве родительского максимальный (или минимальный) пиксел группы. Преимущество такого метода заключается в том, что родительский пиксел равен одному из его потомков. Кодер просто закодирует три пиксела группы, а декодер декодирует три пиксела (или их разности) и дополнит группу четвертым родительским пикселом. При кодировании последовательных групп слоя, кодер должен выбирать поочередно максимальное или минимальное значение в качестве родителя, поскольку выбор только одного экстремума породит темнеющие или светлеющие слои. Рис. 3.47g,h,i показывает три слоя для этого случая. В сжатом файле будут записаны числа

140, (0), 21, 72, 16, (3), 90, 72, 23, (3), 58, 33, 18, (0), 18, 32, 44, (3), 100, 70, 59,

где число в скобках имеет длину в 2 бита. Оно говорит о том, в какой квадрант поместить родительский пиксел. Заметим, что квадранты занумерованы следующим образом:

.

Выбор медианы группы производится несколько медленнее нахождения максимума или минимума, но улучшает динамику проявления слоев при прогрессирующей декомпрессии. По определению, медианой последовательности чисел  называется элемент , такой, что половина (или почти половина) элементов последовательности меньше , а другая половина - больше . Если четыре элемента группы пикселов удовлетворяют неравенству , то медианой будет служить число  или . Основное достоинство выбора медианы для родительского пиксела заключается в том, что это позволит сгладить большие разности значений пикселов. В группе 1, 2, 3, 100 выбор в качестве родителя числа 2 или 3 является более характерным для этой группы, чем выбор среднего числа. Нахождение медианы требует двух сравнений, а для вычисления среднего понадобится деление на 4 (или правый сдвиг).

Если используется медиана при кодировании слоя , то оставшиеся три пиксела можно кодировать в слое  с помощью их разностей, за которыми следует 2-х битовый код, сообщающий, который из четырех был родительским. Другое небольшое преимущество использования медианы заключается в том, что когда декодер читает этот 2-х битовый код, то ему становится известно, сколько из трех пикселов больше медианы, а сколько меньше. Например, если этот код говорит, что один пиксел меньше медианы, а два другие - больше, а прочитанный пиксел меньше медианы, то декодер точно знает, что оставшиеся пикселы будут больше медианы. Полученная информация изменяет распределение разностей пикселов, и это преимущество может быть реализовано с помощью трех таблиц счетчиков для определения вероятностей при кодировании разностей. Одна таблица используется при кодировании пикселов при условии, что декодер знает, что они больше медианы. Другая таблица применяется для кодирования, если известно, что пиксел меньше медианы. А третья таблица работает, если декодер не знает заранее их соотношение с медианой. Это обстоятельство улучшает сжатие на несколько процентов и показывает, как добавление новых признаков в метод сжатия дает общее уменьшение сжатого файла.

Некоторые методы прогрессирующего сжатия, используемые на практике, такие, как SPIHT и EZW, изложены в [Salomon 2000].