В работе рассматривается алгоритм синтеза трехмерных радиоголографических изображений. Оценена вычислительная сложность алгоритма. Проведено распараллеливание алгоритма для многоядерных процессоров и графических успорителей. Приводятся результаты численных экспериментов, дающие оценку производительности алгоритма в реальных задачах. Предлагается дальнейший путь повышения качества синтезируемых изображений.
Параллельные алгоритмы построения и обработки трехмерных радиоголографических изображений* В данной работе проводится оценка производительности параллельных вариантов алгоритма синтеза трехмерного изображения, с использованием ресурсов центрального и графического процессора, а также оценивается разрешающая способность локатора и предлагается способ ее повышения.
Рис. 1. Фотография (в центре) и трехмерные радиочастотные изображения человека без предметов (слева) и со скрытыми предметами (справа). 2. Алгоритм синтеза изображений передатчика (xk , yk ,zk ) .
Sk ( f ) F sk (t) .
Алгоритм синтеза изображений состоит из следующих этапов [
3. Выполняем фазирование для всего набора: Sk ( ) Sk ( ) e j0 ( ) , где 0 ( ) 2 ( f0 f / 2) . Вычислительная сложность этапа O(N K ) . 4. Для всех координат требуемого объема x, y,z выполняется накопление:
I (x, y, z) | Sk ( k ) | ,
K где k – суммарная задержка отраженного сигнала от точки пространства с координатами x, y, z с учетов возможного преломления на границе сред. Вычислительная сложность этапа составляет O(M K ) , где M X Y Z – общее количество вокселей синтезируемого изображения, X ,Y , Z – разрешение по каждому из измерений изображения.
Таким образом, общая вычислительная сложность алгоритма O(K (N log(N ) M )) .
Для достижения требуемых характеристик по разрешению синтезируемых изображений накладываются определенные ограничения на все компоненты формулы.
При использовании систем с последовательным зондированием возможно использование распараллеливания при обработке каждого отдельного сигнала на этапах вычисления БПФ и накопления для одновременного вычисления значений для различных координат объема, что
K уменьшает сложность до O( (N log(N ) M )).
T 3. Распараллеливание и результаты численных экспериментов При выполнении вычислений с многопоточной системой данные от каждого канала могут быть обработаны независимо от остальных, что, при одновременном выполнении T потоков, позволяет уменьшить сложность до того же значения. Но при этом в T раз увеличивается объемная сложность алгоритма, что обусловлено необходимость хранения различных копий данных для каждого потока.
Также возможны комбинации обоих подходов в зависимости от решаемой задачи. В данном случае был выполнен синтез изображения со следующими параметрами: размер изображения 100×100×300 в вокселях, длина набора сигналов биений K равнялась 2048, количество дискретов в сигнале взято 216.
При реализации обоих подходов были получены идентичные результаты. На рис. 2 представлены результаты при выполнении в 4 потока. Можно видеть, что время выполнения растет линейно с увеличением количества сигналов.
Рис. 2. Время выполнения при различных реализациях алгоритма выполнения в зависимости от количества сигналов Еще одним путем повышения производительности при реализации является использование различных оптимизаций, зависящих от выбранной архитектуры ЭВМ. Например, современные процессоры Intel поддерживают векторные инструкции, позволяющие существенно повысить производительность при использовании операций с плавающей точкой. Рис. 3. Время выполнения в зависимости от количества используемых потоков, количество сигналов
K=2048 Результаты выполнения алгоритма с автоматической оптимизацией под процессоры Intel Core i7, выполненной компилятором Intel C++ compiler 14.0, представлены на рис. 3 в виде зависимости времени выполнения от количества потоков. Распределение на потоки реализовано с использованием OpenMP. Количество сигналов K=2048.
Рис. 4. Время выполнения на видеоускорителе Nvidia GTX 780Ti.
Также алгоритм был реализован для выполнения на GPU с использованием технологии CUDA и проведено исследование эффективности с использованием видеокарты Nvidia GTX 780Ti, имеющей 2880 ядер CUDA и тактовую частоту 875МГц. На рис. 4 видно, что реализованная система позволяет получать изображение с частотой 15 кадров в секунду.
Измерения производительности произведены на ПК с процессором Intel Core i7 3610M с тактовой частотой 2.3ГГц с восемью потоками выполнения, с доступными 16 ГБ оперативной памяти. Параметры алгоритма: M=106, N=262144. Указанное время – минимальное среди тысячи замеров при одних условиях. В качестве реализации алгоритма БПФ использованы библиотеки FFTW и cuFFT. 4. Оценка разрешающей способности
Трехмерная аппаратная функция системы (изображение идеального точечного отражателя) характеризует пространственную разрешающую способность локатора. При этом ее диаметры по уровню 0.5 от максимума определяют возможность разрешения рядом расположенных отражателей. Боковые лепестки определяют возможность обнаружения слабых отражателей на фоне мощных.
Цель эксперимента состояла в оценке того, насколько далека форма реальной аппаратной функции от идеальной формы. Изображение идеальной аппаратной функции получено с помощью имитационной цифровой модели. Реальная аппаратная функция прибора оценивается с помощью небольшой металлической пластинки.
Параметры зондирования: апертура синтеза 1,3 х 1,2 м, всего 600 точек; девиация частоты ЛЧМ-сигнала 0,85 ГГц; центральная частота 2,163 ГГц.
На рис. 5 показаны результаты сравнения. Изображены поверхности, «натянутые» на разные уровни изображения. Сторона куба на рисунках равна 40 см. Показано, что поперечное и продольное разрешение реальной системы практически максимально при данных параметрах зондирования. Для заданных параметров реальная разрешающая способность в поперечном направлении составила 5,5 см, в продольном – 15 см. Идеальная разрешающая способность в поперечном направлении составит 4,8 см, в продольном – 7 см.
Рис. 5. Вид аппаратной функции идеальной (слева) и реальной (справа) системы
по различным уровням.
Уровень боковых лепестков и фоновой засветки существенно больше теоретического значения. Основные причины этого состоят в следующем: сигнал прямого прохождения и переотражения в приемо-передающем тракте; паразитная амплитудная модуляция сигнала биений и остаточная нелинейность частотной модуляции; статическая и динамическая ошибки позиционирования антенн. 5. Повышение разрешающей способности
Дальнейшее повышение качества изображений требует применения вторичной обработки
изображений. Для этого предлагается воспользоваться аппаратом решения обратных задач
восстановления изображений [
Относительно f задача является трехмерным интегральным уравнением Фредгольма
первого рода, и поэтому является сущеcтвенно некорректной задачей. Для ее решения
предполагается построить алгоритмы, использующие идеи итерационной регуляризации [
В рамках первого подхода, исходное уравнение регуляризуется, например, методом Тихонова:
A(u) (u u* ) f , где u* — начальное приближение искомой функции (изображения), f — правая часть уравнения (полученное изображение), g( , , ) f , — параметр регуляризации.
Для решения данного уравнения можно использовать регуляризованный метод
наискорейшего спуска [
S u k
2 2 A u k S u k S u k
S u k , 2 * где S u k A u k A u k f u k u* , A — производная Фреше оператора A , uk — приближенное регуляризованное решение (искомое изображение) на k ой итерации, k — демпфирующие множители.
Поскольку решение обратных задач восстановления трехмерных изображений большого разрешения потребует значительных объемов вычислений, будет актуальным применение мощных вычислителей, например, видеоускорителей или сопроцессоров. 6. Заключение
Проведен анализ вычислительной сложности алгоритма синтеза трехмерных радиоголографических изображений при последовательной и параллельной реализации. Проведено экспериментальное исследование возможностей повышения производительности алгоритма, использующих распараллеливание вычислений и использование специализированных инструкций процессора. Показана возможность применения видеоускорителей для достижения производительности, достаточной для синтеза изображений в реальном времени. Литература Parallel algorithms for synthesizing and processing
of 3D radio holographic images Yeltsin Ural Federal University1, Krasovskii Institute of Mathematics and Mechanics of Ural
Branch of the Russian Academy of Sciences2 This paper is devoted to the algorithm for synthesizing of 3D radio holographic images. Computational complexity of the algorithm is estimated. The algorithm was parallelized for multicore processors and GPUs. The numerical experiments estimating the algorithm performance for real applications were carried out. The further way to improve the quality of synthesized images is proposed.