Методи одновимірних нормалізацій афінних перетворень у задачах розпізнавання зображень

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

Харківський національний університет радіоелектроніки

05.13.23 системи та засоби штучного інтелекту

УДК 007.001.362+681.327.12.001.362

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

Автореферат

МЕТОДИ ОДНОВИМІРНИХ НОРМАЛІЗАЦІЙ АФІННИХ ПЕРЕТВОРЕНЬ У ЗАДАЧАХ РОЗПІЗНАВАННЯ ЗОБРАЖЕНЬ

Яковлева Олена Володимирівна

Харків 2004

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

Робота виконана в Харківському національному університеті радіоелектроніки, Міністерство освіти і науки України

Науковий керівник: доктор технічних наук, професор Путятін Євген Петрович, Харківський національний університет радіоелектроніки, завідувач кафедри інформатики

Офіційні опоненти: доктор технічних наук, професор Любчик Леонід Михайлович, Національний технічний університет “Харківський політехнічний інститут”, завідувач кафедри комп'ютерної математики та математичного моделювання;

- кандидат технічних наук, доцент Авраменко Віктор Васильович, Сумський державний університет, доцент кафедри інформатики

Провідна установа: Донецький державний інститут штучного інтелекту, відділ розпізнавання зорових образів, Національна академія наук України та Міністерство освіти і науки України

Захист відбудеться: “ 9 ” червня 2004 р. о 1300 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14, тел.: (057) 70-21-451

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки (61166, м. Харків, пр. Леніна, 14)

Автореферат розісланий “ 23 ” квітня 2004 р.

Вчений секретар спеціалізованої вченої ради В. І. Саєнко

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертація виконана на кафедрі інформатики Харківського національного університету радіоелектроніки (ХНУРЕ) в рамках держбюджетних науково-дослідних робіт: “Концептуальні підходи та моделі розпізнавання зображень в умовах регулярних і випадкових збурень для систем реального часу” (№ ДР 0100U003416, виконавець), “Дослідження та розробка методів аналізу зображень в умовах складних збурень” (№ ДР 0103U001572, виконавець), а також у рамках двох договорів про науково-технічне співробітництво: між кафедрою інформатики ХНУРЕ і лабораторією охорони ґрунтів від ерозії Національного наукового центру “Інститут ґрунтознавства та агрохімії ім. О. Н. Соколовського” (ННЦ ІГА) відповідно до науково-технічної програми Української академії аграрних наук на 20012005 роки “Родючість і охорона ґрунтів”, а саме, підпрограми 2, завдання 01.03 № ДР 0101U006046 (етап 01.03.03: Обґрунтувати і розробити методику й алгоритм коректування ґрунтово-картографічних матеріалів і картографування ерозійно небезпечних ґрунтів різних ґрунтово-кліматичних зон України на основі космічної зйомки); між кафедрою інформатики ХНУРЕ і ТОВ НВФ “Оптима”.

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

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

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

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

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

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

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

Предмет дослідження - методи одновимірних нормалізацій для розпізнавання зображень.

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

Наукова новизна отриманих результатів полягає в тому, що:

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

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

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

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

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

Результати дисертаційної роботи впроваджені в ННЦ ІГА в системі обробки космічних знімків, а саме, при створенні програмного модуля, призначеного для їхнього суміщення шляхом нормалізації (акт від 20.03.03 р.); у ТОВ НВФ “Оптима” в системі ідентифікації автомобільного транспорту для розпізнавання моделей автомобілів (акт від 19.06.03 р.). Матеріали дисертації також використовуються в ХНУРЕ при проведенні занять з курсів “Математичне та інформаційне забезпечення систем обробки складних сигналів”, “Методи і способи розпізнавання образів”, “Алгоритми і програмне забезпечення синтезу зображень”, “Information systems technology” (акт від 29.09.03 р.).

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

Апробація результатів дисертації. Матеріали дисертаційних досліджень доповідалися, обговорювалися та були схвалені на наступних науково-технічних конференціях і форумах: 25, 7-у Міжнародних молодіжних форумах “Радіоелектроніка і молодь у ХХІ столітті” (Харків, 1998-2001, 2003); VII, X, XI міжнародних науково-практичних конференціях “Інформаційні технології: наука, техніка, технологія, освіта, здоров'я” (Харків, 1999, 2002, 2003); 6-й міжнародній конференції “Теорія і техніка передачі, прийому й обробки інформації” (“Нові інформаційні технології”) (Туапсе, 2000); на конференції “XXV Гагаринские чтения” (Москва, 1999).

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

Структура й обсяг дисертаційної роботи. Дисертація складається із вступу, 6 розділів, висновків, списку літературних джерел з 171 найменувань на 15 с., 5 додатків на 37 с. Загальний обсяг становить 199 с. (з них 147 с. основного тексту). Роботу проілюстровано 40 рисунками (з них 7 на 5 окремих сторінках), 20 таблицями.

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

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

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

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

Нехай G група перетворень площини. Під індукованою дією групи G на прямих площини у роботі розуміються перетворення gl, g, що формуються шляхом відображення (g, l): g(g, gl), де gG, gG, glGl (G, Gl групи перетворень, викликані перетвореннями групи G; G група перетворень на прямій l; Gl група перетворень положення прямої l). Якщо G, то на підставі властивостей афінного перетворення у роботі показано, що перетворення g, gl у загальному випадку мають вигляд: g: +, gl: +, +, де координата на прямій l, початок відліку якої знаходиться в точці перетину нормалі n, опущеної з початку координат (0,0) на пряму l (рис.1); параметр перетворення масштабу на прямій l; параметр зсуву вздовж прямої l; кут між нормаллю n і додатною піввіссю OX, взятий за годинниковою стрілкою; кут повороту нормалі n відносно початку координат (0,0); довжина нормалі n; зміна довжини нормалі n. Координати (,,) відображають положення точки M на площині, координати (,) задають положення прямої l. Параметри , , , є параметрами індукованих перетворень g, gl і залежать від gG та рівняння прямої l.

Введено наступне визначення. Прямі l, для яких gl: , , називаються інваріантними прямими першого або другого типів відносно групи G в залежності від того, вірно це для кожного перетворення gG чи тільки для якогось конкретного gG. Незважаючи на відсутність інваріантних прямих першого типу відносно багатьох груп, зведення нормалізації цих груп до вирішення одновимірних задач можливе. Справа в тому, що майже кожна багатопараметрична група має інваріантні прямі другого типу із сімей прямих, зручних для нормалізації зображень. Такими є однопараметричні сім'ї: Sy горизонтальних прямих {l: y=, }; Sx вертикальних прямих {l: x=, }; S00 центральних прямих {l: cosx+siny=0, [0,)}, де параметр сім'ї.

Виявлено, що в залежності від виду індукованої дії на прямих, який викликано перетворенням площини gG, ці сім'ї можуть мати такі інваріантні властивості відносно групи G: бути інваріантними, інваріантно-стійкими або стійкими. Сім'я S називається інваріантною відносно групи G, якщо lS lS, де l= gll, glGl, тобто жодне з перетворень gG не виводить прямі цієї сім'ї за її межі (є інваріантною множиною). Інваріантна відносно групи G сім'я S називається інваріантно-стійкою відносно цієї групи, якщо для lS gl: , , тобто сім'я S складається з інваріантних прямих першого типу відносно G. Сім'я прямих S називається стійкою відносно групи G першого або другого типу, якщо для будь-якого перетворення gG вона містить хоча б одну інва-ріантну пряму відповідно першого або другого типу.

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

Встановлено, що група є підгрупою , що містить найбільшу кількість підгруп , відносно яких існує сім'я прямих з однаковою інваріантною властивістю. Такою сім'єю є сім'я S0, яка являється відносно та її підгруп інваріантною множиною. На прямій lS0 індуковані перетворення gG, glGl, що викликані перетвореннями g , мають вигляд

g: , gl: +, (1)

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

У третьому розділі розроблено методи одновимірних нормалізацій, які дозволяють одержувати параметри індукованих перетворень на прямих, що дає можливість визначати параметри, які нормалізують зображення в цілому. Метод одновимірних нормалізацій засновано на принципі найбільшої подібності обмежень на прямі вхідного і еталонного зображень та інваріантних властивостях сімей прямих. У роботі під обмеженням зображення на пряму l розуміється функція bl(), що утворюється шляхом перетину поверхні, яку задано функцією зображення B(x,y), площиною, що ортогональна площині XY та проходить через її пряму l. Одновимірною нормалізацією (ОН) у роботі називається пошук обмеження b вхідного зображення, що відповідає обмеженню еталонного зображення, шляхом визначення перетворень g, gl, для яких виконується умова:

, (2)

де l пряма, на яку розглядається обмеження еталона; l=gll пряма, яка є образом прямої l, міра подібності між обмеженнями; деяка гранична величина. Параметрами ОН для прямої l називаються параметри індукованих перетворень, що отримані у результаті ОН, і які дозволяють обмеження вхідного зображення привести до еталонного вигляду.
У випадку перетворень (1) параметрами ОН для прямої l являються 1/, -.

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

b(), b(). (3)

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

Комбінаторна місткість перевірки умови для пошуку відповідних обмежень у загальному випадку оцінюється як === =+=nnnn=n4, де розширена множина припустимих значень параметрів суперпозиції перетворень ggl, що утворена об'єднанням множин ={(, ) g(, ), gb0; =1,2,…,, 1=, =; =1,2,…, , 1=, =} та ={(, ) gl(, ), glb0; =1,2,…, , 1=, =, =1,2,…,, 1=, =}; n, n, n, n кількість припустимих значень параметрів , , , відповідно, які мають однаковий порядок і можуть бути замінені величиною n того ж порядку. Розширення множини припустимих значень параметрів полягає в завданні границь інтервалів припустимих значень параметрів у такий спосіб. Для кожного i-го параметра інтервал визначається за вимогою D (D поле зору) у припущенні, що інші параметри фіксовані і дорівнюють таким значенням, неначе перетворення g, gl одиниці своїх груп. Відрізок числової прямої, що містить ці значення, і буде прийнятий як інтервал [] припустимих значень параметру пi. Оцінена в такий спосіб комбінаторна місткість двовимірної кореляції для групи дорівнює потужності множини

. (4)

Основну увагу приділено розгляду методу ОН для сімей Sx, Sy, S0, що мають інваріантні властивості. Використання таких сімей знижує кількість параметрів індукованої дії, що дозволяє знизити комбінаторну місткість перевірки загальної умови. Якщо відомо, що шукана пара обмежень знаходиться на прямих l, l S (S одна з сімей Sx, Sy, S0; l пряма еталона; l пряма вхідного зображення), тоді перетворення gl містить тільки один параметр, а саме, при l, lSx або l, lSy gl: +, якщо ж l, lS0, то gl: +. Знаючи, що параметри індукованих перетворень будуть мати дискретні значення, прямі сім'ї S можна пронумерувати. Тоді кожному i-му значенню перетворення gl буде відповідати пряма S, і вирішальна умова набуває вигляду:

, (5)

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

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

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

У роботі розкладання у суперпозицію підгруп пропонується використовувати як засіб для одержання параметрів центроафінного перетворення від параметрів ОН. Використовувалися такі розкладання центроафінної групи: , , , , , , , , , , , , , де - група поворотів; - група неоднорідної зміни масштабу; , - групи зміни масштабу вздовж осей X і Y відповідно; , - групи косого зсуву вздовж осей X і Y відповідно. Для цих розкладань побудовані відображення Q: q1,…, q4 а11, а12, а21, а22, де q1,…, q4 параметри перетворень, що входять до розкладання; а11, а12, а21, а22 параметри центроафінного перетворення (а11а22 a21а120).

Параметри q1,…, q4 розкладань пропонується одержувати на підставі результатів ОН шляхом побудови відображення I(): 1, , 2, q1,…, q4, де 1, 1, 2, 2 параметри індукованої дії (1) на прямих , S0 (центральних прямих), викликаної перетворенням g, що нормалізує. ОН в цьому випадку реалізується за розробленим базовим алгоритмом, призначеним для нормалізації в умовах, коли сім'я прямих є інваріантною множиною.

Для отримання відображень I() досліджено закономірності зміни параметрів , індукованих дій на прямих сім'ї S0 (наприклад, наявність під дією gGd екстремальних значень за перпендикулярними напрямками покладено в основу побудови відображення I()), розглянуто особливості поведінки прямих сім'ї S0 під дією підгруп Gi (i=), які входять у розкладання, та їх композицій, а саме: розглянуто збереження взаємної ортогональності пари центральних прямих з точки зору використання цієї властивості для нормалізації, вивчено можливість одержання взаємно ортогональних центральних прямих, вирішено ряд геометричних задач по приведенню обмежень зображень перетвореннями з підгруп Gi до заданого вигляду. Так, наприклад, в результаті досліджень можливості приведення будь-яких двох прямих до взаємно ортогонального вигляду перетворенням gGh,x отримано таке твердження: перетворення gGh,x будь-які дві прямі і , для яких виконується умова , може перевести у взаємно ортогональні, причому величина параметру перетворення визначається за формулою при 1, 2k або за формулою при 1=k, де 1, 2 кути нахилу першої і другої прямих до перетворення gGh,x. Функцію проілюстровано на рис. 2а. На рис. 2б сірим кольором виділено область , де пара прямих , може бути приведена перетворенням gGh,x до взаємно ортогонального виду.

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

а б

Рис. 2. Ілюстрація умови для 1, 2(0,):

а функція ; б область, де .

На основі цих досліджень отримано відображення I(, ) для таких випадків: для еталонної прямої S0 параметр приймає максимальне значення; прямі , S0 збігаються з осями X, Y еталона; прямі , S0 взаємно ортогональні, але не збігаються с осями еталона; прямі , S0 зай-мають яке завгодно положення на еталонному зображенні. Наприклад, встановлено відображення:

I(,): (6)

1=, =max, =min, (7)

, (8)

де 1, , , 2 параметри перетворень підгруп (1), (, ), (2) відповідно; 2, кути нахилу обраної еталонної прямої та її образу; max, min максимальне та мінімальне значення ; кут нахилу прямої вхідного зображення, для якої =max;

: (9)

, (10)

, , (11)

де , hx, , параметри перетворень підгруп (), (hx), (, ) відповідно; 1, 1, , 2, 2, параметри ОН для обмежень на прямі , S0, що збігаються з осями X, Y еталона. Також встановлено відображення I(, ) для інших розкладань.

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

1. Перехід до центроафінної групи шляхом нормалізації зсуву.

2. Визначення параметрів індукованих перетворень на прямих сім'ї S0 (ОН).

3. Одержання афінних параметрів та приведення зображення до вигляду еталона.

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

Для того, щоб результати ОН на прямих сім'ї S0 дозволяли визначити параметри , , , групи , необхідно знайти параметри індукованих перетворень , для двох пар відповідних обмежень. Індуковані перетворення g, gl, що відповідають перетворенню g , на прямих lS0 набувають вигляду (1). Параметри , визначаються за допомогою базового алгоритму ОН, який розроблено для випадку інваріантних множин. У результаті цього знаходяться значення 1, 1, 2, 2, де 1, 1 параметри ОН першої , та другої , пари обмежень еталонного та вхідного зображень.

Для того, щоб обмеження зображень дали можливість приймати рішення про віднесення вхідного зображення до одного з класів еквівалентності, необхідне виконання умови несхожості: , i, j =1,…,; r, t=1,…, m, крім випадку одночасного рівняння i=j и r=t, де кількість еталонних прямих зображення (при роботі з центроафінною групою за базовим алгоритмом =2, за уточнюючим =n2, n кількість повторень базового алгоритму); m кількість еталонів; 0 деяка гранична величина, яка залежить від подібності еталонів та завадової обстановки.

Нехай є множина еталонів , t=1,…, m, на кожному з яких зазначені обмеження на прямі lj S, j=1,…, , що задовольняють умові несхожості. Для вирішення задачі розпізнавання вхідного зображення B шляхом нормалізації на базі одновимірних процедур правило ОН (2) поширюється на всю множину еталонних зображень і має вигляд:

, (12)

де обмеження еталонного зображення на j-у пряму сім'ї S; обмеження вхідного зображення B на i-у пряму сім'ї S.

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

Для одержання параметрів , , , на базі параметрів ОН в роботі розроблено два способи:

- на основі розкладань центроафінної групи у суперпозицію підгруп;

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

Нормалізація за допомогою спільного використання одновимірного аналізу і різних розкладань центроафінної групи висвітлюється в роботах [1, 3]. В основі цього методу лежить побудова відображень I(), Q , що дозволяє одержати зв'язок параметрів ОН 1, , 2, з параметрами центро-афінного перетворення , , , . В залежності від початкових умов застосовуються різні розкладання центроафінної групи.

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

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

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

В результаті експериментів встановлено залежність імовірності правильного розпізнавання методом ОН від величин d, d кроків зміни індукованих параметрів , . Експерименти проводилися на півтонових зображеннях розміром 256*256 пікселів. У ході експериментів отримано такий результат: імовірність правильного розпізнавання, яка дорівнює 0,96 і вище, досягається при величині кроків d1, d0,01. Однак при роботі з аналогічними зображеннями більш великих розмірів імовірність 0,96 досягається, коли максимальна величина кроків менша. Це пояснюється тим, що неточності нормалізації центроафінного перетворення найпомітніші по краях зображення і збільшуються зі збільшенням його розміру.

Оцінено, що швидкодія методу розпізнавання на базі ОН у порівнянні
з інтегральним кореляційним краща на три порядки, однак гірша на один порядок від методу нормалізації шляхом обчислення функціоналів. Встановлено, що за наявності шумів метод ОН забезпечує правильне розпізнавання з імовірністю 0,96 при співвідношенні сигнал/шум: А>7, і тим самим поступається за завадозахищеністю інтегральному кореляційному (А>3), але кращий за метод нормалізації на базі обчислення функціоналів (А>10). За наявності локальних завад методи ОН кращі ніж інтегральні. Проведені дослідження методів ОН дозволяють зробити висновок, що вони мають перевагу у використанні перед інтегральним кореляційним та методом нормалізації шляхом обчислення функціоналів, оскільки вони суттєво перевершують перший за швидкодією та другий за завадозахищеністю.

На базі методу ОН розроблено програмний модуль CarAffineRecognition, призначений для розпізнавання моделей автомобільного транспорту. Даний модуль використовується в ТОВ НВФ “Оптима”. Розроблено також програмний модуль SpacePhotoNorm, основною функцією якого є суміщення шляхом нормалізації знімків з ресурсних супутників Землі, створених при напрямку зйомки за місцевою вертикаллю. Як тестові були використані знімки Харківської області одного сезонного періоду із супутників Landsat4 (сенсор ТМ), Landsat7 (сенсор EТМ) та Terra (сенсор Aster). Програмний модуль SpacePhotoNorm впроваджено у ННЦ ІГА.

У додатках наведено алгоритми нормалізації однопараметричних і деяких багатопараметричних підгруп афінної групи шляхом використання інваріантних властивостей сімей прямих; обґрунтування застосування методу ОН для суміщення космічних знімків із супутників Landsat4 (сенсор ТМ), Landsat7 (сенсор EТМ), Terra (сенсор Aster); приклади космічних знімків, а також результати їхнього суміщення; акти про впровадження.

ВИСНОВКИ

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

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

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

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

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

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

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

7. Запропонований підхід до розпізнавання і нормалізації зображень шляхом одновимірних нормалізацій реалізовано у вигляді універсального дослідницького програмного комплексу, а також двох спеціалізованих програмних модулів, один з яких призначений для суміщення космічних знімків шляхом їхньої нормалізації і впроваджений у ННЦ ІГА в системі обробки космічних знімків, другий призначений для розпізнавання автомобілів і впроваджений у системі ідентифікації автомобільного транспорту в ТОВ НВФ “Оптима”.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Путятин Е. П., Яковлева Е. В. Любченко В. А. Разложение матрицы центроаффинного преобразования для нормализации изображений // Радиоэлектроника и информатика. 1998. № 4(05). С. 9194.

2. Путятин Е. П., Яковлева Е. В. Любченко В. А. Исследование инвариантных прямых и их применение в алгоритмах нормализации изображений // АСУ и приборы автоматики. Харьков: ХТУРЭ, 1999. Вып. 109. С. 8495.

3. Путятин Е. П., Яковлева Е. В., Луцив В. В. Синтез нормализаторов аффинных преобразований на базе одномерных корреляций // Радиоэлектроника и информатика. 1999. № 4(9). С. 7683.

4. Яковлева Е. В. Исследование свойств подгрупп центроаффинного преобразования для нормализации изображений // Проблемы бионики. Харьков: ХНУРЭ, 2001. Вып. 54. С. 5159.

5. Путятин Е. П., Яковлева Е. В. Исследование свойств центральных прямых для нормализации аффинных преобразований изображений // АСУ и приборы автоматики. Харьков: ХНУРЭ, 2002. Вып. 121. С. 3542.

6. Яковлева Е. В. Об одном подходе к решению задачи нормализации аффинных преобразований на базе одномерных корреляций // Вестник НТУ “ХПИ”. Новые решения в современных технологиях. Харьков: НТУ “ХПИ”, 2002. Вып. 3. С. 7883.

7. Путятин Е. П., Яковлева Е. В., Любченко В. А. Применение свойств аффинной группы геометрических преобразований для нормализации изображений // Сб. научн. тр. по материалам 7-й Междунар. конференции “Информационные технологии: наука, техника, технология, образование, здоровье” (MicroCAD99). Харьков: ХГПУ, 1999. Вып.7. Ч. 1. С. 169172.

8. Яковлева Е. В., Любченко В. А. Применение одномерной нормализации и разложения матрицы центроаффинного преобразования для нормализации изображений // Сб. наук. праць за матеріалами 3-го Міжнар. молод. форуму “Радіоелектроніка і молодь у ст.”. Харків: ХТУРЕ, 1999. Ч.2. С. 481484.

9. Путятин Е. П., Яковлева Е. В., Любченко В. А. Применение одномерной нормализации при распознавании изображений // Тезисы докладов Междунар. молод. научн. конференции “XXV Гагаринские чтения”. Москва, 1999. Т. 1. С. 193194.

10. Любченко В. А., Яковлева Е. В. Пути повышения эффективности метода одномерной нормализации при распознавании образов // Сб. научн. тр. по материалам 6-й междунар. конференции “Теория и техника передачи, приема и обработки информации” (“Новые информационные технологии”). Харьков: ХТУРЭ, 2000. С. 285287.

11. Яковлева Е. В. Условия синтеза последовательных нормализаторов изображений при разложении многопараметрических групп // Сб. научн. тр. по материалам 5-го Междунар. молод. форума “Радиоэлектроника и молодежь в веке”. Харьков: ХТУРЭ, 2001. Ч. 1. С. 384385.

12. Яковлева Е. В. Нормализация сложных преобразований изображений путем перехода к одномерным корреляциям на центральных прямых // Анотації доповідей міжнар. науково-практ. конференції “Інформаційні технології: наука, техніка, технологія, освіта, здоров'я” (MicroCAD-2002). Харків: НТУ “ХПІ”, 2002. С. 3132.

13. Яковлева Е. В. Нормализация аффинных искажений космических снимков // Материалы 7-го Междунар. молод. форума “Радиоэлектроника и молодежь в ХХІ веке”. Харьков: ХНУРЭ, 2003. С. 281.

14. Яковлева Е. В. Распознавание автомобильного транспорта путем нормализации // Анотації доповідей міжнар. науково-практ. конференції “Інформаційні технології: наука, техніка, технологія, освіта, здоров'я” (MicroCAD-2003). Харків: НТУ “ХПІ”, 2003. С. 62.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за фахом 05.13.23 системи та засоби штучного інтелекту. Харківський національний університет радіоелектроніки, Харків, 2004.

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

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

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

Яковлева Е. В. Методы одномерных нормализаций аффинных преобразований в задачах распознавания изображений. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 системы и средства искусственного интеллекта. Харьковский национальный университет радиоэлектроники, Харьков, 2004.

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

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