Винокуров Олексій Сергійович 

ДонНТУ | Портал магистрів ДонНТУ

RUS | UKR | ENG

• Біографія

Реферат по темі випускної роботи

Актуальність теми дослідження

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

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

Мета работи

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

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

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

Підходи до решення

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

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

В основі деформаційних моделей лежить завдання співвідношення контурів. Вона відома в англомовній літературі як "matching". Ця задача розпадається на два напрямки: розмітка (labeling) - співвідношення контуру, отриманого з зрізу, з контуром, взятим з моделі; реєстрація (registration) - співвідношення контурів, отриманих з двох різних зрізів. Рішення вищенаведених завдань зазвичай виконується шляхом побудови структурованого опису контурів і наступного "еластичного" співвідношення описів. Під структуризацією опису розуміється пошук в контурі характерних точок, елементарних кривих і інших елементів, які будуть порівнюватися між двома контурами. "Еластичне" співвідношення будується на основі методу "деформаційних моделей" (deformable models), відомого також під назвою "геометричні деформовані контури". Двовимірний варіант цього методу отримав назву "змійка" (snake). Сутність цього методу полягає в тому, що контур або його елемент відчуває ітераційний деформацію до тих пір, поки не досягне максимально можливого відповідності з іншим відповідним контуром або елементом. Зміна поверхні (деформація) відбувається виходячи з того, що шуканий контур зазнає зміни під впливом двох енергій: внутрішньої і зовнішньої. На кожному кроці алгоритму відшукується контур, для якого присутній баланс енергій, тобто мінімальна деформація. Уточнення відбувається до тих пір, поки не буде досягнуто критерій відповідності шуканого і еталонний контуру.

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

Інтерполяцією називають визначення значення функції для проміжних значень аргументу. Можна припустити, що графік зміни функції на одному кроці досить добре апроксимуються хорда, що з'єднує дві сусідні точки. На практиці ця умова виконується далеко не завжди. Результат буде більш точним, якщо через задані точки провести криву, як можна більш плавну (рис. 2.3) без зламів. Тоді значення функції y (x) для значення x =? можна буде просто рахувати з графіка. Звичайно, такий спосіб інтерполювання спирається скоріше на інтуїцію, ніж на сувору математику, але, тим не менше, це краще, ніж лінійна інтерполяція. Особливо гарний результат буде одержано у разі застосування функціональних шкал, коли крива залежності y від x спрямлена.

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

Алгоритм порівняння шляхом побудови деформаційних моделей виконується досить довго: для кожної точки розпізнається хмари розраховується енергія, з якою в неї буде деформована кожна точка еталонного хмари. Початкове хмара становлять n точок, а еталонне - m. Якщо припустити що n приблизно дорівнює m, то складність алгоритму можна оцінити, як O (n2). Крім того, побудова деформаційної моделі - ітераційний процес, що вимагає деякого числа кроків - k. Однак, k на порядок менше n, тому на тимчасовій складності не відіб'ється. Необхідно також врахувати трудомісткість процесу вирішення рівняння Ейлера, який так само потребують відчутне машинний час.

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

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

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

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

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

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

Досягнуті результати та подальші перспектіви

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

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

Список використаної літератури

1. Скороспелов, В. А. Сплайны в инженерной геометрии. –М.: Машиностроение 1985. – 156с.
2. Неймарк Ю.И., Баталова З.С., Васин Ю.Г., Брейдо М.Д. Распознавание образов и медицинская диагностика. М.: Наука, 1972.
3. Terzopoulos, D. 1986b). Regularization of inverse visual problems involving discontinuities. IEEE Transon Pattern Analysis and Machine Intelligence 8(4):413–424.
4. Fischler, M. and Elschlager, R. (1973). The representation and matching of pictorial structures. IEEE Transon Computers 22(1):67–92.
5. Zienkiewicz, O.C.and Taylor, R.L.(1989). The Finite Element Method. NewYork, NY:McGraw–Hill.
6. Gourdon, A.(1995). Simplication ofirregular surface meshes in3Dmedical images. InAyache(1995b). 413–419.
7. Hill,A.,Thornham,A.andTaylor,C.J.(1993). Model-based interpretation of3Dmedicalimages. InProc.4th British Machine Vision Conf. (BMVC93), Surrey, UK,September, 1993, 339–348. BMVAPress.
8. Essa, I., Sclaroff, S. and Pentland, A.P. (1993). Physically-based modeling for graphics and vision. In Martin, R.,ed., Directions in Geometric Computing. Information Geometers, U.K.
9. Young, A.A., Axel, L., Dougherty, L., Bogen, D.K. and Parenteau, C.S. (1993). Validation of tagging with MR imaging to estimate material deformation. Radiology 188:101–108.
10. Берилло, А. NVIDIA CUDA — неграфические вычисления на графических процессорах http://www.ixbt.com/video3/cuda-1.shtml