Методи та засоби зменшення обсягів даних тріангуляційного опису об’єктів комп’ютерної томографії (стр. 3 из 5)
Також у розділі обґрунтовано вибір типу локальної модифікації для зменшення обсягів даних та структури даних для представлення об’єктів у пам'яті комп’ютера. Проведено дослідження та порівняння розробленого методу з відомими аналогами за такими параметрами: числова оцінка відхилення (рис.4); візуальна оцінка відхилення; ефективність зменшення обсягів даних при нульовому допустимому відхиленні; час виконання. Як аналоги, використано два методи – метод прорідження тріангуляційних моделей (ПТ) (графік 1) та метод зменшення обсягів даних на основі квадратичної метрики похибок (КМП) (графік 2). На рис.4 видно, що середнє відхилення, що виникає при зменшенні обсягів даних розробленим методом, (графік 3) є суттєво меншим, ніж для методу ПТ, та майже рівним відхиленню для методу КМП.
Наступним кроком виконано зменшення обсягів даних об’єктів до заданої кількості трикутників і виконано візуалізацію початкової (рис.5. а) та вихідних моделей на дисплеї комп’ютера.
Це дало змогу візуально оцінити якість зменшення обсягів даних. При порівнянні отриманих моделей зроблено висновки: модель найгіршої якості отримана методом ПТ (рис.5. б), а між моделями, отриманими методом КМП (рис.5. в) та розробленим методом (рис.5. г), важко знайти візуальні відмінності, щоб їх оцінити.
Рис.5. Візуалізація об’єктів до та після зменшення обсягів даних їх опису
Оскільки метод КМП не забезпечує зменшення обсягів даних у межах заданого відхилення, для оцінки ефективності розробленого методу при нульовому відхиленні, проведено його порівняння із методом ПТ. Середнє значення ефективності для тривимірних об’єктів різної геометричної форми, отримане розробленим методом, становить 79%, що є на 16% вищим від методу ПТ.
Для визначення швидкодії обробки тривимірних об'єктів визначено час роботи кожного із методів при зменшенні обсягів даних об’єктів до однакової кількості трикутників.
Таблиця 1. Час обробки об’єктів
| Метод зменшення даних | Час виконання, сек. |
| Прорідження тріангуляції | 134,332 |
| Квадратична метрика похибок | 326,078 |
| Розроблений метод | 174,093 |
Аналіз отриманих результатів свідчить, що розроблений метод забезпечує вищу ефективність зменшення обсягів даних при нульовому рівні допустимого відхилення та дозволяє генерувати спрощені моделі об’єктів, обсяги даних для представлення яких на 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. Вивести опрацьований блок даних у вихідну пам'ять.