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

14

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

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

«ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ»

БАБКОВ ВІКТОР СВІТОЗАРОВИЧ

УДК 004.925.83

ЕФЕКТИВНИЙ МЕТОД РЕКОНСТРУКЦІЇ ТРИВИМІРНИХ МОДЕЛЕЙ РЕАЛЬНИХ ОБ'ЄКТІВ ТА ЙОГО РЕАЛІЗАЦІЯ НА ПАРАЛЕЛЬНИХ КОМП'ЮТЕРНИХ СИСТЕМАХ

05.13.05 - комп'ютерні системи та компоненти

Автореферат

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

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

ДОНЕЦЬК - 2009



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

Робота виконана в Державному вищому навчальному закладі „Донецький національний технічний університет” Міністерства освіти і науки України

Науковий керівник:	доктор технічних наук, професор Башков Євген Олександрович ДВНЗ „Донецький національний технічний університет”, проректор з наукової роботи, завідувач кафедри „Прикладна математика і інформатика”.
Офіційні опоненти:	доктор технічних наук, професор Пєтух Анатолій Михайлович Вінницький національний технічний університет, м. Вінниця, завідувач кафедри „Програмне забезпечення”; кандидат технічних наук, доцент Сулема Євгенія Станіславівна Національний технічний університет України „Київський політехнічний інститут”, м. Київ, доцент кафедри „Спеціалізовані комп'ютерні системи”.

Захист відбудеться 18.06.2009 о 14-00 годині на засіданні спеціалізованої вченої ради Д.11.052.03 Державного вищого навчального закладу „Донецький національний технічний університет” за адресою: 83001, м. Донецьк, вул. Артема, 58, уч. корпус 8, ауд. 704.

З дисертацією можна ознайомитися в бібліотеці Донецького національного технічного університету за адресою: 83001, м. Донецьк, вул. Артема, 58, уч. корпус 2.

Автореферат розісланий 14.05.2009.

Вчений секретар Спеціалізованої вченої ради Д.11.052.03 Г.В. Мокрий



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

Для розв'язання поставлених перед дисертантом задач важливу роль відіграли роботи В.В. Савченка, А.А. Паска та Н. Кожекіна, які заклали теоретичний базис для використання радіальних симетричних функцій для отримання ізоповерхневих моделей у тривимірному просторі. Значний внесок у розвиток і вдосконалення методів і засобів побудови тривимірних моделей за проекційними даними внесли Дж. Карра, Г. Турка та Дж. О'Брайна, Б. Мурса.

Математичний апарат для розв'язання задачі тривимірної інтерполяції було запропоновано та розроблено Р. Беатсоном. У роботі автор також спирався на результати Дж. Поудерокса та китайських дослідників В. Кьянга, Ж. Пана та ін.

Також внесок у розробку методів побудови та візуалізації ізоповерхневих моделей внесли роботи, які виконувалися під керівництвом В.М. Гусятина та Н.В. Білоуса (Харківський національний університет радіоелектроніки), С.В. Шевелєва та С.І. Вяткіна (Інститут автоматики та електрометрії, ПВ РАН, Новосибірськ, Росія).

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

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

- не розроблені методи побудови ізоповерхонь за множиною дискретних даних, орієнтовані на реалізацію на паралельних комп'ютерних системах;

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

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

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

Зв'язок роботи з науковими програмами, планами, темами.

Дослідження за темою дисертації проводилися на кафедрі прикладної математики та інформатики Донецького національного технічного університету в рамках виконання науково-дослідницьких робіт з держбюджетних тем, які включені до плану фундаментальних досліджень, затверджених МОН України: Г-13-2000 „Архітектура обчислювальних систем для комп'ютерного синтезу і пошуку зображень у реальному часі” (№ держреєстрації 0100U001049), Д-2-03 „Методи, алгоритми та архітектури реального часу для пошуку, генерації, тривимірної реконструкції й моделювання зображень складних об'єктів” (№ держреєстрації 0103U001322), Д-2-06 «Ефективні алгоритми індексації та виконання запитів в глобальних графічних і відео-базах даних, обробки та генерації зображень» (№ держреєстрації 0106U001265), в яких здобувач приймав участь як виконавець.

Мета та завдання досліджень.

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

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

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

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

- відобразити метод реконструкції на паралельні комп'ютерні системи SIMD і MIMD-архітектур з різними характеристиками;

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

- розв'язати практичні задачі реконструкції ізоповерхневих моделей тривимірних об'єктів (органів людини) на основі проекційних даних (2D і 3D сканування) у медичній практиці.

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

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

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

Наукова новизна отриманих результатів полягає в наступному:

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

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

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

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

Практичне значення отриманих результатів полягає в тому, що на основі отриманих теоретичних положень:

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

розроблено рекомендації щодо реалізації алгоритмів реконструкції ізоповерхневих моделей тривимірних об'єктів на багатопотокових графічних процесорах;

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

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

Результати дисертаційного дослідження використано у комп'ютерній системі для тривимірного моделювання порушень хребта за результатами томографічних досліджень, в науково-дослідницьких роботах Донецького національного технічного університету: „Архітектура обчислювальних систем для комп'ютерного синтезу і пошуку зображень у реальному часі”, „Методи, алгоритми та архітектури реального часу для пошуку, генерації, тривимірної реконструкції й моделювання зображень складних об'єктів”, «Ефективні алгоритми індексації та виконання запитів в глобальних графічних і відео-базах даних, обробки та генерації зображень»; у навчальному процесі при виконанні науково-дослідницьких, дипломних і магістерських робіт, при підготовці лекційного курсу „Комп'ютерний синтез та обробка зображень” на кафедрі прикладної математики та інформатики ДонНТУ.

Особистий внесок здобувача.

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

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

Міжнародна науково-технічна конференція "Інформаційно-комп'ютерні технології 2002", Житомирський інженерно-технологічний інститут (м. Житомир, 9-12 жовтня 2002 р.);

Загальноросійська науково-технічна конференція з міжнародною участю „Комп'ютерні та інформаційні технології у науці, інженерії та керуванні”, Таганрозький радіотехнічний університет (м. Таганрог, Росія, 24-25 травня 2004 р.);

Міжнародна науково-технічна конференція “ІНФОТЕХ-2004”, Севастопольський національний технічний університет (м. Севастополь, 20-25 вересня 2004 р.);

Третя міжнародна науково-технічна конференція молодих вчених та студентів „Інформатика і комп'ютерні технології”, Донецький національний технічний університет (м. Донецьк, 11-13 грудня 2007 р.);

Міжнародна конференція „Моделювання-2008”, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова (м. Київ, 14-16 травня 2008 р.);

IV науково-практична конференція „Донбас-2020: наука і техніка виробництву”, Донецький національний технічний університет (м. Донецьк, 27-28 травня 2008 р.);

IV Міжнародна науково-практична конференція „Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій”, Запорізький національний технічний університет (м. Запоріжжя, 24-26 вересня 2008 р.).

Публікації. Основні результати дисертаційної роботи опубліковані в 12 наукових працях, з них 5 статей у фахових виданнях ВАК України, 7 публікацій у працях міжнародних наукових конференцій та семінарів, 10 наукових праць написані без співавторів.

Структура і обсяг дисертаційної роботи. Дисертація складається із вступу, 4 розділів, висновків, списку використаних джерел з 101 найменування, розташованого на 11 сторінках, і 4 додатків. Повний обсяг дисертації складає 185 сторінок друкарського тексту, з них 133 сторінки основного тексту, містить 101 рисунок (у тому числі 27 - на окремих сторінках) і 26 таблиць.

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

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

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

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

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

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

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

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

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

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

, (1)

де , ,

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

, (2)

де

- деяка функція, яка забезпечує безперервність розв'язання на межах піддоменів;

- множина значень локальних розв'язань у піддоменах нижчого рівня.

, (3)

де

- коефіцієнт впливу локального розв'язання на глобальне;

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

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

(4)

У загальному випадку функції відстані повинні задовольняти наступним умовам:

орган людина проекційний ізоповерхня

	, лежить на межі піддомену	(5)
	, лежить у центрі піддомену
	, лежить у центрі сусіднього під домену	(6)
	, лежить на межі даного піддомену, що найбільше віддалена від сусіднього піддомену

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

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

При використанні квадратичної функції відстані значення відносної похибки при і не перевищує 8%. Визначено комбінації параметрів і , при яких має місце ділення на 0, що унеможливлює визначення функції відстані.

При використанні експоненційної функції відстані значення відносної похибки при і не перевищує 1%. Визначено, що це має місце у випадку, коли і .

При використанні функції відстані типу „інверсний мультиквадрик” значення відносної похибки при і не перевищує 1%. Визначено, що це має місце у двох випадках: коли і або і .

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

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

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

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

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

- координати центру домену;

- покажчик на 8 доменів нижчого рівня (для проміжного домену);

- кількість точок у домені та перелік їх індексів (для домену найнижчого рівня).

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

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

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

на етапі декомпозиції кожний процесорний елемент обробляє окремий центр інтерполяції (паралелізм на рівні точок);

на етапі розв'язання систем лінійних рівнянь кожний процесорний елемент розв'язує свою СЛАР (паралелізм на рівні систем рівнянь);

етап обчислення інтерполянту не розпаралелюється і виконується для однієї шуканої точки.

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

на етапі декомпозиції кожний процесорний елемент обробляє групу центрів інтерполяції (паралелізм на рівні груп точок);

на етапі розв'язання систем лінійних рівнянь кожний процесорний елемент розв'язує свою СЛАР (паралелізм на рівні систем рівнянь);

на етапі обчислення інтерполянту кожний процесорний елемент обробляє точку (паралелізм на рівні точок).

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

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

Дольова частка операцій обміну та операцій процесорного елементу наведено на рис. 8.

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

Залежності для загального часу роботи запропонованого паралельного методу побудови ізоповерхні для трьох типів архітектур (SIMD, MIMD UMA, MIMD NC-NUMA) наведено на рис. 9. Залежності окремо показано для двох діапазонів: і . Таке розбиття на діапазони обумовлене тим, що - це максимально можлива практична кількість процесорних елементів у структурі MIMD систем з шинною організацією, а у даних умовах можна практично вважати нескінченою кількістю процесорних елементів.

Проведений аналіз показав, що:

у діапазоні малих значень (1..256) найменші часові витрати на процедуру побудови ізоповерхні забезпечує реалізація запропонованого методу на архітектурі MIMD NC-NUMA. Виняток складають діапазони P1, N0 і P1, , у яких перевагу (з точки зору часових витрат) має SIMD архітектура;

відмова від використання локальної пам'яті () та перехід до архітектури MIMD UMA обумовлює вузький діапазоні: P256, , в якому MIMD архітектура має перевагу над SIMD;

у діапазоні значень (256..) архітектури MIMD UMA та MIMD NC-NUMA мають практично однакові часові характеристики, причому виграш у часових витратах порівняно з SIMD архітектурою носить теоретичний характер, тому що відповідна кількість процесорних елементів у MIMD архітектурах з шинною організацією на практиці не реалізується.

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

У розділі отримано такі результати:

- запропонований метод реконструкції відображено на паралельні архітектури типу SIMD, MIMD UMA, MIMD NC-NUMA та запропоновано схеми організації обчислювального процесу для вищевказаних архітектур;

- для архітектур SIMD, MIMD UMA, MIMD NC-NUMA отримано теоретичні оцінки часових витрат залежно від обсягу вхідних даних і кількості процесорних елементів;

- для архітектур SIMD, MIMD UMA, MIMD NC-NUMA визначено максимальну кількість процесорних елементів, перевищення якої перестає зменшувати часові витрати на процедуру побудови ізоповерхні;

- визначено дольову частку операцій пересилання та операцій процесорного елементу у часові витрати (54% на 46% - SIMD, 57% на 43% - MIMD UMA та 23% (глоб.), 45% (локал.) на 43% - MIMD NC-NUMA, відповідно);

- проаналізовано реалізацію запропонованого методу на архітектурах SIMD, MIMD UMA, MIMD NC-NUMA. Показано, що SIMD-реалізація запропонованого методу забезпечує прискорення (за критерієм прискорення паралельних алгоритмів) <40,а MIMD-реалізація -<100. При цьому за великих значень ефективність (за критерієм Амдала) для SIMD-реалізації спрямовується до 0.1, а MIMD-реалізації - до 0.5;

- отримано теоретичні оцінки для ступеню паралелізму SIMD і MIMD-реалізацій і визначено, що ступінь паралелізму для MIMD-реалізації теоретично перевищує ступінь паралелізму для SIMD-реалізації у 4R2/(4R+7) разів (- максимальна кількість точок в одному піддомені після декомпозиції).

У четвертому розділі для експериментальної перевірки запропонованого методу обрано технологію CUDA (Compute Unified Design Architecture), що є розширенням мови програмування Сі та дозволяє програмувати паралельні обчислення на мультипроцесорах сучасних відеокарт.

У розділі отримано рекомендації щодо відображення схем обчислювального процесу для SIMD і MIMD реалізації на архітектуру графічного процесору (рис. 10-11) та описано процедуру проведення експерименту з використанням створених програмних модулів, що виконуються на графічному процесорі.

Узагальнено результати експериментів і зроблено такі висновки:

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

визначено, що відносне зменшення часу реконструкції порівняно з ієрархічним методом радіальних симетричних функцій (прототипом, що має кращі часові характеристики серед відомих методів реконструкції) складає 32..83% (тобто в середньому 57% залежно від виду об'єкту);

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

при SIMD-реалізації методу спостерігається стрімке зростання часу роботи алгоритму при N. При N>105 кількість точок не впливає на час реконструкції, незалежно від кількості задіяних процесорних елементів;

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

при MIMD-реалізації час реконструкції для малих значень P (P<40) є більшим порівняно з SIMD-реалізацією, що підтверджує теоретичні висновки;

реалізація MIMD NC-NUMA зменшує час реконструкції порівняно з MIMD UMA приблизно на 30%.

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

Результати обробки показані на рис. 12.

Приклади реконструкції тривимірних моделей приведено на рис. 13.

За результатами аналізу експериментальних результатів зроблено висновок, що практично отримане усереднене прискорення для SIMD реалізації становить 3..15 разів, а MIMD реалізації - 1.5..5 разів. При цьому реалізація MIMD NC-NUMA забезпечує додаткове прискорення відносно MIMD UMA реалізації (в середньому на 30%) за рахунок зменшення часу виконання операцій доступу до пам'яті.

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



ВИСНОВКИ

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

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

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

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

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

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

6. Отримано відображення запропонованого методу реконструкції на паралельні архітектури типу SIMD, MIMD UMA, MIMD NC-NUMA та запропоновано схеми організації обчислювального процесу для вищевказаних архітектур. Отримано теоретичні оцінки для часових витрат залежно від обсягу вхідних даних і кількості процесорних елементів. Також визначено максимальну кількість процесорних елементів, перевищення якої перестає зменшувати часові витрати на процедуру побудови ізоповерхні. Визначено дольову частку операцій пересилання та операцій процесорних елементів у часових витратах (54% на 46% - SIMD, 57% на 43% - MIMD UMA та 23% (глоб.), 45% (локал.) на 43% - MIMD NC-NUMA, відповідно).

7. Проаналізовано характеристики реалізацій методу на архітектурах SIMD і MIMD. Визначено, що SIMD-реалізація методу забезпечує прискорення <40,а MIMD-реалізація -<100. При цьому для великих P ефективність SIMD-реалізації спрямовується до 0.1, а MIMD-реалізації - до 0.5.Отримано теоретичні оцінки для ступеню паралелізму SIMD і MIMD-реалізацій і визначено, що ступінь паралелізму для MIMD-реалізації перевищує ступінь паралелізму для SIMD-реалізації у 4R2/(4R+7) разів (R- максимальна кількість точок в одному піддомені після декомпозиції).

8. Експериментально визначено, що запропонований метод з точки зору часових витрат ефективніший за ієрархічний метод радіальних симетричних функцій в середньому на 57%. Підтверджено, що при малій кількості процесорних елементів (P<40) MIMD-реалізація має гірші часові характеристики порівняно з SIMD. Показано, що на практиці збільшення кількості процесорних елементів в MIMD-архітектурі з топологією „загальна шина” зменшує прискорення через вплив накладних витрат при роботі із загальної пам'яттю. Також визначено, що практичне прискорення паралельної реалізації запропонованого методу лежить у межах теоретичних оцінок і для SIMD-реалізації складає в середньому 3..15 разів. Доведено, що використання архітектури MIMD NC-NUMA замість MIMD UMA зменшує для даного типу графічного процесора та пам'яті час реконструкції в середньому на 30%.



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

1. Бабков В.С. Реконструкція 3D-моделей органів в комп'ютерній томографії при обмеженому об'ємі вхідних даних / В.С. Бабков // Наукові праці Донецького національного технічного університету. Серія: “Проблеми моделювання та автоматизації проектування динамічних систем”, випуск 52. - Донецьк: ДонНТУ. 2002. - С. 100-105.

2. Бабков В.С. Застосування методу „деформованих моделей” для реконструкції органів в КТ за умови обмеженої кількості вхідної інформації / В.С. Бабков // Вісник Житомирського інженерно-технологічного інституту. Спеціальний випуск за матеріалами Міжнародної науково-технічної конференції "Інформаційно-комп'ютерні технології 2002". - Житомир: ЖІТІ. 2002 р. - С. 207-214.

3. Бабков В.С. Застосування сплайнів для подання контурів в методах обробки томографічних зображень / В.С. Бабков // Наукові праці Донецького національного технічного університету. Серія “Інформатика, кібернетика та обчислювальна техніка”, випуск 70. - Донецьк: ДонНТУ. 2003 р. - С. 30-38.

4. Бабков В.С. Співвіднесення щільних 3D-моделей органів в комп'ютерній томографії / В.С. Бабков // Вісник Севастопольського національного технічного університету. Спеціальний випуск за матеріалами Міжнародної науково-технічної конференції “ІНФОТЕХ-2004”. - Севастополь: Вид-во СевНТУ. 2004 р. - С. 87-88.

5. Бабков В.С. Модифицированный алгоритм деформационного сопоставления контуров в компьютерной томографии / В.С. Бабков // Известия Таганрогского радиотехнического университета. Тематический выпуск: материалы Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» №1 (45). - Таганрог: Изд-во ТРТУ. 2005. - С. 82-85.

6. Бабков В.С. Метод співвіднесення контурів томографічних зрізів на основі сплайнового подання / В.С. Бабков // Наукові праці Донецького національного технічного університету. Серія „Інформатика, кібернетика і обчислювальна техніка”, випуск 120. - Донецьк: ДонНТУ. 2007. - С. 14-21.

7. Бабков В.С. Проектирование многофункциональной программной системы для реконструкции трехмерных объектов в медицинской практике / В.С. Бабков, Е.В. Ивашковец // Сборник трудов Третьей международной научно-технической конференции молодых ученых и студентов «Информатика и компьютерные технологии» 11-13 декабря 2007 г. - Донецк: ДонНТУ, Министерства образования и науки, 2007. - С. 285-287.

8. Бабков В.С. Исследование возможностей применения RBF-алгоритма и его модификаций для построения поверхностных компьютерных моделей в медицинской практике / Е.А. Башков, В.С. Бабков // Сборник трудов международной конференции "Моделирование-2008", 14-16 мая 2008 г. - Киев: Институт проблем моделирования в энергетике им. Г.Е. Пухова, т. 1, 2008. - С. 166-171.

9. Бабков В.С. 3D-моделювання об'єктів на основі 2D та 3D-проекційних даних / В.С. Бабков // Матеріали IV науково-практичної конференції „Донбас-2020: наука і техніка - виробництву”, 27-28 травня 2008 р. - Донецьк: ДонНТУ Міністерства освіти і науки, 2008. - С. 383-387.

10. Бабков В.С. Спецпроцессор для формирования описания объектов в составе подсистемы реконструкции 3D-моделей в КТ / В.С. Бабков // Известия ЮФУ. Технические науки. Тематический выпуск: "Компьютерные и информационные технологии в науке, инженерии и управлении" №2. - Таганрог: Изд-во ТТИ ЮФУ, 2008. - С. 120-125.

11. Бабков В.С. Реконструкція 3D-моделей реальних об'єктів методом RBF з використанням GPU / В.С. Бабков // Наукові праці Донецького національного технічного університету. Серія: “ Інформатика, кібернетика і обчислювальна техніка”, випуск 9 (132). - Донецьк: ДонНТУ. 2008. - С. 132-136.

12. Бабков В.С. Модифікація ієрархічного методу RBF для отримання 3D-моделей за результатами лазерного сканування / В.С. Бабков // IV Міжнародна науково-практична конференція „Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій”: тези доповіді, 24-26 вересня, 2008 р. - Запоріжжя, ЗНТУ. - C. 116-117.



АННОТАЦИЯ

Бабков В.С. Эффективный метод реконструкции трехмерных моделей реальных объектов и его реализация на параллельных компьютерных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - ГВУЗ „Донецкий национальный технический университет”, Донецк, 2009.

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

В диссертации предложен метод вычисления изоповерхности в 3D-пространстве с помощью радиальных симметричных функций на основе декомпозиции центров интерполяции на группы и иерархического рекурсивного вычисления интерполянта.

Исследована возможность применения предложенного метода в пространстве 3D и предложены алгоритмы декомпозиции и вычисления интерполянта.

Для предложенного метода определены теоретические оценки временной сложности.

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

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

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

Экспериментально получены характеристики ускорения, степени параллелизма и эффективности параллельной реализации предложенного метода на графическом процессоре Nvidia c использованием технологии CUDA (Compute Unified Design Architecture).

Установлено, что SIMD-реализация метода обеспечивает ускорение <40, а MIMD-реализация - <100. При этом для большого числа процессорных элементов эффективность SIMD-реализации стремится к 0.1, а MIMD-реализации - к 0.5.

Определено, что степень параллелизма для MIMD-реализации превышает степень параллелизма для SIMD-реализации в 4R2/(4R+7) раз (R -максимальное количество точек в одном субдомене после декомпозиции).

Эксперимент показал, что предложенный метод с точки зрения временных затрат эффективнее иерархического метода радиальных симметричных функций в среднем на 57%. Подтверждено, что при малом количестве процессорных элементов (P<40) MIMD-реализация имеет худшие временные характеристики по сравнению с SIMD. Показано, что на практике увеличение количества процессорных элементов в MIMD-архитектуре с топологией „общая шина” уменьшает ускорение из-за влияния накладных расходов при работе с общей памятью. Также определено, что практическое ускорение параллельной реализации предложенного метода лежит в границах теоретических оценок и для SIMD-реализации составляет в среднем 3..15 раз. Доказано, что использование архитектуры MIMD NC-NUMA вместо MIMD UMA уменьшает для данного типа графического процессора и памяти время реконструкции в среднем на 30%.

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

Предложенные в работе методы и архитектуры были использованы в научно-исследовательских госбюджетных темах кафедры прикладной математики и информатики ГВУЗ ДонНТУ: Г-13-2000 „Архитектура вычислительных систем для компьютерного синтеза и поиска изображений в реальном времени”, Д-2-03 „Методы, алгоритмы и архитектуры реального времени для поиска, генерации, трехмерной реконструкции и моделирования изображений сложных объектов”, Д-2-06 «Эффективные алгоритмы индексации и выполнения запросов в глобальных графических и видео-базах данных, обработки и генерации изображений».

Материалы диссертации использовались в учебном процессе при выполнении научно-исследовательских, дипломных и магистерских работ, при подготовке лекционного курса „Компьютерный синтез и обработка изображений” на кафедре прикладной математики и информатики ГВУЗ ДонНТУ.

Ключевые слова: модель трехмерного объекта, изоповерхность, Интерполяция, декомпозиция, системы линейных уравнений, параллельные методы, графический процессор, коэффициенты эффективности и ускорения.



АНОТАЦІЯ

Бабков В.С. Ефективний метод реконструкції тривимірних моделей реальних об'єктів та його реалізація на паралельних комп'ютерних системах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - ДВНЗ „Донецький національний технічний університет”, Донецьк, 2009.

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

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

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



ANNOTATION

Babkov V.S. Effective method for reconstruction of 3D-models of real objects and his implementation on the parallel computer systems. - Manuscript.

Thesis for candidate's degree in technical science by speciality 05.13.05 are the Computing systems and components. - „Donetsk National Technical University”, Donetsk, 2009.

Thesis is devoted to development of methods for reconstruction of 3D-models of the real objects from projections data, which provide the increase of efficiency for computer graphics systems. In thesis the new method for isosurface calculation in 3D is offered. Method use the RBF and based on interpolation centres decomposition and hierarchical recursive interpolant calculation. For the new method the estimations of numerical complication are certain. Influence of distance function type on an error at the calculation of interpolant is explored and it is set that the use inversion multiquadric provides a minimum error. The reflections of the offered method on parallel architectures SIMD and MIMD is proposed. The estimations of numerical complication depending on the volume of information and amount of processor are got. The compare for realization on SIMD and MIMD architectures is executed.

Key words: three-dimensional model, isosurface, interpolation, decomposition, systems of linear equations, parallel methods, graphic processor, coefficients of efficiency and acceleration.

Размещено на Allbest.ru

...