Черніговський Дмитро Якович Факультет: Обчислювальної техніки та інформатики Спеціальність: Програмне забезпечення автоматизованих систем Керівник: Зорі Сергій Анатолійович

Біографія

Ефективна програмна візуалізація реальних об'єктів, заданих моделями класу «Хмара точок»

Вступ

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

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

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

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

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

Цілі і завдання, які повинні вирішуватися

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

При цьому повинні бути вирішені наступні завдання:

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

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

Актуальність теми

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

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

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

Передбачувана наукова новизна

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

Заплановані практичні результати

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

Огляд досліджень і розробок по темі

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

1. Leica Cyclone. Програмний комплекс Leica Cyclone - одне з найпоширеніших у світі рішень для обробки даних наземного лазерного сканування. Leica Cyclone містить у собі всі інструменти, необхідні для виконання повного циклу робіт з використанням обладнання Leica HDS, починаючи з управління процесом сканування і закінчуючи оформленням кінцевого результату і передачею його замовнику. Робота в Cyclone можлива як в режимі одного користувача, так і за технологією «Клієнт-Сервер», з використанням плаваючих або вузлових ліцензій. Комплекс Leica Cyclone складається з окремих модулів, що вбудовуються в єдину програмну оболонку. Кожен модуль призначений для вирішення конкретного кола завдань і відповідає певному процесу обробки даних сканування [5].
2. DAVID. Безкоштовне програмне забезпечення, яке дає можливість виконувати тривимірне сканування об'єктів і перетворювати отриманий результат в моделі, які можна імпортувати в 3D-редактори. На жаль, на безкоштовну версію накладаються деякі обмеження порівняно з платної програмою DAVID Pro [4].

Представники локального рівня:

1. Бабков Віктор Светозаровіч, «Реконструкція 3D-моделей реальних об'єктів методом RBF з використанням GPU». У роботі Віктора Светозаровіча досліджуються можливості реконструкції моделей об'єктів, засобами розпаралелювання обчислень на процесорі графічної плати [1].
2. Хромова Олена Миколаївна, «Відтворення поверхні по довільному набору точок. Підзадача побудови площини, найменш віддаленої від сукупності точок ». Відмінністю роботи Олени Миколаївни є використання інших методів обробки хмари точок, програмні інструментальні засоби, які використовуються, і відсутність можливості стерео візуалізації [2].

Постановка завдання

Хмарою точок ми будемо називати сукупність точок у тривимірному просторі, які задають поверхню деякого об'єкта.

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

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

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

1. Побудова поверхні що інтерполює
2. Триангуляція отриманої поверхні
3. Вивід полігональної моделі на екран

При використанні стерео візуалізації додається етап формування стереопари та її подальше перетворення в стерео.

Побудова поверхневої моделі. Метод RBF.

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

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

Завдання тріангуляції. Огляд методів.

Під візуалізацією тривимірних скалярних полів розуміється візуалізація поверхні заданої за допомогою функції від трьох аргументів і фіксованого значення цієї функції - рівня. {(x,y,z)|f(x,y,z)=c}

де f (x, y, z) - це задана функція, а с - заданий рівень. Безліч точок, які задовольняють цій формулі, і є шукана поверхня. Однак зручніше відновлювати не саму поверхню, а поверхню апроксимуючих, шукану за допомогою трикутників. Такий спосіб візуалізації називається тріангуляції.

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

Осередкові методи (cell-based)

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

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

Найбільш відомі осередкова алгоритми: метод Канейра (Caneiro), метод, запропонований Гуезеком (Gueziec), метод Скала (Skala), метод «марширування кубів».

Метод предиктор-коректора (predictor-corrector)

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

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

Мозаїчні методи (pre-tessellation methods & particle-based methods)

Суть таких методів полягає в розбитті шуканої поверхні на частини та подальшої їх тріангуляції. Розбиття на частини в pre-tessellation методи передбачає розбиття поверхні на «примітивні» поверхні - фрагменти сфер і площин. Розбиття на частини в методах з плеяди particle-based - менш «інтелектуально» - шукаються тільки фрагменти площин. При цьому виникає проблема «з'єднання» вже «протріангулірованних» частин. Найчастіше цей процес зводиться до підбору локальних по Делоне трикутників, що з'єднують частини шуканої поверхні.

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

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

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

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

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

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

Швидкість роботи

Помилка апроксимації

Кількість згенерованих трикутників

Якість генеруються трикутників

Проте, розглянуті алгоритми мають одну і ту ж основу. Тому швидкість і помилка апроксимації розрізняються несуттєво. Таким чином, аналіз алгоритмів достатньо провести за наступними критеріями - кількість трикутників, «якість» трикутників.

Огляд методів формування стереозображень

Метод наскрізного погляду

Цей метод дозволяє бачити стереозображення без використання будь-якого обладнання.

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

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

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

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

Метод перехресного погляду

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

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

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

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

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

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

Анагліфові окуляри

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

Растрова стереофотографія

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

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

Затвірні стереоокуляри

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

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

Поляризовані стереоокуляри

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

Зазвичай цей метод застосовується в стереокінотеатрах.

Стереомонітор

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

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

Стереошолом

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

«Псевдостереоскопія»

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

Зразок псевдостерео.

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

Формування стереопари

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

для формування коректної Off-axis стереопари необхідно модифікувати матрицю таким чином

Тут змінні означають:

• eye - означає для якого ока формується зображення (-1 - лівий, 1 - правий)
• sep - поділ екрану, повинна приблизно дорівнювати половині відстані між очима, значення має бути в діапазоні від 0 до zNear/dist
• dist - Z координата площини нульового паралакса (за замовчуванням дорівнює zNear), значення має бути в діапазоні від -zNear/sep до zNear/sep

Висновки

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

Література

1. Бабков В.С. Реконструкція 3D-моделей реальних об’єктів методом RBF з використанням GPU / В.С. Бабков // Наукові праці Донецького національного технічного університету. Серія: “Інформатика, кібернетика та обчислювальна техніка”, випуск 9 (132). – Донецьк: ДонНТУ. 2008. – С. 132-136.
2. Хромова Е.Н., Пауков Д.П., Башков Е.А. «Воссоздание поверхности по произвольному набору точек. Подзадача построения плоскости, наименее удаленной от совокупности точек» ІІ Республіканська наукова конференція студентів , аспірантів та молодих вчених «Комп ’ютерний моніторинг та інформаційні технології» Донецк ДонНТУ 15 мая 2006г.
3. Башков Е.А. Исследование возможностей применения RBF-алгоритма и его модификаций для построения поверхностных компьютерных моделей в медицинской практике / Е.А. Башков, В.С. Бабков // Сборник трудов международной конференции "Моделирование-2008", 14-16 мая 2008 г. – Киев: Институт проблем моделирования в энергетике им. Г.Е. Пухова, т. 1, 2008. - С. 166–171.
4. DAVID-laserscanner [Электронный ресурс] / Сайт DAVID, - http://www.david-laserscanner.com/
5. Leica Geosystems [Электронный ресурс] / Leica Geosystems, - http://www.leica-geosystems.ru/ru/index.htm
6. Горькавый И. Н. Автоматизация обработки данных лазерного сканирования для получения высокоточных трехмерных моделей земного рельефа / ВМиК МГУ. http://2006.edu-it.ru/docs/4/04_09_Gorkaviy.doc
7. Ohtake Y., Belyaev A. G., Proceedings of the International Conference on Shape Modeling & Applications, Page: 74, 2001. http://cis.k.hosei.ac.jp/~F-rep/OhtakeSmi01.pdf
8. Ohtake Y., Belyaev A. G., ACM Symposium on Solid Modeling and Applications, pp. 171 - 178, 2002. http://cis.k.hosei.ac.jp/~F-rep/SM02ob.pdf
9. Durst M., "Letters: Additional Reference to Marching Cubes" Computer Graphics, vol. 22, no. 2, pp. 72-73, 1988.
10. Skala V., Conference on Scientific Computing 2000, pp. 368 - 378. http://www.emis.de/journals/AMUC/_contributed/algo2000/skala.pdf

Примітка

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

---

Біографія

---