Алгоритм Хаффмана

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

Алгоритм LZW

Алгоритм, названный в честь своих создателей Лемпеля, Зива и Велча (Lempel, Ziv и Welch), не требует вычисления вероятностей встречаемости символов или кодов. Основная идея состоит в замене совокупности байтов в исходном файле ссылкой на предыдущее появление той же совокупности.

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

Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Для кода очистки и кода конца информации используются коды 256 и 257. Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 258 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.

Алгоритмы сжатия без потерь

В качестве примеров таких алгоритмов сжатия без потерь можно рассмотреть следующие:

кодирование длин серий; метод Хаффмана; алгоритм LZW.

Алгоритмы сжатия графической информации

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

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

В этой области компьютерной теории разработаны два основных способа уменьшения объема хранения:

сжатие без потерь (lossless), когда информация полностью восстанавливается;
сжатие с потерями (lossy), когда информация до сжатия и после сжатия отличается в определенной и регулируемой степени.

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

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

Алгоритмы сжатия с потерями

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

Формула объема пиксельного файла

В данном разделе предстоит составить довольно простую формулу, которая позволит в дальнейшем рассчитывать объем файла.

с практической точки зрения, поскольку

Глава 10

.

Объем файла пиксельной графики

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

Объем пиксельного файла — это тот объем информации, для хранения которого требуется соответствующий объем дискового пространства. Для того чтобы определить, может ли какой-либо носитель информации (например, такой "малобюджетный", как дискета) вместить тот или иной объем информации, необходим предварительный расчет ("прикидка") требуемого объема при устанавливаемых параметрах.

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

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

Объем файла пиксельной графики

Глава 10 Объем файла пиксельной графики Формула объема пиксельного файла Возможность расчета объема Алгоритмы сжатия графической информации Алгоритмы сжатия без потерь Кодирование длин серий Алгоритм Хаффмана Алгоритм LZW Алгоритмы сжатия с потерями Краткая информация о форматах пиксельных файлов Графический формат PCX Графический формат BMP Графический формат GIF Графический формат JPEG Графический формат PNG Графический формат TIF Графический формат PSD

Графический формат BMP

Графический формат BMP — это разработка фирмы Microsoft для операционной системы Windows (сокращение от слова bitmap), он представляет собой чрезвычайно простую структуру и служит для описания и визуализации небольших изображений-пиктограмм (icons), широко применяемых в графических интерфейсах.

Графический формат GIF

Графический формат GIF (Graphics Interchange Format) разработан фирмой CompuServe в 1987 году как экономный формат для хранения пиксельных изображений с компрессией (сжатием по алгоритму LZW) и обмена графическими файлами по телефонной сети с помощью модемов. Этот формат допускает хранение нескольких изображений, что нашло широкое применение в так называемых "анимированных GIF-изображениях". Формат позволяет присвоить одному или нескольким цветам прозрачность, что дает возможность размещать такие изображения на любом фоне. Ограничение состоит в том, что поддерживается только палитра индексированных цветов (256 цветов).

Формат нашел самое широкое применение на Web-страницах для размещения изображений с небольшим количеством цветов, т. е. деловой и декоративной графики (надписи, знаки, логотипы, кнопки, элементы оформления и т. д.).

Графический формат JPEG

Графический формат JPEG (Joint Photographic Experts Group — Объединенная группа экспертов фотографии) предназначен для хранения полноцветных фотореалистичных изображений. Основанный на особенностях человеческого зрения, этот формат использует алгоритмы сжатия с потерями и обеспечивает значительное уменьшение объема графического файла. Однако чаще всего это ухудшение не бросается в глаза, кроме случаев, когда вокруг контуров с резкими переходами цвета образуются помехи в виде ореолов.

Формат JPEG широко используется во всемирной сети.

Графический формат PNG

Графический формат PNG (Portable Network Graphics — Переносимая графика для сети, произносится как "пинг") является форматом, который специально создан для размещения графики на Web-страницах. В формате PNG используется алгоритм сжатия Deflate.

Формат PNG соединяет в себе достоинства форматов GIF и JPEG.

Существует два варианта формата: PNG8 и PNG24, цифры в названии формата означают максимальную глубину цвета. В варианте PNG24 реализована поддержка градационной прозрачности за счет альфа канала с 256 оттенками серого.

Графический формат PSD

Графический формат PSD (Adobe Photoshop Document) является внутренним для самого популярного графического редактора Adobe Photoshop, поэтому он предназначен для сохранения текущего документа со всеми элементами, свойственными для программы: векторные контуры, каналы, слои, векторный шрифт и т. д. Формат поддерживает большинство цветовых моделей и все типы изображений, различающихся по глубине цвета.

Резюме

Объем цифровой матрицы пиксельного изображения зависит только от формальных параметров.
Если собрать все действия в компактную формулу, применяя ранее принятые обозначения, объем файла (V) будет выглядеть как произведение длины (I), ширины (W), квадрата разрешения (R) и глубины цвета (D): V= Lx Wx R2x D.
В соответствии с этой формулой объем пиксельного файла получается в битах. В этом случае для получения значения в байтах итоговое значение необходимо разделить на 8, а затем на 1024 — для получения значения в килобайтах или на 1 048 576 — для получения значения в мегабайтах.
Для уменьшения объема дискового пространства файлы подвергаются компрессии (сжатию). Существует два основных принципа сжатия: сжатие без потерь (кодирование длин серий, метод Хаффмана и алгоритм LZW), когда информация полностью восстанавливается, и сжатие с потерями (JPEG-компрессия), когда информация до сжатия и после сжатия отличается в определенной и регулируемой степени.

Последний аспект, который еще предстоит обсудить, — ЭТО неизбежные сложности, связанные с трансформированием пиксельной графики (масштабированием, поворотами и т. д.).

Графический формат TIP

Название формата TIF, разработанного компанией Aldus для программы PhotoStyler, расшифровывается как Tag Image File, что означает "теговый изобразительный файл". Этот графический формат является достаточно сложным, зато его структура предусматривает как гибкость записи данных, так и широкие возможности для расширения.

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

Применение тегов также дает возможность формулировать многочисленные дополнительные функции.

Кодирование длин серий

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

уменьшить объем файла, является поиск повторяющихся кодов (символов, цвета и т. п.) — серий одинаковых значений (Run Length Coding). Каждая такая серия фиксируется двумя числами: первое указывает количество одинаковых значений, а второе — само значение.

Краткая информация о форматах пиксельных файлов

Графический формат PCX

Графический формат PCX разработан фирмой Zsoft и был предназначен для программы Paintbrush, а затем PhotoFinish. Построение этого графического файла является простым, поэтому он пользовался до недавнего времени достаточной популярностью, хотя имел ограничения по объему цветовой палитры.

Пример-метафора

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

С точки зрения влияния на объем в пиксельной графике нет более важных и менее важных областей, как, например, в живописных произведениях. Каждый пиксел, где бы он ни располагался, занимает одинаковое количество памяти (то есть пустых пространств не бывает).

В связи с этим возникает несколько следствий.

Необходимость кадрирования, что обозначает "обрезку" лишнего изображения и удаление лишней площади. Кстати, это требуется и по эстетическим критериям, поскольку кадрирование всегда выполняется с учетом композиционного решения, например статики или динамики, оптимального размещения объекта и т. д.
Если необходимо уменьшать объем файла (минимизировать или оптимизировать, например, для размещения на Web-страницах, для передачи средствами электронной почты), то влиять можно только на параметры, которые "принимают участие" в указанной выше формуле: геометрические размеры, разрешение и глубина цвета.

В последних версиях программы Adobe

В последних версиях программы Adobe Photoshop этот формат позволяет сохранять документы со слоями, что ранее было возможно только во внутреннем формате программы PSD. Кстати, появилась возможность выбирать метод сжатия (LZW, Deflate или JPEG) и сохранять копии изображения с разным разрешением (функция "image pyramid").

Совокупность таких тегов образует область IFD, что означает Image File Directory — "указатель изображений файла". Формат позволяет включать в документ несколько таких указателей, а следовательно, и несколько изображений.

В частности, самым обычным является размещение в файле формата TIF небольшого контрольного изображения, которое называется thumbnail image — "миниатюра". Такая миниатюра представляется в диалоговых окнах при выборе имени файла.

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

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

Заменим для простоты значения цвета

Заменим для простоты значения цвета буквами. Если в документе, скажем, имеется такая последовательность "АААААВВВВВВВСССССС", ее можно сжать таким образом: 5А7В6С. В результате вместо 18 символов в документе достаточно хранить всего 6.

Алгоритм рассчитан на деловую или декоративную графику — изображения с большими областями локального (повторяющегося) цвета.

Достоинством такого алгоритма является простота (что очень важно, т. к. позволяет выполнять процедуры компрессии и декомпрессии достаточно быстро), а недостатками — необходимость различать собственно данные и числа повторений, а также возможное увеличение объема файла, если в документе мало повторений (например, серия АВСАВС не уменьшит, а увеличит объем документа, поскольку будет иметь следующий вид: 1А1В1С1А1В1С, т. е. вместо 6 символов получится вдвое больше).

Заменим также для простоты значения

Заменим также для простоты значения цвета буквами. Например, в следующей последовательности букв ААСАААВАВАВВАВСАСВСАСААССС заметно, что чаще всего встречается символ А (12 раз), затем символ С (9 раз) и, наконец, символ В (5 раз). Следовательно, символ А можно заменять кодом 0, символ С — кодом 1, а символ В — кодом 00. И так далее, если элементов для кодирования больше. В результате, если считать, что каждый символ в нашем примере кодируется 1 битом, то для передачи строки потребуется 208 битов, а в сжатом виде объем информации составит только 31 бит.

Пусть сжимается последовательность символов АВВСВВВ.

Пусть сжимается последовательность символов АВВСВВВ. Сначала в сжатый документ сохраняется код удаления [256], затем считывается символ "А" и проверяется, существует ли в таблице строка "А". Поскольку при инициализации в таблицу сохраняются все строки длиной в один символ, то строка "А", конечно, существует в таблице.

Далее считывается следующий символ "В" и проверяется, существует ли в таблице строка "АВ". Такая строка в таблице пока отсутствует, поэтому с первым свободным кодом [258] в таблицу вносится строка "АВ", а в документе сохраняется код [А]. Последовательность "АВ" в таблице отсутствует, поэтому в таблицу добавляется код [258] для сочетания "АВ", а в документе сохраняется код [А].

Далее рассматривается последовательность "ВВ", которая отсутствует в таблице, в таблицу заносится код [259] для символов "ВВ", а в документе сохраняется код [В].

Считывается символ "С" и проверяется наличие символов "ВС" в таблице, поскольку такая последовательность отсутствует, то в таблицу заносится кед [260] для последовательности "ВС", а в документ — код [В].

Снова добавляется из исходного файла символ "В" и теперь уже проверяется сочетание "СВ", которое тоже отсутствует. В таблицу записывается код [261] для "СВ", а в документ — код [С].

Затем считывается символ "В" и строка "ВВ", наконец, имеется в таблице, поэтому считывается следующий символ и рассматривается последовательность "ВВВ", которая, конечно, в таблице отсутствует. В таблицу заносится код [262] для "ВВВ", а в документ (внимание!) — код [259].

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

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

Метафора объема пиксельного изображения

Рис. 10.1. Метафора объема пиксельного изображения

Объем такого тела, естественно, вычисляется путем перемножения его составляющих. Правда, у "виртуального" пиксельного параллелепипеда есть некоторые особенности.

Предположим, что необходимо рассчитать объем дискового пространства для хранения черно-белого тонового изображения размером 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 (пикселов).

Типичное диалоговое...

Рис. 10.2. Типичное диалоговое окно для создания нового пиксельного документа с обсуждаемыми данными

Интерфейс планшетного сканера

Рис. 10.3. Интерфейс планшетного сканера

Наконец, стоит собрать все действия в компактную формулу, применяя ранее принятые обозначения:

V= L x W x R2 х D.

В зависимости от значения глубины цвета (D) итоговый объем получается в битах (в этом случае это значение необходимо разделить на 8) или байтах (в этом случае это значение необходимо разделить на 1024 — для получения килобайтов или на 1 048 576 — для получения мегабайтов).

Компромисс между качеством и уровнем компрессии

Рис. 10.4. Компромисс между качеством и уровнем компрессии

Наиболее известным методом компрессии с потерями является JPEG-компрессия. Метод компрессии основан на особенности человеческого восприятия: глаз достаточно четко различает яркость объекта и цветовые контрасты, а плавные изменения в светах и тенях значительно меньше. При записи такой изобразительной информации часть цветовых данных может быть опущена, как предполагается, без заметного ущерба для восприятия.

Для этого обработка изображения происходит в несколько этапов. Сначала изображение конвертируется в особое цветовое пространство, напоминающее цветовую модель CIE Lab, в котором один канал сохраняет яркостные характеристики, а в остальных двух цветовых каналах уменьшается разрешение (по методу мозаики).

Возможность расчета объема

После получения универсальной формулы стоит задаться вопросом: а почему оказывается возможным рассчитать объем изображения еще до того, как оно реально создано. Ведь значение этого объема можно получить в диалоговом окне New (Новый), т. е. до формирования самого документа.

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

Необходимо учесть, что этот формат

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

Не рекомендуется использовать этот формат

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

Полноценному использованию этого формата мешают

Полноценному использованию этого формата мешают устаревшие версии браузеров.

в виду, что пока речь

Следует иметь в виду, что пока речь не идет о форматах, а только о совокупности битовых карт, которые занимают определенный объем дисковой или оперативной памяти.

Прежде всего разумно признать, что метафора объема пиксельного файла имеет реальные основания: площадь матрицы и совокупность битовых карт, уходящих в глубину, волей-неволей провоцируют представление об объемном теле, например параллелепипеде (рис. 10.1).

то эти рассуждения не очень

Если кому- то эти рассуждения не очень понятны, давайте эту формулу запишем еще проще. По длине каждый дюйм состоит из 72 пикселов, следовательно, длина включает 72 х 10 = 720 (пикселов). По ширине каждый дюйм также состоит из 72 пикселов, следовательно, ширина включает 72 х 5 = 360 (пикселов). Количество пикселов во всем изображении будет равно произведению этих величин: 720 х 360 = 259 200 (пикселов). Удивительно, но получилось одно и то же число пикселов.

Запишем эти действия в одну строку:

(72 х 10) х (72 х 5) = 72 х 72 х 5 х 10 = 722 х 5 х 10 = 259 200.

Таким образом, все изображение состоит из 259 200 пикселов, каждый из которых требует одного байта для кодирования тоновой информации (глубину цвета обозначим символом D). Следовательно, объем файла, который обозначим символом V, будет равен:

V= N X D = 259 200 х 1 = 259 200 (байтов).

Для того чтобы это значение пересчитать в килобайты, полученное число необходимо разделить на 1024:

V= 259 200 : 1024 = 253,125 х 253 (килобайта).

Можно убедиться в правильности расчетов, если ввести исходные данные в соответствующее окно программы пиксельной графики (рис. 10.2) или интерфейса сканера (рис. 10.3).

в расчетах используются величины различных

Поскольку в расчетах используются величины различных размерностей (дюймы, разрешение, байты), иногда у аудитории, далекой от математики, возникает вопрос: а как мы можем перемножать или делить разнозначные числа, т. е. можно ли, скажем, перемножать яблоки и компьютеры?

Математика допускает выполнение таких действий, тем более что чаще всего полученные величины имеют и физическое обоснование. Например, разделив метры на секунды — получают скорость, хотя метры — это мера длины, а секунды — это мера времени, т. е. совершенно иная категория. Можно получить значение ускорения, разделив длину на квадрат времени. Что, казалось бы, совсем невозможно себе представить.

Затем изображение разбивается на фрагменты

RGB-изображение конвертируется в пространство YUV (иногда называемое также YcrCb), основанное на характеристиках яркости (составляющая Y) и цветности (составляющие U и V).

Затем изображение разбивается на фрагменты квадратной формы со стороной в 8 пикселов. Каждый фрагмент подвергается достаточно сложным математическим преобразованиям.

Одновременно каждый блок разлагается на

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

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

в частности алгоритм JPEG, не

Алгоритмы сжатия с потерями, в частности алгоритм JPEG, не позволяют полностью восстановить изображение до его исходного состояния, а следовательно, не рекомендуется сжимать изображения несколько раз.