WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

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

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

Целью вычисления новых массивов является генерирование массивов, элементами которых будут заменяться значение яркости соседней с заполняемой ячейки при условии, если эта ячейка также является пустой (не отстканирована).

Генерирование нового массива происходит по следующей формуле:

(12) где, – среднее значение яркости ячейки с координатами нового массива, – значение яркости ячейки старого массива, – число объединенных ячеек старого массива.

Целью второго шага является вычисление значений яркости всех пустых ячеек исходного массива по сгенерированным массивам. Здесь используется интерполяционный полином третьей степени

(8) где, – координата ячейки, – значение яркости ячейки,,, и – коэффициенты.

Так как по трем координатам получается 3 разных значения яркости заполняемой ячейки, то за значение яркости данной ячейки можно принять среднее значение

, (9)
где, – значение яркости данной ячейки,,, – составляющие компоненты значения яркости на трех направлениях.

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

(10) где, – вычисленное значение яркости пустой ячейки массива, – число соседних ячеек, – результат по формуле (8), – значение яркости ячеек на диагональных направлениях, – число ячеек на диагональных направлениях.

Для реализации используемого в методе скалярного произведения матрицы и вектора в диссертации разработан специальный узел (рис. 5). Если используются абсолютные координаты, то нужно вычислить четыре коэффициента путем решения системы уравнения (11), – это требует 48 (344) умножений и 36 (343) сложений.

Для упрощения схемы предлагается использовать относительные координаты: координаты заполняемой ячейки принимаются за начало координат, тогда координаты её соседних ячеек будут равны: -2, -1, 1, 2. Таким образом, формула (8) сводится к следующей:

(12)

Рис. 5. Функциональная схема узла вычисления значения яркости заполняемой ячейки при использовании абсолютных координат

Функциональная схема вычисления значения интенсивности заполняемой ячейки после упрощения представлена на рис. 6.

Рис. 6. Функциональная схема узла вычисления значений яркости при использовании относительных координат

Очевидно, что использование относительных координат позволяет заметно сократить аппаратные ресурсы и время вычисления. Сравнительные данные приведены в таблице 1.

Таблица 1. Сравнение количества аппаратных ресурсов узла вычисления значения яркости

Кол-во аппаратных ресурсов

Использование абсолютных координат

Использование относительных координат

Сокращение

%

Кол-во сумматоров

47 (315+2)

11 (33+2)

77%

Кол-во умножителей

58 (319+1)

13 (34+1)

78%

Кол-во триггеров

122 (403+2)

38 (123+2)

69%

Кол-во мультиплексоров

15 (35)

6 (32)

60%

Структурная схема аппаратной части блока заполнения пустот представляется на рис. 7. Инструменты моделирования – Matlab/Simulink и Modelsim. Моделирование схемы показывает правильность предложенного алгоритма.

Рис. 7. Структурная схема аппаратной реализации блока заполнения пустот

Очевидно, погрешность (отклонение вычисленной яркости от истинной) заполнения пустот 3-мерного изображения зависит не только от выбора алгоритмов, но и от числа и распределения сечений. Ниже приведены результаты эксперимента на геометрическом предмете – эллипсоиде. При увеличении количества сечений средняя погрешность (среднее отклонение вычисленного значения от исходных данных всех заполняемых ячеек) постоянно уменьшается (рис. 8).

Рис. 8. Зависимость средней погрешности от количества сечений

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

Таблица 2. Сравнение алгоритмов заполнения на примере сканирования эллипсоида

Алгоритм

Средняя погрешность, %

Время вычисления, с.

Заполнение соседним элементом

6.81

1.0995

Линейная интерполяция

2.12

5.6524

Sinc-интерполяция

2.04

4.6461

Предложенный алгоритм

2.07

2.0077

Примечание: число сечений - 20, среда - Matlab, CPU - P4 2.4ГГц, ОЗУ - 512 MB

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

Четвертая глава посвящена исследованию и аппаратной реализации алгоритмов сегментации и построения 3-мерных изображения. С ростом производительности микросхем появилась возможность реализовывать на них сложные, трудоёмкие алгоритмы, такие как алгоритмы визуализации 3-мерных изображений, которые всё шире используются в науке и технике.

Традиционный алгоритм визуализации обрабатывает все кубики в 3-мерном пространстве. Однако, те кубики, которые надо визуализировать (которые пересекаются с поверхностью контура изображения), занимают только маленькую часть объёма. Большинство времени исполнения алгоритма затрачивается на обход кубиков, не пересекающихся с изоповерхностью. Например, для визуализации рис. 9.а) только нужно обходить кубики на линии контура на рис. 9.б).

а) б)

Рис. 9. Контур изображения

В связи с этим возникает необходимость упростить определение поверхности 3-мерного объекта. В данной главе для визуализации в 3-мерном массиве сохраняются только те кубики, значения яркости которых находятся между порогами (клетки серого цвета на рис. 9. б). Реализация предложенного алгоритма представляется следующими шагами:

  1. Инициализировать исходные данные и порог сегментации;
  2. Разделить 3-мерное изображение на разные части с использованием заданного порогового уровня сегментации;
  3. Создать новый 3-мерный массив, который содержит данные, подвергающиеся визуализации (один из органов);
  4. Выделить два 2-мерных массива из созданного нового трёхмерного массива и образовать один слой;
  5. Обходить элементы с ненулевым значением яркости в 2-мерных массивах и образовать кубики, которые состоят из 8 соответствующих точек (вершин) в двух массивах;
  6. Определить по значениям яркости вершин кубика, пересекает ли ячейку искомая поверхность. Если значения некоторых вершин более значения изоповерхности, то между ним существует пересечение, и эти вершины отмечаются, в противном случае они не пересекаются;
  7. Генерировать треугольники и вычислять их нормали;
  8. Повторять шаги 4-7 до тех пор, пока все слои не обработаны;
  9. Добавить модель освещения;
  10. Нарисовать все треугольники по принципам перспективной (центральной) проекции и модели освещения;

На рис. 10 представлены полученные по представленному алгоритму трёхмерные изображения контура человеческой головы после построения на разных направлениях. Разрешение изображений составляет 128128128.

Рис. 10. Изображения контура человеческой головы после 3-мерного построения (на двух разных направлениях)

После успешного моделирования приведен анализ скорости вычисления. В результате получено, что обработка одного кубика занимает 5 циклов (5 – максимальное число треугольников в одном кубике). Таким образом, для рассматриваемого трёхмерного изображения с разрешением 128128128 точек процесс визуализации при использовании ПЛИС с тактовой частотой 250МГц может выполниться примерно за 0,04 секунды (5127127127/(250106)=0.04). В таблице 3 приведены времена вычисления при аппаратной (в САПР Xilinx ISE на ПЛИС Virtex-4 SX) и программной (в среде Matlab и Visual C++) реализации.

Табл. 3. Анализ времени визуализации при аппаратной и программной реализации

Метод реализации

Количество тактов

Время вычисления, с.

Программный (Matlab)

4,31

Программный (Visual C++)

1,54

Аппаратный (Xilinx ISE ПЛИС Virtex-4)

51273

0,04

Примечание: CPU – P4 2.4 ГГц, ОЗУ - 512MB, fтакт=250MГц

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

Реализация более сложных, чем удалось в диссертации, алгоритмов обработки 3-мерных изображений на базе лишь ПЛИС неизбежно приводит к огромным трудностям. Идеальным вариантом является совместное использование FPGA, DSP и GPU (графический процессор). Типичная структура сложных систем для трёхмерных изображений представлена на рис. 11. FPGA используется для логики и связи с внешними устройствами, DSP – для высокопроизводительной обработки изображений и реализации сложных алгоритмов, GPU – для визуализации и воспроизведения трёхмерных изображений на экране монитора.

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

Приведённые в диссертационной работе исследования позволяют сформулировать требования к таким микросхемам и предложить их структуру. Во-первых, в микросхеме необходимо иметь память большого объема, например, для трехмерного изображения с разрешением 512512512 память должна не менее 16МБ (51251228, одновременно обрабатывать два слоя) и те блоки, которые наиболее используются в системе обработки 3-мерных изображений, например, такие, как блок вычисления тригонометрических функций. Во-вторых, в микросхеме должны храниться часто встречающиеся константные массивы, не занимающие большой объем, например таблицы ребер и треугольников в виде постоянного запоминающего устройства. Добавление этих компонентов дает возможность значительно ускорить процесс проектирования и облегчить труд разработчиков.

ЗАКЛЮЧЕНИЕ

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

В результате выполненной работы сделано следующее:

1. Разработан подход к построению 3-мерных вложенных геометрических объектов, заданных формой, размерами, координатами и плотностью материала, и медицинских изображений, заданных параллельными сечениями. Это позволяет решить проблему проведения диссертационных исследований без УЗ-приборов;

2. Разработана аппаратная реализация алгоритма R-интерполяции и алгоритма пространственного преобразования координат, что дает возможность выполнить операции в реальном масштабе времени;

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

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»