Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
: Cистема стиснення відеоданих на основі аналізу ентропійності
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет Харківський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра обчислювальна техніка та програмування
Інформація про роботу
Рік:
2009
Тип роботи:
Дипломна робота
Предмет:
Системне програмування та операційні системи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний технічний університет
“Харківський політехнічний інститут"
Кафедра Обчислювальна техніка та програмування
Спеціальність Системне програмування
До захисту допускаю
Завідувач кафедри
ДИПЛОМНИЙ ПРОЕКТ
Освітньо-каліфікаційного рівня спеціаліст
Тема проекту: Cистема стиснення відеоданих на основі аналізу ентропійності
Харків 2009
ЗАВДАННЯ
на виконання дипломного проекту
1. Тема проекту Система стиснення відеоданих на основі аналізу ентропійності______________________________________________________
2. Зміст завдання Дослідити проблеми кодування відеоінформації, призначення й мету створення системи. Розробити загальну структуру програми та алгоритм. Розробити програмне забезпечення. Вивести результати роботи та тестування. Ознайомитись з питаннями охорони праці та навколишнього середовища. Зробити економічну оцінку проекту у вигляді бізнес-плану.
3. Вихідні дані для виконання проекту Айвазян С.А., Мхитарян.В.С. Прикладная статистика и основы эконометрики; Дидэ Э. и др. Методы анализа данных; Кричевский Р.Е. Сжатие и поиск информации; Куренков Н.И. Ананьев С.Н. Энтропийный подход к решению задач классификации многомерных данных; Левенштейн В.И. Об избыточности и замедлении разделимого кодирования натуральных чисел; Семенюк В.В. Применение вероятностного моделирования в методах экономного кодирования видеоинформации; Сакоян С.А. Об оптимальных разбиениях на градации в задачах классификации; Семенюк В.В. Экономное кодирование дискретной информации
4. Скласти звіт і виконати необхідні документи (програмні, плакати) відповідно до плану виконання дипломної роботи
Найменування програмного продукту "Графічний кодер чорно-білих зображень”. Розробляється для дипломного проекту "Система стиснення відеоданих на основі аналізу ентропійності".
Область застосування програмного продукту вищі учбові заклади, книжкові та газетні видавництва, служби охорони, та державна служба безпеки. Програмний продукт дозволяє будь-які 256-кольорові чорно-білі зображення, які зберігаються у форматі. jpeg або. bmp, у зображення. bmp з меншою кількістю кольорів (від 2 до 16) із зберіганням інформативності зображення. Для покращення результатів обробка зображення виконується декількома методами, з метою отримати найбільш вигідне зображення.
1. ПІДСТАВА ДЛЯ РОЗРОБКИ
Розробка ведеться відповідно до наказу по Національному технічному університету "Харківський політехнічний інститут"
№_3001 - ІІІ_ від “_21_" _листопада_ 2008 р. Найменування програмного продукту: "Графічний кодер чорно-білих зображень".
Розробляється для дипломного проекту "Система стиснення відеоданих на основі аналізу ентропійності".
2. ПРИЗНАЧЕННЯ РОЗРОБКИ
Розроблюваний програмний продукт повинен розв’язувати важливі питання в галузі роботи з графічними зображеннями чорно-білого формату, з метою запропонувати користувачам метод кодування інформації на основі аналізу ентропійності, який дозволяє стиснути зображення у менший розмір, з меншою кількістю кольорів, але при цьому зберігаючи інформативність зображення.
Програма може використовуватися у вищих учбових закладах для проведення практичних занять з теорії кодування відеоінформації, у книжкових та газетних видавництвах для покращення чорно-білих малюнків на сторінках, та у службах охорони та безпеки, для зберігання фотоінформації, відбитків пальців, тощо.
3. ВИМОГИ ДО ПРОГРАМНОГО ПРОДУКТУ
Функціональні характеристики
Розроблюваний програмний продукт повинен забезпечувати:
Відкриття зображення з його виводом на екран;
Кодування відеоінформації методами на основі аналізу ентропійності;
Кодування інформації методом рівномірної розбивки;
Вивід отриманого зображення на екран;
Зберігання інформації у формат. bmp з кількістю кольорів 16.
Вивід гістограми початкового та кінцевого зображення
3.2 Вимоги до надійності
Розроблений програмний продукт повинен відповідати наступним вимогам за критерієм надійності:
коректно працювати, тобто не призводити до припинення роботи ПЕОМ, яке може виникнути у ході роботи програмного продукту;
відмова в роботі не повинна призвести до втрати даних у базі даних тестів.
3.3 Умови експлуатації
Програмний продукт повинен функціонувати у нормальних умовах для персоналу:
температура навколишнього середовища від 100 С до 320 С;
вібрації, зовнішні магнітні, радіаційні та електричні поля не повинні перевищувати норми.
Для нормальної експлуатації програмного продукту обслуговуючому персоналу необхідні знання по експлуатації ПК.
3.4 Вимоги до складу і параметрів технічних засобів.
Для експлуатації програмного продукту необхідна ПЕОМ з наступними апаратними характеристиками:
1) стандартна конфігурація IBM-сумісних ПК;.
2) процесор з частотою не менше 750 МГц;
3) ОЗП обсягом не менше 256 Мбайт;
4) жорсткий диск обсягом не менше 100 Гбайт;
5) сумісні монітор та відео адаптер;
6) маніпулятор типа “миша”;
7) мережна карта
8) зв`язок з іншими машинами за допомогою кабелів (витої пари, або оптоволокна), або радіозв`язку.
3.5 Вимоги до інформаційній та програмної сумісності
Розроблений програмний продукт повинен функціонувати на ПЕОМ з операційними системами Microsoft Windows 2000/XP.
3.6. Вимоги до маркування та упаковки
Вимоги до маркування та упаковки програмного продукту, розробленого в роботі на тему: “ Система стиснення відеоданих на основі аналізу ентропійності ” не пред’являються.
3.7. Вимоги до транспортування та збереження.
Вимоги до транспортування та збереження програмного продукту “ Графічний кодер чорно-білих зображень ” не пред’являються.
4. ВИМОГИ ДО ПРОГРАМНОЇ ДОКУМЕНТАЦІЇ
Для дипломної роботи, що розробляється, повинні бути складені наступні програмні документи:
1. Специфікація.
2. Опис програми.
3. Текст програми.
4. Керівництво оператора.
5. ТЕХНІКО-ЕКОНОМІЧНІ ПОКАЗНИКИ
Техніко-економічні показники повинні бути визначені в процесі розробки і зазначені у відповідному розділі звіту про виконання дипломного проекту.
6. СТАДІЇ ТА ЕТАПИ РОЗРОБКИ
Розробка програмного продукту відповідає стадії робочого проекту. Етапи розробки виконують в наступному порядку:
отримання завдання;
збір початкових матеріалів;
огляд літератури й обґрунтування необхідності розробки;
визначення областей застосування;
розробка технічного завдання;
техніко-економічне обґрунтування розробки;
розробка алгоритму розв’язання задачі;
розробка структури програмного продукту;
визначення конфігурації програмних засобів;
розробка звіту дипломного проекту;
програмування і відлагодження програмного продукту;
розробка програмних документів;
тестування програмного продукту;
коректування програми та програмних документів за результатами тестування.
7. ПОРЯДОК КОНТРОЛЮ І ПРИЙМАННЯ
При прийманні дипломної роботи перевіряється:
1. Комплектність, зміст та оформлення документації згідно розділу 4 цього документу.
2. Відповідність програмного продукту згідно вимогам до програмного продукту розділу 3 цього документу.
РЕФЕРАТ
Звіт про ДП: 98 стр., 15 рис., 18 табл., 32 джерела
КЛЮЧОВІ СЛОВА: ентропія, квантування, гістограма яскравості, кодування, стиснення, оптимальна градація, зображення.
У даній роботі розглянуті питання кодування відеоінформації, а точніше, 256-кольорових зображень на основі аналізу ентропійності, сформульовані умови градації яскравості зображення, знайдено коефіцієнт оптимального співвідношення яскравості кластерів, розроблено алгоритм зберігання отриманого зображення та побудови гістограм яскравостей.
Розроблено алгоритм і програма реалізації завдання. Чітко сформульовані основні проблеми, існуючи при кодуванні відеоінформації, та визначено новий комплексний підхід для їх вирішення.
Розглянуті питання охорони праці й навколишнього середовища, проведена техніко-економічна оцінка роботи. На підставі аналізу результатів зроблені висновки й рекомендації для подальшої роботи в даному напрямку.
Зміст
TOC \o "1-3" \n \h \z \u HYPERLINK \l "_Toc234417389" ЗАВДАННЯ HYPERLINK \l "_Toc234417390" на виконання дипломного проекту
HYPERLINK \l "_Toc234417391" РЕФЕРАТ
HYPERLINK \l "_Toc234417392" Вступ
HYPERLINK \l "_Toc234417393" 1. Імовірнісний підхід у теорії кодування відеоінформації
HYPERLINK \l "_Toc234417394" 1.1 Інформаційний опис
HYPERLINK \l "_Toc234417395" 1.2 Імовірнісний підхід
HYPERLINK \l "_Toc234417396" 1.2.1 Ентропія
HYPERLINK \l "_Toc234417397" 1.2.2 Дешифровані коди
HYPERLINK \l "_Toc234417398" 1.2.3 Оптимальна довжина коду
HYPERLINK \l "_Toc234417399" 1.3 Методи генерації коду
HYPERLINK \l "_Toc234417400" 1.3.1 Префіксне кодування
HYPERLINK \l "_Toc234417401" 1.3.2 Алгоритм Шеннона
HYPERLINK \l "_Toc234417402" 1.3.3 Алгоритм Хаффмана
HYPERLINK \l "_Toc234417403" 1.4 Основні результати і висновки
HYPERLINK \l "_Toc234417404" 2. Розробка імовірнісних методів для підвищення ефективності кодування
HYPERLINK \l "_Toc234417405" 2.1 Квантування
HYPERLINK \l "_Toc234417406" 2.2 Побудова інформаційного критерію
HYPERLINK \l "_Toc234417407" 2.2.1 Оцінка інформативності ознак
HYPERLINK \l "_Toc234417408" 2.2.2 Оптимальна градація ознак.
HYPERLINK \l "_Toc234417409" 2.2.3 Градація перших 100 чисел натурального ряду
HYPERLINK \l "_Toc234417410" 2.2.4 Градація яскравостей зображень
HYPERLINK \l "_Toc234417411" 3. Розробка ефективного алгоритму кодування зображень на основі зміни градації яскравості
HYPERLINK \l "_Toc234417412" 3.1 Загальна структура програми
HYPERLINK \l "_Toc234417413" 3.3 Розробка алгоритму завантаження зображення з файлу
HYPERLINK \l "_Toc234417414" 3.4 Розробка перетворення кольорового зображення у чорно-біле
HYPERLINK \l "_Toc234417415" 3.5 Розрахунки гістограми яскравостей
HYPERLINK \l "_Toc234417416" 3.6 Розробка функції обчислення порогового значення відрізку масиву яскравостей зображення
HYPERLINK \l "_Toc234417417" 3.7 Розробка рекурсивної процедури розділення масиву гістограми яскравостей та складання масиву відповідностей елементів палітри
HYPERLINK \l "_Toc234417418" 3.8 Розробка функції ентропійного кодування зображення
HYPERLINK \l "_Toc234417419" 3.9 Опис використаних компонентів
HYPERLINK \l "_Toc234417420" 4. Тестування програми
HYPERLINK \l "_Toc234417421" 5. Техніко-економічна частина
HYPERLINK \l "_Toc234417422" 5.1 Позначка й призначення
HYPERLINK \l "_Toc234417423" 5.2 Оцінка ринку збуту
HYPERLINK \l "_Toc234417424" 5.3 Оцінка конкурентноздатності
HYPERLINK \l "_Toc234417425" 5.4 Стратегія маркетингу
HYPERLINK \l "_Toc234417426" 5.4.1 Оцінка витрат на розробку продукту
HYPERLINK \l "_Toc234417427" 5.4.2 Реклама
HYPERLINK \l "_Toc234417428" 5.5 Оцінка ризику і страхування
HYPERLINK \l "_Toc234417429" 5.6. Фінансовий план
HYPERLINK \l "_Toc234417430" 5.7 Висновок
HYPERLINK \l "_Toc234417431" 6. Охорона праці і навколишнього середовища
HYPERLINK \l "_Toc234417432" 6.1 Основні питання охорони праці
HYPERLINK \l "_Toc234417433" 6.2 Промислова санітарія
HYPERLINK \l "_Toc234417434" 6.2.1 Мікроклімат
HYPERLINK \l "_Toc234417435" 6.2.2 Виробниче освітлення
HYPERLINK \l "_Toc234417436" 6.2.3 Шум
HYPERLINK \l "_Toc234417437" 6.2.4 Випромінювання від екрана
HYPERLINK \l "_Toc234417438" 6.3 Техніка безпеки на робочому місці
HYPERLINK \l "_Toc234417439" 6.3.1 Електробезпека
HYPERLINK \l "_Toc234417440" 6.3.2 Ергономічні вимоги до робочого місця
HYPERLINK \l "_Toc234417441" 6.4 Пожежна безпека
HYPERLINK \l "_Toc234417442" 6.5 Охорона навколишнього середовища
HYPERLINK \l "_Toc234417443" Висновки
HYPERLINK \l "_Toc234417444" Список джерел інформації
HYPERLINK \l "_Toc234417445" Додаток
HYPERLINK \l "_Toc234417446" Текст програми
HYPERLINK \l "_Toc234417447" Керівництво оператора
HYPERLINK \l "_Toc234417448" Опис програми
Вступ
На сьогоднішній день актуальна проблема зберігання й передачі інформації в цифровому виді. Для одержання компактних інформаційних подань застосовуються технології ощадливого кодування. Використання цих технологій дозволяє істотно знизити вимоги, пропоновані до обсягу інформаційних носіїв, а також відчутно збільшує швидкість передачі інформації з каналів зв'язку.
Передача інформації є основною областю застосування ощадливого кодування. На даний момент першочергове завдання - організація ефективного телевізійного й мультимедійного віщання. Як відомо, відеоінформація являє собою найбільш об'ємний тип інформації. З обліком обмеженої пропускної здатності цифрових каналів, щоб гарантувати високу якість передачі зображень, необхідно забезпечити їх досить ефективне подання (якість передачі прямо залежить від обсягу інформації, переданого в одиницю часу). Як наслідок, протягом уже більше 15 років значні зусилля направляються на розробку технологій ефективного подання зображень. Цій проблемі присвячена й дана дипломна робота.
Основна мета роботи - аналіз існуючих технологій одержання компактних подань відеоінформації з погляду способу організації кодування й пошук можливих шляхів підвищення їхньої ефективності.
Вибір напрямку дослідження заснований на результатах порівняльного аналізу існуючих алгоритмів ощадливого кодування. Алгоритм ощадливого кодування являє собою певний спосіб генерації ощадливого коду на основі наближеної моделі породження кодуємої інформації. З метою зниження обчислювальної складності на практиці довгий час застосовувалися спрощені методи інформаційного моделювання й генерації коду. Як моделі бралися найпростіші комбінаторні моделі, а генерація коду здійснювалася з використанням найбільш швидких реалізацій префіксного кодування. У цей час постановка завдання змінилася: на перший план стала всі частіше виходити ефективність кодування. Сьогодні стає доцільним застосування більше складних технологій кодування, які дозволяють досягти максимально компактного інформаційного подання.
Одним з найбільш ефективних методів інформаційного моделювання є імовірнісне контекстно-залежне моделювання. При використанні даного методу вибір інформаційної моделі в кожен момент часу здійснюється на основі значення деякого контексту, що формується з елементів уже обробленої інформаційної вибірки. Уводячи контексти, ми фактично вирішуємо завдання ідентифікації станів інформаційного джерела. Для кожної моделі зберігається статистична інформація про появу різних символів інформаційного алфавіту в контексті, що відповідає даної моделі. На основі цієї інформації формується розподіл імовірнісних оцінок появи символів на виході джерела, що є основою для генерації коду.
Арифметичне кодування являє собою найбільш ефективний метод генерації коду по заданому імовірнісному розподілі. Використання цього методу дозволяє одержувати коди, довжини яких мало відрізняються від теоретично оптимальних значень.
Таким чином, сполучення контекстно-залежного імовірнісного моделювання й арифметичного кодування найбільше вигідно з погляду ефективності. При цьому найбільш ефективним буде кодування інформації на основі аналізу її ентропійності - завдяки такому підходу, ми зможемо гарантувати зменшення обсягу відеоінформації, за умови зберігання достатнього рівня інформаційності, тобто зображення залишається досить чітким, але кількість кольорів зображення зменшується, при цьому чоловіче око може аналізувати цю інформацію на рівні із попередньою.
Тому в дипломній роботі приділимо увагу до кодування найпростішого виду відеоінформації - чорно-білого зображення, що дає можливість отримати основи алгоритмів для кодування більш складних видів зображень, як кольорові картинки та відео файли.
1. Імовірнісний підхід у теорії кодування відеоінформації
1.1 Інформаційний опис
Теорія ощадливого кодування займається проблемою створення ефективних подань інформаційної вибірки. Мова в більшості випадків іде про вибірку джерел дискретної інформації з кінцевим алфавітом. Ефективне кодування стає можливим завдяки наявності в інформації певних особливостей, тому однієї з найбільш важливих задач є одержання як можна більше точного опису властивостей інформаційних джерел.
Існує кілька підходів до такого роду опису. Найбільше часто використовувані - комбінаторний й імовірнісний.
У рамках комбінаторного підходу символи розглядаються не обособлено, а групами, іменованими інформаційними повідомленнями. Покладається, що з виходу джерела інформації можуть надходити не всі можливі повідомлення, а тільки повідомлення з деякого виділеної множини. При цьому повідомлення, що належати даній множині, уважаються зовсім рівнозначними, тобто їхня поява покладається рівноймовірним. Конкретний вибір множини припустимих повідомлень виконує роль інформаційного опису.
Комбінаторний підхід одержавши досить широке поширення на практиці. Основним його достоїнством є простота опису інформаційних особливостей, тому практичні реалізації методів ощадливого кодування, в основі яких лежить даний підхід, мають низьку обчислювальну складність.
Недолік полягає в тім, що точність опису годиною прямо залежить потужності множини припустимих повідомлень - для одержання досить точного опису може знадобитися розглянути дуже велика кількість повідомлень. Комбінаторний підхід також не дозволяє одержувати інформаційні характеристики для окремих символів усередині повідомлення.
Суть імовірнісного підходу полягає у використанні імовірнісних оцінок фактів появи різних символів на виході джерела інформації. У порівнянні з комбінаторним підходом імовірнісний підхід є більше точним способом опису властивостей інформаційних джерел. У тієї ж година імовірнісний підхід менш вигідний з обчислювальної крапки зору, тому що його застосування сполучене з обчисленням складних імовірнісних оцінок. Таким чином, з одному боку, імовірнісний опис, як правило, більш ефективно в порівнянні з комбінаторним описом, з іншого боку, імовірнісний опис не завжди можна використати на практиці через існуючі обчислювальні обмеження. Постійне збільшення продуктивності обчислювальних систем робить останній фактор менш значимим, внаслідок чого імовірнісний підхід останнім годиною всі частіше й частіше береться за основу при розробці алгоритмів ощадливого кодування.
1.2 Імовірнісний підхід
1.2.1 Ентропія
Основоположником імовірнісного підходу є Шеннон. Він запропонував ввести характеристику невизначеності інформації H (p1; p2; …; pN), що залежить від імовірностей p1; p2; …; pN появи символів алфавіту 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 (p1; p2; …; pk; pk+1; …; pk+l) = H (p1; p2; …; pk; ps) + psH (pk+1/ ps,…, pk+l/ps), де ps = сума від 1 до l (pk+1).
Як показав Шеннон, функція, що задовольняє зазначеним властивостям, має вигляд H (p1; p2; …; pN) = - K∑pi logm pi, де K та m - деякі позитивні константи. Для зручності пропонується вибирати K рівним одиниці, а в якості m брати основу системи подання інформації. Як показує практика, такий вибір багато в чому виправданий. Наприклад, у системі подання інформації з підставою 2 невизначеність появи одного із двох символів, що з'являються з рівною ймовірністю, виявляється рівної 1 біту. Це добрі погодиться з визначенням біта як одиниці інформації, необхідної для подання вибору одного із двох равновероятных подій. Таким чином, підсумкова формула для обчислення ентропії інформаційного джерела з імовірнісним розподілом появи символів {pi}Ni=1 виглядає в такий спосіб:
Формула (1.1) дозволяє визначити ентропію джерела, що перебуває в деякому конкретному стані. Ентропія джерела в цілому - безвідносно до конкретного стану - може бути визначена далеко не завжди. Можливість визначення ентропії залежить від імовірностей тихнув або інших станів і відповідних цих станів ансамблів перехідних імовірностей (перехід зі стану в стан здійснюється при породженням джерелом чергового символу). Розглянемо окремий випадок, коли інформаційне джерело S може перебувати в одному з T станів, причому чітко відомі всі ймовірності переходів джерела з будь-якого стану i у стан j (pij). Якщо існує межа , де Р - матриця з компонентами pi,j, величина ентропії джерела S може бути обчислена по формулі
Отут pi - імовірність знаходження джерела S в i-м стані (pi є значення i - елемента будь-якого рядка матриці P∞), a m - підстава системи подання інформації.
Множина станів інформаційного джерела в сукупності з ансамблем перехідних імовірностей прийнято називати моделлю станів або марковской моделлю. Для визначення ентропії джерела інформації в рамках даної моделі необхідно правильно підібрати її структуру й параметри, які повинні повною мірою відповідати джерелу. На практиці це досить важко, тому що параметри інформаційних джерел, як правило, апріорі не відомі1. Визначити їх можна тільки приблизно, тому при рішенні практичних задач доводити прибігати до емпіричних способів оцінки ентропії. Як правило, мова йде про усереднення величини ентропії за годиною.
Нехай джерело послідовно перебуває в станах s1, s2,..., sn, які відповідають розподілу ймовірностей появи символів
Через рі1, і2, іn позначимо ймовірність появи на виході джерела послідовності символів з індексами i1, i2,..., in (символ ik породжується джерелом у стані sk). Очевидно, що
Напівемпіричною ентропією джерела назвемо величину
З урахуванням тотожності (1.3) формула (1.4) приводитися до більше зручного для обчислення виду
Приставка "напів" означає, що для отримання ентропії частино використовуються апріорні дані про імовірнісні характеристики джерела (відомий розподіл імовірностей появи символів у різних станах), а частина, що залишилася, інформації - конкретна послідовність станів - виходить емпіричним шляхом. У реальних задачах, як правило, подібної апріорної інформації ні, тому доцільно ввести поняття емпіричної ентропії, визначивши її величину по формулі:
У цьому випадку ri (sj) - емпірична оцінка ймовірності появи символу з індексом i при породженні j-й вибірки джерела інформації1. Причина, по якій особлива увага приділяється способах обчислення ентропії, полягає в тім, що величина ентропії є чисельною границею ефективності ощадливого кодування вибірки інформаційного джерела. Знаючи ентропію, можна оцінити ефективність того або іншого методу або алгоритму. В ідеалі ефективність винна збігатися з величиною ентропією. При цьому, якщо природа інформаційного джерела не є імовірнісної, тобто чітко виділити ті або інші імовірнісні стани не можна, мова може йти тільки про ентропію, що обчислює частково на емпіричній основі. В силу останньої обставини, надалі при вживанні терміна ентропія найчастіше буде матися на увазі напівемпірична ентропія.
Обчислення ентропії на практиці можна здійснювати в процесі послідовного аналізу станів інформаційного джерела, що безпосередньо треба з формул (1.5) і (1.6). Як видно з наведених формул, величина ентропії складається з величин ентропії в станах, у яких послідовно перебуває джерело інформації. Таким чином, задача оптимального моделювання послідовної інформаційної вибірки зводиться до задачі створення оптимальної моделі породження символів у шкірному конкретному стані, що є істотним спрощенням. Як буде показаний нижче, подібне спрощення припустиме й відносно механізму генерації коду, тобто воно фактично припустимо відносно методу кодування в цілому.
1.2.2 Дешифровані коди
Найпростіший варіант кодування вибірки інформаційного джерела - установлення відповідності між конкретними символами алфавіту й кодами, що мають цілу довжину в одиницях подання інформації. Природно зажадати, щоб код, отриманий у результаті такого кодування, був дешифрованим, тобто по будь-якій комбінації кодів символів можна було б відновити закодоване повідомлення. Необхідна умова дешифруємості було запропоновано й доведене Макмілланом. Формулювання виглядає в такий спосіб: якщо система кодів із цілими довжинами {li}Ni=1 дешифровані, те виконується нерівність
де m - підстава системи подання інформації.
Виконання нерівності (1.7) спричиняє виконання більше важливої нерівності:
Для доказу досить скористатися опуклістю функції logm (x). Таким чином, ефективність дешифрованого посимвольного кодування обмежена величиною ентропії імовірнісного розподілу появи символів на виході інформаційного джерела.
Більше складний й у той же час найбільше ефективний варіант кодування має на увазі одержання кодів не для окремих символів, а для цілих повідомлень. Коди декодуємих повідомлень, мабуть, також повинні задовольняти нерівності Макміллана. При цьому оцінка ефективності з розрахунку на один символ повідомлення ускладнюється необхідністю проведення усереднення по довжині повідомлення. Покажемо, що ефективність кодування вибірки інформаційного джерела зазначеним способом також обмежується величиною ентропії.
Будемо використати раніше уведені позначення. Джерело, що послідовно перебуває в станах s1, s2,..., sn, як і раніше, характеризується імовірнісними розподілами
.
Через pi1, i2,..., in позначається ймовірність появи повідомлення "i1, i2,... in", через li 1, i2,..., in - довжина коду повідомлення. Ефективність кодування повідомлень довжини n з розрахунку на один символ визначається по формулі
Коди для повідомлень довжини n повинні бути дешифрованими, тому можна скористатися нерівністю (1.8):
Права частина нерівності являє собою вираження для ентропії. Таким чином, ефективність кодування з розрахунку на один символ не може перевершувати величину ентропії повідомлення, що доводити на один символ. Використовуючи формулу (1.5), одержуємо більше зручну з обчислювальної крапки зору оцінку:
Якщо джерело, що породжує повідомлення, є стаціонарним (імовірнісний розподіл не залежить від позиції символу в повідомленні), нерівність здобуває спрощений вид:
1.2.3 Оптимальна довжина коду
Тому що код виходить для повідомлення в цілому, не можна говорити про коди для конкретних символів, що становлять повідомлення. Проте виникає необхідність визначати деякий внесок у результуючу довжину коду повідомлення, внесень кожним вхідної в нього символом. Фізичний зміст такого внеску - середнє збільшення довжини коду повідомлення, обумовлене входженням у нього даного символу. Позначимо через xi внесок, внесень символом з індексом i (у загальному випадку величина внеску являє собою речовинне число). Через xi1, i2,..., in позначимо внесок, внесень повідомленням s = i1, i2,..., in - Виходячи зі змісту поняття "внесок", для випадку стаціонарної незалежної вибірки логічно зажадати виконання наступних властивостей:
(адитивність)
,
де li1, i2,..., in - довжина реального коду повідомлення (ціле число), а M (n) - ненегативна функція, така що M (n) /n - > 0 при n - > оо
Асимптотичне поводження функції M (n) /n дозволяє зробити висновок:
Таким чином, отримане узагальнення нерівності Макміллана на випадок внесків символів у результуючу довжину повідомлень.
Узагальнена нерівність (1.9) дозволяє обчислити точне значення величини внеску xa символу з індексом a для випадку оптимального кодування. Для обчислення точного значення необхідно вирішити задачу про мінімізацію суми
,
яка визначає середню ефективність кодування, за умови виконання нерівності (1.9). У крапці мінімуму похідна від зазначеної суми звертається в нуль:
Підстановка рішення задачі про мінімізацію в нерівність (1.9), мабуть, повинне перетворювати його в рівність. Звідси будь-який оптимальний внесок xk легко виражається через внески інших символів:
Підставляючи вираження для xk у рівняння (1.10), одержуємо
Після узяття похідної рівняння здобуває наступний вид:
, або
Індекс k може приймати одне з N значень, тобто реально для шкірного фіксованого індексу a є N рівнянь. Просумувавши ці рівняння, одержимо
що з урахуванням виконання рівності у вираженні (1.9) рівносильне
Звідси отримаємо формулу для xa:
Таким чином, оптимальний внесок символу, що з'являється з імовірністю p: у довжину результуючого коду становить logm p одиниць інформації в системі подання з підставою m. - анный висновок може бути використаний для обчислення оптимальної довжини коду в рамках тієї або іншої імовірнісної моделі. Одержуючи оцінку ймовірності появи чергового символу на деякому етапі кодування, можна точно визначити оптимальну довжину відповідного інформаційного опису.
1.3 Методи генерації коду
1.3.1 Префіксне кодування
Серед кодів, що задовольняють нерівності Макміллана, особливе місце займають префіксні коди. Система кодів називається префіксною, якщо жоден з кодів, що належить системі, не є качаном (префіксом) іншого коду із цієї ж системи. Очевидне достоїнство префіксного кодування полягає в тім, що одержуваний код може бути легко декодований. Завдяки властивості префікса для того, щоб визначити черговий закодований символ (повідомлення), досить проаналізувати качан відповідної чергової порції коду. При цьому довжина аналізованої порції ніколи не перевищує довжину коду чергового закодованого символу (повідомлення).
Геометрична трактування систем префіксних кодів - m-арные дерева. Властивість префікса гарантує відсутність циклів у графі, ребрам якого зіставлені різні значення інформаційної одиниці. Таким чином, граф є деревом зі ступенем розгалуження, що збігає з підставою системи подання інформації m. Слід зазначити, що нумерація ребер може бути здійснена довільним образом; значення має тільки конкретна структура дерева, а точніше - набір відстаней від кореневого вузла до листових вузлів. Ці відстані відповідають довжинам кодів префіксної системи. Крафт показав, що виконання нерівності (1.7) є гарантією існування кодового дерева зі структурою, що відповідає набору довжин , що фігурують у нерівності. Інакше кажучи, якщо система довжин задовольняє нерівності (1.7), можна побудувати систему префіксних кодів з відповідними довжинами. Дане твердження дозволяє відмовитися від розгляду систем кодів, відмінних від префіксних. Будь-яка система дешифрованих кодів задовольняє нерівності (1.7), а виходить, вона може бути без шкоди для ефективності замінена системою префіксних кодів. Нерівність (1.7) стосовно до систем префиксних кодів називають також нерівністю Крафта.
Розглянемо блокове кодування повідомлень довжини n, породжуваних деяким інформаційним джерелом. Як і раніше, позначимо через
імовірнісний розподіл появи j-ro символу повідомлення (sj - відповідний стан джерела), через pi1, i2,..., in - імовірність появи повідомлення "i1, i2,..., in". Відповідно до твердження Крафта, можна побудувати систему префіксних кодів із длинами
(Для доказу досить підставити ці довжини в нерівність Крафта й переконатися в тім, що воно виконується) Оцінимо ефективність кодування з розрахунку на один символ повідомлення:
Використовуючи альтернативне вираження для ентропії (1.5), одержуємо
Для випадку стаціонарного джерела з розподілом імовірностей
маємо:
Збільшуючи довжину повідомлення n, можна домогтися ефективності кодування як завгодно близької до ентропії джерела інформації. Таким чином, знаючи апріорі ймовірності появи різних символів на виході джерела в кожен конкретний момент часу, можна організувати кодування даного джерела, наближене до оптимального кодування на кожну наперед задану величину, за умови, що є достатній об'єм інформаційної вибірки.
1.3.2 Алгоритм Шеннона
Алгоритм побудови системи префиксних кодів з довжинами, що залежать від імовірностей по формулі , був запропонований Шенноном. Алгоритм працює в такий спосіб. Імовірності появи повідомлень p1,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), менш чим на одну інформаційну одиницю. Таким чином, різниця між ефективністю кодування й ентропією (так називана надмірність) не перевищує одиниці.
1.3.3 Алгоритм Хаффмана
Алгоритм Шеннона має досить високу ефективність, однак він не є оптимальним алгоритмом побудови системи префіксних кодів. Для знаходження оптимального алгоритму необхідно при фіксованому наборі ймовірностей {p1,p2,...,pn} вирішити задачу про мінімізацію суми за умови виконання нерівності Крафта (тут li - довжина коду повідомлення з індексом i).
На практиці алгоритм Хаффмана реалізується в такий спосіб. На початковому етапі кожному повідомленню ставиться у відповідність вага, дорівнює оцінці ймовірності появи даного повідомлення. Повідомлення містяться в список, що впорядковується по убуванню ваг. Надалі елементи списку обробляються з використанням ітеративної процедури. На кожному кроці (ітерації) m останніх елементів списку поєднуються в новий елемент, що потім міститься в список замість поєднуваних елементів. Новому елементу списку ставиться у відповідність вага, дорівнює сумі ваг елементів, що заміщають. Кожна ітерація закінчується впорядковуванням отриманого нового списку, що завжди містить на один елемент менше, ніж старий список. Паралельно з роботою зазначеної процедури здійснюється послідовна побудова m-арного дерева. На кожному кроці алгоритму будь-якому елементу списку відповідає кореневий вузол m-арного дерева, що складає з вершин, що відповідають елементам, об'єднанням яких був отриманий даний елемент. При об'єднанні m елементів списку відбувається об'єднання відповідних дерев в одне нове m-арне дерево, у якому кореневий вузол відповідає новому елементу, що поміщає в список, а заміщають елементам, що, списку відповідають дочірні вузли цього кореневого вузла. Алгоритм завершує роботу, коли в списку залишається один елемент, що відповідає кореневому вузлу побудованого бінарного дерева. Для гарантії коректного завершення роботи алгоритму вихідний розмір списку повинен мати довжину, представиму у вигляді n• (m-1) +1. Якщо кількість повідомлень не відповідає цій довжині, список доповнюється до необхідного розміру за рахунок додавання в кінець фіктивних елементів, що мають нульові ваги. Побудоване в результаті описаної процедури дерево називається деревом Хаффмана. Система префіксних кодів може бути отримана шляхом присвоєння конкретних m-арних значень ребрам цього дерева.
Алгоритм Хаффмана має найбільшу ефективність серед алгоритмів побудови префіксних кодів по заданому імовірнісному розподілі1. Очевидний недолік алгоритму - більша обчислювальна складність. Алгоритм доцільно використати в тих випадках, коли імовірнісний розподіл залишається незмінним для досить великого об'єму інформаційної вибірки. Застосування алгоритму Хаффмана у випадку, коли статистичні характеристики інформаційного джерела швидко міняються, сильно утруднено необхідністю здійснення частих змін структури кодового дерева. Галлагером був запропонований ефективний спосіб зміни структури дерева Хаффмана, не потребуючий його повної перебудови. Застосування даного способу хоча й приводить до істотного спрощення хутранизма генерації коду, проте не завжди дозволяє досягти необхідної швидкості обробки інформації. Тим же недоліком володіють і практичні реалізації алгоритму Шеннона.
1.4 Основні результати і висновки
У даній главі були докладно розглянуті різні аспекти імовірнісного підходу в теорії ощадливого кодування. Викладено методи побудови імовірнісних моделей, методи генерації коду змінної довжини на основі імовірнісних розподілів, методи одержання імовірнісних оцінок. Отримано наступні важливі результати:
Сформульовано й доведена нерівність Макміллана для випадку нероздільних кодів. Обчислено величину оптимального внеску символу в результуючу довжину коду повідомлення (див. розділ 1.2.3).
Алгебраїчно доведена оптимальність алгоритму Хаффмана для системи подання інформації з довільною підставою (див. розділ 1.3.3).
Наведені результати є серйозним внеском у теорію ощадливого кодування. Ці результати можуть бути використані при розробці й аналізі нових методів одержання ефективних подань інформації різної природи.
Нажаль, серед наведених алгоритмів нема ідеального для виконання ентропійного кодування відеоінформації. Тому у наступному розділі ми запропонуємо метод, та розробимо алгоритм і програму, яка буде виконувати стиснення зображення, з метою зменшити кількість кольорів у зображенні, але зберегти його інформаційність. Цей алгоритм також не буде ідеальним, але його можна застосовувати як швидкий і зручний спосіб стиснення зображення.
2. Розробка імовірнісних методів для підвищення ефективності кодування
2.1 Квантування
Ефективність ощадливого кодування природного напівтонового зображення (наприклад, фотографічного) методами, описаними в попередньому розділі, у середньому становить декілька бітів на одне закодоване значення колірної матриці. Стосовно до синтезованих зображень (такі зображення можуть містити текст, малюнки, графічні об'єкти й т.п.) ефективність виявляється трохи вище й іноді становить менш одного біта на закодоване значення. Однак існують технології кодування, що дозволяють домогтися істотно більшого результату. Висока ефективність досягається за рахунок того, що при кодуванні стають припустимими деякі інформаційні перекручування. Щоб перекручування були як можна менш помітні, їхні характеристики вибираються з урахуванням особливостей психовизуального сприйняття зображення людиною.
Перекручування найчастіше виникають внаслідок квантування значень інформаційної вибірки. Ідея квантування полягає в заміні всіх значень із групи (інтервалу) деяким єдиним значенням. Даний прийом дозволяє зменшити кількість різних значень, що зустрічаються в матриці, що дозволяє кодувати її більш ефективно. Інформаційні перекручування, мабуть, виникають через розбіжність групуємих значень зі значенням, отриманим у процесі їхнього квантування. Повне відновлення інформації стає, таким чином, неможливим.
Розвитком зазначеного підходу є метод у якому групуються не окремі значення, а цілі вектора, складені зі значень, що перебувають на близьких позиціях у матриці. Квантоване значення в даному випадку відповідає деякій множині векторів значень. Таке рішення представляє значно більше можливостей для інформаційного опису. Воно зветься векторне квантування, а розглянутий раніше спрощений варіант називається скалярним, квантуванням.
Як неважко помітити, векторне квантування частково виконує функції контекстно-залежного моделювання: об'єднання векторів значень, що перебувають на близьких позиціях, дозволяє врахувати можливі імовірнісні взаємозв'язки між ними. Тому векторне квантування, як альтернативний метод обліку інформаційних закономірностей, є предметом для окремого розгляду, і буде залишений за рамками даної роботи. Надалі мова йтиме тільки про ті методи кодування, у яких використається скаля...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора