Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика->Реферат
Ряды данных – это наборы значений, которые требуется изобразить на диаграмме. Например, при построении диаграммы дохода компании за последнее десятиле...полностью>>
Информатика->Реферат
Представленная курсовая работа разработана среде программирования Delphi 6 от Borland. Данный программный продукт предоставляет широкие возможности дл...полностью>>
Информатика->Реферат
2.)Также я попробовал дать такое название переменной, которое начиналось бы с какого-либо синтаксического знака (например &), система выдала ошибку: S...полностью>>
Информатика->Реферат
В комплект поставки Windows NT входит сервис удаленного доступа Remote Access Service (RAS). Удаленный доступ - это частный случай соединения компьюте...полностью>>

Главная > Дипломная работа >Информатика

Сохрани ссылку в одной из сетей:

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 Квантування

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

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

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

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

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

Позначимо через ∆ довжину інтервалу при рівномірному квантуванні {параметр квантування). Сукупність інтервалів представима у вигляді [x0+∆-i, x0+∆- (i + 1)). Значення x0 належить речовинному інтервалу [-∆/2, /2) і задає базовий зсув інтервалів при квантуванні. i приймає довільні цілочисельні значення і являє собою номер інтервалу.

Номер інтервалу виступає в ролі кодуємого об'єкта. У процесі декодування по ньому відновлюється шуканий інтервал значень (деквантування). Тому що конкретні значення відновленню не підлягають, при деквантуванні вони заміняються деяким фіксованим числом. Оптимально використати як дане число математичне очікування значень інтервалу. У випадку, коли значення розподілені рівномірно, математичне очікування відповідає середині інтервалу - x0+∆•i+∆/2.

Квантуєма інформаційна вибірка часто представлена числами зі знаком, симетрично розподіленими щодо нуля. Маленькі по абсолютній величині значення звичайно не грають визначальної ролі - їхнє перекручування залишається практично непомітним для нашого сприйняття. У подібних ситуаціях базовий зсув інтервалу x0 має сенс вибирати рівним - ∆/2. При такому виборі значення в околиці [-∆/2, /2) будуть замінятися нулями (так називана мертва зона). З метою поліпшення схеми квантування розмір мертвої зони збільшують, залишаючи незмінними розміри інших інтервалів. Крім підвищення ефективності це дозволяє спростити процедуру квантування: якщо вибрати розмір мертвої зони рівним 2∆, визначення номера інтервалу при квантуванні зведеться до ділення квантуємого значення на параметр квантування. Дане рішення використається в багатьох практичних додатках, зокрема, у стандартах кодування відеоінформації JPEG, JPEG2000, MPEG, Н.261, Н.263.

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

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

2.2 Побудова інформаційного критерію

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

Нехай матриця з позитивними елементами

,

що має рядків і стовпців і нехай

.

Для кожної матриці можна визначити функцію

, (2.1)

де - транспонована матриця, елементи якої є зворотними значеннями елементів матриці .

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

.

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

Можливість використання властивостей вектора для рішення завдання кластерізації даних квітів ірису на три класи - virginic, versicol й setosa з покажемо на прикладі. На рис.2.1 показаний графік значень компонент вектора для всієї вибірки. Як видно найбільші значення компонентів вектора відповідають двом елементам: [7,2 3,6 6,1 2,5] ; [4,3 3,0 1,1 0,1].



Загрузить файл

Похожие страницы:

  1. Системи когенерації енергії

    Реферат >> Промышленность, производство
    ... і теплову енергію в централізованих системах теплозабезпечення (у вигляді пару і гарячої ... газотурбінної установки. В системах з замкненим тепловим циклом процеси ... іни з триступеневим розширенням і двоступеневим стисненням і процесом рекуперації. Рис. 9. ...
  2. Система живлення ВАЗ-2121

    Курсовая работа >> Транспорт
    ... палива "L-Jetronic” із карбюраторною системою живлення. Система живлення дизелів має відпов ... багато автомобілів іноземного виробництва із системою впорскування палива (інжектором). Застосування карбюратор ... об’єм,л 1.69 Степінь стиснення 83 Потужність,кВт 58 ...
  3. Система обробки аудіоінформації. Підсистема фільтрації і обробки сигналу

    Дипломная работа >> Информатика, программирование
    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 11 1. РОЗРОБКА СИСТЕМИ ОБРОБКИ Аудиоинформация ... ... 14 1.1. Обґрунтування ... Функціональне призначення системи .. 20 1.3.3. Особливості системи та умови її ...
  4. Система охолодження ВАЗ-2107

    Курсовая работа >> Транспорт
    ... можна встановлювати і з двигунів 2108. система охолодження вентилятор термостат / —- крильчатка; ... водою і підводять у радіатор стиснене повітря під тиском 1 кгс/ ... навколишнього середовища, технічного обслуговування системи охолодження, її неполадки та методи ...
  5. Система запалювання від магнето

    Реферат >> Транспорт
    ... . Завдання : - визначити призначення та принцип дії системи запалювання від магнето - охарактеризувати особливості конструкц ... ів, кількості ділянок дотикання та сили їх стиснення. Параметром, що використовується для ...

Хочу больше похожих работ...

Generated in 0.0017938613891602