Національна академія наук України Міністерство освіти та науки України

Міжнародний науково-навчальний центр

інформаційних технологій та систем

Рябоконь Дмитро Ігорович

УДК 004.932

Технологія побудови тривимірних моделей

неперервних поверхонь за стереопарами зображень

Спеціальність 05.13.23

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

Автореферат

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

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

Київ – 2005

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

Робота виконана в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та МОН України.

Науковий керівник: доктор фізико-математичних наук, професор Шлезінгер Михайло Іванович, Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України, головний науковий співробітник.

Офіційні опоненти: доктор технічних наук, професор Вінцюк Тарас Климович, Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України, завідувач відділу.

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

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

Захист відбудеться 24 червня 2005 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.171.01 в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та МОН України за адресою 03680, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в бібліотеці Міжнародному науково-навчальному центрі інформаційних технологій та систем: 03680, Київ-187, проспект Академіка Глушкова, 40

Автореферат розіслано 23 травня 2005 р.

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалась в Міжнародному науково-навчальному центрі інформаційних технологій та систем у відділі розпізнавання зображень в рамках завдання НАН України “Дослідження структурних та статистичних моделей зображень і розроблення оптимізаційних методів їх обробки та розпізнавання” (номер державної реєстрації роботи – 0101U002683). Результати дисертаційної роботи використані автором під час виконання науково-дослідної та дослідно-конструкторської роботи “Апаратно-програмний комплекс для просторової реконструкції тривимірних сцен за стереопарою зображень (обличчя, промислові споруди, ландшафти)”, державний реєстраційний номер 0101U007949), а також при створенні апаратно-програмного комплексу “Стереовізор” при виконанні науково-дослідної роботи “Розробити моделі та алгоритми комп’ютерної технології стереозору для портативних мікроелектронних виробів” (0104U007432) в рамках Державної науково-технічної програми “Образний комп’ютер”.

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

Для досягнення мети сформульовано такі задачі:

1.

2.

3.

Методи дослідження. В основу дисертації покладено роботи Гімельфарба Г.Л. з теорії бінокулярного та тринокулярного машинного стереозору, Шлезінгера М.І. та Главача В. з теорії структурного розпізнавання образів, Шлезінгера М.І. та Флаха Б. з теорії вирішення задач розмітки, Ішикави Х., Бойкова Ю., Колмогорова В. та ін. з теорії розв’язання задач оптимізації методами пошуку перерізу на графі, а також інших авторів. При розробці власних алгоритмів обробки зображень використовувались методи проекційної геометрії, математичної статистики, самонавчання та інші.

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

1.

2.

3.

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

4.

5.

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

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

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

Результати дисертаційного дослідження впроваджено в ТОВ “Інтегрейтед Текнікал Віжн Лтд”(акт впровадження від 28.02.05 р.) при виконанні науково-технічної роботи “Програмне забезпечення для ідентифікації особи за зображенням її обличчя” за договором № 91 від 1.08.2003 р. Алгоритми та методика створення тривимірних моделей людських облич за стереопарами зображень дозволяють підвищити точність та надійність роботи алгоритмів ідентифікації особи за зображенням її обличчя завдяки врахуванню положення та орієнтації обличчя людини під час зйомки.

Результати дисертаційного дослідження впроваджено також в діючому макетному зразку – апаратно-програмному комплексі “Відеосек’юріті”. (Державний науково-дослідний центр прикладної інформатики, Київ; акт впровадження від 14.03.05 р.) Комплекс був розроблений автором разом з колективом відділу розпізнавання зображень Міжнародного науково-навчального центру інформаційних технологій та систем в рамках Державної науково-технічної програми “Образний комп’ютер”. Розробки виконувались за замовленням Державного комітету промислової політики України.

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

· П’ята Всеукраїнська конференція з оброблення сигналів та розпізнавання образів УкрОбраз-2000 (листопад 2000 р., Київ).

· Всеукраїнська виставка наукових досягнень, присвячена 10-й річниці Незалежності України (червень 2001р., Київ)

· Міжнародна виставка інформаційних технологій CeBit-2002 (березень 2002 р., Ганновер, Німеччина).

· Міжнародна конференція електронних візуальних мистецтв – “Electronic and Visual Arts” – EVA-2002 (травень 2002 р., Київ).

· Міжнародна конференція IFAC (International Federation of Automatic Control) “Automatic control in aerospace” (“Автоматичне управління у космосі”) ACA-2004 (червень 2004 р., С-Петербург).

· Десята міжнародна конференція Автоматика-2004 (вересень 2004 р., Київ).

· Сьома Всеукраїнська конференція з оброблення сигналів та розпізнавання образів УкрОбраз-2004 (жовтень 2004 р., Київ).

Результати дослідження обговорювались на наукових семінарах в Інституті штучного інтелекту Дрезденського технічного університету (квітень 2002 р., Дрезден, Німеччина), Міжнародного науково-навчального центру інформаційних технологій та систем (1999-2005 роки, Київ), семінарі відділу Космічних інформаційних технологій та систем Iнституту космічних досліджень НАН України (жовтень 2004 р., Київ) та кафедри Моделювання складних систем факультету Кібернетики Київського національного університету ім. Шевченко (березень 2005 р.).

Публікації. За матеріалами дисертації опубліковано 9 наукових статей, в тому числі 4 в фаховому виданні України – журналі “Управляющие системы и машины”. Структура дисертації. Дисертація складається із вступу, п’яти розділів, висновків, переліку посилань, що містить 68 найменувань в алфавітному порядку, та додатків. Загальній обсяг дисертації – 138 сторінок, в тому числі додатки на 10 сторінках. Загальна кількість ілюстрацій 64 рисунки.

Зміст роботи

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

В першому розділі “Задачі дисертаційного дослідження та їх місце в сучасній проблематиці машинного стереобачення”, аналізуються відомі алгоритми побудови моделей тривимірних об’єктів за стереопарами. Відзначаються дослідження Р. Шари з Чеського технічного Університету (м. Прага), в яких задача ототожнення пар пікселів на рядках зображень формулюється як задача пошуку стабільного поєднання пар. Обробка зображень виконується рядок за рядком незалежно, і в деяких пікселях дозволяється відмовитися від пошуку відповідної пари. Експерименти показали, що алгоритм забезпечує прийнятні результати відновлення просторової конфігурації таких сцен, де більшість точок проектується одночасно на обидва знімки. В іншому випадку, коли існує багато точок, що видимі лише на одному із стереознімків, результати роботи незадовільні. Це пояснюється тим, що алгоритм Р. Шари є надто загальним і не робить жодних припущень про структурні особливості відновлюваної сцени. Вважається, що на стереопарі може міститися будь-який об’єкт: чи то одна неперервна поверхня, чи багато поверхонь, що перетинаються. Отже, при стереореконструкції тривимірної сцени слід враховувати інформацію про її можливу конфігурацію так, щоб здійснювати пошук тривимірної моделі серед чітко визначеного класу.

На відміну від підходу Р. Шари, в дослідженнях колективу вчених на чолі з В.І. Рибаком та Г.Л. Гімельфарбом, що виконувались в Міжнародному науково-навчальному центрі інформаційних технологій та систем (Київ), припускалося, що відновлювана модель об’єкта має бути бінокулярно видимою поверхнею. Вченими запропоновано швидкий та економний алгоритм стереореконструкції поверхні за ідеальною парою знімків, який ґрунтується на методі динамічного програмування. Алгоритм має задовільну точність, він відновлює просторову конфігурацію сцени рядок за рядком та складає цілісну модель об’єкта у вигляді неперервних по горизонталі шматочків, що отримані в результаті незалежної обробки пари рядків на лівому та правому зображеннях. В цьому і полягає його недолік, адже він не враховує залежності між конфігурацією сусідніх по вертикалі ділянок тривимірної моделі. Ще одна особливість алгоритму (яка, до речі, притаманна й великій кількості інших алгоритмів) полягає в тому, що ототожнюються лише такі пари точок, які знаходяться в однакових по вертикалі рядках стереозображень. Ця особливість призволить до необхідності мати точно калібровані стереопари зображень.

Узагальнення методів “одновимірної” (рядкової) обробки стереопар на “двовимірний” випадок стало можливим завдяки підходу, що базується на вирішенні (max , +) задач розмітки. М.І. Шлезінгер (Міжнародний науково-навчальний центр, Київ) та Б. Флах (Дрезденський технічний Університет, Німеччина) запропонували алгоритм точного вирішення (max , +) задачі для широкого класу математичних моделей. За його допомогою просторова конфігурація об’єкта відновлюється у вигляді цілісної неперервної поверхні, а не у вигляді набору неперервних ділянок, як це було раніше. Також виявилось, що деякі підкласи (max , +) задач можна звести до відомої задачі про максимальний потік чи мінімальний переріз в мережі. Х. Ішікава та Д. Гейгер (Нью-Йоркський Університет) запропонували метод “двовимірної” обробки стереозображень на основі пошуку мінімального перерізу в мережі, а вчені з Корнелського Університету (США) – Ю. Бойков, О. Векслер, Р. Забих та В. Колмогоров вдосконалили та застосували цей алгоритм для широкого кола прикладних задач розпізнавання. Головною особливістю “двовимірних” алгоритмів, які знаходять за стереопарою зображень найімовірнішу неперервну поверхню, є значні потреби пам’яті та великий час роботи, який набагато більший за час роботи “одновимірних” алгоритмів.

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

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

1.

2.

3.

4.

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

На початку розділу наведено прийняті позначення.

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

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

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

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

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

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

.

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

Рис. 1. Проекція точок тривимірного простору на проекційні площини стереокамер.

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

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

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

.

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

(1)

Задача (1) розв’язується за допомогою методу динамічного програмування. Розмітка елементів зображення відбувається в кожному рядку незалежно. Алгоритм пошуку найкращої розмітки в деякому рядку полягає в послідовному знаходженні найкращої розмітки частини його пікселів. Обчислювальна складність алгоритму складає .

На відміну від алгоритму В.І. Рибака та Г.Л. Гімельфарба (прим. 1 на ст. 2), запропонований алгоритм допускає співставлення пікселів лівого та правого зображення, що знаходяться в різних рядках. Пікселю лівого зображення можна співставити, взагалі кажучи, будь-який піксель правого зображення, а не лише такий, що має вертикальну координату . Результати експериментального порівняння двох алгоритмів наведено на рис. 2-4. Рис. 2 містить стереопару зображень людського обличчя. Вона не є ідеальною, адже існують такі точки обличчя, що проектується в різні рядки пари зображень. На рис. 3 містяться чотири просторові моделі, кожна з яких є результатом алгоритму Рибака та Гімельфарба і отримана за умови, коли праве зображення було зсунуте по вертикалі на певну величину. Як бачимо, кожна з цих моделей містить ділянки, просторова конфігурація яких відновлена невірно. Нарешті, рис. 4 містить тривимірну модель, що є результатом роботи запропонованого алгоритму обробки неідеальних зображень. Як бачимо тут, просторова конфігурація обличчя відновлена майже скрізь вірно.

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

Рис. 2. Стереопара обличчя.

Рис. 3. Результати відомого алгоритму рядкової обробки стереопари.

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

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

.

Позначимо штраф за прийняття рішення на користь розмітки у випадку, коли дійсна, проте невідома розмітка є . Тут – є певний штраф за прийняття рішення щодо мітки в конкретному пікселі . Ризик (математичне очікування штрафу) розмітки визначатиметься величиною . Тут є значення маргінальної вірогідності стану в пікселі . За умови відомої стереопари , розмітка , що має найменший ризик, визначається за правилом . Як бачимо, задача пошуку розмітки з найменшим байесівським ризиком зводиться до обчислення значень апостеріорних маргінальних ймовірностей міток для всіх пікселів : |

(2)

Точний підрахунок значення виразу (2) є так звана (+ , X) задача, яка входить до класу NP-повних задач. Наступний науковий результат, що розкривається в другому розділі дисертації, полягає в розробці алгоритму для наближеного обчислення виразу. Обчислення здійснюється не за допомогою генерування випадкових розміток марківського поля та підрахунку частот реалізацій його станів в кожному пікселі, як це робить більшість відомих алгоритмів, а за допомогою перебору всіх можливих реалізацій випадкового поля, проте не на цілому полі зору, а в його підмножині на смузі розміром , де – горизонтальний розмір поля зору, а – висота смуги, що може приймати значення в інтервалі . На відміну від алгоритмів генерування, умови збіжності та точність обчислень яких досі не досліджені належним чином, запропонований алгоритм характеризується розміром смуги , на якій здійснювались наближені обчислення. Складність розробленого алгоритму для підрахунку наближеного значення (2) для всіх пікселів поля зору складає , а потреби пам’яті . Експерименти засвідчили його значну перевагу перед алгоритмом пошуку найімовірнішої поверхні у випадках, коли стереозображення спотворені випадковим шумом.

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

Рис. 5. Штучна стереопара зображень та просторові моделі:

істина конфігурація поверхні, результат алгоритму пошуку

найімовірнішої тривимірної поверхні та результат байесівського алгоритму.

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

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

.

Необхідно серед множини всіх можливих розміток знайти розмітку з найбільшою ймовірністю: |

(3)

На відміну від задачі (1), теперішня постановка (3) враховує зв’язок не лише між мітками сусідніх по горизонталі пікселів, а й між мітками сусідніх по вертикалі пікселів (рис. 6).

Рис. 6. Граф на якому шукається найімовірніша розмітка та

мережа, де шукається мінімальний переріз.

В лівій частині рис. 6 міститься масив пікселів 3х2. Вони позначені прямокутними клітками. Кожен піксель може знаходитися в одному з трьох станів. Стани позначені чорними точками. Деякі стани сусідніх пікселів поєднані ребром. Кожному стану в кожному пікселі приписано число . Необхідно в кожній клітині вибрати один єдиний стан так, щоб добуток чисел, які приписані обраним станам, був максимальним, а стани сусідніх пікселів поєднані ребром.

В дисертаційній роботі показано: пошук найімовірнішої розмітки , що є розв’язком задачі (3) рівносильний пошуку в мережі перерізу з мінімальною пропускною спроможністю. Тут – вершини, – ребра, а – значення, що приписані ребрам. Множина вершин складається із вершини-джерела , вершини-приймача , а також тривимірного масиву вершин . Розв’язок задачі (3) визначається як .

Множина ребер та їх вага будується за наступним правилом (рис. 2).

1. Ребра, що прямують з джерела до вершин , мають вагу .

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

3. Ребра, що прямують з вершин до приймача , мають вагу .

4. Дві вершини і сусідніх пікселів і з’єднані ребром з вагою .

Тут символ означає величину, що обчислюється за формулою .

Новизна запропонованого підходу полягає у використанні відомих алгоритмів пошуку мінімального перерізу (Min-Cut) в мережі (алгоритм Едмондса-Карпа чи проштовхування передпотоку), за допомогою яких розв’язок задачі (3) потребує пам’ять обсягом , а не , як це передбачається в роботах вчених з Корнелського Університету (с. 7). Оцінка часу роботи оптимізаційних алгоритмів на мережі складає .

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

. | (4)

. |

(5)

Задача (4)–(5) вирішується за допомогою алгоритму самонавчання11 Schlesinger M.I., Hlavac V. Ten Lectures on Statistical and Structural Pattern Recognition. – Kluwer Academic Publishers, Dordrecht, 2002., який оцінює параметри марківського випадкового поля. Результатом його роботи є неперервна поверхня, дальність до точок якої є реалізацією випадкового марківського поля, а також значення параметрів цього поля, що максимізують вірогідність вихідної вибірки – результату роботи попереднього алгоритму стереореконструкції. На відміну від відомих “двовимірних” алгоритмів обробки стереозображень, алгоритм пост-обробки відзначається високою швидкодією. Його застосування є ефективним у випадках, коли результати попередньої обробки стереозображень в цілому задовільні, і їх необхідно виправити лише в невеликій кількості точок.

Порівняння результатів відновлення просторової конфігурації поверхні “одновимірним” та “двовимірними” алгоритмами наведено на рис. 7. У верхній частині рис. 7 міститься стереопара земної поверхні, а в нижній частині – так звані карти дальності. Карта дальності являє собою зображення, на якому більш близькі до спостерігача точки забарвлені в світлий колір, а більш віддалені від спостерігача точки забарвлені в темний колір. Як бачимо, поверхня, що є результатом алгоритму “одновимірної” обробки стереопари, містить ділянки, просторова конфігурація яких відновлена невірно. Результати ж алгоритмів “двовимірної” обробки – Min-Cut алгоритму пошуку найімовірнішої неперервної поверхні та алгоритму пост-обробки, що застосовано до результату “одновимірного” алгоритму – значно кращі. Вони отримані із врахуванням зв’язку між конфігурацією ділянок поверхні, що є сусідами

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

Рис. 7. Стереопара земної поверхні та результат її обробки “одновимірним” алгоритмом, “двовимірним” Min-Cut алгоритмом і алгоритмом пост-обробки .

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

В п’ятому розділі “Результати експериментальних випробувань” сформульовано кількісні та якісні критерії для оцінки роботи алгоритмів відновлення просторової конфігурації об’єктів, а саме

·

·

·

·

·

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

Висновки

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

1.

2.

3.

4.

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

5.

список опублікованих праць

1.

2.

3.

4.

5.

6.

7.