Доброго времени суток!
Вам когда-нибудь хотелось узнать как устроены файлы PNG? Нет? А я все равно расскажу.
Формат PNG(Portable Network Graphics) был изобретен в 1995 году, чтобы стать заменой GIF , а уже в 1996, с выходом версии 1.0, он был рекомендован W3C , в качестве полноправного сетевого формата. На сегодняшний день PNG является одним из основных форматов веб-графики.
Под катом вы найдете общее описание строения PNG-файла, некоторое количество картинок-схем, препарирование в hex-редакторе, и, конечно, ссылку на спецификацию.
Общее строение
Структура PNG в самом общем виде представлена на следующем рисунке.
То есть файл состоит из подписи и некоторого количества блоков(чанков, chunks), каждый из которых несет в себе некоторую информацию (спасибо КО!). Но почему подпись нельзя считать одним из чанков? Давайте разберемся поподробнее.
Подпись файла
Подпись PNG-файла всегда одинакова, состоит из 8 байт, и представляет собой (в hex-записи)Что же это означает?
- 89 - non-ASCII символ. Препятствует распознаванию PNG, как текстового файла, и наоборот.
- 50 4E 47 - PNG в ASCII записи.
- 0D 0A - CRLF (Carriage-return, Line-feed), DOS-style перевод строки.
- 1A - останавливает вывод файла в DOS режиме (end-of-file), чтобы вам не вываливалось многокилобайтное изображение в текстовом виде.
- 0A - LF, Unix-style перевод строки.
Chunks
Чанки - это блоки данных, из которых состоит файл. Каждый чанк состоит из 4 секций.
Разберем эти секции по порядку.
Длина
Ну, с длиной вроде все ясно. Просто числовое значение длины блока данных.Тип (имя)
С типом немного поинтересней. Тип представляет собой 4 чувствительных к регистру ASCII-символа. Регистры символов (пятый бит в числовой записи символа) в имени чанка различаются неспроста - это флаги, которые сообщают декодеру некоторую дополнительную информацию.- Регистр первого символа определяет является ли данный чанк критическим(верхний регистр) или вспомогательным(нижний регистр). Критические чанки должны распознаваться каждым декодером. Если декодер встречает критический чанк, тип которого не может распознать, он обязан завершить выполнение с ошибкой.
- Регистр второго символа задает «публичность»(верхний регистр) или «приватность»(нижний регистр) чанка. «Публичные» чанки - официальные, задокументированные, распознаваемые большинством декодеров. Но если вдруг вам для каких-то своих нужд понадобится кодировать специфическую информацию, то просто в имени чанка сделайте второй символ маленьким.
- Регистр третьего символа оставлен для будущих свершений. Предполагается, что он будет использоваться для дифференциации различных версий стандарта. Для версий 1.0 и 1.1 третий символ должен быть большим. Если он (внезапно!) оказался маленьким, все нынешние декодеры должны поступать с чанком, так же как и с любым другим не распознанным (то есть выходить с ошибкой если чанк критический, или пропускать в противном случае).
- Регистр же четвертого символа означает возможность копирования данного чанка редакторами, которые не могут его распознать. Если регистр нижний, чанк может быть скопирован, вне зависимости от степени модификации файла, иначе (верхний регистр) он копируется только в случае, когда при модификации не были затронуты никакие критические чанки.
Ниже приведен список типов чанков с краткими пояснениями.
Критические чанки
- IHDR - заголовок файла, содержит основную информацию о изображении. Обязан быть первым чанком.
- PLTE - палитра, список цветов.
- IDAT - содержит, собственно, изображение. Рисунок можно разбить на несколько IDAT чанков, для потоковой передачи. В каждом файле должен быть хотя бы один IDAT чанк.
- IEND - завершающий чанк, обязан быть последним в файле.
Вспомогательные чанки
- bKGD - этот чанк задает основной фоновый цвет.
- cHRM используется для задания CIE 1931 цветового пространства.
- gAMA - определяет гамму.
- hIST - в этом чанке может храниться гистограмма или общее содержание каждого цвета в изображении.
- iCCP - цветовой профиль ICC
- iTXt - содержит текст в UTF-8, возможно сжатый, с необязательной языковой меткой. iTXt чанк с ключевым словом "XML:com.adobe.xmp" может содержать Extensible Metadata Platform (XMP) .
- pHYs - содержит предполагаемый размер пикселя и/или отношение сторон изображения.
- sBIT (significant bits) - определяет «цветовую точность» (color-accuracy) изображения (черно-белое, полный цвет, черно-белое с прозрачностью и т.д.), для более простого декодирования.
- sPLT - предлагает палитру для использования, если полный спектр цветов недоступен.
- sRGB - свидетельствует о использовании стандартной sRGB схемы.
- sTER - индикатор стереоскопических изображений.
- tEXt - может содержать текст в ISO/IEC 8859-1 формате, с одной name=value парой для каждого чанка.
- tIME - хранит дату последнего изменения изображения.
- tRNS - содержит информацию о прозрачности.
- zTXt - сжатый текст, с теми же ограничениям, что и tEXt.
CRC
Контрольная сумма CRC-32 . Кстати на днях был топик о ее подсчете в Windows.Минимальный PNG
С общей структурой разобрались. Теперь разберем содержание обязательных чанков. Но какие из них обязательные (не критические, критические обязаны распознаваться декодером, а не присутствовать в каждом файле), и как выглядит минимальный PNG-файл? А вот как:
IHDR
Блок данных в IHDR содержит следующие поля:- Ширина, 4 байта
- Высота, 4 байта
- Битовая глубина (bit depth), определяет количество бит на каждый сэмпл(не пиксель), 1 байт
- Тип цвета, состоит из 3 флагов 1 (используется палитра), 2 (используется цвет, не монохромное изображение), and 4 (присутствует альфа-канал), 1 байт
- Метод сжатия. На данный момент доступно только значение 0 - сжатие по алгоритму deflate . Если значение отлично от 0, чанк считается нераспознанным, и декодер рапортует об ошибке. 1 байт
- Метод фильтрации. Так же, как и в случае сжатия, на данный момент может быть только нулем. 1 байт
- Interlace(переплетение) метод. Определяет порядок передачи данных. На данный момент доступно 2 значения: 0 (no interlace) и 1 (Adam7 interlace). 1 байт
IEND
Сигнализирует о конце файла, блок данных этого чанка не содержит ничего.IDAT
Содержит данные, закодированные, в соответствии с полем метода сжатия в заголовке. Алгоритм декодирования выходит за рамки данной статьи (однако если будут желающие, может появиться в следующей), но в довольно хорошо (и по-русски) описан .Таким образом, простейший PNG-файл (на примере ) выглядит следующим образом. 
Заключение
При написании данной статьи я ставил своей задачей дать читателю общие знания о строении PNG-файла, для более глубокого понимания рекомендуется читать спецификации .Топик на хабре про строение JPEG: habrahabr.ru/blogs/algorithm/102521
Топик на хабре про строение GIF: habrahabr.ru/blogs/algorithm/127083
Спасибо за внимание, буду рад любой критике!
Привет! В этой статье я познакомлю вас с устройством изображений в формате PNG, а так же с механизмом работы алгоритма Deflate. Мы на примере рассмотрим все аспекты этой темы. Надеюсь, вам будет интересно.
Дисклеймер
Данный материал не призван быть максимально объективным и академически верным. Автор статьи (в дальнейшем — я и другие личные местоимения первого лица) мог упускать некоторые моменты, а некоторые рассматривать лишь с одной стороны. Статья была рождена на свет исключительно из спортивного интереса, а также желания лучше понимать то, с чем я работаю каждый день. Если ты, дорогой читатель, не согласен со мной или считаешь, что я забыл дописать что-то очень важное, то, пожалуйста, напиши об этом в комментариях. Этим сотрудничеством мы сможем добиться ликвидации пробелов в знаниях и, быть может, сделать мир чуточку лучше.
Тем не менее, данная статья поможет начинающим примерно понять внутреннее устройство PNG (о котором и идёт речь), что создаст основу для дальнейшего развития.
В разделе «материалы» я оставил ссылки на полезные статьи и спецификации PNG и zlib, которые помогли мне понять всё то, о чём я написал (и даже больше). Иногда я прямо указываю на них, о чём пишу в виде «ссылка #{номер ссылки}».
Пример изображения
Внутреннее устройство PNG мы будем разбирать на примере маленького изображения 2 x 2 пикселя. Ссылку на него я оставлю в разделе «материалы» в нижней части страницы.
Вот так выглядит увеличенная копия изображения:
Долой длинные вступления. Начинаем!
Структура PNG
Не буду грузить читателя описанием формата, историей его появления и прочими вещами, которые никаким образом не относятся к теме статьи, а сразу же без всяких прелюдий перейду к рассмотрению структуры.
Любой файл PNG начинается со следующей последовательности байтов (в шестнадцатеричном представлении):
89 50 4E 47 0D 0A 1A 0A
Это так называемая подпись PNG (PNG file signature). 50 4E 47 — как раз и соответствуют символам P N и G из таблицы ASCII. Наличие данной строки указывает программе-декодеру, что она имеет дело с классическим изображением формата PNG, которое состоит из последовательности чанков (об этом ниже), первый из которых — это IHDR, а последний — IEND. Отчасти именно эта подпись позволяет большинству программ преспокойно прочитать изображение PNG, даже если у него в качестве расширения указан, скажем, JPEG.
PNG имеет удивительно логичную и лаконичную структуру, что позволяет без лишних затруднений читать, изменять и создавать изображения в этом формате. Как я уже выше упомянул, в основе структуры любого PNG-изображения лежит последовательность чанков (от англ. «chunk» — кусок, ломоть; я буду использовать именно это слово, вместо соблазнительного «блок», так как это позволит избежать путаницы), которые следуют друг за другом.
Каждый чанк состоит из следующих обязательных частей:
1. Length — информация о длине чанка. Нужна для того, чтобы декодер знал, когда заканчивается тот или иной чанк. Записывается при помощи 4 байт.
2. Chunk type — тип чанка. У каждого из них есть своё собственное предназначение, поэтому программа интерпретирует их по-разному. 4 байта.
3. Chunk data — непосредственно данные, которые содержит чанк. Длина зависит от того, что было указано в поле Length. Может быть пустым.
4. CRC — контрольная сумма Length и Chunk type, высчитанная при помощи алгоритма CRC-32. 4 байта.
Все чанки можно разделить на обязательные (critical) и вспомогательные (ancillary). Самые догадливые уже всё поняли, но я, всё же, опишу несколькими словами их различия. Обязательные чанки должны присутствовать в любом PNG-изображении, а вспомогательные — нет (вот это новость!). Отсутствие обязательного чанка вызовет ошибку, а вот отсутствие вспомогательного, даже если на него ссылается какой-нибудь другой чанк, декодер проигнорирует.
Названия обязательных чанков всегда начинаются с прописной буквы, а вспомогательных — со строчной (например IDAT — обязательный, а вот tIME — нет).
К обязательным чанкам относятся:
IHDR — содержит сведения об изображении: ширина, высота, глубина цвета и другие.
PLTE — содержит перечень цветов, используемых в изображении. Является обязательным, но в некоторых случаях может отсутствовать. Об этом немного позже.
IDAT — чанк, содержащий непосредственно данные изображения.
IEND — чанк, указывающий программе-декодеру на окончание файла. Данных не содержит.
Перечень вспомогательных чанков можно найти в документации PNG (ссылка #1), а обязательные мы разберем немного подробнее:
IHDR
Это самый первый из обязательных чанков. Важно запомнить, что он должен располагаться в самом начале документа. Состоит из 13 байт:
4 байта — ширина изображения
4 байта — высота изображения
1 байт — глубина цвета (bit depth)
1 байт — цветовая модель (color type)
1 байт — метод сжатия
1 байт — метод фильтрации
1 байт — метод чересстрочной развертки
Наиболее важными для нас являются 9 и 10 байты. Давайте рассмотрим их чуть подробнее.
Color type
Используемая цветовая модель. Может принимать следующие значения:
- 0 10 (000 2) — grayscale
Самое первое и самое простое значение. Каждый одноканальный пиксель кодируется 1, 2, 4, 8 или 16-битовым целым числом, которое выражает уровень яркости белого цвета. - 2 10 (010 2) — RGB/TrueColor
Три канала: красный, зеленый и синий. Каждый из каналов (для одного пикселя) кодируется 8 или 16-битным числом. - 3 10 (011 2) — индексированные значения
Содержит индексы каналов, которые находятся в чанке PLTE. Количество битов: 1, 2, 4 или 8. - 4 10 (100 2) — grayscale и альфа-канал: для каждого пикселя указывается прозрачность
2 канала: оттенок серого и альфа-канал. Каждый канал кодируется 8 или 16 битами. - 6 10 (110 2) — RGBA
То же самое, что и RGB, только с добавлением альфа-канала, который отвечает за степень прозрачности.
В виде таблицы:
| Bits per pixel | ||||||
|---|---|---|---|---|---|---|
| Color option | Channels | BIts per channel | ||||
| 1 | 2 | 4 | 8 | 16 | ||
| Grayscale | 1 | 1 | 2 | 4 | 8 | 16 |
| RGB | 3 | 24 | 48 | |||
| Indexed | 1 | 1 | 2 | 4 | 8 | |
| Grayscale and alpha | 2 | 16 | 32 | |||
| RGBA | 4 | 32 | 64 | |||
Глубина цвета
Цветовая глубина — значение, представляющее собой количество битов, которое необходимо для кодирования одного канала. Например, если у нас color type равен RGB, а глубина цвета — 8 бит, то количество битов, необходимое для кодирования 1 пикселя будет равняться 24.
То, что я написал выше, очень важно запомнить или записать, так как эта информация обязательно пригодится нам при расшифровке чанка IDAT.
В нашем случае чанк IHDR является следующей строкой (в шестнадцатеричном представлении):
00 00 00 02 00 00 00 02 10 02 00 00 00
Теперь нам совершенно не составит труда всё это расшифровать:
Ширина изображения — 2 пикселя.
Высота изображения — 2 пикселя.
Глубина цвета — 16 пикселей на канал.
Color type — 2.
Сжатие, фильтрация и чересстрочная развертка — по нулям.
Что же это означает? Color type равняется 2, значит используется цветовая модель RGB, т.е. комбинация красного, зелёного и синего каналов. Глубина цвета равняется 16, а значит каждый из этих каналов закодирован парой байтов. Отсюда также несложно понять, что для кодирования одного пикселя изображения используется 48 бит или 6 байт. Идём дальше.
PLTE
Считается обязательным чанком, но фактически является таковым только для color type 3. PLTE содержит от 1 до 256 трёхбайтовых цветов:
1 байт — красный (от 0 до 255)
1 байт — зелёный (от 0 до 255)
1 байт — синий (от 0 до 255)
Подробно на нём останавливаться я не собираюсь, так как на практике color type 3 встречается очень редко. Самые любознательные смогут найти исчерпывающую информацию в спецификации PNG (ссылка #1).
IDAT
Наконец-то мы добрались до содержимого нашего изображения. Чанк IDAT начинается с 4 байтов — 49 44 41 54, которые, собственно, и декодируется в «IDAT». Согласно спецификации PNG, содержимое IDAT сжато методом Deflate и упаковано в формат zlib. В общем случае чанк состоит из следующих обязательных частей:
- Zlib header, содержащий информацию о методе, степени сжатия и некоторую служебную информацию.
- Последовательность блоков со сжатой информацией, следующих друг за другом.
- Последовательность битов, представляющих собой контрольную сумму несжатых данных, сгенерированную при помощи алгоритма Adler-32
Давайте немного подробнее.
Zlib header
Спецификация RFC 1950 говорит нам, что zlib header должен состоять из двух байтов. Первый байт – это Compression Method and Flags (CMF), который в свою очередь содержит:
- Первые 4 бита (от младшего к старшему) — Compression Method (CM). Если CM равен 8, то это означает, что используется алгоритм Deflate (о котором я подробнее расскажу чуть дальше).
- Последние 4 бита – Compression Info (CINFO). Этот параметр отвечает за размер окна (речь о так называемом «скользящем окне», которое используется в алгоритме Deflate (подробнее об этом я напишу в соответствующем пункте) и находится следующим образом:
\(C=\log _{ 2 }{ W } -8,\)
где W — размер окна, C — CINFO.
Например, если CINFO равен 7, то
\(W={ 2 }^{ 7+8 },\)
что равняется 35768 байтам или 32 килобайтам.
Второй байт — Flags (FLG), содержит:
- Compression Level (FLEVEL) – степень сжатия.
- Preset Dictionary (FDICT) – Если он равен 1, то за байтом FLG должен идти словарь. Если я правильно понял, то это просто последовательность несжатых байтов, которая необходима для кодирования/декодирования содержимого. Словарь полезно использовать при небольших размерах файла.
- Check bits for CMF and FLG (FCHECK) – число, которое дополняет CMF * 256 + FLG до такого значения, чтобы оно было кратно 31.
Схематично Zlib header можно изобразить так:
| CMF | FLG | DICT (IF FDICT === 1) | |||
|---|---|---|---|---|---|
| CINFO | CM | FLEVEL | FDICT | FCHECK | |
| 0111 | 1000 | 11 | 0 | 11010 | |
В нашем случае: 78 DA или в двоичном представлении 0111100011011010:
- CM – 1000, что в десятичной равно 8. Согласно спецификации RFC 1950 – это Deflate.
- CINFO – 0111, в десятичной — 7. Мы можем сразу же найти размер окна:
\(7+8=15;\)
\(\log _{ 2 }{ x } =15;\)
\(x={ 2 }^{ 15 }\) — размер окна равен 32 килобайта.
- FLEVEL — 11 2 или 3 10 . (RFC 1950) – compressor used maximum compression, slowest algorithm – максимальное сжатие.
- FDICT – 0 – словарь не используется.
- FCHECK – 11010 2 или 26 10
Проверим. Для удобства переведём всё это в десятичную систему:
CMF: \({ 78 }_{ 16 }={ 120 }_{ 10 }\)
FLG — FCHECK: \({ 11000000 }_{ 2 }={ 192 }_{ 10 }\)
\(120\times 256+192=30912\)
\(\dfrac { 30912 }{ 31 } =997,161290…\) — не кратно 31
Ближайшее целое число такое, что \(x\times 31\ge(120\times 256+192)\), это 998.
Значит \(998\times 31-30912=26\)
Получилось 26. Это и есть наш FCHECK. Всё правильно.
Изучаем сжатые данные
Это самый скучный и однообразный процесс. Внутри этих блоков мы ожидаем увидеть последовательность строк, каждая из которых начинается со значения FILTER — фильтра (речь о фильтрации, используемой при сжатии для увеличения его эффективности). FILTER может принимать значения от 0 до 4, которые носят названия «None», «Sub», «Up», «Average», «Paeth». Для чего это нужно? При больших размерах файла фильтрация может помочь сократить занимаемое изображением пространство. Например, фильтр «Sub» означает, что нужно сложить значение текущего пикселя со значениями предыдущих пикселей в строке. Вот так выглядит формула для декомпрессии с использованием «Sub»:
\(Raw(x)=Sub(x)+Raw(x-bpp)\),
где Raw(x) — искомое значение, Raw(x-bpp) — сумма значений уже декодированных байтов в строке, Sub(x) — отфильтрованное значение текущего пикселя.
Считываем блоки, помня про спецификацию RFC 1950, которая гласит, что блок начинается с трёхбитного заголовка:
- 00 – без сжатия
Внимательность: каждый байт рассматривается в виде последовательности битов, идущих от младшего к старшему. Например, байт 11100001 мы прочитаем как 10000111.
В работе будем использовать таблицу фиксированных кодов Хаффмана (для фиксированных значиний, разумеется), таблицу смещений и таблицу длин. Давайте их и рассмотрим.
Таблица фиксированных кодов Хаффмана
Как мы будем её использовать? Очень просто, на самом деле. Сначала берём первые 7 битов (минимальное значение, см. таблицу), после этого смотрим на префикс нашей получившейся последовательности. Префиксом называется подстрока, начинающаяся с 1 символа. Таблица кодов Хаффмана построена таким образом, чтобы по ней можно было однозначно декодировать наше значение, так как ни один из кодов не является подстрокой для другого кода. Это позволит нам по префиксу восстановить правильное значение. Для тех, кто не очень понял, объясню на примере:
Допустим, у нас есть последовательность 110011000011001. Берём первые 7 битов — 1100110. Теперь смотрим в таблицу и в третьем столбце находим такой промежуток, чтобы наша последовательность при соответствии старших битов однозначно попадала в него. Начнём с первой строки — промежуток равен , смотрим:
\(1100110\_ >10111111\)
Нижними подчёркиваниями я обозначил любые значения, ибо они нам в данный момент безразличны.
Как видим, наше значение не попадает в первый промежуток. Идём дальше:
\(110010000\lt1100110\_\_\lt111111111\)
А вот тут уже интереснее. Значение действительно попадает в промежуток. Теперь смотрим во второй столбец и видим, что необходимое количество битов — 9. Значит берём еще два бита, после чего наша измученная последовательность выглядит так: 110011000.
Теперь, чтобы восстановить исходное значение, нужно воспользоваться следующей формулой:
\(V=D-B+L\)
V — искомое значение, D — наша последовательность, B — нижнее значение из 3 столбца таблицы, L — нижнее значение из 1 столбца таблицы.
Код 256 — признак конца блока, символы 286 и 287 лишние.
Таблицы длин и обратных смещений
Тут тоже нет ничего сложного. Если код, который мы высчитали по предыдущей таблице попадает в промежуток от 257 до 285 (то есть, 3 и 4 случаи, исключая код 256, 286 и 287), то наше итоговое значение будет высчитываться по длине и обратному смещению. Но что же это? А это и есть результат работы Deflate. Название таблицы говорит само за себя. Когда мы натыкаемся на подобную команду, нужно отступить назад на количество битов, равное обратному смещению и взять количество битов, равное длине.
Код 285 обозначает длину 258
Внимательность: пара замечаний по таблице. Я так понимаю, она была сгруппирована по доп. битам и сделано это лишь с целью экономии места. Поэтому немного объясню. Первая колонка содержит диапазоны кодов, а вторая — соответствующие им диапазоны длин. То есть, например, коду 265 соответствуют длины 11-12, 266 — 12-13, 267 — 13-14, ну и так далее со всеми остальными. Дополнительные биты нужны для того, чтобы в этом диапазоне длин выбрать нужное значение. Если, например, у нас длины равны 12-13 и есть 1 дополнительный бит, то 0 будет указывать на 12, а 1 — на 13. Думаю, логика примерно ясна.
Таблица обратных смещений:
| Таблица смещений | ||
|---|---|---|
| Коды | Доп. биты | Диапазон смещений |
| 0-3 | 0 | 1-4 |
| 4,5 | 1 | 5-6, 7-8 |
| 6,7 | 2 | 9-12, 13-16 |
| 8,9 | 3 | 17-24, 25-32 |
| 10,11 | 4 | 33-48, 49-64 |
| 12,13 | 5 | 65-96, 97-128 |
| 14,15 | 6 | 129-192, 193-256 |
| 16,17 | 7 | 257-384, 385-512 |
| 18,19 | 8 | 513-768, 769-1024 |
| 20,21 | 9 | 1025-1536, 1537-2048 |
| 22,23 | 10 | 2049-3072, 3073-4096 |
| 24,25 | 11 | 4097-6144, 6145-8192 |
| 26,27 | 12 | 8193-12288, 12289-16384 |
| 28,29 | 13 | 16285-24576, 24577-32768 |
Логика здесь точно такая же. После того, как мы нашли значение длины, считываем еще 5 битов (от младшего к старшему, естественно), переводим в десятичное представление для удобства. Этот код находим в таблице, используем дополнительные биты при необходимости и находим обратное смещение. Поехали дальше, начнём разбирать наш код.
Приступаем
Для удобства переведём всю последовательность в двоичный код (можно написать программу для этого, можно сделать вручную, а можно воспользоваться калькулятором, которых в Интернете полно; лично я предпочитаю первый вариант). Итак, у нас получается код (не забывайте про нули, их здесь может и не быть, но каждый байт обязательно является двоичным восьмибитным числом):
01100010 01011000 10110001 1010100 1000001 10100001 10100000 11100000 11111111 11111111 11111111 11111111 11111111 11111111 1100111 10000000 1010000 10000 | 100001 01000000 00000000 00000000 00000000 11111111 11111111 11011100 01000111 00010000 11001111 1001001 1000101 1001110 1000100
Выглядит эффектно, правда? На самом деле, тут всё просто. Начинаем:
1. Считываем первые 3 бита, заголовок первого блока.
| 0 | 10 | 00110
BFINAL — 0 — блок не последний.
BTYPE — 10 — используются фиксированные коды Хаффмана.
2. На этом этапе нужно брать минимум 7 битов, определять префикс. Далее уже переводить в число, либо считать смещения и длины. Что же мы стоим? Вперёд!
2.1 Берём первые 7 битов: |00110 00| 011010
0011000 — префикс попадает в первую категорию, а значит число должно иметь длину 8 бит. Берем еще один — 00110000.
По формуле находим значение:
\(F=00110000-00110000+0\)
\(F=0\)
Таким же образом проделываем всю остальную работу. Мы помним, что для кодирования 1 пикселя в нашем случае используется 6 байтов. Считаем их всех, а потом ненадолго остановимся:
… : |1101 001| 01| 010
\({ R }_{ 2 }=421-400+144=165\)
… : |010 1000| 0| 010
\({ G }_{ 1 }=80-48+0=32\)
… : |010 1000|0| 101
\({ G }_{ 2 }=80-48+0=32\)
… : |101 0000|0|101
\({ B }_{ 1 }=160-48+0=112\)
… : |101 0000|0|111
\({ B }_{ 2 }=160-48+0=112\)
Самые смышлёные тут опять же вспомнят, что в данном изображении используется цветовая модель RGB с глубиной цвета 16 бит. Каждый их трёх каналов закодирован двумя байтами. Чтобы получить 16-битное значение мы должны просто конкатенировать два байта. Далее, если мы захотим преобразовать их в 8-битный аналог, то я предлагаю решить следующую пропорцию. Можно, конечно же, просто отбросить второй байт, но тогда есть небольшая вероятность того, что полученное значение будет искажено. Поехали:
Переводим и соединяем:
\({ 168 }_{ 10 }={ 10101000 }_{ 2 },\)
\({ 165 }_{ 10 }=10100101_{ 2 },\)
\({ 1111111111111111 }_{ 2 }={ 65535 }_{ 10 }\) — конкатенация 255 и 255,
\({ 1010100010100101 }_{ 2 }={ 43173 }_{ 10 }\)
Отсюда x:
\(\dfrac { 65535 }{ 43173 } =\dfrac { 255 }{ x },\)
\(65535\times x=255\times 43173,\)
\(x=\dfrac { 255\times 43173 }{ 65535 },\)
\(x=\left\lceil 167,9 \right\rceil =168\)
Символами \(\lceil\) \(\rceil\) обозначают потолок, то есть округление до целого в большую сторону.
Получилось, что R в нашем случае равен 168. Если мы проделаем то же самое с G и B-каналами, то получим, что цвет нашего первого пикселя в RGB-представлении равен (168, 32, 112). Теперь посмотрим на скриншот:
Мы движемся в верном направлении. А это значит, что нет смысла останавливаться! Второй пиксель декодируем так:
Сразу же можно предугадать сколько битов нам понадобится:
… : 111 111111|11 1111111 | 1 11111111 | 11111111 1 | 1111111 11 |111111 111 | 00110
Путём несложных вычислений получаем наш код: RGB(255, 255, 255) — белый цвет. Всё верно. На этом строка заканчивается, так как её ширина составляет всего 2 пикселя. Приступаем ко второй (и последней) строке:
… : | 00110 00 | 0 | 00001
\(F=48-48+0=0\)
… : | 00001 00 |00101 | 0 |
Значение попадает в третий промежуток, давайте разбираться. По формуле получим следующий код:
\({ 0000100 }_{ 2 }-{ 0000000 }_{ 2 }+{ 256 }_{ 10 }={ 260 }_{ 10 }\)
Заглянем в таблицу длин и получим значения:
1. Длина — 6
2. Доп. биты — 0
Теперь считываем следующие 5 битов, которые являются обратным смещением: \(00101=5\)
По таблице:
1. Доп.биты — 1
2. Расстояние 7,8
Следующий бит скажет скорректирует смещение. Он равен 0, значит фактическое смещение равняется 7.
А вот тут самое интересное. Наш «курсор» находится сразу же после байта со значением FILTER (который равен 0). Вернёмся на 7 байтов назад (обратное смещение) и скопируем 6 байтов (это как раз байты последнего пикселя первой строки):
\({ R }_{ 1 }=511-400+144=255\)
\({ R }_{ 2 }=511-400+144=255\)
\({ G }_{ 1 }=511-400+144=255\)
\({ G }_{ 2 }=511-400+144=255\)
\({ B }_{ 1 }=511-400+144=255\)
\({ B }_{ 2 }=511-400+144=255\)
Вот и всё. Ничего тут страшного нет. Цвет первого пикселя второй строки — RGB(255, 255, 255), что правда. Ух, надо идти вперёд! Я буду краток:
3-й промежуток. Код — 260:
1. Длина — 6
2. Доп. биты — 0
Смещение:
| 0 1000 | 010 | 0
\({ 01000 }_{ 2 }={ 8 }_{ 10 }\)
1. Доп. биты — 3
2. Длина — 17-24
Смещение = \(17+2=19\)
Получаем:
\({ R }_{ 1 }=424-400+144=168\)
\({ R }_{ 2 }=421-400+144=165\)
\({ G }_{ 1 }=80-48+0=32\)
\({ G }_{ 2 }=80-48+0=32\)
\({ B }_{ 1 }=160-48+0=112\)
\({ B }_{ 2 }=160-48+0=112\)
Цвет — RGB(168, 32, 112). В принципе, может показаться, что это всё. Но на самом деле, нет. Считываем дальше:
|0 000000|00
\(0-0+256=256\)
256 — признак конца блока. Мы закончили.
Итак, что у нас получилось? Две строки по два пикселя. Первый имеет цвет RGB(168, 32, 112), второй RGB(255, 255, 255), третий и четвёртый — RGB(255, 255, 255) и RGB(168, 32, 112) соответственно. Если вы вспомните изображение, то поймете, что это недалеко от правды. Значит, мы всё делаем правильно, что внушает надежду на светлое будущее.
Судя по всему, начало нового блока? Ладно. Сжатия нет, блок последний.
Здесь самый простой вариант — без сжатия. В этом случае после заголовка идёт выравнивание на границу байта (то есть мы должны взять оставшееся количество битов в этом байте). Потом два байта — LEN и еще 2 — NLEN.
LEN — длина несжатых данных, NLEN — дополнение LEN до единицы.
00000000 00000000 — LEN
11111111 11111111 — NLEN
Как мы видим, всё действительно так. Единственное, что LEN = 0, т.е. данных нет. Зачем это сделано — непонятно.
Ну и наконец, в самом конце чанка IDAT следует четырёхбайтовая хеш-сумма несжатых данных, высчитанная по алгоритму Adler-32. В нашем случае, хеш-сумма в двоичном представлении выглядит так:
11011100 01000111 00010000 11001111
Adler-32
Подробную информацию о том, как работает Adler-32 можно найти по ссылке #5. А мы пока возьмем последовательность расшифрованных байтов и захешируем её.
Последовательность (в десятичном представлении):
0 168 165 32 32 112 112 255 255 255 255 255 255 0 255 255 255 255 255 255 168 165 32 32 112 112
Я набросал на PHP простенький код:
$array = explode(" ", $uncompressed);
$start_1 = 1;
$start_2 = 0;
foreach($array as $num)
{
$temp_1 = $start_1 + trim($num);
$temp_2 = $start_2 + $temp_1;
$start_1 = $temp_1;
$start_2 = $temp_2;
$hash = sprintf("%016b", $temp_2 % 65521) . sprintf("%016b", $temp_1 % 65521);
Переменная $hash после выполнения кода содержит строку:
11011100010001110001000011001111
Найдите 10 отличий. Хеш-суммы совпадают, а поэтому с полной уверенностью заявляю, что мы сделали всё верно! Со следующего байта уже начинается чанк IEND, с IDAT же мы наконец-то закончили.
Стоит признать, что это было довольно просто. В пункте про алгоритм Deflate мы также рассмотрим декодирование строки (да, для примера возьмем обычную строку) с динамическими кодами Хаффмана.
IEND
Обязательный чанк, который должен следовать после всех остальных. Символизирует окончание PNG-документа и не содержит какой-либо информации.
Deflate
Чтобы сильно не утомлять моего читателя, который к этому моменту мог уже слегка подустать, расскажу лишь то, что встречалось выше. Данные в PNG хранятся в формате zlib и представляют собой последовательность блоков, сжатых при помощи Deflate. Deflate — это алгоритм сжатия, комбинирующий LZ77 и метод Хаффмана. Если очень коротко, то несжатая последовательность обрабатывается при помощи LZ77, после чего получившиеся коды упаковываются при помощи алгоритма Хаффмана.
LZ77
Сам алгоритм довольно сложный, поэтому объясню его принцип, что называется, «на пальцах». LZ77 — это алгоритм сжатия без потерь, основанный на принципе «скользящего окна» (помните я писал про размер окна?), призванный заменять последовательности, встречающиеся чаще одного раза, на ссылки, указывающие на самые ранних из них. Что я имею в виду? Программа поочерёдно считывает последовательность битов, держа «в голове» (то есть в буфере) информацию об уже прочитанных битах. Когда программа натыкается на последовательность, которая уже содержится в буфере, то она полностью заменяется ссылкой, которая представляет собой сведения о смещении и длине последовательности. Смещение может быть как прямым (то есть начинаться от начала окна, либо от произвольной точки), так и обратным (отсчитываться смещение будет в обратном порядке относительно обрабатываемого бита). На самом деле, я не особо уверен в существовании прямого смещения, так как на практике не встречал, но в разных документах я видел упоминания о нём . Проще говоря, программа-интерпретатор получает указания отступить на n шагов назад и взять m байтов. Размер окна — это и есть размер нашего буфера, то есть расстояние от первого бита, который программа еще помнит, до первого бита, который программа уже помнит. Во время кодирования, программа без проблем может заменять комбинации, которые пока еще лежат за пределами окна.
Алгоритм Хаффмана
Еще один алгоритм сжатия без потерь, заменяющий все символы входящей последовательности на специальные коды таким образом, что самые часто встречающие символы образуют самые короткие коды. Алгоритм пробегается по строке, подсчитывая частоту вхождения каждого символа, потом выстраивается очередь с приоритетом, где самыми первыми встраиваются элементы с наименьшей частотой. После чего выстраивается бинарное дерево, в котором каждый символ является концевой вершиной. В конце концов каждый символ получает свой код исходя из того, насколько далеко он располагается относительно корня. Есть смысл объяснять подробнее?
Ладно, уговорили. Допустим, у нас есть строка: «Hello, World!». Поехали:
1. Сначала выстраиваем список «Символ — частота»:
H - 1 e - 1 l - 3 o - 2 , - 1 W - 1 r - 1 d - 1 ! - 1
2. Сортируем его по частоте и создаем очередь. Приоритетом является частота. При этом, элементы с самым низким приоритетом выстраиваются в самом начале:
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | | H | e | , | W | r | d | ! | o | l |
3. Теперь создаем бинарное дерево. Алгоритм такой: Берем первые два элемента и формируем из них мини-дерево, где листьями будут наши элементы. В таблицу записываем сумму приоритетов, помещая его в нужное место:
| 1 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | | , | W | r | d | ! | o | / \ | l | H e
Таким же образом делаем со всеми остальными. В итоге получается такое дерево:
| 11 | / \ /\ / \ l /\ /\ /\ o /\ , w r w H e
Общий приоритет — 11. Теперь присвоим коды. Каждая левая ветка — 0, правая — 1. В итоге получается что-то вроде этого:
L - 00 o - 010 H - 0110 e - 0111 , - 100 w - 101 r - 110 d - 111
Теперь нужно заменить нашу последовательность полученными кодами и выстроить таблицу, чтобы интерпретатор мог без проблем её декодировать. В принципе, это всё.
Ближе к теме
Я уже выше писал, но напомню еще раз. Данные состоят из блоков, следующих друг за другом последовательно. Каждый из них содержит заголовок, состоящий из 3 битов (RFC 1950):
1 бит – BFINAL. Устанавливается в 1, если данный блок последний.
2 бита – BTYPE. Содержит информацию о типе сжатия:
- 00 – без сжатия
- 01 – сжатие с фиксированными кодами Хаффмана
- 10 – сжатие с динамическими кодами Хаффмана
- 11 – зарезервированное значение. Установка его вызовет ошибку.
«Без сжатия» означает, что данные представлены в нетронутом виде. Мы рассмотрели работу с подобными данными в подпункте IDAT пункта «структура PNG».
«Сжатие с фиксированными кодами Хаффмана» — данные сжаты с помощью уже заранее предопределенных кодов. Этот способ мы тоже рассмотрели.
«Cжатие с динамическими кодами Хаффмана» — в данном случае, сжатая последовательность состоит из кодов, создаваемых «на лету». Коды и их значения хранятся непосредственно в блоке. Давайте рассмотрим немного подробнее.
Для урока я взял простую последовательность, которая не включает в себя длины и смещения. Тем не менее, работать с подобными данными мы уже умеем, так как это было рассмотрено выше, а метод сжатия значения не имеет, ибо всё происходит точно так же. Также уточню, что строка ниже не содержит заголовка zlib и контрольной суммы. Мы рассматриваем только Deflate.
Пример Deflate с динамическими кодами Хаффмана
Предположим, у нас есть следующая последовательность:
05 A0 61 0B 00 00 18 86 2E 68 8F EA D9 3D AE C7 B4 9B 10 E8 FF 40 21 07 14 56 5A DA
В двоичном представлении:
00000101 10100000 01100001 00001011 00000000 00000000 00011000 10000110 00101110 01101000 10001111 11101010 11011001 00111101 10101110 11000111 10110100 10011011 00010000 11101000 11111111 01000000 00100001 00000111 00010100 01010110 01011010 11011010
Считываем по байтам, биты от младшего к старшему. Первые 3 байта — заголовок:
101 — последний блок, динамический Хаффман. Да, информация о типе сжатия берется справа-налево, если мы идём от младшего к старшему. Дальше идут следующие значения:
HLIT — 5 бит, которое равно: количество_длин_и_символов минус 257. В нашем случае, 0, значит количество длин и символов — 257.
HDIST — 5 бит, которое равно: количество_смещений минус 1. В нашем случае 0, значит количество смещений — 1.
HCLEN — 4 бита, которое равно: количество_длин_и_команд минус 4. В нашем случае 11. Значит количество команд и длин — 15.
Давайте ненадолго остановимся и рассмотрим всё это. Блок с динамическими кодами состоит из следующих частей (исключая заголовок и описание длин):
1. Сначала следуют трёхбитовые длины команд и кодов, которых FCLEN + 4. Длины нам помогут декодировать наши значения.
Дело в том, что у каждого кода и команды есть длина (0110 — 4, 111 — 3). Знание длин команд и кодов даёт нам возможность узнать сами коды, нигде их не записывая. Как это работает? Допустим, у нас есть 5 кодов, которые имеют длины соответственно 2, 3, 4, 4, 4. Если при кодировании использовались канонические коды, то мы без проблем их восстановим. Начинаем с наименьшей длины, присваиваем ей код 00. а дальше увеличиваем их в пределах своей длины, дописывая 0, если длина меняется:
Длина - код 2 - 00 3 - 010 4 - 0110 4 - 0111 4 - 1000
Еще раз, если не очень понятно. Если у нас одна длина, то увеличиваем значение на 1. Если длина меняется — увеличиваем на единицу и дописываем 0. Таким образом мы избавляемся от префиксов, то есть мы уверены, что ни один из кодов не является подстрокой для другого. А это позволяет интерпретатору однозначно декодировать значения. Удобно, правда?
Внимательность: в первой части мы получаем лишь длины, которые в последствии пригодятся при декодировании. Мы получаем длины тем же способом, что я описал выше.
Коды и команды следуют в следующем порядке: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15.
Здесь:
0-15 — длины непосредственно кодов.
16 — длина команды, которая говорит интерпретатору повторить предыдущее значение n раз. Следующие 2 бита как раз являются этим n.
17 — повторить значение 0 n раз. 3 бита являются значением n.
18 — повторить значение 0 n раз. 8 битов являются значением n.
2. Далее идёт последовательность из HLIT + 257 команд и значений закодированных символов, которые можно найти, исходя из их позиции в потоке данных (на примере я объясню этот момент). В предыдущем блоке мы получили их длины. Теперь же мы сможем сопоставить распакованное значение и длину кода, которым оно закодировано. Используя приведённый выше алгоритм, зная длины кодов и их значения, мы без проблем найдем сами коды.
3. Последним идёт блок со сжатыми данными. На этом этапе мы уже знаем коды и их значения (или длины и смещения). Поэтому без проблем можем декодировать строку.
Если у вас каша в голове, то не переживайте, сейчас на примере мы всё разберём. Поехали!
Итак, берём HCLEN + 4 (15) трёхбитовых значений:
|16 | 17 | 18 | 0 | 8 | 7 | 9 | 6 | 10 | 5 | 11 | 4 | 12 | 3 | 13 | 2 | |000 | 011 | 011 | 010 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 011 | 000 | 011 | 000 | 010 |
Отбросим все значение, где длина равна 0 и переведём в десятичную систему:
0 - 2 2 - 2 3 - 3 4 - 3 17 - 3 18 - 3
Теперь восстанавливаем коды длин:
0 - 00 2 - 01 3 - 100 4 - 101 17 - 110 18 - 111
Затем у нас следуют 257 длин и команд. Здесь мы и применяем наши длины символов и команд. Давайте я покажу как найти значение.
Допустим, возьмём первый код. Благодаря тому, что у нас отсутствуют префиксы, мы можем правильно определить коды. Первый код в нашем потоке — это 111. Смотрим выше и понимаем, что 111 соответствует 18. Смотрим еще выше и вспоминаем, что 18 это команда. Нам требуется еще 7 битов, возьмем же их — 0100000 (32). Это значит, что нам нужно повторить значение 0 32 раза. Самый первый символ имеет позицию 0. Если мы «передвинемся» по нашей последовательности на 32 бита вправо (включая 0), то окажемся на 31 бите. Это всё.
Дальше берём следующую порцию битов — 101. 101 соответствует длине 4. Запоминаем этот код и делаем еще один шаг — 32. Это значит, что первые код с длиной, равной 4, имеет значение 32. Возможно, это не совсем корректное объяснение, но так проще всего понять. Всё остальное делаем точно так же:
Длина/команда - значение/повторения. Если 0 - просто делаем еще один шаг. | 18 | 32 | 4 - 32 | 4 - 33 | 18 - 10 | 4 - 44 | 18 - 27 | 4 - 72 | 18 - 14 | 4 - 87 | 18 - 12 | 4 - 100 | 4 - 101 | | 111 | 0100000 | 101 | 101 | 111 0001010 | 101 | 111 0011011 | 101 | 111 0001110 | 101 | 111 0001100 | 101 | 101 | | 17 - 6 | 2 - 108 | 0 | 0 | 3 - 111 | 0 | 0 | 4 - 114 | 18 - 138 | 0 | 0 | 0 | 256 | 0 | 110 110 | 01 | 00 | 00 | 100 | 00 | 00 | 101 | 111 1111111 | 00 | 00 | 00 | 101 | 00 |
Общаясь со своими коллегами на различных семинарах и в студии, я пришел к выводу, что для многих единственным преимуществом формата PNG является наличие честной полупрозрачности. Если поискать в интернете информацию об этом формате, несложно заметить, что веб-разработчики разделились на два лагеря. Первые пишут о том, какой этот формат замечательный, оперируя чисто техническими данными, непонятными обычным кодерам и дизайнерам (к примеру, о превосходстве deflate-алгоритмов сжатия над LZW), другие же оставляют комментарии разной степени глупости о бесполезности PNG, не потрудившись даже вникнуть в суть вещей, описанных в спецификации.
Попробуем разобраться, какие преимущества дает этот формат, чтобы научиться ими пользоваться при подготовке иллюстраций для веба.
Начнем с терминологии. Предполагаю, что большинство читателей пользуются фотошопом и встречали там названия PNG-8 и PNG-24. Это не два разных формата, а всего лишь вариации одного и того же PNG. Формат позволяет хранить три типа изображений: greyscale (для описания изображения используется один канал — белый), indexed-colour (используется палитра цветов, как в GIF) и truecolor (используется три канала — RGB).
Самое главное преимущество формата PNG — это, конечно же, новые алгоритмы сжатия. Все помнят, что GIF эффективно сжимает только горизонтальные одноцветные области? Про это ограничение теперь можно забыть:
| GIF, 2568 байт |
|
Вторым важным преимуществом является фильтрация строк (scanline filtering, или delta filters), благодаря которой PNG-упаковщик может получить гораздо более удобные данные для сжатия.
Рассмотрим на примере, как они работают. Возьмем изображение 5×5 пикселей с горизонтальным градиентом и схематично отобразим, как оно может быть сохранено в файле (каждое число — уникальный цвет).
Как видно из примера, GIF-кодировщик отдал бы на сжатие строки, которые плохо упаковываются по горизонтали (потому что одинаковые цвета распространяются по вертикали). А вот как может преобразовать эти данные PNG-кодировщик:
Перед каждой строкой появилась цифра 2. Это — фильтр, который был применен к строке. В данном случае это фильтр Up, который говорит декодеру: «Для текущего пикселя возьми значение пикселя выше и прибавь к нему текущее значение». В нашем случае это 0, потому что цвета текущего и верхнего пикселей не отличаются. А эти данные можно эффективней упаковать, если у нас достаточно большое изображение.
Почему я написал может ? Потому что в нашем идеализированном случае более эффективной была бы такая схема:
Тут применен фильтр 1 под названием Sub, который говорит декодеру: «Возьми значение пикселя левее текущего и прибавь ему текущее значение». В данном случае 1.
После фильтрации все строки (вместе со значениями фильтров) объединяются в одну последовательность, которая затем сжимается deflate-алгоритмами (их обсуждение выходит за рамки этой статьи).
Проверим работу фильтров:
Внимательный читатель может заметить, что фильтры применяются не ко всему файлу целиком, а к строкам. Это значит, что каждая строка может иметь свой фильтр. Получается, что способов фильтрации одного изображения может быть 5 высота картинки. В общем-то, задача хорошего кодировщика как раз заключается в том, чтобы подобрать такие значения фильтров, при которых объем файла будет минимальным. К сожалению, фотошоп не всегда хорошо справляется со своей работой, поэтому на помощь приходят различные утилиты вроде и , которые в большое количество проходов подбирают разные способы фильтрации и стратегии сжатия данных, значительно сокращая тем самым объем некоторых сложных изображений. Однако стоит помнить, что эти программы не гарантируют уменьшение объема для каждого файла, они всего лишь пытаются найти оптимальный способ кодирования данных.
Еще один больной укол фотошопу за то, что он не умеет сохранять изображения в greyscale-режиме, то есть не умеет понижать глубину цвета. Тут нас опять спасут вышеозначенные утилиты, которые по возможности снижают глубину цвета, не ухудшая при этом качества картинки.
|
8167 байт |
6132 байта |
Преимущества greyscale над truecolor очевидны: к примеру, белый цвет в первом случае записывается (в десятичной системе счисления) числом 255, а во втором — 16777215.
Теперь, вооружившись знаниями о хранении данных в формате PNG, мы можем применять их в подготовке изображений для веба. Об этом — в следующих статьях.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Расчетно-графическая работа
Тема: «BMP, PCX, PNG – форматы»
По курсу «Сетевые информационные технологии »
Выполнил:
Группа:
АВТ-918
Проверил:
Новосибирск, 2013г.
1. Теоретическая часть
1.1. Введение
1.2. PNG – формат
1.2.1. Общая информация
1.2.2. Область применения
1.2.3. Структура файла
1.2.4. Достоинства
1.2.5. Недостатки
1.3. PCX – формат
1.3.1. Общая информация
1.3.2. Область применения
1.3.3. Структура файла
1.3.4. Достоинства
1.3.5. Недостатки
1.4. BMP – формат
1.4.1. Общая информация
1.4.2. Область применения
1.4.3. Структура файла
1.4.4. Достоинства
1.4.5. Недостатки
1.5. Сравнительная характеристика форматов
2. Практическая часть
1. Теоретическая часть
- Особенности растровой графики
Растровая графика описывает изображения с использованием цветных точек - пикселей, расположенных на сетке. Например, серфер в море описывается конкретным расположением и цветом каждой точки изображения, примерно, как в мозаике (фотографии, отсканированные рисунки и т. д.). При редактировании растровой графики изменяются пиксели, а не линии. Растровая графика зависит от разрешения, так как информация, описывающая изображение, прикреплена к сетке определенного размера. При изменении размеров данных файлов, качество может измениться, например, приведет к «разлохмачиванию» краев изображения, поскольку пиксели будут перераспределяться. Вывод растровой графики на устройства с более низким разрешением, чем само изображение, понизит его качество.
Применение растровой графики позволяет добиться качественного изображения, фотографического. Но все это создается за счет большого объема файла и работы вручную, т. е. при редактировании приходится поправлять каждую точку. Даже если использовать инструменты типа линии или примитивов (овалов, квадратов), то результат представляет собой изменение пикселей.
При изменении размеров изображений растровой графики качество ухудшается: при уменьшении - исчезают мелкие детали, а при увеличении картинка может превратиться в набор неряшливых квадратов (увеличенных пикселей).
При печати растровой графики или при просмотре на средствах, имеющих недостаточную разрешающую способность, значительно ухудшается восприятие образа.
- Разнообразие форматов растровой графики
Ни одна область применения компьютера не может похвастаться таким многообразием типов форматов файлов, как графика. Многие фирмы, выпуская графическую программу, создают свой собственных формат файлов, в котором редактор должен идеально сохранять все работы, созданные с его помощью. С увеличением количества существующих графических форматов совмещать их становится все труднее. Поэтому появилось несколько определенных форматов, ставших стандартами. Так, например, для изображений в Интернете в большинстве случаев используются форматы JPG и GIF, а в издательском деле царствует TIFF.
Многие растровые форматы обладают способностью нести дополнительную информацию: различные цветовые модели изображения, вектора, альфа-каналы (дополнительный канал, с помощью которого можно сохранять выделенные или прозрачные области изображения), слои различных типов, интерлиньяж (возможность чересстрочного показа изображения), анимацию, возможности сжатия и многое другое.
Достоинства растровых изображений: способность передать тончайшие нюансы изображения, возможность редактировать индивидуально каждый пиксель, изменяя его параметры. Ну, а принципиальный недостаток один - очень большие размеры полученного файла.
1.2.1. Общая информация
Формат PNG (P ortable N etwork G raphics ) представляет собой растровый формат хранения графической информации, использующий сжатие без потерь по алгоритму Deflate . Данный формат был создан как свободный формат для замены GIF.
Днём рождения PNG можно считать 4 января 1995 года, когда Т. Боутелл предложил в ряде конференций Usenet создать свободный формат, который был бы не хуже GIF. И уже через три недели после публикации идеи были разработаны четыре версии нового формата. Вначале он имел название PBF (Portable Bitmap Format ), а нынешнее имя получил 23 января 1995 года. Уже в декабре того же года спецификация PNG версии 0.92 была рассмотрена консорциумом W3C , а с выходом 1 октября 1996 года версии 1.0 PNG был рекомендован в качестве полноправного сетевого формата.
Формат PNG спроектирован для замены устаревшего и более простого формата GIF, а также, в некоторой степени, для замены значительно более сложного формата TIFF (см. официальный сайт PNG или хронологическую страницу для дополнительной информации).
Формат GIF был разработан фирмой CompuServe в 1987 году и изначально был недоступен для свободного использования. До окончания в 2004 году действия патентов на алгоритм сжатия LZW , принадлежавших Unisys и используемых в GIF, его применение в свободном программном обеспечении было затруднено. На данный момент такие затруднения сняты. PNG же с самого начала использует открытый, непатентованный алгоритм сжатия Deflate , бесплатные реализации которого доступны в Интернете. Этот же алгоритм используют многие программы компрессии данных, в том числе PKZIP и gzip (GNU zip ).
Для передачи анимированных изображений был разработан расширенный формат MNG, опубликованный в середине 1999 года и уже поддерживаемый в различных приложениях, однако пока так и не ставший общепринятым.
Некоторые - в частности, разработчики Mozilla Foundation - критиковали MNG за сложность и большой размер реализации, и отсутствие обратной совместимости с PNG. В 2004 году они разработали формат APNG, который не был принят в качестве официального стандарта разработчиками PNG и MNG, но его поддержка к 2008 году была реализована в тестовых сборках некоторых браузеров и некоторых программах просмотра изображений.
1.2.2. Область применения
Формат PNG предназначен, прежде всего, для использования в Интернете и редактирования графики.
Формат позволяет хранить три типа изображений: greyscale (для описания изображения используется один канал - белый), indexed-colour (используется палитра цветов, как в GIF) и truecolor (используется три канала - RGB). При этом он хранит графическую информацию в сжатом виде, и это сжатие производится без потерь, в отличие, например, от JPEG.
Формат PNG является хорошим форматом для редактирования изображений, даже для хранения промежуточных стадий редактирования, так как восстановление и пересохранение изображения проходят без потерь в качестве. Также, в отличие, например, от TIFF, спецификация PNG не позволяет авторам реализаций выбирать, какие возможности они собираются реализовать. Поэтому любое сохранённое изображение PNG может быть прочитано в любом другом приложении, поддерживающем PNG.
1.2.3. Структура файла
Файл PNG состоит из блоков данных, называющихся chunk "ами. C hunk в общем случае имеет переменную длину. Чтобы отличить один от другого, в каждом chunk "е есть поле типа.
Минимальный PNG-файл должен содержать как минимум сигнатуру и три chunk "a:
IHDR -- заголовок файла
IDAT -- данные, собственно картинка
IEND -- конец файла
Chunk состоит из четырёх полей:
Length -- длина поля данных chunk"а (4 байта)
Type -- поле типа (4 байта)
Data -- поле данных, может быть нулевой длины
CRC -- поле с проверочным кодом для полей Type, Data
Сигнатура PNG-файла содержит всегда 8 байт:
* (decimal) 10 26 10
* (hexadecimal)e 47 0d 0a 1a 0a
* (ASCII C notation) \211 P N G \r \n \032 \n
Сигнатура не является стандартным chunk "ом.
IHDR chunk
Этот chunk содержит основную информацию о картинке: ширина и высоту в пикселях, количество битов на сэмпл (не на пиксель) или количество бит, определяющее размер палитры и т. п.
IEND chunk
Это chunk сигнализирует о конце PNG-файла.
IDAT chunk
Этот chunk содержит данные с графической информацией. Эти данные запакованы в zlib формат. Данные, запакованные в zlib формат, запакованы в формат DEFLATE, который в общем случае предусматривает сжатие информации. Но один из вариантов DEFLATE позволяет хранить данные в контейнерах DEFLATE без сжатия.
Графическая информация, хранящаяся в IDAT chunk "ах, представляет собой набор строк (scanlines ). В формате PNG для более эффективного сжатия предусмотрена фильтрация строк. Для указания используемого фильтра перед данными строки должен следовать один байт. Содержимое означает, какой фильтр используется. В самой простой реализации фильтр можно не использовать (ведь и сжатия никакого не планируется). В этом случае этот байт должен быть равен 0.
Как вариант, одна строка графической информации может упаковываться в один IDAT chunk . Так, например, сделано в Беркут-ЕТ: файл содержит 240 IDAT chunk "ов.
Алгоритмы упаковки данных без сжатия в zlib и deflate форматы очень просты для реализации во встраиваемых системах, поскольку они сводятся к простому формированию заголовков и подсчёту контрольной суммы adler32.
Рис. 1. Структура PNG -файла
На рисунке изображена последовательность chunk "ов, образующих файл PNG. Как уже говорилось, в chunk "и IDAT "укладываются" 240 строк. Перед каждой строкой следует байт, указывающий тип фильтра (значение 0).
На рисунке используются следующие обозначения:
CH - chunk header , содержит длину поля данных и тип chunk "а IDAT
ZH - zlib header ,
DH - DEFLATE header, содержит 5 байт
CC - контрольная сумма crc32 для chunk "a
ZA - контрольная сумма adler32 для данных, упакованных DEFLATE алгоритмом.
Важно, что CC считается для каждого chunk "a, а ZA считается для всего вектора данных, упакованного алгоритмом DEFLATE.
- zlib header
Он содержит 2 байта: 0x78, 0x01
Байт 0х78 означает, что для компрессии данных используется DEFLATE с окном до 32 Кбайт.
Байт 0х01 содержит проверочный бит для первого байта и определяет уровень сжатия "без сжатия".
DEFLATE header
DEFLATE header содержит 5 байт . Первый байт содержит информацию о типе компрессии и о последнем блоке. Если используется тип компрессии "no compression", то первый и последующие блоки должны иметь первый байт 0x00, а последний блок 0x01.
Ещё четыре байта используются для указания длины блока (первые 2 байта) и проверочного поля для длины блока (вторые 2 байта). Другими словами -- LEN и NLEN, где NLEN = 0xffff - LEN.
- png check
PNG check -- это утилита, упрощающая жизнь программисту при отладке кода, создающего PNG. Она проверяет правильность формирования PNG и сообщает, если что-то не так. Например, утилита может отследить, что не сходится контрольная сумма или отсутствует какой-нибудь chunk , и т. п.
1.2.4. Достоинства
PNG обладает более высокой степенью сжатия для файлов с большим количеством цветов, чем GIF, но разница составляет около 5-25 %;
Так же самое главное преимущество формата PNG - это новые алгоритмы сжатия. В отличие от формата GIF, который эффективно сжимает только горизонтальные одноцветные области, формат PNG этим не ограничивается. Для сравнения приведено два изображения в разных форматах. Очевидно, что при почти десятикратной эффективности сжатия потерь в качестве не замечено.
Рис. 2. PNG (372 байта) Рис. 3. GIF (2, 5 Кбайт)
Еще одним важным преимуществом является фильтрация строк (scanline filtering , или delta filters ), благодаря которой PNG-упаковщик может получить гораздо более удобные данные для сжатия.
Например, есть изображение 5×5 пикселей с горизонтальным градиентом. Схематично отобразим, как оно может быть сохранено в файле (каждое число - уникальный цвет).
Рис. 4. Схематичное отображение
Как видно из примера, GIF-кодировщик отдал бы на сжатие строки, которые плохо упаковываются по горизонтали (потому что одинаковые цвета распространяются по вертикали). А вот как может преобразовать эти данные PNG-кодировщик:
Рис. 5. Схематичное отображение (PNG -кодировщик)
Перед каждой строкой появилась цифра 2. Это - фильтр, который был применен к строке. В данном случае это фильтр Up , который говорит декодеру: «Для текущего пикселя возьми значение пикселя выше и прибавь к нему текущее значение». В нашем случае это 0, потому что цвета текущего и верхнего пикселей не отличаются. А эти данные можно эффективней упаковать, если у нас достаточно большое изображение.
1.2.5. Недостатки
К недостаткам формата можно отнести :
а. Не все веб-браузеры одинаково отображают содержимое png-файла. Узким местом являются:
Частичная прозрачность (альфа-канал);
Поддержка прозрачности в палитре;
Гамма-коррекция.
Поддержка расширений PNG с анимацией.
Цветовая коррекция (ICC).
б. Существует одна особенность GIF, которая в PNG не реализована - поддержка множественного изображения, особенно анимации; PNG изначально был предназначен лишь для хранения одного изображения в одном файле.
1.3.1. Общая информация
PCX (PCExchange ) - стандарт представления графической информации, разработанный компанией ZSoft Corporation. Использовался графической программой ZSoft PC Paintbrush (одной из первых популярных графических программ) для MS-DOS, текстовыми процессорами и настольными издательскими системами, такими как Microsoft Word и Ventura Publisher .
Данный формат является не столь популярным аналогом BMP, хотя поддерживается специфическими графическими редакторами, такими как Adobe Photoshop, Corel Draw, GIMP и др. В настоящее время вытеснен форматами, которые поддерживают лучшее сжатие: GIF, JPEG и PNG.
Тип формата - растровый. Большинство файлов такого типа использует стандартную палитру цветов, но формат был расширен из расчета на хранение 24-битных изображений.
PCX - аппаратно-зависимый формат. Предназначается для хранения информации в файле в таком же виде, как и в видеоплате. Для совместимости со старыми программами необходима поддержка EGA-режима видеоконтроллером.
Формат предполагает использование простейшего алгоритма сжатия (Run Length Encoding, RLE) без потерь информации. Алгоритм такого сжатия очень быстрый и занимает небольшой объём памяти, однако не очень эффективен, непрактичен для сжатия фотографий и более детальной компьютерной графики. При сохранении изображения, подряд идущие пиксели одинакового цвета объединяются, и вместо указания цвета для каждого пикселя указывается цвет группы пикселей и их количество. Такой алгоритм хорошо сжимает изображения, в которых присутствуют области одного цвета.
1.3.2. Область применения
Область применения данного формата сокращается, поскольку вытесняется другими форматами. Имеет больше историческое значение, нежели практическое.
Однако, благодаря поддержке многими приложениями и простоте перезаписи, данный формат нередко используется разработчиками при работе с растровой графикой.
Так же данный формат используют многие графические редакторы, в частности Paint . Вместе с форматом TIFF формат PCX является одним из наиболее распространённых форматов, которые используют сканеры.
1.3.3. Структура файла
Файл изображения PCX начинается с заголовка длиной 128 байт. Затем идут закодированные графические данные.
При кодировании используется простой алгоритм, основанный на методе длинных серий. Если в файле запоминается несколько цветовых слоев, каждая строка изображения запоминается по цветовым слоям. Согласно документации Zsoft , это выполняется по приведенной ниже схеме (R - красный слой, G - зеленый слой, B - синий слой, I - слой интенсивности)
Строка изображения 0:
RRR...
GGG...
BBB...
III...
Строка изображения 1:
RRR...
GGG...
BBB...
III...
(и т. д.)
Запоминание по слоям проводится, как правило, для 16-цветных изображений EGA. При стандартной палитре EGA, которая устанавливается по умолчанию BIOS"ом, нулевой слой видео памяти содержит СИНЮЮ компоненту цвета, а не красную. Если же палитра отлична от стандартной, то говорить о том, что слои видео памяти, соотносятся с компонентами цвета вообще затруднительно.
Метод кодирования состоит в следующем:
ДЛЯ каждого байта X, прочитанного из файла. ЕСЛИ оба старших бита X равны 1, то <повторитель> = значению, хранящемуся в 6 младших битах X <данные> = находятся в следующем байте за X. ИНАЧЕ <повторитель> = 1 <данные> = X
Поскольку для насыщения данного алгоритма требуется в среднем 25% неповторяющихся данных и, по меньшей мере, наличие смещения между повторяющимися данными, то размер получаемого файла, как правило, оказывается приемлемым.
Смещение | Обозначение | Длина | Описание / комментарий |
Manufacturer | Постоянный флаг 10 = ZSoft. PCX |
||
Version | Информация о версии: |
||
Encoding | 1 = PCX кодирование длинными сериями |
||
Bits per pixel | Число бит на пиксел в слое |
||
Window | Размеры изображения (Xmin, Ymin) – (Xmax, Ymax) в пикселах включительно |
||
Hres | Горизонтальное разрешение создающего устройства |
||
Vres | Вертикальное разрешение создающего устройства |
||
Colormap | |||
Reserved | |||
NPlanes | Число цветовых слоев |
||
Bytes per Line | Число байт на строку в цветовом слое (для PCX-файлов всегда должно быть четным) |
||
Palette Info | Как интерпретировать палитру: |
||
Filler | Заполняется нулями до конца заголовка |
||
1.3.4. Достоинства
Возможность создания ограниченной палитры цветов (например, 16 или 256 цветов);
Поддерживается большим количеством приложений;
Сжатие производится без потерь.
1.3.5. Недостатки
Не поддерживает цветовые системы, отличные от RGB;
Многочисленные варианты, особенно при работе с цветами, могут делать работу с файлом невозможным;
Неудобная схема сжатия в действительности может увеличивать размеры некоторых файлов.
1.4.1. Общая информация
BMP (от англ. Bitmap Picture) - формат хранения растровых изображений, разработанный компанией Microsoft.
С форматом BMP работает огромное количество программ, так как его поддержка интегрирована в операционные системы Windows и OS/2. Файлы формата BMP могут иметь расширения. bmp, .dib и. rle. Кроме того, данные этого формата включаются в двоичные файлы ресурсов RES и в PE-файлы.
Компания Microsoft также разработала для своих нужд форматы ICO и CUR, которые имеют похожую на BMP структуру. Кроме этого, структуры из этого формата используются некоторыми WinAPI-функциями подсистемы GDI.
Глубина цвета в данном формате может быть 1, 4, 8, 16, 24, 32, 48 бит на пиксель. При этом для глубины цвета меньше 16 бит используется палитра с полноцветными компонентами глубиной 24 бита.
В формате BMP изображения могут храниться, как есть или же с применением некоторых распространённых алгоритмов сжатия. В частности, формат BMP поддерживает RLE-сжатие без потери качества, а современные операционные системы и программное обеспечение позволяют использовать JPEG и PNG (эти форматы встраиваются в BMP как в контейнер).
1.4.2. Область применения
Из-за большого объема изображения и редкого использования сжатия, файлы в данном формате весят слишком много для использования в сети.
Однако же, не смотря на свою «старость», данный формат широко используется для работы в пределах одной машины благодаря интегрированной поддержке в ОС Windows . С данным форматом работают практически все известные программы .
1.4.3. Структура файла
BMP - стандартный формат графических файлов Windows. Подавляющее большинство BMP-файлов хранится без сжатия, что облегчает работу с ними.
BMP-файлы состоят из трех основных частей:
- заголовок;
палитра;
графические данные (значения пикселей).
Заголовок содержит информацию о файле и находящемся в нем графическом изображении. Здесь хранятся параметры изображения (ширина, высота, глубина пикселей), а также количество цветов в нем.
Палитра присутствует только в BMP-файлах, содержащих палитровые изображения (с глубиной пикселей 8 бит и менее). К 8-битным изображениям прикладывается палитра, состоящая не более чем из 256 элементов.
Графические данные - это и есть само изображение. Формат этих данных зависит от глубины пикселей. 8-битные BMP-файлы могут использоваться для работы с 8-битными поверхностями, а 24-битные - для беспалитровых поверхностей.
- Структура заголовка
Данные заголовка BMP-файла хранятся в двух структурах:
BITMAPFILEHEADER и BITMAPINFOHEADER .
Структура BITMAPFILEHEADER присутствует в начале любого BMP-файла и содержит информацию о самом файле. Для нас в этой структуре представляет интерес лишь одно поле - bfType , сигнатура BMP-файла. В BMP-файлах это поле содержит буквы BM (обе буквы - прописные). По содержимому этого поля мы будем убеждаться в том, что выбранные файлы действительно имеют формат BMP.
Структура BITMAPINFOHEADER содержит информацию об изображении, хранящемся в BMP-файле. Эта структура объявляется так:
typedef struct tagBITMAPINFOHEADER {
DWORD biSize;
LONG biWidth;
LONG biHeight;
WORD biPlanes;
WORD biBitCount;
DWORD biCompression;
DWORD biSizeImage;
LONG biXPelsPerMeter;
LONG biYPelsPerMeter;
DWORD biClrUsed;
DWORD biClrImportant;
} BITMAPINFOHEADER, FAR *LPBITMAPINFOHEADER, *PBITMAPINFOHEADER;
Первое поле, biSize , определяет размер структуры BITMAPINFOHEADER в байтах. Если ваша программа создает BMP-файл, это поле заполняется тривиально - достаточно определить размер структуры функцией sizeof . Однако при чтении BMP-файла по содержимому этого поля приходится рассчитывать позицию файла, на которой структура заголовка кончается. Эта мера обеспечивает обратную совместимость, благодаря ей Microsoft в будущем сможет увеличить размер структуры BITMAPINFOHEADER , не нарушая работы существующих приложений.
Поля biWidth , biHeight и biBitCount определяют размеры изображения. Содержимое поля biCompression позволяет узнать, хранится ли изображение в сжатом виде. Поскольку мы не собираемся работать со сжатыми BMP-файлами, необходимо проверить, имеет ли это поле значение BI_RGB (а не BI_RLE8 , свидетельствующее о сжатии файла).
В поле biSizeImage хранится размер графических данных (в пикселях). Однако учтите, что это поле часто оказывается незаполненным (содержит нулевое значение). В таких случаях нам придется самостоятельно вычислять размер графических данных.
Наконец, поле biClrUsed определят количество цветов в палитре (для палитровых изображений). Как и поле biSizeImage , оно часто может быть равно нулю. Это означает, что палитра содержит максимальное количество элементов (256 для 8-битных изображений).
- Палитра
Палитра в BMP-файлах хранится в виде списка структур RGBQUAD , где каждый элемент представляет отдельный цвет. Структура RGBQUAD объявляется так:
typedef struct tagRGBQUAD {
BYTE rgbBlue;
BYTE rgbGreen;
BYTE rgbRed;
BYTE rgbReserved;
} RGBQUAD;
В первых трех полях хранятся цветовые RGB-составляющие. На поле rgbReserved мы не будем обращать внимания (предполагается, что оно равно нулю). Как я упоминал выше, количество структур RGBQUAD в BMP-файле определяется полем biClrUsed . Тем не менее обычно 8-битные BMP-файлы содержат 256 структур RGBQUAD . В 24-битных RGB-файлах структуры RGBQUAD отсутствуют.
- Графические данные
Графические данные в основном представляют собой список пикселей, из которых состоит изображение. Однако каждая горизонтальная строка пикселей должна занимать блок памяти, выровненный по границе параграфа. Следовательно, если количество байт, необходимых для хранения строки пикселей, не кратно четырем, в каждую строку включается от одного до трех дополняющих байт.
При этом для работы с графическими данными BMP-файлов используется концепция шага. Отличие состоит в том, что для графических данных BMP-файлов значение шага программисту придется считать самостоятельно. Впрочем, это не так уж сложно, потому что шаг всегда попадает на ближайшую границу параграфа за концом блока памяти, необходимого для хранения строки пикселей.
Изображения хранятся в BMP-файлах в перевернутом виде, так что первая строка пикселей файла на самом деле является нижней строкой настоящего изображения.
1.4.4. Достоинства
Возможность редактирования почти в любой программе, как стандартной, так и специальной;
Высокое качество изображения.
1.4.5. Недостатки
Абсолютно не подходит для сети Интернет;
Крайне неудачный выбор для последующей распечатки;
Аппаратно-зависимый формат.
JPEG | |||||
Потери при сжатии | |||||
Максимальное число бит на пиксел | |||||
Прозрачность | альфа-канал | ||||
Гамма-коррекция | |||||
Множественное изображение | |||||
Алгоритм сжатия | Deflate(LZ 77) | JPEG | |||
Размер изображения | |||||
Проблемы отображения браузерами | |||||
Цветовая схема | Все доступные | Не поддерживает CMYK | Все доступные | Не поддерживает Indexed color , со CMYK вероятны проблемы при чтении |
Статьи по теме
Еще статьи из этой рубрики
|
