Глава 6 (Учебник в электронном виде), страница 13

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

Алгоритмы сжатия изображений базируются на модификациях стандартных кодировщиков. Таких программ существует довольно много и они, как правило, специализированные, т.е. созданы специально для обработки данных только определенных типов. Их особенностью является применение процедуры подстановки данных из словаря. Примером подобного алгоритма, получившего название неадапти­вного кодировщика,  является алгоритм сжатия CCITT. Он  содержит статический словарь предопределенных подстрок, о которых известно, что они появляются в кодиру­емых данных достаточно часто. В отличие от него адаптивный кодировщик не содержит априорных эвристических правил для сжимаемых данных. Адаптивные компрессоры, такие как LZW, не зависят от типа обрабатываемых данных, поскольку строят свои словари полностью из поступивших (рабочих) данных. Они не имеют предопределенного списка статических подстрок, а, наоборот, строят фразы динамически, в процессе кодирования. Наконец, метод полуадаптивного кодирования  основан на применении обоих принципов кодирования. Кодировщик  работает в два прохода. При первом он просматривает все данные и строит свой словарь, при втором - выпол­няет кодирование. Этот метод позволяет постро­ить оптимальный словарь прежде, чем приступить к кодированию.

Рассмотрим подробнее некоторые типовые алгоритмы сжатия изображений без потерь информации. Существует два основных подхода; либо оптимизируется кодирование минимального элемента информации - байта, либо удаляется избыточная информация. Представителем первого подхода является метод Хаффмана, второго - метод LZW, разработанный Лемпелем и Зивом и дополненным Велчем, а также групповое кодирование.

В методе Хаффмана сжатие проводится в два этапа. Сначала считываются данные, и определяется частота встречаемости отдел­­­ьных байтов данных. Затем байты кодируются, причем, наиболее часто встречающиеся значения кодируются меньшим количеством символов. (Например, самое часто встре­чающееся значение яркости -183 кодируется одним битом, что в 8 раз меньше, чем при использовании стандартной кодовой таблицы). По мере снижения частоты появления значений используются все более длинные слова для их кодирования. В сжатый файл записывается поток битов и информация о том, как этот поток интерпретировать. Этот метод используется, например, при факсимильной передаче. Кодирование по Хаффману неэффективно, если значения данных распределены статистически равномерно.

Групповое кодирование (RLE) - представляет собой алгоритм сжатия данных, поддерживаемый большинством растровых файловых форматов, включая такие популярные как TIFF, BMP и PCX. В СТЗ данный алгоритм имеет также и другое название КДС - кодирование методом длин серий. Алгоритм RLE позволяет сжи­мать данные любых типов, невзирая на содержащуюся в них информацию. Групповое кодирование уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки, называемые группами, обычно кодируются в двух байтах. Первый байт определяет количество символов в группе и называется счетчиком группы. На практике закодированная группа может содержать от 1 до 128 или 256 символов. Второй байт содержит значение символа в группе, которое находится в диапазоне от 0 до 255 и называется  зна­чением группы. Например, несжатая символьная группа из 15 символов А обычно занимает 15 байтов:

ААААААААААААААА

После RLE-кодирования та же строка займет все­­го два байта: 15А. Схемы RLE просты и быстры, но эффективность сжатия зависит от типа данных изображения, подлежащего кодированию. Черно-бе­лые изображе­ния, со­держащие значительно больше белого цве­­­­­та (напри­мер, страница книги), кодируются очень хорошо, поско­ль­ку включают большие объемы непрерывных данных постоянного цвета. Однако, сложные изображе­ния с большим количеством цветов, типа фотографий, кодируются значительно хуже.

Анализ эффективности алгоритмов сжатия без потерь показывает, что для черно-белых изображений наиболее эффективны модифицированные алгоритмы Хаффмана.

Схема сжатия без потерь Лемпела-Зива-Велча, названная в честь разработчиков LZW-сжатием является одной из наи­более распространенных в компьютерной графике. Этот метод применяется в различных форматах файлов изобра­жений в частности в GIF и TIFF, а также включен в стандарт сжатия для модемов V.42bis и post-Script Level 2. Основой метода явился созданный в 1977 г. А. Лемпелом и Д. Зивом первый компрессор из широко известного семейства архиваторов LZ. В соответствии с алгоритмом пер­вая часть файла передается без сжатия, и кодируются лишь та часть изображения, в которой содержатся уже переданные данные (например, где значения яркости повторяются). Ал­горитмы сжатия LZ77 широко использовались для сжатия текста, а также стали основой таких архивирующих программ как ZOO, LHA, PKZIP и ARJ. Алгоритмы сжатия LZ78 часто применялись для сжатия двоичных данных, например, бинарных изображений. В 1984 г. сотрудник фи­рмы Unisys Т. Велч модифицировал компрессор LZ78 с учетом применения высокоскоростных дисковых контроллеров. Алгоритм LZW относится к алгоритмам, основанным на словарях.

Подведем итоги.

Чем больше количество деталей в изображении, тем хуже оно сжимается. Это характерно для полутоновых изображений и изображения в истинных цветах. Степень сжатия составляет 5%. Палитровые изображения сжимаются без потерь весьма эффективно, особенно при использовании комбинации LZW и RLE (КДС) методов. В лучшем случае, степень сжатия достигает 50%. В то же время, использование этих методов сжатия иногда приводит к увеличению размера графического фай­ла.

Принципиально другой подход используется в методах сжатия изображений с потерей информации. Он основан на частотном представлении изображения. Действительно, инфо­р­мационное содержание виде­о­си­г­на­ла чаще удо­бно ана­лизи­ро­вать, не рассматривая его изменение во вре­мени, а раскладывая на частотные составляющие. Тогда, бла­годаря удалению менее существенных ко­м­понент можно упростить запоминание сигнала и, следовательно, уме­ньшить требуемую емкость памяти. Правда, некоторая часть информации теряется безвозвратно. Наиболее известным способом кодирования с потерей информации является сжатие с помощью ДКП (DCT). ДКП - это общее имя определенного класса операций, на которых базируются раз­­личные методы сжатия, в основе которых ле­жит цифровое частотное кодирование. Для примера рассмотрим процесс сжатия полутонового изображения, состоящего из матрицы байтовых элементов. На первом этапе производится преобразование значений яркости и цвета каждого элемента в частотную область. Для упрощения процедуры изображение разбивается на субматрицы размером 88 элементов, в которых определяются частотные сос­тав­ля­ющие фрагментов. Затем сокращают число этих составляющих, сохраняя только самые существенные, и, наконец, записы­вают их возможно более компа­к­тным способом.

ДКП определяется следующей процедурой:

P_DCT = DCTPDCT^T

Здесь P - блок изображения размером 88 элементов, P - блок дан­ных после ДКП, DCT - ма­трица ко­синусного преобразо­ва­ния, DCT^T - соответствую­щая ей тра­н­­спон­иро­ван­ная матрица. Зна­ком  обозна­че­но мат­ри­ч­ное ум­ножение.

Матрица ДКП имеет вид пре­дставленный на рис. 6.39. Для упрощения записи в каждом коэффициенте учтены только три цифры после запятой.

П роцедура ДКП реализуется с помощью последовательности матричных перемножений, поблочно (размер блока 88 элементов). Сначала производится умножение видеоданных P на транспонированную ДКП матрицу DCT^T, затем результат умножается на собственно матрицу ДКП. Результатом этого преобразования является новая матрица, численные значения элементов которой быстро уменьшаются от левого верхнего угла к правому нижнему (рис. 6.40). Она характеризует распределение частот в видеоданных: в левом верхнем углу размещаются наиболее важные данные. Сжатие выполняется путем устранения менее важных составляющих, для чего проводится квантование преобразованных (частотных) данных. Идея квантования заключается в выборке из матрицы тех составляющих изображения, которые превышают некоторый частотный порог. Выбор правильного порога является отдельной проблемой. Если он будет слишком высоким, то потеряется большая часть видеоданных, хотя и само сжатие будет значительным. Тогда восстановленное изображение будет сильно отличаться от исходного. На практике, можно обеспечить степень сжатия до 80%, прежде чем потери качества изображения будут заметными [ ]. Квантование осуществляется умножением «частотной матрицы» на матрицу делителей, определяемую с помощью алгоритма «дели­тель - качество». Так, при квантовании «с качеством 2» при котором потери прак­тически незаметны в матрице сохраняется лишь неболь­шое число ненулевых элементов, значения которых также невелики [ ]:

Полученные значения можно экономно запомнить, применяя, например, кодирование по Хаффману. Если установить зигзагообразную траекторию обхода коэффициентов, то можно получить очень длинную непрерывную последо­вательность из 26 нулей.

Восстановление сжатого изображения производится обратным ДКП. При этом все шаги выполняются в обратном порядке.

Д КП является очень эффективным способом сжатия. При его использовании необходимо в изображении выделить яркостную и цветовую компоненты. Поэтому если изображение представлено в цветовых моделях RGB или CMYK, его следует преобразовать в одну из аппаратно-независимых моделей - HSV или YUV. Яркостную информацию сжимают непосредственно, а цветовую с помощью ДКП. Следовательно, и палитровые изображения с помощью ДКП также не сжимаются. Это связано с тем, что в них цвет пикселей представлен не непосредственно, а лишь через индексы в таблице цветов. Поэтому палитровые изо­бражения тоже необходимо преобразовать в форму HSV или YUV моделей, что оправданно лишь в редких случаях.

Теперь рассмотрим некоторые особенности спецификации JPEG. На сегодняшний день JPEG является одним из наиболее актуальных направлений развития технологии сжатия изображений. Принцип JPEG-кодирования также не является одним алгоритмом сжатия; он может рассматриваться как набор методов сжатия, при­­годных для удовлетворения нужд пользователя. В основе JPEG лежит схема ДКП кодирования (рис. 6.41).

Аббревиатура JPEG про­­исходит от названия комитета по стандартам Jo­int Photo­graphic Experts Gro­up (дословно - объе­ди­нен­ная груп­па экспертов по фотографии), входящего в состав Международной организации по ста­н­дар­тизации (ISO). В 1982 году ISO сформировала группу экспертов по фотографии (PEG), возложив на нее обязанности по проведению исследований в области передачи видеосиг­налов неподвижных изображений и текстов по каналам ISDN (интеграль­ной цифровой сети связи). В 1987 году PEG и CCITT объединили свои группы в коми­тет, который должен был провести ис­сле­дования и выпустить один стандарт сжатия данных. Новый комитет получил название JPEG.

Схема JPEG была специально разработана для сжатия цветных и полутоновых (т.е. многограда­ци­он­ных) изображений - фото­графий и другой сло­жной графики. При этом анимация, черно-белые ил­люстра­ции и документы, а также типичная векторная графика, как правило, сжимаются плохо. Прак­тически JPEG хорошо работает только с изо­бра­жени­ями, имеющими глубину хотя бы 4 … 5 битов на цве­то­вой канал.

Алгоритм JPEG преобразует каждый компонент цветовой модели отдельно, что обеспечивает его полную независимость от любой модели цветового прост­ранства (напри­мер, от RGB, HSI или SMY). Лучшая степень сжатия достигается в слу­чае применения цветового пространства YUV или YCbCr. Спецификация на JPEG файлы показывает, что это расширение позволяет хранить одно и то же изображение с разными разрешениями в порядке иерархии. Так, изображение может быть сохранено с разрешениями 250250, 500500, 10001000 и 20002000 пикселей (что позволяет поддерживать его отображение на экранах мониторов с низким раз­решением, лазерных принтерах среднего разрешения и на высококачественных устройствах печати). Степень сжатия изображения с фотогра­фическим качеством может составить от 20:1 до 25:1 без заметной потери качества. Регулиро­вание качества кодировщика JPEG осуществляется с помощью Q-фак­тора. В различных программах обработки изображений используются разные диапазоны изменения Q-фактора, но типичные значения находятся в диапазоне 1... 100. При Q = 100 сжатие мало: изображение будет иметь значительный размер, но высокого качества. Оптимальное значение Q-фактора зависит от содержимого изображения и под­бирается индивидуально.

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