Сравнительный анализ модификаций алгоритма покоординатного спуска в вероятностном методе восстановления изображений в компьютерной томографии

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

Сравнительный анализ модификаций алгоритма покоординатного спуска в вероятностном методе восстановления изображений в компьютерной томографии

Чуканов Вячеслав Сергеевич

Штурц Игорь Викторович

Санкт-Петербургский политехнический

университет Петра Великого

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

Ключевые слова: метод покоординатного спуска, компьютерная томография

COMPARATIVE ANALYSIS OF THE MODIFICATIONS OF THE COORDINATE-WISE DESCENT ALGORITHM IN A PROBABILISTIC METHOD FOR IMAGE RESTORATION IN COMPUTED TOMOGRAPHY

V.S. Chukanov, I.V. Starts

St. Petersburg Polytechnic University Peter Led the article deals with the coordinate-wise descent algorithm in the problem of three-dimensional reconstruction of images in computed tomography. The analysis of the so-called inhomogeneous updates voxels that guarantee the best convergence.

Keywords: coordinate-wise descent method, computed tomography.

Введение

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

Проблема заключается в том, что в современных компьютерных томографах реализованы алгоритмы, основанные на преобразованиях Фурье. Эти алгоритмы отличаются высокой скоростью работы, но при этом и высокой чувствительностью к шумам. Для уменьшения шумов приходится увеличивать дозу облучения. В то же время существуют алгоритмы, восстанавливающие изображение итеративно и требующие лишь 10-50% от обычной дозы облучения. Семейство таких алгоритмов называется вероятностным. Однако их применению препятствует гораздо большая вычислительная трудоемкость, приводящая к многочасовой задержке в получении результата сканирования. Возникают две задачи: построение наиболее быстро сходящегося алгоритма, т.е. алгоритма, который требует минимальное число итераций для получения результата, а также оптимизация алгоритма с учетом современного аппаратного обеспечения (графических процессоров) для получения наименьшего времени итерации.

Математическая модель

Компьютерный томограф представляет собой пару источник-детектор, описывающую циклическую траекторию вокруг тела пациента в процессе сканирования. Источник излучает рентгеновские кванты, которые, проходя сквозь тело, регистрируются элементами детектора. Детектор представляет собой прямоугольную «сетку» элементов, где каждый элемент способен улавливать рентгеновские кванты. Исследуемый объект представляется в виде воксельной сетки, где каждый воксел - это некий малый объем пространства, характеризуемый определенным коэффициентом поглощения излучения. Задача реконструкции изображения - это задача восстановления значений коэффициентов поглощения в каждом вокселе исследуемого объекта по данным с элементов детектора.

Будем использовать следующие обозначения:

- число квантов, генерируемых рентгеновской трубкой, - число квантов, попавших на детектор, - веса вокселов, - текущее приближение значения коэффициента поглощения в j-м вокселе (рис. 1). Необходимо отметить, что веса вокселов вводятся для того, чтобы модель процесса проекции была более правдоподобной: луч малой толщины пересекает не целиком воксел, а только некоторую его часть, и потому только эта часть воксела поглощает излучение. Если p - проекция, то вычисляется она как .

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

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

Рисунок 1 - Соотношение f, a, p и реконструируемого изображения

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

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

Методы оптимизации. Покоординатный спуск

Для вероятностных методов в качестве начального приближения, как правило, используется результат работы классического метода на базе преобразования Фурье.

Одним из методов с достаточно высокой скоростью сходимости является метод покоординатного спуска (iterative coordinate descent, ICD [2]). В ходе итерации производится поочередный обход вокселов, и для каждого воксела решается задача одномерной оптимизации. Этот метод можно отнести к семейству «жадных» алгоритмов, поскольку на каждом шаге (обновлении воксела) алгоритм пытается максимально уменьшить разницу между проекцией текущего изображения и данными сканирования.

Оригинальный ICD обновляет в ходе итерации каждый воксел ровно один раз. Одним из улучшений метода является применение идеи неоднородного обновления вокселов. Суть состоит в том, что разные вокселы изображения находятся на разном «расстоянии» от своих финальных значений. Показателем такого состояния можно считать абсолютную величину обновления воксела в ходе последней выполненной итерации. Разумеется, хранить подобную характеристику для каждого воксела было бы неэффективно с точки зрения памяти. Меньше памяти требуется для усредненной характеристики «линии вокселов» - множества вокселов с одними и теми же (x, y) координатами. Эту арактеристику линии вокселов будем называть VSC (voxel selection criterion):

Итерации в неоднородном ICD чередуются:

1. Выполняется итерация ICD. Рассчитываются VSC для линий вокселов.

2. Выбирается некоторая доля линий с максимальными значениями VSC (5%), производится их обновление. В процессе обновления VSC так же обновляется, и этот шаг повторяется определенное количество раз.

Неоднородный метод покоординатного спуска (NH-ICD [2]) показывает лучшую сходимость, чем оригинальный ICD, однако и этот результат может быть улучшен. Показано [2], что если линия вокселов имеет высокое значение VSC, то и соседние линии также с большой вероятностью имеют высокое значение VSC. Опираясь на это предположение, можно разбить множества линий вокселов по критерию четности x/y координаты, получив 4 подмножества. Для каждого подмножества:

1. Применяется обновление методом ICD, вычисляются VSC.

2. VSC интерполируются по всему изображению

3. Производится неоднородная часть итерации NH-ICD

После обхода всех подмножеств производится обработка методом NH-ICD. Этот метод носит название Interleaved NH-ICD [2]. Использование данных VSC позволяет фокусировать еще большее количество вычислений на вокселях, требующих большего числа обновлений.

Улучшение возможностей для распараллеливания ICD

Если неоднородные модификации ICD направлены на улучшение скорости сходимости, то отдельно стоит затронуть модификацию алгоритма, позволяющую добиться лучшей степени параллелизма. Самым эффективным способом распараллеливания ICD является параллельная обработка вокселов одной линии (Axial Block Coordinate Descent, ABCD [1]). Для осуществления этого строится замещающая квадратичная функция, касающаяся целевой функции в данной точке (текущие значения вокселов), но во всех остальных лежащая выше. Доказано [1], что эта модификация сходится к тому же решению, что и ICD, причем приблизительно с той же скоростью.

Мы использовали комбинацию ABCD и неоднородных модификаций для оценки сходимости и влияния неоднородных обновлений на качество изображения.

Результаты

Мы реализовали все описанные выше модификации ICD. Кроме того, мы реализовали обновление изображения только неоднородной частью Interleaved NH-ICD, чтобы оценить, до какой итерации требуются неоднородные обновления.

Рисунок 2 - График сходимости. Здесь INH-ABCD - Interleaved NH-ABCD; INH - Interleaved NH-ABCD, с постоянным неоднородным обновлением

Заключение

Мы изучили сходимость семейства вероятностных алгоритмов, основанных на методе покоординатного спуска. Наиболее выгодным с точки зрения соотношения скорость сходимости/вычислительная трудоемкость оказался Interleaved NH-ABCD. Этот метод фокусирует вычисления на тех областях изображения, которые требуют большего числа обновлений, и при этом обладает большим потенциалом для распараллеливания, обрабатывая параллельно все вокселы одной линии.

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

покоординатный спуск томография воксель

Список использованных источников

1. J. A. Fessler and D. Kim, “Axial block coordinate descent (ABCD) algorithm for X-ray CT image reconstruction”, Proceedings of the Fully 3D, pp. 262-265, 2011.

2. Z. Yu, J.-B. Thibault, C. A. Bouman, K. D. Sauer, and J. Hsieh, “Fast model-based x-ray CT reconstruction using spatially nonhomogeneous ICD optimization," IEEE Trans. Image Proc. 20(1), pp. 161-175, 2011

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