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

Размещено на http://www.allbest.ru/

ДИПЛОМНА РОБОТА

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



ВСТУП

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

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

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

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

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

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



ГЛАВА 1 ОСНОВНА ЧАСТИНА

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) і з'являється кодова надмірність.

1.1.2 Міжелементна надмірність

Розглянемо зображення, представлені на Рис. 1.2 (а) і (б). Як показують Рис. 1.2 (в) і (г), ці зображення мають майже однакові гістограми. Зауважимо, що обидві гістограми містять по три явних піку. Це показує, що на зображенні є три домінуючих діапазону яркостей. Оскільки яскравості на зображення не є рівноімовірними, то для скорочення кодової надмірності, що виникає при прямому або звичайному двійковому кодуванні значень пікселів, можна скористатися нерівномірним кодуванням. Такий процес кодування, однак, не призведе до зміни кореляційних залежностей між елементами зображення. Іншими словами, кодування, використовуються для представлення значень яскравості, не може змінити кореляції між пікселями, яка є наслідком структурних або геометричних взаємозв'язків між об'єктами на зображені.

Графіки на Рис. 1.2 (д) і (е) суть відповідні коефіцієнти автокореляції , обчислені уздовж одного рядка кожного зображення. Ці коефіцієнти були отримані за допомогою нормалізованого варіанта рівняння

де

Нормувальні коефіцієнт в (1.1-6) враховує зміну числа елементів підсумовування, яке залежить від значення . Звичайно, значення повинно бути строго менше числа елементів в рядку. Значення змінної є номер рядка, використовуваної для обчислень. Звернемо увагу на істотні відмінності між графіками на Рис. 1.2 (д) і (е), які можуть бути якісно пов'язані зі структурами зображень (а) і (б). Цей зв'язок особливо помітний на Рис. 1.2 (е), де висока кореляція між значеннями пікселів, віддалених на 45 і 90 відліків, може бути прямо пов'язана з відстанями між вертикально орієнтованими спічками на Рис. 1.2 (6). Крім того, сильно корельованими виявляються значення суміжних пікселів: при , для зображення (а) і для зображення (б). Ці значення є типовими для більшості правильно оцифрованих телевізійних зображень.

кодер стиснення декодер бітовий



Рис. 1.2 Два зображення, гістограми значень їх яскравості і нормалізовані коефіцієнти автокореляції уздовж однієї із рядків

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

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

Приклад 1.2 Просте пояснення до кодування довжин серій.

На Рисунку 1.3 показана проста процедура відображення. На Рис. 1.3 (а) зображений ділянку монтажної схеми електронного пристроя, оцифрований з дозволом приблизно 13 ліній / мм. (330 dpi). На Рис. 1.3 (6) дане зображення представлене в двох градаційному варіанті, а графік на Рис. 1.3 (в) показує профіль яскравості уздовж деякого рядка зображення і рівень порогу бінарності. Оскільки на двохградаційному зображенні міститься багато областей з постійними значеннями, то більш ефективним поданням може бути перетворення значень елементів уздовж рядка в набір наступних пар: тут означает значення яскравості на відрізку (серії) - довжину даної серії.

Координата по горизонталі

Рис. 1.3 Малюнок до кодування довжини серії

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

Для представлення 1024 біт вихідних двохградаційних даних виявилося достатньо всього 88 біт. В цілому ж, весь наведений фрагмент розмірами 1024x343 елемента може бути представлений у вигляді 12166 серій.

На запис однієї серії використовувалося 11 біт, таким чином результуючий коефіцієнт стиснення і відповідна відносна надмірність складають

1.1.3 Візуальна надмірність

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

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

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

Приклад 1.3. Стиснення допомогою квантування.

Я Розглянемо зображення на Рис. 1.4. На Рис. 1.4 (а) представлено чорно-біле зображення з 256 можливими градаціями яскравості. На Рис. 1.4 (6) показано те ж саме зображення після рівномірного квантування на 16 рівнів (4 біта). Отриманий в результаті коефіцієнт стиснення дорівнює 2:1. Зауважимо, що на гладких областях вихідного зображення з'явилися помилкові контури; це звичайний видимий ефект занадто грубого представлення рівнів яркостей зображення.

а) б) в)

Рис. 1.4 (а) Початкове зображення. (6) Рівномірне квантування на 16 рівнів. (в) Метод модифікованого квантування яскравості на 16 рівнів

Можна відзначити значне покращення зображення на Рис. 1.4 (в), що стало можливим при використанні квантування, базованих на особливостях зорової системи людини. Незважаючи на те, що коефіцієнт стиснення при другому способі квантування теж рівний 2:1, помилкові контури значно ослаблені; однак при цьому з'явилася деяка додаткова, хоча і мало помітна зернистість. Для отримання даного результату був використаний так названий метод модифікованого квантування яскравості (МКЯ). Він враховує властиву оці чутливість до контурів і руйнує помилкові контури шляхом додавання до значення кожного елементу перед його квантуванням невеликий квазівипадкової величини, генеруємої на підставі значень молодших бітів сусідніх елементів. Оскільки молодші біти, як правило, досить випадкові, це еквівалентно додаванням деякого рівня випадковості, залежного від локальних характеристик зображення, і тим самим призводить до руйнування чіткості виникають перепадів, що виглядають як помилкові контури. Даний метод пояснюється Таблицею 1.2. Значення суми - спочатку рівне нулю - формується шляхом складання поточного 8-бітового значення яскравості і чотирьох молодших розрядів раніше отриманої суми. Однак якщо старші чотири розряду значення елемента вже були рівні 1111, то перенесення одиниці з молодших розрядів в старші блокіруется. Чотири старших біта отриманої суми використовуються в якості результату квантування (кодування) значення елемента.

Таблиця 1.2 Ілюстрація методу модифікованого квантування яскравості(МКЯ)

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

1.1.4 Критерії вірності відтворення

Як зазначалося раніше, скорочення візуальної надмірності спричиняє втрату реальної кількісної візуальної інформації. Оскільки при цьому може бути також загублена і представляє інтерес інформація, то дуже бажано мати засоби кількісних оцінок характеру і величини втрат інформації. В основу такого визначення можуть бути покладені як об'єктивні, так і суб'єктивні критерії вірності (точності) відтворення.

Якщо ступінь втрати інформації може бути виражена як функція вихідного (вхідного) зображення і стиснутого, а потім відновленого (вихідного) зображення, то такий підхід називають об'єктивним критерієм вірності відтворення.

Гарним прикладом тут є критерій середньоквадратичного відхилення (СКВ) різниці вихідного і вхідного зображень. Нехай означає вхідне зображення, а - його наближення, одержуване в результаті операцій стиснення і подальшого відновлення. Для будь-яких і помилка (нев'язка) для елементів зображень і визначається як

а величина повної нев'язки двох зображень дорівнює

де розміри зображення рівні . Величина середньоквадратичного відхилення еск0 різниці зображень і буде дорівнює

Іншим близьким об'єктивним критерієм вірності відтворення є відношення сигнал-шум стисненого - відновленого зображення. Якщо за допомогою простої перестановки членів у виразі (1.1-7) розглядати зображення як суму початкового зображення і шуму , то середній квадрат відносини сигнал-шум вихідного зображення, що позначається , буде дорівнювати

Відношення сигнал-шум, позначуване, виходить витягом квадратного кореня з правої частини виразу (1.1-9).

Хоча об'єктивні критерії вірності відтворення пропонують простий і зручний механізм оцінки інформаційних втрат, все-таки більшість відновлених зображень, врешті-решт, розглядаються людиною. Отже, визначення якості зображення за допомогою суб'єктивного оцінювання часто є кращим. Це може бути досягнуто шляхом показу «типового» відновленого зображення групі спостерігачів (експертів) і усереднення їх оцінок. Оцінювання може вироблятися як з використанням абсолютної шкали оцінок, так і шляхом попарного порівняння зображень і . У Таблиці 1.3 наведений один з можливих варіантів абсолютної шкали оцінювання. Попарні порівняння з використанням такої шкали можуть бути сформовані, наприклад, у вигляді набору наступних чисел: {-3, -2, -1,0,1,2.3}, що відображає, відповідно, суб'єктивні оцінки рейтингу: {значно гірше, гірше , злегка гірше, однаково, злегка краще, краще, значно краще}. У будь-якому випадку ці оцінки засновані на суб'єктивних критеріях вірності відтворення.

Приклад 8.4. Порівняння оцінок якості зображень.

Оцінки середньоквадратичних відхилень (1.1-8) зображень на Рис. 1.4 (6) і (в) від оригіналу (а) складають 6,93 і 6,78 градацій яскравості. Аналогічні оцінки відносин сигнал-шум () дорівнюють відповідно 10,25 і 10,39. Хоча ці значення досить близькі, суб'єктів незалежні оцінки візуальної якості двох вищевказаних зображення складають «погано» для зображення на Рис. 1.4 (6) і «приймемо» для зображення на Рис. 1.4 (в).

Таблиця 1.3 Шкала оцінок якості зображень. (Організація з дослідження класифікацій в телебаченні)

1.2 Моделі стиснення зображень

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

Як видно з Рис. 1.5, система стиснення містить два принципово різних структурних блоку: кодер і декодер. Початкове зображення подається на кодер, який перетворить вхідні дані в набір символів. Після передачі по каналу кодовані дані потрапляють на декодер, де створюється відновлене зображення . Взагалі, зображення може бути точною копією зображення , а може такий і не бути.

Рис. 1.5 Загальна модель системи стиснення

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

Як кодер, так і декодер, показані на Рис. 1.5, складаються з двох досить незалежних блоків. Кодер містить кодер джерела, кодування усуває надмірність джерела (вхідного сигналу), і кодер каналу, який збільшує перешкодостійкість сигналу на вихідні кодера каналу. Як легко припустити, декодер містить декодер каналу, за яким слідує декодер джерела. Якщо канал між кодером і декодером є каналом без перешкод (тобто в ньому не виникає помилок), то кодер каналу і декодер каналу можуть був відсутній ¬ вати, і тоді колер і декодер будуть містити, відповідно, тільки кодер джерела і декодер джерела.

1.2.1 Кодер і декодер джерела

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

а) Кодер джерела

б) Декодер джерела

Рис. 1.6 (а) Модель кодера джерела, (б) Модель декодера джерела

На першій стадії процесу кодування джерела перетворювач перетворює вхідні дані, тобто зображення, у формат (звичайно не візуальний), призначений для скорочення межелементної надмірності вхідного зображення. Як правило, дана операція оборотна, і, в принципі, може як скорочувати, так і збільшує обсяг даних, необхідний для представлення зображення. Кодування довжин серій (Розділи 1.1.2 та 1.4.3) є прикладом перетворення, яке прямо призводить до скорочення обсягу даних на даній початковій стадії загальної процедури кодування джерела. Представлення зображення за допомогою набору коефіцієнта перетворення (Розділ 1.5.2) є прикладом протилежній ситуації. У цьому випадку перетворювач перетворює зображення в деякий масив коефіцієнтів з визначеними статистичними характеристиками, завдяки чому міжелементна надмірність може бути вилучена на більш пізній стадії процедури кодування.

Друга стадія, або блок квантувач на Рис. 1.6(а), зменшує точність виходу перетворювача у відповідності з деяким попередньо заданим критерієм вірності. На цій стадії скорочується візуальна надмірність вхідного зображення. Як зазначалось у Розділі 1.1.3, ця операція є незворотною, а значить повинна бути пропущена, якщо потрібно стиснення без втрат.

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

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

Схема декодера джерела, представлена ??на Рис. 1.6 (6), має лише два блоки: блок декодера символів і блок зворотного перетворювача. Ці блоки здійснюють операції, зворотні тим операціям, які виконувалися в кодері джерела блоками кодера символів і перетворювача, причому в зворотному порядку. Оскільки операція квантування незворотна, то блок «зворотного квантователя» на Рис. 1.6 (6) відсутня.

1.2.2 Кодер і декодер каналу

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

Один з найбільш фундаментальних і корисних способів кодування каналу був розроблений Р.В. Хеммінга [Натгшпе, 1950]. Він базується на додаванні до переданих даним деякого числа бітів, які гарантують, що допустимі кодові слова будуть відрізнятися не менш ніж у заданому числі позицій (двійкових розрядів, бітів). Хеммінг показав, наприклад, що якщо 4-бітове кодове слово розширити трьома додатковими бітами (перевірочними символами) так,щоб відстань між будь-якими двома допустимими кодовими словами стало не менш ніж 3, то будь-які одиничні помилки (в будь однією позиції будь-якого слова) можуть бути виявлені і виправлені. Додавання більшої кількості перевірочних бітів дозволяє виявляти і виправляти помилки в декількох позиціях одночасно.

Розглянемо 7-бітовий код Хеммінга, що складається з кодових слів виду , асоційований з безліччю 4-бітових двійкових чисел :

де знак означає операцію виключає АБО. Зауважимо, що біти , і суть біти парності для наборів бітів і відповідно. (Нагадаємо, що двійкова рядок є парною, якщо містить парне число бітів зі значенням 1).

При декодуванні декодер каналу повинен перевірити на парність бітові позиції отриманого розширеного кодового слова. Це здійснюється наступними операціями:

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

Приклад 8.5. Кодування по Хеммінга.

Розглянемо передачу 4-бітових значень яскравості, наприклад, отриманих за допомогою алгоритму модифікованого квантування яскравості (МКЯ) - див. Таблицю 1.2, по каналу зв'язку з шумом. Помилка в єдиному біті може призвести до зміни правильного значення сигналу на 128 градацій яскравості. Для підвищення стійкості до шуму і щоб забезпечити виявлення і усунення одиночних помилок, кодер каналу може використовувати код Хеммінга, що потребує деякого збільшення надмірності. Згідно рівнянням (1.2-1), після кодування по Хеммінга перше значення МКЯ з Таблиці 1.2 буде однаково 1100110. Оскільки код Хеммінга збільшує число біт, необхідних для передачі значення МКЯ, з 4 до 7, то коефіцієнт стиснення 2:1, який був раніше досягнутий за рахунок використання методу МКЯ, зменшиться до 8/7 або 1,14:1 . Таке зменшення результуючого коефіцієнта стиснення є та ціна, яку доводиться платити за підвищення перешкодозахищеності.

1.3 Елементи теорії інформації

У Розділі 1.1 було представлено декілька шляхів зменшення обсягів об'ємних даних, необхідних для представлення зображення. Природно виникає наступне питання: наскільки багато даних в дійсності необхідно для представлення зображення? Іншими словами, чи існує мінімальна кількість даних, яких потрібно для повного опису зображення без втрат інформації? Теорія інформації дає математичну основу для відповіді на це та близькі йому запитання.

1.3.1 Вимірювання інформації

Фундаментальна передумова теорії інформації полягає в тому, що джерело інформації може бути описаний як імовірнісний процес, який може бути вимірюваними природним чином. У відності з цим припущенням кажуть, що випадкова подія Е, що з'являється з імовірністю Р(Е), містить одиниць інформації.

Значення Р(Е) часто називають кількістю інформації в подію Е. Взагалі кажучи, приписуване події Е кількості інформації тим більше, чим менше ймовірність Е. Якщо Р(Е) = 1 (тобто подія виникає завжди), то І(Е) = 0 і даним обставинам не приписують ніякої інформації. Це означає, що немає ніякої невизначеності, пов'язаної з подією, то повідомлення про те, що дана подія сталася, не несе ніякої інформації. Однак, якщо Р(Е)=0,99, то повідомлення про те, що Е сталося, вже передає якийсь невелика кількість інформації. Повідомлення ж, що Е не відбулося, передає істотно більше інформації, оскільки ця подія значно рідше.

Підстава логарифма в (1.3-1) задає одиницю виміру кількості інформації. Якщо використовується підставу m, то говорять про одиниці вимірювання по підставі m. Коли основа дорівнює 2, одиниця інформації називається біт. Зауважимо, що якщо Р (Е) = 1/2, то , або одному біту. Таким чином, біт є кількість інформації, що передається повідомленням про те, що сталося одне з двох можливих рівноймовірно подій. Простий приклад повідомлення такого роду - повідомлення про результат підкидання монети.

1.3.2 Канал передачі інформації

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

Рис. 1.7.Проста система передачі інформації

Припустимо, що джерело інформації на Рис. 1.7 генерує випадкову послідовність символів з кінцевого або рахункового набору можливих символів, тобто вихід джерела є дискретна випадкова величина. Набір вихідних символів називають алфавітом джерела А, а елементи набору - символами або літерами. Імовірність того, що джерело породжує символ дорівнює , причому

Для опису сукупності ймовірностей символів джерела зазвичай використовується J-мірний вектор ймовірностей . Тим самим джерело інформації повністю описується кінцевим ансамблем повідомлень (А, z).

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

Середня кількість інформації, що припадає на один символ джерела і позначуване , одно

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

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

Імовірність виходу даного каналу і розподіл імовірності джерела z пов'язані наступним виразом

де є умовна ймовірність, тобто ймовірність отримати на виході символ , за тієї умови, що на вхід був поданий символ .

Якщо умовні ймовірності, що входять у вираз (1.3-4), записати в вигляді матриці Q розмірами , так що

тоді розподіл ймовірностей вихідних символів каналу може бути записано в матричній формі

Матрицю Q з елементами називають матрицею перехідних ймовірностей каналу, або, в скороченому вигляді, матрицею каналу.

Щоб визначити пропускну здатність каналу з прямою матрицею переходів Q, спочатку необхідно обчислити ентропію джерела інформації в припущенні, що одержувач спостерігає на виході деякий символ . Для будь-якого спостережуваного рівняння (1.3-4) задає розподіл ймовірностей на множині символів джерела, так що для кожного є своя умовна ентропія, представлена у вигляді . За допомогою послідовності кроків, використовуваних при виводі рівняння (1.3-3), умовна ентропія може бути записана в наступному вигляді

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

яке, після підстановки рівняння (1.3-7) для і нескладних подібних перетворень може бути записано в наступному вигляді

Тут є спільна ймовірність і , тобто ймовірність того, що був переданий символ і був отриманий символ .

Величину називають умовною ентропією або невизначеністю величини z щодо величини v. Вона являє середнє кількість інформації на один символ джерела, за умови спостереження конкретного вихідного символу. Оскільки - cередня кількість інформації на один символ без припущення при отриманому вихідному символі, то різниця між і є середня кількість інформації, що отримується при спостереженні одного вихідного символу. Ця різниця, що позначається і називається середньою взаємною інформацією z і v, дорівнює

Підставляючи вирази (1.3-3) та (1.3-9) для і в (1.3-10), і згадуючи, що , отримуємо

після подальших перетворень цей вираз може бути переписано у вигляді

Таким чином, середня кількість інформації, що отримується при спостереженні одного символу на виході каналу, залежить від розподілення ймовірностей джерела (вектора z) і матриці каналу Q. Мінімальнt можливе значення дорівнює нулю і досягається тоді, коли вхідні і вихідні символи виявляються статистично незалежними, тобто у разі, коли : при цьому логарифмічні члени в правій частині (1.3-11) дорівнюють нулю для всіх значень j і k. Максимальне значення по всіх можливих виборам розподілу z джерела є пропускна здатність С каналу, описуваного матрицею каналу Q. Таким чином

,

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

Приклад 8.6. Двійковий випадок.

Розглянемо двійковий джерело інформації з вихідним алфавітом . Ймовірності породження символів джерелом дорівнюють і , відповідно. Згідно (1.3-3), ентропія джерела дорівнює

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

Тепер припустимо, що інформація повинна передаватися за допомогою бінарного інформаційного каналу з шумом, і нехай ймовірність помилки при передачі будь-якого символу дорівнює . Такий канал називається двійковим симетричним каналом (ДСК) і визначається наступною матрицею каналу:

Для кожного вступника на вхід символу ДСК породжує один символ Ьу з алфавіту каналу Ймовірності отримання на виході символів і можуть бути визначені з (1.3-6):

Оскільки , отже, ймовірність того, що на виході буде символ 0, дорівнює , а ймовірність того, що на виході буде символ 1 , дорівнює .

Тепер з (1.3-12) може бути обчислена середня взаємна інформація для ДСК. Розкриваючи знак підсумовування в цьому рівнянні, і збираючи разом відповідні члени, отримаємо в результаті:

а) б) в)

Рис. 1.8. Три функції двійкової інформації: (а) Двійкова функція ентропії. (б) Середня взаємна інформація двійкового симетричного каналу (ДСК). (в) Пропускна здатність ДСК

,

де є двійкова функція ентропії, показана на Рис. 1.8 (а). Якщо значення помилки каналу фіксоване, то при і . Більш того, приймає максимальне значення, коли символи двійкового джерела рівноймовірні. На Рис. 1.8 (6) представлена залежність від при фіксованому значенні помилки каналу .

Згідно рівнянню (1.3-13), пропускна здатність ДСК визначається як максимум середньої взаємної інформації по всіх утворюючим розподілам джерела. На Рис. 1.8 (6) наведено графік для всіх можливих розподілів двійкового джерела (тобто для , або для всіх значень від до ). Можна побачити, що для будь-якого максимум досягається при = 1/2. Це значення відповідає вектору розподілів символів двійкового джерела . При цьому значення буде рівно . Таким чином, пропускна здатність ДСК, зображена на Рис. 1.8 (в) дорівнює

.

Зауважимо, що якщо в каналі немає помилок ( = 0), так само як якщо помилка є завжди ( = 1), пропускна здатність каналу досягає свого максимального значення, рівного 1 біт/символ. В обох випадках можлива максимальна передача інформації, оскільки вихід каналу абсолютно передбачуваний. Однак, якщо , то вихід каналу повністю непередбачуваний і передача інформації через нього неможлива.

1.3.3 Основні теореми кодування

Загальні математичні принципи, викладені в Розділі 1.3.2, базуються на моделі системи передачі інформації, схема якої приведена на Рис. 1.7, і складається з джерела інформації, каналу та одержувача. У даному розділі в цю схему буде додана система зв'язку, і будуть розглянуті три основні теореми кодування, або подання, інформації. Як показано на Рис. 1.9, система зв'язку розміщена між джерелом і одержувачем, і складається з кодера і декодера, з'єднаних каналом зв'язку.

Терема кодування для каналу без шуму

Коли і інформаційний канал, і система зв'язку вільні від помилок, то основна роль останньої повинна зводитися до подання джерела в максимально компактній формі.

Рис. 1.9 Модель системи передачі інформації

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

Джерело інформації з кінцевим ансамблем повідомлень (А,z) і статистично незалежними символами джерела, називається джерелом без пам'яті. Якщо виходом джерела є не один символ, а послідовність з n символів алфавіту, то можна вважати, що вихід джерела приймає одне з можливих значень, позначуваних з повного набору можливих послідовностей в n елементів: . Іншими словами, кожен блок , називається блоковою випадковою змінною, складається з n символів алфавіту A. (Позначення дозволяє відрізняти набір блоків від набору символів алфавіту A.) Імовірність окремого блоку , дорівнює і пов'язана з імовірностями окремих символів наступним співвідношенням

де індекси використовуються для вказівки n символів алфавіту А, складових блок . Як і раніше, вектор (штрих означає, що використовується блокова випадкова змінна) позначає сукупне розподіл ймовірностей , і ентропія джерела дорівнює

Підставляючи (1.3-14) для і спрощуючи вираз, отримаємо

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

Оскільки кількість інформації на виході джерела , є перші , розумним представляється кодування , за допомогою кодових слів довжини, де l-ціле число, таке що

Інтуїція підказує, що вихід джерела , повинен бути представлений кодовим словом, довжина якого є найближче ціле, превищує кількість інформації в . Множення (1.3-16) на і підсумовування по всіх , дає

або

де означає середню довжину кодового слова, яке відповідає n-кратному розширенню нерозширення джерела, тобто

Розділивши (1.3-17) на n, і враховуючи, що , отримаємо нерівність:

, (1.3-19)

яке перетворюється в граничному випадку в рівність

(1.3-20)

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

Оскільки є точною нижньою гранню для вираження (цей вираз, згідно (1.3-20), прагне до при збільшенні ), то ефективність будь-якої стратегії кодування може бути виражена наступною формулою

Приклад 1.7. Кодування з розширенням.

Джерело інформації без пам'яті з алфавітом має ймовірності символів і . Згідно (1.3-3), ентропія цього джерела дорівнює 0,918 біт/символ. Якщо символи і представлені однобітових кодовими словами 0 і 1, то біт/символ і результуюча ефективність кодування дорівнює , або 0,918.

У Таблиці 1.4 містяться і тільки що розглянутий код, і альтернативний спосіб кодування, заснований на двократному розширення джерела. У нижній частині таблиці наведені чотири блокових символу (), відповідних другому варіанту. Як випливає з (1.3-14), їх ймовірності рівні 4/9, 2/9, 2/9 і 1/9. Відповідно (1.3-18), середня довжина кодового слова при цьому буде дорівнює 17/9 = 1,89 біт/символ. Ентропія при двократному розширенні джерела дорівнює подвоєною ентропії нерозширення джерела, тобто 1,83 біт/символ, так що ефективність при другому варіанті кодування складе = 1,83 / 1,89 = 0,97.

Таблиця 1.4 Приклад кодування з розширенням

Це дещо краще, ніж ефективність нерозширення джерела, яка дорівнює 0,92. Як легко бачити, кодування дворазового розширення джерела скорочує середнє число бітів кодової послідовності на один символ джерела з 1 біт/символ до 1,89 / 2 = 0,94 біт/символ.

Теорема кодування для каналу з шумом

Якщо канал, зображений на Рис. 1.9 є каналом із шумом (тобто в ньому можливі помилки), то інтерес зміщується від завдання представлення інформації максимально компактним методом до задачі її кодування таким чином, щоб досягти максимально можливої надійності зв'язку. Питання, яке природно виникає, звучить наступним чином: наскільки можна зменшити помилки, утворені в каналі?

Приклад 1.8. Двійковий канал з шумом.

Припустимо, що ДСК має ймовірність помилки = 0,01 (тобто 99% всіх символів джерела передаються через канал правильно). Простий спосіб збільшення надійності зв'язку полягає в повторенні кожного повідомлення або кожного двійкового символу кілька разів. Наприклад, припустимо, що замість передачі одного символу 0 або 1, використовується кодове повідомлення 000 або 111. Імовірність того, що під час передачі трьохсимвольного повідомлення не виникне помилки, дорівнює , або Імовірність однієї помилки буде , двох , а ймовірність трьох помилок складе . Оскільки імовірність помилки при передачі одного символу становить менше 50%, то одержуване повідомлення може бути декодовано методом голосування трьох отриманих символів. Вірогідність невірного декодування трьохсимвольного кодового слова дорівнює сумі імовірностей помилок в двох символах і в трьох символах, тобто . Якщо ж у слові немає помилок, або всього одна помилка, то воно буде декодовано вірно. Таким чином, для = 0,01 ймовірність помилки при передачі зменшилася до значення 0,0003.

Розширюючи тільки що описану схему повторення, можна досягти як завгодно малої результуючої помилки передачі. У загальному випадку, це здійснюється кодуванням n-кратного розширення джерела при використанні K-символьної кодової послідовності довжини r, де . Ключовим питанням при такому підході є вибір в якості допустимих кодових слів тільки деякого числа з можливих кодових послідовностей, а також формулювання вирішального правила, оптимізуючого ймовірність правильного декодування. У попередньому прикладі, повторення кожного символу джерела три рази еквівалентно кодуванню нерозширення двійкового джерела, використовуючого лише два з = 8 можливих кодових слів. Два допустимих коду - це 000 і 111. Якщо на декодер надходить якийсь інший (недопустимий) код, то вихід визначається голосуванням по більшості з трьох кодових бітів. Джерело інформації без пам'яті породжує інформацію зі швидкістю (в одиницях інформації на символ), рівної ентропії джерела . У разі n-кратного розширення, джерело створює інформацію зі швидкістю одиниць інформації на символ. Якщо інформація кодується так, як у попередньому прикладі, то максимальна швидкість кодованої інформації дорівнює , і вона досягається у випадку, коли всі допустимі кодові слова рівноймовірні. У такому випадку говорять, що код розміру і довжиною блоку має швидкість коду одиниць інформації на символ.