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

Задача реконструкції реалістичних моделей реальних тривимірних обєктів виникає у багатьох випадках, зокрема, тоді, коли інформація про обєкт надана у вигляді дискретної множини проекційних даних. Відновлення обєкту в одній з відомих форм подання (полігональне, функціональне та ін.) - задача, розвязанню якої присвячено багато робіт. Значна обчислювальна складність методів і засобів для побудови ізоповерхонь за множиною проекційних даних обумовлює часові витрати на реалізацію, що обмежує їх використання у системах реального часу, особливо при формуванні зображень динамічних обєктів. Дослідження за темою дисертації проводилися на кафедрі прикладної математики та інформатики Донецького національного технічного університету в рамках виконання науково-дослідницьких робіт з держбюджетних тем, які включені до плану фундаментальних досліджень, затверджених МОН України: Г-13-2000 „Архітектура обчислювальних систем для компютерного синтезу і пошуку зображень у реальному часі” (№ держреєстрації 0100U001049), Д-2-03 „Методи, алгоритми та архітектури реального часу для пошуку, генерації, тривимірної реконструкції й моделювання зображень складних обєктів” (№ держреєстрації 0103U001322), Д-2-06 «Ефективні алгоритми індексації та виконання запитів в глобальних графічних і відео-базах даних, обробки та генерації зображень» (№ держреєстрації 0106U001265), в яких здобувач приймав участь як виконавець. Результати дисертаційного дослідження використано у компютерній системі для тривимірного моделювання порушень хребта за результатами томографічних досліджень, в науково-дослідницьких роботах Донецького національного технічного університету: „Архітектура обчислювальних систем для компютерного синтезу і пошуку зображень у реальному часі”, „Методи, алгоритми та архітектури реального часу для пошуку, генерації, тривимірної реконструкції й моделювання зображень складних обєктів”, «Ефективні алгоритми індексації та виконання запитів в глобальних графічних і відео-базах даних, обробки та генерації зображень»; у навчальному процесі при виконанні науково-дослідницьких, дипломних і магістерських робіт, при підготовці лекційного курсу „Компютерний синтез та обробка зображень” на кафедрі прикладної математики та інформатики ДОННТУ.У вступі проаналізовано сучасний стан питання, обґрунтовано актуальність теми, окреслено її джерельну базу, сформульовано мету, основні задачі досліджень, визначено наукову новизну та практичне значення основних результатів, наведено відомості про їхню апробацію та реалізацію. Проведено аналіз відомих методів опису ізоповерхонь на основі проекційних даних і показано, що ці методи фактично розвязують задачу інтерполяції ізоповерхні у тривимірному просторі. У другому розділі показано, що зменшення часових витрат на різних етапах побудови тривимірної моделі можливе за рахунок розпаралелювання методів і алгоритмів. Здійснено розрахунок абсолютної та відносної похибок, які мають місце при використанні тієї чи іншої функції, і в результаті зроблено такі висновки ( - центр інтерполяції поточного домену, - центр інтерполяції сусіднього домену, - сторона домену, - відстань між центрами інтерполяції, - деяка точка простору). Також запропоновано реалізацію побудови ізоповерхні на архітектурі MIMD, особливість якої полягає в тому, що: на етапі декомпозиції кожний процесорний елемент обробляє групу центрів інтерполяції (паралелізм на рівні груп точок);Запропоновано паралельний ієрархічний метод реконструкції, який відрізняється від відомих незалежним обчисленням частин глобального інтерполянту, що дозволяє зменшити часові витрати на побудову моделі тривимірного обєкту. Подальшого розвитку отримав ієрархічний метод розрахунку поверхні двовимірного обєкту за множиною проекційних точок, який відрізняється від відомого принципом декомпозиції простору на частини, що дозволяє використовувати метод у тривимірному просторі. Досліджено вплив виду функції відстані на похибку при розрахунку глобального інтерполянта запропонованим методом і встановлено, що використання інверсного мультиквадрика у якості функції відстані забезпечує мінімальну відносну похибку, яка у найгіршому випадку не перевищує 0.98%. При цьому для великих P ефективність SIMD-реалізації спрямовується до 0.1, а MIMD-реалізації - до 0.5.Отримано теоретичні оцінки для ступеню паралелізму SIMD і MIMD-реалізацій і визначено, що ступінь паралелізму для MIMD-реалізації перевищує ступінь паралелізму для SIMD-реалізації у 4R2/(4R 7) разів (R-максимальна кількість точок в одному піддомені після декомпозиції). Експериментально визначено, що запропонований метод з точки зору часових витрат ефективніший за ієрархічний метод радіальних симетричних функцій в середньому на 57%.

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

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

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.