Изображения: форматы и сжатие (2/3)

И снова здравствуйте! После перерыва в месяц продолжаем экскурсию по форматам изображений и алгоритмам сжатия. Где мы остановились? Ах, да, восьмидесятые годы.

TIFF: Собери сам

На дворе 1986 год. Форматы PCX и TGA начинают обеспечивать зрелищами счастливых обладателей обычных десктопов. Но ведь домашними компьютерами дело не ограничивается, есть ещё предприятия и университеты. А у них уж мощные машины и сканеры, а в среде сканеров… бардак и безобразие. Задача сканера — перевести изображение на бумаги в цифровой формат, а этот формат был у каждого производителя свой.

Представьте на минутку, Вы делаете скан какого-нибудь Важного Чертежа, несете его в типографию, а там говорят, что прочитать его не могут. Придется перегонять его в другой формат, а лучше вообще просто принести фотокопию для надежности. Обидно.

Решением этой проблемы и занялась компания Aldus, в итоге представив формат TIFF. Все сканы теперь были в одном формате, да ещё и «из коробки» могли в одном файле содержать несколько страниц документа. Плюс, вместе с растровыми данными стало возможно можно хранить метаинформацию: название документа, автора, дату сканирования, модель сканера — да почти все, что угодно.

Формат получился настолько расширяемым, что он живет и здравствует и по сей день. А все из-за того, что Aldus переосмыслили само понятие графического формата. Вместо фиксированного пласта информации используются относительно небольшие структуры, из которых можно собрать файл. Известен автор — вставялем структуру, неизвестен — просто удаляем. Использование таких «меток», собственно, и обыгрывалось в самом названии формата: «Tagged Image File Format».

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

Формат для обмена картинками

Новый формат TIFF, обладая шикарными преимуществами, годился только для печатного дела: первая ревизия предусматривала только черно-белые изображения без полутонов. А в 1987 году уже появились видеокарты VGA с палитрой до умопомрачительных 256 цветов. TGA и PCX (с допиливанием) позволяли хранить пресловутые 256 цветов, но размер файла увеличивался вдвое, а то и больше — простенький RLE на большой палитре работал значительно хуже.

Для оценки масштаба возьмем полноэкранную картинку VGA (320×200@256) в формате PCX — порядка 50 КиБ, плюс-минус. Теперь попробуем передать её при помощи быстрого, на 9600 бод, дайл-ап модема, и получим время загрузки где-то около минуты. Не круто. Примерно так же показалось компании CompuServe, что зарабатывала деньги, предоставляя доступ к своей BBS'ке в солнечном Колумбусе, штат Огайо.

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

Оба эти подхода и объединились в формате GIF («Graphics Interchange Format»). А теперь подробнее.

GIF: Структура

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

Заголовок

Первые шесть байт файла — заголовок. Он состоит из сигнатуры «GIF» и версии: «87a» или «89a», где 87 и 89 — года, в которых они были разработаны. Версия 89а расширяет 87а и полностью с ней обратно совместима. Спецификация предписывает по возможности использовать 87a, но лично я бы не советовал — браузеры кривовато работают с 87a. В качестве демонстрации немного забегу вперед и покажу фокус:

Что изображено на картинке? Если один квадрат, то у Вас Firefox или Chrome. Если два, то IE. Если три, то Opera (которая ещё на Presto).

Блок описания логического экрана

Логический экран — это просто прямоугольная область, выделенная под отображение графики, по смыслу что-то вроде порта просмотра. GIF может содержать несколько изображений, и они могут быть меньше по размеру, чем логический экран. Более того, в GIF87a эти изображения не являются кадрами анимации, а скорее слоями.

Иными словами, если нужно нарисовать на весь экран 800×600 посередине котёнка, а в углу цветочек, то можно вместо одного огромного «сведённого» изображения, хранить котёнка и цветочек с их смещениями относительно логического экрана.

Небольшой дисклеймер. Несмотря на то, что на интуитивном уровне сама гифка (арргх… ладно, «джифка») — это картинка, которая показывается на экране, мы будем придерживаться терминологии, указанной в спецификации: «логический экран» — это размер всей GIF'ки целиком, а «изображение» — это слой/кадр.

Итак, блок описания логического экрана всегда занимает 7 байт. Первыми идут размеры — два байта на ширину и два байта на высоту (UInt16LE). Получается, максимальный размер — 65535×65535 пикселей. В спецификации не указано, что ширина или высота обязаны быть больше нуля, но осознание этого не дает нам ничего, кроме разве что курьезности.

Тут следет сделать важное замечание: если файл GIF версии 87a, Firefox и Chrome всегда игнорируют это поле, и используют в качестве размера логического экрана размер первого изображения. Opera и IE поступают так же только в случае, если координаты первого изображения нулевые.

Далее следует один байт, содержащий в себе несколько полей. Седьмой бит (старший) указывает, есть ли глобальная палитра, а биты с 0 по 2 определяют её размер (от 2¹ до 2⁸). Оставшиеся 4 бита за давностью лет смысл потеряли.

Следующее поле — один байт, указывающий на цвет фона в глобальной палитре (если она используется). Этим цветом должны быть залиты все области логического экрана, не занятые ни одним из изображений. В теории. На практике же это требование выполняют только Photoshop и IrfanView. Распространенные браузеры незанятое место оставляют прозрачным. А у Оперы 12 есть интересный бажок: если GIF версии 87a, и в нем содержится более одного изображения, это пустое место заливается чёрным.

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

Глобальная палитра

Если флажок глобальной палитры выставлен в 0, её просто нет. А если есть, то размер всего блока в байтах равен количеству цветов в палитре помножить на три. Принцип заполнения: RGB RGB RGB…, точно так же, как в PCX.

Глобальная палитра применяется для каждого изображения в файле, если у него нет локальной палитры. А если нет ни той, ни другой? Спека по этому поводу говорит «эмм… ну не знаю, разберитесь как-нибудь», и предлагает использовать стандартную палитру устройства, но желательно, чтобы первый цвет в ней был черным, а второй белым. В 2013 году все уже забыли, что такое стандартная палитра устройства, и этот фокус не проходит.

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

Изображение

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

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

Изображение начинается с маркера, ASCII-символа «,» (запятая). Этот маркер нужен для того, чтобы понять, какая структура сейчас началась: изображение («,»), блок расширения («!»), или блок конца изображения («;»).

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

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

После этого, как и в описании логического экрана, следует непосредственно локальная палитра, если она есть.

Кстати, раз уж пошла речь, Вы же уже догадались, каким образом на одном логическом экране GIF можно отобразить более 256 цветов?

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

Упаковка данных произвольной длины

Потом в изображении идут непосредственно сжатые LZW данные. Но хранятся они не простым шматком данных с указанной длиной, а упаковываются в блоки. (Видимо, чтобы избежать при кодировании произвольного IO и излишнего потребления памяти.) Принцип упаковки: один байт длины блока, n байтов данных, один байт длины блока, n байтов данных, и так далее, пока данные не кончатся. А на окончание данных указывает блок длиной 0.

Например, известную панграмму про шуструю лисицу можно упаковать вот так:

<b><u>x2B</u></b>The quick brown fox jumps over the lazy dog<b><u>x00</u></b>

А можно и по-другому, потратим на один байт больше, но ошибкой это считаться не будет:

<b><u>x20</u></b>The quick brown fox jumps over t<b><u>x0B</u></b>he lazy dog<b><u>x00</u></b>

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

Расширения

Внимательный читатель уже, наверное, заметил что ни в описании изображения, ни в описании логического экрана, пока не было собственно «плюшек» GIF: прозрачности и анимации. Это потому что они были введены в версии 89a в виде блока расширения.

Всего типов блоков расширения четыре: расширение управления графикой, текстовое расширение, комментарий и расширение приложения. Все блоки опциональны, что делает формат GIF89a обратно совместимым с 87a.

Расширение управления графикой

Это расширение по сути набор дополнительных полей для изображения, которое следует сразу после него. Фактически, именно оно превращает смутно описанное понятие «изображение» во вполне конкретный «кадр». Из фиксированных полей только два байта-маркера: 0x21, «это расширение» и 0xF9, «это расширение управления графикой».

Дальнейшие поля упакованы так же, как и сырые данные изображения — длина блока, n байт, длина блока, n байт. Иное дело, что по спецификации это всегда один блок длиной 4 байта. Зачем вообще надо было разбивать на блоки — даже разбираться не хочется, видимо, так было проще.

Так или иначе, первый из этих четырех байтов — набор битовых полей. Три старших бита зарезервированы. Далее три бита, образуя целое от 0 до 7, указывают на то, что следует сделать с кадром перед тем, как показать следующий. 0: ничего (не определено); 1: ничего (оставить все как есть); 2: очистить экран; 3: вернуть то, что было до этого кадра; значения 4-7 зарезервированы.

Бит 1 — самый интересный с исторической точки зрения. Ждать ли от пльзователя «any key» для того, чтобы показать кадр, следующий за этим. Да-да, на основе GIF можно было сделать не только слайдшоу, но и вполне себе презентацию. Сейчас эту фича фактически не поддерживается.

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

Два следующих байта образуют UInt16, указывающий, сколько сотых секунды нужно подождать перед показом следующего кадра. Таким образом, задержка может быть в интервале от 0 до 655,35 секунд.

Наконец, последний байт — индекс «прозрачного» цвета в палитре (если выше было указано, что он есть).

Расширение приложения

Это расширение создано для того, чтобы позволять приложениям записывать в GIF свои проприетарные метаданные. Формат уже знакомый: два байта маркера- сигнатуры, 0x21 0xFF, остальное блоки с указанием длины перед ними. И опять длина первого блока строго фиксирована: 11 байт, которые идентифицируют приложение. Последующие же блоки могут быть любой длины и содержать что угодно.

Одно такое расширение было придумано браузером Netscape Navigator. Дело в том, что сам формат GIF не предусматривает цикличности анимации, а при помощи проприетарного расширения «NETSCAPE2.0» можно указать, сколько раз прокручивать анимацию: от 1 до 65535 раз, или бесконечно.

Сейчас эту конструкцию понимают все браузеры, а если её нет, считается, что анимация не зациклена.

Остальные расширения приложений в целях уменьшения размеров файла можно смело выкашивать.

Текстовое расширение

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

Но увы, реальной поддержки этого расширения нет. В природе этот вид не встречается, из красной книги вычеркнут. А мы с Вами идем дальше.

Комментарий

Последнее расширение самое простое. Два байта-маркера 0x21 0xFE, а далее произвольное содержимое, упакованное в блоки.

Замыкающий блок

Замыкающий блок («trailer») состоит из одного-единственного байта 0x3B («;»). Он находится в конце файла и означает, что в этом месте, собственно, конец файла. Всё, что находится после него, считается мусором и игнорируется.

Эта конструкция по спецификации является обязательной, не забывайте про нее.

Фух! Кажется, по структуре всё. Честно сказать, я сам ожидал, что она будет проще. Если вдруг возникли какие-то недопонимания, из-за стиля изложения или перевода терминов, можно ознакомиться с официальной спецификацией GIF89a. Также очень советую программку GIF opener, ей сто лет в обед, но лучше для низкоуровневого редактирования gif я пока ничего не видел.

Алгоритм Лемпеля-Зива-Велча

Теперь, когда мы осмотрели окрестности, окнунемся в самое сердце GIF — алгоритм Лемпеля-Зива-Велча, он же LZW. Прежде всего стоит отметить, что этот алгоритм словарный. Давайте посмотрим, что это значит.

Сжатие со словарем, простой пример

Словарное сжатие — прямое развитие идеи RLE. В общем и целом принцип такой: ищем повторяющиеся значения и заносим их в словарь, а затем в нужном месте делаем указание на элемент словаря. Таким образом, сжимаются не только одинаковые значения подряд, но и группы разных значений, между которыми может быть определенное расстояние.

Для примера возьмем такую строку:

АБРАКАДАБРА С ХАБРАХАБРА

Видно, что она прямо-таки нашпигована повторяющимися «АБРА». Выберем какой-нибудь неиспользуемый символ, например, «1» и скажем, что любой такой встреченный символ следует заменить на «АБРА». В результате получим строку «1КАД1 С Х1Х1», вдвое меньшую. А чтобы кто-то кроме нас мог понять, что эта шифровка зачит, нужно не забыть записать сам словарь, т.е., на что именно нужно заменить «1». Результатом станет что-то вроде:

1=АБРА;1КАД1 С Х1Х1

Можно пойти чуть дальше, и заменить ещё и «Х1» на «2»:

1=АБРА,2=Х1;1КАД1 С 22

Хм… вроде бы мы и заменили больше повторяющихся значений, а строка получилась длиннее. Увы, словарь тоже нужно хранить, и чем он больше, тем больше накладные расходы.

Разумеется, с этим пытаются как-то бороться. Например, алгоритм LZ77 формально считается словарным, но в качестве словаря там выступают сами декодированные данные — декодеру дается команда вернуться на n байт назад и скопировать оттуда m байт. Подробнее о LZ77 можно почитать в этой статье за авторством уважаемого horror_x.

В LZW, «потомке» LZ77, записи словаря также появляются по мере декодирования, но это уже не просто копирование со смещением, а полноценный словарь.

LZW: общий принцип кодирования

Для примера возьмем ту же самую строку, «АБРАКАДАБРА С ХАБРАХАБРА».

Теперь нужно выбрать кодировку этой строки. Использование многобайтовой кодировки сильно усложнит пример, так кто UTF-8 отложим напотом. Прах семибитных кодировок, таких как КОИ-7 Н1 (ГОСТ 13052-74), тревожить не будем. Выберем какую-нибудь восьмибитную, например всеми любимую CP866.

Таким образом, изначальный словарь будет идентичен CP866:

00000000 <NUL>
00000001 <SOH>
...
10000000 А
10000001 Б
...
10011111 Я
...
11111111 <NBSP>

Этот словарь уже заполнен, и добавить в него ничего не получится. Но в LZW в словарь всегда должна быть возможность добавить новую запись. Как только предыдущей длины кодов начинает для этого не хватать, её нужно увеличить:

000000000 <NUL>
...
011111111 <NBSP>

Теперь для указания индекса словаря используется семь бит (это и есть «длина кодов»). Кстати, когда говорят, что-то вроде «LZW с длиной кодов 8», имеется в виду длина кодов изначального словаря, начинаем кодирование же мы с длиной кодов на единицу большей. Немного запутанно, но так уж есть.

Строка начинаетс с заглавной «А». Ей в словаре соответствует бинарное значение 010000000. Биты выписываем прямо так, LZW работает напрямую с битами, и то, что в байте обычно 8 бит, для этого алгоритма не имеет никакого значения.

А     010000000  (в словарь ничего не добавляем)

Следующая буква — «Б». Аналогично вписываем её, но теперь вместе с этим добавляем в словарь новую запись: предыдущая закодированная строка плюс первый символ этой. Прошлая строка была «А», эта — «Б», и её первый символ, соответственно «Б».

Б     010000001 | добавляем в словарь АБ = 100000000

Продолжим дальше:

Р     010010000 | БР = 100000001
А     010000000 | РА = 100000010
К     010001010 | АК = 100000011
А     010000000 | КА = 100000100
Д     010000100 | АД = 100000101

Дальше можно было бы точно так же записать «А», но у нас же уже есть в словаре «АБ»! Используем его. И не забываем, что в новую запись словаря идет только первая буква.

АБ    100000000 | ДА = 100000111
РА    100000010 | АБР = 100001000
<SP>  000100000 | РА<SP> = 100001001
С     010010001 | <SP>С = 100001010
<SP>  000100000 | С<SP> = 100001010
Х     010010101 | <SP>Х = 100001011

Теперь джекпот! У нас в словаре уже есть «АБР», и мы можем вставить всето одной буквы сразу три. Выбирать из словаря наиболее длинную подходящую строку кажется чертовски хорошей идеей.

АБР   100001000 | ХА = 100001100
А     010000000 | АБРА = 100001101
ХА    100001100 | АХ = 100001110
БР    100000001 | ХАБ = 100001111
А     010000000 | БРА = 100010000

Теперь все полученные биты (из второй колонки) выписываем в строчку, группируем по 8 байт и готово. Вместо 24×8 = 192 бит получили 18×9 = 162 бита. 15% экономии, при том, что RLE тут вообще ни одного бита не убрал бы.

Жадность — это скверно

В описании алгоритма указывается, что при кодировании нужно выбирать из словаря строку наибольшей длины. Но как учит песенка про мальчика Билли из «Острова Сокровищ», жадность не самый оптимальный вариант. Возьмем предыдущий пример и откатимся чуть-чуть назад:

А     010000000
Б     010000001 | АБ = 100000000
Р     010010000 | БР = 100000001
А     010000000 | РА = 100000010
К     010001010 | АК = 100000011
А     010000000 | КА = 100000100
Д     010000100 | АД = 100000101
АБ    100000000 | ДА = 100000111
РА    100000010 | АБР = 100001000
<SP>  000100000 | РА<SP> = 100001001
С     010010001 | <SP>С = 100001010
<SP>  000100000 | С<SP> = 100001010
Х     010010101 | <SP>Х = 100001011
АБР   100001000 | ХА = 100001100
А     010000000 | АБРА = 100001101

В этом месте мы молжем пойти против жадности и выбрать из словаря не «ХА» более короткую строку, «Х»:

Х     010010101 | АХ = 100001110
АБРА   100001101 | ХА = 100001111

Теперь длина закодированного сообщения 17×9 = 153 бита, разница около 5%. Но это мы вручную файл собирали, а как алгоритмически определить, не идти на поводу у жадности? В лоб не получится: сложность прямого перебора экспоненциальная. Так что, как говорится во всяких умных книжках, я оставлю это на рассмотрению читателю. Может, ещё премию Тьюринга получите.

Сжатие одинаковых значений

Попробуем теперь сжать примитивную строку, состоящую только из букв «А».

А   |
А   | АА
АА  | АА
АА  | ААА
ААА | ААА
...

Как-то не очень эффективно, словарь забивается дубликатами. Но на этот случай в LZW предусмотрен хитрый приём. Во второй строке мы добавляем в словарь «АА», хотя эта запись пригодилась бы нам прямо на месте. Собственно, так мы и можем сделать:

А   |
АА  | АА
ААА | ААА
...

Для определения новой записи имеет значение только первый кодируемый символ. Его мы точно знаем, это «А». Поэтому мы сначала добавляем новую запись в словарь, а потом ищем в нем строку с наибольшей длиной.

Этот подход работает не только с одинаковыми буквами, но и с более длинными последовательностями:

А   |
Б   | АБ
АБ  | БА
АБА | АБА
...

Вы можете удивиться, а как же декодер поведет себя, если ему скажут: «теперь вставь седьмую запись», а у него их в словаре всего шесть. Ничего страшного, он таким штукам обучен и поймет без проблем.

LZW в GIF

Ну что же, на кошках потренировались, теперь переходим к реальным действиями. Создадим GIF с вот таким нехитрым изображением.

Для удобства увеличено в 8 раз, настоящие размеры: 11×6 пикселей, высота каждой полосы 2 пикселя.

А чей это флаг? Ничей. Просто три горизонтальные полосы. Но если удобнее, можно считать это флагом Суверенной Цветовой Модели RGB.

Размер палитры выбираем точно так же, как в PCX,— как можно меньше. В изображении всего три цвета, так что будем использовать палитру из 4 цветов. Напомню, что для LZW порядок цветов в палитре значения не имеет, только длина кодов. Изображение в файле будет одно, так что нам без разницы, локальная это будет палитра, или глобальная. Пусть будет глобальной.

Интерлейс использовать не будем, пиксели будем выбирать просто слева направо, сверху вниз. Размер логического экрана 11×6, размер изображения такой же, размер кодов 2 бита, поехали!

Составялем словарь:

00 R (индекс палитры 0)
01 G (индекс палитры 1)
10 B (индекс палитры 2)
11 (индекс палитры 3)

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

Это еще не все. В словарь добавляем специальное значение «Clear Code». Оно не кодирует ничего, только инструктирует декодер сбросить словарь до начального состояния.

Также в словарь идет ещё одно особое значение «End of Information», оно указывает на то, что сжатый поток окончился. Зачем оно нужно? Предположим, что на одну запись словаря уходит 4 бита, и есть закодированное значение «00010010 00110000». Непонятно, то ли это раскодировать как 1 2 3, то ли как 1 2 3 0, а код EoI указывает конец потока с точностью до бита, и проблема исчезает.

Итого, изначальный словарь у нас выглядит так:

000 R (индекс палитры 0)
001 G (индекс палитры 1)
010 B (индекс палитры 2)
011 (индекс палитры 3)
100 <CC>
101 <EoI>

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

100 <CC>   |

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

Далее код первого пикселя. Если в PCX мы четыре пикселя с возможным значением от 0 до 3 склеивали в один байт, то в GIF этого делать не нужно.

000 R      |

Далее описанный выше приём: используем запись словаря одновременно с её добавлением.

110 RR     | RR = 110
111 RRR    | RRR = 111

Словарь заполнился, и его нужно увеличить на один бит. Следующая запись будет занимать уже 4 бита.

1000 RRRR   | RRRR = 1000

Закодировано 10 пикселей, а в одном сканлайне 11. Но в GIF нет ограничений, связанных со сканлайнами — все пиксели «вытягиваются в строчку», и кодируются как одна большая последовательность. Если бы мы использовали интерлейс, то следующей взяли бы синюю полосу, что, разумеется, на сжатии положительно бы не сказалось.

1001 RRRRR  | RRRRR = 1001
1010 RRRRRR | RRRRRR = 1010

21 красный пиксель закодирован, остался один. На этот раз пиксель кодируется четырьмя битами. Несмотря на то, что запись «RR» в словаре уже есть, добавляем её еще раз.

0000 R      | RRRRRRR = 1011

Продолжаем так же, с зелёными пикселями.

0001 G      | RG = 1100
1101 GG     | GG = 1101
1110 GGG    | GGG = 1110
1111 GGGG   | GGGG = 1111

Снова увеличиваем длину кодов.

10000 GGGGG  | GGGGG = 10000
10001 GGGGGG | GGGGGG = 10001
00001 G      | GGGGGGG = 10010
00010 B      | GB = 10011
10100 BB     | BB = 10100
10101 BBB    | BBB = 10101
10110 BBBB   | BBBB = 10110
10111 BBBBB  | BBBBB = 10111
11000 BBBBBB | BBBBBB = 11000
00010 B      | BBBBBBB = 11001

Наконец, указываем маркер конца данных.

00101 <EoI>  |

Теперь полученные биты пакуем по восемь штук в байт, от младшего к старшему. Из последовательности (100) (000) (110) (111) (1000) … получим:

10) (000) (100)       = 0x84
(1000) (111) (1       = 0x8F
...

А к полученным 13 байтам не забываем дописать в начале длину блока (0x0D = 13) и 0x00 в конце, чтобы показать, что изображение закончено.

И вот, наконец, что получилось: . Кажется, работает.

Сброс словаря

Если присмотреться, то окажется, что из трех одинаковых по размеру полос на красную пришлось 25 бит, на зеленую — 31, а на синюю уже 35. А как же, пришлось увеличивать размер кодов, чтобы работать с разрастающимся словарем.

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

Вернемся к концу красной полосы:

100 <CC>   |
000 R      |
110 RR     | RR = 110
111 RRR    | RRR = 111
1000 RRRR   | RRRR = 1000
1001 RRRRR  | RRRRR = 1001
1010 RRRRRR | RRRRRR = 1010
0000 R      | RRRRRRR = 1011

Сбросим словарь, и продолжим кодирование.

0100 <CC>   | (сброс словаря)
001 G      |
110 GG     | GG = 110
111 GGG    | GGG = 111
1000 GGGG   | GGGG = 1000
1001 GGGGG  | GGGGG = 1001
1010 GGGGGG | GGGGGG = 1010
0001 G      | GGGGGGG = 1011

И ещё раз.

0100 <CC>   | (сброс словаря)
010 B      |
110 BB     | BB = 110
111 BBB    | BBB = 111
1000 BBBB   | BBBB = 1000
1001 BBBBB  | BBBBB = 1001
1010 BBBBBB | BBBBBB = 1010
0010 B      | BBBBBBB = 1011
0101 <EoI>  |

Получилось 90 бит, а суммарный размер файла уменьшился с 52 до 51 байта, при том, что остался читаемым: . А вот, кстати, gifsicle, тулза номер один для сжатия GIF, так сжать уже не может.

Кстати, можно заметить, что все три полосы закодировались почти одинаково. Для LZW нет разницы между «0x00 22 раза» и «0x02 22 раза», и расположение цветов в палитре можно выбрать любое.

Нестандарт

Немного маньячества. Код сброса словаря («CC») в самом начале потока ни на что не влияет. А код конца потока («EoI»), в общем-то, и не нужен — если в хвосте байта и останутся какие-то данные, то они уже будут за пределами изображения. Вырезав их, мы можем ужать картинку ещё больше, до 50 байт, и она будет нормально отображаться в браузерах: .

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

Но есть одно но, и это «но» принципиальное: это нарушение спецификации. Стоит ли этого экономия в один байт — решайте сами.

Анимированный GIF

На сегодняшний день, пожалуй, это единственное применение GIF. Для неанимированных иконок и иллюстраций PNG гораздо круче. Но, к сожалению, форматы анимированных изображений на основе PNG «не взлетели»: APNG не является стандартом W3C, и поддерживается только половиной браузеров; а стандартный W3C'шный MNG вообще мертворожденный. Это дает возможность старичку GIF еще немного пожить.

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

Композиция

Тут следует начать с главного: если на логическом экране 800×600 с новым кадром поменялся только квадратик 2×2, то имеет смысл сделать кадр размером 2×2, а не 800×600. Думаю, это логично. Но, увы, не все программы обработки изображений заморачиваются таким анализом, и львиная доля оптимизации GIF приходится именно на исправление этой тривиальной ошибки.

А теперь к деталям, а именно к полю Disposal Method расширения изображения, которое указывает, что делать с кадром перед тем, как показывать новый. Немного повторюсь:

Значения 0 и 1 разными формулировками указывают рендереру ничего не делать. Т.е., пиксели следующего кадра рисовать прямо поверху (кроме прозрачных, само собой).

Значение 2 — перед показом нового кадра удалить с логического экрана всё. По спецификации логический экран должен быть заполнен фоновым цветом, на практике он становится полностью прозрачным.

Значение 3 самое интеlt;NULресное — перед показом следующего кадра вернуть всё, как было до показа текущего кадра. Так что, при кодировании, скажем, пятого кадра стоит определить разницу не только со четвертым, но и с третьим — вдруг так сожмется лучше.

Прозрачный цвет

Обратите внимание, прозрачный цвет указывается для каждого изображения, даже если используется глобальная палитра. Что нам может это дать? Посмотрим на картинку:

Сколько тут цветов? Красный, зеленый, синий, желтый и прозрачный — пять. Именно так думают GIMP и Photoshop. Но они ошибаются — тут только четыре цвета. Все четыре изображения-кадра абсолютно одинаковы, и используют глобальную палитру. Разница только в расширениях изображения, которые стоят перед ними, каждый цвет поочередно объявляется прозрачным.

Палитра и размер кодов

Хотя размер кодов LZW обычно и равен размеру (в количестве битов) палитры, такого требования в спеках нет. Нужно только чтобы сами кодируемые значения ссылались на существующие индексы палитры, а так можно хоть 24-битные коды использовать, если места не жалко.

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

Картинкой для примера будет… хм… а давайте опять НЛО! Анимация пусть будет несложной, всего два кадра.

Глобальная палитра в 8 цветов:

В первом кадре используем все восемь, при этом указываем, что цвет по смещению 0 (светло-синий) считается прозрачным.

Во втором же кадре нам понадобится только два первых цвета глобальной палитры: светло-синий и серый. И прозрачным на этот раз будет серый цвет (по смещению 1). И вот тут-то мы можем уменьшить размер кодов LZW до двух битов. При этом получится, что из восьми цветов мы сможем закодировать только цвета от 0 до 3, но ведь больше-то нам и не надо. Можно было бы и до одного, но по спецификации минимальный размер кодов — 2.

Проверяем, работает ли?

Работает. Ну, тогда склеиваем GIF'ки в одну и вуаля!

Картинка «весит» 437 байт. Если бы мы использовали локальную палитру, то файл занимал бы на 6 байт больше, 443 байта. А если бы увеличили глобальную палитру, как предлагает Photoshop, то уже 469 байт, а это уже около 7% разницы.

Итого

Резюмируем. Техники оптимизации GIF:

• Удаление ненужных блоков, в том числе расширений изображения;
• Выбор минимально возможной глубины цвета (размера палитры);
• Минимизация размеров изображений-кадров;
• Использование локальной палитры;
• Отход от жадности LZW;
• Cброс словаря LZW;
• Выбор между прогрессивным или чересстрочным сканированием (если допустимо);
• Использование способов очистки кадра: «оставить», «очистить», «отменить» (только для анимации);
• «Повторное использование» прозрачных цветов (только для анимации);
• Оптимизация палитры с целью уменьшить размер кодов (только для анимации).

Работает, но не поощряется:

• Удаление маркера конца потока LZW и кода сброса словаря в начале.

Продолжение следует

На сегодня всё. А следующая, заключительная, часть — графический формат PNG и его производные.

Автор: subzey

Источник