Стандарти стиснення півтонових нерухомих зображень

МККТТ і ISO розробили декілька стандартів стиснення напівтонових (многоградаціонних) зображень. Ці стандарти, знаходяться на різних стадіях твердження, стосуються алгоритмів стиснення як монохромних (чорно-білих), так і кольорових зображень. У протилежний стандартам стиснення двійкових зображень, розглянутих в Розділі 1.6.1, стандарти стиснення напівтонових зображень принципово грунтуються тільки на методах стиснення з втратами (див. Розділи 1.5.2 та 1.5.3). При розробці стандартів, комітети МККТТ і ISO запитували рекомендації з приводу алгоритмів у великого числа дослідницьких лабораторій, компаній та університету. Кращі з числа алгоритмів, представлених на розляд, були відібрані на основі критеріїв якості зображення і характеристик стиснення. Підсумковими стандартами, що відображають сучасне положення технології стиснення напівтонових зображень, з'явилися наступні: первісний стандарт JPEG заснований на ДКП; нещодавно запропонований, заснований на вейвлет-перетворенні, стандарт JPEG 2000; а також стандарт JPEG-LS, що поєднує схему безпомилкового або майже безпомилкового адаптивного передбачення з механізмом виявлення плоских областей та кодуванням довжин серій [ISO/IЕС, 1999].

JPEG

Одним з найбільш повних і популярних стандартів стиснення напівтонових нерухомих зображень є стандарт JPEG. Він визначає три різних режими кодування: (1) режим послідовного кодування з втратами, заснований на ДКП та відповідний для більшості застосувань; (2) розширений режим кодування, використовуємих для більшого стиснення, для більш високої точності, або для покрокового відтворення; та (3) режим кодування без втрат, гарантує точне відновлення інформації після стиснення. Щоб бути сумісним зі стандартом JPEG, продукт або система повинні забезпечувати підтримку режиму послідовного кодування. При цьому точно не визначаються ні формат файлу, не проторове розширення, ні модель колірного простору.

В системі з послідовною обробкою (кодуванням), часто називається системою послідовної розгортки, точність вхідних і вихідних даних обмежена 8 бітами, а точність квантованих коефіцієнтів ДКП обмежена 11 бітами. Сам процес стиснення складається з трьох послідовних кроків: обчислення ДКП, квантування і кодування нерівномірним кодом. Спочатку зображення розбивається на окремі блоки розмірами 8x8 елементів, які обробляються послідовно зліва направо і зверху вниз. Обробка кожного блоку починається зі зсуву по яскравості значень всіх його 64 елементів, що отримується відніманням величини , де - максимальне число рівнів яскравості. Потім обчислюється двовимірне дискретне косинусное перетворення елементів блоку. Отримані значення коефіцієнтів квантуються відповідно до формули (1.5-40), перебудовується зигзаг перетворенням згідно Рис. 1.36 (д), і формується одномірна послідовність квантованих коефіцієнтів.

Одновимірний масив, отриманий після зигзаг перетворення відповідно до Рис. 1.36 (д), впорядковується за зростанням просторової частоти; при цьому, як правило, виникають довгі послідовності нулів, що ефективно використовується процедурою JPEG кодування. Зокрема, ненульові АС коефіцієнти кодуються нерівномірним кодом, що визначає одночасно і значення коефіцієнта і число попередніх нулів.

Таблиця 1.17. Категорії кодування JPEG коефіцієнтів.

Таблиця 1.18. Стандартні JPEG коди для DС коефіцієнтів (яскравість).

Таблиця 1.19. Стандартні JPEG коди для АС коефіцієнтів (яскравість).

Таблиця 1.19 (продовження). Стандартні JPEG коди для АС коефіцієнтів (яскравість).

Поточний DС коефіцієнт кодується диференціальним кодом як різниця з DС коефіцієнтом попереднього блоку. Таблиці 1.17, 1.18 і 1.19 передставляють складені JPEG і задаються за умовчанням стандартні коди Хаффмана для яскравості. Рекомендований JPEG масив квантування яркостей представлений на Рис. 1.37 (6) і може бути масштабованим для отримання безлічі рівнів стиснення. Хоча як для яскравості, так і для кольору передбачені стандартні таблиці кодування, а також перевірені шкали квантування, тим не менш, допускається побудова користувальницьких таблиць і шкал, адаптованих до характеристик стисливого зображення.

Приклад 1.28. Послідовне кодування і декодування JPEG.

Розглянемо стиснення і відновлення наступного блоку з 8x8 елементів відповідно до стандарту послідовного кодування JPEG:

52 55 61 66 70 61 64 73

63 59 66 90 109 85 69 72

62 59 68 113 144 104 66 73

63 58 71 122 154 106 70 69

67 61 68 104 126 88 68 70

79 65 60 70 77 68 58 75

85 71 64 59 55 61 65 83

87 79 69 68 65 76 78 94

Вихідні значення пікселів можуть мати 256 або можливих рівнів яскравості, так що процес кодування починається зі зсуву діапазону значень - вибору з значень пікселів величини 27 або 128. В результаті вийде масив:

-76 -73 -67 -62 -58 -67 -64 -55

-65 -69 -62 -38 -19 -43 -59 -56

-66 -69 -60 -15 16 -24 -62 -55

-65 -70 -57 -6 26 -22 -58 -59

-61 -67 -60 -24 -2 -40 -60 -58

-49 -63 -68 -58 -51 -65 -70 -53

-43 -57 -64 -69 -73 -67 -63 -45

-41 -49 -59 -60 -63 -52 -50 -34

який, після прямого ДКП згідно (1.5-24) і (1.5-32) для N = 8, буде мати вигляд:

-415 -29 -62 25 55 -20 -1 3

7 -21 -62 9 11 -7 -6 6

-46 8 77 -25 -30 10 7 -5

-50 13 35 -15 -9 6 0 3

11 -8 -13 -2 -1 1 -4 1

-10 1 3 -3 -1 0 2 -1

-4 -1 2 -1 2 -3 1 -2

-1 -1 -1 -2 -1 -1 0 -1

Якщо для квантування отриманих даних використовується рекомендований JPEG масив нормалізації, наведений на Рис. 1.37 (6), то після масштабування і усікання (тобто нормалізації в відповідності до (1.5-40)), коефіцієнти візьмуть наступні значення:

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 -1 0 0 0

-4 1 2 -1 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

де, наприклад, DС коефіцієнт обчислений наступним чином:

Зауважимо, що процедура перетворення і нормалізації дає значе число нульових коефіцієнтів. Після того, як коефіцієнти переупорядковані відповідно до зигзаг перетворенням (див. Рис. 1.36 (д)), вийде наступна одномірна послідовність коефіцієнтів:

Передбачено спеціальне кодове слово КБ, що означає кінець блоку (див. код категорії 0 і довжиною серії 0 в Таблиці 1.19 кодів Хаффмана), яке вказує, що все залишилися коефіцієнти в переупорядкованій послідовності дорівнюють нулю.

Побудова JPEG коду для переупорядоченной послідовності коефіцієнтів починається з обчислення різниці між значеннями DС коефіцієнтів в поточному і попередньому (вже закодованому) блоках. Оскільки блок був узятий нами з зображення на Рис. 1.23, і відомо, що DС коефіцієнт соседнеголевого, вже перетвореного і закодованого, блоку дорівнює - 17, одержувана ДІКМ різниця буде (-26 - (-17)) = -9, яка потрапляє в категорію 4 різниць DС в Таблиці 1.17. Згідно стандартним кодами Хаффмана для різниць з Таблиці 1.18, правильний основний код буде 101 (3-бітовий код). Однак сумарна довжина повністю закодованого коефіцієнта категорії 4 складе 7 біт - залишається 4 біти повинні бути взяті з молодших розрядів (МР) значення різниці. У загальному випадку, для конкретної категорії DС різниць (скажімо, категорії К), додатково вимагається К бітів, які обчислюються або як К молодших розрядів позитивної різниці, чи як К молодших розрядів негативної різниці мінус 1. Для роз ниці -9 відповідні значення МР складуть (0111-1), або 0110, і, таким чином, повне кодоване ДІКМ кодове слово буде 1010110.

Ненульові АС коефіцієнти переупорядоченного масиву кодуются аналогічним чином по Таблицям 1.17 і 1.19. Різниця складає лише в тому, що вибір кодового слова коду Хаффмана для АС коефіцієнта залежить як від категорії амплітуди коефіцієнта, так і від числа попередніх нулів (див. колонку «Довжина серії/категорія» в Таблиці 1.19). Остаточний код першого ненульового АС коефіцієнта переупорядкованого масиву (-3) буде 0100. Перші 2 біти даного коду вказують, що коефіцієнт був з категорії 2, і що в нього немає попередніх нульових коефіцієнтів (див. Таблицю 1.17); останні 2 біти були отримані процедурою додавання МР, аналогічної викладеної вище для коду DС різниць. Продовжуючи подібним чином, повна кодова послідовність переупорядкованого масиву буде виглядати:

1010110 0100 001 0100 0101 100001 0110 100011 001 100011 001 001 100101 11100110 110110 0110 11110100 000 1010.

Прогалини між кодовими словами поставлені тут виключно для зручності читання. Хоча це і не потрібно в даному прикладі, таблиця стандартних кодів Хаффмана містить спеціальне кодове слово для серії довжиною в 15 нулів, за якою знову йде 0 (див. довжину серії F і категорію 0 в таблиці 1.19). Загальне число бітів, необхідних для кодування переупорядоченного масиву (а значить, необхідних для кодування всіх 8x8 елементів вибраного блоку), становить 92. Вихідний коефіцієнт стиснення дорівнює 512/92, або близько 5,6 / 1.

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

-26 -3 -6 2 2 0 0 0

1 -2 -4 0 0 0 0 0

-3 1 5 -1 -1 0 0 0

-4 1 2 -1 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

Після множення на коефіцієнти нормалізації згідно (1.5-42), отримаємо масив:

-416 -33 -60 32 48 0 0 0

12 -24 -56 0 0 0 0 0

- 42 13 80 -24 -40 0 0 0

-56 17 44 -29 0 0 0 0

18 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

де, наприклад, DС коефіцієнт отриманий таким чином

Повністю відновлений блок виходить після виконання зворотнього ДКП отриманого масиву відповідно до рівнянь (1.5-25) і (1.5-32), що дає

-70 -64 -61 -64 -69 -66 -58 -50

-72 -73 -61 -39 -30 -40 -54 -59

-68 -78 -58 -9 13 -12 -48 -64

-59 -77 -57 0 22 -13 -51 -60

-54 -75 -64 -23 -13 -44 -63 -56

-52 -71 -72 -54 -54 -71 -71 -54

-45 -59 -70 -68 -67 -67 -61 -50

-35 -47 -61 -66 -60 -48 -44 -44

і зворотного зсуву діапазону значень на + (тобто + 128). У результаті отримуємо:

58 64 67 64 59 62 70 78

56 55 67 89 98 88 74 69

60 50 70 119 141 116 80 64

69 51 71 128 149 115 77 68

74 53 64 105 115 84 65 72

76 57 56 74 75 57 57 74

83 69 59 60 61 61 67 78

93 81 67 62 69 80 84 84

Всі відмінності значень елементів вихідного і відновленого бло ків виникають внаслідок самої природи стиснення з втратами, явля ющегося суттю 1РЕС процедур стиснення і відновлення. У даному прикладі, помилки відновлення знаходяться в діапазоні від -14 до +11 і розподілені наступним чином:

-6 -9 -6 2 11 -1 -6 -5

7 4 -1 1 11 -3 -5 3

2 9 -2 -6 -3 -12 -14 9

-6 7 0 -4 -5 -9 -7 1

-7 8 4 -1 11 4 3 -2

3 8 4 -4 2 11 1 1

2 2 5 -1 -6 0 -2 5

-6 -2 2 6 -4 -4 -6 10

Середньоквадратична помилка відхилення, що з'явилася в результаті всього процесу стиснення і відновлення, становить приблизно 5,9 рівнів яскравості.

Блок пікселів, відновлюваний в попередньому прикладі, розміщений майже в центрі правого ока знімка жінки на Рис. 1.38 (а). Зауважимо, що як у вихідному, так і у відновленому блоках є пік значень яскравості у п'ятому елементі четвертого ряду, що відповідає відблиску на зіниці. Наявність такого локального піку і призвело до помітному збільшенню середньоквадратичної помилки відхилення відновленого блоку в порівнянні з середньою помилкою по всьому відбудовн-ленному зображенню. Фактично вона виявилася вдвічі вищою, ніж у відновленого зображення на Рис. 1.38 (а), яке також було стисло тим же JPEG алгоритмом послідовного кодування. Причина в тому, що багато блоки на вихідному зображенні потрапляють на ділянці з майже постійним значенням, і можуть бути представлені з малими помилками. На Рис. 1.38 (6) представлений ще один результат стиску зображення JPEG алгоритмом послідовного кодування.

JPEG 2000

Стандарт JPEG 2000, хоча він ще остаточно формально не прийнятий, розширює вихідний стандарт JPEG, надаючи велику гнучкість, як при стисненні напівтонових зображень, так і при доступі до самим стислим даними. Так, наприклад, окремі частини зображення, стиснутого за стандартом JPEG 2000, можуть бути виділені для передачі, зберігання, відтворення або редагування. Стиснення за стандартом JPEG 2000 засновано на методах вейвлет-кодування, розглянутих в Розділі 1.5.3. Квантування коефіцієнтів здійснюється по-різному в різних масштабах і діапазонах (смугах), а самі квантовані коефіцієнти кодуються арифметичним кодом як бітові площини (див. Розділ 1.4). Згідно з визначеннями стандарту [ISO/IEC, 2000], процедура кодування зображення полягає в наступному.

Першим кроком процедури кодування є зрушення значення середнього рівня яскравості, здійснюваний вирахуванням з позитивних значень відліків кодованого зображення величини , де n - число бітів в елементах зображення. Якщо зображення має більше однієї компоненти - як, наприклад, червона, зелена і синя компоненти в разі кольорового зображення - кожна компонента зрушується незалежно. Якщо компонент в точності три, то вони додатково можуть бути декорельовані за допомогою лінійного перетворення компонент. Згідно стандарту, перетворення компонент може бути оборотним (перетворення цілих значень в цілі, використовуване в оборотньому вейвлет-перетворенні 5-3 без втрат), або незворотних (перетворення дійсних значення в дійсності, використовуючи у необоротному вейвлет-перетворенні 9-1 з втратами). Так, необоротне перетворення компонент складається в наступному:

де , і - зрушені вліво по осі яскравості значення вхідних компонент, а , і - відповідні значення декорельованих компонент. Якщо вхідними компонентами є червона, зелена і синя складові кольорового зображення, то формули (1.6-1) відповідають колірному перетворенню з простору R’G’B’ в простір . Мета перетворення полягає в поліпшенні ефективності стиску; компоненти і є різницевими зображеннями, гістограми яких мають чітко виражені піки поблизу нуля.

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

Потім обчислюється одномірне дискретне вейвлет-перетворення по рядках і по стовпцях кожної компоненти тайла. Стиснення без втрат (оборотне вейвлет-перетворення 5-3) засноване на використанні коефіцієнтів уточнюючих послідовностей для масштабованої функції та вейвлет-функції системи біортогонапьних вейвлетів. Для нецілих значень коефіцієнтів перетворення задається процедура округлення. У системах стиснення з втратами (необоротне вейвлет-перетворення 9-7) застосовують коефіцієнти уточнюючих послідовностей для масштабується функції та вейвлет-функції системи вейвлетів, описаної в. У кожному з випадків перетворення обчислюється з допомогою швидкого вейвлет-перетворення, або за допомогою так званої ліфтинг-схеми. Коефіцієнти, необхідні для побудови блоку фільтрів аналізу незворотного швидкого вейвлет-перетворення (БВП) 9-7, наведені в Таблиці 1.20. Реалізація альтернативної ліфтинг-схеми вимагає шести послідовних операцій:

Тут X є перетворюються тайл-компонента, Y - результат перетворення, а і задають положення тайл-компоненти всередині компоненти повного зображення. Тобто, вони є індекс першого відліку перетвореного рядка або стовпця тайл-компоненти (), і того відліку, який слідує безпосередньо за послідовним відліком (). Змінна n приймає значення у залежності від значень і , а також від того, яка з шести операцій виконується. Для або , X(n) виходить симетричним продовженням Х; наприклад, . По закінченні операцій ліфтінга значення Y з парними індексами будуть збігатися з результатами на виході низькочастотного БВП фільтра аналізу, а значення Y з непарнимі індексами - з результатами на виході високочастотного БВП фільтра аналізу. Параметри ліфтингу складають: = -1,586134342, = -0,052980118, = 0,882911075, = 0,433506852, а коефіцієнт К = 1,230174105.

Таблиця 1.20. Імпульсні характеристики низькочастотного і високочастотного фільтрів аналізу для незворотного вейвлет-перетворення 9-7, застосовуваного в разі стиснення з втратами.

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

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

Рис. 1.46. Система позначень JPEG 2000 для коефіцієнтів двухмасштабного вейвлет-перетворення тайл-компоненти і число додаткових бітів розміщення.

де - знак числа, [•] - ціла частина числа, а крок квантування становить

Тут - номінальний динамічний діапазон складової b, а - число бітів, що відводяться на значення порядку і мантиси її коефіцієнтів. Номінальний динамічний діапазон складової b є сума числа бітів, використовуваних для представлення початкового зображення, і числа додаткових бітів розкладання складової b; число додаткових бітів приведено цифрами в кільцях на Рис. 1.46. Так, для складової потрібно 2 додаткових біти розкладання.

У разі стиснення без втрат, , , а . Для не оборотнього стиснення в стандарті не вказується ніякого конкретного кроку квантування. Замість цього, число бітів порядку і мантиси повинно передаватися декодеру або разом з кожною складовою, і це називається явним квантуванням, або ж тільки з складовою що називається неявним квантуванням. В останньому випадку інші складові квантуються з використанням значень параметрів, обчислених з параметрів складової . Вважаючи, що і - число бітів, що відводяться для складової , параметри для складової обчислюються наступним чином:

де позначає число рівнів розкладання складової від вихідної тайл-компоненти зображення до складової b.

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

У декодері JPEG 2000 описані вище операції виконуються в зворотному порядку. Спочатку, на підставі зазначених вище користувачів цікавить фрагмента зображення і точності його відтворення, здійснюється відновлення потрібних смуг відповідних тайл-компонент. Для цього із загального потоку даних вибираються необхідні пакети потрібних шарів, відновлюється бітовий потік, здійснюється арифметичне декодування і розпаковуються біти коефіцієнтів. Хоча кодер міг закодувати бітових площин конкретної смуги, користувач, завдяки особливостям вкладеності кодового потоку, може вибрати відновлення лише частини бітових площин. Це еквівалентно квантуванню коефіцієнтів кодового блоку з кроком розміру . Все не розпаковані біти обнуляються, і результуючі коефіцієнт ти, що позначаються відновлюються наступним чином

де означає відновлене значення коефіцієнта, а - число декодованих бітових площин для . Отримані значення коефіцієнтів потім піддаються зворотним перетворенням по стовпцях і рядках, використовуючи блок фільтрів зворотнього БВП, коефіцієнти якого беруться з Таблиці 1.20, або за допомогою наступної ліфтинг-операції

Параметри , , , і тут ті ж, що використовувалися для рівнянь (1.6-2). Якщо необхідно, здійснюється симетричне продовження значень коефіцієнтів по рядках і стовпцях. Фінальними операціями декодування є збір тайл-компонент, зворотне перетворення компонент (якщо потрібно) і зворотний зсув значення середнього рівня яскравості. У разі незворотного вейвлет-перетворення 9-7, зворотне перетворення компонент обчислюєтся за формулами

після чого до отриманим значенням додається величина , де n - число бітів в елементах зображення. Зображення на Рис. 1.40 і 1.41 Розділу 1.5.3, що ілюструють стиснення з коефіцієнтами від 34:1 до 167:1, були отримані за допомогою алгоритму JPEG 2000 стиску з втратами.

Поиск по сайту: