Застосування теорії інформації

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

Приклад 1.10. Обчислення ентропії зображення.

Розглянемо питання оцінювання інформаційного змісту (тобто ентропії) простого 8-бітового зображення:

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

Один відносно простий підхід полягає в тому, що можна припустити деяку конкретну модель джерела і обчислити ентропію зображення, базуючись на цій моделі. Наприклад, можна припустити, що зображення було отримано уявним «8-бітовим напівтоновим джерелом», який послідовно породжує статистично незалежні пікселі згідно якомусь заздалегідь заданому імовірнісному законом. При цьому необхідно, щоб символи джерела були рівнями яскравості, а алфавіт джерела складався з 256 можливих символів. Якщо ймовірності символів відомі, то середній інформаційний зміст зображення (ентропія) кожного елемента зображення може бути обчислена безпосередньо за допомогою виразу (1.3-3). Наприклад, у випадку одномірної щільності ймовірностей, символи джерела рівноймовірно і джерело характеризується ентропією 8 біт/елемент. Тобто кількістю інформації на символ джерела (елемент зображення) складе 8 біт. Тоді повна ентропія наведеного вище зображення складе 256 бітів. Це конкретне зображення є тільки одне з можливих рівноймовірно зображень розмірами 4 8 пікселів, які можуть бути породжені обраним джерелом.

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

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

Для даного прикладу оцінка першого порядку складе 1,81 біт/елемент. Таким чином, Ентропія джерела складе приблизно 1,81 біт/елемент, а всього зображення - 58 бітів.

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

Отримана оцінка ентропії (знову-таки, за допомогою (1.3-3)) складає 2,5 / 2 = 1,25 біт/елемент, де поділ на 2 є наслідком розгляду двох пікселів одночасно. Ця оцінка називається оцінкою другого порядку ентропії джерела, оскільки вона отримана обчисленням відносних частот двохелементний блоків. Хоча оцінки третього, четвертого, і більш високих порядків забезпечили б ще краще наближення ентропії джерела, збіжність цих оцінок до істинної ентропії джерела повільна, а їх обчислення складно. Наприклад, звичайне 8-бітове зображення містить можливих пар значень, відносні частоти яких повинні бути визначені. Якщо розглядаються блоки з 5 елементів, то значення можливих груп з п'яти значень складе , або ~ .

Хоча знаходження істинної ентропії зображення достатньо за труднітельно, тим не менш, оцінки, подібні розглянутим у попередніх прикладах, допомагають у розумінні можливостей стиснення зображения. Наприклад, оцінка першого порядку ентропії дає нижню межу для стиснення, якого можна досягти застосуванням одного тільки коду змінної довжини. (Згадаймо з Розділу 1.1.1, що коди змінної довжини використовуються для скорочення кодової надлишковості.) Крім того, відмінності між оцінками ентропії першого і більш високих порядків вказують на наявність або відсутність міжелементної надмірності; тобто вони показують, чи є елементи зображення статистично незалежними. Якщо елементи виявляються стастатистично незалежні (що означає відсутність міжелементних надмірності), то тоді оцінки високих порядків ентропії еквівалентні оцінкам першого порядку, а значить, нерівномірне кодування забезпечує оптимальне стиснення. Для зображення, розглянутого в попередньому прикладі, чисельна різниця між оцінками ентропії першого і другого порядків показує, що може бути побудоване таке відображення, яке дозволить додатково скоротити представлення зображення на 1,81 - 1,25 = 0,56 біт/елемент.

Приклад 1.11. Застосування відображення для зменшення ентропії.

Розглянемо відображення елементів зображення, наведеного в попередньому прикладі, яке представляє зображення наступним чином:

21 0 0 74 74 74 0 0

21 0 0 74 74 74 0 0

21 0 0 74 74 74 0 0

21 0 0 74 74 74 0 0

Сформований тут різницевий масив отриманий за допомогою першого стовпця вихідного зображення і використанням значень різниць сусідніх стовпців для інших елементів. Наприклад, другий елемент у першому рядку отриманий як (21 - 21) = 0. Статистика різницевого зображення наступна:

Якщо тепер розглядати отриманий масив як породжений «різницевим джерелом», то для визначення оцінки першого порядку ентропії можна знову скористатися формулою (1.3-3). Результатом буде 1,41 біт/елемент. Це означає, що якщо кодувати отримане різницеве ​​зображення способом нерівномірного кодування, вихідне зображення може бути представлене з допомогою 1,41 біт/елемент, або близько 46 бітів. Це значення більше, ніж оцінка другого порядку ентропії, отримана в попередньому прикладі і рівна 1,25 біт/елемент. Тим самим ясно, що може бути знайдений більш ефективний спосіб відображення.

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

Із застосуванням засобів теорії інформації може також вирішуватися і кілька більш складних завдань - стиснення зображення з втратами. У цьому випадку, однак, найважливішим результатом є теорема кодування джерела. Як показано в Розділі 1.3.3, ця теорема стверджує, що будь-яке джерело без пам'яті може бути закодований за допомогою коду, що має швидкість , такого, що середнє спотворення на символ не перевищує . Щоб правильно застосувати цей результат до стисненню зображень з втратами, потрібно розробити підходящу модель джерела, вибір адекватної міри спотворень, а також обчислення відповідної швидкості як функції спотворень . Перший крок цієї процедури вже був розглянутий. На другому кроці можливий підхід на основі використання об'єктивного критерія якості з Розділу 1.1.4. Заключний крок стосується відшукання матриці Q, елементи якої мінімізують висловлювання (1.3-12) при обмеженнях, що накладаються умовами (1.3-24) - (1.3-28). На жаль, дана задача особливо важка, і може бути вирішена лише в невеликому числі практичних випадків. Одним з таких є випадок, коли зображення являє собою гауссову випадкову величину, а міра спотворення є функція середньоквадратичної помилки. Тоді оптимальний кодер повинен перетворювати зображення за методом головних компонент і представити кожну компоненту з однаковою середньоквадратичною помилкою.

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