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

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

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

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

УДК 519.67 + 681.5

АВТОРЕФЕРАТ

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

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

01.05.02 - математичне моделювання

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

Смелякова Анастасія Сергіївна

Харків - 2008

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

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

Науковий керівник: кандидат технічних наук, професор Лєсна Наталя Совєтівна, Харківський національний університет радіоелектроніки, професор кафедри програмного забезпечення ЕОМ, проректор з науково-педагогічної роботи.

Офіційні опоненти:

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

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

Захист відбудеться « 17 » лютого 2009 р. о 14-00 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

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

Автореферат розісланий « 14 » січня 2009 р.

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

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась із 2003 р. у Харківському національному університеті радіоелектроніки згідно з планом НДР університету в рамках теми № ДР0103U001571 “Розробка інформаційної технології мета контекстної інтеграції гетерогенних інформаційно-освітніх ресурсів в інформаційно-освітніх середовищах”, НДР № 200-1 “Агентно-онтологічні технології створення інформаційно-освітнього середовища” і НДР № 200-3 “Методи та технології побудови інтегрованих електронних бібліотек з урахуванням критеріїв якості джерел інформації”, які входять до міжвузівської програми НДР № 200 (№ ДР0106U003152) “Методи та технології створення інформаційно-освітнього середовища з метою інтеграції у загальноєвропейський простір вищої освіти” координаційного плану МОН України. У цих темах автором як виконавцем розроблені онтологічні моделі розв'язання задач апроксимації для інформаційно-освітнього середовища для дистанційного вивчення дисциплін “Чисельні методи в інформатиці” та “Інтелектуальний аналіз даних”.

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

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

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

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

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

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

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

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

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

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

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

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

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

Практичне значення одержаних результатів. Запропоновані в роботі моделі, методи та алгоритми апроксимації об'єктів нерегулярного вигляду у не однозв'язних областях дозволяють розширити якісні можливості СТЗ в діапазоні від систем відображення наземної (або повітряної) обстановки до наукоємких систем аналізу біологічних об'єктів у іридодіагностиці, гістології та інших галузях. Їх широка застосовність ґрунтується на використанні стандартних моделей даних - векторних моделей контурів, прийнятих в ГІС, та еліпсів.

Розроблені моделі, методи і алгоритми оптимізації полігонального наближення впроваджені: у Східному регіональному управлінні Державної прикордонної служби України - при розробці підсистеми автоматизації контролю обстановки задля оптимізації розташування стаціонарних і мобільних пунктів спостереження за прикордонною смугою і прикордонною зоною; в Об'єднаному Науково-дослідному інституті Збройних Сил України - при розробці алгоритмів масштабування інформації щодо зон бойової відповідальності частин Повітряних сил Збройних Сил України з використанням цифрових карт місцевості для мінімізації складності опису зон при обмеженні на точність і локальні особливості границь; при підготовці курсів «Інтелектуальний аналіз даних» і «Чисельні методи» на кафедрі програмного забезпечення ЕОМ Харківського національного університету радіоелектроніки.

Особистий внесок здобувача. Усі результати, представлені в роботі, отримані автором самостійно. У роботах, написаних зі співавторами, здобувачу належать: у [1] - модель та постановка задачі апроксимації границь не опуклих областей при різних критеріях, метод полігональної апроксимації, онтологічна система фільтрів; у [2] - гомотопічна модель ліній у не однозв'язній області; у [3] - постановка основної задачі та її декомпозиція на систему базових задач, метод знаходження вершин апроксиманта, полярна модель зіркової області та метод апроксимації її границі; у [5] - метод формування границі зображення при масштабуванні, який засновано на використанні ключових точок (полюсів) для підвищення точності апроксимації; у [6] - постановка загальної задачі контурної апроксимації для задач моніторингу та зведення її до базових задач еліптичного та полігонального наближення; у [7] - модель не однозв'язної області для оптимізації трас у геоінформаційних системах (ГІС), використання оптимізуючих деформацій для отримання екстремалей, які гомотопні до вихідного наближення; у [9] - XML-модель для зберігання даних у корпоративній системі ГІС для оптимізації зберігання та передачі даних про контури; у [12] - модель оцінки контрастності для аналізу точності апроксимації границь не опуклих об'єктів; у [15] - метод мінімізації складності полігонального апроксиманта при різних критеріях точності для відображення інформації на картографічному фоні.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на міжнародних та регіональній наукових конференціях, які мають прямий стосунок до теми роботи: 3-тя Міжнародна конференція “Проблемы информатики и моделирования - 2003” (Харків, 2003); 9-та Міжнародна наукова конференція “Теория и техника передачи, приема и обработки информации” (Харків-Туапсе, 2003); 7-й - 9-й Міжнародний молодіжний форум “Радиоэлектроника и молодежь в ХХІ веке” (Харків, 2003, 2004, 2005); 7-ма і 8-ма Міжнародні науково-практичні конференції “Современные информационные и электронные технологии” (Одеса, 2006, 2007); International Conference EWDTW 06 (Sochi, 2006); Третя наукова конференція Харківського університету повітряних сил (Харків, 2007); Міжнародна наукова конференція “Современные проблемы математики и ее приложения в естественных науках и информационных технологиях” (Харків, 2007).

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

Структура і обсяг дисертації. Дисертація складається із вступу, п'яти розділів, висновків, списку використаних джерел із 123 найменувань (14 стор.), двох додатків (21 стор.) та має обсяг 160 сторінок. Основний текст роботи викладений на 125 сторінках, що містять 22 рисунка (9 стор.).

Основний зміст роботи

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

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

Топологічно вичерпною моделлю зв'язної множини на площині є диск із дірками

= (1)

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

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

Знайти

(2)

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

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

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

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

(3)

(4)

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

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

Оскільки, на відміну від функціональної апроксимації, в цьому випадку

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

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

Узагальнення цього методу на випадок не однозв'язних областей і незамкнутих ламаних надано у розділі 3.

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

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

(5)

~ (6)

(7)

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

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

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

Рис. 1. Гомотопічні властивості апроксиманта

За цих умов задача (2) може бути сформульована таким чином:

(8)

Якщо відрізок АВ лежить в області виду (1), то з теореми Гаусса-Бонне отримуємо, що його внутрішні точки не містять не опуклих (з боку області ) вершин границі цієї області. На базі цього встановлено, що відрізок АВ задовольняє обмеженням і відносно ламаної з кінцями А і В тоді і лише тоді, коли ні одна з опуклих вершин множини опуклих вершин V границі області не належить внутрішності многокутника . Ця властивість використовується для побудови оператора , який набуває значення 1, якщо обмеження і для ламаної з кінцями А, В і відрізку АВ виконані, і 0 - в іншому випадку.

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

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

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

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

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

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

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

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

У четвертому розділі побудовано модель і метод розв'язання задачі (2) на класі еліпсів F , де потрібно мінімізувати похибку апроксимації

= (9)

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

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

З урахуванням близькості розташування точок , для обчислення відхилень розроблено метод, де початкова оцінка для точки M(s, t) на еліпсі, найближчої до точки , із трудомісткістю 18 (оп) шукається за аналогічною точкою для попередньої вершини із розглядом проекції вектора на дотичну в і диференціала довжини дуги еліпса. Це надає можливість одразу отримати оцінку для точки M з похибкою, на порядок меншою за . Ця оцінка може уточнюватись за ітераційною схемою із трудомісткістю одного кроку 10 (оп). У типовому випадку трудомісткість складає від до ( + 2 + ), тобто від 18 до 30 (оп), що лише в 3 - 5 рази перевищує витрати = 6 (оп) на обчислення відстані .

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

Оскільки границя радужки описується кількістю пікселів N в обсязі від 2000 до 4000, трудомісткість розрахунку оцінок відхилень не перевищить, у середньому, величину порядку (оп). На процесорі, який забезпечує виконання порядку оп/c, за 1 секунду, це дозволить розрахувати (9) для 20000 варіантів параметрів еліпсів.

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

Незалежно від оцінку центру отримуємо по осям еліптичних об'єктів на радужці (лакун) з використанням отриманої в роботі необхідної та достатньої умови їх радіальної орієнтації , де - кут оси лакуни у вихідній системі координат, а - полярний кут центру еліпса відносно центру лакуни. Для цього запропоновано метод лакунарного оцінювання центру , що полягає в розрахунку середнього для точок перетину осей лакун з подальшим вилученням із розгляду лакун, осі яких відносно поточного середнього не задовольняють умові радіальної орієнтації, і переліченням середнього для лакун, що лишились. Отримана система лакун , q>1, задовольняє необхідній і достатній умові радіальної орієнтації відносно точки , яку й беремо за лакунарну оцінку центру радужки. Сталість і збіжність методу витікають із допустимості малих варіацій їх кутів нахилу, вилучення із розгляду екстремально орієнтованих лакун і використання середнього, що дає статистично сталу оцінку центру . За інтервальну оцінку центру вибираємо опуклу оболонку точок перетину осей лакун із .

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

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

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

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

(10)

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

+ , (11)

Отримана кільцева область з радіусами r < R), відображається на еталон - кільце з радіусами ,; <. Для розв'язання цієї задачі гомотетичного розтягування використаємо оператор концентричної нормалізації : , що від куту вже не залежить

(12)

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

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

У додатку Б розміщено акти впровадження результатів роботи.

Висновки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Лесная Н.С. Аппроксимация границ изображений на основе онтологической структуризации системы фильтров / Н. С. Лесная, А. С. Смелякова // Проблемы бионики. - 2003. - Вип. 59. - C. 3-7.

2. Белоус Н. В. Модель и метод решения задачи оптимизации соединений по топологическому критерию / Н. В. Белоус, А. С. Смелякова // Системи обробки інформації. - 2003. - Вип. 1. - С. 218-225.

3. Лесная Н. С. Полигональная аппроксимация границ невыпуклых областей / Н. С. Лесная, А. С. Смелякова // Радиоэлектроника и информатика. - 2005. - №3. - C. 73-82.

4. Смелякова А.С. Эллиптическая аппроксимация с повышенной точностью идентификации параметров / А. С. Смелякова // Системи обробки інформації. - 2007. - Вип. 8 (66). - С. 146-151.

5. Рубан И. В. Кратномасштабная сегментация изображений / И. В. Рубан, К. С. Смеляков, А. С. Смелякова // Системи обробки інформації. - 2008. - Вип. 5 (72). - С. 107-110.

6. Рубан И. В. Контурная аппроксимация областей нерегулярного вида в задачах мониторинга чрезвычайных ситуаций / И. В. Рубан, А. С. Смелякова // Системи управління, навігації та зв'язку. - 2008. - Вип. 4(8). - С. 73-78.

7. Белоус Н. В. Минимизация индекса линейной связности для геоинформационных систем принятия решения / Н. В. Белоус, А. С. Смелякова // Теория и техника передачи, приема и обработки информации: материалы 9-й международной научной конференции, 7-10 окт. 2003 г.: тезисы докл. - Харьков-Туапсе, 2003. - С. 305-306.

8. Смелякова А.С. Распознавание доминирующих на площади цветных изображений для ГИС реального времени в системе цветов HLS/ А. С. Смелякова // Проблемы информатики и моделирования: тезисы доклада 3-ей международной конференции, 27-29 ноября 2003 г.: тезисы докл. - Х.: ХПИ, 2003. - С. 24.

9. Сакало Т.С. Использование языка разметки документов XML при создании обучающего ресурса / Т. С. Сакало, А. А. Дейнеко, А. С. Смелякова // Радиоэлектроника и молодежь в ХХІ веке: материалы 7-го международного молодежного форума, 22-24 апреля 2003 г.: тезисы докл. -Х.: ХНУРЭ, 2003. - С. 396.

10. Смелякова А. С. Аппроксимация границ изображений на основе онтологической структуризации системы фильтров / А. С. Смелякова // Радиоэлектроника и молодежь в ХХІ веке: материалы 8-го международного молодежного форума, 13-15 апреля 2004 г.: тезисы докл. - Х.: ХНУРЭ, 2004. - С. 81.

11. Смелякова А. С. Основные задачи идентификации изображений нерегулярного вида / А. С. Смелякова // Радиоэлектроника и молодежь в ХХІ веке: материалы 9-го международного молодежного форума, 16-19 апреля 2005 г. : тезисы докл. - Х.: ХНУРЭ, 2005. - С. 361.

12. Ruban I. V. Low Contrast Images Edge Detector / I. V. Ruban, K. S. Smelyakov, A. S. Smelyakova, A. I. Tymochko // Proceedings of International Conference EWDTW 06, 15-19 September 2006. - Sohci : Kharkov National University of Radioelectronics, 2006. - P. 390-396.

13. Смелякова А. С. Параметрическая идентификация осей радужки / А. С. Смелякова // Современные информационные и электронные технологии: материалы 7-й международной научно-практической конференции, 22-26 мая 2006 г. : тезисы докл. - Одесса, 2006. - C. 63.

14. Смелякова А.С. Контурная аппроксимация невыпуклых областей / А. С. Смелякова // Современные проблемы математики и ее приложения в естественных науках и информационных технологиях: международная научная конференция, 23-25 марта 2007 г. : тезисы докл. - Х.: ХНУ им. В.Н. Каразина, 2007. - С. 126 -128.

15. Смелякова А.С. Задачи контурной аппроксимации при отображении информации в воздушной обстановке / А. С. Смелякова, К. А. Спорышев, А. В. Северинов // Третя наукова конференція Харківського університету повітряних сил імені Івана Кожедуба, 28-29 марта 2007 г. : тезисы докл. - Харків, 2007. - С. 74.

16. Смелякова А.С. Метод нормализации эллиптических изображений / А. С. Смелякова // Современные информационные системы. Проблемы и тенденции развития: 2-я международная научная конференция, 3-6 октября 2007 г. :тезисы докл. - Харьков-Туапсе, 2007. - С. 241-242.

Анотація

Смелякова А.С. Моделі і методи апроксимації границь об'єктів нерегулярного вигляду в системах технічного зору. - Рукопис.

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

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

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

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

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

Аннотация

Смелякова А.С. Модели и методы аппроксимации границ объектов нерегулярного вида в системах технического зрения. - Рукопись.

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

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

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

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

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

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

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

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

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

...