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

Любченко Валентин Анатолійович

УДК 004.932: 007.52

МАТЕМАТИЧНІ МОДЕЛІ ТА МЕТОДИ НОРМАЛІЗАЦІЇ

ПРОЕКТИВНИХ ПЕРЕТВОРЕНЬ В СИСТЕМАХ

ОБРОБКИ ЗОБРАЖЕНЬ

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

АВТОРЕФЕРАТ

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

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

Харків – 2004

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

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

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

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

начальник кафедри математичного і
програмного забезпечення АСУ;

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

професор Борисенко Олексій Андрійович,

Сумський державний університет,

завідувач кафедри електроніки і
комп’ютерної техніки.

Провідна установа - Інститут проблем машинобудування ім. А.М. Підгорного НАН України (відділ
математичного моделювання та оптимального
проектування), м. Харків.

Захист відбудеться „22” червня 2004 р. о 13-00 годині на засіданні спеціалізованої вченої ради Д .052.02 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

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

Автореферат розіслано „ 21” травня 2004 р.

Вчений секретар

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки (ХНУРЕ) в рамках держбюджетних тем № ДР U003416 “Концептуальні підходи та моделі розпізнавання зображень в умовах регулярних і випадкових збурень для систем реального часу” (автор був виконавцем: розроблено методи та алгоритми нормалізації перспективних перетворень); №ДР0103U001572 “Дослідження та розробка методів аналізу зображень в умовах складних збурень” (автор є відповідальним виконавцем: розроблено методи та алгоритми нормалізації проективних перетворень).

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

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

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

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

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

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

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

Наукова новизна результатів дисертаційної роботи полягає в розробці методів зорового сприйняття і нормалізації зображень на основі проективної геометрії в системах обробки зображень. Були отримані наступні результати:– 

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

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

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

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

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

Результати дисертаційної роботи знайшли застосування в ТОВ НВФ “Оптима” при розробці методів нормалізації проективних перетворень зображень автомобілів, реалізованих у програмному модулі NormalizProektiv. Даний модуль є складовою частиною програмного комплексу ідентифікації транспортних засобів. Робота виконувалась відповідно до договору від .03.03 р. про науково-технічне співробітництво між кафедрою інформатики ХНУРЕ і ТОВ НВФ “Оптима” (акт від 29.07.2003 р.). Розроблені методи одновимірної і двовимірної проективної нормалізації були застосовані в Харківському державному відділенні комплексних досліджень і оцінки впливу на навколишнє середовище при розробці методів нормалізації зображень перетинів землі, що були отримані з радіолокатора підповерхневого зондування “Терразонд 3” (Розробки велися відповідно до робочого плану за проектом “Радар” у період з 16 жовтня 2001 р. по 30 квітня 2002 р., акт від .08.2003 р.). Результати дисертаційної роботи знайшли застосування в навчальному процесі при проведенні лекційних занять і підготовці методичних посібників для проведення лабораторного практикуму з курсів “Математичне й інформаційне забезпечення систем обробки складних сигналів”, “Алгоритми і програмне забезпечення синтезу зображень”, а також при підготовці навчального посібника “Information systems technology. Image processing and patter recognition” (акт від .09.2003 р.).

Особистий внесок здобувача. У роботах, що опубліковані в співавторстві, здобувачеві належать:

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

Апробація результатів дисертації. Основні результати роботи доповідалися й обговорювалися в 9 доповідях на 8 конференціях: на 4 - 7 Міжнародних молодіжних форумах “Електроніка і молодь у XXI столітті” (Харків, 2000 - 2003), Міжнародних конференціях “Теорія і техніка передачі, прийому й обробки інформації” (Харків-Туапсе, 2000 - 2003).

Публікації. За темою дисертаційної роботи опубліковано 16 друкованих робіт, 7 з яких у виданнях, зазначених в переліку фахових видань ВАК, 8 – у збірниках наукових праць за матеріалами конференцій та 1 – анотація доповіді на конференції.

Структура й обсяг дисертаційної роботи. Дисертація складається із вступу, п’яти розділів, висновків, списку використаних літературних джерел з 124 найменувань на 11 сторінках, 2 додатків на 6 сторінках. Робота містить 39 рисунків, 7 таблиць. Загальний обсяг роботи складає 145 сторінок.

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

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

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

Рис. . Схема виникнення проективного перетворення:

Ф – точка сприйняття; О – об’єкт, за яким ведуть спостереження; і – можливі площини сприйняття зображень об’єкта під час його руху; В1, В2 – зображення об’єкта в площинах і ; a, b, c, d – параметри, які характеризують відстані між образами точок площин і , що забезпечують виникнення проективних перетворень між зображеннями.

У системах обробки зображень геометричні перетворення часто розглядають в рамках теорії груп. Для цього всі зображення Вg об’єкта О розглядають як результат дії на еталонне зображення В0 перетвореннями з деякої групи G, тобто В0 = gBg, де gG. Нормалізація в цьому випадку розглядається як процедура знаходження параметрів перетворення gG. Трудомісткість процедури нормалізації напряму залежить від кількості параметрів групи.

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

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

Обмеженням зображення В на пряму є та частина зображення, що збігається з розташуванням прямої і позначається B(). Фізично це означає перетин зображення уздовж прямої . Нехай сімейство {} складається з s () рівновіддалених прямих, паралельних вісі ординат, що знаходяться в полі зору D. Тоді обмеження на прямі В() зображення В формуються з тих ділянок зображення, що перетинаються з прямими сімейства {}. Аналогічно отримують обмеження на горизонтальні прямі. Власне кажучи, дискретизація – це і є обмеження на вертикальні або горизонтальні прямі з досить малим кроком. Однак, використання горизонтальних і вертикальних прямих при складних перетвореннях часто обмежено за можливостями. Більш універсальним є аналіз обмеження зображення В на прямі {}, що проходять через задану опорну точку з однаковим кутом між і (рис. ).

а) б)

Рис. 2. Перехід від зображення до його обмежень на сімейство прямих {},
що проходять через задану точку: а) обмеження B() зображення В
при виборі 90 прямих, б) обмеження B() зображення В - 45 прямих.

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

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

На першому етапі побудови принципу нормалізації проективного перетворення розглядаються дві можливості:

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

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

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

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

, (1)

де B0, B - еталонне та вхідне зображення;

() - параметри проективного перетворення,

визначаємо два принципово різних нормалізатори:

, ,

де - нормалізатор повної проективної групи перетворень;  - нормалізатор афінної групи перетворень; - нормалізатор деякого перспективного перетворення; - нормалізатор зсуву; - нормалізатор центропроективної проективної групи перетворень (, ).

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

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

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

, . (2)

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

, (3)

де , - еталонне і перетворене зображення відповідно; , - енергія зображень , відповідно.

Залежність (3) дає змогу зробити декілька висновків:

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

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

Це дозволило для нормалізатора параболічної гомології

(4)

побудувати наступні функціонали:

- функціонал, який напряму випливає із (3):

=0; (5)

- функціонал, який базується на перерозподілі енергії зображення:

, (6)

де , - енергія, а , S - площа зображень , відповідно.

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

, (7)

де - енергія прямої на еталоні;

- енергія образу прямої , y 0.

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

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

, ,

де m, n – параметри зсуву уздовж вісі ординат вхідного і еталонного зображень; t, k – параметри зсуву уздовж вісі абсцис вхідного і еталонного зображень;  параметр параболічної гомології при незміщених зображеннях.

Матриця, що відповідає даному перетворенню, має вигляд:

.

Якщо вдається для зображень провести процедуру центрування, тоді і зображення можна розглядати під дією перетворення, яке являється композицією базових перетворень , в якому D(a,2) – стиск із параметром ; Py(h) – параболічна гомологія уздовж вісі ординат з параметром ; - косий зсув з параметром , де .

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

,

де - нормалізатор масштабу; - нормалізатор параболічної гомології виду (4); – нормалізатор косого зсуву уздовж вісі абсцис.

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

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

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

, (8)

матрицю яких можна представити у вигляді композиції:

Пц.о = DP, (9)

де - матриця перетворення масштабу з параметром m,

- матриця перспективи з параметром t.

На основі розкладання (9) нормалізатор перетворення (8) можна представити у вигляді синтезу двох базових нормалізаторів:

,

де - нормалізатор масштабу на прямій;

- нормалізатор перспективного перетворення на прямій.

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

,

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

Повна двовимірна група перетворень задається математичною моделлю (1). З існування проективних перетворень випливає, що параметри b31, b32, b33 одночасно не рівні нулю, отже повну проективну групу можна розглядати як восьмипараметричну в одному із виглядів, які представлені матрицями:

, , .

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

П1 = ANK, П2 , П2 , П2 = ПцСxy,

П3 = I, П3 = I,

де Px (n), Py (m) – перспективи уздовж координатних осей з параметрами n і m; P (h) – перспектива з параметром h уздовж прямої з кутом нахилу рівним ; - зсув уздовж координатних осей; - центропроективне перетворення (, ); , - афінні перетворення; , - безпараметричні ортогональні проективні перетворення.

Центропроективне перетворення можна також представити у вигляді розкладання:

Пц = D(m, n)Py(t) Px(k) () U(),

де D(m, n) – стиск уздовж координатних осей з параметрами m, n; Px (k), Py (t) – перспектива уздовж координатних осей з параметрами k, t; () – косий зсув уздовж вісі абсцис на кут ; U() – поворот на кут .

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

На основі її розкладань отримані такі послідовні нормалізатори проективної групи:

, , ,

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

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

, ,

де - нормалізатор повороту.

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

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

Як окрема задача розглянуто питання знаходження інтервалу можливих значень перспективних та проективних перетворень. Експериментально була встановлена залежність інтервалу можливих значень параметру перспективного перетворення від розмірів поля зору. Так, наприклад, якщо розміри поля зору мають порядок 103, то величина має порядок 10-3, якщо розглядати поле зору порядку 102 – має порядок 10-2, при розгляді поля зору порядку 10 – має порядок 10-1. Тобто при збільшенні порядку розмірів поля зору величина параметру перспективного перетворення зменшується на порядок.

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

Експериментальні дослідження для двовимірних зображень підтвердили, що при відомій точці або вісі проективного перетворення можна знайти параметри нормалізації проективного перетворення. У порівнянні з кореляційним, розроблені методи нормалізації мають більш низьку трудомісткість. Так, для нормалізації перспективи при невідомій точці перетворення, трудомісткість методу кореляції оцінюється як O(m3), у порівнянні з розробленим – O(m). Для центрованих зображень розроблений метод має трудомісткість O(m2) плюс трудомісткість одного з відомих методів нормалізації центроафінного перетворення, що значно менше від трудомісткості кореляційного методу – O(m6). При відомому напрямку вісі перетворення перспективи, розроблений метод нормалізації проективних перетворень має трудомісткість O(m) плюс трудомісткість одного з відомих методів нормалізації афінного перетворення, що значно менше трудомісткості кореляційного методу – O(m8).

Отримані результати були застосовані в практичних задачах:

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

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

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

Трудомісткість розроблених методів значно нижча від кореляційних. Так, для нормалізації перспективи при невідомій точці перетворення, трудомісткість методу кореляції оцінюється як O(m3), у порівнянні з розробленим – O(m). Для центрованих зображень розроблений метод має трудомісткість O(m2) плюс трудомісткість одного з відомих методів нормалізації центроафінного перетворення, що значно менше трудомісткості кореляційного методу – O(m6). При відомому напрямку вісі перетворення перспективи, розроблений метод нормалізації проективних перетворень має трудомісткість O(m) плюс трудомісткість одного з відомих методів нормалізації афінного перетворення, що значно менше трудомісткості кореляційного методу – O(m8).

Результати дисертаційної роботи знайшли застосування в ТОВ НПФ “Оптима” при розробці методів нормалізації проективних перетворень зображень автомобілів, реалізованих у програмному модулі NormalizProektiv. Модуль є складовою частиною програмного комплексу ідентифікації транспортних засобів. Розроблені методи одновимірної і двовимірної проективної нормалізації були застосовані в Харківському державному відділенні комплексних досліджень і оцінки впливу на навколишнє середовище при розробці методів нормалізації зображень перетинів землі, одержуваних з радіолокатора підповерхневого зондування “Терразонд 3”. Результати дисертаційної роботи були використані в навчальному процесі Харківського національного університету радіоелектроніки під час проведення лекційних занять і підготовки методичних посібників для проведення лабораторного практикуму.

СПИСОК опублікованИХ ПРАЦЬ за темою дисертації

1. Любченко В.А., Путятин Е.П. Нормализация проективной группы // АСУ и приборы автоматики. – 2002. – Вып. 120. – С.112 – 117.

2. Любченко В.А., Путятин Е.П. Математические модели разложения проективных преобразований в задачах нормализации // Радиоэлектроника и информатика. – 2002. - №2(19). – С.57-59.

3. Любченко В.А., Путятин Е.П. Математические модели зрительного восприятия и нормализации изображений // Проблемы бионики. – 2002. – №56. – С. 44 – 48.

4. Гарячевская И.В., Любченко В.А., Путятин Е.П.  Проблема построения базы данных для системы поиска и распознавания изображений // Радиоэлектроника и информатика. – 2002. - №1(18). - С.40-42.

5. Любченко В.А., Путятин Е.П. Математические модели нормализации перспективы // Проблемы бионики – 2000. - №53. – Ст.22-27.

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

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

8. Любченко В.А. Математические модели зрительного восприятия // Сб. научн. тр. по материалам 7-го Межд. молодежного форума “Радиоэлектроника и молодежь в XXI веке”. – Харьков: ХНУРЭ. – 2003. С.283.

9. Любченко В.А. Особенности проективных искажений в задачах нормализации изображений // Тезисы докладов Межд. научн. конф. “Теория и техника передачи, приема и обработки информации” Харьков-Туапсе. 2003г. – С. 260-261.

10. Любченко В.А. Применение одномерной нормализации в задачах распознавания изображений при проективных искажениях // Сб. научн. тр. по материалам 6-го Межд. молодежного форуму “Радиоэлектроника и молодежь в XXI веке”. Ч.2. - Харьков: ХНУРЭ. - 2002. С.388-389.

11. Любченко В.А., Путятин Е.П. Применение разложения центропроективной группы в задачах нормализации изображений // Сб. научн. тр. по материалам 8 Межд. конф. “Теория и техника передачи, приема и обработки информации”. – Харьков: ХНУРЭ. – 2002. – С. 541 – 542.

12. Любченко В.А. Нормализация и свойства параболической перспективы // Сб. научн. тр. по материалам 5-го Межд. молодежного форума “Радиоэлектроника и молодежь в веке”. Ч.1. Харьков: ХТУРЭ. 2001. С. 278-279.

13. Любченко В.А., Путятин Е.П. Математические модели разложения проективных преобразований в задачах нормализации // Сб. научн. тр. по материалам 7 Межд. конф. “Теория и техника передачи, приема и обработки информации” Харьков: ХТУРЭ. – 2001. – С. 432 – 433.

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

15. Гарячевская И.В., Любченко В.А. Информационная система хранения и поиска информации об изображениях // Сб. научн. тр. по материалам 4-го Межд. молодежного форуму “Радиоэлектроника и молодежь в XXI веке”.- Харьков: ХТУРЭ. - 2000. - С.279-280.

16. Гарячевская И.В., Любченко В.А. Система хранения и поиска информации о изображениях // Сб. научн. тр. по материалам 6-й Межд. конф. “Теория и техника передачи, приема и обработки информации”. Харьков: ХТУРЭ. 2000. С.276 – 278.

АНОТАЦІЯ

Любченко В. А. Математичні моделі і методи нормалізації проективних перетворень у системах обробки зображень. - Рукопис

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

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

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

АННОТАЦИЯ

Любченко В.А. Математические модели и методы нормализации проективных преобразований в системах обработки изображений. – Рукопись.

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

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

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

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

На основе полученных свойств (с точки зрении нормализации) перспективного преобразования (параболической гомологии) разработан критерий его присутствия на изображении. Он был реализован в виде функционала, лежащего в основе нормализатора.

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

На основании разработанных методов предложено несколько алгоритмов нормализации проективной группы преобразований, использующих последовательные нормализаторы.

Полученные алгоритмы нормализации были разделены на два вида, которые определяются решаемой первоначальной задачей:

- нормализация перспективного преобразования;

- центрирование изображений в условиях действия проективных преобразований.

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

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

Трудоемкость разработанных методов значительно ниже трудоемкости корреляционных. Так, для нормализации перспективы при неизвестной точке преобразования, трудоемкость метода корреляции оценивается как O(m3), по сравнению с разработанным – O(m). Для центрированных изображений разработанный метод имеет трудоемкость O(m2) плюс трудоемкость одного из известных методов нормализации центроаффинного преобразования, что значительно меньше трудоемкости корреляционного метода равной O(m6).

При известном направлении оси преобразования перспективы, разработанный метод нормализации проективных преобразований имеет трудоемкость O(m) плюс трудоемкость одного из известных методов нормализации аффинного преобразования, что значительно меньше трудоемкости корреляционного метода равной O(m8).

Результаты диссертационной работы нашли применение в ООО НПФ “Оптима” при разработке методов нормализации проективных искажений изображений автомобилей, реализованных в программном модуле NormalizProektiv. Модуль является составной частью программного комплекса идентификации транспортных средств. Разработанные методы одномерной и двумерной проективной нормализации были применены в Харьковском государственном отделении комплексных исследований и оценки воздействия на окружающую среду при разработке методов нормализации изображений сечений земли, получаемых с радиолокатора подповерхностного зондирования “Терразонд 3”.

Ключевые слова: нормализация изображений, проективная группа преобразований, преобразования перспективы, эталон, математические модели восприятия.

ABSTRACT

Lyubchenko Valentin Anatolievich. Mathematical models and