|
p align="left">2.1.1 Якщо всі вершини в околі ребра є помічені, як невикористані, то утворити окремий елемент опрацювання тріангуляції та помітити вказані вершини, як використані. 2.1.2 Вершини, помічені, як використані, пропускаються. 3. Вивести список окремих елементів опрацювання. Моделювання методу виконано на основі його програмної реалізації мовою С++. На рис.12 зображено результати виділення окремих елементів опрацювання на тестовому зображенні. Рис.12. Виділення окремих елементів опрацювання. а - початкова модель, б - окремі елементи опрацювання початкової тріангуляції Потокове опрацювання отриманих блоків запропоновано виконувати наступним чином: Крок 1. Вичитати блок даних та розмістити його у вхідній пам'яті; Крок 2. Обчислити відхилення, що виникає внаслідок виконання локальної модифікації над текучим блоком даних; Крок 3. Порівняти обчислене відхилення із заданою величиною допустимого відхилення; Крок 4. Якщо обчислене відхилення менше або дорівнює величині заданого відхилення, то виконати локальну модифікацію над текучим блоком даних; Крок 5. Вивести опрацьований блок даних у вихідну пам'ять. Базову структуру апаратних прискорювачів зменшення обсягів даних, що забезпечує потокову обробку даних, з можливістю розділення кроків алгоритму конвеєрними регістрами наведено на рис.13. Рис.13. Базова структура апаратних прискорювачів зменшення обсягів даних Також у розділі розроблено структури вузлів апаратних прискорювачів зменшення обсягів даних, зокрема вузла обчислення відхилення (ОВ), блоків вхідної і вихідної пам'яті та вузла виконання локальних модифікацій (ЛМ). Задачами вузла ОВ є обчислення відхилення, яке виникне внаслідок виконання локальної модифікації, порівняння його із значенням заданого відхилення та формування ознак про можливість виконання ЛМ над біжучим фрагментом тріангуляції. Основними елементами вузла ОВ (рис.14) є обчислення нормалі до площини, обчислення коефіцієнтів для знаходження квадрату відстані від вершини до площини та обчислення відстані від вершини до площини. При такій реалізації вузол ОВ має 6 входів та 2 виходи. На входи вузла подаються координати вершин, що задають суміжні ребру, над яким виконується локальна модифікація, трикутники, координати вершин, що утворюють це ребро та задане значення допустимого відхилення. На виході формуються ознаки, виконання локальної модифікації над опрацьованим блоком даних. Вузол ОВ є конвеєрним, оскільки потік даних розбитий регістрами на 5 ярусів. Частота роботи вузла ОВ визначається, як: f=1/Tmax, (16) де Tmax - максимальна затримка спрацювання внутрішніх елементів вузла ОВ. Аналіз розроблених графів алгоритмів виконання базових операцій свідчить, що максимальну затримку обробки даних має вузол обчислення квадрату відстані від вершини до площини. На основі (16) частота роботи вузла ОВ буде визначатися часом обчислення квадрату відстані від вершини до площини. Вимогами до пам'яті є забезпечення швидкого надходження даних на всі вхідні порти ВОВ. Тому доцільно використати багатопортову пам'ять з можливістю її постійного завантаження вхідними даними. Огляд відомих типів пам'яті дозволив взяти за основу багатопортову сортувальну пам'ять та на її основі розробити структури, що є ефективними для розв'язання поставленої задачі. Інтерфейс та діаграми функціонування розробленої пам'яті наведено на рис.15. Вона має множини вхідних та вихідних портів, входи для задання із блоком даних номеру вихідного порту, по якому слід здійснити видачу цього блоку даних та номер даних у вихідному масиві. На діаграмі виділено послідовне потактове завантаження блоків даних та їх одночасну видачу по трьох вихідних портах. Рис.15. Інтерфейс та результати моделювання роботи вхідної пам'яті Блоком даних, над яким виконується локальна модифікація, є ребро та суміжні до нього трикутники. Залежно від відхилення, що виникає внаслідок виконання ЛМ, можливими є три варіанти виконання ЛМ, що графічно зображені на рис.16, зокрема виконання колапсу ребра (е1, е2) у вершину е1 (рис.16. а); виконання колапсу ребра (е1, е2) у вершину е2 (рис.16. в) та залишення початкового блоку даних без змін, якщо відхилення, що виникає внаслідок виконання ЛМ, перевищує задане значення (рис.16. б). Найпростішим є випадок, зображений на рис.16. б. Для його реалізації достатньо отримати весь фрагмент даних із входу та вивести його у тій самій послідовності. Для реалізації випадків рис.16. а та рис.16. б необхідно виконати такі дії: на основі ознак, що генеруються вузлом обчислення відхилення, визначити вершину, що буде видалена з моделі, та замінити її в описі усіх суміжних з нею трикутників на протилежну. Трикутники, що є спільними для обох вершин, видалити з моделі. Розроблені внутрішні вузли та пристрої зменшення обсягів даних тріангуляційного опису об'єктів комп'ютерної томографії реалізовано шляхом їх опису на мові VHDL, проведено їх поведінкове моделювання та досліджено характеристики. VHDL-коди та функціональні діаграми розроблених вузлів наведено в додатках до дисертації. ВИСНОВКИПроведено огляд методів зменшення обсягів даних опису об'єктів тріангуляційними сітками, виділено їхні особливості, через які вони є неефективними для застосування в галузі неруйнівного контролю за даними комп'ютерної томографії. Обґрунтовано потреби розробки нових методів та вдосконалення існуючих шляхом збільшення ефективності їх роботи. Розроблено метод зменшення обсягів даних тріангуляційного опису об'єктів комп'ютерної томографії, що забезпечує збереження форми об'єктів у межах заданого відхилення. Розроблений метод забезпечує вищу ефективність зменшення обсягів даних при однаковому рівні заданого відхилення (обсяги даних для представлення спрощених моделей є на 15-20% менші порівняно з методом прорідження тріангуляції), час виконання в 1,9 раза менший порівняно з методом на основі квадратичної метрики похибок. Розроблене програмне забезпечення, що базується на запропонованих у роботі методах, апробовано на реальних даних та використовується на практиці, як складова системи неруйнівного контролю на основі рентгенівської комп'ютерної томографії. Встановлено, що доцільною є апаратна реалізація розробленого методу, оскільки процедура зменшення обсягів даних тріангуляційного опису об'єктів, відтворених за даними комп'ютерної томографії високої роздільної здатності з використанням універсальних комп'ютерів, виконується за неприйнятний час. Вдосконалено метод розбиття тріангуляційних сіток на окремі елементи опрацювання, що дає можливість прискорення обробки даних шляхом їх конвеєрної чи паралельної обробки. Виконано програмну реалізацію розробленого методу та перевірено його працездатність на тестових даних. Розроблено апаратно-орієнтовані алгоритми виконання основних операцій зменшення обсягів даних, зокрема обчислення нормалі до площини, обчислення коефіцієнтів для запису рівняння площини і обчислення відстані від вершини до площини в тривимірному просторі та відповідні їм структури спеціалізованих пристроїв. Розроблено базову структуру, принципи функціонування та VHDL-модель реконфігурованого апаратного прискорювача зменшення обсягів даних тріангуляційного опису об'єктів, засновану на розроблених методах, а також проведено її функціональне моделювання. Розроблена структура дає можливість синтезу комп'ютерних пристроїв для зменшення обсягів даних, використовуючи засоби сучасних технологій. СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ1. Мельник А.О., Акимишин О.І. Прорідження тріангуляційних сіток тривимірних об'єктів комп'ютерної томографії // Вісник Національного університету "Львівська політехніка". - 2006. - № 573. - С.131-137. 2. Акимишин О.І., Мороз І.В. Методика обчислення відхилення між тріангуляційними сітками для виконання контролю спрощення // Збірник наукових праць ІМПЕ НАНУ. - № 39. - Київ, 2007. - С.103-109. 3. Акимишин О.І. Алгоритми виконання базових операцій спрощення тріангуляції // Вісник Хмельницького національного університету. - Хмельницький: ХНУ, 2007. - №2, Т.2. - С.9-12. 4. А. Мельник, В. Ємець, В. Мархивка, І. Мороз., О. Акимишин. Система автоматизованого пошуку дефектів в суцільних середовищах та конструкційних матеріалах за воксельними даними комп'ютерної томографії // Науково-соціальний часопис "Технічні вісті". - Львів, 2007. - С.46-48. 5. А. Melnyk, V. Emets, V. Markhyvka, I. Moroz, O. Akymyshyn. Flaw detection according to computed tomography volume data // Proceedings of the 3-rd International conference Advanced computer systems and networks. ACSN-2007. - Lviv, 2007 - P.170-171. 6. Акимишин О.І. Обробка зображень за даними комп'ютерної томографії // Матеріали 1-ї Міжнародної конференції молодих науковців CSE-2006. - Львів: Видавництво Національного університету "Львівська політехніка", 2006. - С.44-45. 7. Акимишин О.І. Оптимізація тріангуляційного опису тривимірних моделей реальних об'єктів із заданою точністю // Збірник матеріалів міжвузівської науково-технічної конференції науково-педагогічних працівників. - Львів: Ліга-Прес, 2006 - С.184-185. 8. Акимишин О.І. Виділення незалежних елементів опрацювання тріангуляційних сіток в тривимірному просторі // Матеріали ІІІ Міжнародної науково-технічної конференції "Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування" СПРТП-2007. - Вінниця, 2007. - С.117-118. 9. Акимишин О.І., Мархивка В.С. Контроль допустимого відхилення для задач спрощення тріангуляції в 3-d просторі. // Збірник матеріалів ІІ міжвузівської науково-технічної конференції науково-педагогічних працівників. - Львів: Ліга-Прес, 2007 - С. 206-207. 10. Акимишин О.І. Структури пристроїв спрощення тривимірних моделей об'єктів // Матеріали 2-ї Міжнародної конференції молодих науковців CSE-2007. - Львів: Видавництво Національного університету "Львівська політехніка", 2007. - С.74-75. АНОТАЦІЇАкимишин О.І. Методи та засоби зменшення обсягів даних тріангуляційного опису об'єктів комп'ютерної томографії. - Рукопис. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. - Національний університет "Львівська політехніка", Львів, 2008. Дисертація присвячена питанням зменшення обсягів даних при поданні об'єктів комп'ютерної томографії тріангуляційними сітками. Запропонований метод забезпечує зменшення обсягів даних та збереження геометричної форми об'єктів у межах заданого відхилення. Розроблено графи алгоритмів та структури пристроїв для виконання основних операцій зменшення обсягів даних. На підставі аналізу тріангуляційного опису об'єктів запропоновано метод розбиття тріангуляції на окремі елементи, що дозволило пришвидшити обробку даних та на основі запропонованого в роботі методу розробити базову структуру апаратних прискорювачів зменшення обсягів даних. Результати експериментів із використанням запропонованого методу зменшення даних показали високу ефективність на реальних зображеннях комп'ютерної томографії. Ключові слова: комп'ютерна томографія, тріангуляційні сітки, виділення об'єктів зображень, графи алгоритмів, реконфігуровані апаратні прискорювачі. Акимишин О.И. Методы и средства уменьшения объемов данных триангуляционного описания объектов компьютерной томографии. - Рукопись. Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. Национальный университет "Львовская политехника", Львов, 2008. Диссертация посвящена вопросам уменьшения объемов данных для представления объектов компьютерной томографии триангуляционными сетями. Предложенный метод позволяет уменьшение объемов данных и сохранение геометрической формы объектов в пределах заданного отклонения. Разработано графы алгоритмов и структуры устройств для выполнения основных операций уменьшения объемов данных. На основании анализа триангуляционного описания объектов предложено метод разделения триангуляции на отдельные элементы, что дало возможность ускорить обработку данных и на основе предложенного в работе метода разработать базовую структуру аппаратных ускорителей уменьшения объемов данных. Результаты экспериментов с использованием предложенного метода уменьшения объемов данных показали высокую эффективность на реальных изображениях компьютерной томографии. Ключевые слова: компьютерная томография, триангуляционные сети, выделение объектов изображений, графы алгоритмов, реконфигурируемые аппаратные ускорители. O.I. Akymyshyn Methods and facilities of data reduction of triangular mesh description of computed tomography objects. - Manuscript. Thesis for a candidate's degree in technical sciences in speciality 05.13.05 - Computer systems and components. Lviv Polytechnic National University, Lviv, 2008. The thesis is dedicated to task solving of reduction amount of data in computed tomography object representation. Computed tomography provides non destructive, three-dimensional characterization and visualization of features within the interior of solid objects. Typically for visualization and post-processing a computed tomography 3D objects are represented by triangular meshes, which often are too huge to be effectively processed. Moreover the object description by regular triangular mesh is redundant, because simple flat region of object surfaces are described by hundreds of thousands of triangles, when they can be represented by a few triangles without the loss of the object geometrical shape quality. Therefore the data reduction of computed tomography 3D object triangular description before their analysis and processing is a important task. The review of known data reduction methods of triangular mesh and their comparative analysis is carried out. It has been found out that most of the methods provide the reduction of data up to the user's specified number of triangles instead of the user's defined deviation, as computed tomography objects must be represented. The method that provides the amount of data reduction of a computed tomography object representation with a guaranteed error tolerance of the object geometrical shape has been proposed. The software based on the proposed method is developed and its efficiency on real 3D computed tomography objects is investigated. The results of the method have been compared with the state-of-the-art data reduction methods, including the Mesh Decimation method (MD) and method based on Quadric Error Metric (QEM) numerically, visually and in terms of execution times to strengthen the efficiency and quality of the method. The developed method allows 1.2 times greater reduction amount of data than the MD method with a zero deviation of object geometrical shapes, allows to generate high quality approximation of objects and it is 1.9 times faster than the QEM method. The basic processing operations of data reduction methods, including normal computation, plane coefficients definition and vertex-plane distance computation, have been singled out and their hardware-oriented algorithms have been developed. It allows to define the structures of the computational devices for data reduction of triangular mesh representation based on the proposed methods. Based on the analysis of data processing performance it has been determined that the stream data processing is the most suitable. The method of triangulation partitioning into separated processing elements is developed. The separated elements are independent blocks of data, when geometrical changes in one block do not require changing in the other. The proposed method is verified on test objects. It allows partitioning the input triangulation into separated blocks of data to their stream, parallel or pipeline processing. The algorithm of stream data processing based on proposed method has been developed. The basic structures and functioning principles of the reconfigurable hardware accelerators of data reduction of object triangular representation have been developed. The VHDL-model of the accelerators has been designed and their characteristics have been examined. The results of numerical experiments of the proposed data reduction method of computed tomography object triangle representation have shown the effectiveness of the method. The results were used in SME “Intron” for the development of the data reduction unit of the Non-Destructive Testing Software System for X-Ray 3D Computed Tomography (NDTS System) for flaw detection in solid objects according to computed tomography data. The results allow 50-90% amount of data reduction depending on object geometrical shapes. Key words: computed tomography, triangular mesh, object detection, graph of algorithm, reconfigurable hardware accelerators.
Страницы: 1, 2, 3
|
