1.1. Основи

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

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

де величина зазвичай називається коефіцієнтом стиснення, є

У разі, коли , отримаємо: і , що говорить про те, що перший спосіб подання інформації не містить надлишкових даних у порівнянні з другим. Якщо , то і , що означає значне стискання та високу надмірність даних першого набору по відношенню до другого. Нарешті, якщо , то і , і означає, що другий набір містить багато надлишкових даних в порівнянні з першим. Як правило, таке збільшення кількості даних є небажаним. Взагалі, значення і знаходяться всередині відкритих інтервалів і , відповідно. На практиці, коефіцієнт стиснення, такий як 10 (або 10:1), означає, що перший набір даних (в середньому) містить 10 одиниць зберігання інформації (скажімо, біт) на кожну одну одиницю другого (тобто стисненого) набору даних. Відповідне цьому значення надмірності 0,9 і означає, що 90% даних першого набору є надлишковими.

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

1.1.1. Кодова надмірність

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

Припустимо, що дискретна випадкова змінна , розподілена в інтервалі [0, 1], являє значення яскравості зображення, і що кожне значення з'являється з імовірністю .

де - загальне число рівнів яскравості, - кількість пікселів, що має значення яскравості , а - загальне число елементів в зображенні. Якщо число бітів, використовуваних для представлення ожного із значень , дорівнює , то середнє число бітів, необхідних для представлення значення одного елемента, дорівнює

Отже, середня довжина всіх кодових слів, привласнених різним значень яркостей, визначається як сума добутків числа бітів, використовуваних для представлення кожного з рівнів яркостей, на імовірність появи цього рівня яскравості. Таким чином, загальне число бітів, необхідну для кодування зображення розмірами , складе .

Подання рівня яскравості зображення звичайним -бітовим двійковим кодом спрощує праву частину рівняння (1.1-4). Коли замість підставляється , а сума по всіх дорівнює 1, то .

Приклад 8.1 Просте пояснення нерівномірного кодування.

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

Таблиця 1.1 Приклад нерівномірного кодування.

Відповідно до формули (1.1-2), результуючий коефіцієнт стиснення дорівнює 3/2, 7 або 1,11. Таким чином, при використанні Коду 1 біля 10% даних (у порівнянні з Кодом 2) є надлишковими. Точний рівень надмірності може бути обчислений згідно (1.1-1):

На Малюнку 1.1 проілюстрований принцип, що лежить в основі стиску, що досягається при використанні Коду 2. Суцільною лінією наведена гістограма зображення (залежність від ), а пунктирною - число використовуваних бітів . Оскільки із зменшенням значення зростає, то найбільш короткі кодові слова в Коді 2 присвоєні найбільш часто зустрічається рівням яскравості на зображенні.

Рис. 1.1. Графічне представлення принципу, що лежить в основі стиснення данних за допомогою нерівномірного кодування.

Як видно з попереднього прикладу, присвоєння кодових слів з меншим числом бітів більш імовірним значенням яскравості, і навпвки, більш довгих кодових слів менш імовірним значенням, дозволяє досягти стискування даних. Такий підхід називають нерівномірним кодуванням. Якщо значення яскравості зображення кодуються деяким способом, що вимагає більшого числа символів, ніж це суворо необхідно (тобто код не мінімізує рівняння (1.1-4)), то кажуть, що зображення має кодову надлишковість. Взагалі, кодова надмірність виникає завжди, коли при виборі кодових слів, що привласнюються подіям (наприклад, значеннях яскравості), знання про ймовірностях подій не використовується повною мірою. Коли значення яскравості зображення представляються звичайним або прямим двійковим кодом, це відбувається майже завжди. Підставою для виникнення кодової надмірності в цьому випадку є те, що зображення, як правило, складаються з об'єктів, що мають регулярну, в деякому розумінні передбачувану морфологію (форму) і дзеркальні властивості поверхні, причому розміри об'єктів на зображеннях зазвичай набагато перевищують розміри пікселів. Прямим наслідком цього є той факт, що на більшості зображень певні значення яскравості виявляються більш вірогідними, ніж інші (тобто гістограми більшості зображень не є рівномірними). Звичайне двійкове кодування значень яскравості таких зображень присвоює кодові слова однакової довжини як більш імовірним, так і менш ймовірним значенням. У результаті не забезпечується мінімізація рівняння (1.1 -4) і з'являється кодова надмірність.