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

Аналітичне представлення операції обчислення нормалі запропоновано подати у вигляді графу, що наведений на Рис.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. Виділення окремих елементів опрацювання. а – початкова модель,

б – окремі елементи опрацювання початкової тріангуляції

Потокове опрацювання отриманих блоків запропоновано виконувати наступним чином: