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

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

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

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

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

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

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

Надникнете в JPEG

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

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

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

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

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

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

Чтобы понять, как да декодираме 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? Нали именно така работят повечето съвременни екрани. Вашият монитор може да показва всякакъв цвят, включително червен, зелен и син със различна интензивност за всеки пиксел. Бялото се получава чрез включване на всички три на пълна яркост, а черното – чрез изключването им.

Това също много прилича на работата на човешкото око. Цветовите рецептори на нашите очи се наричат „колбички«, и се делят на три типа, всеки от които е по-чувствителен в червения, зеления или синия спектър [колбочки 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 коефициенти в сравнение с версия с по-високо качество.

Може да се направи страхотен ефект, като постепенно предаване на изображения. Може да се покаже размазана картинка, която става все по-детайлизирана, докато се сваля все повече 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