Стиснення зображень

Приклад 1.26. Вибір інтервалу «мертвої зони» в вейвлет-кодуванні.

Вплив розміру інтервалу «мертвої зони» на частку усікаються детальних коефіцієнтів для трьохрівневого вейвлет-кодування. З збільшення розміру «мертвої зони» число обнуляємих коефіцієнтів також зростає. Вище зламу кривої (тобто більше 4,5) приріст малий; це є наслідком того, що гістограма детальних коефіцієнтів має яскраво виражений пік поблизу нуля. Стандартні відхилення помилок відновлення, відповідні порогу «мертвої зони» зростають від 0 до 1,77 рівня яскравості при порозі 4,5, і до 2,79 при порозі 18, де число нулів досягає вже 96,43%. Якщо видалити всі детальні коефіцієнти, що збільшить частку нулів приблизно на 1,5%, то помилка відновлення зросте до 7,6 рівнів яскравості.

1.6 Стандарти стиснення зображень

Багато з методів стиснення (як з втратами, так і без втрат), описані до справжнього моменту, грають найважливішу роль в найбільш розповсюджених стандартах стиснення зображень. У даному розділі розглядаються деякі з цих стандартів, і на їх основі демонструются представлені раніше методи. Більшість з стандартів були схвалені Міжнародною організацією зі стандартизації (International Standardization Organization - IOS) і Міжнародним Консультативним Комітетом з телефонії і телеграфії - МККТТ. Вони стосуються застосування методів стиснення як двійкових, так і напівтонових (монохромних або кольорових) зображень, а також і нерухомих, і рухомих зображень (тобто відеопослідовностей).

1.6.1 Стандарти стиснення двійкових зображень

Двома з найбільш широко використовуваних стандартів стиснення двійкових (двохградаційнних) зображень є стандарти МККТТ Групи 3 та Групи 4. В даний час вони застосовуються в багатьох комп'ютерних додатках, хоча спочатку вони розроблялися як методи факсимільного (FАХ) кодування для передачі документів по телефонним мережам. Стандарт Групи 3 використовує неадаптивний метод одновимірного кодування довжин серій, згідно якого в кожній групі з K рядків (К = 2 або 4) всі рядки крім першої можуть кодуватися двовимірним чином. Стандарт Групи 4 є модернізованим і дещо спрощеним варіантом стандару Групи 3, допускає лише двовимірне кодування. Обидва стандарти використовують один і той же неадаптівний підхід до двовимірному кодуванню. Цей підхід дуже близький до методу кодування відносних адрес (КВА), описаного в Розділі 1.4.3.

При розробці стандартів МККТТ були відібрані вісім представлених тестових документів, що містять надруковані і рукописні тексти на декількох мовах, а також графічні малюнки. Зображення цих документів використовувалися як основа для оцінювання різних варіантів двійкового стиснення. Існуючі стандарти Групи 3 та Групи 4 дозволяють стискати їх з коефіцієнтом близько 15:1. Оскільки стандарти Групи 3 та Групи 4 є неадаптівними методами, то іноді вони приводять до збільшення обсягу даних (наприклад, у випадку напівтонових зображень). Щоб подолати цю та пов'язані з нею інші проблеми. Об'єднана група по двійковим зображенням, що є об'єднаним комітетом при МККТТ і ISO, адаптувала і запропонувала кілька інших стандартів стиснення двійкових зображень. Вони включають JBIG1 - метод адаптивного арифметичного кодування, що забезпечує найкращі результати стиснення, як в середньому, так і в найгіршому випадках, а також JBIG2 (на даний момент остаточний варіант, представлений комітетом), який дозволяє досягти стиснення в 2-4 раз кращого, ніж JBIG1. Ці стандарти можуть бути використані для стиснення як двійкових, так і напівтонових зображень з роздільною здатністю по яскравості до 6 бітів на піксель (методом кодування бітових площин).

Одновимірний стиск.

У одновимірному методі стиснення МККТТ Групи 3 кожен рядок зображення кодується послідовністю нерівномірних кодів, які відображають довжини переміжних серій білих і чорних елементів при порядковому скануванні зліва направо. При цьому бувають два типи кодових слів. Якщо довжина серії менше 63 елементів, то використовується код закінчення з Таблиці 1.14, що містить модифікований код Хаффмана. Якщо ж довжина серії перевищує 63 елемента, то спочатку ставиться максимально можливий код продовження (не перевищує довжини серії) з Таблиці 1.15, за яким йде код закінчення, відповідної різниці між дійсною довжиною серії і значенням коду продовження.

Таблиця 1.14 Коди закінчення МККТТ

Стандарт вимагає, щоб кожен рядок починалася з серії білих точок, яка може виявитися нульової довжини - в цьому випадку вона буде представена кодовим словом 00110101. Нарешті, для закінчення кожного рядка, а також для початку нового зображення (сторінки), використовується унікальне кодове слово кінця рядка (КР) із значенням 000000000001. Кінець послідовності зображень (документа) позначається шістьма послідовними кодами КР.



Таблиця 1.15 Коди продовження МККТТ

Двовимірний стиск.

Спосіб двовимірного стиснення, прийнятий стандартами МККТТ Групи 3 і Групи 4, заснований на построчном скануванні, згідно якому позиція кожного елемента зміни (тобто елемента переходу з чорного на біле або з білого в чорне) поточного кодованого рядка кодується, або щодо позиції відповідного елемента зміни опорного рядка (тобто рядки, розташованої безпосередньо над кодованого рядком), або щодо позиції попереднього елемента зміни в кодованого рядку. Опорним рядком для першого рядка кожного зображення є уявний білий рядок.

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

Після визначення позиції поточного опорного елемента і пов'язаних з ним елементів зміни, виконуються дві прості перевірки, на підставі яких вибирається один з трьох можливих режимів кодування: перехідний режим, вертикальний режим або горизонтальний режим. Перша перевірка, відповідна першій точці розгалуження, порівнює позиції і . Інша перевірка, відповідна другої точки розгалуження в схемі на Рис. 1.44, визначає відстань між позиціями і і порівнює його зі значенням 3. Залежно від результатів цих перевірок здійснюється перехід на один із трьох обведених блоків на Рис. 1.44, після чого виконується відповідна процедура кодування. Потім для підготовки до наступного кроку ітерації визначається нова позиція опорного елемента згідно відповідному методу на блок-схемі.

У Таблиці 1.16 наведені особливі коди, що використовуються для кожного із трьох можливих режимів кодування. У перехідному режимі, в якому, зокрема, виключений випадок розташування безпосередньо під , потрібно тільки кодове слово перехідного режиму 0001. Як показано на Рис. 1.45 (а), даний режим відповідає випадку, коли білі або чорні серії опорної рядки не перекривають поточну білу або чорну серію на кодованого рядку. У горизонтальному режимі кодування відстані від до і від до повинні кодуватися відповідно до кодів закінчення і кодами продовження з Таблиць 1.14 і 1.15, які слідують за кодовим словом горизонтального режиму 001. Цей випадок позначений в Таблиці 1.16 як де і позначають відстані, відповідно, від до і від до . Нарешті, у вертикальному режимі кодування одне з семи кодових слів позначає відстань між і . Параметри, пов'язані з горизонтальним і вертикальними режимами кодування. Кодове слово моди розширення, наведене в нижньому рядку Таблиці 1.16, використовується для вказівки додаткового режиму факсимільного кодування. Так, наприклад, код 0000001111 використовується для початку режиму передачі без стискування.

Таблиця 1.16 Таблиця двовимірного коду МККТТ.

Приклад 1.27. Приклад вертикального режиму кодування МККТТ.

Друга перевірка, здійснює вибір між вертикальним і горизонтальним режимом, вказує на те, що повинен бути задіяний вертикальний режим, оскільки відстань між і менше 3. Згідно Таблиці 1.16, повинно бути вибрано кодове слово 000010, яке вказує, що знаходиться на дві позиції лівіше . В якості підготовки до наступної ітерації, переміщається в позицію .

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

МККТТ і 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 (д), впорядковується за зростанням просторової частоти; при цьому, як правило, виникають довгі послідовності нулів, що ефективно використовується процедурою 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) застосовують коефіцієнти уточнюючих послідовностей для масштабується функції та вейвлет-функції системи вейвлетів, описаної в. У кожному з випадків перетворення обчислюється з допомогою швидкого вейвлет-перетворення, або за допомогою так званої ліфтинг-схеми. Коефіцієнти, необхідні для побудови блоку фільтрів аналізу незворотного швидкого вейвлет-перетворення (БВП).Реалізація альтернативної ліфтинг-схеми вимагає шести послідовних операцій:

Тут X є перетворюються тайл-компонента, Y - результат перетворення, а і задають положення тайл-компоненти всередині компоненти повного зображення. Тобто, вони є індекс першого відліку перетвореного рядка або стовпця тайл-компоненти (), і того відліку, який слідує безпосередньо за послідовним відліком (). Змінна n приймає значення у залежності від значень і , а також від того, яка з шести операцій виконується. Для або , X(n) виходить симетричним продовженням Х; наприклад

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

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

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

Стандарт не визначає число масштабів, які повинні бути обчислені.

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

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

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

Так, для складової потрібно 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 стиску з втратами.

1.6.3 Телевізійні стандарти стиснення

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

Багато зі стандартів для відеоконференцій, включаючи Н.261 (називаються також РХ64), Н.262, Н.263, і Н.320, визначені Міжнародним союзом з телекомунікацій (ITU), що є наступником Міжнародного консультативного комітету з телеграфії і телефонії (МККТТ). Стандарт Н.261 призначений для застосування при швидкостях, відповідних звичайними телефонними лініями, і забезпечує передачу відеоданих по лініях Т1 із затримками не більше 150 мс. (При затримках більше 150 мс. у спостерігача частково втрачається відчуття візуальної зворотнього зв'язку). Стандарт Н.263, навпаки, призначений для передачі відеоданих з дуже низькими швидкостями від 10 до 30 Кбіт/сек., а стандарт Н.320, який є розширенням Н.261, розроблений з урахуванням смуги пропускання Цифрових мереж з інтегрованими послугами (ISDN). У кожному з стандартів використовується схема кодування на основі дискретного косинусного перетворення (ДКП) з компенсацією руху. Здійснити оцінку руху по перетвореним данних складно, тому дана операція здійснюється в просторовій області. Блоки пікселів, називаються макроблоками, порівнюються з блоками попереднього кадру, знаходиться величина зсуву блоку, що забезпечує найменшу помилку пророкування, яка і є параметром компенсації руху. Помилка передбачення потім трансформується ДКП по блокам 8x8 пікслів, квантуєтся і кодується для передачі або зберігання.

Мультимедійні стандарти стиснення відеоданих для персоналізваного телебачення, цифрове широкомовне телебачення високої чіткості (ТВЧ), а також обслуговування баз даних зображень / відео використовують близькі методи оцінки руху і кодування. Три основні стандарти - MPEG-1, МРЕG-2 і МРЕG-4 були розроблені Групою Експертів по рухомих зображеннях (МРЕG), що діє під егідою ISO і МККТТ. МРЕG-1 є стандартом кодування «розважаючої якості», призначеного для запису та відтворення відеоданих на цифрові носії типу компакт-дисків (СD-RОМ); він забезпечує швидкість потоку даних близько 1,5 Мбіт/с. МРЕG-2 орієнтований на додатки, що вимагають телевізійного якості з рівнем між NTSC/PAL і CCIR 601 при швидкості передачі від 2 до 10 Мбіт/с. - даний параметр відповідає диапазону кабельного телебачення і вузькосмугових систем супутникової сигналізації. Метою як МРЕG-1, так і МРЕG-2 є забезпечення ефективності передачі та зберігання аудіо-і відеоданих (АВ). МРЕG-4, з іншого боку, забезпечує підвищення ефективності стиснення відеоданих; інтерактивність, засновану на зберіганні, наприклад, об'єктно-орієнтований доступ до АВ-об'єктам, або ефективну інтеграцію натурних і синтезованих даних, універсальний доступ, що допускає нестійко працююче обладнання, можливість додавати або видаляти АВ-об'єкти або міняти масштаби розширення об'єктів. Хоча подібні функціональні можливості і призводять до необхідності сегментації відеоданих на об'єкти довільного виду, тим не менш, сегментація як така не є частиною стандарту. Значна частина відеоданих (наприклад, комп'ютерні ігри) виготовляється і легкодоступна у формі відео об'єктів. МРЕВ-4 націлений на швидкості передачі від 5 до 64 Кбіт / с. для мобільних і Комутованих телефонних мереж загального доступу (PSTN), а також на швидкості до 4 Мбіт / с. для передачі ТВ і фільмів. Крім того, він підтримує передачу як з постійною, так і зі змінною швидкостями кодування.

Також як і стандарти відеоконференцій ITU, стандарти МРЕG побудовані на основі гібридної блокової схеми ДІКМ/ДКП кодування. Він використовує надлишковості як всередині кадру, так і між сусідніми кадрами, одноманітність руху між кадрами, а також психофізичні властивості зорової системи людини. Входом кодера є масиви 8x8 пікселів, названі блоками зображення. Стандартами визначені також макроблоки розмірами 2x2 блоку зображення (тобто масиви з 16x16 пікселів) і так звані слайси - набори з послідовних неперекриваючих макроблоків. Для кольорового відео макроблок складається з чотирьох блоків яскравості, що позначаються від до , і двох блоків цветоразностей і

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

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

1. Основний або незалежний кадр (І-кадр). І-кадр кодується незалежно від всіх як попередніх, так і наступних кадрів відео послідовності. Із всіх трьох можливих типів кадрів він найбільш схожий на JPEG-кодоване зображення. Більш того , він є точкою відліку для побудові послідовності із Р- і В - кадрів. Наявність І - кадрів забезпечує вільний доступ до відео послідовності, легкість її змін, а також захист від поширення помилок передачі. Як результат, всі стандарти вимагають періодичного вставляння подібних кадрів в стислий кодовий потік.

2. Передбачений кадр (Р-кадр). Р-кадр є стисла різниця між поточним кадром і його пророкуванням, зробленим на основі попереднього I-або Р- кадру. Різниця формується у блоці обчислення різниці. Передбачення включає компенсацію руху, здійснювану зміщенням декодувати макроблоки в околиці своєї центральної точки, і обчисленням заходи кореляції (наприклад, суми квадратів різниць значень пікселів в пророкує зображенні і зрушеному макроблоків); ці операції показані в нижній частині схеми на Рис. 1.47. У дійсності процес пошуку оптимального передбачення часто проходить на більш точному рівні, ніж розмір одного елемента (наприклад, можливе зміщення макроблоку на 1/4 елемента), що вимагає здійснення інтерполяції значень елементів до обчислення заходів кореляції. Знайдений вектор руху потім кодується нерівномірним кодом і передається як частина загального кодованого потоку даних.

3. Двонаправлений кадр (В-кадр). В-кадр є стисла різниця між поточним кадром і його пророкуванням, заснованому на інтерполяції між попереднім I-або Р-кадром і наступним Р-кадром. Відповідно, декодер повинен мати доступ як до попередніх за часом, так і до майбутніх опорних кадрам. Для цього кодуються кадри перед передачею переставляється, так, що на вхід декодеру вони надходять в потрібному для декодування порядку; потім декодер відновлює початкову послідовність кадрів.

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



Висновок

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



Посилання та література для подальшого вивчення

1. С.М. Клименко, О.С. Дуброва Стандарти стиснення зображень: Навч. пос. К.: КНЕУ, 2005

2. С.Ф. Покропивний, С.М. Соболь, Г.О. Швиданенко Бізнес-план: технологія розробки та обґрунтування: Навч. пос. - К.: КНЕУ, 1999. - 208 с.

3. С.Ф. Покропивний, С.М. Соболь, Г.О. Швиданенко, Л.М. Шапринська Моделі стиснення зображень : Навч. метод. Посібник для самост. вивч. диск. К.: КНЕУ, 2001. - 160 с.

4. Л.Г. Агафонова, О.В. Рога Підготовка плану: Практикум. - 3-тє вид., стер. К.: Т-во „Знання”, КОО, 2001. - 158 с.

5. Тєлєтов О. С. Елементи теорії інформації: Підручник. -- : К.: Центр навчальної літератури, 2004. -- 248 с.

6. Покропивний С.Ф. Графіка. - 2-ге, переробл. та доп. - К.: КНЕУ, 2001. - 528 с., іл.

7. Т.О. Примак «СТИСНЕННЯ ЗОБРАЖЕНЬ» : Навч.посібник.

Размещено на Allbest.ur