етектування поверхонь - виділення країв об'єктів на томограмах; сегментація та опис поверхонь - виділення об'єктів та опис їх поверхонь тріангуляційними сітками; На цьому етапі реальні моделі об'єктів містять велику кількість даних у їх описі, внаслідок чого виникають проблеми, пов'язані з обробкою моделей, обсяги даних для представлення яких перевищують обсяг основної пам'яті комп'ютера, що суттєво сповільнює їх обробку та забезпечення швидкого відображення об'єктів на дисплеї комп'ютера. Крім того, первинний опис об'єктів є надлишковим, оскільки незалежно від форми об'єктів їх поверхні описуються рівномірною сіткою трикутників. Тому доцільним є зменшення (оптимізація) опису поверхонь - зменшення кількості елементів тріангуляції, що описують поверхні об'єктів так, як показано на рис.1. Також у розділі проведено аналіз відомих методів зменшення обсягів даних опису тривимірних об'єктів, на основі якого встановлено: процедура зменшення обсягів даних виконується або в межах наперед заданої кількості трикутників, або в межах заданого відхилення; залежно від галузі застосування, критичним є час, що затрачається на виконання зменшення обсягів даних, чи збереження максимально можливої якості вихідної моделі; в деяких випадках важливу роль відіграють атрибути моделі (колір, текстура), коли в інших випадках ними нехтують. Більшість відомих методів орієнтовані на обробку зображень для комп'ютерної графіки, забезпечують зменшення обсягів даних у межах наперед заданої кількості трикутників та не гарантують повного збереження форми тривимірних об'єктів. Це є їхніми основними недоліками при застосуванні в автоматизованому відтворенні об'єктів за даним комп'ютерної томографії. Тому є необхідність розробки методів зменшення обсягів даних, що забезпечують збереження форми об'єктів в межах заданого відхилення. У другому розділі "Розробка методу зменшення обсягів даних тріангуляційного опису об'єктів комп'ютерної томографії" на основі особливостей подання об'єктів комп'ютерної томографії запропоновано метод зменшення обсягів даних, що забезпечує збереження форми об'єктів у межах заданого допустимого відхилення. Задачу зменшення обсягів даних тріангуляційного опису об'єктів запропоновано подати таким чином. Маючи початкову модель об'єкту М, задану тріангуляційною сіткою Т0, що містить N точок, отримати апроксимацію моделі М', тріангуляційною сіткою Тn, таку що: вона має відхилення d від М не більше заданого значення d(M, M') ? ; тріангуляційна сітка Тn має мінімальну кількість вузлів (точок) n, n = min n(Ti). Відхиленням у тривимірному просторі для вершини тріангуляції vi, яка є кандидатом на видалення з моделі, прийнято відстань від цієї вершини до площини Pavg - апроксимуючої площини для точок, що лежать в околі vi (рис.2). При оцінці можливості видалення вершини з тріангуляції виконується перевірка рівності d ? , де d - відхилення, що виникає внаслідок видалення vi, та дорівнює відстані від точки до площини, - задане значення допустимого відхилення. Якщо ця рівність виконується, то вершина видаляється разом із суміжними їй трикутниками. Для реалізації описаного методу запропоновано виконати таку послідовність кроків: Обчислити одиничну нормаль апроксимуючої площини, (1) де - зважені нормалі до площин, інцидентних вершині vi трикутників, - абсолютна величина вектора . Обчислити координати точки апроксимуючої площини, (2) де 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) та обчислити їх векторний добуток: . (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 Перевірити вершини, які утворюють ребро. Якщо вони помічені, як невикористані, то перевірити вершини в їх околі.
Страницы: 1, 2, 3
|
