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

Машталір Сергій Володимирович

УДК 004.932: 007.52

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

БІНАРНИХ ПЕРЕРІЗІВ ЗОБРАЖЕНЬ

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

Автореферат

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

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

Харків – 2004

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

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

Науковий керівник – доктор технічних наук, професор Путятін Євгеній Петрович,

Харківський національний університет радіоелектроніки, завідувач кафедри інформатики.

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

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

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

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

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

Захист відбудеться “22” лютого р. о 1300 годині на засіданні спеціалізованої вченої ради Д .052.02 у Харківському національному університеті радіоелектроніки (61166, м. Харків, пр. Леніна, 14).

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

Автореферат розіслано “13” січня 2005 р.

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

спеціалізованої вченої ради _____________________  Безкоровайний В.В.ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

Основний вплив на розвиток методів обробки зображень в умовах різного роду збурювань зробили дослідження українських і закордонних учених: В.В. Авраменко, А.М. Ахметшина, Р.А. Воробеля, Г.П. Катиса, В.А. Ковалевського, В.П. Кожем’яко, В.Г. Лабунця, Є.П. Путятіна, Б.Н. Русина, М.І. Шлезінгера, L.H.B.K.P.M.K. Hu, T.S.I.M.. У розвиток методів аналізу складної, у тому числі геометричної інформації, а також напівтонової і бінарної морфології найбільший внесок зробили Ю.І. Журавльов, І.Б. Сироджа, С.В. Смеляков, Ю.Г. Стоян, Ю.П. Шабанов-Кушнаренко, H.J.A.M. , P.A.G.A. Rosenfeld, J.S.R.а також ряд інших учених. Незважаючи на істотні досягнення в цій області, багато питань синтезу моделей і методів обробки множин бінарних зображень усе ще залишаються недослідженими, зокрема, задачі аналізу сімейств бінарних перерізів в умовах впливів, що заважають, вимагають свого рішення в силу можливостей уніфікації і простоти реалізації потенційних методів, які володіють подібними показниками ефективності з алгоритмами обробки напівтонових зображень.

Зв’язок роботи з науковими програмами, планами, темами. Дисертація виконана на кафедрі інформатики Харківського національного університету радіоелектроніки в рамках держбюджетних науково-дослідних робіт: “Дослідження і розробка методів аналізу зображень в умовах складних перекручувань” (№ ДР 0103U001572, виконавець), “Розробка теоретичних основ і математичного забезпечення нейро-фаззі-систем ранньої діагностики, прогнозування і моделювання в умовах апріорної і поточної невизначеності” (№ ДР 0101U001762, відповідальний виконавець розділу “Розробка теоретичних основ і алгоритмів розпізнавання в багатомірних ознакових просторах в умовах невизначеності”), “Інтелектуальний аналіз і обробка даних у реальному масштабі часу на основі засобів обчислювального інтелекту” (№ ДР 0104U003432, відповідальний виконавець розділу “Методи морфологичної обробки бінарних зображень в умовах геометричних перетворень”) координаційного плану Міністерства освіти та науки України, а також ряду робіт з договорів про науково-технічне співробітництво.

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

Для досягнення мети треба розв’язати такі задачі: –

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

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

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

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

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

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

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

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

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

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

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

Матеріали дисертації впроваджені в Науковому центрі Військ ППО України при розробці програмно-алгоритмічного комплексу “Основа-ТВ” (акт про упровадження від 7.05.2004 р.), у Харківському державному технічному університеті сільського господарства при проведенні досліджень і розробці мікропроцесорних засобів розпізнавання образів у системах точного землеробства для АПК України (акт про упровадження від 11.03.2004 р.), у Науковому метрологічному центрі військових еталонів при виконанні робіт з дослідження метрологічних характеристик вихідних і робочих еталонів (акт про упровадження від 11.10.2004 р.), у навчальному процесі в Харківському національному університеті радіоелектроніки (акт про упровадження від 11.10.2004 р.).

Особистий внесок здобувача. Усі положення, що виносяться на захист, отримані здобувачем особисто. З 14 публікацій за темою дисертації 7 робіт на-писані в співавторстві, у яких здобувачу належать постановки задач, вибір і обґрунтування їхнього рішення, а також: [2] – модель представлення напів-тонових зображень множинами бінарних перерізів; метод морфологічної нормалізації по крайніх точках – [4], по скелетонах – [6]; [5] – дослідження властивостей n-арних відносин на бінарних перерізах зображень; [8] – до-слідження прикладних аспектів морфологічної нормалізації; [11] – алгоритмізація морфологічної обробки перерізів; [13] – аналіз особливостей по-шук характерних точок.

Апробація результатів дисертаційної роботи. Матеріали дисертацій-них досліджень доповідалися, обговорювалися і були схвалені на таких нау-ково-технічних конференціях і семінарах: VI, VIII, IX Міжнародних конференціях “Теорія і техніка передачі, прийому та обробки інформації” (2000, 2002, 2003 р., Харків-Туапсе); 4, 5, 7, 8 Міжнародних молодіжних форумах “Радіоелектроніка і молодь у XXI столітті” (2000, 2001, 2003, 2004 р., Хар-ків); International Conference on Computer Vision and Graphics (ICCVG 2004, Warsaw, Poland), Міжнародної науково-технічної конференції “Штучний ін-телект. Інтелектуальні і багатопроцесорні системи” (Таганрог-Донецьк, 2004), Міжнародної науково-технічної конференції “Автоматика” (Київ, 2004).

Публікації. Основні наукові положення дисертації відбиті в 14 роботах, серед яких 3 статті в 3 різних журналах, 1 стаття в збірнику наукових праць (усі – у виданнях, включених у переліки ВАК України), 10 публікацій у працях, матеріалах і тезах різних конференцій.

Обсяг та структура дисертації. Дисертаційна робота складається із вступу, 4 розділів, висновків, списку використаної літератури із 253 джерел на 23 с., 2 додатків на 19 с. Загальний обсяг становить 171 с., основного тексту – 124 с., ілюстрацій – 41 (з них 7 на 5 окремих сторінках), таблиць – 5 (з них 2 на 8 окремих сторінках).

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

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

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

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

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

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

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

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

, (1)

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

. (2)

Тут значення , , взагалі кажучи, індукуються розбивкою (1). Тоді кожен бінарний переріз задається виразом

де .

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

Для бінарних відносин уведені індикаторні функції

(3)

де значення “–1” означає, що , є точками різних об’єктів, “1” – того самого об’єкта, “0” – інформації для ухвалення рішення недостатньо. Далі будемо позначати , . З метою вибору можливих перетворень множин бінарних перерізів вивчено, як і при яких умовах відображення , множини на , де  – узагалі кажучи, довільна множина (на практиці часто ), модифікують або не змінюють (3). Нехай індикаторна функція індукує тризначну функцію зі значеннями –1, 0, 1

, (4)

де . Установлено необхідні і достатні умови для виконання (4) у залежності від властивостей відносин . Зокрема:

(5)

(6)

; (7)

; (8)

; (9)

. (10)

При виконанні умов (5) – (7) відношення являє собою відношення толерантності, тобто, використовуючи його, можна оперувати поняттям “подібності”, що стосовно до обробки бінарних перерізів зображень природним образом інтерпретується як геометрична конгруентність (наявність спільних точок, фрагментів границь і ін.). При справедливості (5) – (7), (9) відношення є еквівалентністю, тобто, оперуючи поняттям “узагальненої рівності”, можна аналізувати розбивки бінарних перерізів з позицій їхньої приналежності зображень одному чи декільком об’єктам. При виконанні умов (5), (6), (9) одержуємо відношення часткового порядку, тобто інструмент аналізу множин бінарних перерізів з погляду вкладеності розбивок поля зору. Нарешті, використовуючи всю сукупність умов (5) – (10), можна розглядати упорядкованість перерізів з можливістю порівняння всіх елементів розбивок.

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

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

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

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

Нехай , де , , дія має вигляд

, (11)

де – невироджена матриця другого порядку, – вектор паралельного переносу. Кожне з зображень представлено бінарними перерізами: , де – вагові коефіцієнти, обумовлені (2). Зрозуміло, що . Задача полягає в пошуку за відомими сімействами , параметрів перетворень зображень , .

Елементи множини названі особливими точками, якщо . Індексовані особливі точки названі характерними точками, якщо існує підстановка така, що .

Відображення повинно задовольняти умовам

, (12)

, (13)

, (14)

. (15)

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

, ,

задовільняють умовам (12) – (15).

Базовими операціями бінарної морфології є: “розширення” (в оригіналі – dilation), співпадаюче з додаванням по Мінковському

и “звуження” (в оригіналі – erosion)

,

де , – фіксована множина, яка зветься структурним елементом та фактично визначає результат.

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

На основі інваріантності відносин площин при афінних перетвореннях проводиться пошук такого, що

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

,

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

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

,

де , , , , , , ,

продукує особливі точки, які формують афінно-еквівалентний скелетон

.

Значення відповідає умові .

На базі представлення скелетона в вигляді графа: , де , , – індексна множина, , а підмножина інцидентних вершин скелетона має вигляд , розглядаються триплети такі, що

. (16)

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

,

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

, .

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

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

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

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

,

де – слід матриці. – матриця, яка визначає задане (відоме) афінне перетворення, – матриця знайденого афінитету.

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

.

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

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

Шляхом експериментальних досліджень (усередненням результатів по 10 зображенням і 5 перетворенням) установлено, що для виконання морфологічної нормалізації досить використовувати поля зору, що мають 400 – 460 відліків по кожній з координат (рис. 4) і 3 – 6 бінарних перерізів, тому що при подальшому зросту цих характеристик точність і надійність практично не поліпшуються.

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

9. Результати теоретико-експериментальних досліджень реалізовані та впроваджені у виді прикладних і дослідницьких програмних комплексів, два з яких сертифіковані УкрСЕПРО. Результати дисертації орієнтовані на ефективне використання в системах технічного зору, які призначені для обробки та інтерпретації відеоданих при геометричних перетвореннях в реальному масштабі часу.

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

1. Машталир С.В. Модель обработки множеств бинарных сечений // Вестник Херсонского государственного технического университета. – 2004. – № (19). – С. 92–95.

2. Машталир С.В., Мегель Ю.Е., Путятин Е.П. Анализ изображений биологических объектов по бинарным сечениям // Радиоэлектроника и информатика. – 2004. – № . – С. –121.

3. Машталир С.В. Поиск аффинитета на основе скелетонизации бинарных изображений // Прикладная радиоэлектроника. – 2003. – Т. 2, № 2. – С. 188–192.

4. Машталир С.В., Путятин Е.П. Морфологическая обработка изображений динамических объектов // Автомобильный транспорт. Вып. 12. – Харьков: ХНАДУ, 2003. – С. 55–58.

5. Машталир С.В., Путятин Е.П. Свойства отношений на множествах бинарных изображений // Матер. междунар. научно-техн. конф. “Искусственный интеллект. Интеллектуальные и многопроцессорные системы”. – Таганрог: ТГРУ, 2004. – Т.2. – С. 259–263.

6. ChupikovMashtalir S., Yegorova E. Morphological normalization of image binary cuts // Book of abstracts of International Conference on Computer Vision and Graphics. – Warsaw: PJIIT. – 2004. – P. .

7. Машталир С.В. Операции над множеством бинарных сечений изображений // Матер. 8 междунар. молодежного форума “Радиоэлектроника и молодежь в XXI веке”. – Харьков: ХНУРЭ, 2004. – Т. 2. – С. 84.

8. Машталир С.В., Путятин Е.П. Нормализация изображений динамических объектов // Матер. 11-ої міжнар. конф. по автоматичному управлінню “Автоматика – 2004”. – Київ: НУПТ, 2004. – Т.1. – С. 78.

9. Машталир С.В. Представление структурных элементов при обработке бинарных сечений изображений // Матер. 7 междунар. молодежного форума “Радиоэлектроника и молодежь в XXI веке”. – Харьков: ХНУРЭ, 2003. – С. 520.

10. Машталир С.В. Применение скелетонов для поиска аффинно-эквива-лентных характерных точек изображений // Сб. тез. докл. по матер. меж-дунар. научн. конф. “Теория и техника передачи приема и обработки информации”. – Харьков: ХНУРЭ, 2003. – С. 319–320.

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

12. Машталир С.В. Геометрические преобразования бинарных сечений изображений // Сб. научн. трудов по матер. 5 междунар. молодежного форума “Радиоэлектроника и молодежь в XXI веке”. – Харьков: ХГТУРЭ, 2001. – Т. . – С. 73–74.

13. Машталир С.В., Путятин Е.П. Прямые методы нормализации изображений // Сб. научн. трудов по матер. 6 междунар. конф. “Теория и техника передачи приема и обработки информации”. – Харьков: ХГТУРЭ, 2000. – С. –322.

14. Машталир С.В. Модели геометрических преобразований изображений на базе алгебры Минковского // Сб. научн. трудов по матер. 4 междунар. молодежного форума “Радиоэлектроника и молодежь в XXI веке”. – Харьков: ХГТУРЭ, 2000. – Ч. 2. – С. 112–113.

АНОТАЦІЯ

Машталір С.В. Методи морфологічної нормалізації бінарних перерізів зображень. – Рукопис.

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

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

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

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

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

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

АННОТАЦИЯ

Машталир С.В. Методы морфологической нормализации бинарных сече-ний изображений. – Рукопись.

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

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

Предложен подход, основанный на использовании нетрадиционных моделей представления изображений в смешанных системах счисления в виде множеств бинарных сечений, соответствующих “эквипотенциальным” уровням функций распределения яркостей. Использованы хорошо апробированные в задачах распознавания трехзначные индикаторные функции, позволяющие принимать и отклонять некоторое решение или делать вывод о недостаточности данных для его принятия. Индикаторные функции определяются на отдельных сечениях или их наборах либо для отдельных пикселов, либо для фрагментов изображений. Изучены возможности преобразований множеств бинарных сечений при условии сохранения свойств индикаторных функций. Исследованы свойства бинарных и n-арных отношений, обеспечивающих анализ связей между отдельными элементами или областями двухградационных изображений и их семейств.

Обоснована целесообразность использования в качестве математического аппарата обработки двухградационных изображений в условиях геометрических преобразований аппарата бинарной математической морфологии, базирующейся на операциях алгебры Минковского. Разработаны, обоснованы, теоретически и экспериментально исследованы методы поиска аффинитета, основанные на автоматическом установлении характерных точек. Эти точки ищутся на множествах крайних или внутренних точек (скелетонах) изображений объектов. На первом этапе выделяются особенные точки (множества аффинно-эквивалентных точек, мощность которых сравнительно невелика), на втором – на основании инвариантности отношения площадей при аффинных преобразованиях устанавливается достоверная связь между индексациями их некоторых подмножеств. В результате продуцируются переопределенные системы линейных уравнений, решение которых и представляет собой необходимые для компенсации искажений коэффициенты. Исследованы пути повышения точности и надежности морфологической нормализации изображений.

При проведении экспериментальных исследований рассматривались два типа ошибок нормализации: в пространстве преобразований и в пространстве изображений. В качестве базовых выбраны 88 изображений и 7 различных аффинных преобразований с каждым из них. На основе дисперсионного анализа установлено, что нормализация изображений на базе анализа скелетонов не зависит от вида входных изображений, тогда как при использовании множеств крайних точек этого утверждать нельзя. В то же время первый метод является менее быстродействующим, но более помехоустойчивым. Экспериментальным путем доказано, что достаточно использовать не более 3 – 6 информативных сечений изображений (при дальнейшем увеличении их числа показатели точности и надежности практически не улучшаются) при представлении изображений с разрешением 400 – 460 точек по полю зрения. На примере биологических объектов обсуждены вопросы использования методов математической морфологии при нахождении геометрических характеристик изображений.

Реализация результатов диссертации проведена в виде программных комплексов обработки полутоновых и бинарных изображений, два из которых сертифицированы УкрСЕПРО. Исследованы особенности программной реализации методов морфологической нормализации, отличительной чертой которых является достаточная простота и высокая степень унификации всех операций преобразований изображений. При программно-аппаратной реализации методы могут весьма эффективно представляться SIMD и MIMD архитектурами. Проведен анализ результатов внедрения методов морфологической нормализации, рассмотрены пути их дальнейшего использования и развития.

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

ABSTRACT

Mashalir S.V. Morphological normalization methods of images bynary cuts. – Manuscript.

Thesis for candidate’s degree in technical science by speciality 01.05.02 – mathematical modeling and calculation methods. – Kharkiv National University of Radio Electronics, Kharkiv, 2004.

The thesis is devoted to problem solution of image processing under affine transformations, namely, to image normalization for computer vision.

On the basis of image non-traditional models in the form of binary cuts sets of graylevel continuos functions conditions imposed to 2 and n-arity relations are investigated, these properties provide an analysis of dependences between separate pixels or binary image domains or binary cuts sets. The properties of three-valued indicator functions and transformations of their arguments are researched.

By determination of affine-equivalent points (among image extremities and among skeleton pixels) methods of image transformation parameters searching are vindicated, produced, theoretically and experimentally investigated on the basis of mathematical morphology operations.

Reference feature of morphological normalization consists in sufficient simplicity and high level of all operations standardization at hardware-software implementation.

Keywords: image processing, affine transformations, mathematical morphology, binary cut.

Підп. до друку __.__.2004. Формат 60х84 1/16. Спосіб друку – ризографія.

Умов. друк. арк. 1,0. Облік. вид. арк. 1,1. Тираж 100 прим.

Зам. № Ціна договірна. __________________________________________________________________

ХНУРЕ, 61166, Харків, просп. Леніна, 14

__________________________________________________________________

Віддруковано в учбово-виробничому

видавничо-поліграфічному центрі ХНУРЕ

61166, Харків, просп. Леніна, 14