3.6. Прогрессирующее сжатие изображенийБольшинство современных методов сжатия изображений являются прогрессирующими (поступательными) или они легко делаются такими. Это особенно важно, если сжатое изображение передается по каналам связи, а затем декодируется и наблюдается получателем в режиме реального времени (например, это делается браузерами всемирной паутины). Когда такое изображение принимается и разжимается, декодер способен очень быстро показать всю картинку в формате с низким качеством, а затем постепенно улучшать качество по мере приема остальной части сжатого изображения и его декодирования. Пользователь, наблюдая на экране развитие образа, может распознать все особенности этого изображения после декодирования всего 5-10% от его размера. Это можно сравнить со сжатием растрово-сканированных изображений. Когда изображение сканируется и сжимается по строкам сверху вниз, а потом декодируется последовательно, пользователь обычно не может многое узнать о нем, наблюдая на дисплее лишь 5-10% от всего изображения. Поскольку картинки будут рассматриваться людьми, прогрессирующее сжатие является более предпочтительным, даже если оно, в целом, работает медленнее и имеет меньшую эффективность, чем непрогрессирующее сжатие. Для того, чтобы лучше понять прогрессирующее сжатие, представьте себе, что кодер сначала сжимает самую важную часть изображения и помещает ее в файл, затем сжимается менее важная информация и добавляется в сжатый файл и так далее. Это объясняет также, почему потерю информации при прогрессирующем сжатии можно контролировать естественным образом: достаточно остановить сжатие в некоторой точке. Пользователь может менять долю опущенной информации с помощью параметра, который сообщает кодеру, как долго следует продолжать процесс сжатия. Чем раньше произойдет эта остановка, тем выше будет степень сжатия и тем больше будет размер утерянной информации. Другое преимущество прогрессирующего сжатия становится несомненным, когда сжатый файл должен разжиматься много раз и каждый раз с разным разрешением. Декодер может в каждом случае остановить процесс декодирования, когда изображение достигло разрешения, доступного данному устройству. Образование - это прогрессирующее обнаружение нашего невежества.
Мы уже упоминали прогрессирующее сжатие изображений в связи с алгоритмом JPEG (стр. 185). Этот алгоритм использует DCT для разделения образа на пространственные частоты и начинает сжатие с низкочастотных компонентов. Поэтому декодер может быстро показать соответствующую им грубую картинку. Высокочастотные компоненты содержат детали изображения. Кроме того, полезно представлять себе прогрессирующее декодирование как процесс улучшения качества изображения во времени. Это можно сделать тремя путями: 1. Закодировать пространственные частоты изображения прогрессирующим образом. Наблюдатель, следящий за декодированием, увидит такое изображение изменяющимся от расплывшегося до резкого. Методы, которые работают подобным образом, имеют среднюю скорость кодирования и медленную скорость декодирования. Этот тип сжатия часто называется прогрессирующим по соотношению сигнал/шум, или прогрессирующим по качеству изображения. 2. Начать с черно-белого полутонового изображения, а потом добавить цвет и тени. При декодировании зритель с самого начала увидит изображение со всеми деталями, которые будут улучшаться по мере добавления цветов и красок. Метод векторного квантования применяет этот принцип компрессии. Такие алгоритмы отличаются медленным кодированием и быстрым декодированием. Рис. 3.45. Последовательное декодирование. 3. Кодировать изображение по слоям, где ранние слои состоят из нескольких пикселов большого разрешения. Наблюдатель заметит постепенную детализацию картинки во времени при ее декодировании. Такой метод добавляет все новые детали по мере разжатия файла. Этот путь прогрессирующего сжатия называется пирамидальным или иерархическим кодированием. Большинство методов сжатия используют этот принцип, поэтому в этом параграфе обсуждаются общие идеи осуществления пирамидального кодирования. Рис. 3.46 иллюстрирует три принципа прогрессирующего сжатия, перечисленные выше. Они контрастируют с рис. 3.45, на котором изображены этапы последовательного декодирования. Предположим, что изображение состоит из
что на 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 второго слоя можно вычислить из уравнения Рис. 3.47. Прогрессирующее сжатие образа. Лучшее решение заключается в использовании родителя группы при вычислении его четырех потомков. Это можно делать, вычисляя разность между родителем и его потомками и записывая эту разность (после подходящего кодирования) в слой Если в памяти нет места для всех слоев, можно применить простую адаптивную модель. Она начинается присвоением счетчика 1 каждому значению разности (чтобы избегнуть проблему нулевой вероятности, см. [Salomon 2000]). После вычисления очередной разности, ей присваивается некоторая вероятность, и она кодируется, исходя из ее счетчика. После чего счетчик обновляется. Неплохо делать увеличение счетчика не на единицу, а на большее число. Тогда исходные единичные значения счетчиков быстро станут незначимыми. Некоторого улучшения можно достигнуть, если использовать родительский пиксел при вычислении трех его потомков, а затем этих трех потомков и родителя использовать при вычислении четвертого пиксела данной группы. Если четыре пиксела группы равны а, b, с и d, то их среднее равно Родительский пиксел не обязан быть равен среднему значению группы. Можно, например, выбрать в качестве родительского максимальный (или минимальный) пиксел группы. Преимущество такого метода заключается в том, что родительский пиксел равен одному из его потомков. Кодер просто закодирует три пиксела группы, а декодер декодирует три пиксела (или их разности) и дополнит группу четвертым родительским пикселом. При кодировании последовательных групп слоя, кодер должен выбирать поочередно максимальное или минимальное значение в качестве родителя, поскольку выбор только одного экстремума породит темнеющие или светлеющие слои. Рис. 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 бита. Оно говорит о том, в какой квадрант поместить родительский пиксел. Заметим, что квадранты занумерованы следующим образом:
Выбор медианы группы производится несколько медленнее нахождения максимума или минимума, но улучшает динамику проявления слоев при прогрессирующей декомпрессии. По определению, медианой последовательности чисел Если используется медиана при кодировании слоя Некоторые методы прогрессирующего сжатия, используемые на практике, такие, как SPIHT и EZW, изложены в [Salomon 2000].
|