Анотація до роботи:

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

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

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

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

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

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

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

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

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

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

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

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

8. Експериментально визначено, що запропонований метод з точки зору часових витрат ефективніший за ієрархічний метод радіальних симетричних функцій в середньому на 57%. Підтверджено, що при малій кількості процесорних елементів () 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.

У роботах, які опубліковані в співавторстві, дисертантові належать: [7] – метод обчислення ізоповерхні тривимірного об’єкту за результатами 2D-сканування; [8] – дослідження обчислювальних і просторових характеристик методів побудови ізоповерхонь на основі використання радіальних симетричних функцій. Роботи [1-6, 9-12] написані без співавторів.