МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

“ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра: “Обчислювальна техніка та програмування”

Реферат

Імовірнісні методи ощадливого кодування інформації

Харків 2009

Зміст

Вступ

1. Імовірнисний підхід у теорії ощадливого кодування

1. Оцінка інформативності ознак

1.2 Оптимальна градація ознак

1.3 Градація перших 100 чисел натурального ряду

1.4 Градація яркостей зображеннь

2. Застосування імовірнісних методів для підвищення ефективності ощадливого кодування відеоінформації

2.1 Загальна теорія

2.2 Методи із пророкуванням

2.3 Методи прогресивного кодування

2.4 Квантування

3. Ефективні алгоритми кодування інформації

3.1 Алгоритм медіанного перетину

3.2.1 Методи кластерізації для квантування зображення

3.2.2 Метод К-середніх

3.2.3 Метод связности графа

3.2.4 Іерархічний метод

3.2.5 Метод динамічних згущеннь

4. Висновок

Список джерел

Вступ

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

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

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

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

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

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

Таким чином, сполучення контекстно-залежного імовірнісного моделювання й арифметичного кодування найбільше вигідно з погляду ефективності.

1. Імовірнісний підхід у теорії ощадливого кодування

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

Існує кілька підходів до такого роду опису. Найбільше часто використовувані - комбінаторний й імовірнісний.

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

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

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

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

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

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

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

Нехай матриця з позитивними елементами , що має рядків і стовпців і нехай . Для кожної матриці можна визначити функцію

, (1)

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

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

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

На першому кроці з використанням міри близькості

виявилося можливим розбити всю сукупність характеристик квітів ірису на два кластери по ступені їхньої близькості до виділених елементів по алгоритму. Отримані в результаті кластери, перший - квіти virginic й versicol, другий - квіти setosa. На другому кроці після проведення аналогічної процедури для даних першого кластера спостерігалися 9 помилок, які розподілилися між класами (квітами) як 5 до 4.

Рис.1 Графік зміни компонент вектора для всієї вибірки характеристик квітів ірису.

Загальні результати класифікації, представлені у вигляді матриці переплутування

.

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

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

.

Легко перевірити, що

1. ;

2.

3. .

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

і шуканий інформаційний критерій

,

де ( ) і ( ) -заелементні операції розподілу й множення відповідно.

Область визначається умовами розв'язуваного завдання. Приведемо приклади використання формули (7). Почнемо із простого випадку. Нехай перетворення полягає в заміні вихідного вектора вектором . Тоді область обмежень визначиться співвідношеннями , а величина - рівністю

,

звідки треба, що максимально можлива кількість інформації втримується в тотожному перетворенні й дорівнює

,

що й випливало очікувати.

Розглянемо більше складні й практично важливі приклади.

1.2 Оцінка інформативності ознак

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

З погляду змісту поняття «інформативність», можна дати наступне визначення: інформативна ознака - це ознака, що має близькі значення на елементах (об'єктах) одного класу й істотно різні значення на елементах різних класів.

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

.

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

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

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

Таблиця 1 - Результати оцінки інформативності ознак квітів ірису

Властивості ознаки	Ознаки
	чашолисток		маточка
	довжина	ширина	довжина	ширина
Інформативність	0,0126	0,0079	0,3205	0,8158
Відносний діапазон зміни	0,6116	0,3980	5,0146	12,1539

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

Рис. 2 - Графіки зміни ознак квітів ірису

1.3 Оптимальна градація ознак

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

Нехай - вектор-стовпець речовинних позитивних чисел упорядкованих по зростанню. Потрібно розбити всі його значень по ступені близькості на груп по значень у кожній ( , ). Позначимо . Тоді для завдання область є .

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

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

Градація перших 100 чисел натурального ряду. У табл. 2 наведені результати градацій цих чисел. Відзначимо, що при відносна величина порога 0,21 близька до золотого перетину 0,168.

Таблиця 2 - Результати градації перших 100 чисел натурального ряду

Кількість градацій до	граничні значення
2
3
4
5
10

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

1.4 Градація яркостей зображень

Відзначений у п. 1 факт можна використати для градації зображень, коли необхідно більше «часто» градуювати ті області яркостей пикселей, розходження яких необхідно підкреслити. Наприклад, яскраві значення пикселей, а не темних, оскільки око більше чутливе до сприйняття світлих ділянок зображень. Для цього досить перейти до градуировке зображення з матрицею яскравості пикселей , рівного , де - матриця, всі значення якої дорівнюють максимальному значенню матриці вихідного зображення . Для стислості такий метод градації назвемо «зворотним», на відміну від градації вихідного зображення, що ми назвемо «прямим».

На мал.1 представлені результати 4-х уровневой (2 біти) градації яркостей пикселей зображення «Роза». В інтересах зіставлення на всіх 4-х зображень (включаючи вихідне) сума яркостей пикселей однакова.

Як видно, при рівномірному, не оптимальному, розбивці спостерігаються нечисленні артефакти, «прямий» метод показав гарну чутливість до малих значень пикселей, «зворотній» - виділив всі яскраві ділянки вихідного зображення.

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

4-х рівневі градуйовані зображення
рівномірна розбивка	пропонований метод
	«прямий»	«зворотній»
Вихідне зображення	Графіки зміни критерію інформативності
	«прямий» метод	«зворотній» метод

Рис.1 Результати градації зображення «Роза»

Тепер розглянемо методи, якими можна обробити зображення.

2.Застосування імовірнісних методів для підвищення ефективності ощадливого кодування відеоінформації

2.1 Загальна теорія

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

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

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

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

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

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

2.2 Методи із пророкуваннями

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

Тому помилки пророкування можуть бути дуже ефективно закодовані.

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

Імовірність появи целочисленной помилки ε виходить шляхом інтегрування щільності імовірнісного розподілу ρ(x) в околиці [ε- ½, ε + ½]:

ε+1/2

p(ε) = / ρ(x)dx.

ε-1/2

Як правило, за основу береться розподіл Лапласа, щільність якого обчислюється по формулі

ρ (x) = ~т2 σ ² exp(-в -2 \x - µ\)).

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

2.3 Методи прогресивного кодування

З метою спрощення моделювання при формуванні факторного вектора, як правило, використаються тільки ті значення матриці, які перебувають на сусідні (примыкающих) позиціях стосовно кодируемой позиції. Таким чином, у розрахунок не приймаються значення, що перебувають на деякому видаленні. Таке рішення невигідно, тому що між вилученими крапками зображення також можуть існувати залежності, які ніяк не враховуються. Для обліку цих залежностей можна використати методику, при якій зображення кодується в прогресивному режимі: спочатку кодуються крапки зображення, що утворять мережу з деяким досить більшим кроком; потім кодуються ще незакодовані крапки, що належать мережі з меншим кроком, і так далі, доти, поки не будуть закодовані всі крапки зображення (кодування в більшості випадків є контекстно-контекстно-залежним). Одним з переваг описаної методики є можливість відновлення зображення з послідовним поліпшенням його деталізації, що може мати особливу цінність при її використанні в телекомунікаційних додатках¹. Один з найбільш удалих методів прогресивного кодування описаний у роботі. До методів прогресивного кодування ставляться також методи, засновані на застосуванні оборотних вейвлет-преобразований. Крім усього іншого, прогресивний режим вносить елемент завадостійкості.

2.4 Квантування

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

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

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

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

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

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

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

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

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

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

3. Ефективні алгоритми кодування відеоінформації

3.1 Алгоритм медіанного перетину

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

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

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

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

Наступний крок виконується після формування N паралелепіпедів і покликаний заповнити палітру. Палітра заповнюється або центральними крапками паралелепіпедів, або середніми арифметичними значень, що потрапили в дані паралелепіпеди.

Далі проводиться процедура знаходження відповідного паралелепіпеда для даного значення атрибута вихідного зображення й заміни значення на нове.

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

Часто реалізації алгоритму використають спеціальні структури для зберігання розбивки колірного простору. Прикладом такої структури може служити BSP дерево.

Результати роботи алгоритму є дуже гарними, при цьому швидкість роботи даного алгоритму висока. Різні варіації даного алгоритму використаються у відомих додатках для обробки зображень, наприклад в GNU ImageManipulation Program (GIMP).

3.2.1 Методи кластерізації для квантування зображень

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

3.2.2 Метод K-середніх

Це один із самих популярних алгоритмів для кластеризации. Зафіксуємо число K- розмір палітри - і будемо розбивати всі значення атрибутів зображення на K кластерів.

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

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

3.2.3 Метод связности графа

Побудуємо матрицю відстаней D між значеннями атрибутів вихідного зображення. Як відстань можна взяти квадрат евклідової метрики. Потім виберемо число T - поріг. Після цього побудуємо матрицю B по матриці D за наступним правилом:

Матрицю B можна розглядати як задає ребра в графі, у якому вершинам відповідають пиксели зображення. Таким чином, зв'язні області графа задають кластери. Для формування кластерів можна використати хвильовий алгоритм. Покладемо в кожну вершину графа додаткове число.

Нехай це число дорівнює 0. Далі вибираємо випадкову вершину й "підпалюємо" її, тобто кладемо в неї число 1. Потім для кожної вершини, що з'єднана ребром з обраної, кладемо 1. Після цього те ж саме робимо для зв'язних сусідів вершин, куди вже поклали 1, - їм також кладемо число 1, і т.д. Таким чином, ми запустили хвилю. Коли вона зупиниться, це означає, що отримано всі значення кластера. Далі, варто вибрати випадково ту вершину, що не потрапила в кластер, тобто зберігає 0. І запустити для неї хвильовий алгоритм, наприклад, із числом 2. Проробивши таку процедуру кілька разів, одержимо розбивку на кластери. У палітру варто покласти центри кластерів, що вийшли.

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

3.2.4 Ієрархічний метод

Припустимо, що в зображенні n пикселей і кожний з них утворить свій кластер. Зв'яжемо із кластером величину, називану центром ваги кластера. Для кластера, що складає з одного значення, центром ваги є саме значення (у нашому випадку, значення атрибута пикселя). Побудуємо матрицю відстаней D між кластерами. Як відстань береться, наприклад, квадрат евклідової метрики між центрами ваги кластерів. Потім виберемо число T - поріг і пари кластерів (i*, j*) так, щоб (i*, j*) = arg min_(i,j) d_ij (т. е, щоб d_i*j* було мінімальним у матриці). Об'єднаємо кластери, що відповідають i* й j*, поклавши центром ваги нового кластера напівсуму центрів ваги поєднуваних кластерів. Таким чином, одержимо n-1 кластерів. Для цих кластерів також побудуємо матрицю відстаней D^* і знову знайдемо пару, що має мінімальна відстань між центрами ваги. Замінимо знайдену пару одним кластером, обчисливши його центр ваги. Отже, одержимо n - 2 кластерів і т.д.

Ми можемо зробити максимум n - 1 ітерацію. У такому випадку після останньої ітерації ми одержимо тільки один кластер. Щоб одержати K кластерів, потрібно зробити n - K ітерацій.

Даний метод дозволяє знаходити нетривіальні кластери, однак час його роботи дуже велико, до того ж утруднена процедура обробки кластерів для великого об'єму вхідних даних.

3.2.5 Узагальнений метод K-середніх або метод динамічних згущень

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

Припустимо, що представник кластера - це не одиночне значення, а ядро, що володіє наступними властивостями:

1. по представнику можна ідентифікувати кластер;

2. по кластері обчислюється представник.

Приклад: представник - два значення. Даний представник задовольняє першій властивості, тому що можна коректно визначити відстань від об'єкта, що складає із двох значень, до об'єкта з одного значення. Друга властивість також виконується, якщо застосувати простий алгоритм K-середніх з K = 2, тобто розбити кластер на два, а потім вибрати як представник вихідного кластера центри получившихся двох подкластеров.

Інші приклади представників: кілька значень, відрізки, різноманітні геометричні фігури.

Далі узагальнений алгоритм повторює стандартний алгоритм K-середніх: спочатку сформувати K кластерів по випадково обраних ядрах, потім итерировать процес формування K нових ядер і перерахування кластерів доти, поки кількість переміщень не стане досить малим.

4. Висновок

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

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

Список використаних джерел інформації

1. Айвазян С.А., Мхитарян.В.С. Прикладная статистика и основы эконометрики.- М.: Юнити. 1998.-1022 с.

2. Дидэ Э. и др. Методы анализа данных / под ред Айвазяна С.А. и Бухштабера В.М. — М.: Финансы и статистика, 1985. — 357с.

3. Кричевский Р. Е. Сжатие и поиск информации. - М.: Радио и связь, 1989.

4. Куренков Н.И. Ананьев С.Н. Энтропийный подход к решению задач классификации многомерных данных. // Информационные технологии. 2006. № 8. С. 50-55.

5. Левенштейн В. И. Об избыточности и замедлении разделимого кодирования натуральных чисел // Проблемы кибернетики. - М., 1968. - Вып. 20. - С. 173 - 179.

6. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфа­витами // Проблемы передачи информации. - 1999. - Т. 35, Вып. 4. - С. 95 - 108.

7. Семенюк В. В. Применение вероятностного моделирования в методах экономного кодирования видеоинформации // Труды XI Всероссийской научно-методической конференции Теле-матика'2004. - Санкт-Петербург, Россия, 7-10 июня, 2004. -С. 186 - 187.

8. Сакоян С.А. Об оптимальных разбиениях на градации в задачах классификации //Прикладная статистика -М.: Наука, 1983. —С.179-188.

9. Семенюк В.В. Экономное кодирование дискретной информации.-СПб: СПб ГИТМО (ТУ), 2001. - 115 с, - ISBN 5-7577-0076-9.

10. Хаффмен Д. А. Метод построения кодов с минимальной избыточностью: Пер. с англ. // Кибернетический сборник. - М.: ИЛ, 1961. - Вып. 3. - С. 79 - 87.