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

де xi, yi, zi, - координати точок в околі, точки vi.

Обчислити відстань від вершини viдо апроксимуючої площини

. (3)

Для перевірки працездатності запропонованого методу розроблено програмне забезпечення зменшення обсягів даних та досліджено його роботу на тестових зображеннях. На рис.3 подано приклад зменшення обсягів даних опису моделі правильного куба (рис.3. а), що містить 56 вершин та 108 трикутників. Модель куба обрано для наочного сприймання одержаних результатів. Використавши запропонований метод, отримано модель куба, що містить 30 вершин та 56 трикутників (рис.3. б).

Рис.3. Зменшення обсягів даних опису моделі правильного куба.

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

на основі рівняння площини Ax+By+Cz+D=0, квадрат відстані від вершини v [xv,yv,zv] до цієї площини визначається як:

dist2(v) =(Axv+Byv+Czv+D) 2; (4)

парі вершин (v1, v2), що утворюють ребро тріангуляційної сітки, поставлено у відповідність множину площин, інцидентних обом вершинам трикутників. Тоді сума квадратів відстаней від вершини v до цієї множини площин дорівнює:

; (5)

відстань від вершини до відповідної їй множини суміжних площин дорівнює нулю:

, (6)

оскільки вершина належить кожній з цих площин. Використавши вирази (5), (6) та підставивши координати вершини v1, отримано:

. (7)

Рівність (7) виконується тоді і тільки тоді, коли інцидентні вершині v1 площини співпадають з площинами, інцидентними вершині v2. В цьому випадку вершина v2 може бути видалена з моделі. Якщо рівність (7) не виконується для вершини v1, то перевіряється її виконання для вершини v2. Якщо рівність (7) не виконується ні для вершини v1, ні для v2, то жодна з вершин v1, v2 не може бути видалена з моделі. Результат роботи методу наведено на рис.3. г. Отримана модель куба містить 8 вершин та 12 трикутників, що є мінімальною кількістю елементів тріангуляції для подання куба та доводить ефективність розробленого методу.

Також у розділі обґрунтовано вибір типу локальної модифікації для зменшення обсягів даних та структури даних для представлення об’єктів у пам'яті комп’ютера. Проведено дослідження та порівняння розробленого методу з відомими аналогами за такими параметрами: числова оцінка відхилення (рис.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)

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