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

ГЛАВА 1

СТИСНЕННЯ ЗОБРАЖЕНЬ

Введення

Кожен день величезна кількість інформації запам'ятовується, перетворюється і передається в цифровому вигляді. Фірми постачають через Інтернет своїх ділових партнерів, інвесторів і потенційних покупців річними звітами, каталогами та інформацією про товари. Введення і спостереження розпоряджень - дві основні електронні банківські операції - можуть виконуватися в комфортних умовах прямо зламу. Як частина урядової програми інформатизації в США сформовано повний каталог (а також засоби для його підтримки і зберігання) Бібліотекі Конгресу - найбільшої в світі бібліотеки, доступної по мережі Інтернет. Ось-ось стане реальністю складання персональної програми кабельного телебачення за замовленням користувачів. Відповідно значна частина переданих даних при цьому є по суті графічній або відеоінформацією, вимоги до пристроїв зберігання і засобів зв'язку стають величезними. Таким чином, значний практичний і комерційний інтерес набувають засоби стиснення даних для їх передачі або зберігання.

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

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

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

У цьому розділі розглядаються теоретичні та практичні аспекти стиснення зображень. Розділи 1.1-1.3 є введенням і складають теоретичні основи даної дисципліни. В розділі 1.1 розглядається надмірність даних, яка може використовуватися алгоритмами стиснення зображень. У розділі 1.2 на базі моделі вводиться система понять, що використовуються в загальній процедурі стиснення-відновлення. У розділі 1.3 в деталях розглядаються основні поняття теорії інформації та їх роль у визначенні фундаментальних меж представлення інформації.

Розділи 1.4-1.6 присвячені практичній стороні питання стиснення зображень, включаючи як найважливіші використовувані методи, так і прийняті стандарти, які стимулювали розширення меж і сприяли визнанню даної дисципліни. Методи поділяються на дві великі категорії: методи стиснення без втрат і методи стиснення з втратами. Розділ 1.4 присвячений методам першої групи, які, зокрема, корисні при архівації зображень. Ці методи гарантують стиск і відновлення зображень без якого б то не було спотворення інформації. У розділі 1.5 описуються методи другої групи, що дозволяють досягти більш високого рівня об’єднання даних, але не забезпечують абсолютно точного відтворення вихідного зображення. Стиснення зображень з втратами знаходить застосування в таких областях як широкомовне телебачення, відеоконференції і факсимільні передачі, в яких деяка кількість помилок є прийнятним компромісом, що дозволяє підвищити ступінь стиснення. Нарешті, розділ 1.6 присячений розгляду існуючих і пропонованих стандартів стиснення зображень.

Основи

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

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

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

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

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

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

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

Припустимо, що дискретна випадкова змінна , розподілена в інтервалі [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) і з'являється кодова надмірність.

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