Для цього використовується квантування коефіцієнтів (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

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

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

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

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

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

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

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

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

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

1.2.6.2 Алгоритм JPEG 2000

Алгоритм JPEG-2000 розроблений тією же групою експертів в області фотографії, що й JPEG. Формування JPEG як міжнародного стандарту було закінчено в 1992 році [4,10]. В 1997 стало ясно, що необхідно новий, більше гнучкий і потужний стандарт, що і був дороблений до зими 2000 року. Основні відмінності алгоритму в JPEG 2000 від алгоритму в JPEG полягають у наступному:

1. Краща якість зображення при сильному ступені стиснення.

Підтримка кодування окремих областей із кращою якістю. Відомо, що окремі області зображення критичні для сприйняття людиною, у той час як якістю інших можна знехтувати. При «ручній» оптимізації збільшення ступеня стиснення проводиться доти, поки не буде втрачена якість у якійсь важливій частині зображення. В даному методі з'являється можливість задати якість у критичних областях, стиснувши інші області сильніше, тобто одержується ще більший остаточний ступінь стиснення при суб'єктивно рівній якості зображення.

3. Основний алгоритм стиснення замінений на wavelet. Крім зазначеного підвищення ступеня стиснення це дозволило позбутися від 8-піксельної блочності, що виникає при підвищенні ступеня стиснення.

4. Для підвищення ступеня стиснення в алгоритмі використовується арифметичне кодування.

5. Підтримка стиснення однобітних (2-кольорових) зображень. Для збереження однобітних зображень (малюнки тушшю, відсканований текст і т.п.) раніше повсюди рекомендувався формат GIF, оскільки стиснення із використанням ДКП досить неефективно стискає зображеня із різкими переходами кольорів. В JPEG при стисненні 1-бітна картинка приводилася до 8-бітної, тобто збільшувалася в 8 разів, післе чого робилася спроба стиснення. Зараз можна рекомендувати JPEG 2000 як універсальний алгоритм.

6. На рівні формату підтримується прозорість. Крім того, підтримується не тільки 1 біт прозорості (піксель прозорий/непрозорий), а окремий канал, що дозволить задавати плавний перехід від непрозорого зображення до прозорого фону.

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

Базова схема JPEG-2000 дуже схожа на базову схему JPEG. Відмінності полягають у наступному:

Замість дискретного косинусного перетворення (DCT) використається дискретне вейвлет-перетворення (DWT).

Замість кодування по Хаффмену використовується арифметичне стиснення.

В алгоритм закладене керування якістю областей зображення.

4) Не використовується явно дискретизація компонентів U і V після перетворення колірних просторів, оскільки при DWT можна досягти того ж результату, але більш акуратно.

Блок-структурна схема даного алгоритму приведена на рис. 1.10.

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

Розглянемо алгоритм по кроках.

Етап 1. В JPEG-2000 передбачене зрушення яскравості (DC level shift) кожного компонента (RGB) зображення перед перетворенням в YUV. Це робиться для вирівнювання динамічного діапазону (наближення до 0 гістограми частот), що приводить до збільшення ступеня стиснення. Формулу перетворення можна записати як:

(1.10)

При відновленні зображення виконується зворотне перетворення:

. (1.11)

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

Етап 3. Дискретне wavelet перетворення (DWT) також може бути двох видів - для випадку стиснення із втратами й для стиснення без втрат.

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

, (1.12)

. (1.13)

Оскільки більшість , крім i=0, рівні 0, то можна переписати наведені формули з меншою кількістю операцій. Для простоти розглянемо випадок стиснення без втрат.

, (1.14)

, (1.15)

Легко показати, що даний запис можна еквівалентно переписати, зменшивши ще втроє кількість операцій множення й розподіли (однак тепер необхідно буде підрахувати спочатку всі непарні у). Додамо також операції округлення до найближчого цілого, що не перевищує задане число а, позначені як [a]:

, (1.16)

, (1.17)

Етап 4. Так само, як і в алгоритмі JPEG, після DWT застосовується квантування.

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

Етап 5. Для стиснення отриманих масивів даних в JPEG 2000 використовується варіант арифметичного стиснення, названий MQ-кодер, прообраз якого (QM-кодер) розглядався ще в стандарті JPEG, але реально не використовувався через патентні обмеження.

1.2.7 Зведені характеристики існуючих методів стиснення зображень

В табл. 1.3 наведені основні параметри, що характеризу.ть методи стиснення зображень, описані вище [4].

Таблиця 1.3. Порівняльна хаарктеристика методів стиснення зображень

1.3 Висновки по розділу