Удосконалення математичної моделі прихованого марковського дерева в задачах попередньої обробки та компресії зображень

Размещено на http://www.allbest.ru/

Національний університет “Львівська політехніка”

УДК 519.713+004.932

Удосконалення математичної моделі прихованого марковського дерева в задачах попередньої обробки та компресії зображень

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Капшій Олег Вірославович

Львів 2006

Дисертацією є рукопис

Робота виконана у Фізико-механічному інституті ім. Г.В.Карпенка НАН України.

Науковий керівник: доктор технічних наук, професор Русин Богдан Павлович завідувач відділу методів і систем обробки, аналізу та ідентифікації зображень Фізико-механічного інституту ім. Г.В.Карпенка НАН України, м.Львів

Офіційні опоненти: доктор технічних наук, професор Матвійчук Ярослав Миколайович професор кафедри теоретичної радіотехніки та радіовимірювань Національного університету "Львівська політехніка", м.Львів

кандидат технічних наук, доцент Биков Микола Максимович професор кафедри комп'ютерних систем управління Вінницького національного технічного університету, м.Вінниця

Провідна установа: Інститут кібернетики ім. В.М.Глушкова НАН України, відділ керуючих машин та систем, м.Київ

Захист відбудеться “23” червня 2006 р. о 15⁰⁰ годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, Львів-13, вул.С.Бандери, 12).

З дисертацією можна ознайомитися у бібліотеці Національного університету “Львівська політехніка” (79013, Львів-13, вул.Професорська,1).

Автореферат розісланий “19” травня 2006 р.

Вчений секретар спеціалізованої

вченої ради, д.т.н., проф. Бунь Р.А.

загальна характеристика роботи

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

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

Розвинуті у даній роботі положення базуються на доробку таких вчених, як Р.Баранюк, Р.Новак, М.Крузо, Б.Русин, В.Лукін, В.Кожем'яко, Є.Путятін, В.Тихонов, У.Претт, Т.Павлідіс, М.Шапіро, А.Ортега, К.Рамчандран, К.Шенон і інші.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною досліджень, що проводились у рамках виконання держбюджетних тем: “Розробка методів автоматичного експрес-аналізу параметрів мікроструктури конструкційних матеріалів” (номер державної реєстрації 0102U002670), “Розробка інформаційних технологій реконструкції і кількісного аналізу тривимірних зображень поверхні зламів конструкційних матеріалів” (номер державної реєстрації 0105U004310), де автор брав участь як виконавець.

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

Для досягнення поставленої мети у роботі розв'язано наступні задачі:

- проведено аналіз існуючих математичних моделей статистичного опису даних у вейвлет-просторі та методів, що їх використовують;

- розроблено метод швидкого визначення параметрів моделі прихованого марковського дерева;

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

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

- застосовано модель прихованого марковського дерева до задачі втратної компресії даних та збільшено швидкодію розробленого алгоритму компресії.

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

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

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

Наукова новизна одержаних результатів полягає у наступному.

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

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

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

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

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

Практичне значення одержаних результатів.

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

Реалізація науково-технічних результатів. Теоретичні та практичні результати, отримані у дисертаційній роботі, використано в науково-дослідних роботах відділу “Методів та систем обробки, аналізу та ідентифікації зображень” Фізико-механічного інституту ім. Г.В.Карпенка НАН України, у навчальному процесі на кафедрі телекомунікацій Національного університету “Львівська політехніка” при викладанні дисциплін “Цифрова обробка сигналів” та “Системи розпізнавання”. Результати роботи реалізовані у вигляді модулів спеціального програмного забезпечення та впроваджені у ВАТ “Укртелеком”, Науково виробничому приватному підприємстві “РТФ” та Львівському центрі Інституту космічних досліджень НАН України та НКА України, що засвідчено актами впровадження.

Особистий внесок здобувача. Усі результати, що складають основний текст роботи, отримані автором самостійно. У працях, написаних у співавторстві, здобувачеві належать: розробка структури та реалізація системи стиску дактилоскопічних зображень із втратами на основі вейвлет-перетворення [6]; алгоритми виділення інформаційних фрагментів з використанням інформації простору кольору зображення [2]; метод визначення законів густин розподілів окремих вейвлет-коефіцієнтів з використанням параметрів глобальної моделі прихованого марковського дерева, ідея накладання апріорних обмежень на дисперсії сумішей гаусіан [4, 12]; метод визначення початкового наближення значень параметрів моделі прихованого марковського дерева шляхом апроксимації сумішей гаусіан за допомогою узагальненого гаусівського закону розподілу [9]; модель сумісного опису коефіцієнтів вейвлет-підсмуг одного типу різних кольорових смуг замість сумісного опису коефіцієнтів вейвлет-підсмуг різного типу одного кольору [10]; метод порівняння моделей прихованих марковських дерев шляхом визначення відносної ентропії сумішей гаусіан, а також ідея використання додаткової контекстної інформації та врахування інформації про правдоподібність появи точок зображення по всіх вейвлет-підсмугах окремо, а не загалом у блоці грубої класифікації точок текстурного зображення [5].

Апробація результатів дисертаційної роботи. Результати досліджень та основні положення роботи доповідались та обговорювалися на:

- VI міжнародній конференції УкрОбраз'2002, Київ, 2002;

- XVIII та XIX відкритих науково-технічних конференціях молодих науковців і спеціалістів Фізико-механічного інституту ім. Г.В.Карпенка НАН України, КМН-2003 та КМН-2005 у Львові;

- III міжнародній конференції по оптико-електронним інформаційним технологіям "Фотоніка-ОДС 2005", Вінниця, 2005;

- IX міжнародній науково-практичній конференції "Системи і засоби передачі і обробки інформації", Черкаси, 2005;

- II міжнародній науково-технічній конференції "Сучасні комп'ютерні системи та мережі: розробка та використання" ACSN'2005, Львів, 2005;

- Науково-практичній конференції "Сучасні проблеми телекомунікацій - 2005". Львів, 2005.

Публікації. Основні результати дисертаційної роботи опубліковано у 12 наукових працях, з них 5 статей у наукових фахових виданнях із переліку, затвердженого ВАК України.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, переліку літературних джерел (105 найменувань) і додатків. Загальний обсяг роботи - 151 сторінка, у тому числі 28 рисунків та 7 таблиць.

Основний зміст ДИСЕРТАЦІЙНОЇ роботи

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

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

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

Густина розподілу значень вейвлет-коефіцієнтів даних в багатьох випадках має великий пік близько нуля та довгі спадаючі хвости, тобто дуже сильно відрізняється від гаусівського закону розподілу. Для опису такої густини розподілу, у моделі прихованого марковського дерева, кожному вейвлет-коефіцієнту ставиться у відповідність дві випадкові змінні: прихована та вейвлет-змінна. Прихована змінна S приймає два значення m=1..2 з імовірністю p(S=m) та визначає чи мале , чи велике значення дисперсії у гаусівського закону з нульовим матсподіванням , який описує імовірність появи значень вейвлет-змінної W. В результаті, густина розподілу значень вейвлет-коефіцієнта визначається зваженою сумішю двох гаусівських розподілів. За відомого значення прихованої змінної вважають, що вейвлет-змінна є незалежною від інших коефіцієнтів.

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

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

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

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

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

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

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

Запропонована методика апроксимації суміші двох гаусівських законів розподілу узагальненим гаусівським розподілом дозволила, також, побудувати метод оцінки значення ентропії суміші двох гаусіан, яку не можна визначити у аналітичному вигляді. У методі використано той факт, що ентропія УГР записується у аналітичному вигляді через відомі значення параметрів розподілу. Тому запропоновано робити оцінку ентропії суміші гаусівських законів розподілу шляхом визначення ентропії УГР, який апроксимує суміш. Тобто розв'язується задача пошуку значень параметрів УГР при відомих значеннях параметрів суміші гаусіан. Як і у випадку визначення значень параметрів суміші гаусіан за відомими параметрами УГР, критерієм якості апроксимації виступає відносна ентропія. Оскільки поставлена задача не має аналітичного розв'язку, використовуються чисельні методи. Розрахунок виконується для наперед визначеного дискретного діапазону значень параметрів суміші. На рис.2 показано отримані залежності коефіцієнта форми УГР від параметрів p(S_j=1) та суміші гаусіан.

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

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

Аналіз методу фільтрації на основі моделі прихованого марковського дерева показав, що він є гіршим порівняно з іншими методам, в першу чергу, через наявність наступних недоліків: по перше, модель не враховує зв'язків між сусідніми в межах однієї підсмуги коефіцієнтами, а по друге, для всіх коефіцієнтів окремих вейвлет-підсмуг використовуються однакові параметри законів розподілу. Зокрема однаковими є дисперсії умовних гаусівських законів розподілу моделі, при оцінці значень незашумлених вейвлет-коефіцієнтів даних, спотворених адитивним білим гаусівським шумом. Оцінка проводиться згідно стандартного, в таких випадках, виразу: , де - оцінка значення неспотвореного вейвлет-коефіцієнта рівня j, розміщеного за координатами i,k підсмуги (в одномірному випадку використовується лише i), за умови відомих значень коефіцієнтів вейвлет-піраміди зашумлених даних, зокрема зашумленого коефіцієнта за цими ж координатами ; - апостеріорна імовірність появи значення прихованої змінної S_i,k,j коефіцієнта за умови відомих значень коефіцієнтів та параметрів моделі , обчислюється для кожного коефіцієнта; - згідно властивостей дисперсій гаусівських даних зашумлених адитивним білим гаусівським шумом; - дисперсії гаусіан суміші, яка характеризує розподіл значень зашумлених вейвлет-коефіцієнтів підсмуги j-го рівня розкладу; - енергія шуму, оцінена за значеннями коефіцієнтів найдетальнішого рівня розкладу.

Для усунення недоліків запропоновано метод зміни структури моделі прихованого марковського дерева з відомими параметрами на етапі її застосування до задачі фільтрації зображення. Перш за все, змінено методику визначення апостеріорної імовірності появи значень прихованих змінних. Запропоновано проводити її обчислення не на основі відомих значень вейвлет-коефіцієнтів всієї піраміди , а з використанням відомих значень лише околу вейвлет-коефіцієнта , який відповідає прихованій змінній S_i,k,j, тобто , де N - половина розміру вікна околу коефіцієнта. Але в такому випадку імовірнісними зв'язками моделі є пов'язані лише кілька коефіцієнтів з , які розміщені під . Інші коефіцієнти пов'язуються через вищі коефіцієнти дерева, які не враховуються в околі. Для того, щоб врахувати і їх, модифікується структура дерева моделі шляхом введення додаткових зв'язків між та непов'язаними коефіцієнтами. Приймається, що предок коефіцієнта w_i,k,j має зв'язок з його околом через гілку з вагою рівною вазі гілки зв'язку самого коефіцієнта з предком. Відповідно, імовірність сумісної появи значень вейвлет-коефіцієнтів околу за виключенням самого коефіцієнта w_i,k,j, при відомому значенні прихованої змінної предка визначається за допомогою виразу:

.

Імовірність появи значення прихованої змінної предка коефіцієнта при відомому значенні прихованої змінної коефіцієнта визначається за правилом Байєса:

.

Тоді імовірність появи значень вейвлет-коефіцієнтів околу та предка, при відомому значенні прихованої змінної коефіцієнта, визначається як

.

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

.

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

.

В результаті, дисперсії гаусіан суміші визначаються з виразу , розв'язком якого є

.

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

Таблиця 1

Результати фільтрації. Пікове співвідношення сигнал/шум, дБ

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

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

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

Врахувавши, що основна інформація про різкі зміни яскравості зображення, які в першу чергу й визначають його геометричне наповнення, закодована у високочастотних підсмугах LH, HL та HH, запропоновано проводити часткову реконструкцію підсмуги LL для кожного рівня вейвлет-розкладу, прийнявши, що низькочастотна копія зображення попереднього рівня розкладу рівна нулю:

,

де x,y - координати підсмуги LL; та - базисні масштабуюча та вейвлет-функції перетворення; N_j-1 - розмір сторони підсмуги рівня розкладу j-1; - коефіцієнти підсмуг відповідних типів рівня j-1; .

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

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

Остання частина третього розділу дисертаційної роботи присвячена удосконаленню, базованих на апараті прихованих марковських дерев, алгоритмів сегментації текстурних зображень. Зокрема розглянуто алгоритм сегментації напівтонових текстурних зображень. Вхідними даними алгоритму є зображення I та кількість типів текстур L, які на ньому присутні. Алгоритм базується на можливості обчислення для будь-якого піддерева T_i,k,j вейвлет-піраміди зображення імовірності появи значень вейвлет-коефіцієнтів цього піддерева за умови відомих параметрів моделі дерева . Імовірність обчислюється за допомогою рекурсивої формули, яка опрацьовує вейвлет-коефіцієнти T_i,k,j починаючи з найдетальніших. Спочатку в алгоритмі проводиться грубий поділ зображення на області з різними характеристиками, який базується на тому факті, що різні текстурні області по різному вписуються у модель прихованого марковського дерева з параметрами визначеними за цілим зображенням. Тобто для точок, що належать одному типу текстури є близькими, а для точок областей різних типів текстур - значно відрізняються. Далі, за точками зображення, які відповідають кожному типу, визначаються параметри моделей, які найкраще описують відповідний тип текстури l. Кожна точка зображення маркується тим типом, до якого вона належить з більшою імовірністю, обчисленою за допомогою рекурсивних виразів моделей кожного типу текстури . При цьому, для кожного коефіцієнта вейвлет-піраміди визначається контекстна змінна, яка містить інформацію про мажоритарний клас околу коефіцієнта на поточному та вищому рівнях розкладу, що накладає апріорні обмеження підвищуючи надійність роботи алгоритму сегментації. Останні два кроки алгоритму: визначення параметрів моделей текстур за віднесеними до них точками та сегментація згідно максимуму правдоподібності належності точки до моделі текстури, ітераційно повторюються до тих пір, поки не перестануть змінюватися типи текстур точок зображення.

Точність роботи описаного алгоритму сегментації значною мірою залежить від похибок блоку початкового грубого поділу областей зображення на класи. Грубий поділ проводиться для рівнів вейвлет-піраміди з номерами j=3,4. Це пояснюється тим, що коефіцієнти цих рівнів, а також піддерева T_i,k,j, які з них починаються, містять інформацію про властивості деякої області вхідного зображення, що є важливим при обробці текстур. Вейвлет-піраміди складені з коефіцієнтів підсмуг різних типів LH, HL та HH вважаються некорельованими, що дозволяє формувати для них незалежні моделі прихованого марковського дерева та обчислювати імовірність появи вейвлет-коефіцієнтів будь-якої області зображення через добуток імовірностей появи піддерев різних типів, що відповідають цій області. Відповідно, критерій грубої класифікації - імовірність появи даних певної області зображення за відомих параметрів моделей відповідних їй дерев різних типів B{LH,HL,HH}, визначається як . Класифікація починається шляхом розбиття гістограми імовірностей z_i,k,j на L відрізків за допомогою методу К-середніх та встановлення кожній області зображення відповідного до відрізку, в який вона попадає, типу текстури. Далі, границі розбиття уточнюються шляхом моделювання розподілу імовірностей z_i,k,j класів за допомогою гаусівського закону розподілу з параметрами m_l,j, та встановленням імовірнісних ваг класів . Також накладаються додаткові апріорні обмеження через контекстні змінні, які містять інформацію про переважаючий клас околу коефіцієнта.

Незважаючи на ефективність, описаний алгоритм має недоліки, які інколи призводять до грубих помилок класифікації і відбиваються на результатах роботи блоку кінцевої сегментації. Справа в тому, що при наявності на зображенні текстур, серед яких є як близькі, так і неподібні текстури, гістограми z_i,k,j можуть перекриватися для різних типів текстур і мати багатомодальну структуру для однієї текстури. В результаті алгоритм класифікації може визначити однаковий клас для точок різних текстур і віднести до різних класів точки однієї текстури. Основною причиною цього є використання у алгоритмі сумісної імовірності появи коефіцієнтів всіх типів підсмуг z_i,k,j. Але дерева різних типів містять свою частину інформації про область зображення, в першу чергу, про спрямованість його елементів у різних точках. Для уникнення втрати інформації запропоновано використати в якості критерію вектор імовірностей z_i,k,j=, де . Тепер кожен клас описується областю заданою у тривимірному просторі, що формується гаусівськими законами розподілу з параметрами m_B,l,j, .

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

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

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

При створені сучасних автоматизованих систем все частіше використовують інформацію про колір об'єктів. Методи сегментації, які базуються на моделі прихованого марковського дерева можуть бути застосовані і для сегментації кольорових чи багатоспектральних зображень. Якщо розглядати вейвлет-перетворення кольорового зображення у просторі червоного R, зеленого G та синього B кольорів, як розклад у вейвлет-базис окремо кожної кольорової смуги, то в результаті отримуємо дев'ять вейвлет-підсмуг - по три (LH, HL, HH) на кожну кольорову смугу. Відповідно формується дев'ять прихованих марковських дерев і, використовуючи припущення про їх незалежність, обчислюється імовірність появи точок областей зображення через добуток імовірностей окремих дерев. Але для реальних зображень різні кольорові смуги відображають одну й ту ж сцену, тобто те саме геометричне наповнення. Отже, результати вейвлет-перетворення різних кольорових смуг є корельованими, адже вейвлет-перетворення реагує на різкі зміни яскравості, тобто на геометрію зображення. Врахування цього факту у моделі зображення покращує результати її застосування.

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

,

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

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

Четвертий розділ “Компресія зображень та сигналів на базі вейвлет-перетворення та її оптимізація по швидкодії” присвячено задачі втратної компресії даних. Як у задачах фільтрації та сегментації, так і при побудові алгоритмів втратної компресії, важливим є статистичне моделювання кожного вейвлет-коефіцієнта для визначення важливості його для вхідних даних. Зокрема, при стиску даних часто використовується процедура передбачення значення вейвлет-коефіцієнта за відомими значеннями коефіцієнтів його околу, що дозволяє враховувати залишкові зв'язки між коефіцієнтами зменшуючи надлишковість присутню в даних. Однією з реалізацій такого процесу є процедура зворотної класифікації, суть якої полягає у віднесенні вейвлет-коефіцієнта до певного класу на базі відомостей про коефіцієнти попередньо обробленого околу . Кожен клас обробляється своїм способом згідно статистичних властивостей його коефіцієнтів. Модель прихованого марковського дерева ефективно описує статистичні залежності між коефіцієнтами, тому вона може бути застосована при розв'язку такої задачі. Отже запропоновано будувати модель кожного вейвлет-коефіцієнта у вигляді умовної густини розподілу їх значень при умові відомих значень коефіцієнтів околу та параметрів моделі прихованого марковського дерева, яке описує дані в цілому: , де - попередньо оброблені коефіцієнти каузального вікна розміру . Вагові коефіцієнти обчислюються як:

.

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

.

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

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

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

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

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

висновки

У роботі розв'язано наукову задачу пов'язану з удосконаленням математичної моделі прихованого марковського дерева та методів попередньої обробки і втратної компресії зображень на її основі. Зокрема отримано такі результати:

1. Проведено порівняльний аналіз методів та моделей статистичного опису зображень у вейвлет-просторі. Наведено основні методи застосування моделей у практичних задачах обробки та компресії зображень.

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

3. Удосконалено модель прихованого марковського дерева та метод фільтрації зображень на її основі, за допомогою запропонованого методу перерахунку глобальних параметрів моделі вейвлет-піраміди до локальних параметрів моделей окремих вейвлет-коефіцієнтів, який враховує додаткові кореляційні зв'язки між коефіцієнтами, що дозволяє покращити пікове співвідношення сигнал/шум на 0.6_1 дБ порівняно із вихідним методом та на 0.05-0.15 дБ порівняно з кращими відомими аналогами.

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

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

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

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

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

Список опублікованих праць за темою дисертації

1. Капшій О.В. Оптимізація швидкості роботи алгоритму втратного стиску даних // Відбір і обробка інформації. Львів, 2003. №19(95). С. 149-154.

2. Іванюк В.Г., Капшій О.В., Косаревич Р.Я., Лау Г. Інформаційна оцінка і виділення фрагментів кольорових зображень // Радіоелектроніка і інформатика. Харків, 2004. №3. С. 122-125.

3. Капшій О.В. Створення локальної прихованої марковської моделі з геометричним контекстом для фільтрації зображень у вейвлет-просторі // Відбір і обробка інформації. Львів, 2004. №21(97). С. 68-73.

4. Капшій О.В., Русин Б.П. Локальний опис вейвлет-коефіцієнтів у моделі прихованого марковського дерева для задач фільтрації зображення // Відбір і обробка інформації. Львів, 2005. №22(98). С. 64-69.

5. Капшій О.В., Русин Б.П. Метод попередньої класифікації текстур у задачі сегментації зображень // Моделювання та інформаційні технології. Київ: Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України, 2005. Вип.31. С. 65-70.

6. Капшій О.В., Русин Б.П. Система стиску дактилоскопічних зображень на основі вейвлетного перетворення // Праці Шостої міжнар. конф. УкрОбраз'2002. Київ, 2002. С. 171-174.

7. Капшій О.В. Вплив типу вейвлета та алгоритму пошуку параметрів квантувача на швидкість компресії // Матеріали XVIII відкритої наук.-техн. конф. молодих науковців і спеціалістів Фізико-механіченого інституту ім.Г.В.Карпенка НАН України (КМН-2003). Львів, 2003. С. 234-236.

8. Kapshiy O. Inverse classification in an image compression system based on hidden markov tree model // Матеріали III міжнар. конф. “Оптоелектронні інформаційні технології” (Фотоніка-ОДС 2005). Вінниця, 2005. С. 72-73.

9. Капшій О.В., Русин Б.П. Мінімізація часу тренування моделі прихованого марковського дерева // Матеріали IX міжнар. наук.-практ. конф. "Системи і засоби передачі і обробки інформації". Черкаси, 2005. С. 152-154.

10. Kapshiy O., Rusyn B. Color images segmentation using hidden markov tree // Матеріали 2-ї Міжнар. наук.-техн. конф. "Сучасні комп'ютерні системи та мережі: розробка та використання" (ACSN'2005). Львів, 2005. С. 91_92.