1.2.6. Алгоритми стиснення з втратами

1.2.6.1. Алгоритм jpeg

Однимими з найпоширеніших на сьогоднішній день кодерів стиснення відеозображень є JPEG|, що розроблявся об'єднаною|з'єднаною| міжнародною групою експертів по обробці даних відеозображень (Joint| Photographic| Experts| Group|) спільно з|із| комітетом СCITT і міжнародною організацією |з'єднаних| стандартизації ISO| в 1991 році. Перший кодер JPEG розроблявся, як алгоритм стиснення для неперервно-тонових 24-бітових зображень [9].

Оперує алгоритм областями 8x8, на яких яскравість і кольори міняються порівняно плавно. Внаслідок цього, при розкладанні матриці такої області в подвійний ряд по косинусах (див. формули нижче) значимими виявляються тільки перші коефіцієнти. Таким чином, стиснення в JPEG здійснюється за рахунок плавності зміни кольорів у зображенні.

У цілому алгоритм заснований на дискретному косинусоїдальному перетворенні (надалі ДКП), застосовуваному до матриці зображення для одержання деякої нової матриці коефіцієнтів. Для одержання вихідного зображення застосовується зворотне перетворення.

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

Для цього використовується квантування коефіцієнтів (quantization). У найпростішому випадку - це арифметичне побітове зрушення вправо. При цьому перетворенні губиться частина інформації, але може досягатися більший ступінь стиснення.

Отже, розглянемо алгоритм докладніше. Нехай ми стискаємо 24-бітне зображення.

Етап 1. Переводимо зображення з колірного простору RGB, з компонентами, відповідальними за червону (Red), зелену (Green) і синю (Blue) складові кольору крапки, у колірний простір YCrCb (іноді називають YUV).

У ньому Y - яскравісна складова, а Сг, Сb - компоненти, відповідальні за кольори (хроматичний червоний і хроматичний синій). За рахунок того, що людське око менш чутливе до кольорів, ніж до яскравості, з'являється можливість архівувати масиви для Сг і Сb компонент із більшими втратами й, відповідно, більшими ступенями стиснення. Подібне перетворення вже давно використовується в телебаченні. На сигнали, відповідальні за кольори, там виділяється більш вузька смуга частот.

Спрощено переклад з колірного простору RGB у колірний простір YCrCb можна представити у вигляді матриці переходу:

Зворотнє перетворення здійснюється множенням вектору YUV на обернену матрицю:

Етап 2. Розбиваємо вихідне зображення на матриці 8x8. Формуємо з кожної третьої робочої матриці ДКП - по 8 біт окремо для кожного компонента. При більших ступенях стиснення цей крок може виконуватися трохи складніше. Зображення ділиться по компоненті Y - як і в першому випадку, а для компонентів Сг і Сb матриці набираються через рядок і через стовпець. Тобто з вихідної матриці розміром 16x16 виходить тільки одна робоча матриця ДКП. При цьому, як неважко помітити, ми втрачаємо 3/4 корисної інформації про колірні складові зображення й одержуємо відразу стиснення у два рази. Ми можемо робити так завдяки роботі в просторі YCrCb. На результуючому RGB зображенні, як показала практика, це позначається несильно.

Етап 3. У спрощеному вигляді ДКП при п=8 можна представити так:

, (1.8)

де ,

а .

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

Етап 4. Проводимо квантування. У принципі, це просто розподіл робочої матриці на матрицю квантування поелементно. Для кожного компонента (Y, U і V), у загальному випадку, задається своя матриця квантування q[u,v] (далі МК).

(1.9)

На цьому кроці здійснюється керування ступенем стиснення, і відбуваються самі більші втрати. Зрозуміло, що, задаючи МК із більшими коефіцієнтами, ми одержимо більше нулів і, отже, більший ступінь стиснення.

У стандарт JPEG включені рекомендовані МК, побудовані дослідним шляхом. Матриці для більшого або меншого ступеня стиснення одержують шляхом множення вихідної матриці на деяке число gamma.

Із квантуванням зв'язані й специфічні ефекти алгоритму. При більших значеннях коефіцієнта gamma втрати в низьких частотах можуть бути настільки великі, що зображення розпадеться на квадрати 8x8. Втрати у високих частотах можуть виявитися в так званому «ефекті Гіббса», коли навколо контурів з різким переходом кольорів утвориться своєрідний «німб».

Етап 5. Переводимо матрицю 8x8 в 64-елементний вектор за допомогою «зиґзаґ»-сканування, тобто беремо елементи з індексами (0,0), (0,1), (1,0), (2,0)... (рис.1.8).

Рис. 1.8. Зиґзаґ-сканування

Таким чином, на початку вектора ми одержуємо коефіцієнти матриці, що відповідають низьким частотам, а наприкінці - високим.

Етап 6. Згортаємо вектор за допомогою алгоритму групового кодування. При цьому одержуємо пари типу (пропустити, число), де «пропустити» є лічильником нулів, що пропускають, а «число»- значення, які необхідно поставити в наступну ячійку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1... буде згорнутий у пари (0,42) (0,3) (3,-2) (4,1)....

Етап 7. Згортаємо отримані пари кодуванням по Хаффману з фіксованою таблицею.

Процес відновлення зображення в цьому алгоритмі повністю симетричний. Метод дозволяє стискати деякі зображення в 10-15 разів без серйозних втрат.

Основні кроки стиснення за методом JPEG,| представлені|уявляти| у вигляді структурно-логічної схеми на рис. 1.9.

Рис. 1.9. Блок-структурна схема реалізації методу JPEG|

Істотними позитивними сторонами алгоритму є те, що:

1. Задається ступінь стиснення.

1. Вихідне кольорове зображення може мати 24 біта на крапку.

Негативними сторонами алгоритму є те, що:

1. При підвищенні ступеня стиснення зображення розпадається на окремі квадрати (8x8). Це пов'язане з тим, що з’являються більші втрати в низьких частотах при квантуванні, і відновити вихідні дані стає неможливо.

2. Проявляється ефект Гіббса — ореоли по межах різких переходів кольорів.

Як уже говорилося, стандартизований JPEG був в 1991 році. Але вже тоді існували алгоритми, що стискають сильніше при менших втратах якості. Справа в тому, що дії розроблювачів стандарту були обмежені потужністю існуючої на той момент техніки. Тобто навіть на персональному комп'ютері алгоритм повинен був працювати менше хвилини на середньому зображенні, а його апаратна реалізація повинна бути відносно простою і дешевою. Алгоритм повинен був бути симетричним (час розархівації приблизно дорівнює часу архівації).

Виконання останньої вимоги уможливило появу таких пристроїв, як цифрові фотоапарати, що знімають 24-бітові фотографії на 8 - 256 Мб флеш карту. Потім ця карта вставляється в роз’єм на вашому ноутбуці й відповідна програмі дозволяє зчитати зображення. Чи не правда, що якби алгоритм був несиметричний, було б неприємно довго чекати, поки апарат «перезарядиться»- стисне зображення.

Не дуже приємною властивістю JPEG є також те, що нерідко горизонтальні й вертикальні смуги на дисплеї абсолютно не помітні й можуть виявитися тільки при печатці у вигляді муарового візерунка. Він виникає при накладанні похилого растра друку на горизонтальні й вертикальні смуги зображення. Через це JPEG не рекомендується активно використати в поліграфії, задаючи високі коефіцієнти матриці квантування. Однак при архівації зображень, призначених для перегляду людиною, він на даний момент незамінний.

Широке застосування JPEG довгий час зумовлювалося, мабуть, лише тим, що він оперує 24-бітними зображеннями. Тому для того, щоб із прийнятною якістю подивитися картинку на звичайному моніторі в 256-кольоровій палітрі, було необхідне застосування відповідних алгоритмів і, отже, певний час. У програмах, орієнтованих на прискіпливого користувача, таких, наприклад, як ігри, подібні затримки неприйнятні. Крім того, якщо наявні у вас зображення, припустимо, в 8-бітному форматі GIF перевести в 24-бітний JPEG, а потім назад в GIF для перегляду, то втрата якості відбудеться двічі при обох перетвореннях. Проте, виграш у розмірах архівів найчастіше настільки великий (в 3-20 разів), а втрати якості настільки малі, що зберігання зображень в JPEG виявляється дуже ефективним.