Как е структуриран форматът JPEG

JPEG изображения се срещат навсякъде в нашия цифров живот, но зад тази завеса на осведомеността се крият алгоритми, които премахват детайли, невидими за човешкото око. В резултат на това получаваме най-високо визуално качество с минимален размер на файла – но как точно работи всичко това? Нека да разгледаме какво точно не виждат нашите очи!

Лесно е да приемем за даденост възможността да изпратим снимка на приятел и да не се притесняваме за това какво устройство, браузър или операционна система използва – обаче, така не винаги е било. В началото на 80-те години компютрите можеха да съхраняват и показват цифрови изображения, но съществуваха множество конкуриращи се идеи относно най-добрия начин за това. Не можеше просто да изпратиш изображение от един компютър на друг и да се надяваш, че всичко ще работи.

За решаването на този проблем през 1986 година беше събран комитет от експерти от цял свят, наречен „Обединена група експерти по фотография“ (Joint Photographic Experts Group, JPEG), основан в рамките на съвместната работа на Международната организация по стандартизация (ISO) и Международната електротехническа комисия (IEC) – две международни организации за стандартизиране, чиято централа се намира в Женева (Швейцария).

Група хора, наречена JPEG, създаде стандарта за компресия на цифрови изображения JPEG през 1992 година. Всеки, който е използвал интернет, вероятно е срещал изображения в JPEG кодировка. Това е най-разпространеният начин за кодиране, изпращане и съхраняване на изображения. От уеб страници до имейли и социални мрежи, JPEG се използва милиарди пъти на ден – почти всеки път, когато гледаме изображение онлайн или го изпращаме. Без JPEG, уебът щеше да бъде по-малко живописен, по-бавен и вероятно в него щеше да има по-малко котешки снимки!

Тази статия е за това как да декодирате JPEG изображение. С други думи, за това какво е необходимо, за да се преобразуват компресираните данни, съхранявани на компютъра, в изображение, появяващо се на екрана. Това е важно да знаете не само защото е значимо за разбирането на технологията, която използваме ежедневно, но и защото като разглеждаме нивата на компресия, по-добре разбираме възприятието и зрението, както и какви детайли нашите очи възприемат най-силно.

Освен това, да си играете с изображения по този начин е много интересно.

Вглеждайки се вътре в JPEG

На компютъра всичко се съхранява под формата на последователност от двоични числа. Обикновено, тези битове, нули и единици, се групират по осем, образувайки байтове. Когато отворите JPEG изображение на компютъра, нещо ( браузър, операционна система, нещо друго) трябва да декодира байтовете, възстановявайки оригиналното изображение под формата на списък с цветове, който може да бъде показан.

Ако свалите тази симпатична снимка на котка и я отворите в текстов редактор, ще видите купища безсмислени символи.

Тук използвам Notepad++ за да изследвам съдържанието на файла, тъй като обикновените текстови редактори, като Notepad от Windows, ще развалят бинарния файл след запазване, и той ще спре да удовлетворява формата JPEG.

Отваряйки изображение в текстов редактор, вие обърквате компютъра точно както обърквате мозъка си, когато търкате очите си и започвате да виждате цветни петна!

Тези петна, които виждате, са известни като фосфени, и не са резултат от въздействието на светлинен стимул или халюцинации, предизвикани от ума. Те възникват, защото вашият мозък счита, че всякакви електрически сигнали в зрителните нерви предават информация за светлината. Мозъкът трябва да прави такива предположения, тъй като не може да разбере дали сигналът е звук, визия или нещо друго. Всички нерви в тялото предават абсолютно идентични електрически импулси. Когато натискате на очите, изпращате сигнали, които не са зрителни, но активират рецепторите на окото, които вашият мозък интерпретира - в този случай погрешно - като нещо зрително. Вие буквално можете да видите натиска!

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

За да разберем как да декодираме JPEG, трябва да видим самите оригинални сигнали – бинарни данни. Това може да се направи с помощта на шестнадесетичен редактор или директно на веб-страницата на оригиналната статия! Там има изображение, до което в текстовото поле са представени всичките му байтове (с изключение на заглавката), представени в десетичен вид. Можете да ги променяте и скриптът ще прескриптира и ще изведе ново изображение в движение.

Много неща можете да научите, просто играейки с този редактор. Например, можете ли да кажете в какъв ред са съхранени пикселите?

В този пример странното е, че промяната на някои числа изобщо не влияе на изображението, а, например, ако замените числото 17 с 0 в първия ред, снимката ще бъде напълно развалена!

Други промени, например, замяна на 7 в ред 1988 с числото 254, променят цвета, но само на следващите пиксели.

Възможно е най-странното нещо е, че някои числа променят не само цвета, но и формата на изображението. Променете 70 в ред 12 на 2 и погледнете горния ред на изображението, за да видите какво имам предвид.

И независимо от това какво JPEG изображение използвате, винаги ще намирате тези загадъчни шахматни последователности при редактиране на байтове.

Играейки с редактора, е трудно да се разбере как изображението се възпроизвежда от тези байтове, тъй като JPEG компресията се състои от три различни технологии, които се прилагат последователно. Ще изучим всяка от тях поотделно, за да разкрием наблюдаваното от нас загадъчно поведение.

Три нива на JPEG компресия:

1. Цветова субдискретизация.
2. Дискретно косинусно преобразуване и дискретизация.
3. Кодиране на дълги серии, делта и Хаффман

За да можете да си представите мащабите на компресията, обърнете внимание, че изображението, представено по-горе, съдържа 79 819 числа, т.е. около 79 Кб. Ако го съхранявахме без компресия, за всеки пиксел биха били нужни три числа – за червената, зелената и синята съставка. Това би било 917 700 числа, или около 917 Кб. В резултат на JPEG компресията, финалният файл е намален повече от 10 пъти!

Всъщност, това изображение може да се компресира много по-силно. По-долу са представени две изображения един до друго – снимката вдясно е компресирана до 16 Кб, т.е. 57 пъти по-малко от несжатата версия!

Ако се вгледате, ще видите, че тези изображения не са идентични. И двете са картинки с JPEG компресия, но дясното е значително по-малко по обем. Освен това изглежда леко по-лошо (погледнете квадратчетата с цветове на фона). Поради това JPEG често се нарича компресия с загуби; по време на компресията изображението се променя и губи някои детайли.

1. Цветова субдискретизация

Ето изображение, прилагано с само първото ниво на компресия.

(Интерактивна версия – в оригинала на статията). Премахването на едно число разрушава всички цветове. Въпреки това, ако премахнете точно шест числа, това почти не влияе на изображението.

Сега числата са малко по-лесни за разглобяване. Това е почти обикновен списък с цветове, при който всеки байт променя точно един пиксел, но освен това е вече два пъти по-малко от несжатото изображение (което би било около 300 Кб в този намален размер). Можете ли да се досетите защо?

Може да се види, че тези числа не обозначават стандартните червена, зелена и синя съставки, тъй като ако заменим всички числа с нули, ще получим зелено изображение (а не бяло).

Това е така, защото тези байтове обозначават Y (яркост),

Cb (относителна синьо),

и Cr (относителна червенина) на картината.

Защо да не използваме RGB? Нали именно така функционират повечето съвременни екрани. Вашият монитор може да показва всякакъв цвят, включително червен, зелен и син с различна интензивност за всеки пиксел. Белият цвят се получава при включване на всички три на пълна яркост, а черният – когато са изключени.

Това също е много подобно на начина, по който работи човешкото око. Цветните рецептори на нашите очи се наричат „колбичкиТe тези рецептори се делят на три типа, като всеки от тях е по-чувствителен към червеното, зеленото или синьото. [S тип конуси са чувствителни в виолетово-синя (S от английски. Short — късовълнов спектър), M тип — в зелено-жълта (M от английски. Medium — средновълнов), а L тип — в жълто-червена (L от английски. Long — дълговълнов) част на спектъра. Наличието на тези три вида конуси (и пръчки, чувствителни в изумрудено-зелена част на спектъра) позволява на човека да вижда цветове. / бел. прев.] Пръчки, друг тип фоторецептори в нашите очи, е способен да улавя промени в яркостта, но е много по-чувствителен към цвета. В нашите очи има около 120 милиона пръчки и само 6 милиона конуси.

Затова очите ни много по-добре забелязват промени в яркостта, отколкото промени в цвета. Ако отделим цвета от яркостта, можем да намалим малко цвета и никой няма да забележи. Цветовата субдискретизация е процес, при който цветните компоненти на изображението се представят с по-ниска резолюция в сравнение с компонентите на яркостта. В примера по-горе всеки пиксел има точно един компонент Y, а всяка отделна група от четири пиксела има точно един компонент Cb и един Cr. Затова изображението съдържа четири пъти по-малко цветова информация в сравнение с оригинала.

Цветовото пространство YCbCr се използва не само в JPEG. То е създадено през 1938 година за телепредавания. Не всички разполагат с цветен телевизор, затова разделянето на цветове и яркост позволи на всички да получават един и същ сигнал, а телевизорите, които не предават цветове, просто използваха само компонента на яркостта.

Така че премахването на едно число от редактора напълно разрушава всички цветове. Компонентите се съхраняват в следния формат Y Y Y Y Cb Cr (всъщност не е задължително в този ред – редът на съхранение се определя в заглавката на файла). Премахването на първото число ще доведе до това, че първото значение Cb ще бъде възприето като Y, Cr като Cb и ще се получи ефект на домино, който променя всичките цветове на изображението.

JPEG спецификация не налагает обязательства использовать YCbCr. Однако большинство файлов применяют этот формат, так как он обеспечивает лучшее качество изображения после субдискретизации по сравнению с RGB. Но не стоит верить мне на слово. Посмотрите сами в таблице ниже, как будет выглядеть субдискретизация каждого отдельного компонента как в RGB, так и в YCbCr.

(Интерактивна версия – в оригинала статии).

Удаление синего цвета менее заметно, чем красного или зелёного. Это происходит потому, что из шести миллионов колбочек в ваших глазах около 64% чувствительны к красному, 32% к зелёному и только 2% к синему.

Субдискретизация компонента Y (слева внизу) видна лучше всего. Даже небольшое изменение заметно.

Преобразование изображения из RGB в YCbCr не уменьшает размер файла, но упрощает поиск менее заметных деталей, которые можно удалить. Сжатие с потерями происходит на втором этапе, основанном на идее представления данных в более сжимаемом виде.

2. Дискретное косинусное преобразование и дискретизация

Этот уровень сжатия в основном и определяет суть JPEG. После преобразования цветов в YCbCr компоненты сжимаются по отдельности, поэтому далее мы можем сосредоточиться только на компоненте Y. Вот как выглядят байты компонента Y после применения этого уровня.

(Интерактивна версия – в оригинала статии). В интерактивной версии клик на пикселе прокручивает редактор до строки, которая его обозначает. Попробуйте удалить числа с конца или добавить несколько нулей к определённому числу.

На первый взгляд, это выглядит как очень плохое сжатие. В изображении 100 000 пикселей, и для обозначения их яркости (Y-компоненты) требуется 102 400 чисел — это хуже, чем если вообще ничего не сжимать!

Тем не менее, обратите внимание на то, что большинство этих чисел равны нулю. Больше того, все эти нули в конце строк можно удалить, не меняя изображение. Остаётся порядка 26 000 чисел, что уже в 4 раза меньше!

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

Тези шаблони се формират на базата на график на косинус. Ето как изглеждат някои от тях:

8 от 64 коефициента

По-долу е изображение, което демонстрира всички 64 шаблона.

(Интерактивна версия – в оригинала статии).

Тези шаблони имат специално значение, тъй като те формират основата на изображения с размер 8х8. Ако не сте запознати с линейната алгебра, това означава, че всяко изображение с размер 8х8 може да бъде получено от тези 64 шаблона. DCT е процес на разделяне на изображенията на блокове 8х8 и преобразуване на всеки блок в комбинация от тези 64 коефициента.

Фактът, че всяко изображение може да бъде съставено от 64 определени шаблона, изглежда като магия. Въпреки това, това е същото като да кажем, че всяка точка на Земята може да бъде описана с две числа – ширина и дължина [с указание за хемисфери / бележка на преводача]. Ние често считаме повърхността на Земята за двумерна, затова ни трябват само две числа. Изображение с размер 8х8 има 64 измерения, така че ни трябват 64 числа.

Все още не е ясно как това ни помага в смисъл на компресия. Ако ни трябват 64 числа за представяне на изображение 8х8, защо този метод би бил по-добър от просто съхраняване на 64 компоненти на яркост? Правим го по същата причина, поради която преобразувахме трите RGB числа в три числа YCbCr: това ни позволява да премахнем невидимите детайли.

Трудно е да видим кои точно детайли се премахват на тази стъпка, тъй като JPEG прилага DCT на блоковете 8х8. Въпреки това, никой не ни забранява да го прилагаме на цялото изображение. Ето как изглежда DCT по компонента Y при прилагане към цялото изображение:

От края може да се премахнат повече от 60 000 числа практически без забележими промени на снимката.

Въпреки това, имайте предвид, че ако нулираме първите пет числа, разликата ще бъде очевидна.

Числата в началото обозначават изменения с ниска честота в изображението, и нашите очи улавят тях най-добре. Числата, близо до края, обозначават изменения с висока честота, които е по-трудно да се забележат. За да 'видим това, което окото не вижда', можем да изолираме тези детайли с висока честота, като нулираме първите 5000 числа.

Виждаме всички области на изображението, в които се случват най-големи промени от пиксел на пиксел. Изтъкват се очите на котката, нейните мустаци, пухеното одеяло и сенките в долния ляв ъгъл. Можем да отидем дори по-далеч, като нулираме първите 10 000 числа:

20 000:

40 000:

60 000:

Тези високочестотни детайли в JPEG и ги заличава на етапа на компресия. Преобразуването на цветовете в коефициенти DCT не носи загуби. Загубите възникват на етапа на дискретизация, където се заличават величини с висока честота или близки до нула. Когато намалите качеството на запазване на JPEG, програмата увеличава прага на броя заличавани стойности, което води до намаляване на размера на файла, но прави изображението по-пикселизирано. Затова изображението в първия раздел, което бе 57 пъти по-малко, изглеждаше така. Всеки блок 8х8 се представяше с много по-малко коефициенти DCT в сравнение с по-качествената версия.

Можете да постигнете такъв страхотен ефект, както постепенното поточно предаване на изображения. Можете да изведете размазано изображение, което става все по-подробно, докато се изтеглят все повече коефициенти.

Ето, просто за интерес, какво ще получите, ако използвате само 24 000 числа:

Или само 5000:

Много размазано, но сякаш разпознаваемо!

3. Кодиране на дълги серии, делта и Хаффман

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

Как може да се компресира нещо, без да се изхвърля информация? Представете си как бихме описали прост черен правоъгълник 700 х 437.

JPEG използва за това 5000 числа, но може да се постигне много по-добър резултат. Можете ли да си представите схема на кодиране, която описва подобно изображение с възможно най-малко байтове?

Минималната схема, която успях да измисля, използва четири: три за обозначаване на цвета и четвъртият – колко пиксела имат такъв цвят. Идеята за представяне на повтарящи се стойности по такъв компресиран начин се нарича кодиране на дълги серии. Тя е без загуби, тъй като можем да възстановим кодираните данни в първоначалния им вид.

Размерът на JPEG файл с черен правоъгълник е много по-голям от 4 байта – помнете, че на ниво DCT компресията се прилага на блокове с размер 8х8 пиксела. Затова поне един DCT коефициент е необходим на всеки 64 пиксела. Един е необходим, тъй като вместо да съхраняваме един DCT коефициент, последван от 63 нули, кодиране на дълги серии ни позволява да съхраняваме едно число и да обозначим, че „всички останали са нули”.

Делта-кодирането е техника, при която всеки байт съдържа разлика от определена стойност, а не абсолютна величина. Затова редактирането на определени байтове променя цвета на всички останали пиксели. Например, вместо да съхраняваме

12 13 14 14 14 13 13 14

Можехме да започнем с 12, а след това просто да обозначаваме колко трябва да добавим или извадим, за да получим следващото число. И тази последователност в делта-кодирането придобива вид:

12 1 1 0 0 -1 0 1

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

Делта-кодирането е една от малкото техники, приложими извън блоковете 8х8. От 64 DCT коефициента един е просто постоянна вълнова функция (едноцветен). Той представлява средната яркост на всеки блок за компонентите на яркостта или средната синевина за компонентите Cb и т.н. Първото значение на всеки DCT блок се нарича DC-стойност и всяка DC стойност преминава през делта-кодиране спрямо предишните. Следователно промяната на яркостта на първия блок ще повлияе на всички блокове.

Остава последната загадка: как промяната на едно единствено число може напълно да развали цялата картинка? Все още няма свойства на нивата на компресия, които да обясняват това. Отговорът е в заглавката на JPEG. Първите 500 байта съдържат метаданни за изображението – ширина, височина и т.н., и докато не работим с тях.

Без заглавка практически е невъзможно (или много трудно) да декодираме JPEG. То ще изглежда така, сякаш се опитвам да ви опиша картина, и започвам да съчинявам думи, за да предам впечатлението си. Описанието вероятно ще бъде много сбито, тъй като мога да съчинявам думи с точното значение, което искам да предам, но за всички останали те няма да имат смисъл.

Звучи глупаво, но точно така се случва. Всяко изображение JPEG се компресира с кодове, специфични именно за него. Речникът на кодовете се съхранява в заглавката. Техника, наречена „Хъфман кодиране“, а речникът – Хъфманова таблица. В заглавката таблицата е обозначена с два байта – 255 и след това 196. Всеки цветови компонент може да има своя собствена таблица.

Промените в таблиците радикално ще повлияят на всяко изображение. Добър пример е да смените 1 с 12 на 15-тия ред.

Това се случва, защото в таблиците се указва, как да се четат отделните битове. До сега работихме само с двоични числа в десетичен вид. Но това ни скрива факта, че ако искате да съхраните числото 1 в байта, то ще изглежда като 00000001, тъй като всеки байт трябва да съдържа точно осем бита, дори ако ви е нужен само един от тях.

Потенциално, това е голямо разхищение на пространство, ако имате много малки числа. Хъфман кодиране е техника, която ни позволява да облекчим това изискване, при което всяко число трябва да заема осем бита. Тоест, ако видите два байта:

234 115

Тогава, в зависимост от Хъфмановата таблица, това могат да бъдат три числа. За да ги извадите, първо трябва да ги разделите на отделни битове:

11101010 01110011

След това се обръщаме към таблицата, за да разберем как да ги групираме. Например, това може да са първите шест бита (111010) или 58 в десетична система, последвани от пет бита (10011) или 19, и накрая последните четири бита (0011) или 3.

Така че е много сложно да се разберат байтовете на този етап на компресия. Байтовете не представят това, което изглежда. Няма да навлизам в детайлите на работата с таблицата в тази статия, но материали по този въпрос в интернет е достатъчно.

Един от интересните трикове, които можете да направите, знаейки това, е да отделите заглавката от JPEG и да я съхранявате отделно. По същество, файлът ще може да бъде прочетен само от вас. Facebook прави това, за да намали файловете още повече.

Какво още може да се направи – да измените малко таблицата Хъфман. За другите това ще изглежда като повредена картинка. И само вие ще знаете магическия вариант за нейното поправяне.

Накратко: какво е необходимо за декодиране на JPEG? Нужно е:

1. Да се извлече Хъфмановата таблица (таблици) от заглавката и да се декодират битовете.
2. Извлечете коефициентите на дискретното косинусно преобразуване за всеки цвят и яркост за всеки блок 8х8, проведете обратни преобразувания на кодове с дълги серии и разлики.
3. Комбинирайте косинусите на база коефициентите, за да получите стойностите на пикселите за всеки блок 8х8.
4. Масштабирайте компонентите на цветовете, ако е проведена субдискретизация (тази информация е в заглавието).
5. Преобразувайте получените стойности YCbCr за всеки пиксел в RGB.
6. Показвайте изображението на екрана!

Сериозна работа за простото разглеждане на снимка с коте! Въпреки това, това което ми харесва е, че показва колко технологиите JPEG са насочени към човека. Те са базирани на особеностите на нашето възприятие, което позволява постигането на много по-добро компресиране в сравнение с обикновените технологии. И сега, след като разбирам как работи JPEG, мога да си представя как тези технологии могат да бъдат пренесени в други области. Например, кодиране с разлики в видео може да доведе до значително намаляване на размера на файла, тъй като често има цели области, които не се променят от кадър на кадър (например фон).

Кодът, използван в статията, е отворен и съдържа инструкции за замяна на картинките с ваши собствени.

Източник: habr.com