Содержание к диссертации
Введение
CLASS 1. Введение CLASS 1
1.1. Рентгеновская компьютерная томография 1
1.2. Исследования в области быстрых вычислений для КТ 2
1.3. Научная новизна 4
1.4. Структура диссертации 5
2. Компьютерная томография 7
2.1. Введение и базовые определения 7
2.2. Преобразование Радона 11
2.3. Центральная проекционная теорема 13
2.4. Обратное преобразование Радона 15
2.5. Аналитические методы реконструкции 16
2.5.1. Методы реконструкции на базе преобразования Фурье . 16
2.5.2. Метод обратного проецирования с фильтрацией 18
2.6. Итерационные методы реконструкции 22
2.7. Сравнение различных методов 22
2.8. Детальное описание метода обратного проецирования с фильтрацией 24
2.8.1. Дискретные переменные и функции 24
2.8.2. Фильтрация 26
2.8.3. Алгоритм реконструкции Фельдкампа 29
2.8.4. Дискретный алгоритм обратного проецирования с фильтрацией 33
2.9. Выводы 35
3. Быстрая реконструкция на практике 37
3.1. Цилиндрический алгоритм 38
3.1.1. Система координат реконструкции 40
3.1.2. Распределение вокселей 41
3.1.3. Вращение цилиндрической сетки 45
3.1.4. Важные параметры эксперимента 46
3.1.5. Таблица объема 48
3.1.6. Таблица отфильтрованных проекций 49
3.1.7. Таблица геометрии 50
3.1.8. Таблица весовых коэффициентов 56
3.1.9. Модифицированный алгоритм 58
3.1.10. Анализ цилиндрического алгоритма 61
3.2. Реконструкция с применением параллельных вычислений . 62
3.2.1. Обзор исследований 63
3.2.2. Требования к проектированию системы 65
3.2.3. Аппаратная архитектура 66
3.3. Выводы 67
4. Формальное описание реконструкции 68
4.1. Последовательное обратное проецирование 69
4.1.1. Модули памяти последовательного обратного проецирования 69
4.1.2. Процесс последовательного обратного проецирования . 70
4.2. Параллельное обратное проецирование 72
4.2.1. Выбор метода параллельной обработки 72
4.2.2. Модули памяти параллельного обратного проецирования 74
4.2.3. Процесс параллельного обратного проецирования . 75
4.2.4. Корректность схемы параллельного обратного проецирования 78
4.3. Конвейеризированное параллельное обратное проецирование . 79
4.3.1. Модули памяти конвейеризированного параллельного обратного проецирования 79
4.3.2. Процесс конвейеризированного параллельного обратного проецирования 81
4.3.3. Корректность схемы конвейеризированного параллельного обратного проецирования 83
4.4. Конвейеризированная реконструкция плоскости 85
4.4.1. Вычисления геометрии 85
4.4.2. Планирование процесса реконструкции 86
4.5. Реконструкция объема 88
4.5.1. Проекция одной плоскости 89
4.5.2. Модуль памяти отфильтрованных проекций 91
4.5.3. Фильтрация проекционных данных 92
4.5.4. Процесс конвейеризированной реконструкции 95
4.5.5. Анализ производительности 97
4.6. Выводы 98
5. Аппаратная архитектура 99
5.1. Основные обозначения 99
5.2. Обзор аппаратной архитектуры 102
5.2.1. Структура 103
5.2.2. Требования архитектуры 103
5.2.3. Процесс реконструкции 108
5.3. Устройство управления 109
5.3.1. Окружение CCenv 112
5.3.2. Окружение FCCenv 114
5.3.3. Окружение PECenv 118
5.4. Подсистема памяти 119
5.4.1. Выбор типа памяти 119
5.4.2. Структура внешней памяти 120
5.5. Устройство фильтрации проекций 123
5.5.1. Окружение FDenv 126
5.5.2. Окружение FLTenv 128
5.6. Устройство вычисления геометрии 130
5.6.1. Вычисления геометрии 130
5.6.2. Переменные и константы 133
5.6.3. Обзор архитектуры 134
5.6.4. Окружение управления INSCenv 137
5.6.5. Окружение TSCenv 140
5.6.6. Вычисление «Общего элемента» 140
5.6.7. Окружение WCOEenv 143
5.6.8. Окружение ZCenv 144
5.6.9. Вычисление адресов пересечений 145
5.7. Устройство управления данными 148
5.7.1. Окружение DFCenv 152
5.7.2. Окружение GMenv 156
5.7.3. Двойная структура памяти 159
5.7.4. Окружение Alenv 160
5.7.5. Окружение DSenv 161
5.7.6. Интерфейс SDRAM 162
5.7.7. Окружение IFCont 163
5.7.8. Окружение RFRenv 166
5.7.9. Доступ к памяти 167
5.8. Устройство параллельного обратного проецирования 168
5.8.1. Процессорные элементы 171
5.8.2. Окружение ADDenv 175
5.8.3. Окружение RAenv 178
5.8.4. Окружение AVMenv 178
5.9. Выводы 181
6. Оценка аппаратной архитектуры 182
6.1. Параметры системы 182
6.2. Вычисления геометрии 185
6.2.1. Метрики и параметры 185
6.2.2. Выбор коэффициентов 185
6.3. Реконструкция изображения фантома 189
6.4. Производительность системы 192
6.4.1. Параметры объема 192
6.4.2. Скорость реконструкции 196
6.4.3. Пропускная способность 200
6.4.4. Масштабируемость 202
6.5. Реализация дизайна 203
6.6. Моделирование 206
6.7. Выводы 208
7. Заключение 209 Приложения 213
А. Дельта функция 213
Б. Доказательство центральной проекционной теоремы 214
8. Обзор технологии SDRAM 216
Список литературы 219
- Исследования в области быстрых вычислений для КТ
- Детальное описание метода обратного проецирования с фильтрацией
- Реконструкция с применением параллельных вычислений
- Модули памяти конвейеризированного параллельного обратного проецирования
Исследования в области быстрых вычислений для КТ
Проблема исследования внутренней структуры объектов была всегда важна во многих областях науки и техники, в особенности в медицине и неразрушающем контроле (НРК). Среди различных методов, используемых, для таких исследований рентгеновская компьютерная томография (КТ) является одной из самых лучших, ввиду возможности исследования всех типов материалов.
Рентгеновская КТ основана на измерении ослабления рентгеновского излучения, проходящего сквозь объект исследования. Используя данные измерения, называемые проекциями, которые собраны с разных сторон объекта, возможно вычисление (реконструкция) распределения плотности в исходном объекте. Математически, исходная проекция это прямое преобразование Радона, а реконструкция — обратное преобразование [1, 2, 3, 4, 5]. В зависимости от измерений реконструкция может быть двух- или трехмерной, и реализуется в виде специального алгоритма с большим количеством вычислений — 0(N4), где N — число элементов в одной строке детектора. Большое количество данных и вычислительная сложность алгоритмов реконструкции являются причиной значительного времени реконструкции. Например, объем, состоящий из 5123 векселей, может быть реконструирован примерно за пять минут1, используя современный компьютер [6, 7]. Для приложений критичных ко времени реконструкции задача восстановления объема может быть ускорена за счет применения па 1 осень 2003 г. раллельных вычислений, например, распределения реконструкции по вычислительным узлам сети. Однако, такое решение не может быть использовано при условии, что размер системы ограничен, например, в системах промышленного контроля и мобильных системах контроля. Появление новых детекторов высокого разрешения также усложняют задачу реконструкции ввиду значительного увеличения объема обрабатываемых данных. Например, в работе [6] показано, что используя детектор с 10242 пикселями получаются проекции общим объемом приблизительно 1.6 Гб и время реконструкции объема на одном ПК занимает около 90 минут.
Поиск альтернативных вычислительных структур, которые могут заменить мультикомпьютерные системы в специальных задачах, является актуальной задачей исследования. Такие структуры обычно создаются на базе процессоров цифровой обработки сигналов (ЦОС), программируемых логических интегральных схем (ПЛИС) либо заказных интегральных схем (ИС). Специализированные вычислительные структуры имеют широкие возможности для реализации сложных алгоритмов и структур данных, а также позволяют сфокусироваться на оптимизации критических для производительности параметров. Такие преимущества специализированного аппаратного обеспечения, как распараллеливание и конвейеризация операций, могут легко быть реализованы на базе программируемой логики.
1.2. Исследования в области быстрых вычислений для КТ
Исследования и результаты в области быстрой реконструкции в КТ известны давно и обычно выделяются два основных направления: программная и аппаратная реконструкция. Под термином программная реконструкция будем подразумевать реализацию алгоритмов реконструкции на базе ПК, при этом вычисления производятся одним или несколькими ПК, соединенными в локальную вычислительную сеть. Ускорение реконструкции достигается путем наращивания количества ПК и использования оптимальных схем параллельных вычислений. Некоторые примеры таких высокопроизводительных систем описаны в источниках [6, 7, 8, 9, 10].
Аппаратные реализации, предложенные и описанные в литературе, изготовлены в виде специализированных плат для использования в составе ПК. Эти системы построены на базе различных технологий, таких, как специализированные процессоры, программируемая логика и заказные ИС.
Первые аппаратные реализации с использованием сверх больших интегральных схем (СБИС) содержали в себе достаточно простые вычислительные структуры, которые предназначались только для произведения основного шага реконструкции — обратного проецирования (сложения) [11, 12, 13]. Это были заказные разработки для двухмерной КТ с параллельным пучком лучей. Последующие исследования были сделаны группой под руководством Agi [14, 15, 16]: заказные ИС комбинировались с процессорами ЦОС для вычисления реконструкции. Такая архитектура состояла из матрицы элементов, на базе которой были реализованы прямое и обратное преобразование Радона с использованием конвейеризации операций. Эта разработка использовалась для двухмерной КТ с параллельным и веерным пучками. Аналогичное исследование, однако специализированное для двухмерной реконструкции с параллельных проекций, было описано в работе [17]. При этом, в качестве основного вычислительного элемента для реализации процесса обратного проецирования была использована ПЛИС.
В настоящее время, наиболее значима в практике так называемая конусная томография (схема сканирования с расходящимся пучком), которая имеет значительное преимущество перед схемой сканирования с параллельным пучком — время измерения проекций значительно ниже. Однако, процесс реконструкции объекта по конусным проекциям более сложен, чем по параллельным проекциям. Известны две работы (осень 2003 года) в области аппаратной реконструкции трехмерных объектов по конусным проекциям. Оба исследования используют алгоритм реконструкции Фельдкампа [18]. Первая система CBR-2000 на базе процессоров XTrillion (заказные ИС) производится фирмой Terarecon [19] и позволяет производить реконструкцию объема из 5123 вокселей приблизительно за 128 секунд, используя арифметику с фиксированной точкой. Вторая си стема [20, 21], разработанная фирмой Mercury Computer Systems на базе ПЛИС, реконструирует объем из 5123 вокселей приблизительно за 39 секунд. При этом, в открытой печати не представлены сведения о точности реконструкции и о масштабировании этих двух систем для реконструкции объемов с большим количеством вокселей, например, 10243. Эти сведения очень важны для использования такого рода систем в области промышленного НРК. Также, отсутствует описание возможностей данных систем работать с новыми детекторами, имеющими высокое разрешение.
Тема исследования данной работы — практическая реализация системы трехмерной рентгеновской КТ Описана разработка высокоскоростной аппаратной архитектуры реконструкции объекта по конусным проекциям. Алгоритм реконструкции трехмерных объектов, использованный в данной работе, является самым современным прикладным алгоритмом в НРК. В отличие от других работ в области аппаратной реализации алгоритмов реконструкции, данная работа представляет аппаратную реализацию с полным формальным описанием и спецификацией аппаратной архитектуры.
Для реализации в системе была использована модификация алгоритма реконструкции Фельдкампа по коническим проекциям. В работе формализованы все модификации данного алгоритма, такие как распараллеливание и конвейеризация вычислений. Эти модификации позволили значительно ускорить процесс реконструкции. Дополнительное внимание было уделено архитектуре подсистемы памяти и организации доступа к ячейкам памяти, выполняемых в процессе обратного проецирования. Все вычисления производятся с использованием арифметики с фиксированной точкой.
После анализа алгоритма и полной спецификации параметризированной вычислительной архитектуры была произведена реализация этой архитектуры на базе ПЛИС фирмы Xilinx. Были исследованы воздействия различных параметров на производительность и точность реконструкции. Моделирования показали, что аппаратная система, содержащая в себе одну микросхему ПЛИС и внешнюю динамическую память приблизительно на порядок быстрее, чем система программной реконструкции на базе процессора Intel Pentium 4 2GHz [6, 7]. Было показано, что разработанная архитектура является масштабируемой для реконструкции объемов разного размера. Разработанная архитектура была оценена для различного числа процессорных элементов, используя теоретические и практические (основанные на моделировании) расчеты. В результате было проанализировано влияние параметров дизайна системы на ускорение вычислений и масштабирование архитектуры.
Детальное описание метода обратного проецирования с фильтрацией
Большинство обзорных работ в области КТ, например [2, 5, 29, 50], включают в себя сравнения различных методов реконструкции и их вариации. При этом,
3используя, например, метод Качмажа (1937) для решения системы уравнений результаты сравнения и выводы значительно зависят от природы реконструируемых объектов и особенностей реализации методов. Не существует однозначного ответа на вопрос «Какой из методов наилучший?»; очевидно то, что различные методы подходят для различных приложений.
При анализе скорости и точности вычислений, метод обратного проецирования с фильтрацией является предпочтительнее всех остальных методов [30] и может производить лучшее пространственное/контрастное разрешение у изображения4. Другими причинами того, что метод обратного проецирования с фильтрацией является преимущественным в использовании на практике являются его простота реализации и внутренний параллелизм: каждая отфильтрованная проекция (2.5.5) для определенного угла может быть вычислена независимо от других проекций, и, соответственно, на практике процесс обратного проецирования может быть запущен в течение измерения проекций.
С другой стороны, методы реконструкции на базе преобразования Фурье не так просты в реализации и процесс интерполяции является особенно долгим, чтобы избежать появления артефактов в восстанавливаемом изображении.
Методы, использующие декомпозицию реконструкции, являются очень перспективными и уже получены хорошие результаты в процессе оптимизации обратного проецирования с фильтрацией. Значительные ускорения процесса реконструкции описаны в работах [36, 37], однако данные алгоритмы находятся в состоянии изучения для построения подходящих математических моделей и оценки точности.
По сравнению с аналитическими методами итерационные методы реконструкции значительно медленнее, т.к. для получения подходящего результата необходимо выполнение нескольких итераций реконструкции. Однако, итерационные методы позволяют получить оптимальные результаты в случаях за-шумленных или неполных данных с детектора в реальных приложениях, где аналитические методы производят значительные артефакты.
Сложность реконструкционных методов может быть измерена используя раз-описание результатов и характеристик качества изображения различных алгоритмов реконструкции приведено в главе "Computerized Tomography" под редакцией мер сетки, который обычно равен количеству элементов в одной строке детектора N. Соответственно, количество пикселей в восстанавливаемом изображении для двумерного случая равно N2, а для трехмерного N3. Метод обратного проецирования с фильтрацией имеет вычислительную сложность 0(N3) для двумерного случая (0(N4) для трехмерного) с количеством проекций 0(N). Основное преимущество методов на основе преобразования Фурье в том, что ни один шаг алгоритма не требует более чем 0(iV2log2Ar) операций для двумерного случая. Методы декомпозиции оцениваются тем же количеством операций для двумерного случая, однако в этих методах тоже присутствует интерполяция. Конечно же, разработка методов реконструкции и в настоящее время является актуальной задачей, ввиду того, что почти ежедневно появляются новые задачи в КТ, каждая из которых имеет свои сложности для разработчиков алгоритмов и ученых в области численных методов.
В прошлом разделе представлены непрерывные функции для реконструкции функции плотности с параллельных проекций используя метод обратно проецирования с фильтрацией. Однако непрерывные функции не могут быть реализованы для восстановления изображения на практике по нескольким причинам:
- количество проекций с углами ф не может быть бесконечным, т.е. значение ())j будет дискретным;
- разрешение системы КТ ограничено ввиду конечности геометрических размеров элементов детектора.
В то время как теоретическое описание восстановления изображения по проекциям требует использование непрерывных функций, практическая реализация сновывается только на дискретных величинах, и, соответственно, необходимо провести преобразование всех величин в дискретные.
Реконструкция с применением параллельных вычислений
Анализ Цилиндрического алгоритма проведем используя следующие практические соображения: ЧИСЛО Элементов В ОДНОЙ ПЛОСКОСТИ ГОтах Отах (N2), ЧИСЛО ПЛОСКОСТеЙ Ютах N, ЧИСЛО ПрОЄКЦИЙ fydmax — , общее число вокселей в объеме 0(N3). Время работы всего алгоритма реконструкции трехмерного объема по коническим проекциям остается 0(N4). Каждая часть алгоритма обратного проецирования с фильтрацией имеет следующую временную сложность: - вычисление таблицы геометрии имеет сложность - вычисление таблицы весовых коэффициентов имеет сложность - фильтрация с использованием свертки имеет сложность 0(7V3); - обратное проецирование имеет сложность 0(N4). Преобразование объема из цилиндрических в декартовы координаты имеет временную сложность 0(N3). Влияние использования цилиндрической сетки на качество реконструируемого изображения при реализации на ПК было проанализировано в диссертации Buck [59], где показано, что скорость реконструкции при N — 512 более чем в три раза быстрее, чем непосредственно реализованный алгоритм обратного проецирования с фильтрацией для трехмерных объектов на ПК. Для задач НРК [61] этот результат означал значительное снижение времени реконструкции в промышленных приложениях, например, поиск трещин в металлических образцах готовой продукции.
Пространственная сложность модифицированного алгоритма считается следующим образом:
- таблица геометрии INS[] содержит 0(N3) элементов,
- таблица весовых коэффициентов WT[] содержит 0(N2) элементов,
- таблица отфильтрованных проекций FD[] содержит fydmax N2 элементов (ее можно уменьшить до N2 элементов, сохраняя отфильтрованные данные только для текущей проекции),
- реконструированная таблица объема Vc [ ] содержит элементов.
Точные значения требуемого объема памяти можно вычислить для определенного параметра эксперимента — полугла раскрытия (см. выражение для числа плоскостей (3.1.15)). Для N = 512 в Таблицах геометрии и объема содержатся более 130-106 элементов.
Доступ к таблицам геометрии, весовых коэффициентов и объема осуществляется последовательно, тогда как доступ к таблице отфильтрованных проекций выполняется произвольно. Следовательно, для реализации высокоскоростной реконструкции необходимо оптимизировать размещение данных в памяти и, соответственно, модифицировать сам Цилиндрический алгоритм. Эти изменения алгоритма описаны в последующих главах при описании аппаратной архитектуры.
Усовершенствование алгоритмов и применение параллельных вычислений являются теми решениями, которые требуются для сокращения времени реконструкции и оптимизации работы с памятью.
Системы, использующие параллельные вычисления, базируются на работе Параллельных (вычислительных) Элементов (ПЭ), имеющих свою собственную память и доступ к общей памяти системы. Примеры ПЭ это ОКМД7 и МКМД8 процессоры и транспьютеры [66, 67], собранные в единую комплексную систему для решения задач КТ в различных сферах.
При параллельной обработке задача восстановления изображения распределяется по ПЭ в системе, причем распределение вычислений основано на одной из четырех форм параллелизма при реконструкции, определенных в работе Nowinski [68]:
1) параллельность обработки пикселей (вокселей в трехмерном случае) — все пиксели обрабатываются независимо друг от друга,
2) параллельность обработки лучей — в процессе реконструкции лучи могут обрабатываться независимо,
3) параллельность обработки проекций — каждая проекция обрабатывается независимо от других,
4) параллельность операций — операции низкого уровня, такие как сложение и умножение, могут быть сделаны параллельно.
Программные системы реконструкции
Исследования в области эффективной параллельной реализации алгоритмов КТ были проведены на широком спектре коммерчески доступных ОКМД и МКМД компьютеров: СМ-5, iPSC/2, Intel Paragon, Alpha и Cray [8, 9, 10, 61, 69, 70, 71, 72, 73, 74]. Поиск эффективных схем соединения и передачи данных для ПЭ, а также схем распределения задач по ПЭ являются основными направлениями исследований во всех работах. Большинство работ имеют практическое применение в медицине и НРК. Среди производителей полных комплектов оборудования для КТ, построенных на базе многопроцессорных систем для трехмерной диночный Поток Команд Множественный Поток Данных 8МКМД: Множественный Поток Команд Множественный Поток Данных
Аппаратные системы реконструкции
В области реализации аппаратных систем реконструкции основные решения состоят в том, что в виде ПЭ выступают процессоры цифровой обработки сигналов, либо специализированные системы, спроектированные и реализованные на ПЛИС либо на СБИС.
Вычислительная структура, составленная из процессоров цифровой обработки сигналов соединенных в гиперкуб была предложена в работах [76, 77] для реализации метода обратного проецирования с фильтрацией и алгебраического метода реконструкции. Анализ и выбор подходящих процессоров цифровой обработки сигналов был проведен в исследованиях [14, 78]: подробно описаны характеристики таких процессоров и их производительность при обратном проецировании с фильтрацией. Исследования показали хорошие результаты производительности таких процессоров, потому что они оптимизированы для выполнения операций умножения и сложения. Такие системы предназначены для реконструкции двумерных изображений по веерным проекциям и получения реконструированных трехмерных объектов из таких двумерных срезов.
Конкуренцию процессорам цифровой обработки сигналов составляют специализированные системы ввиду своей гибкости в управлении и организации вычислений. Ранние примеры специализированных структур для КТ на базе СБИС описаны в [12, 13]: геометрические вычисления с интерполяцией и двумерное обратное проецирование были реализованы в виде конвейерной архитектуры на базе СБИС. Оптимальную реализацию промежуточных вычислений для метода обратного проецирования с фильтрацией — различные структуры суммирования и умножения, были изучены в работе посвященной двумерной реконструкции [11].
Некоторые исследования использовали графические карты [48] и специализированные аппаратные системы рендеринга объема [79] для решения задач реконструкции в медицинских приложениях. Описываются эффективные системы еализации итерационных методов реконструкции (ART, SART).
Конвейеризированная архитектура на СБИС для реконструкции двумерных изображений построена Agi et. al. [15] и, совместно с многопроцессорной системой (на базе процессоров цифровой обработки сигналов), была применена при исследовании задачи реконструкции [16]. Процессоры цифровой обработки сигналов использовались для выполнения быстрого преобразования Фурье для фильтрации проекций и управления потоками данных, в то время как процесс обратного проецирования производился конвейеризированной структурой в СБИС с микросхемами внешней памяти.
Появление и совершенствование технологии ПЛИС открыло новые перспективы проектирования различных типов устройств для реконструкции по проекциям. Работы [19, 20] описывают реконфигурируемые системы КТ на базе ПЛИС, используемые для быстрой реконструкции в различных областях применения КТ. Высокая скорость реконструкции (сравнивая с ПК) была достигнута одной из работ по реконструкции по двумерным параллельным проекциям методом обратного проецирования с фильтрацией используя в системе коммерческую платформу с ПЛИС фирмы Xilinx [17]. В этой работе все вычисления с плавающей точкой были преобразованы в вычисления с фиксированной точкой и были теоретически проанализированы ошибки вычислений. Обратное проецирование с фильтрацией используя предварительно отфильтрованные данные было реализовано с использованием параллельной сбалансированной архитектуры с конвейерной обработкой при использовании различных типов памяти: внешней и находящейся внутри ПЛИС.
Все известные работы в области аппаратной реконструкции производят восстановление объекта либо в двумерной веерной схеме, либо комбинируют трехмерное изображение из двумерных срезов. Ни одна из известных разработок не имеет реализацию в одной микросхеме всех стадий алгоритма реконструкции по коническим проекциям используя обратное проецирование с фильтрацией для приложений промышленного контроля.
Изучение работ в области аппаратной реконструкции показало, что для создания аппаратной архитектуры нужно обратить внимание на следующее:
- необходимо провести модификацию алгоритма реконструкции для соответствия различным ограничениям аппаратного обеспечения, таким как пропускная способность памяти и т.д.;
- выбор системы счисления, например, система с фиксированной точкой [17] или башенная система (знак/логарифм) [11], значительно влияет на скорость реконструкции;
- скорость процесса реконструкции значительно повышается при использовании конвейеризации вычислений и параллельной обработки потоков данных.
Модули памяти конвейеризированного параллельного обратного проецирования
Проблема высокоскоростной реконструкции изображения в настоящее время является актуальной в трехмерной КТ. Существующие алгоритмы стали объектом постоянных исследований и оптимизаций с целью увеличения скорости трехмерной реконструкции. Увеличение объема данных с детекторов, например, при применении новых детекторов с большим количеством элементов, может быть обработано используя многомашинные вычислительные комплексы. Это является актуальной и важной проблемой в области НРК [6, 8, 58, 69]. Если же система для реконструкции имеет специальные ограничения по размеру (например, в промышленных или медицинских приложениях), то использование многомашинных систем ограничено, и, соответственно, требуются исследования в области создания альтернативных систем. Такие альтернативные системы должны производить трехмерную реконструкцию и иметь производительность сравнимую с существующими системами на базе ПК.
Одна из таких аппаратных архитектур, предназначенная для реконструкции по коническим проекциям, представлена в данной работе. В этой архитектуре реализован модифицированный алгоритм реконструкции Фельдкампа (Цилиндрический алгоритм [59]). Для повышения скорости реконструкции были использованы, во-первых, методы параллельной обработки данных и, во-вторых, специализированное планирование процесса реконструкции. Все модификации алгоритма были формализованы. Специальное исследование было посвящено определению минимального объема памяти, требуемого в процессе реконструкции. Вычисления в ходе реконструкции производится с использованием арифетики с фиксированной точкой, в том числе детально описан процесс геометрических вычислений с фиксированной точкой. Разработанная архитектура объединяет все этапы реконструкции:
- фильтрация и управление проекционными данными,
- вычисление данных геометрии в реальном масштабе времени, и
- взвешенное обратное проецирование отфильтрованных данных.
Параметризированная вычислительная архитектура подробно описана и реализована на базе ПЛИС фирмы Xilinx.
Разработанная архитектура оценена для ПЛИС фирмы Xilinx. Представлены различные характеристики разработанной аппаратной архитектуры, например, размер дизайна в микросхеме и скорость реконструкции. Проанализировано влияние различных параметров на точность вычислений и скорость реконструкции. Дополнительно проанализировано влияние использования динамической памяти на производительность реконструкции.
В работе показана связь между точностью результата реконструкции и вычислениями данных геометрии и фильтрацией. Результаты вычислений данных геометрии в формате с фиксированной точкой (моделирование) сравнивались с результатами вычислений с плавающей точкой (программа на языке Си). Определены ограничения аппаратных вычислений и выбраны допустимые размеры бит-векторов для аппроксимаций вычислений. Определены и оценены ошибки вычислений геометрии. Также проанализировано влияние этих ошибок на результаты реконструкции. Используя результаты моделирования выявлено значительное влияние фильтрации на результаты реконструкции. Для фильтрации использован КИХ-фильтр с переменой длиной ядра фильтрации. Естественно, что фильтрация с небольшой длиной фильтра требует проведения дополнительной фильтрации конечных результатов. Однако, размер ядра фильтра имеет значительное влияние на размер и скорость дизайна на ПЛИС [88].
Производительность архитектуры была оценена при использовании минимальной длительности синхросигнала в реализации на ПЛИС фирмы Xilinx.
Одна плоскость реконструируется приблизительно за 0.08 с1, в зависимости от числа параллельных процессорных элементов, позиции плоскости внутри объема и параметров эксперимента. Объем, состоящий из 490 х 5122 вокселей, может быть реконструирован за 39.22 с используя 12 процессорных элементов и за 22.64 с используя 24 процессорных элемента. Время реконструкции объемов, содержащих большее количество вокселей, например, 10243, может быть вычислено используя время, необходимое на реконструкцию одной плоскости (6.4.1) умноженное на количество плоскостей в этом объеме. Такие вычисления могут быть сделаны после оценки модифицированного дизайна для новой задачи. Длительность синхросигнала может быть уменьшена при использовании новых версий программного обеспечения ПЛИС в которых, например, применяются новые алгоритмы расположения устройств на кристалле и алгоритмы трассировки. Однако улучшения скорости дизайна почти непредсказуемы ввиду того, что существуют большие задержки межмодульных соединений на кристалле. Предполагается, что результат может быть улучшен на 10-15%.
Производительность аппаратной архитектуры для реконструкции сравнивалась с системой для реконструкции на базе процессора Intel Pentium 4 с частотой 2 ГГц. Время реконструкции объема, состоящего из 512 вокселей, по 400 коническим проекциям равно примерно пяти минутам [6, 7]. Вычисления с использованием разработанной архитектуры примерно на порядок2 быстрее для такой же задачи. Все же, технологии для ПЛИС и для микропроцессоров не могут сравниваться. Дизайн ПЛИС имеет меньшую функциональность и всегда медленнее, потому что ПЛИС это перепрограммируемая логика с большими задержками межкомпонентных соединений. Технологии памяти современных ПК, например, RDRAM и DDR RAM, также быстрее чем SDRAM, использованная в аппаратной архитектуре. Дальнейшее повышение скорости и производительности аппаратной архитектуры достигается путем: - использования нескольких ПЛИС (несколько архитектур, работающих параллельно), что ведет к значительному повышению размера дизайна ввиду для 12 процессорных элементов олучены ускорения для различного количества параллельных процессорных элементов использования большого количества микросхем памяти; - реализация представленной архитектуры на заказной СБИС, что поможет увеличить скорость дизайна, которая будет в таком случае ограничена только компонентами памяти архитектуры, однако приведет к увеличению стоимости реализации вычислительной архитектуры.
