Моделі, методи та засоби обробки наборів зображень

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

Автореферат

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

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

Моделі, методи та засоби обробки наборів зображень

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

зображення векторний топологічний

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

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

Основними методами покращання інформативності наборів зображення є:

- їхнє суміщення (для її формування);

- інтервальне оцінювання (для її фільтрації);

- зміна роздільної здатності та синтез (для зміни розмірності вектора інформативності).

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

Розвинута в цій роботі теорія побудови засобів попередньої обробки наборів зображень, розроблені моделі, методи, алґоритми та створені засоби ґрунтуються на доробку багатьох вітчизняних і зарубіжних вчених, таких, як: Р. Дуда і П. Харт (розпізнавання образів); Р. Гонсалес, Г. Ендрюс, M. Текалп, У. Претт, Л. Шапіро, Є.Путятин (теоретичні та прикладні основи обробки зображень); В.Грицик, Ш. Пелег (збільшення роздільної здатності зображень); В. Яншин, Я. Фурман (контурний аналіз); Є. Очин, В. Старовойтов (сеґментація зображень); Т. Павлідіс, О.Свенсон, І.Грузман, О. Лукін, Л. Ярославський, Т. Хуанг (методи фільтрації); М.Шлезінгер (структурне розпізнавання, статистична сеґментація); В. Сойфер, В.Кожем'яко, Р.Ткаченко, Е.Бодянський (нейромережеві методи обробки зображень); С.Абламейко, В. Машталір (кореляційні методи обробки); Т.Вінцюк, О. Івахненко, Р. Воробель (методи покращання зображень); Н.Куссуль, Д.Х'юз (робастне оцінювання), В. Боюн (обробка сиґналів на основі ентропійних параметрів); Я. Драган (енерґетична теорія лінійних моделей стохастичних сиґналів) тощо.

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

Зв'язок роботи з науковими проґрамами, планами, темами. Тема дисертаційної роботи повністю відповідає науковим напрямам, які здійснюють на кафедрі автоматизованих систем управління Національного університету "Львівська політехніка", зокрема науковим дослідженням в області цифрової обробки сиґналів та інтелектуального аналізу даних (DataMining). Роботу виконано в межах держбюджетних тем, госпдоговорів та міжнародних проектів, зокрема "Високоефективні інформаційні технології видобування даних для соціально-економічних явищ та процесів"(№ 0109U001144); "Реконструкція об'єктів НПЗ Бориславського родовища. Автоматизована система раціонального видобутку, підготовки і збереження нафти і газу" (№0102U004324); "Адаптація програмного продукту під операційну систему MS Windows 2000\XP" (№0104U002358); "Розробка концепції та пропозицій побудови інформаційної інфраструктури Львівської області" (№0104U009866); "Інтегрування протоколів обліку інтелектуальних лічильників в програмне забезпечення" (№0104U002357); "Макет адаптивного пристрою введення та обробки зображень з використанням програмно-керованих растрів", (№0106U007185); "Розроблення систем збору і опрацювання технологічних даних для екологічного моніторингу режимів енергоблоків Бурштинської ТЕС" (Д-03/2007) та польсько-українсько-японського міжнародного проекту "Передавання інформаційних технологій Україні".

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

Для досягнення поставленої мети необхідно вирішити такі завдання:

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

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

3. Сформулювати принципи введення тополоґій для побудови сепарабельних просторів у задачах прикладної обробки зображень.

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

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

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

7. Розробити методи зміни роздільної здатності зображень, які ґрунтуються на використанні надлишкової просторової інформативності наборів зображень.

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

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

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

Методами дослідження є:

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

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

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

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

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

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

Наукова новизна. На основі виконаних теоретичних і експериментальних досліджень вирішено важливо науково-прикладну проблему розробки методів попередньої обробки наборів зображень. При цьому отримано такі нові результати:

вперше:

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

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

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

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

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

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

Отримали подальший розвиток:

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

- методи суміщення зображень у наборах на основі розв'язання задачі пошуку кореляційного максимуму, яким властива менша в 1.3-1.8 разів алґоритмічна складність;

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

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

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

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

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

- розробляти алґоритми зміни роздільної здатності із максимальним збереженням надлишкової інформативності зображень, які зорієнтовані на паралельні комп'ютерні системи;

- створювати інструментальні засоби синтезу зображень на основі надлишкової інформативності наборів.

Результати роботи впроваджені під час розроблення: модуля детектування руху для систем відеоспостереження (каталог розробок НУ "Львівська політехніка"), транскодерів реального часу в рамках проекту InterObject Media SDK (акт впровадження від 08.06.2008р.), проґрамно-апаратного комплексу для динамічного розпізнавання образів в рамках НДР Центру стратегічних досліджень екобіотехнічних систем (акт впровадження від 26.06.2009р.), макету адаптивного пристрою введення та обробки зображень у ДНДІ інформаційної інфраструктури (акт впровадження від 05.01.2009р.); під час виконання держбюджетних і госпдоговірних тем у Національному університеті Львівська політехніка (акт впровадження від 09.02.10р.), а також під час підготовки навчальних курсів "Штучний інтелект", "Цифрова обробка сиґналів" та "Комп'ютерна графіка" у Національному університеті "Львівська політехніка" (акт впровадження від 13.04.10 р.).

Особистий внесок здобувача. У роботах, написаних у співавторстві, здобувачеві належать: представлення зображень та наборів [14, 18, 29, 30, 32, 33, 36], методологія класифікації моделей представлення зображень [29, 32, 33], векторна модель представлення зображень [3], введення тополоґій [3], формулювання поняття майже факторизації та задачі побудови майже фактор просторів над тополоґічними просторами зображень [2, 3, 30, 31], визначення адитивних груп та лінійних функціоналів над тополоґіями зображень [29], концепція побудови гільбертових просторів [3, 31], розробка методів суміщення [3, 11, 13, 14, 18, 20, 31, 39-41], виділення об'єктів уваги [27, 40], та фільтрації [4, 21, 35, 36, 38], побудова матриць операторів [8] та методологія використання власних векторів для зміни роздільної здатності та синтезу зображень [8], метод збільшення роздільної здатності на основі нечіткої логіки та його удосконалення [6, 9, 10, 15, 16, 34], аналіз методів обробки наборів зображень [22-24], часові оцінки управління паралельними потоками [26], структури розпаралеленого проґрамного забезпечення [25-28].

Апробація результатів дисертації. Основні положення дисертації обговорювались більш ніж на 22 міжнародних науково-технічних конференціях та наукових семінарах і симпозіумах, зокрема: Міжнародній науково-технічній конференції "Інформаційні системи та технології" (м. Львів, 1999); International Conference on Modeling &Simulation Proccedings - MS'2001 (Lviv, 2001); International WorkShop Conference Telematics and Life-Long Learning, TLLL-2001 (Kyiv, 2001); Міжнародній науковій конференції з індуктивного моделювання МКІМ, (м. Львів, 2002); International Workshop on Intelligent data acquisition and advanced computing systems: technology and application (м. Львів, 2003); 6-14th International Modelling School of AMSE-UAPL, (м. Алушта, 2001-2009); ІІ міжнародному конгресі "Інформатизація рекреаційної та туристичної діяльності: перспективи культурного та економічного розвитку", (м. Трускавець, 2003); Міжнародних наукових конференціях "Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій" (м. Євпаторія, 2005, 2006, 2009, 2010); X International conference "The Experience of Designing and application of CAD Systems in Microelectronics - CADSM09" (Polyana, 2009); International conference "Perspective technologies and methods in MEMS design - MEMSTECH" (Polyana, 2009, 2010); International conference of computer science and information technologies CSIT, (м. Львів, 2006-2009); Міжнародній конференції "Інформаційні-телекомунікаційні технології в сучасній освіті: досвід, проблеми, перспективи" (м. Львів, 2009).

Публікації. За результатами дисертаційних досліджень опубліковано 49 друкованих праць, серед них 33 статті у фахових виданнях згідно з переліком, який затверджено ВАК України, 15 публікацій у збірниках праць конференцій, 1 моноґрафія та отримано 1 авторське свідоцтво.

Структура та обсяг роботи. Робота складається із вступу, семи розділів, списка використаних джерел та додатків. Загальний обсяг роботи становить 366 стор. друкарського тексту. Дисертація містить 52 рисунки на 52 стор., 20 таблиць на 20 стор. Список використаних джерел складається із 308 назв на 32 стор. П'ять додатків розміщено на 41стор.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

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

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

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

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

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

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

, . (1)

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

Дискретне представлення кожного цифрового зображення

(2)

де X2,+d N2,+ - двовимірний тополоґічний многовид простoру N2,+; Qd Color. X2,+d та Qd є замкненими, обмеженими та зліченними підмножинами просторів N2,+ та Color. У більшості практичних випадків X2,+d є прямокутником

де l, h N+ - довжина та висота P; s = l h є площею і розмірністю X2,+d .

У разі набору зображень P за умов і маємо:

1) за виразом (2) оператор набору С

(3)

де - значення кольору (інтенсивності) піксела з координатами (i, j); z - індекс зображення у наборі P; N - розмірність набору.

2) за виразами (1) і (3) представлення набору зображень

; (4)

cтатистичну модель. Параметрами моделі є: математичне сподівання - ; дисперсія - ; девіація - ; кореляція - . Методи обробки ґрунтуються на кореляційному та реґресійному аналізі, теорії випадкових процесів;

енерґетичну модель. Параметрами моделі є: скінченна енерґія (клас сиґналів) - та середня потужність (клас сиґналів) - . Методи обробки ґрунтуються на теорії функцій і функціональному аналізу, теорії операторів;

інформаційну модель. Параметрами моделі є: інформативність - ; ентропія - ; приведена ?-ентропія - . Методи обробки ґрунтуються на динамічній теорії інформації, теорії випадкових процесів;

частотну (спектральна) модель. Параметрами моделі є: операційні одновимірні (або двовимірні) перетворення. Методи обробки ґрунтуються на функціональному аналізі, варіаційному численні;

модель на основі теорії множин. Основу моделі становлять нейромережеві технології, методи теорії генетичних алґоритмів та нечітких множин;

векторну модель. Модель ґрунтується на гіпотезі про існуванні вектор-функції .

Першим параметром моделі є потік вектора C

, (5)

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

Другим параметром моделі є ґрадієнт кольору як векторна функція на евклідовому просторі координат вектора C на поверхні .

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

У разі набору зображень (4) третім параметром є набір {Фz}:

.

Тут набір {Фz} є евклідовим простором.

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

У роботі показано, що вирази

; ,

є відповідно скалярним добутком і метрикою простору .

Доведено, що є гільбертовим сепарабельним простором, а його метрика є напівметрикою, тобто метрикою фактор простору простору .

Подібно до випадку простору побудовано і досліджено гільбертовий сепарабельний простір , з детермінантною нормою

.

На основі гельдерової та синґулярної норм побудовано гільбертові сепарабельні простори , та (тут - норма Фробеніуса, яка отримується із гельдерової норми при p = 2). Показано, що є простором із мультиплікативною метрикою (тут ?i - власне число матриці).

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

У третьому розділі розглянуто питання формування тополоґій і відповідних покриттів та розбиттів зображень. Існування таких покриттів обґрунтовуються відображенням тополоґії в колірній області неперервним оператором над тополоґією компакту. Для цього на многовиді X2,+d зображення P означено фреймову тополоґію

. (6)

Тут підмноговид є прямокутною дискретною областю (фреймом) і підмножиною X2,+d

, (7)

яка виступає точкою простору . Тут - координати початку, довжина та висота m-го фрейму зображення P.

Оскільки є тополоґією простору X2,+d, то є тополоґічним простором з відомою дискретною метрикою.

Покриттям (фреймовим покриттям) простору X2,+d зображення P є підмножина тополоґії (тут - розмірність покриття ). Cама тополоґія є набором фреймових покриттів з базою .

У разі існування набору (4) для побудови фреймової тополоґії та фреймового покриття для P, розглянуто два випадки:

1. Кожне зображення має власний тополоґічний простір . Тоді:

. (8)

2) Усі зображення набору мають однаковий координатний многовид X2,+d. Тоді:

. (9)

На основі введених тополоґій зображення та набору неперервним оператором породжуються неіндуковані тополоґії в колірній області. За означеннями (2) і (6) маємо

, (10)

де Сm - оператор С, заданий на фреймі . Тоді С - набір операторів Сm на многовиді X2,+d, який за певних умов може утворювати адитивну абелеву групу.

На основі (2), (3) і (10) зображення P можна подати у вигляді набору фраґментів

(11)

де Pm називається фраґментом зображення P. Набір утворює фраґментну тополоґію зображення P у Qd , породжену оператором С з тополоґії . Тоді оператор (2) є відображенням тополоґій

. (12)

У роботі показано, що простір P є сепарабельним.

За означеннями (11) та (12) кожним породжується фраґментне покриття з визначеними операціями розширення та звуження простору

У разі існування набору зображень (4), подібно до (8) та (9), також розглянуто два випадки:

1. Для усіх зображень набору визначено умови випадку (8). Тоді оператор набору P є таким:

 (13)

де - вектор фраґментних тополоґій набору, який породжений з ; , - фрейм та розмірність z-го покриття зображення Pz.

2. Для усіх зображень набору визначено умови випадку (9). Тоді оператор набору P є таким:

(14)

За обома випадками для набору представлення (3) та оператор набору (4) матимуть вигляд

. (15)

Якщо з кожної тополоґії ?z вибрати по одному покриттю ?z, то отримаємо вектор фраґментного покриття набору

.

На основі тополоґій (8), (9) і (13), (14) в кожній із моделей представлення побудовано адитивні абелеві групи функціоналів над полем ?z у:

? енерґетичній моделі - адитивні групи функціоналів енерґії {Ez,m} та потужності {Пz,m}, які визначені для фраґмента Pz,m на диз'юнктивних покриттях ?z ????z,??z ???z. Тоді для кожного зображення маємо такі представлення: клас сиґналів

? - ; клас сиґналів - ;

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

векторній моделі - адитивна група потоків {Фz,m} крізь фрейм , на диз'юнктивних покриттях. Тоді представлення зображення є таким:

.

У векторній моделі представлення при заданих тополоґіях ?z, ?z визначено лінійний функціонал на многовиді . За цим визначенням на фреймі потік Фz,m є значенням деякого абстрактного функціонала Fz на тополоґії

.

Доведено, що на многовиді функціонал Fz є лінійним.

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

, (16)

де - кореляція між фраґментами; . При цьому доведено, що вираз (16) є метрикою і напівметрикою простору .

На основі напівметрики (16) для елементів простору тополоґії означено відношення еквівалентності

. (17)

На основі метрики (16) і відношення еквівалентності (17) задачу факторизації простору сформульовано так (задача 3.1 - про факторизацію простору зображення): факторизація покриття тополоґії полягає у побудові фактор-простору за допомогою напівметрики (16).

Задача 3.1 означає побудову класів еквівалентності для кожного елемента Pm простору тополоґії за відношенням еквівалентності (17).

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

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

,

де - розмірність простору ; ? - зліченно-адитивна міра.

У випадку набору P (4) із тополоґією та фраґментним покриттям , елементи якого мають однакову розмірність і для них задана метрика (16), задачу 3.1 сформульовано так (задача 3.2 - про факторизацію простору набору зображень): факторизація покриття тополоґії полягає у побудові фактор-простору за допомогою напівметрики (16).

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

Означення 3.1. Класом майже еквівалентності елемента Pm називається такий клас еквівалентності , який визначений майже скрізь на . Це означає, що на множині міри нуль повинна виконуватись умова майже еквівалентності

. (18)

У роботі доведено, що міра класу майже еквіалентності дорівнює мірі класу еквівалентності елемента Pm , отримано обмеженість міри класу еквівалентності

.

Означення 3.2. Майже фактор-простором або ?-фактор-простором називається такий фактор-простір тополоґічного простору , що принаймні один із його класів є класом майже еквівалентності.

Побудова майже фактор-простору називається ?-факторизацією тополоґічного простору . Майже фактор-простір є об'єднанням фактор-простору і множини класів майже еквівалентності :

Показано, що міра майже фактор-простору дорівнює мірі фактор-простору .

Означення 3.3. Змінна ? з умови (18) називається довжиною (параметром) майже факторизації.

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

.

Подібно до задачі 3.1 сформулювано задачу майже факторизації (задача 3.3 - про майже факторизацію простору зображення): майже факторизація простору полягає у побудові простору за допомогою відношення еквівалентності (17) і відношення майже еквівалентності (18) на множинах міри нуль.

У разі набору P (15) із заданою тополоґією (7) і фраґментним покриттям, подібно до задачі 3.2, сформульовано задачу майже факторизації (задача 3.4 - про майже факторизацію простору набору зображень): майже факторизація простору тополоґії полягає у побудові майже фактор-простору за допомогою відношення еквівалентності (17) і розширенні цього простору за рахунок множини, елементи якої є класами майже еквівалентності, які побудовані на основі відношення (18).

У четвертому розділі на основі сформульованих задач.3.1 - 3.4 розроблено методи суміщення однотипних зображень набору в межах одного піксела.

Вхідними умовами задачі суміщення є: набір P, фіксоване зображення Pфікс = P1, фрейм і відповідний фраґмент P1,зад. Задача суміщення зводиться до побудови набору P', такого, щоб

.

і усі зображення набору P' були вирівняні відносно Pфікс в межах піксела.

За заданих початкових умов з використанням, виділених в розділі 2, параметрів моделей представлення зображень, побудованих гільбертових сепарабельних просторів і розроблених у розділі 3 тополоґічних представлень та сформульованої задачі 3.4 розроблено набір методів, класифікація яких наведена на рис.1.

Рис.1. Класифікація розроблених методів суміщення

Загальна схема усіх методів складається із таких кроків:

Крок 1. Визначення покриттів та тополоґій (9) та (14) для P'.

Крок 2. Звуження просторів і до і за допомогою розв'язання задачі майже факторизації 3.4.

Крок 3. Побудова простору та відповідного простору , для яких , за допомогою пошуку кореляційного максимуму на .

Крок 4. За фреймовим набором пошук координатних зміщень та для зображення Pz

Тут і - координатні зміщення z-го елемента простору .

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

На рис.2. наведено усереднені значення часу роботи алґоритмів розроблених і відомих методів. Характеристики НШЗЗ (набору штучно згенерованих зображень) є такими: розмірність набору - N = 99 зображень; зображення в градаціях сірого; розмірність кожного зображення - l = 34; h = 54 пікселів; Pфікс = P0. Параметри заданого фрейму : ; ; ? = 0.01.

З рис.2 видно, що алґоритми, побудовані на основі розроблених методів, демонструють більшу швидкість роботи порівняно із алґоритмами на базі відомих методів.

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

Рис.2. Порівняння часу роботи різних алґоритмів суміщення НШЗЗ при N = 99 зображень

Рис.3. Порівняння часових результатів роботи методів суміщення НШЗЗ при різних розмірностях набору

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

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

Рис.4. Кількість помилок при різних значення параметра майже факторизації різних алґоритмів суміщення

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

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

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

Означення 5.1. Під шумом набору розумітимемо стохастичні варіації параметрів моделі представлення зображень набору.

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

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

.

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

Крок 1. Формування варіантного ряду - здійснюється із параметрів моделі представлення

. (19)

Крок 2. Побудова інтервалів - здійснюється за правилом

(20)

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

Крок 3. Визначення характеристик на кожному інтервалі, зокрема середнього значення та експериментальної частоти величини {Mz} на k-му інтервалі

. (21)

У результаті отримується набір інтервалів і відповідних характеристик

. (22)

Крок 4. Перевірка нульової гіпотези - здійснюється за критерієм Пірсона

 . (23)

Крок 5. Побудова інтервалу довіри

, (24)

де - математичне сподівання; - середньоквадратичне відхилення середнього арифметичного; t - процентиль розподілу Стьюдента

Крок 6. Формування набору PШ - здійснюється за правилом

. (25)

У роботі описано використання параметрів енерґетичної та інформаційної моделей представлення.

У випадку, коли розмірність вхідного набору є малою для отримання достовірної оцінки, розроблено метод фільтрації наборів на основі квантування параметрів моделей представлення зображень (метод 5.2). За цим методом схема (19) - (25) видозміниться. Формування варіантного ряду здійснюється за характеристиками проміжків квантування параметрів

.

де - m-ні проміжки квантування відповідно у координатній та колірній областях параметра Mz; - кількість проміжків квантування; - середнє значення Mz на ; m - індекс проміжку квантування.

Визначення інтервалів (для кожного m), перевірка нульових гіпотез і побудова довірчих інтервалів здійснюється подібно до базової схеми. Для формування набору PШ використано:

,

де - вектор розмірністю , елементи якого дорівнюють 0 та 1.

На рис.5 наведено порівняння результатів фільтрації НРОЗ за параметром та на основі квантування параметрів. Розмірність вхідного набору вдалось збільшити у 1.3 раза. До того ж незалежно від параметра моделі представлення максимальна похибка фільтрації не перевищує двох зображень, що становить 7%.

Для випадків великих за розмірностями наборів зображень розроблено метод фільтрації набору на основі частот параметрів моделей представлення (метод 5.3). Схема цього методу відносно базової схеми видозмінюється так: формування варіантного ряду здійснюється за принципом: кожному інтервалу ставимо у відповідність частоту параметра Mz

,

де N(M) - кількість інтервалів розбиття набору частот ; k - індекс інтервалу.

Побудова інтервалів, визначення характеристик, перевірка гіпотез та побудова довірчого інтервалу здійснюється подібно до базової схеми. Формування набору PШ - здійснюється за правилом



Рис.5. Відхилення результатів фільтрації НРОЗ за параметром та на основі квантування параметрів

Табл.1 містить порівняння сумарних (для усіх значення ?-квантиля) результатів експериментів з фільтрації набору за параметром та на основі квантування параметрів. Незалежно від параметра максимальна похибка не перевищувала 2.5 - 3%. Для різних параметрів вдалось отримати різні коефіцієнти зменшення розмірності. Подальше зменшення призводить до різкого зростання похибки обчислювального процесу.

Таблиця 1. Зведена таблиця сумарних відхилень фільтрації набору за параметрами та за статистичною частотою параметрів

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

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

.

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

Таблиця 2. Зведена таблиця сумарних відхилень фільтрації набору за параметрами та частотної фільтрації на основі квантування параметрів

Таблиця 3. Зведена таблиця сумарних відхилень фільтрації набору за параметрами та частотної фільтрації на основі квантування імовірностей параметрів

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

У шостому розділі розроблено методи зміни роздільної здатності (ЗРЗ). Розглянуто два випадки:

1) випадок окремого зображення (задача 6.1 - ЗРЗ зображення). Задача 6.1 полягає у формуванні із P нового зображення P із піксельною матрицею . Тут l', h' - розмірність матриці C' зображення P такі, що l' l h' h;

2) випадок набору однотипних зображень. У цьому випадку розглянуто дві задачі

2.1) задача 6.2 - ЗРЗ зображень із збереженням розмірності набору. Задача полягає в тому, щоб сформувати новий набір P? з P такий, щоб

; (26)

2.2) задача 6.3 - ЗРЗ зображень із збільшенням розмірності набору. Задача полягає в тому, щоб сформувати новий набір P? з P з матрицями (26) такий, щоб

.

Для розв'язання задачі 6.1 розроблено три методи.

Перший з них (метод 6.1) ґрунтується на власних векторах матриці оператора, яка будується із рядка чи стовпця матриці С, зокрема

; (27)

. (28)

У (27) і (28) верхній індекс визначає напрям ЗРЗ. Зокрема індекс j означає ЗРЗ по вертикалі (напрямку j), індекс i - ЗРЗ по горизонталі (напрямок i).

Власні вектори матриць (27), (28) використовуються для отримання матриці пікселів С' нового зображення P' з початкової матриці С у такий спосіб: у разі збільшення роздільної здатності для розширення наборів рядків чи стовпців; у разі зменшення роздільної здатності для заміни двох послідовних рядків чи стовпців.

Другий метод (метод 6.2) ґрунтується на використанні генетичних алґоритмів під час побудови операторів (27), (28).

Першим кроком методу 6.2 є формування початкових векторів для ЗРЗ:



.

У результаті операції кросинговера

А = kА + (1 - k)В, B = (1- k )А + kВ, 0 < k < 1, (29)

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

; (30)

. (31)

Тоді оператори (27) та (28) мають вигляд

;

.

Третій метод ЗРЗ (метод 6.3) ґрунтується на методах теорії нечітких множин. В основі методу є матриці скалярних добутків, які в кожному із напрямків ЗРЗ мають вигляд

; - i-й рядок матриці С; (32)

; - j-й стовпець матриці С. (33)

Декартовий добуток матриць (32) і (33) у кожному напрямку визначають так

;

.

де F - нечіткий оператор. Тоді додаткові вектори визначають за формулами

;

.

На останньому етапі методу виникає задача впорядкування розміщення , яку розв'язуємо пошуком мінімуму норми

;

,

і позиції за правилами

- у напрямку j: якщо , то розміщується перед ; якщо , то розміщується після ;

- у напрямку i: якщо , то розміщується перед ; якщо , то розміщується після .

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

Для розв'язання задачі 6.2 розроблено два методи. Перший з них (метод 6.4) ґрунтується на власних векторах матриці оператора, яка будується із наскрізних наборів

Елементи матриць операторів (27), (28) визначають так:

;

.

У табл. 4 наведено результати експериментів використання різних варіацій методу 6.4 і порівняння їх із результатами просторової інтерполяції. Характеристики набору є такими: розмірність набору - N = 4 зображення; зображення в градаціях сірого; розмірність кожного зображення - l = 34; h = 54 пікселів. Із цих даних видно, що найкращі результати за усіма гістограмними метриками має метод 6.4 із ітераційним способом визначення власних векторів.

Таблиця 4. Результати порівняння за гістограмними метриками збільшених по ширині зображень набору різними методами:

a - методом 6.4 з ітераційним пошуком власних значень;

b - методом просторової інтерполяції;

c - методом 6.4 з прямим пошуком власних значень

Інший метод (метод 6.5) розв'язання задачі 6.2 ґрунтується на використанні операції кросинговера (29) та мінімаксного оператора (30), (31) під час побудови матриць операторів. Початковими векторами приймаємо , а за та , записані у зворотному порядку початкові вектори. За векторами та , які отримані у результаті операції кросинговера (29) відносно початкових векторів та дії мінімаксних операторів (30) та (31), будуються матриці оператори для ЗРЗ:

; (34)

. (35)

Збереження розмірності набору в обидвох випадках забезпечується виконанням умови

У табл.5 наведено результати експериментів використання різних варіацій методу 6.5. Після порівняння даних з табл. 4 і 5 можна стверджувати, що метод 6.5 дає кращі результати порівняно із методом 6.4.

Для розв'язання задачі 6.3 також розроблено два методи. У першому з них (метод 6.6) початковими векторами для ЗРЗ є:

; (36)

. (37)

Тоді оператори (34) та (35) будують так:

 (38)

– у напрямку j:

(39)

– у напрямку i:

(40)

Таблиця 5. Результати порівняння за гістограмними метриками збільшених по ширині зображень методом 6.5 з: a - ітераційним пошуком власних значень; b - прямим пошуком власних значень

У табл.6 наведено результати практичних експериментів використання методу 6.6 з ітераційним способом пошуку власних векторів. Під час порівняння даних з табл.4-5 можна констатувати зниження якості передискретизованих зображень. Проте розмірність початкового набору збільшено у два рази.

Таблиця 6. Результати порівняння за гістограмними метриками збільшених по ширині і синтезованих зображень методом 6.6

У останньому методі (метод 6.7) для розв'язання задачі 6.3 початкові вектори будують згідно з виразами (36), (37), а та - як записані у зворотному порядку початкові вектори. Операція кросинговера здійснюється за формулою (29), мінімаксний оператор - відповідно до виразів (30), (31), а матриці оператори для кожного з напрямків будують за формулами (38) - (40).

У табл.7 наведено результати практичних експериментів використання методу 6.7 з ітераційним способом пошуку власних векторів. У разі порівняння даних з табл.5 і 7 можна констатувати зниження якості передискретизованих зображень. Проте якість є вищою від результатів методу 6.6 і співвимірною із даними методу 6.5. При цьому також було синтезовано чотири нових зображення.

Збільшення розмірності в обидвох випадках набору забезпечується виконанням умови

.

Таблиця 7. Результати порівняння за гістограмними метриками збільшених по ширині і синтезованих зображень методом 6.7

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

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

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