Ентропія

Наведені тут приклади вказують на те, що величина інформаційної ємності, що вимагається для представлення зображень, залежить від їх статистики (від розподілу ймовірностей, з якими зустрічаються ті чи інші елементи).
Шеннон (Shannon a. Weaver, 1949) встановив кількісне співвідношення між мінімальною інформаційною ємністю, достатній для подання повідомлення (тобто кількістю інформації, що міститься у повідомленні), та розподілом ймовірностей його елементів. Висновок цього співвідношення можна знайти в курсах теорії інформації. Ми обмежимося тим, що відразу напишемо отриманий Шенноном результат і обговоримо деякі слідства.
Почнемо з найпростішого випадку, коли алфавіт складається з двох символів, і ці символи статистично незалежні, тобто знання попередніх елементів не впливає на ймовірність появи того чи іншого подальшого. До повідомлень такого типу можна віднести, наприклад, двухградационные зображення, показані на рис. 29. Позначимо ймовірність одного символу (в розглянутому прикладі - ймовірність чорного елемента) через р, а ймовірність іншого (ймовірність білого елемента) - через q; очевидно, q=1-Р
Тоді, по Шеннону, мінімальна інформаційна ємність, яка припадає в середньому на один символ, або середня кількість інформації на один символ, буде
H = - log p p - qlogq (30)
або
H = - log p p- (1 - р) log (1 - р)
(див. рис. 30).

Рис. 30. Ентропія в разі вибору з двох можливостей з ймовірностями р, 1 - р

Якщо у формулі (30) обрані двійкові логарифми, то величина Н виражена в двійкових одиницях. Надалі, якщо не буде зроблено спеціальної застереження, будемо вважати, що log позначає двійковий логарифм.
Величину Н називають ентропією. * Вона залежить від розподілу ймовірностей (в даному випадку р і q) і характеризує ступінь невизначеності результату події, що полягає у виборі одного з символів. Ентропія досягає максимуму у випадку найбільшої невизначеності вибору, коли обидва символи рівноймовірні, р = 1-р = 0.5. Навпаки, якщо відсутня невизначеність (р=1 або 5=1), ентропія звертається в нуль. Це добре відповідає нашим інтуїтивним уявленням. Чим більше невизначеність до приходу повідомлення, тим більше інформації містить повідомлення, що знімає цю невизначеність. Навпаки, якщо достовірно можливо тільки одна подія, повідомлення про нього не містить ніякої інформації.
Якщо вибір здійснюється не з двох, а з т можливостей {т символів, наприклад т градацій яскравості) і ймовірність здійснення цих можливостей буде р2, р3 ... рм, причому p1 + р2 + р3 ... + рм = 1, то мінімальна інформація, яка припадає в середньому на один символ, буде
H = -p1 log p1 - p2 log p2 - ... - рм log рм. (31)
Рівність (30) є окремим випадком рівності (31). виходить при m=2.
Можна показати, що і в цьому більш загальному випадку максимальне значення H досягається, коли всі можливості рівноймовірні, P1 = р2- ... = рм = 1/m.
Найбільшої невизначеності відповідає найбільша кількість інформації. Це максимальне значення легко знайти з (31),

Якщо ж вибір відсутній і є лише одна достовірна можливість, а ймовірність інших дорівнює нулю (наприклад, р1=1, р2 = р3= ... = рм = 0), то дорівнює нулю і кількість інформації: все відомо заздалегідь.
Як відомо з теорії ймовірностей, права частина рівності (31) має сенс середнього значення (математичного очікування) величини - log pi. Але це рівність разом з тим визначає кількість інформації H, що припадає в середньому на один символ. Звідси випливає інша, еквівалентна раніше введеного визначення кількості інформації:
Інформація при виборі можливості, що має апріорну ймовірність рі, дорівнює - log рі. (33)
Іншими словами, приріст інформації при повідомленні про подію, ймовірність якого була рі, дорівнює - log рі.
Це визначення також ховаю відповідає нашим інтуїтивним уявленням. Повідомлення про дуже ймовірне подію несе менше інформації, ніж повідомлення про малоймовірному, несподівану подію. Якщо ж подія має статися достовірно (p = 1), то приріст інформації при повідомленні про нього дорівнює нулю (log 1=0).
Якщо повідомлення складається з N символів (наприклад, N елементів зображення), то мінімальна інформаційна ємність, яка потрібна для його подання, дорівнює NH. Слід мати на увазі, що це твердження стає точним лише при безмежному зростанні N. Чим ближче частоти, з якими зустрічаються символи, до відповідних імовірностей, тим точніше величина NH що вимагається визначає мінімальну інформаційну ємність.
Підрахуємо в якості прикладу ентропію для двох типів зображень, вже розглядалися раніше (типові фрагменти зображень показано на рис. 29). В обох випадках для подання цих зображень було використано інформаційна ємність
Нмакс = log2 = 1 дв. од./елемент.
Формула (30) дозволяє розрахувати мінімальну інформаційну ємність, що вимагається для запису зображень з заданим розподілом ймовірностей.
У першому випадку р=1/16, q = 15/16
У другому випадку,

З більш рідкісними символами (в розглянутому раніше прикладі (рис. 29, а) - з чорними елементами) пов'язано більше інформації. Проте переважають більш ймовірні події (у розглянутому прикладі - білі елементи), що несуть меншу інформацію. У середньому інформація, яка припадає на один вибір, виявляється менше, ніж у випадку рівноймовірно можливостей.
Якщо у другому випадку записати зображення більш економно, ніж це зроблено, вже не можна, то в першому випадку необхідну інформаційну ємність можна зменшити майже в чотири рази.
Ставлення ентропії до її максимального значення Нмакс, получающемуся, коли всі символи рівноймовірні, H/Нмакс називається відносної ентропії. Обернена Величина цього відношення, що показує, у скільки разів можна зменшити інформаційну ємність, що вимагається для подання повідомлення (наприклад, зображення) з ентропією Н, порівняно з випадком, коли при тому ж алфавіті (наприклад, при тому числі помітних градацій яскравості) усі символи (наприклад, всі градації яскравості) рівноймовірні.
Величина
R = 1 - H/Нмакс (34)
характеризує ступінь незавантаженості інформаційної ємності. Ця величина називається надлишковістю. Вона дорівнює нулю тільки при H = Нмакс, наприклад для зображень такого типу, як на рис. 29, б. Для зображень, типовий фрагмент яких показаний на рис. 29, а, надмірність становить
R = 1-0.278/1=0.722.
Знаючи Н, можна оцінити ефективність тих чи інших способів «стиснення» повідомлень. Так, розглянутий у зв'язку з рис.29, а спосіб економного представлення зображень з зазначеним розподілом ймовірностей хоча і дозволяє зменшити необхідну інформаційну ємність більш ніж удвічі, проте ще далеко не на ту величину, яка визначається надлишковістю.
Досі всі міркування ставилися до випадку, коли всі елементи повідомлення, наприклад, елементи зображення, статистично незалежні і ймовірність того, що елемент приймає значення яскравості, не залежить від значень попередніх елементів.
Проте зазвичай зустрічаються зображеннях між елементами є сильні статистичні зв'язки. Особливо значні статистичні зв'язки між сусідніми елементами. Як правило, досить велика ймовірність того, що яскравості двох сусідніх елементів рівні з точністю до однієї градації або мало відрізняються один від одного. Знаючи яскравість одного елемента, можна з відносно великою ймовірністю правильно передбачити яскравість сусіднього елемента. Іншими словами, інформація, що міститься в повідомленні про яскравості даного елемента, помітно зменшується, якщо вже була відома яскравість попереднього елемента. З'являється можливість відповідно зменшити інформаційну ємність, що вимагається для запису зображень.
На рис. 31 показаний приклад того, як можуть бути використані межэлементные статистичні зв'язки для скороченого запису зображення. У вихідному двухградационном зображенні (а) чорні та білі елементи зустрічаються майже однаково часто (Рчерн ≈ Рбел ≈ 1/2), тобто так само, як і на рис. 29, б. Однак на відміну від зображення того типу тут є помітні межэлементные зв'язку. Число переходів і дрібних деталей відносно невелика. Частоти, з якими зустрічаються чорні елементи після чорні або білі після білих, у багато разів перевершують частоти, з якими відбуваються переходи від чорного до білого або навпаки. Таке зображення може бути замінено контурним малюнком (рис. 31, б). Контури вказують на місця переходів від чорного до білого і від білого до чорного. Оскільки частота переходів відносно мала, відповідно мало і число контурних елементів. Якщо тепер вказати положення цих контурних елементів (їх координати або номери, як у випадку рис. 29, а), то число двійкових цифр, потрібних для такого запису зображення, виявляється істотно меншою, ніж число елементів вихідного зображення. Якщо зображення було б многоградационным, довелося б ще вказати величину переходу або градації яскравості після переходу.

Рис. 31. Приклад заміни вихідного (а) зображення контурним (б).

Статистичні зв'язки спостерігаються не тільки між найближчими сусідніми елементами, але і більш віддаленими елементами. Внаслідок того що сприймаються нами зображення зазвичай змінюються в часі відносно повільно, існують сильні статистичні зв'язки між значеннями яскравості одного і того ж елементарного ділянки зображення, послідовно отсчитываемыми через певні інтервали часу. Добре відомо, що середнє число елементів, що змінюються від кадру до кадру в кіно або на телебаченні, порівняно невелика. Якщо відома яскравість даного елемента в даному кадрі, повідомлення про яскравість того ж елемента в наступному кадрі несе в середньому порівняно мало інформації.
Для точного розрахунку ентропії зображень знадобилося б перш за все встановити, чи допускають можливі зображення єдине статистичне опис, т. е. можна вважати їх статистично однорідними, а відповідні усереднення - мають сенс. Далі знадобилося б врахувати всі статистичні зв'язки в зображеннях.
Можна відразу відповісти негативно на питання про статистичної однорідності зображень. Але навіть якщо це було б не так, все одно облік всіх статистичних зв'язків у зображеннях був би практично неможливий.
Однак деякі корисні оцінки кількості інформації в зображеннях можуть бути зроблені. Наближені оцінки ентропії зображень виявилися необхідними у зв'язку з роботами в галузі підвищення ефективності та завадостійкості телевізійних систем. З цією метою було розроблено декілька експериментальних методів дослідження статистики зображень. Огляд цих методів дано, наприклад, у дисертації Лебедєва (1958). Ми наведемо лише основні результати досліджень, що мають, як це з'ясується в подальшому, важливе значення для розуміння властивостей зорової системи.