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

6

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

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

УДК 004.932; 004.04

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

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

Автореферат

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

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

Львів-2008

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

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

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

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

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

обробка моделей, обєми даних для представлення яких не поміщаються в основній памяті компютера, що суттєво сповільнює їх обробку;

забезпечення швидкого відображення моделі тривимірного обєкту на дисплеї компютера;

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

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

Звязок роботи з науковими програмами, планами і темами. Представлені в дисертації дослідження виконувалися згідно з планом наукових досліджень, що проводились кафедрою електронних обчислювальних машин Національного університету "Львівська політехніка" в рамках держбюджетної теми ДБ-АВАГ (номер держреєстрації 0104U002284)"Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища" 2004-2006 рр. та Державної програми "Інформаційні та телекомунікаційні технології в освіті і науці" на 2006-2010 роки (номер 0107U009397)"Розробка структури львівського ресурсно-операційного Grid центру та його ресурсів" №1 ІТ506-2007).

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

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

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

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

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

розробити апаратно-орієнтований метод зменшення обсягів даних тріангуляційного опису обєктів, а також для пришвидшення обробки даних розробити метод розбиття вхідних даних на окремі елементи опрацювання;

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

Обєкт дослідження: подання тривимірних обєктів компютерної томографії.

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

Методи дослідження: У роботі використано методи аналітичної геометрії та обчислювальної математики, що дозволило синтезувати алгоритми обчислення геометричних функцій у тривимірному просторі та методи проектування компютерних пристроїв, що дозволило синтезувати структури апаратних прискорювачів на основі розроблених у роботі методів. Для перевірки працездатності отриманих моделей та структур пристроїв, а також висвітлення отриманих результатів використано експериментальні дані і методи математичного та імітаційного моделювання.

Наукова новизна одержаних результатів полягає в наступному:

Запропоновано метод зменшення обсягів даних тріангуляційного опису обєктів компютерної томографії, що, на відміну від відомих, базується на використанні квадрату відстані від вершини до площини та суми квадратів відстаней від вершини до множини інцидентних площин. Це дозволило в 1,2 рази зменшити обсяги даних обєктів порівняно із відомими методами.

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

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

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

Практичне значення отриманих результатів. Використання розробленої моделі зменшення обсягів даних тріангуляційного опису обєктів, відтворених за даними компютерної томографії, в складі математичного, алгоритмічного та програмного забезпечення рентгенівського компютерного томографа дозволяє зменшити обєми даних для представлення тривимірних обєктів на 50-90% залежно від геометричної форми обєктів.

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

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

Використання результатів. Теоретичні і практичні результати дисертаційної роботи використано і впроваджено при розробці системи автоматизованого пошуку дефектів у суцільних середовищах та конструкційних матеріалах за даними рентгенівської компютерної томографії, що виконана на науково-виробничому підприємстві "Інтрон", а також при виконанні держбюджетних тем на кафедрі електронних обчислювальних машин Національного університету "Львівська політехніка";

Практичну цінність одержаних результатів підтверджують акти впровадження, отримані у Національному університеті "Львівська політехніка" та НВП "Інтрон".

Особистий внесок здобувача. Основний зміст роботи, всі теоретичні та практичні результати, висновки і дослідження, які представлено до захисту, одержані автором особисто. Роботи [3, 6, 7, 9, 10] опубліковані самостійно. У публікаціях, написаних у співавторстві, автору належать: розробка загальної стратегії зменшення обсягів даних тріангуляційного опису обєктів [1], розробка та реалізація модуля оптимізації тривимірних моделей обєктів у складі системи пошуку дефектів за даними компютерної томографії [4, 5], розробка методу обчислення відхилення для контролю якості вихідного тріангуляційного опису обєктів [2, 8].

Апробація результатів дисертації. Наукові та практичні результати роботи доповідались та обговорювались на:

І, ІІ Міжнародних конференціях молодих науковців "Компютерні системи та інженерія" (м. Львів, 2006-2007р);

ІІІ International conference "Advanced Computer Systems and Networks: Design and Application" ACSN-2007 (Lviv, 2007);

V Міжнародній науково-практичній конференції "Компютерні системи в автоматизації виробничих процесів" КСАВП-2007 (м. Хмельницький, 2007);

ІІІ Міжнародній науково-технічній конференції "Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування" СПРТП-2007 (м. Вінниця, 2007);

І, ІІ міжвузівських науково-технічних конференціях науково-педагогічних працівників "Проблеми та перспективи розвитку економіки і підприємництва та компютерних технологій в Україні" (м. Львів, 2006-2007р).

Публікації. За результатами виконаних досліджень опубліковано 10 наукових праць, в тому числі 4 статті у фахових наукових виданнях із переліку, затвердженого ВАК України.

Обсяг і структура дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, викладених на 124 сторінках друкованого тексту, списку використаних джерел (106 найменувань). Робота містить 69 рисунків, 9 таблиць та 4 додатки.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

детектування поверхонь - виділення країв обєктів на томограмах;

сегментація та опис поверхонь - виділення обєктів та опис їх поверхонь тріангуляційними сітками;

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

Крім того, первинний опис обєктів є надлишковим, оскільки незалежно від форми обєктів їх поверхні описуються рівномірною сіткою трикутників. Тому доцільним є зменшення (оптимізація) опису поверхонь - зменшення кількості елементів тріангуляції, що описують поверхні обєктів так, як показано на рис.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. Час обробки обєктів

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

ВИСНОВКИ

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

Розроблено метод зменшення обсягів даних тріангуляційного опису обєктів компютерної томографії, що забезпечує збереження форми обєктів у межах заданого відхилення. Розроблений метод забезпечує вищу ефективність зменшення обсягів даних при однаковому рівні заданого відхилення (обсяги даних для представлення спрощених моделей є на 15-20% менші порівняно з методом прорідження тріангуляції), час виконання в 1,9 раза менший порівняно з методом на основі квадратичної метрики похибок.

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

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

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

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

Розроблено базову структуру, принципи функціонування та 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.

АНОТАЦІЇ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - компютерні системи та компоненти. - Національний університет "Львівська політехніка", Львів, 2008.

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

Ключові слова: компютерна томографія, тріангуляційні сітки, виділення обєктів зображень, графи алгоритмів, реконфігуровані апаратні прискорювачі.

Акимишин О.И. Методы и средства уменьшения объемов данных триангуляционного описания объектов компьютерной томографии. - Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. Национальный университет "Львовская политехника", Львов, 2008.

Диссертация посвящена вопросам уменьшения объемов данных для представления объектов компьютерной томографии триангуляционными сетями. Предложенный метод позволяет уменьшение объемов данных и сохранение геометрической формы объектов в пределах заданного отклонения. Разработано графы алгоритмов и структуры устройств для выполнения основных операций уменьшения объемов данных. На основании анализа триангуляционного описания объектов предложено метод разделения триангуляции на отдельные элементы, что дало возможность ускорить обработку данных и на основе предложенного в работе метода разработать базовую структуру аппаратных ускорителей уменьшения объемов данных. Результаты экспериментов с использованием предложенного метода уменьшения объемов данных показали высокую эффективность на реальных изображениях компьютерной томографии.

Ключевые слова: компьютерная томография, триангуляционные сети, выделение объектов изображений, графы алгоритмов, реконфигурируемые аппаратные ускорители.

O.I. Akymyshyn Methods and facilities of data reduction of triangular mesh description of computed tomography objects. - Manuscript.

Thesis for a candidates degree in technical sciences in speciality 05.13.05 - Computer systems and components. Lviv Polytechnic National University, Lviv, 2008.

The thesis is dedicated to task solving of reduction amount of data in computed tomography object representation. Computed tomography provides non destructive, three-dimensional characterization and visualization of features within the interior of solid objects. Typically for visualization and post-processing a computed tomography 3D objects are represented by triangular meshes, which often are too huge to be effectively processed. Moreover the object description by regular triangular mesh is redundant, because simple flat region of object surfaces are described by hundreds of thousands of triangles, when they can be represented by a few triangles without the loss of the object geometrical shape quality. Therefore the data reduction of computed tomography 3D object triangular description before their analysis and processing is a important task.

The review of known data reduction methods of triangular mesh and their comparative analysis is carried out. It has been found out that most of the methods provide the reduction of data up to the users specified number of triangles instead of the users defined deviation, as computed tomography objects must be represented.

The method that provides the amount of data reduction of a computed tomography object representation with a guaranteed error tolerance of the object geometrical shape has been proposed. The software based on the proposed method is developed and its efficiency on real 3D computed tomography objects is investigated. The results of the method have been compared with the state-of-the-art data reduction methods, including the Mesh Decimation method (MD) and method based on Quadric Error Metric (QEM) numerically, visually and in terms of execution times to strengthen the efficiency and quality of the method. The developed method allows 1.2 times greater reduction amount of data than the MD method with a zero deviation of object geometrical shapes, allows to generate high quality approximation of objects and it is 1.9 times faster than the QEM method.

The basic processing operations of data reduction methods, including normal computation, plane coefficients definition and vertex-plane distance computation, have been singled out and their hardware-oriented algorithms have been developed. It allows to define the structures of the computational devices for data reduction of triangular mesh representation based on the proposed methods. Based on the analysis of data processing performance it has been determined that the stream data processing is the most suitable.

The method of triangulation partitioning into separated processing elements is developed. The separated elements are independent blocks of data, when geometrical changes in one block do not require changing in the other. The proposed method is verified on test objects. It allows partitioning the input triangulation into separated blocks of data to their stream, parallel or pipeline processing. The algorithm of stream data processing based on proposed method has been developed.

The basic structures and functioning principles of the reconfigurable hardware accelerators of data reduction of object triangular representation have been developed. The VHDL-model of the accelerators has been designed and their characteristics have been examined.

The results of numerical experiments of the proposed data reduction method of computed tomography object triangle representation have shown the effectiveness of the method. The results were used in SME “Intron” for the development of the data reduction unit of the Non-Destructive Testing Software System for X-Ray 3D Computed Tomography (NDTS System) for flaw detection in solid objects according to computed tomography data. The results allow 50-90% amount of data reduction depending on object geometrical shapes.

Key words: computed tomography, triangular mesh, object detection, graph of algorithm, reconfigurable hardware accelerators.