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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Методи та засоби зменшення обсягів даних тріангуляційного опису об’єктів комп’ютерної томограф

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

6

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Акимишин Орест Ігорович

УДК 004.932; 004.04

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

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

Автореферат

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

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

Львів-2008

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

Робота виконана в Національному університеті “Львівська політехніка” Міністерства освіти і науки України

Захист відбудеться “ 11 ” липня 2008 р. о 16 годині на засіданні спеціалізованої вченої ради Д 35.052.08 у Національному університеті “Львівська політехніка” (79013, Львів-13, вул. С. Бандери,

12) З дисертацією можна ознайомитись у бібліотеці Національного університету “Львівська політехніка” (79013, Львів, вул. Професорська,

1) Автореферат розісланий “ 10 ” червня 2008 р.

Аналіз отриманих результатів свідчить, що розроблений метод забезпечує вищу ефективність зменшення обсягів даних при нульовому рівні допустимого відхилення та дозволяє генерувати спрощені моделі об'єктів, обсяги даних для представлення яких на 15-20% менші порівняно із методом ПТ. Час, що затрачається на зменшення обсягів даних розробленим методом, в 1,9 рази меншим порівняно із методом, що базується на квадратичній метриці похибок та в 1,3 більшим порівняно із методом прорідження тріангуляції.

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

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

Для обчислення нормалі до площини, яка задана трьома точками v1, v2 та v3, необхідно знайти два вектори а і b:

(8)

, (9)

та обчислити їх векторний добуток:

. (10)

Аналітичне представлення операції обчислення нормалі запропоновано подати у вигляді графу, що наведений на Рис.6.

Відстань від вершини до площини можна записати як:

, (11)

де - ненормована нормаль, dist - відстань від точки до площини.

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

. (12)

Рис.6. Граф виконання алгоритму обчислення нормалі до площини

Щоб уникнути операції добування кореня квадратного з виразу , праву та ліву частини (12) піднесено до квадрату:

(13)

Згідно з (13) для обчислення квадрату відстані від вершини до площини необхідним є визначення 10 коефіцієнтів, граф алгоритму якого наведено на рис.7.

Обчислення квадрату відстані від вершини до площини виконується на основі (13), тобто підстановки координат заданої вершини в рівняння площини. Граф розробленого алгоритму зображено на рис.8. Вхідними даними є координати вершини (x,y,z) та коефіцієнти {a2, ab, ac, ad, b2, bc, bd, c2, cd, d2}. Для виконання алгоритму використовуються операції множення, додавання та зсув на один розряд вліво, які позначені '*', '+' та '<<' відповідно. Результатом є квадрат відстані від заданої вершини до площини, помножений на значення (a2+b2+c2).

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

Рис.8. Граф алгоритму обчислення квадрату відстані від вершини до площини

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

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

Рис.9. Структура пристроїв зменшення обсягів даних для реалізації на НВІС

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

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

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

1. Помітити всі вершини вхідної послідовності, як невикористані.

2. Для кожного ребра тріангуляції виконувати:

2.1 Перевірити вершини, які утворюють ребро. Якщо вони помічені, як невикористані, то перевірити вершини в їх околі.

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-коди та функціональні діаграми розроблених вузлів наведено в додатках до дисертації.

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.