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

е+1/2

p(е) = / с(x)dx.

е-1/2

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

с (x) = ~т2 у 2 exp(-в -2 \x - µ\)).

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

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

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

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) dij (т. е, щоб di*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.

Страницы: 1, 2, 3