1.2.6.2. Алгоритм jpeg 2000

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

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

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

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

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

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

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

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

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

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

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

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

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, але реально не використовувався через патентні обмеження.