Система стиснення відеоданих на основі аналізу ентропійності

Зміст
ЗАВДАННЯ на виконання дипломного проекту
РЕФЕРАТ
Вступ
1. Імовірнісний підхід у теорії кодування відеоінформації
1.1 Інформаційний опис
1.2 Імовірнісний підхід
1.2.1 Ентропія
1.2.2 Дешифровані коди
1.2.3 Оптимальна довжина коду
1.3 Методи генерації коду
1.3.1 Префіксне кодування
1.3.2 Алгоритм Шеннона
1.3.3 Алгоритм Хаффмана
1.4 Основні результати і висновки
2. Розробка імовірнісних методів для підвищення ефективності кодування
2.1 Квантування
2.2 Побудова інформаційного критерію
2.2.1 Оцінка інформативності ознак
2.2.2 Оптимальна градація ознак.
2.2.3 Градація перших 100 чисел натурального ряду
2.2.4 Градація яскравостей зображень
3. Розробка ефективного алгоритму кодування зображень на основі зміни градації яскравості
3.1 Загальна структура програми
3.3 Розробка алгоритму завантаження зображення з файлу
3.4 Розробка перетворення кольорового зображення у чорно-біле
3.5 Розрахунки гістограми яскравостей
3.6 Розробка функції обчислення порогового значення відрізку масиву яскравостей зображення
3.7 Розробка рекурсивної процедури розділення масиву гістограми яскравостей та складання масиву відповідностей елементів палітри
3.8 Розробка функції ентропійного кодування зображення
3.9 Опис використаних компонентів
4. Тестування програми
5. Техніко-економічна частина
5.1 Позначка й призначення
5.2 Оцінка ринку збуту
5.3 Оцінка конкурентноздатності
5.4 Стратегія маркетингу
5.4.1 Оцінка витрат на розробку продукту
5.4.2 Реклама
5.5 Оцінка ризику і страхування
5.6. Фінансовий план
5.7 Висновок
6. Охорона праці і навколишнього середовища
6.1 Основні питання охорони праці
6.2 Промислова санітарія
6.2.1 Мікроклімат
6.2.2 Виробниче освітлення
6.2.3 Шум
6.2.4 Випромінювання від екрана
6.3 Техніка безпеки на робочому місці
6.3.1 Електробезпека
6.3.2 Ергономічні вимоги до робочого місця
6.4 Пожежна безпека
6.5 Охорона навколишнього середовища
Висновки
Список джерел інформації
Додаток
Текст програми
Керівництво оператора
Опис програми
Вступ
На сьогоднішній день актуальна проблема зберігання й передачі інформації в цифровому виді. Для одержання компактних інформаційних подань застосовуються технології ощадливого кодування. Використання цих технологій дозволяє істотно знизити вимоги, пропоновані до обсягу інформаційних носіїв, а також відчутно збільшує швидкість передачі інформації з каналів зв'язку.
Передача інформації є основною областю застосування ощадливого кодування. На даний момент першочергове завдання - організація ефективного телевізійного й мультимедійного віщання. Як відомо, відеоінформація являє собою найбільш об'ємний тип інформації. З обліком обмеженої пропускної здатності цифрових каналів, щоб гарантувати високу якість передачі зображень, необхідно забезпечити їх досить ефективне подання (якість передачі прямо залежить від обсягу інформації, переданого в одиницю часу). Як наслідок, протягом уже більше 15 років значні зусилля направляються на розробку технологій ефективного подання зображень. Цій проблемі присвячена й дана дипломна робота.
Основна мета роботи - аналіз існуючих технологій одержання компактних подань відеоінформації з погляду способу організації кодування й пошук можливих шляхів підвищення їхньої ефективності.
Вибір напрямку дослідження заснований на результатах порівняльного аналізу існуючих алгоритмів ощадливого кодування. Алгоритм ощадливого кодування являє собою певний спосіб генерації ощадливого коду на основі наближеної моделі породження кодуємої інформації. З метою зниження обчислювальної складності на практиці довгий час застосовувалися спрощені методи інформаційного моделювання й генерації коду. Як моделі бралися найпростіші комбінаторні моделі, а генерація коду здійснювалася з використанням найбільш швидких реалізацій префіксного кодування. У цей час постановка завдання змінилася: на перший план стала всі частіше виходити ефективність кодування. Сьогодні стає доцільним застосування більше складних технологій кодування, які дозволяють досягти максимально компактного інформаційного подання.
Одним з найбільш ефективних методів інформаційного моделювання є імовірнісне контекстно-залежне моделювання. При використанні даного методу вибір інформаційної моделі в кожен момент часу здійснюється на основі значення деякого контексту, що формується з елементів уже обробленої інформаційної вибірки. Уводячи контексти, ми фактично вирішуємо завдання ідентифікації станів інформаційного джерела. Для кожної моделі зберігається статистична інформація про появу різних символів інформаційного алфавіту в контексті, що відповідає даної моделі. На основі цієї інформації формується розподіл імовірнісних оцінок появи символів на виході джерела, що є основою для генерації коду.
Арифметичне кодування являє собою найбільш ефективний метод генерації коду по заданому імовірнісному розподілі. Використання цього методу дозволяє одержувати коди, довжини яких мало відрізняються від теоретично оптимальних значень.
Таким чином, сполучення контекстно-залежного імовірнісного моделювання й арифметичного кодування найбільше вигідно з погляду ефективності. При цьому найбільш ефективним буде кодування інформації на основі аналізу її ентропійності - завдяки такому підходу, ми зможемо гарантувати зменшення обсягу відеоінформації, за умови зберігання достатнього рівня інформаційності, тобто зображення залишається досить чітким, але кількість кольорів зображення зменшується, при цьому чоловіче око може аналізувати цю інформацію на рівні із попередньою.
Тому в дипломній роботі приділимо увагу до кодування найпростішого виду відеоінформації - чорно-білого зображення, що дає можливість отримати основи алгоритмів для кодування більш складних видів зображень, як кольорові картинки та відео файли.
1. Імовірнісний підхід у теорії кодування відеоінформації
1.1 Інформаційний опис
Теорія ощадливого кодування займається проблемою створення ефективних подань інформаційної вибірки. Мова в більшості випадків іде про вибірку джерел дискретної інформації з кінцевим алфавітом. Ефективне кодування стає можливим завдяки наявності в інформації певних особливостей, тому однієї з найбільш важливих задач є одержання як можна більше точного опису властивостей інформаційних джерел.
Існує кілька підходів до такого роду опису. Найбільше часто використовувані - комбінаторний й імовірнісний.
У рамках комбінаторного підходу символи розглядаються не обособлено, а групами, іменованими інформаційними повідомленнями. Покладається, що з виходу джерела інформації можуть надходити не всі можливі повідомлення, а тільки повідомлення з деякого виділеної множини. При цьому повідомлення, що належати даній множині, уважаються зовсім рівнозначними, тобто їхня поява покладається рівноймовірним. Конкретний вибір множини припустимих повідомлень виконує роль інформаційного опису.
Комбінаторний підхід одержавши досить широке поширення на практиці. Основним його достоїнством є простота опису інформаційних особливостей, тому практичні реалізації методів ощадливого кодування, в основі яких лежить даний підхід, мають низьку обчислювальну складність.
Недолік полягає в тім, що точність опису годиною прямо залежить потужності множини припустимих повідомлень - для одержання досить точного опису може знадобитися розглянути дуже велика кількість повідомлень. Комбінаторний підхід також не дозволяє одержувати інформаційні характеристики для окремих символів усередині повідомлення.
Суть імовірнісного підходу полягає у використанні імовірнісних оцінок фактів появи різних символів на виході джерела інформації. У порівнянні з комбінаторним підходом імовірнісний підхід є більше точним способом опису властивостей інформаційних джерел. У тієї ж година імовірнісний підхід менш вигідний з обчислювальної крапки зору, тому що його застосування сполучене з обчисленням складних імовірнісних оцінок. Таким чином, з одному боку, імовірнісний опис, як правило, більш ефективно в порівнянні з комбінаторним описом, з іншого боку, імовірнісний опис не завжди можна використати на практиці через існуючі обчислювальні обмеження. Постійне збільшення продуктивності обчислювальних систем робить останній фактор менш значимим, внаслідок чого імовірнісний підхід останнім годиною всі частіше й частіше береться за основу при розробці алгоритмів ощадливого кодування.
1.2 Імовірнісний підхід
1.2.1 Ентропія
Основоположником імовірнісного підходу є Шеннон. Він запропонував ввести характеристику невизначеності інформації H (p 1; p 2; …; p N ), що залежить від імовірностей p 1; p 2; …; p N появи символів алфавіту A потужності N на виході інформаційного джерела. Шеннон зажадав, щоб міра невизначеності, за аналогією з аналогічною фізичною характеристикою названа їм ентропією, мала наступні властивості:
величина H (p1,p2,...,pn) інваріантна щодо перестановок аргументів p1,p2,...,pn;
функція H (p1,p2,...,pn) безперервна по шкірному з аргументів своїх аргументів p1,p2,…,pn]
функція A (N) = H (1/N,…1/N) з кількістю елементів 1/N=N, монотонно зростає по N
виконується співвідношення: H (p 1; p 2; …; pk; pk +1; …; pk +l ) = H (p 1; p 2; …; pk; ps ) + psH (pk +1/ ps,…, pk +l/ps), де ps = сума від 1 до l ( p k +1).
Як показав Шеннон, функція, що задовольняє зазначеним властивостям, має вигляд H (p 1; p 2; …; p N ) = - K∑p i logm p i, д е K та m - деякі позитивні константи. Для зручності пропонується вибирати K рівним одиниці, а в якості m брати основу системи подання інформації. Як показує практика, такий вибір багато в чому виправданий. Наприклад, у системі подання інформації з підставою 2 невизначеність появи одного із двох символів, що з'являються з рівною ймовірністю, виявляється рівної 1 біту. Це добрі погодиться з визначенням біта як одиниці інформації, необхідної для подання вибору одного із двох равновероятных подій. Таким чином, підсумкова формула для обчислення ентропії інформаційного джерела з імовірнісним розподілом появи символів {pi}N i=1 виглядає в такий спосіб:
(1.1)
Формула (1.1) дозволяє визначити ентропію джерела, що перебуває в деякому конкретному стані. Ентропія джерела в цілому - безвідносно до конкретного стану - може бути визначена далеко не завжди. Можливість визначення ентропії залежить від імовірностей тихнув або інших станів і відповідних цих станів ансамблів перехідних імовірностей (перехід зі стану в стан здійснюється при породженням джерелом чергового символу). Розглянемо окремий випадок, коли інформаційне джерело S може перебувати в одному з T станів, причому чітко відомі всі ймовірності переходів джерела з будь-якого стану i у стан j (pij). Якщо існує межа , де Р - матриця з компонентами pi,j, величина ентропії джерела S може бути обчислена по формулі
(1.2)
Отут pi - імовірність знаходження джерела S в i-м стані (pi є значення i - елемента будь-якого рядка матриці P∞ ), a m - підстава системи подання інформації.
Множина станів інформаційного джерела в сукупності з ансамблем перехідних імовірностей прийнято називати моделлю станів або марковской моделлю. Для визначення ентропії джерела інформації в рамках даної моделі необхідно правильно підібрати її структуру й параметри, які повинні повною мірою відповідати джерелу. На практиці це досить важко, тому що параметри інформаційних джерел, як правило, апріорі не відомі1 . Визначити їх можна тільки приблизно, тому при рішенні практичних задач доводити прибігати до емпіричних способів оцінки ентропії. Як правило, мова йде про усереднення величини ентропії за годиною.
Нехай джерело послідовно перебуває в станах s 1, s 2,..., sn , я кі відповідають розподілу ймовірностей появи символів
Через рі1, і2, іn позначимо ймовірність появи на виході джерела послідовності символів з індексами i1, i2,..., in ( символ ik породжується джерелом у стані sk). Очевидно, що
(1.3)
Напівемпіричною ентропією джерела назвемо величину
(1.4)
З урахуванням тотожності (1.3) формула (1.4) приводитися до більше зручного для обчислення виду
Приставка "напів" означає, що для отримання ентропії частино використовуються апріорні дані про імовірнісні характеристики джерела (відомий розподіл імовірностей появи символів у різних станах), а частина, що залишилася, інформації - конкретна послідовність станів - виходить емпіричним шляхом. У реальних задачах, як правило, подібної апріорної інформації ні, тому доцільно ввести поняття емпіричної ентропії, визначивши її величину по формулі:
(1.6)
У цьому випадку ri (sj) - емпірична оцінка ймовірності появи символу з індексом i при породженні j-й вибірки джерела інформації1 . Причина, по якій особлива увага приділяється способах обчислення ентропії, полягає в тім, що величина ентропії є чисельною границею ефективності ощадливого кодування вибірки інформаційного джерела. Знаючи ентропію, можна оцінити ефективність того або іншого методу або алгоритму. В ідеалі ефективність винна збігатися з величиною ентропією. При цьому, якщо природа інформаційного джерела не є імовірнісної, тобто чітко виділити ті або інші імовірнісні стани не можна, мова може йти тільки про ентропію, що обчислює частково на емпіричній основі. В силу останньої обставини, надалі при вживанні терміна ентропія найчастіше буде матися на увазі напівемпірична ентропія.
Обчислення ентропії на практиці можна здійснювати в процесі послідовного аналізу станів інформаційного джерела, що безпосередньо треба з формул (1.5) і (1.6). Як видно з наведених формул, величина ентропії складається з величин ентропії в станах, у яких послідовно перебуває джерело інформації. Таким чином, задача оптимального моделювання послідовної інформаційної вибірки зводиться до задачі створення оптимальної моделі породження символів у шкірному конкретному стані, що є істотним спрощенням. Як буде показаний нижче, подібне спрощення припустиме й відносно механізму генерації коду, тобто воно фактично припустимо відносно методу кодування в цілому.
1.2.2 Дешифровані коди
Найпростіший варіант кодування вибірки інформаційного джерела - установлення відповідності між конкретними символами алфавіту й кодами, що мають цілу довжину в одиницях подання інформації. Природно зажадати, щоб код, отриманий у результаті такого кодування, був дешифрованим, тобто по будь-якій комбінації кодів символів можна було б відновити закодоване повідомлення. Необхідна умова дешифруємості було запропоновано й доведене Макмілланом. Формулювання виглядає в такий спосіб: якщо система кодів із цілими довжинами {li}N i =1 дешифровані, те виконується нерівність
(1.7)
де m - підстава системи подання інформації.
Виконання нерівності (1.7) спричиняє виконання більше важливої нерівності:
(1.8)
Для доказу досить скористатися опуклістю функції logm (x ). Таким чином, ефективність дешифрованого посимвольного кодування обмежена величиною ентропії імовірнісного розподілу появи символів на виході інформаційного джерела.
Більше складний й у той же час найбільше ефективний варіант кодування має на увазі одержання кодів не для окремих символів, а для цілих повідомлень. Коди декодуємих повідомлень, мабуть, також повинні задовольняти нерівності Макміллана. При цьому оцінка ефективності з розрахунку на один символ повідомлення ускладнюється необхідністю проведення усереднення по довжині повідомлення. Покажемо, що ефективність кодування вибірки інформаційного джерела зазначеним способом також обмежується величиною ентропії.
Будемо використати раніше уведені позначення. Джерело, що послідовно перебуває в станах s 1, s 2,..., sn , як і раніше, характеризується імовірнісними розподілами
.
Через pi 1, i 2,..., in позначається ймовірність появи повідомлення "i 1, i2,... in ", через li 1, i 2,..., in - довжина коду повідомлення. Ефективність кодування повідомлень довжини n з розрахунку на один символ визначається по формулі
Коди для повідомлень довжини n повинні бути дешифрованими, тому можна скористатися нерівністю (1.8):
Права частина нерівності являє собою вираження для ентропії. Таким чином, ефективність кодування з розрахунку на один символ не може перевершувати величину ентропії повідомлення, що доводити на один символ. Використовуючи формулу (1.5), одержуємо більше зручну з обчислювальної крапки зору оцінку:
Якщо джерело, що породжує повідомлення, є стаціонарним (імовірнісний розподіл не залежить від позиції символу в повідомленні), нерівність здобуває спрощений вид:
1.2.3 Оптимальна довжина коду
Тому що код виходить для повідомлення в цілому, не можна говорити про коди для конкретних символів, що становлять повідомлення. Проте виникає необхідність визначати деякий внесок у результуючу довжину коду повідомлення, внесень кожним вхідної в нього символом. Фізичний зміст такого внеску - середнє збільшення довжини коду повідомлення, обумовлене входженням у нього даного символу. Позначимо через xi внесок, внесень символом з індексом i ( у загальному випадку величина внеску являє собою речовинне число). Через xi 1, i 2,..., in позначимо внесок, внесень повідомленням s = i1 , i2 ,..., in - Виходячи зі змісту поняття "внесок", для випадку стаціонарної незалежної вибірки логічно зажадати виконання наступних властивостей:
( адитивність)
,
де li 1, i2,..., in - довжина реального коду повідомлення (ціле число), а M (n) - ненегативна функція, така що M (n) /n - > 0 при n - > оо
Асимптотичне поводження функції M (n) /n дозволяє зробити висновок:
(1.9)
Таким чином, отримане узагальнення нерівності Макміллана на випадок внесків символів у результуючу довжину повідомлень.
Узагальнена нерівність (1.9) дозволяє обчислити точне значення величини внеску xa символу з індексом a для випадку оптимального кодування. Для обчислення точного значення необхідно вирішити задачу про мінімізацію суми
,
яка визначає середню ефективність кодування, за умови виконання нерівності (1.9). У крапці мінімуму похідна від зазначеної суми звертається в нуль:
(1.10)
Підстановка рішення задачі про мінімізацію в нерівність (1.9), мабуть, повинне перетворювати його в рівність. Звідси будь-який оптимальний внесок xk легко виражається через внески інших символів:
Підставляючи вираження для xk у рівняння (1.10), одержуємо
Після узяття похідної рівняння здобуває наступний вид:
, або
Індекс k може приймати одне з N значень, тобто реально для шкірного фіксованого індексу a є N рівнянь. Просумувавши ці рівняння, одержимо
що з урахуванням виконання рівності у вираженні (1.9) рівносильне
Звідси отримаємо формулу для xa :
(1.11)
Таким чином, оптимальний внесок символу, що з'являється з імовірністю p: у довжину результуючого коду становить logm p одиниць інформації в системі подання з підставою m. - анный висновок може бути використаний для обчислення оптимальної довжини коду в рамках тієї або іншої імовірнісної моделі. Одержуючи оцінку ймовірності появи чергового символу на деякому етапі кодування, можна точно визначити оптимальну довжину відповідного інформаційного опису.
1.3 Методи генерації коду
1.3.1 Префіксне кодування
Серед кодів, що задовольняють нерівності Макміллана, особливе місце займають префіксні коди. Система кодів називається префіксною, якщо жоден з кодів, що належить системі, не є качаном (префіксом) іншого коду із цієї ж системи. Очевидне достоїнство префіксного кодування полягає в тім, що одержуваний код може бути легко декодований. Завдяки властивості префікса для того, щоб визначити черговий закодований символ (повідомлення), досить проаналізувати качан відповідної чергової порції коду. При цьому довжина аналізованої порції ніколи не перевищує довжину коду чергового закодованого символу (повідомлення).
Геометрична трактування систем префіксних кодів - m-арные дерева. Властивістьпрефікса гарантує відсутність циклів у графі, ребрам якого зіставлені різні значення інформаційної одиниці. Таким чином, граф є деревом зі ступенем розгалуження, що збігає з підставою системи подання інформації m. Слід зазначити, що нумерація ребер може бути здійснена довільним образом; значення має тільки конкретна структура дерева, а точніше - набір відстаней від кореневого вузла до листових вузлів. Ці відстані відповідають довжинам кодів префіксної системи. Крафт показав, що виконання нерівності (1.7) є гарантією існування кодового дерева зі структурою, що відповідає набору довжин , що фігурують у нерівності. Інакше кажучи, якщо система довжин задовольняє нерівності (1.7), можна побудувати систему префіксних кодів з відповідними довжинами. Дане твердження дозволяє відмовитися від розгляду систем кодів, відмінних від префіксних. Будь-яка система дешифрованих кодів задовольняє нерівності (1.7), а виходить, вона може бути без шкоди для ефективності замінена системою префіксних кодів. Нерівність (1.7) стосовно до систем префиксних кодів називають також нерівністю Крафта.
Розглянемо блокове кодування повідомлень довжини n, породжуваних деяким інформаційним джерелом. Як і раніше, позначимо через
імовірнісний розподіл появи j -ro символу повідомлення (sj - відповідний стан джерела), через pi 1, i2,..., in - імовірність появи повідомлення "i 1 , i 2 ,..., in ". Відповідно до твердження Крафта, можна побудувати систему префіксних кодів із длинами
(Для доказу досить підставити ці довжини в нерівність Крафта й переконатися в тім, що воно виконується) Оцінимо ефективність кодування з розрахунку на один символ повідомлення:
Використовуючи альтернативне вираження для ентропії (1.5), одержуємо
Для випадку стаціонарного джерела з розподілом імовірностей
маємо:
Збільшуючи довжину повідомлення n, можна домогтися ефективності кодування як завгодно близької до ентропії джерела інформації. Таким чином, знаючи апріорі ймовірності появи різних символів на виході джерела в кожен конкретний момент часу, можна організувати кодування даного джерела, наближене до оптимального кодування на кожну наперед задану величину, за умови, що є достатній об'єм інформаційної вибірки.
1.3.2 Алгоритм Шеннона
Алгоритм побудови системи префиксних кодів з довжинами, що залежать від імовірностей по формулі , був запропонований Шенноном. Алгоритм працює в такий спосіб. Імовірності появи повідомлень p 1 ,p2 ,...,pn розташовуються в порядку убування (тут N - потужність множини повідомлень). Не обмежуючи спільності, можна вважати
.
Як код повідомлення з індексом i беруться перші m -ичных розрядів числа так називаної накопиченої ймовірності. Тому що довжини кодів у такій системі не убувають зі зменшенням імовірності й імовірності появи повідомлень із індексами i +1, i +2,...,N відрізняються від імовірності появи повідомлення з індексом i принаймні на , код повідомлення з індексом i не є початком кодів повідомлень із індексами i +1, i +2,...,N. Таким чином, система кодів є префіксною. Розглянемо геометричне трактування алгоритму Шеннона. Інтервал [0, 1) може бути розбитий на N підінтервалів
,
відповідним повідомленням з індексами i = 1, 2,...,N. Для ідентифікації i-го повідомлення необхідно вибрати деяке число з підінтервалу [ai , bi ), представиме як можна меншою кількістю m -ічних розрядів. Для цього потрібно побудувати на інтервалі [0,1) одномірну мережу з постійним періодом, що містить крапок (місце розташування будь-якої крапки визначається li -розрядним числом), рівно одна з яких (ідентифікуюча) належить інтервалу [ai , bi ). Ясно, що шукана мережа повинна мати період, що не перевищує pi , тобто . Звідки отримуємо .
Алгоритм Шеннона дозволяє генерувати коди, довжина яких відрізняється від оптимальних значень, обумовлених по формулі (1.11), менш чим на одну інформаційну одиницю. Таким чином, різниця між ефективністю кодування й ентропією (так називана надмірність) не перевищує одиниці.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию