Рассмотрена проблема создания параллельных алгоритмов 3D реконструкции внутренних органов по данным томографии на основе метода активного контура. Идея декомпозиции вычислений основана на возможности обхода последовательности слоев томограммы сразу в двух направлениях от стартового слоя и использовании нескольких стартовых слоев, в которых начальное положение контура генерируется на основе опорной геометрической модели органа. На основе библиотеки ITK реализованы параллельные алгоритмы сегментации почек Первый вариант распараллеливания дал для двух потоков ускорение порядка 1.6, второй - заметный рост эффективности с ростом числа точек в контуре, но в пределах 3.2 раза для 8 потоков CPU. Планируется полный перенос алгоритма на GPU. Ключевые слова: трехмерная реконструкция, 3D реконструкция, сегментация, томография, метод активного контура, опорная геометрическая модель.
Параллельный алгоритм 3D реконструкции внутренних органов по данным томографии на основе метода
активного контура таким образом рельеф заполнять водой, то образуются сегменты-бассейны различные по числу и площади в зависимости от уровня воды. При разрезании изображения в целях распараллеливания возникает трудоемкий этап сшивки результата. Работа по оптимизации разрезания и сшивки продолжается [7]. Алгоритм чувствителен к шуму на изображении, что может приводить к большому количеству полученных областей.
Алгоритм активного контура впервые предложен в работе Касса и Уиткена [1]. Возможности
его использования в медицине широко исследованы для всех внутренних органов [12], в том
числе: сердца[4,5], кишечника[3], головного мозга [10], глаза [
Вопрос о возможных подходах к распараллеливанию данного алгоритма в задачах медицинской сегментации заслуживает отдельного рассмотрения.
Работа классического алгоритма строится на минимизации энергии контура. Активным контуром называется деформируемый контур, состоящий из фиксированного числа n точек в двумерном пространстве:
= { 1, … , }, = ( , ), = {1, … , } Контур параметризован по параметру , изменяющемуся от 0 до 1. Все точки контура перемещаются по изображению, обеспечивая при этом минимизацию критерия в виде = ∫ ( ( )) + ( ( )) Внутренняя энергия контура заставляет контур сжиматься и приобретать более сглаженные формы. Она позволяет отбросить заведомо некорректные решения.
1 ( ( )) = 2 ( | ′( )|2 + | ′′( )|2) Параметр изменяет вес модуля первой производной, позволяя увеличить или уменьшить скорость роста размера активного контура. Увеличение параметра позволяет контуру охватывать более острые углы. Внешняя энергия ответственна за нахождение границ на изображении. Для минимизации функционала используется уравнение Эйлера-Лагранжа. После преобразований получится следующее уравнение:
′′( ) − ′′′′( ) − ∇ ( ( )) = 0, где ∇ (градиент внешней энергии) фактически является силой. Решение уравнения осуществляется методом градиентного спуска. Активный контур считается функцией времени, а 0 в правой части заменяется на частную производную от по времени.
В итоге система подынтегральных энергий и множество параметров позволяет настроить алгоритм под контур изображения на томограмме практически любого органа человека. Но и после установки хорошо подобранных текущих параметров, остается очень важным условием сходимости наличие хорошего начального приближения контура змейки.
Для одного контура этот метод является сугубо последовательным. Однако, применяя метод к соседним слоям томограммы мы можем, хоть и также последовательно, но обеспечить очень высокую скорость сходимости контура текущего слоя за счет его начального приближения контуром предшествующего слоя.
Опираясь на указанные свойства, предлагается решать проблему распараллеливания метода следующими способами:
1) после построения контура для некоторого слоя, процесс сегментации соседних слоев может быть разбит на два независимых потока: для слоев, лежащих выше текущего и ниже текущего;
2) число стартовых слоев может быть произвольным образом увеличено, благодаря построению начального приближения в каждом стартовом слое: А) лучевыми методами на графическом процессоре в качестве препроцессинга; Б) по опорной 3D модели органа, предварительно масштабированной и ориентированной в пространстве по нескольким опорным точкам органа.
Рассмотрим примеры таких параллельных алгоритмов, реализованных на примере задачи сегментации почек методом активного контура. В данном случае мы будем активно использовать предварительную информацию о локализации почек в поясничной области по бокам от двух последних грудных и двух первых поясничных позвонков. 2.1 Метод сегментации, работающий на основе входного контура Последовательный алгоритм работает следующим образом: 1. Пользователь указывает слои, являющиеся верхней и нижней границей сегментируемого органа; 2. Пользователь задает приближенный контур сегментируемого органа в текущем слое. 3. Алгоритм активного контура уточняет контур в текущем слое; 4. Расположенный выше слой копирует контур, вычисленный на предыдущем слое, и уточняет на своем слое.
5. Когда алгоритм обрабатывает все слои, расположенные выше стартового слоя, аналогичные действия выполняются для слоев, расположенных ниже начального.
Параллельный алгоритм работает следующим образом: 1. Шаги 1-3 последовательного алгоритма 2. Программа разделяется на два потока работающих одновременно; Первый поток обрабатывает слои, расположенные выше стартового слоя. Он вычисляет контур на текущем слое на основании контура, вычисленного на слое ниже. Второй поток обрабатывает слои, расположенные ниже стартового слоя. Он вычисляет контур на текущем слое на основании контура, вычисленного на слое выше. 3. Алгоритм заканчивает работу, когда дойдет до слоя, помеченного пользователем как граничный для органа. 2.2 Метод сегментации, работающий на основе лучевого препроцессинга или опорной модели
По данным томограммы определяется локализация сегментов позвоночника, соответствующих расположению почек. Производится трассировка 5-10 лучами области правой (левой) тени позвоночника, определяющая точки, принадлежащие контуру почки (плотность почки заметно выше плотности окружающих тканей. На полученных точках строится начальное приближение контура (рис.1, левый). Алгоритм активного контура параллельно уточняет контур в каждом слое (рис.1, правый).
В случае использования параметризованной 3D модели подобным же препроцессингом устанавливается локализация модели относительно позвоночника пациента. Затем производится преобразование опорной модели под данные пациента и вычисляются сечения опорной модели слоями томограммы. Рис.1 Препроцессинг начального приближения контура почки по томограмме и последующее уточнение контура методом активного контура в каждом из слоев параллельно. 3. Вычислительный эксперимент
Программная реализация метода активного контура разработана при помощи фреймворка Insight Segmentation and Registration Toolkit (ITK). Из фреймворка ITK были использованы функции чтения DICOM файлов, нахождения градиента, работы с векторами и матрицами.
Для сравнения скоростных характеристик алгоритмов были использованы данные КТ томографии, представляющие собой двумерные слои плотностей размером 512 x 512 пикселей. Сегментирование проводилось на 291 слое томограммы.
Сегментирование проводилось на CPU Intel® Core™ i7-4710HQ CPU (1.50GHZ, 4 cores, 8 threads) с 16 Gb памяти DDR3.
Тестирование проводилось для контуров, состоящих из различного количества точек, чтобы проверить масштабируемость алгоритма; использовалась компьютерная томограмма брюшной полости, в которой на 291 слое присутствуют сегментируемые сечения почки.
В таблице представлено время работы метода, работающего на основе одного входного контура. Таблица 1. Время работы алгоритма на основе входного контура последовательная версия, сек.
параллельная вер
сия, сек.
В среднем параллельный алгоритм, работающий в 2 потоках, оказался быстрее последовательной реализации в 1,67 раз, а при работе в 4 потока среднее ускорение достигло 2,50 раз. При параллельной работе в 8 потоков наблюдается незначительное ускорение в связи с тем, что Core i7-4710HQ является четырехъядерным процессором с технологией Hyper-threading.
Качество реконструкции контура алгоритмом по заданному начальному приближению представлено на рисунке ниже. При довольно грубом начальном контуре получено качественное приближение истинного контура почки. Рис. 2. Результат обработки контура почки (слева направо: приближенный контур; уточненный контур; контур, уточненный на соседнем слое). 4. Заключение
В работе рассмотрена проблема создания параллельных алгоритмов 3D реконструкции внутренних органов по данным томографии. Предложены подходы к построению параллельных вариантов использования метода активного контура. Первый вариант позволяет распараллелить процесс на 2 потока обработки слоев томограммы вверх и вниз от среднего слоя, или на 4 потока в случае симметричных органов. Второй вариант основан на быстром препроцессинге для всех или существенной части слоев томограммы (стартовых слоев), который позволяет построить грубый полигональный контур органа. В этом случае число параллельных потоков может быть равным числу стартовых слоев. При помощи фреймворка ITK созданы последовательная реализация, а также параллельная реализация алгоритма активного контура - «Snakes», с помощью которого было произведено сегментирование почки по томограмме. Алгоритм активного контура показал хорошие результаты сегментации компьютерной томограммы, обладающей когерентностью изображений соседних слоев.
Первый вариант распараллеливания дал в среднем для двух потоков ускорение порядка 1.6. Второй вариант распараллеливания показал заметный рост эффективности распараллеливания с ростом числа точек в активном контуре, но для 8 потоков CPU ограничился ускорением в 3.2 раза. Алгоритм включен в ПО для медицинских исследований. Планируется перенос алгоритма полностью на GPU. Литература 2. Jinhui Lan, Yiliang Zeng. Multi-threshold image segmentation using maximum fuzzy entropy based on a new 2D histogram // Int. Journal for Light and Electron Optics. 2013. Vol. 124, Issue 18, P. 3756-3760. 12. Laurent Massoptier, Sergio Casciaro. A new fully automatic and robust algorithm for fast segmentation of liver tissue and tumors from CT scans. // European Journal of Radiology. 2008. Vol. 18. P. 1658 - 1665 A parallel algorithm for 3D reconstruction of internal organs according to imaging based on the active contour model E.P. Vasil'ev, A.A. Belokamenskaja, M.M. Novozhilov, V.E. Turlapov
Lobachevsky State University of Nizhni Novgorod In this paper we consider the problem of building parallel methods for three-dimensional human organs’ geometrical reconstruction based on the active contour method. The idea of computing decomposition is based on opportunity to visit all layers in both directions from the starting layer and use several starting layers that have initial contours generated from the reference body geometrical model. Using ITK library we have implemented parallel kidney segmentation algorithms. The first parallel version gave acceleration of about 1.6 for 2 threads on CPU, and the second - a significant increase in efficiency with an increase in the number of points in the contour, but in the range 3.2 times for 8 threads on CPU. We are planning to transfer the algorithm on the GPU. 2. Jinhui Lan, Yiliang Zeng. Multi-threshold image segmentation using maximum fuzzy entropy based on a new 2D histogram // Int. Journal for Light and Electron Optics. 2013. Vol. 124, Issue 18, P. 3756-3760.