Зі compression зображень DCT: математика за лаштуваннями JPEG

Від пікселів до частот

Фотографія, що зберігається безпосередньо, є сіткою незалежних значень яскравості без очевидного надлишку для використання по пікселю. Але розділивши її на невеликі блоки 8x8, стає в цьому корисно: більшість природних блоків зображення домінують повільні, плавні зміни яскравості з лише рідкісними різкими краями. Дискретна косинусна трансформація перефразовує блок не як 64 значення пікселів, а як 64 просторові частотні коефіцієнти – наскільки певний шаблон блоку схожий на повільно змінювану косинусну хвилю порівняно з швидко коливається, в обох горизонтальних та вертикальних напрямках.

Формула DCT-II

JPEG використовує двовимірну DCT-II, яка застосовується як 1D перетворення по рядках, а потім по стовпцях. Версія 1D для N зразків така:

X_k = 2 * sum_{n=0}^{N-1} x_n * cos( pi/N * (n + 0.5) * k ), k = 0..N-1 X_0 = постійний член (DC) — пропорційний середньому значенню всіх x_n X_1..X_N-1 = змінні члени (AC) — що збільшуються просторовою частотою Застосовуючи це в двох вимірах до 8x8 блоку, отримується 8x8 сітка коефіцієнтів, де верхній лівий елемент відповідає середньому рівню яскравості блоку, а коефіцієнти праворуч і вниз далі представляють прогресивніші горизонтальні та вертикальні частоти. Оскільки DCT є ортогональною та використовує лише справжні косинуси (а не комплексні експоненти, як пов'язане з нею перетворення Фур’є), вона уникає надлишкового симетричного спектру, який би утворилося б від перетворення Фур’є для даних зображень із дійсною величиною, що є однією з причин вибору DCT замість FFT для цієї задачі.

X_k = 2 * sum_{n=0}^{N-1} x_n * cos( pi/N * (n + 0.5) * k ),   k = 0..N-1

X_0        = the DC term  — proportional to the average of all x_n
X_1..X_N-1 = AC terms     — increasing spatial frequency

Концентрація енергії: як це працює

Для типового фотографічного блоку DCT концентрує переважну більшість енергії сигналу в низькочастотний кутовий регіон біля DC-терміна, залишаючи більшу частину високочастотних коефіцієнтів малими або ефективно нульовими. Ця властивість, яка називається концентрацією енергії, є повною причиною корисності перетворення для стиснення: замість того, щоб зберігати 64 приблизно рівнозначні числа, можна зберігати невелику кількість великих коефіцієнтів точно і решту – грубо – або видалити їх – з незначною візуальною втратою.

Квантування: тут відбувається стиснення

Власне DCT є беззбитковим (до округлення) — воно лише змінює представлення. Втрачаючий етап – квантування: кожен коефіцієнт ділиться на значення з таблиці квантування 8x8 і округляється до найближчого цілого числа. Значення в таблиці збільшуються у напрямку кута високих частот, оскільки людське зорове сприйняття значно менш чутливе до тонких деталей високих частот, ніж до широких тіней низьких частот; тому ці коефіцієнти можна квантувати грубіше – часто до нуля – з незначною втратою якості. "Якість" регулятор у кодеку JPEG масштабує цю таблицю: вища якість означає більш дрібне (менше-дільник) квантування та більше коефіцієнтів, що зберігаються не нулем.

Діагональне сканування та ентропійне кодування

Після квантування більшість із 64 коефіцієнтів типового блоку є нульовими і скупчені у високочастотному кутку. JPEG читає коефіцієнти в діагональному порядку, який поступово збільшує загальну частоту, що перетворює цей кут нулів на один довгий пробіг — ідеальний вхід для кодування довжини пробігів, яке потім ще більше стискається за допомогою кодування Хаффмана. Комбінація DCT, агресивного високочастотного квантування та кодування довжини пробігів плюс кодування Хаффмана зазвичай забезпечує стиснення 10:1 з мінімальною видимою втратою якості, а значно вищі співвідношення при помітному утворенні блочних артефактів.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте DCT Image Compression і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.