Розробка і математичне моделювання методів тривимірної томографічної реконструкції

Размещено на http://www.allbest.ru/

Національний технічний університет України

“Київський політехнічний інститут”

УДК 620.179.15:004.942

АВТОРЕФЕРАТ

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

РОЗРОБКА І МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ МЕТОДІВ ТРИВИМІРНОЇ ТОМОГРАФІЧНОЇ РЕКОНСТРУКЦІЇ

01.05.02 - Математичне моделювання та обчислювальні методи

ЦИБУЛЬСЬКА ЄВГЕНІЯ ОЛЕКСАНДРІВНА

Київ - 2010

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

Робота виконана у Відділі спеціалізованих засобів моделювання Інституту проблем реєстрації інформації Національної академії наук України.

Науковий керівник Заслужений діяч науки і техніки України, Лауреат Державної премії СРСР, Лауреат Державної премії України, доктор технічних наук, професор Синьков Михайло Вікторович, ІПРІ НАН України, завідуючий відділом спеціалізованих засобів моделювання.

Офіційні опонентиДоктор технічних наук, старший науковий співробітник Нестеренко Борис Борисович, Інститут математики НАН України, заступник директора.

Кандидат технічних наук, старший науковий співробітник Чемерис Олександр Анатолійович, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, старший науковий співробітник.

Захист дисертації відбудеться „19” квітня 2010 р. о 14:30 годині на засіданні спеціалізованої вченої ради Д 26.002.02 у Національному технічному університеті України “Київський політехнічний інститут” за адресою: 03056, м.Київ, просп. Перемоги, 37, корп. 18, ауд. 306.

З дисертацією можна ознайомитись в бібліотеці НТУУ “КПІ” (03056, м.Київ, просп. Перемоги, 37).

Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати на адресу: 03056, м.Київ, просп. Перемоги, 37, вченому секретарю Національного технічного університету України “Київський політехнічний інститут”.

Автореферат розісланий „_17” _березня___ 2010 р.

Вчений секретар спеціалізованої

вченої ради Д 26.002.02,

кандидат технічних наукМ.М.Орлова

проекційний реконструкція скануючий згортка

ЗАГАЛЬНА характеристика роботи

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

Великий внесок в розвиток комп'ютерної томографії зробили українські вчені. В 1949 р. у Київському науково-дослідному рентгенрадіологічному інституті М.С.Овощніковим був створений томофлюорограф, який дозволяв отримувати ізольовані тіньові зображення внутрішніх органів та окремих їх частин на рентгенівській плівці. В 1956-1957 рр. в Київському політехнічному інституті професор С.І.Тетельбаум, професор Б.І.Коренблюм, А.А.Тютін та інші створили макет одного з перших томографів. У 1989-1991 рр. в ІПРІ НАН України у відділі спеціалізованих засобів моделювання під керівництвом професора М.В.Синькова було розроблено і передано до Росії для серійного виробництва рентгенівський комп'ютерний томограф 3-го покоління “СТ-Київ” для дослідження всього тіла людини.

Теоретичні та практичні роботи з розвитку комп'ютерної томографії виконуються в Німеччині, Франції, Швеції, США, Росії, Японії та інших країнах. Дослідженню і розробці математичного апарату, що використовується в комп'ютерній томографії, присвячено наукові праці таких видатних вчених: Г.Хермена, І.М.Гельфанда, М.І.Граєва, Ф.Натерера, С.І.Тетельбаума, А.Н.Тихонова, В.Я.Арсеніна, А.Кормака, М.В.Синькова, А.І.Закидальского, Б.Сміта, П.Грангеата, Л.Фельдкампа, П.-Е.Даніельсона, О.Кацевича та інших.

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

Зв'язок з науковими програмами, планами, темами. Дисертаційні дослідження пов'язано з відповідним планом науково-дослідних робіт, які проводились в Інституті проблем реєстрації інформації НАН України:

· тема “Пучок” - “Дослідження і розробка методів підвищення продуктивності при об'ємній реконструкції зображень для складної геометрії сканування” (реєстраційний номер 0101U002972), 2001-2003 рр.;

· тема „Крижина” - “Розвиток теорії живучості комп'ютерних систем і методологічних основ розробки захищених інформаційних технологій для систем підтримки прийняття рішень, в тому числі з використанням гіперкомплексних чисел” (реєстраційний номер 0102U0033589), 2002-2006 рр.;

· тема “Куб-2” - “Розвиток методів представлення та обробки багатовимірних даних для вирішення задач захисту інформації, цифрової фільтрації та реконструкції томографічних зображень” (реєстраційний номер 0107U002395), 2007-2009 рр.

Мета і завдання дослідження.

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

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

Предметом дослідження є методи, алгоритми та програмні засоби реконструкції в томографії “великих” об'єктів.

Для досягнення мети в ході дисертаційної роботи було поставлено та вирішено такі задачі:

· розробити методи отримання проекційних даних повного охоплення “великих” об'єктів;

· розробити алгоритми тривимірної реконструкції для дослідження “великих” об'єктів;

· дослідити характеристики алгоритмів реконструкції при неповному охопленні об'єкта скануючою системою;

· провести аналіз методів обчислення згортки з різними формами представлення даних;

· створити метод обчислення одновимірної згортки з використанням гіперкомплексних числових систем (ГЧС);

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

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

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

1. Запропоновано метод отримання проекційних даних повного охоплення “великих” об'єктів за допомогою часткових сканувань горизонтальних секцій при обертанні об'єкта навколо декількох центрів. Показано, що такий підхід дозволяє здійснювати реконструкцію “великих” об'єктів за прийнятний час.

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

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

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

5. Запропоновано метод обчислення одновимірної згортки з переходом до двовимірного перетворення Фур'є та використанням гіперкомплексних чисел, що дозволило скоротити кількість обчислень за рахунок зменшення довжин оброблюваних послідовностей. Показано, що використання бікомплексної ГЧС також дозволяє зменшити кількість обчислень завдяки її простій таблиці множення.

Практичне значення одержаних результатів полягає у забезпеченні можливості тривимірної реконструкції нетрадиційних “великих” об'єктів і досягненні потрібної просторової та щільнісної роздільної здатності при підвищенні продуктивності обчислень. При цьому:

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

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

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

4. Розроблено програмний комплекс моделювання тривимірної томографічної реконструкції “великих” об'єктів. Проведені за його допомогою експериментальні дослідження на математичних фантомах показали, що розроблені алгоритми, які використовують перехід від конусних проекцій до паралельних та обчислення згортки за допомогою ГЧС, забезпечують високопродуктивну тривимірну реконструкцію з заданою просторовою і щільнісною роздільною здатністю.

Особистий внесок здобувача.

Усі наукові результати дисертації отримані самостійно. У роботах, що написані в співавторстві, автору належить значний внесок в ідеологію питань, що вирішуються, та при цьому: [2] - дослідження на ряді експериментів показників якості реконструкції симетричних об'єктів; [3] - аналіз сучасних методів і засобів рендерінгу поверхні в тривимірній томографії; [4] - дослідження на ряді експериментів характеристик алгоритмів реконструкції з повним охопленням об'єкту скануючою системою; [5] - дослідження похибок реконструкції при половинному охопленні “великих” об'єктів; [6] - дослідження обчислювальної складності перетворення даних конусних проекцій у паралельні віяльні шари; [7] - розробка алгоритмічно-програмного модуля швидкого обчислення згортки з використанням швидкого перетворення Фур'є (ШПФ) з проріджуванням за частотою; [8] - дослідження особливостей обчислення згортки в алгоритмах реконструкції; [9] - розробка програмного модуля перетворення даних конусних проекцій у проекційні дані паралельних віяльних шарів; [10] - аналіз сучасного стану комп'ютерної томографії; [11] - спосіб переходу від дійсних послідовностей до гіперкомплексних при обчисленні згортки; [12] - розробка програмного комплексу моделювання тривимірної томографічної реконструкції; [13] - дослідження особливостей використання томографії в задачах контролю та безпеки; [15] - спосіб переходу від дійсних послідовностей до гіперкомплексних при обчисленні перетворення Фур'є.

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

· IV-й науково-практичній конференції “Інформаційні технології та безпека” (Партеніт, червень 2004 р.);

· ХІ-й Міжнародній науково-технічній конференції “Системний аналіз та інформаційні технології” (Київ, НТУУ “КПІ”, ІПСА, травень 2009);

· Українському математичному конгресі (Київ, серпень 2009);

· семінарах відділу спеціалізованих засобів моделювання Інституту проблем реєстрації інформації НАН України.

Публікації. Основні результати роботи викладено у 15-ти наукових роботах, з них у 12-ти статтях у фахових журналах і у доповідях 3-х конференцій.

Структура і обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, 2 додатків. Обсяг основної частини роботи складає 138 сторінок, загальний обсяг - 150 сторінок, робота містить 26 таблиць, 45 рисунків і список використаної літератури зі 104 найменувань.

Основний зміст

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

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

Розглянуто етапи розвитку томографії від одержання пошарових рентгенівських знімків на початку ХХ століття до тривимірної реконструкції в наш час. Приведено схеми томографів різних поколінь.

Наведено основні визначення та класифікацію методів реконструкції. Нехай - функція, що визначає щільність об'єкта (рис. 1). Система “джерело випромінювання-детектор” обертається навколо об'єкта дослідження. Рентгенівський промінь інтенсивністю , проходячи через объект по прямій L, змінює інтенсивність до , причому.

Значення - це проекція функції, яка одержана при просвічуванні об'єкта з поворотом системи “джерело випромінювання-детектор” під кутом.

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

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

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

Аналітичні методи базуються на точному математичному розв'язку рівнянь відновлення зображень, в більшості з них використовується апарат перетворення Радона та перетворення Фур'є. Ці методи, в свою чергу, поділяються на точні та наближені.

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

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

обчислити ДПФ послідовностей і - послідовності і

отримані послідовності і почленно перемножити:;

обчислити обернене дискретне перетворення Фур'є (ОДПФ) добутку:.

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

Другий розділ присвячено розробці методів томографічної реконструкції для дослідження “великих” об'єктів.

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

Розглянемо їх докладніше.

1) Перетворення даних конусних проекцій в проекційні дані паралельних віяльних шарів.

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

Практична реалізація методу інтегрування за заданим напрямком полягає у визначенні відповідних вагових коефіцієнтів для конусних проекційних даних.

Інтеграл лінійного ослаблення в -тому шарі вздовж прямої AB на рис. 2 буде дорівнювати ,

Всього отримуємо в результаті перетворень паралельних шарів.

2) Згортка.

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

3) Обернене проеціювання.

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

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

Алгоритм реконструкції зі скануванням горизонтальних секцій. Збір даних в цьому випадку здійснюється за рахунок багатократного обертання об'єкта навколо відповідно обраних центрів (рис. 3).

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

Значення початкових кутів повороту скануючої системи при скануванні з центрами обертання будуть дорівнювати:

Алгоритм реконструкції зі скануванням вертикальних секцій.

На рис. 4 показаний хід променів при скануванні для двох позицій джерела випромінювання та . Для відновлення шару при скануванні з позиції використовуються промені, зареєстровані на проміжку 1-2, а при скануванні з позиції - промені, зареєстровані на проміжку 3-4.

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

Розглянуто особливості реконструкції при скануванні об'єкта з охопленням його скануючою системою на 100%, на 50%, на . Дослідження якості рекон-струкції в кожному випадку показало, що скорочення кута охоплення об'єкта скануючою системою до 50% приводить до додаткової похибки. Її величина істотно залежить від власти-востей об'єкта дослідження (форми, розміру та просторо-вого розподілу щільності). Але за умови охоплення об'єкта на 55-60%, та застосуванні зглад-жуючої функції для додаткових 5-10% детекторів, похибка зменшується. При цьому скорочується час позиціонування об'єкта за рахунок зменшення кількості центрів обертання. Також це приводить до зменшення часу сканування та реконструкції.

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

В третьому розділі наведено розробки методів підвищення продуктивності обчислення згортки в реконструкційному алгоритмі.

На основі дослідження характеристик алгоритмів ШПФ з основою 2 (метод Кулі-Тьюки), для підвищення ефективності згортки в реконструкційному алгоритмі запропонована наступна організація обчислень:

1) використовується і дійсна, і уявна складові спектру при обробці дійсного сигналу;

2) оскільки спектри послідовностей використовуються тільки для почленного множення, можна виключити перестановку відліків в інверсному порядку;

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

4) скорочується фактична довжина послідовностей згортки з до за рахунок накладення сигналів поза зоною інтересу, що дозволяє вдвічі знизити період ШПФ, та, як наслідок, кількість обчислень.

Розроблено алгоритм обчислення одновимірної дійсної згортки з використанням гіперкомплексних чисел. Застосування методів перетворення одновимірного ДПФ в двовимірне дозволило створити алгоритм обчислення одновимірної згортки за допомогою двовимірних гіперкомплексних спектрів, який складається з таких дій:

1) Перетворити одновимірні послідовності довжини в двовимірні масиви розмірності .

2) Для переходу від дійсної числової системи до гіперкомплексної виконати поділ масиву ядра та масиву даних на 4 масива кожний за правилами:

3) Обчислити ДПФ стовпчиків масивів з урахуванням чотиривимірності відліків.

4) Помножити всі елементи на додатковий повертаючий коефіцієнт.

5) Обчислити ДПФ рядків масивів з урахуванням чотиривимірності відліків.

6) Виконати перетворення «рядокстовпчик».

7) Перемножити поелементно масиви даних з масивами ядра за правилами множення гіперкомплексних чисел.

8) Обчислити ОДПФ стовпчиків масивів з урахуванням чотиривимірності відліків.

9) Помножити всі елементи на повертаючий коефіцієнт, спряжений додатковому.

10) Обчислити ОДПФ рядків масивів з урахуванням чотиривимірності відліків.

11) Виконати перетворення «рядокстовпчик» масиву результата.

12) Перетворити гіперкомплексний результат у дійсний за правилами:

13) Перетворити двовимірний масив результата в одновимірну послідовність.

При цьому використання бікомплексної ГЧС при переході від одновимірного до двовимірного перетворення Фур'є і подальших обчислень дозволило скоротити кількість операцій за рахунок більш економічної таблиці множення бікомплексних чисел, яка містить значну кількість нулів.

Розглянуто обчислювальну склад-ність алгоритмів згор-тки одновимірних послідовностей за допомогою ШПФ з основою 2, ШПФ зі змішаною основою, двовимірного ШПФ з ГЧС К, двовимірного ШПФ з ГЧС СС. Для сигналів різної дов-жини на графіку на рис. 5 наведено кількість дійсних операцій на 1 елемент обчислення ДПФ, на графіку на рис. 6 - кількість дійсних операцій на 1 елемент обчислення згортки.

Як видно з графіків, найкращі показники за кількістю операцій має алгоритм обчислення згортки з двовимірним ШПФ з використанням бікомплексної ГЧС.

Четвертий розділ містить результати роз-робок з моделювання то-мографічної реконструк-ції “великих” об'єктів.

Представлено опис розробленого програм-ного забезпечення, яке реалізує створені методи та алгоритми тривимірної реконструкції. Він містить:

· задачі та алгоритми роботи підсистем;

· опис структури вхідних і вихідних даних;

· інтерфейс користувача.

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

Блок встановлення параметрів віртуальної томографічної системи, який дозволяє задавати такі параметри: кількість ракурсів, кут конічного променя, розмір зони відновлення, розміри об'єкту дослідження, охоплення об'єкта реєструючою системою (50%, 100%, ).

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

Блок обчислення конусних проекцій, в якому формується (кількість проекцій) наборів даних , де - кут відхилення від центрального променя у віяльному шарі, - номер шару.

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

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

В таблиці 1 наведено дані про кількість операцій з плаваючою комою на один внесок проекційних даних для різних тривимірних алгоритмів реконструкції. З таблиці видно, що алгоритм з перетворенням конусних проекцій у проекції паралельних віяльних шарів (PR_PAR) має у 3-7 разів меншу кількість операцій порівняно з наближеними реконструкційними алгоритмами (FDK0, FDK1, MIXED) та у 10-15 разів - порівняно з точними реконструкційними алгоритмами (RADON, RADONZERO, DC).

Таблиця 1 Кількість операцій на внесок для різних алгоритмів реконструкції

Розмірність проекції Алгоритм	25	26	27	28	29	210	211
FDK0	19.00	18.14	17.65	17.36	17.20	17.11	17.06
FDK1	10.75	9.53	8.84	8.46	8.25	8.13	8.07
RADON	36.84	33.42	31.71	30.86	30.43	30.21	30.11
RADONZERO	52.38	42.34	36.75	33.66	31.98	31.06	30.57
DC	36.88	33.06	30.84	29.58	28.88	28.48	28.26
MIXED	39.91	27.30	19.82	15.50	13.04	11.67	10.91
.1.1.1. PR_PAR	4.43	3.38	2.78	2.44	2.25	2.14	2.09

Позначення алгоритмів в таблиці:

- FDK0, FDK1 - модифікації алгоритму Фельдкампа, Девіса, Креса;

- RADON, RADONZERO - алгоритми Грангеата, що базуються на перетворенні Радона;

- DC, MIXED - модифікації алгоритму Дифріза і Клака;

- PR_PAR - алгоритм з перетворенням конусних проекцій в паралельні віяльні шари.

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

Значення мір та знаходяться в діапазоні , причому значення 1 вони приймають в найгіршому випадку.

Одним з основних об'єктів дослідження був стандартний фантом Шепа-Логана В таблиці 2 наведено значення похибок реконструкції даного фантому (розмір реконструйованого об'єкту - 255Ч255Ч255) при використанні різних алгоритмів. З таблиці видно, що алгоритм з перетворенням конусних проекцій у проекції паралельних віяльних шарів забезпечує точність реконструкції на рівні алгоритмів, що найчастіше застосовуються на практиці.

Таблиця 2 Порівняння похибок реконструкції для різних алгоритмів

№	Алгоритм	E1	E2
1	RADON	0.0604	0.1536
2	RADONZERO	0.0384	0.0849
3	MIXED	0.0858	0.1316
4	LINCON	0.0499	0.1123
5	FDK1	0.1067	0.1836
6	PR_PAR	0.0751	0.2198

ВИСНОВКИ

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

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

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

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

4. Запропоновано використовувати надлишковість проекційних даних при обертанні об'єкта на кут для скорочення числа сканувань з різних центрів при реконструкції “великих” об'єктів, що приводить до зменшення часу отримання проекційних даних.

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

6. Розроблено алгоритм обчислення одновимірної дійсної згортки з переходом до двовимірного перетворення Фур'є і використанням гіперкомплексних чисел, який відрізняється від існуючих застосуванням лінійного перетворення відліків одночасно з розбиттям послідовностей на частини, що в подальшому приводить до зменшення сумарного обсягу обчислень. При цьому запропоновано використовувати бікомплексну ГЧС, що дозволило скоротити кількість операцій за рахунок її більш економічної таблиці множення, яка містить значну кількість нулів.

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

8. Проведені численні експерименти з реконструкції математичних фантомів показали, що розроблені алгоритми дозволяють відновити внутрішню структуру об'єктів з похибками, не більшими, ніж у найчастіше вживаних алгоритмів, а також забезпечують просторову роздільну здатність у 0,3% від розміру зони відновлення при 1-2% контрасті та щільнісну роздільну здатність у 0,5% на об'ємі у 1-2% від розміру зони відновлення.

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Цыбульская Е.А. Моделирование высокопроизводительного томографического алгоритма реконструкции промышленных объектов // Реєстрація, зберігання і обробка даних. - 2005. - Т.7, №4. - с. 54-57.

2. Цыбульская Е.А. Практические аспекты реализации алгоритмов объемной реконструкции контрастных объектов / Э.Е.Самбыкина, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2003. - Т. 5, № 2. - c. 10-17. - Досліджено на ряді експериментів показники якості реконструкції симетричних об'єктів.

3. Цыбульская Е.А. Программные средства и методы трехмерной визуализации в томографии / Э.Е.Самбыкина, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2003. - Т.5, №3. - с. 57-62. - Виконано аналіз сучасних методів і засобів рендерінгу поверхні в тривимірній томографії.

4. Цыбульская Е.А. Разработка алгоритмов объемной реконструкции "больших" объектов / М.В.Синьков, А.И.Закидальский, Э.Е.Самбыкина, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2003. - Т. 5, №4. - с. 43-50. - Досліджено на ряді експериментів характеристики алгоритмів реконструкції з повним охопленням об'єкту скануючою системою.

5. Цыбульская Е.А. Способ повышения качества реконструкции "больших" объектов / А.И.Закидальский, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2004. - Т. 6, № 1. - с. 110-114. -Досліджено похибки реконструкції при половинному охопленні “великих” об'єктів.

6. Цыбульская Е.А. Преобразование конусного пучка в квазипараллельные слои веерного типа для повышения производительности реконструкции томографических изображений / А.И.Закидальский, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2004. - Т.6, № 2. - с. 27-32. -Досліджено обчислювальну складність перетворення даних конусних проекцій у паралельні віяльні шари.

7. Цыбульская Е.А. Реализация свертки с помощью рекурсивных процедур для реконструкционного 3-D алгоритма / А.И.Закидальский, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2005. - Т.7, №2. - с. 29-36. - Розроблено алгоритмічно-програмний модуль швидкого обчислення згортки з використанням ШПФ з проріджуванням за частотою.

8. Цыбульская Е.А. Быстрая свертка на основе БПФ / А.И.Закидальский, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2005. - Т.7, №3. - с. 62-70. - Досліджено особливості обчислення згортки в алгоритмах реконструкції.

9. Цыбульская Е.А. Алгоритмическая и программная реализация алгоритма преобразования конусных проекций / М.В.Синьков, А.И.Закидальский, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2006. - Т.8, №1. - с. 31-36. - Розроблено програмний модуль перетворення даних конусних проекцій у проекційні дані паралельних віяльних шарів.

10. Цыбульская Е.А. Компьютерная томография. Этапы развития и вклад ИПРИ НАН Украины / М.В.Синьков, А.И.Закидальский, Я.А.Калиновский, Э.Е.Самбыкина, Е.А.Цыбульская // Реєстрація, зберігання і обробка даних. - 2007. - Т.9, №3. - с. 105-116. - Проведено аналіз сучасного стану комп'ютерної томографії.

11. Цибульська Є.О. Алгоритм обчислення одновимірної згортки з використанням гіперкомплексних чисел / М.В.Синьков, А.І.Закидальський, Є.О.Цибульська // Реєстрація, зберігання і обробка даних. - 2009. - Т.11, №1. - c. 20-26. - Запропоновано спосіб переходу від дійсних послідовностей до гіперкомплексних при обчисленні згортки.

12. Цибульська Є.О. Розробка нового алгоритму тривимірної томографічної реконструкції / М.В.Синьков, А.І.Закидальський, Є.О.Цибульська // Наукові вісті НТУУ КПІ. - 2009. - № 4. - c. 102-111. - Розроблено програмний комплекс моделювання тривимірної томографічної реконструкції.

13. Цыбульская Е.А. Реконструкционные алгоритмы томографических систем, ориентированных на решение задач контроля и безопасности / М.В.Синьков, А.И.Закидальский, Е.А.Цыбульская // Інформаційні технології та безпека. - Матеріали IV міжнародної науково-практичної конференції (Партенит, 22-26 июня 2004). - 2004. - с. 91-95. -Досліджено особливості використання томографії в задачах контролю та безпеки.

14. Цибульська Є.О. Розробка та дослідження високопродуктивних алгоритмів обробки томографічної інформації // Матеріали ХІ-ї Міжнародної науково-технічної конференції “Системний аналіз та інформаційні технології” - Київ, НТУУ “КПІ”, ІПСА. - 2009. - с. 589.

15. Цибульська Є.О. Застосування розширення поля комплексних чисел для рішення обернених задач інтегральної геометрії / Я.О.Каліновський, Є.О.Цибульська // Український математичний конгрес. - Київ. - 2009. - стендова доповідь. - Запропоновано спосіб переходу від дійсних послідовностей до гіперкомплексних при обчисленні перетворення Фур'є.

АНОТАЦІЯ

Є.О.Цибульська. Розробка і математичне моделювання методів тривимірної томографічної реконструкції. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - Математичне моделювання та обчислювальні методи. - Національний технічний університет України “Київський політехнічний інститут”. - Київ, 2010.

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

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

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

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

Ключові слова: томографія, алгоритми 3D-реконструкції, згортка, швидке перетворення Фур'є, гіперкомплексні числові системи.

АННОТАЦИЯ

Е.А.Цыбульская. Разработка и математическое моделирование методов трехмерной томографической реконструкции. - Рукопись.

Диссертация на соискание научной степени кандидата технических наук по специальности 01.05.02 - Математическое моделирование и вычислительные методы. - Национальный технический университет Украины “Киевский политехнический институт”. - Киев, 2010.

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

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

В соответствии с поставленной целью, были предложены новые методы томографической реконструкции, направленные на исследование “больших” объектов, предложены новые подходы к повышению качества и производительности реконструкции.

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

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

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

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

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

В последние несколько лет появился ряд публикаций, в которых указывается на возможность использования гиперкомплексных числовых систем для вычисления двумерной свертки. В работе представлен созданный алгоритм одномерной свертки с использованием гиперкомплексных чисел 4-го порядка, разработан программный модуль на языке С++ для реализации этого алгоритма.

Как известно, существует большое количество гиперкомплексных числовых систем. В результате исследования правил выполнения операций в различных ГЧС, была определена гиперкомплексная числовая система, наиболее приемлемая для использования в алгоритме свертки.

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

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

Ключевые слова: томография, алгоритмы 3D-реконструкции, свертка, быстрое преобразование Фурье, гиперкомплексные числовые системы.

ANNOTATION

I.O.Tsybulska. The development and mathematics modeling of three-dimension tomographic reconstruction methods.

Ph.D. thesis on the speciality 01.05.02 - Mathematics modeling and computed methods. - National Technical University of Ukraine “Kyiv Polytechnical Institute”, Kyiv, 2010.

This thesis holds research in the area of mathematics modeling of tomography 3D-reconstruction, research of construction methods of reconstruction algorithms, developing and modeling of 3D-reconstruction algorithms.

In according of the aims, there are developed new methods of tomography reconstruction to research objects which size is greater than CT-scaner detector system, there are offered methods to increase the reconstruction quality and speed. The analyse of complexity of developed algorithms and the comparison it with some known algorithms is done in the thesis.

There are researched the methods of computing of line convolution which including into reconstruction algorithms, there are offered methods to reduction of comvolution complexity. The developed algorithm for computing of 1D convolution with 4D hypercomplex numbers is represented, the hypercomplex numerical system, which allows the reduction of convolution complexity, is determined.

All described researches give the possibility to develop the program complex for modeling of tomography 3D-reconstruction and to show the results of reconstruction of mathematics phantoms structure.

Keywords: tomography, 3D-reconstruction algorithms, convolution, fast Fourier transform, hypercomplex numerical systems.

Размещено на Allbest.ru

...