Методы сжатия
графических данных
План:
1. История появления и тенденции развития графических форматов
2. Методы сжатия графических изображений
2.1. Алгоритмы сжатия без потерь
2.1.1. Кодирование длин серий (RLE)
2.1.2. Метод Хаффмана
2.1.3. Алгоритм LZW
2.2. Алгоритмы сжатия с потерями
2.2.1. Алгоритм JPEG
3. Конвертация растровых в векторные форматы и обратно
*Создавая в 1804 году ткацкий станок с созданием узора на холсте по информации, находящейся на перфокартах, французский инженер Ж.М. Жаккар не подозревал, что открывает миру машинную графику и один из графических форматов.
Проблема хранения графических данных остается актуальной и сегодня (если нет импорта/экспорта, то система закрыта). Единого, универсального формата, пригодного для всех приложений, очевидно, нет и быть не может. Однако некоторые форматы фактически стали стандартами для целого ряда предметных областей. GIF (самый сжатый), TIFF, PCX, TGA - растровая графика; DXF, HPGL – САПР; EPS – для лазерных принтеров; FLA, AVI - анимационные ролики.
Графические форматы различаются по:
Ø виду хранимых данных (растровая, векторная и смешанная формы);
Ø допустимому объему данных;
Ø параметрам изображения;
Ø хранению палитр;
Ø методике сжатия данных (для EGA без сжатия требуется 256К) - DCLZ (Data Compression Lempel-Ziv), LZW (Lempel-Ziv& Welch)
Ø способам организации файла (текстовый, двоичный);
Ø структуре файла (с последовательной или ссылочной (индексно-последовательной) структурой) и т.д.
Пользователи, работающие с графическими пакетами или программами верстки, решают какой формат лучше выбрать в каждом конкретном случае. А еще приходится обмениваться файлами между разными платформами...
Американским национальным институтом стандартов (ANSI) предложено несколько спецификаций. Но каждая компания - разработчик полагает, что она лучше других понимает, как то или иное приложение должно работать с графическими файлами, поэтому следует принятым стандартам только на словах.
Как вы уже знаете, существуют два принципиально различных способа записи графической информации: растровый и векторный. Первый встречается в ПО для сканеров или в программах обработки фотоизображений.
Растровый файл состоит из точек, число которых определяется разрешением, измеряемым обычно в точках на дюйм (dpi). Очень важным фактором, влияющим, с одной стороны, на качество вывода изображения, а с другой - на размер файла, является глубина цвета, т.е. число разрядов, отводимых для хранения информации о трех составляющих (если это цветная картинка) или одной составляющей (для полутонового нецветного изображения). Например, при использовании модели RGB глубина 24 разряда на точку означает, что на каждый цвет (красный, синий, зеленый) отводится по 8 разрядов и поэтому в таком файле может храниться информация о 224 = 16,777,216 цветов. Даже файлы с низким разрешением содержат в себе тысячи или десятки тысяч точек. Так, растровая картинка размером 1024х768 точек и с 256 цветами занимает 768 Кбайт. Для уменьшения объемов файлов разработаны специальные алгоритмы сжатия графической информации. Именно они и являются основной причиной существования графических форматов. Разные производители ПО используют разные методы сжатия, и в результате слабая совместимость отдельных форматов создает множество проблем для пользователей.
Векторный способ записи графических данных применяется в системах автоматического проектирования (CAD) и в графических пакетах. В этом случае изображение состоит из простейших элементов (линия, ломаная, кривая Безье, эллипс, прямоугольник и т.д.), для каждого из которых определен ряд атрибутов (например, для замкнутого многоугольника - координаты угловых точек, толщина и цвет контурной линии, тип и цвета заливки и т.д.). Записывается также место объектов на странице и расположение их друг относительно друга (какой из них "лежит" выше, а какой ниже).
Файлы векторных форматов способны хранить не только векторные, но и растровые изображения. В этом смысле они более универсальны, чем собственно растровые форматы.
Существует множество программ-трансляторов, переводящих данные из векторного формата в растровый. Как правило, такая задача решается довольно просто, чего нельзя сказать об обратной операции - преобразовании растрового файла в векторный и даже о переводе одного векторного файла в другой. Векторные алгоритмы записи используют уникальные для каждой фирмы-поставщика математические модели, описывающие элементы изображения. Вот почему, например, так мало хороших, надежных трансляторов, переводящих данные на языке PostScript в формат HPGL (Hewlett-Packard Graphics Language).
Не многие высокопроизводительные приложения отличаются эффективными методами перевода растровых изображений в векторные. Одно из них - модуль CorelTrace, поставляемый в составе набора графических приложений CorelDraw фирмы Corel Systems. Этот пакет, обладающий гибкими инструментальными средствами, позволяет определить способ очерчивания растровых картинок в зависимости от их типа, а также производить другие настройки. Среди менее дорогих программ можно отметить пакет Graphics Tools производства Deltapoint, способный не только переводить векторные файлы в растровые и обратно, но и выполнять цветоделение, записывать в буфер изображение с экрана монитора и т.д. В последнюю версию ПО HiJaak Suite for Windows фирмы Inset Systems, помимо встроенных редакторов растровых и векторных изображений, включены средства перевода данных из одних форматов в другие. Новая версия поддерживает 22 векторных формата и 28 растровых - больше, чем любой конкурирующий продукт. (HiJaak работает и с текстовыми форматами, практически все популярные текстовые процессоры.) Но этот пакет не преобразует растровые файлы в векторные. Выделяется своими возможностями и программа Conversion Artist компании North Coast Software, приводящая данные в форматы Amiga, Macintosh, Sun и Unix.
Для уменьшения объема дискового пространства файлы подвергаются компрессии (сжатию). Существует два основных принципа сжатия: сжатие без потерь, когда информация полностью восстанавливается, и сжатие с потерями, когда информация до и после сжатия отличается в определенной и регулируемой степени.
В качестве примеров таких алгоритмов сжатия без потерь можно рассмотреть следующие:
Ø кодирование длин серий;
Ø метод Хаффмана;
Ø алгоритм LZW.
Как известно, все документы (графика, тексты, программы и т. п.) хранятся в компьютере в виде файлов — организованных записей. Изображения хранятся в файлах специальных графических форматов, которых сейчас насчитывается более десятка. Основой для разложения изображения на множество элементов является пиксель. Основа файла — это описание цветов всех пикселей. Описание цвета пикселя (три / четыре числа) является кодом цвета в соответствии с той или иной цветовой моделью. Указание на цветовую модель также включается в файл. Кроме того, записывается размер изображения в пикселях.
Итак, условная структура файла (аналог формата BMP), будет содержать: сведения о цветовой модели; габаритах изображения; и, например, об авторе картинки, включенные в специальный раздел файла, называемый заголовком. После заголовка в файле записываются друг за другом коды цветов (или параметров цветовой модели) отдельных пикселей, слева направо и сверху вниз.
Пиксельное изображение при сохранении фактически вытягивается в цепочку и логично предположить, что встречаются цепочки (последовательности) одинаковых байтов. Самым простым способом, который позволяет уменьшить объем файла, является поиск повторяющихся кодов (символов, цвета и т. п.) — серий одинаковых значений. Каждая такая серия фиксируется двумя числами: первое указывает количество одинаковых значений, а второе — само значение.
Пример:
Заменим для простоты значения цвета буквами. Если в документе, скажем, имеется такая последовательность "АААААВВВВВВВСССССС", ее можно сжать таким образом: 5А7В6С. В результате вместо 18 символов в документе достаточно хранить всего 6.
Алгоритм рассчитан на деловую или декоративную графику — изображения с большими областями локального (повторяющегося) цвета.
Достоинством такого алгоритма является простота (что очень важно, т. к. позволяет выполнять процедуры компрессии и декомпрессии достаточно быстро), а недостатками — необходимость различать собственно данные и числа повторений, а также возможное увеличение объема файла, если в документе мало повторений (например, серия АВСАВС не уменьшит, а увеличит объем документа, поскольку будет иметь следующий вид: 1А1В1С1А1В1С, т. е. вместо 6 символов получится вдвое больше).
Если система выводит ошибку, возможно программа, считывающая файл ожидает появление данных в ином порядке, чем программа, сохраняющая этот файл на диске. Требуется преобразование в иной формат
Метод RLE включается в некоторые графические форматы, например:
Ø PCX (всегда);
Ø BMP (для 16 и 256 по желанию);
Ø TGA (по желанию);
Ø IMG (всегда).
Алгоритм Хаффмана основан на определенном анализе документа и вычислении частоты встречаемости цветовых значений (или значений других видов информации), а затем этим значениям в соответствии с рангом присваиваются коды сначала с минимальным количеством битов, а затем по мере снижения частоты (уменьшения ранга) используется все большее количество двоичных разрядов. Такой способ кодирования иногда называют алфавитным кодированием.
Пример:
Заменим также для простоты значения цвета буквами. Например, в следующей последовательности букв ААСАААВАВАВВАВСАСВСАСААССС заметно, что чаще всего встречается символ А (12 раз), затем символ С (9 раз) и, наконец, символ В (5 раз). Следовательно, символ А можно заменять кодом 0, символ С — кодом 1, а символ В — кодом 00. И так далее, если элементов для кодирования больше. В результате, если считать, что каждый символ в нашем примере кодируется 1 битом, то для передачи строки потребуется 208 битов, а в сжатом виде объем информации составит только 31 бит.
Алгоритм, названный в честь своих создателей Лемпеля, Зива и Велча (Lempel, Ziv и Welch), не требует вычисления вероятностей встречаемости символов или кодов. Основная идея состоит в замене совокупности байтов в исходном файле ссылкой на предыдущее появление той же совокупности.
Процесс сжатия выглядит следующим образом. Последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.
Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Для кода очистки и кода конца информации используются коды 256 и 257. Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 258 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.
Пример:
Пусть сжимается последовательность символов АВВСВВВ. Сначала в сжатый документ сохраняется код удаления [256], затем считывается символ "А" и проверяется, существует ли в таблице строка "А". Поскольку при инициализации в таблицу сохраняются все строки длиной в один символ, то строка "А", конечно, существует в таблице.
Далее считывается следующий символ "В" и проверяется, существует ли в таблице строка "АВ". Такая строка в таблице пока отсутствует, поэтому с первым свободным кодом [258] в таблицу вносится строка "АВ", а в документе сохраняется код [А]. Последовательность "АВ" в таблице отсутствует, поэтому в таблицу добавляется код [258] для сочетания "АВ", а в документе сохраняется код [А].
Далее рассматривается последовательность "ВВ", которая отсутствует в таблице, в таблицу заносится код [259] для символов "ВВ", а в документе сохраняется код [В].
Считывается символ "С" и проверяется наличие символов "ВС" в таблице, поскольку такая последовательность отсутствует, то в таблицу заносится кед [260] для последовательности "ВС", а в документ — код [В].
Снова добавляется из исходного файла символ "В" и теперь уже проверяется сочетание "СВ", которое тоже отсутствует. В таблицу записывается код [261] для "СВ", а в документ — код [С].
Затем считывается символ "В" и строка "ВВ", наконец, имеется в таблице, поэтому считывается следующий символ и рассматривается последовательность "ВВВ", которая, конечно, в таблице отсутствует. В таблицу заносится код [262] для "ВВВ", а в документ (внимание!) — код [259].
В результате в документе окажется следующая последовательность кодов [256][А][В][В][С][259], что короче исходной последовательности. К сожалению, последовательность слишком короткая, а алгоритм достатчно сложен, чтобы выгода оказалась реальной. При значительном объеме коэффициент сжатия может достигать несколько сот единиц.
Особенностью рассматриваемого алгоритма LZW является то, что для выполнения обратного процесса ("распаковки") нет необходимости сохранять таблицу в документе (алгоритм позволяет восстановить таблицу строк только из сохраненных в документе кодов).
Этот метод гораздо совершеннее RLE для областей с переходами цветов, однако кодировка в него требует больше системных ресурсов.
Метод LZW включается в некоторые графические форматы, например: TIFF; GIF.
Исследователями визуального восприятия человека отмечено, что далеко не вся информация требуется для того, чтобы адекватно воспринимать цветное изображение. Для реализации этого закона были разработаны алгоритмы с потерей информации, которые обеспечивают выбор уровня компрессии с уровнем качества изображения (рис. 1). Тем самым достигается компромисс между размером и качеством изображений.
Наиболее известным методом компрессии с потерями является JPEG-компрессия. Метод компрессии основан на особенности человеческого восприятия: глаз достаточно четко различает яркость объекта и цветовые контрасты, а плавные изменения в светах и тенях значительно меньше. При записи такой изобразительной информации часть цветовых данных может быть опущена, как предполагается, без заметного ущерба для восприятия.
Рис. 1. Компромисс между качеством и уровнем компрессии
Для этого обработка изображения происходит в несколько этапов. Сначала изображение конвертируется в особое цветовое пространство, напоминающее цветовую модель CIE Lab, в котором один канал сохраняет яркостные характеристики, а в остальных двух цветовых каналах уменьшается разрешение (по методу мозаики).
Замечание: RGB-изображение конвертируется в пространство YUV (иногда называемое также YcrCb), основанное на характеристиках яркости (составляющая Y) и цветности (составляющие U и V).
Затем изображение разбивается на фрагменты квадратной формы со стороной в 8 пикселей. Каждый фрагмент подвергается достаточно сложным математическим преобразованиям. Записывается два типа информации — усредненная информация о блоке и информация о его деталях, далее, в зависимости от выбранной степени сжатия, удаляется то или иное количество дополнительной информации. Чем меньше будет размер файла, тем хуже будет его качество.
Одновременно каждый блок разлагается на составляющие цвета и производится подсчет частоты встречаемости каждого цвета. Информация о частоте позволяет исключить небольшую часть яркостной характеристики и довольно значительную цветовой. Уровень исключения информации как раз и определяется установкой требуемого качества.
Затем информация о яркости и цвете кодируется таким образом, что остаются только различия между соседними блоками. Результатом всего процесса обработки являются последовательности простых чисел, которые в свою очередь легко сжимать каким-либо алгоритмом сжатия без потерь из уже упомянутых, например алгоритмом Хаффмана.
Алгоритмы сжатия с потерями, в частности алгоритм JPEG, не позволяют полностью восстановить изображение до его исходного состояния, а, следовательно, не рекомендуется сжимать изображения несколько раз.
