Алгоритм стиску зображень JPEG

Алгоритм стиску, використовуваний у форматі зберігання зображень JPEG¹⁾[49],побудований на використанні дискретного косинусного перетворення. Схема стиску в алгоритмі являє собою конвеєр, де дане перетворення - лише одна зі стадій (хоча, можливо, і найважливіша). Опишемо алгоритм, припускаючи, що на вхід дані 24-бітне зображення, значення атрибутів пикселей якого є елементами колірного простору RGB.

1. Переклад у колірний простір YCbCr (докладніше див. лекцію 1). Тут Y - компонента яскравості, Cb і Cr - компоненти кольоровості. Людське око більше чутливе до яскравості, чим до кольору. Тому важливіше зберегти більшу точність при передачі Y, чим при передачі Cb і Cr. Переклад здійснюється по наступній формулі:

зворотний переклад:

2. Субдискретизация компонент кольоровості. Після перекладу в колірний простір YCbCr здійснюється субдискретизация по наступних співвідношеннях: 4:4:4 (відсутність передискретизації), 4:2:2 (компоненти кольоровості міняються через одну по горизонталі), 4:2:0 (компоненти кольоровості міняються через одну по горизонталі; при цьому по вертикалі вони міняються через рядок). Проілюструємо докладніше дані співвідношення на прикладах. Будемо перетворювати блок 4 × 4 пикселя зображення:

1. Y₀₀Cb₀₀Cr₀₀ Y₀₁Cb₀₁Cr₀₁ Y₀₂Cb₀₂Cr₀₂ Y₀₃Cb₀₃Cr₀₃

2. Y₁₀Cb₁₀Cr₁₀ Y₁₁Cb₁₁Cr₁₁ Y₁₂Cb₁₂Cr₁₂ Y₁₃Cb₁₃Cr₁₃

3. Y₂₀Cb₂₀Cr₂₀ Y₂₁Cb₂₁Cr₂₁ Y₂₂Cb₂₂Cr₂₂ Y₂₃Cb₂₃Cr₂₃

4. Y₃₀Cb₃₀Cr₃₀ Y₃₁Cb₃₁Cr₃₁ Y₃₂Cb₃₂Cr₃₂ Y₃₃Cb₃₃Cr₃₃

тоді:

4:4:4. Cубдискретизированный блок буде таким же.

4:2:2. Cубдискретизированный блок буде таким:

Y₀₀Cb₀₀Cr₀₀ Y₀₁Cb₀₀Cr₀₀ Y₀₂Cb₀₂Cr₀₂ Y₀₃Cb₀₂Cr₀₂

Y₁₀Cb₁₀Cr₁₀ Y₁₁Cb₁₀Cr₁₀ Y₁₂Cb₁₂Cr₁₂ Y₁₃Cb₁₂Cr₁₂

Y₂₀Cb₂₀Cr₂₀ Y₂₁Cb₂₀Cr₂₀ Y₂₂Cb₂₂Cr₂₂ Y₂₃Cb₂₂Cr₂₂

Y₃₀Cb₃₀Cr₃₀ Y₃₁Cb₃₀Cr₃₀ Y₃₂Cb₃₂Cr₃₂ Y₃₃Cb₃₂Cr₃₂

4:2:0. Cубдискретизированный блок буде таким:

Y₀₀Cb₀₀Cr₀₀ Y₀₁Cb₀₀Cr₀₀ Y₀₂Cb₀₂Cr₀₂ Y₀₃Cb₀₂Cr₀₂

Y₁₀Cb₀₀Cr₀₀ Y₁₁Cb₀₀Cr₀₀ Y₁₂Cb₀₂Cr₀₂ Y₁₃Cb₀₂Cr₀₂

Y₂₀Cb₂₀Cr₂₀ Y₂₁Cb₂₀Cr₂₀ Y₂₂Cb₂₂Cr₂₂ Y₂₃Cb₂₂Cr₂₂

Y₃₀Cb₂₀Cr₂₀ Y₃₁Cb₂₀Cr₂₀ Y₃₂Cb₂₂Cr₂₂ Y₃₃Cb₂₂Cr₂₂

Надалі компоненти обробляються й зберігаються окремо друг від друга. Таким чином, в останніх двох випадках ми відразу забрали й інформації відповідно. Вибір того або іншого способу передискретизації впливає на зміну ступеня стиску. Очевидно, що при відсутності передискретизації ступінь стиску погіршиться, а при схемі 4:2:0 буде найбільшою. Якщо зображення не ділиться нацело на блоки 4 × 4, то воно доповнюється по безперервності, тобто у випадку, якщо розмір по вертикалі не ділиться на 4, то додається ще від однієї до трьох рядків, що збігаються з останньої знизу. Аналогічно робиться, якщо розмір по горизонталі не ділиться на 4 - додаються стовпці, що збігаються із самим правим.

3. Застосування дискретного косинуса-перетворення. Зображення (точніше, отримані після субдискретизации компоненти) розбивається на блоки 8 × 8; до кожного блоку застосовується дискретне косинус-перетворення (окремо для компонентів Y, Cb і Сr). Якщо зображення не ділиться нацело на блоки 8 × 8, то додається відповідна кількість рядків і стовпців по безперервності.

4. Квантування. Людське око практично не зауважує зміни у високочастотних складових, отже, коефіцієнти, відповідальні за високі частоти, можна зберігати з меншою точністю. Квантування здійснюється за допомогою множення матриці коефіцієнтів ДКП на так звану матрицю квантування:

де означає покомпонентное множення й узяття цілої частини, тобто T_ij = [t_ijq_ij ], де t_ij - вихідні коефіцієнти ДКП, q_ij - компоненти матриці квантування, [] - операція узяття цілої частини. Таким чином, відбувається квантування області визначення коефіцієнтів вихідної матриці. Матриці квантування різні для компонентів кольоровості і яскравості.

На даній стадії можна задавати ступінь стиску шляхом зміни матриць квантування. Чим ближче до нуля елементи матриці квантування, тим менше буде діапазон значень елементів матриці T_ij, а виходить, їх можна закодувати, затративши меншу кількість інформації. Наприклад, якщо елементи q_ij досить близькі до нуля, то більшість елементів T_ij буде нулями.

Матриці квантування застережені в стандарті, а для зміни ступеня стиску їх множать на певний коефіцієнт. Очевидно, що втрати на цій стадії самі більші; якщо забрати занадто багато інформації з низькочастотних компонентів (тобто занадто сильно огрубіти компоненти), те з'являться артефакти: розпадання на квадрати 8 × 8, ефект Гиббса (виникнення ореола поруч із місцями різких колірних переходів) (див. мал. 14.3).

5. Зигзаг-упорядочивание. До кожної квантованной матриці застосовується так зване зигзаг-упорядочивание. Це особливий прохід матриці для одержання послідовності (див. мал. 14.4). Спочатку йде елемент T₀₀, потім T₀₁, T₁₀, T₁₁ . . . Причому для типових фотореалістичних зображень спочатку будуть іти ненульові коефіцієнти, що відповідають низькочастотним компонентам, а потім - безліч нулів.

6. Стиск методом RLE. Отримана послідовність кодується за допомогою модифікованого алгоритму групового кодування. Виводяться пари чисел: перше - число нулів, друге - значення після підпослідовності нулів. Наприклад, закодуємо таку послідовність:

122 0 125 0 0 44 0 0 0 0 -1.

Одержимо: (0, 122) (1, 125) (2, 44) (4, -1). Також існує спеціальний код для позначення того факту, що значення, що залишилися, у послідовності суть нулі.

7. СтискметодомХаффмена. Проводиться кодуванням методом Хаффмена зі спеціальною фіксованою таблицею.

Рис. 14.3. Артефакти JPEG. Угорі - вихідне зображення, унизу - зображення, стисле в 30 разів алгоритмом JPEG

Рис. 14.4. Зигзаг-упорядочивание

Алгоритм відновлення зображення суть інверсія вищенаведених дій. Ступінь стиску від 5 до 100 і більше раз (варіюється за допомогою матриць квантування й завдання методу субдискретизации). При цьому візуальна якість для більшості фотореалістичних зображень залишається на гарному рівні при стиску до 15 разів.

Даний алгоритм і формат є найпоширенішими для передачі й зберігання полноцветных зображень. Настільки широке поширення пояснюється декількома причинами: щодо невисокою обчислювальною складністю (що було дуже актуально до 1996 року), достатнім ступенем стандартизованности формату й алгоритму, а також відсутністю необхідності платити які-небудь ліцензійні відрахування (тому що відсутні патентовані алгоритми). До недоліків алгоритму відносять виникнення згадуваних вище артефактів, які занадто помітні для людського ока.

Описана вище схема стиску є типовою для алгоритмів стиску зображень із втратами (за винятком фрактального). Відмінність в основному складається в типі перетворення на кроці 3. Далі ми розглянемо інший вид перетворення.