Алгоритм Хаффмана основан на определенном анализе документа и вычислении частоты встречаемости цветовых значений (или значений других видов информации), а затем этим значениям в соответствии с рангом присваиваются коды сначала с минимальным количеством битов, а затем по мере снижения частоты (уменьшения ранга) используется все большее количество двоичных разрядов. Такой способ кодирования иногда называют алфавитным кодированием.
Алгоритм, названный в честь своих создателей Лемпеля, Зива и Велча (Lempel, Ziv и Welch), не требует вычисления вероятностей встречаемости символов или кодов. Основная идея состоит в замене совокупности байтов в исходном файле ссылкой на предыдущее появление той же совокупности.
Процесс сжатия выглядит следующим образом. Последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.
Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Для кода очистки и кода конца информации используются коды 256 и 257. Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 258 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.
В качестве примеров таких алгоритмов сжатия без потерь можно рассмотреть следующие:
В предыдущих разделах объем графического файла определялся объемом матрицы, в которую "помещались" битовые данные. И такой объем весьма значительно возрастает при увеличении параметров пиксельного изображения. При этом также очевидно, что существует громадная избыточность данных, которая никак не улучшает качество, но требует большого расхода дисковой памяти.
В связи с этим были разработаны способы, позволяющие сжимать графическую информацию и уменьшать объемы хотя бы на этапе ее передачи и хранения. Ведь эмпирический закон гласит, что дискового пространства всегда не хватает (сколько бы его ни было).
В этой области компьютерной теории разработаны два основных способа уменьшения объема хранения:
Когда говорят, что сжатие "без потерь", имеют в виду отсутствие информационных потерь, а именно: такие алгоритмы гарантируют, что после декомпрессии информация совпадет "бит в бит" с исходной.
И совсем другое дело, отсутствие потерь восприятия, когда зрителю "на глаз" кажется, что изображение совсем не отличается от исходного. На этом допущении основаны алгоритмы сжатия с "потерями", т. е. файл после декомпрессии фактически не идентичен исходному, хотя при определенных условиях это и не слишком заметно.
Исследователями визуального восприятия человека отмечено, что далеко не вся информация требуется для того, чтобы адекватно воспринимать цветное изображение. Для реализации этого закона были разработаны алгоритмы с потерей информации, которые обеспечивают выбор уровня компрессии с уровнем качества изображения (рис. 10.4). Тем самым достигается компромисс между размером и качеством изображений.
В данном разделе предстоит составить довольно простую формулу, которая позволит в дальнейшем рассчитывать объем файла.
Объем файла пиксельной графики
Это важная глава с практической точки зрения, поскольку объем пиксельного файла является критичным фактором при большом количестве графических документов. И разобраться в том, что формирует объем файла, совершенно необходимо для того, чтобы оптимально выбирать не только параметры пиксельного документа, но и форматы файлов.
Объем пиксельного файла — это тот объем информации, для хранения которого требуется соответствующий объем дискового пространства. Для того чтобы определить, может ли какой-либо носитель информации (например, такой "малобюджетный", как дискета) вместить тот или иной объем информации, необходим предварительный расчет ("прикидка") требуемого объема при устанавливаемых параметрах.
Создание фиксированной числовой матрицы предполагает простой расчет ее объема по параметрам пиксельной графики (геометрическим размерам, разрешению и глубине цвета). Никакие иные характеристики пиксельного изображения на объем числового массива влияния не оказывают. В данной главе представлена простая формула, которую используют любые программы, связанные с пиксельной графикой, а также специализированные программы, обслуживающие сканеры. Эта формула позволит, устанавливая параметры пиксельной графики, заранее, еще не сканируя или еще не создавая изображения, рассчитать объем файла.
Значительные объемы любых файлов стимулируют создание алгоритмов сжатия информации, в TQM числе и графической, полезным представляется знакомство с особенностями основных форматов графических файлов.
Графический формат BMP — это разработка фирмы Microsoft для операционной системы Windows (сокращение от слова bitmap), он представляет собой чрезвычайно простую структуру и служит для описания и визуализации небольших изображений-пиктограмм (icons), широко применяемых в графических интерфейсах.
Графический формат GIF (Graphics Interchange Format) разработан фирмой CompuServe в 1987 году как экономный формат для хранения пиксельных изображений с компрессией (сжатием по алгоритму LZW) и обмена графическими файлами по телефонной сети с помощью модемов. Этот формат допускает хранение нескольких изображений, что нашло широкое применение в так называемых "анимированных GIF-изображениях". Формат позволяет присвоить одному или нескольким цветам прозрачность, что дает возможность размещать такие изображения на любом фоне. Ограничение состоит в том, что поддерживается только палитра индексированных цветов (256 цветов).
Формат нашел самое широкое применение на Web-страницах для размещения изображений с небольшим количеством цветов, т. е. деловой и декоративной графики (надписи, знаки, логотипы, кнопки, элементы оформления и т. д.).
Графический формат JPEG (Joint Photographic Experts Group — Объединенная группа экспертов фотографии) предназначен для хранения полноцветных фотореалистичных изображений. Основанный на особенностях человеческого зрения, этот формат использует алгоритмы сжатия с потерями и обеспечивает значительное уменьшение объема графического файла. Однако чаще всего это ухудшение не бросается в глаза, кроме случаев, когда вокруг контуров с резкими переходами цвета образуются помехи в виде ореолов.
Формат JPEG широко используется во всемирной сети.
Графический формат PNG (Portable Network Graphics — Переносимая графика для сети, произносится как "пинг") является форматом, который специально создан для размещения графики на Web-страницах. В формате PNG используется алгоритм сжатия Deflate.
Формат PNG соединяет в себе достоинства форматов GIF и JPEG.
Существует два варианта формата: PNG8 и PNG24, цифры в названии формата означают максимальную глубину цвета. В варианте PNG24 реализована поддержка градационной прозрачности за счет альфа канала с 256 оттенками серого.
Графический формат PSD (Adobe Photoshop Document) является внутренним для самого популярного графического редактора Adobe Photoshop, поэтому он предназначен для сохранения текущего документа со всеми элементами, свойственными для программы: векторные контуры, каналы, слои, векторный шрифт и т. д. Формат поддерживает большинство цветовых моделей и все типы изображений, различающихся по глубине цвета.
Резюме
Последний аспект, который еще предстоит обсудить, — ЭТО неизбежные сложности, связанные с трансформированием пиксельной графики (масштабированием, поворотами и т. д.).
Название формата TIF, разработанного компанией Aldus для программы PhotoStyler, расшифровывается как Tag Image File, что означает "теговый изобразительный файл". Этот графический формат является достаточно сложным, зато его структура предусматривает как гибкость записи данных, так и широкие возможности для расширения.
Причина этого кроется в принципе построения файла. Вся информация, описывающая цифровые данные изображения (геометрический размер, разрешение, глубину цвета и т. д;) содержится не в заголовке файла, как у многих других форматов, а в специальных блоках ("тегах", что переводится с английского языка как "бирка"), которые содержат внутренние определения параметров изображения. Например, пятая версия формата включает 45 разных тегов, хотя практически используется гораздо меньше.
Применение тегов также дает возможность формулировать многочисленные дополнительные функции.
Пиксельное изображение при сохранении фактически вытягивается в цепочку и логично предположить, что встречаются цепочки (последовательности) одинаковых байтов. Самым простым способом, который позволяет
уменьшить объем файла, является поиск повторяющихся кодов (символов, цвета и т. п.) — серий одинаковых значений (Run Length Coding). Каждая такая серия фиксируется двумя числами: первое указывает количество одинаковых значений, а второе — само значение.
Графический формат PCX
Графический формат PCX разработан фирмой Zsoft и был предназначен для программы Paintbrush, а затем PhotoFinish. Построение этого графического файла является простым, поэтому он пользовался до недавнего времени достаточной популярностью, хотя имел ограничения по объему цветовой палитры.
Пиксельный документ можно представить в виде стола с ящиками, который, естественно, создается прежде, чем в нем будет что-либо размещаться.
С точки зрения влияния на объем в пиксельной графике нет более важных и менее важных областей, как, например, в живописных произведениях. Каждый пиксел, где бы он ни располагался, занимает одинаковое количество памяти (то есть пустых пространств не бывает).
В связи с этим возникает несколько следствий.
Объем такого тела, естественно, вычисляется путем перемножения его составляющих. Правда, у "виртуального" пиксельного параллелепипеда есть некоторые особенности.
Предположим, что необходимо рассчитать объем дискового пространства для хранения черно-белого тонового изображения размером 127x254 мм и разрешением 72 ppi.
Начнем с того, что значения длины, которую можно обозначить символом L, и ширины, которую можно обозначить символом W, необходимо представить в дюймах:
L = 127 : 25,4 = 5 (дюймов); W= 254 : 25,4 = 10 (дюймов).
Площадь изображения, обозначим ее символом S, как всем известно, вычисляется перемножением этих величин:
S = L x W= 5 х 10 = 50 (квадратных дюймов).
Геометрическая площадь изображения содержит сетку дискретизации, поэтому следующим шагом необходимо вычислить общее количество пикселов. Для этого следует учесть, что величина разрешения, которую обозначим символом R, по определению — величина линейная, а дискретизация осуществляется по площади.
Информацию об определении разрешения с/и. в главе 7.
Следовательно, сначала необходимо вычислить количество пикселов в квадратном дюйме:
N1 = R2 = 72 х 72 = 5184 (пикселов).
А поскольку площадь изображения составляет не один квадратный дюйм, то общее количество пикселов будет равно:
N= N1 х S= 5184 х 50 = 259 200 (пикселов).
Наконец, стоит собрать все действия в компактную формулу, применяя ранее принятые обозначения:
V= L x W x R2 х D.
В зависимости от значения глубины цвета (D) итоговый объем получается в битах (в этом случае это значение необходимо разделить на 8) или байтах (в этом случае это значение необходимо разделить на 1024 — для получения килобайтов или на 1 048 576 — для получения мегабайтов).
Наиболее известным методом компрессии с потерями является JPEG-компрессия. Метод компрессии основан на особенности человеческого восприятия: глаз достаточно четко различает яркость объекта и цветовые контрасты, а плавные изменения в светах и тенях значительно меньше. При записи такой изобразительной информации часть цветовых данных может быть опущена, как предполагается, без заметного ущерба для восприятия.
Для этого обработка изображения происходит в несколько этапов. Сначала изображение конвертируется в особое цветовое пространство, напоминающее цветовую модель CIE Lab, в котором один канал сохраняет яркостные характеристики, а в остальных двух цветовых каналах уменьшается разрешение (по методу мозаики).
После получения универсальной формулы стоит задаться вопросом: а почему оказывается возможным рассчитать объем изображения еще до того, как оно реально создано. Ведь значение этого объема можно получить в диалоговом окне New (Новый), т. е. до формирования самого документа.
Причина состоит в том, что объем файла в пиксельной графике никоим образом не зависит от содержания. Даже если отсканировать, скажем, белый или черный листы бумаги одинакового размера с одинаковыми разрешением и глубиной цвета, объемы файлов будут идентичными.