Зображення формату JPEG зустрічаються всюди в нашому цифровому житті, але за цим покривом обізнаності ховаються алгоритми, що усувають деталі, які не сприймаються людським оком. У результаті виходить висока візуальна якість при найменшому розмірі файлу - але як саме все це працює? Погляньмо, чого саме не бачать наші очі!
Легко прийняти, як зрозуміло, можливість відправити фотку другу, і не хвилюватися з приводу того, який пристрій, браузер або операційну систему він використовує - проте так було не завжди. На початку 1980-х комп'ютери вміли зберігати і показувати цифрові зображення, проте з приводу найкращого способу цього існувало безліч конкуруючих ідей. Не можна було просто надіслати зображення з одного комп'ютера на інший та сподіватися, що все запрацює.
Для вирішення цієї проблеми у 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 стиснення:
- .
- .
- , и
Щоб ви могли уявити масштаби стиснення, зверніть увагу, що зображення, наведене вище, становить 79 819 чисел, тобто близько 79 Кб. Якби ми зберігали його без стиснення, для кожного пікселя знадобилося б по три числа – для червоної, зеленої та синьої складової. Це становило б 917 700 чисел, або прибл. 917 Кб. В результаті JPEG стиснення підсумковий файл зменшився більше ніж у 10 разів!
Насправді це зображення можна стиснути набагато сильніше. Знизу наведено два зображення поряд – фотка праворуч була стиснута до 16 Кб, тобто в 57 разів менше, ніж стисла версія!
Якщо ви побачите, буде видно, що ці зображення не ідентичні. Обидва вони – картинки з JPEG стиском, проте права набагато менше за обсягом. Також вона виглядає трохи гірше (дивіться на квадрати кольорів тла). Тому JPEG ще називають стисненням із втратами; в процесі стиснення зображення змінюється та втрачає деякі деталі.
1. Колірна субдискретизація
Ось зображення із застосуванням лише першого рівня стиснення.
(Інтерактивна версія – у статті). Видалення одного числа руйнує всі кольори. Однак, якщо видалити рівно шість чисел, це практично не впливає на зображення.
Тепер цифри трохи простіше розшифрувати. Це майже простий список кольорів, у якого кожен байт змінює рівно один піксель, але при цьому він вже вдвічі менший за несжате зображення (яке займало б близько 300 Кб в такому зменшеному розмірі). Здогадаєтеся, чому?
Можна бачити, що ці числа не позначають стандартні червоні, зелені та сині компоненти, оскільки якщо замінити всі числа нулями, ми отримаємо зелене зображення (а не біле).
Це тому, що ці байти позначають Y (яскравість),
Cb (відносна голубина),
і Cr (відносна почервоніння) картинки.
Чому не використовувати RGB? Адже саме так працює більшість сучасних екранів. Ваш монітор може демонструвати будь-який колір, включаючи червоний, зелений та синій кольори з різною інтенсивністю для кожного пікселя. Білий виходить включенням всіх трьох на повну яскравість, а чорний їх відключенням.
Це також дуже схоже на роботу людського ока. Колірні рецептори наших очей називаються ««, і поділяються на три типи, кожен з яких більш чутливий або до червоного, або до зеленого, або до синього кольорів. у зелено-жовтій (M від англ. Medium - середньохвильовий), і L-типу - у жовто-червоній (L від англ. Long - довгохвильовий) частинах спектру. Наявність цих трьох видів колб (і паличок, чутливих у смарагдово-зеленій частині спектру) дає людині кольоровий зір. / прим. перев.]. , Інший тип фоторецепторів в наших очах, здатний вловлювати зміни в яскравості, проте набагато чутливіший до кольору. У наших очах є близько 120 млн паличок і лише 6 млн колб.
Тому наші очі набагато краще помічають зміни у яскравості, ніж зміни у кольорі. Якщо відокремити колір від яскравості, можна забрати трохи кольору, і ніхто нічого не помітить. Колірна субдискретизація – це процес представлення колірних компонентів зображення у меншій роздільній здатності порівняно з компонентами яскравості. У прикладі вище у кожного пікселя рівно один компонент Y, а у кожної окремої групи з чотирьох пікселів є одно компонента Cb і одна Cr. Тому зображення містить у чотири рази менше колірної інформації, ніж у оригіналу.
Колірний простір YCbCr використовується не лише у JPEG. Його спочатку вигадали в 1938 році для телепередач. Не всі мають кольоровий телевізор, тому розділення кольору і яскравості дозволило всім отримувати один і той же сигнал, а телевізори без кольору просто використовували тільки компонент яскравості.
Тому видалення одного числа з редактора повністю руйнує всі кольори. Компоненти зберігаються у вигляді YYYY 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 рази менше!
На цьому рівні знаходиться секрет шахових візерунків. На відміну від інших ефектів, що ми бачили, поява цих візерунків не є глюком. Вони – будівельні блоки всього зображення. У кожному рядку редактора міститься рівно 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. Кожен колірний компонент може мати свою таблицю.
Зміни таблиць радикально вплинуть будь-яке зображення. Гарний приклад - поміняти на 15-му рядку 1 на 12.
Це тому, що у таблицях вказується, як треба читати окремі біти. Поки що ми працювали лише з двійковими числами у десятковому вигляді. Але це приховує від нас той факт, що якщо ви хочете зберігати число 1 в байті, то воно буде виглядати як 00000001, оскільки в кожному байті має бути рівно вісім біт, навіть якщо потрібен з них лише один.
Потенційно це велика витрата місця, якщо у вас є багато дрібних чисел. Код Хаффмана - це техніка, що дозволяє нам послабити цю вимогу, за якою кожне число повинне займати вісім біт. Це означає, що якщо ви бачите два байти:
234 115
Те, залежно від таблиці Хаффмана, може бути три числа. Щоб їх витягти, вам треба спочатку розбити їх на окремі біти:
11101010 01110011
Потім звертаємось до таблиці, щоб зрозуміти, як їх групувати. Наприклад, це можуть бути перші шість бітів, (111010), або 58 у десятковій системі, за якими йдуть п'ять бітів (10011), або 19, і нарешті останні чотири біти (0011), або 3.
Тому дуже складно розібратися в байтах на цьому етапі стискування. Байти не уявляють те, що здається. Не заглиблюватимусь у деталі роботи з таблицею в даній статті, але з цього питання у мережі .
Один із цікавих трюків, які можна зробити, знаючи це – відокремити заголовок від JPEG і зберігати його окремо. По суті вийде, що файл зможете прочитати тільки ви. Facebook робить це, щоб ще більше зменшувати файли.
Що ще можна зробити – зовсім небагато змінити таблицю Хаффмана. Для інших це буде виглядати як зіпсована картинка. І тільки ви знатимете чарівний варіант її виправлення.
Підіб'ємо підсумки: так що ж потрібно для декодування JPEG? Необхідно:
- Витягти таблицю (таблиці) Хаффмана із заголовка і декодувати біти.
- Витягти коефіцієнти дискретного косинусного перетворення кожного компонента кольору і яскравості кожного блоку 8х8, провівши зворотні перетворення кодування довжин серій і дельти.
- Скомбінувати косинус на основі коефіцієнтів, щоб отримати значення пікселів для кожного блоку 8х8.
- Масштабувати компоненти кольорів, якщо проводилася субдискретизація (ця інформація є у заголовку).
- Перетворити отримані значення YCbCr для кожного пікселя RGB.
- Вивести зображення на екран!
Серйозна робота для простого перегляду фотки з котиком! Однак, що мені в цьому подобається – видно, наскільки технологія JPEG є людиноцентричною. Вона заснована на особливостях нашого сприйняття, що дозволяють досягти кращого стиснення, ніж звичайні технології. І тепер, розуміючи, як працює JPEG, можна уявити, як ці технології можна перенести до інших областей. Наприклад, дельта-кодування у відео може дати серйозне зменшення розміру файлу, оскільки часто є цілі області, не змінюються від кадру до кадру (наприклад, фон).
, відкритий, і містить інструкції щодо заміни картинок на свої власні.
Джерело: habr.com