Preview

Вестник Концерна ВКО «Алмаз – Антей»

Расширенный поиск

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

Полный текст:

Аннотация

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

Для цитирования:


Коновальчик А.П. Применение суперкомпьютерных технологий для решения задачи выделения космических объектов в цифровом изображении. Вестник Концерна ВКО «Алмаз – Антей». 2015;(2):82-89.

For citation:


Konovalchik A.P. Application of supercomputer technologies for solving allocation of space objects in a digital image. Journal of «Almaz – Antey» Air and Defence Corporation. 2015;(2):82-89. (In Russ.)

Введение

В процессе развития и совершенствования системы воздушно-космической обороны стремительно возрастает сложность и вычис­лительная ёмкость алгоритмов обработки ин­формации о космических и баллистических объектах [1]. Это обусловлено:

  • повышением разрешающей способности радиолокационных и оптических средств воз­душно-космической обороны, необходимой частоты обновления информации, количества гипотетических целей;
  • увеличением сложности законов эволю­ции целевой обстановки.

Работа таких алгоритмов в режиме ре­ального времени требует их реализации на современных высокопроизводительных вы­числительных платформах с применением спе­циальных технологий программирования.

В настоящей работе рассматривается за­дача автоматического выделения в цифровом изображении перемещающихся за время экспо­зиции малоконтрастных космических объектов с неизвестными орбитами. Съемка проводится в таком режиме, что за время экспозиции при­нимаемый от звезды сигнал накапливается в одном или нескольких соседних пикселях изо­бражения. Сигнал от перемещающегося в пло­скости фотоприёмной матрицы космического объекта «размазывается» по многим пикселям изображения, может иметь малую контраст­ность, что затрудняет обнаружение объекта.

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

Исследования алгоритма обработки изо­бражения проводились на разработанном в ОАО «Концерн ПВО «Алмаз - Антей» ре­конфигурируемом проблемно-ориентирован­ном вычислительном комплексе (РПВС-К) «Орфей-К» (рис. 1) [3], который является ти­пичным представителем суперЭВМ с уско­рительными платами на базе программируемых логических интегральных схем (ПЛИС) (рис. 2).

 

Рис. 1. Реконфигурируемый проблемно­ориентированный вычислительный комплекс «Орфей-К»

 

 

Рис. 2. Структура суперЭВМ «Орфей-К»

 

Структура суперЭВМ «Орфей-К» являет­ся гибридной и включает (см. рис. 2):

а) универсальную компоненту, реализо­ванную как обычный вычислительный кластер из 16 специализированных универсальных вычислительных реконфигурируемых вычис­лительных блоков (СУРВБ) на основе двух процессоров Intel Xeon, соединённых высоко­скоростной сетью Infiniband;

б) специализированную компоненту, со­стоящую из 32 реконфигурируемых вычисли­тельных блоков (РВБ), попарно подключенных к СУРВБ по шине PCI Express; каждый РВБ включает 8 ПЛИС Xilinx XC6VSX475T.

Основные характеристики суперЭВМ «Орфей-К»:

число СУРВБ................................................................16

число процессорных ядер в решающем поле (Intel Xeoi

E5620 2,4 ГГц 4 ядра).................................................128

число ПЛИС на РВБ.......................................................8

число ПЛИС в решающем поле................................256

скорость чтения/записи в системе хранения данных

Мбайт/с.....................................................................~ 250

пропускная способность сети Infiniband, Гбайт/с 4

суммарный объём оперативной памяти в решающем

поле, Гбайт..................................................................192

емкость системы хранения данных, Тбайт.................12

пиковая производительность универсального процес­сора:

float (1ядро), Гфлопс..................................................... 19,2

double (1ядро), Гфлопс.................................................. 9,6

float (РПВС-К в целом), Тфлопс................................ 2,46

double (РПВС-К в целом), Тфлопс........................... 1,23

Постановка задачи

Известный алгоритм обработки изображения для выделения космических объектов осно­ван на замене задачи выделения протяжённых следов задачей обнаружения фрагментов фик­сированной длины с последующим их группи­рованием [3]. Фрагменты следов и звёзды об­наруживаются в скользящем по изображению прямоугольном пиксельном окне с классифи­кацией по признаку «неподвижный объект/ фрагмент следа объекта». Накопление сигна­лов вдоль гипотетических фрагментов следов проводится в пределах окна. Максимальное число наиболее правдоподобных объектов каж­дого типа ограничивается некоторой априори задаваемой константой. Число группируемых фрагментов при этом значительно меньше чис­ла группируемых отметок при традиционном подходе, основанном на пороговой обработке сигналов в пикселях.

Решение задачи

На вход алгоритма подаётся прямоугольное мозаичное изображение (16 бит серого) в виде матрицы размером NX (по горизонтали) на NY (по вертикали) целых чисел (16 бит без знака):

где NX, NY - размер входного изображения (фиксированные).

В пространственном прямоугольном пик­сельном окне размером WL× WL (WL - нечётное целое, фиксированное для каждой отдельно взятой реализации алгоритма) вокруг выбран­ного пикселя изображения выполняется оценка амплитуды сигнала, уровня фона, вычисление решающей статистики (максимума логарифма функции правдоподобия) и выбор оптималь­ной гипотезы, приводящей к максимуму функ­ционал (решающая статистика) [3]:

где k = 0...K - гипотезы;

K = 2· WL;

WL = 3, 5, 7, 9, 11;

ND - максимальное число обнаруживаемых фрагментов (фиксированное);

а - амплитуда сигнала;

b - амплитуда фона;

- матрицы опорных отметок обна­руживаемых космических объектов (шабло­нов) размером WL×WL для K = 2WL гипотез, k=0... K-1 (рассчитываются заранее для каж­дой отдельно взятой реализации алгоритма).

Оптимальная гипотеза k* для i, j-пикселя изображения Yij при расчете выражения (1) вы­бирается по следующим критериям:

где L*k - максимальное значение функционала Li,j (k, a, b), полученное нахождением максими­зирующих правую часть выражения (1) значе­ний a = ak* и b = bk*.

Значения afi и bk* для каждого ij-пикселя изображения Yij вычисляются по формулам:

Выражение для Ck с учетом значений ak* и bk* может быть представлено в виде:

 

Из всего набора гипотез, получивших по­ложительную оценку амплитуды сигнала a*k , и гипотезы отсутствия полезного сигнала (k = 0) по вышеприведенной формуле выбирается ги­потеза с максимальной величиной L*k.

В результате такого попиксельного вы­бора оптимального значения формируются две матрицы промежуточных значений размером (NX-WL + 1)х(АУ - WL + 1). Первая из них содержит номера выбранных гипотез k*, вто­рая - величины функционала Lk* для каждого пикселя, соответствующие выбранным k*:

где n, m = 0...(NX - WL + 1).

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

На основе массива величин Λ формиру­ется неупорядоченный список. Полученный список сортируется по убыванию. В качестве порогового значения TD выбирается (ND+1)-й элемент упорядоченного списка (ND-элемент при индексации от 0).

Отсев подпороговых значений

Для каждого элемента матрицы Λ производит­ся сравнение:

Λi,j > TD.

Если это условие не выполняется, соот­ветствующий элемент матрицы k зануляется.

Операция гарантирует, что число обнару­женных отметок не превысит ND.

Результат пороговой обработки

Результат обработки формируется из прошед­шей пороговую обработку матрицы k дополне­нием до матрицы размером NX на NY нулевыми столбцами и строками по (WL-1)/2 с каждой из четырех сторон.

Минимизация объёма выходных данных

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

Реализация на кристалле адаптивной по­роговой обработки позволяет отказаться от вы­вода с кристалла ПЛИС матрицы Λ, что даже в грубой реализации вывода массива k (то есть в полном его объёме) преуменьшает объём вы­ходных данных по сравнению с входом.

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

Фрагментация кадра

На первом этапе обработки вычисления, вы­полняемые в прямоугольных пиксельных ок­нах для двух соседних пикселей изображе­ния, взаимно независимы. Пересекаются лишь входные массивы данных, и фрагментация не­избежно приведёт к дублированию входных данных на границах окон. Объём дублируемых данных приблизительно (WL-1)∙N элементов для квадратного фрагмента размером N×N, что соотносится с площадью фрагмента как (WL-1)/N.

Второй этап обработки связывает резуль­таты первого этапа процедурой сортировки. Однако в силу физических особенностей ре­шаемой задачи в определённых пределах фрагментация допускается. За грубую оценку ми­нимального размера фрагмента можно выбрать 32×32. При допущении концентрации ложных отметок в 1/16 от площади фрагмента такой выбор позволит всегда обнаруживать след «яр­кого» объекта целиком. В целях же обнаруже­ния «тусклых» объектов размер фрагмента сто­ит увеличить хотя бы до 64×64. Одновременно это позволит обнаруживать более одного объ­екта во фрагменте кадра.

Таким образом, имеет смысл произво­дить фрагментирование кадра дважды: на вход кристалла ПЛИС подавать фрагменты боль­шего размера (в целях сокращения накладных расходов дублирования данных), а пороговую обработку производить над фрагментами мень­шего размера.

Первичная обработка двух различных кадров выполняется независимо. Это автома­тически означает, что производительность си­стемы возрастает с увеличением количества задействованных вычислительных узлов: для каждого кадра - отдельные узлы. Такой подход не уменьшает отклик системы на обработку отдельного кадра, но общая производитель­ность растёт.

Анализ вычислительных особенностей ал­горитма

Упрощенная блок-схема реализации алгоритма на суперЭВМ может быть разбита на четыре этапа:

  • загрузка изображения;
  • осуществление вычислений, не завися­щих от изображения;
  • обработка изображения;
  • адаптивная обработка.

Проведя анализ каждого из этапов, мож­но сделать вывод, что алгоритм удовлетворяет основным требованиям, предъявляемым для реализации на ПЛИС, а именно:

  • наличие в алгоритме параллельных ком­пактных подалгоритмов, в которых сосредо­точена основная вычислительная сложность алгоритма;
  • невысокая ёмкостная сложность подал- горитмов;
  • возможность распараллеливания реали­зуемого фрагмента алгоритма и достаточный уровень потенциального параллелизма;
  • отсутствие или незначительное число ветвлений в алгоритме;
  • высокая вычислительная интенсивность реализуемого подалгоритма.

Оценка числа операций

Основная трудоёмкость приходится на блок об­работки изображения. Общее число операций - (NX-WL)x(NY-WL)xK.

Оценим количество операций на 1 байт данных (входных и выходных) для всех ша­блонов.

Оценка объёмов памяти

Входные данные составляют ~25% (250 тыс. пикселей) от суммарного объёма входных и выходных данных.

Объем памяти под шаблоны K × WL2 слов. Для 100 шаблонов 11x11 потребуется 12 КБайт при однобайтовом элементе, 24 КБайт - при двухбайтовом.

При наличии в ПЛИС XC6 VSX475T ~ 4 Мбайт блочной памяти возможно исполь­зование до 0,5 Мбайт для обрабатываемого изображения, т. е. 1 ПЛИС может обрабатывать фрагменты изображения до 512×512 пикселей, а для обработки изображения 4008×2672 пик­селей потребуется от 64 ПЛИС (т. е. 8 РВБ) [2].

Оценка производительности

При задействовании всей суперЭВМ «Орфей-К» и пропорциональном уменьшении размеров фрагмента (в 4 раза) скорость обра­ботки может достигнуть 340-600 фрагментов на ПЛИС.

Устоявшаяся скорость обмена данными с 1 ПЛИС (при работе со всеми 16 ПЛИС) со­ставляет ~ 80 Мбайт/с в каждую сторону. По­скольку выходные данные в 7 раз превышают входные, именно это является ограничиваю­щим фактором.

С одной ПЛИС можно считывать до ~6×106 данных для пикселей изображений и загружать данные для ~42×106 пикселей, т. е. обрабатывать ~23 фрагмента изображений в секунду (если считать только загрузку, то 160). При уменьшении фрагмента и увеличе­нии числа задействованных ПЛИС пропорци­онально возрастает достижимая скорость обмена и обработки фрагментов соответственно. На «Орфей-К» в полной конфигурации (256 ПЛИС) соответственно возможна обработ­ка со скоростью в 4 раза большей (92 и 640 фрагментов/с на ПЛИС соответственно).

Пропускная способность системы хра­нения данных позволяет извлекать из неё в секунду не более 10-15 изображений разме­ром 20-32 Мбайт и соответственно сохранять данные обработки не более 2-3 изображений.

Пропускная способность сети Infiniband 32 Гбит/с позволяет загружать из сервера за­грузки, управления и мониторинга (СЗУМ) данные не более чем 128-200 изображений в секунду и сохранять результаты обработки не более чем 18-30 изображений в секунду.

При сокращении объемов возвращаемой информации скорость обработки может быть увеличена вплоть до значений, лимитируемых производительностью ПЛИС: порядка 100 изо­бражений в секунду для 100 шаблонов 11×11 или 15×15.

Декомпозиция задачи и оценка возможности реализации на ПЛИС

Параллельность выполнения задачи естествен­ным образом достигается разбиением исходно­го изображения на фрагменты. При обработ­ке на суперкомпьютере изображение делится между ПЛИС, а внутри ПЛИС - между логиче­скими вычислительными устройствами (ВУ), работающими параллельно. При проведении разбиения необходимо обеспечить перекрытие на ширину шаблона гипотезы максимального размера.

Внутри ПЛИС массив входного изо­бражения (ввиду большого объёма) должен храниться в блоке памяти (BRAM), который позволяет хранить минимально 210 точек изо­бражения (например, квадрат размером 32×32).

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

Так как протокол обмена данными с BRAM последовательный, то для ВУ предпо­лагается естественным следующий порядок работы: для каждой точки последовательно выполнять сличение квадрата изображения с центром в данной точке с шаблоном из списка; далее в одном блоке ВУ выполняются вычис­ления, требующие многократного чтения из памяти (это суммы SY и SYF), а во втором - вы­числения, не требующие обращений к памяти, т. е. досчитывать функционал L(k, i, j). Такая организация вычислений позволяет блокам работать параллельно (с разными шаблонами).

Время обработки одной пары «пиксел- шаблон» в первом блоке определяется време­нем вычисления суммы SYF (более простая сумма SY вычисляется попутно). При считы­вании из памяти по одному элементу массивов изображения и шаблонов сумма вычисляется за WL2 тактов. Время обработки пары «точка - шаблон» во втором блоке можно, при распа­раллеливании процесса, свести к 9-10 тактам (минимальной длине периода работы первого блока). Тогда время обработки в ВУ факти­чески будет определяться временем работы первого блока.

Объем ВУ не менее двух 16-Кбит BRAM для хранения || Yi,j || (поскольку к одному фраг­менту изображения может обращаться одно­временно до четырёх ВУ, а элементы блочной памяти имеют 2 порта; иначе можно хранить в одном ВУ фрагмент, охватывающий все необ­ходимые для анализа точки; в данном случае, его размер 42×42); один блок памяти для хра­нения результатов (k, Λ); несколько (не более 15, зависит от реализации) DSP-блоков для вы­полнения умножений и делений.

Дальнейшие вычисления в ПЛИС сво­дятся к отбору результатов с наибольшими значениями. Для каждого фрагмента размером 32×32 достаточно выбрать около 10 наилучших результатов: это выполняется на фоне осталь­ной обработки посредством вставки очередно­го значения в 10-элементный список и требует нескольких тактов.

Окончательно списки, выработанные раз­личными ВУ, должны быть объединены в об­щий список из примерно 50 элементов. При та­кой реализации в одной ПЛИС Virtex6-475SXT можно разместить не менее 128 ВУ. При рабо­чей частоте 100 МГц время обработки фраг­мента размером 32×32 на одном ВУ и при вре­мени обработки всеми (128) ВУ изображения размером 217 точек оценивается как ~ 0,06 с.

Таким образом, обработка изображения размером 225 точек за 0,1 с достижима на ком­плексе из 256 ПЛИС.

Структурная схема элементарного канала обработки в ПЛИС

Элементарный канал обработки выполняет подсчёт функционала (1) для небольшого фраг­мента изображения (ориентировочно 32*32 точки).

Структурная схема канала обработки в ПЛИС приведена на рис. 3.

 

Рис. 3. Структурная схема канала обработки в ПЛИС

 

Реализация алгоритма на архитектуре «Орфей-К» состоит из следующих этапов:

  • рассылка частей изображения по вычис­лительным узлам;
  • «нарезка» изображения на фрагменты; загрузка фрагментов в ПЛИС; обработка фрагмента в ПЛИС; выгрузка результатов обработки из ПЛИС;
  • сборка результатов, преобразование фор­матов и сортировка;
  • сборка частей результата.

Реализация алгоритма на архитектуре «Орфей-К» позволила обработать изображение размером 10 мегапикселей за 35 мс, что более чем в 3900 раз быстрее, чем на универсальном процессоре.

На рис. 4 представлены исходное (а) и обработанное (б) изображения с выделен­ным треком (следом) реального космического объекта. Изображения получены с телескопа VT-53 с апертурой 12 см (ПАО «МАК «Вым­пел»), размер изображения 4008×2672 пиксе­лей.

 

Рис. 4. Исходное (а) и обработанное (б) изображения с выделенным треком (следом) реального космического объекта

 

Таким образом, на суперЭВМ «Орфей-К» целесообразно решать задачи с высокой вы­числительной сложностью, которые за не­обходимое время не могут быть решены на автоматизированном рабочем месте на базе современной ПЭВМ. В качестве ориентира мо­жет быть принят уровень в 27×1015 операций, что соответствует более 16 ч счётной работы на современной ПЭВМ.

Выводы

  1. Проблема выделения в цифровом изобра­жении космических объектов с заданным ка­чеством является вычислительно трудоёмкой задачей и требует для решения в режиме ре­ального времени применения специализиро­ванных вычислителей.
  2. Функциональный параллелизм на верхнем структурном уровне рассматривае­мого алгоритма обеспечивает совмещение во времени вычислений в ПЛИС с вычислениями в универсальных процессорах и с обменами данными, а наличие в подалгоритмах функцио­нального параллелизма - возможность органи­зации макроконвейерной обработки в ПЛИС. Это позволяет реализовать алгоритм автома­тического обнаружения в 10-мегапиксельном цифровом изображении перемещающихся за время экспозиции малоконтрастных косми­ческих объектов с неизвестными орбитами за 35 мс, что приблизительно в 3900 раз быстрее, чем на универсальном процессоре.
  3. Специализированный вычислительный комплекс «Орфей-К» на базе ПЛИС обеспечи­вает реализацию рассмотренного алгоритма в режиме реального времени и может быть ис­пользован в качестве базового вычислителя для перспективных оптических средств мони­торинга космического пространства Минобо­роны России, Роскосмоса и др.

Список литературы

1. Промежуточный научно-технический отчет. НИЭР «КИМС-Вымпел-2014». М.: ОАО «МАК «Вымпел», 2014. 435 с. Инв. 2657.

2. Научно-технический отчет. ОКР «Орфей-К». М.: ОАО «Концерн ПВО «Алмаз – Антей», 2011. 889 с. Инв. 91-214-К.

3. Колесса А. Е., Репин В. Г. Робастный адаптивный алгоритм выделения отметок от целей в цифровом изображении // Космические информационно-управляющие системы. 2009. Вып. 3. С. 203–210.


Об авторе

А.  П. Коновальчик
ОАО «Концерн ПВО «Алмаз – Антей»
Россия

Коновальчик Артем Павлович – советник генерального директора

Область научных интересов: суперкомпьютерные технологии, цифровая обработка сигналов.

г. Москва



Для цитирования:


Коновальчик А.П. Применение суперкомпьютерных технологий для решения задачи выделения космических объектов в цифровом изображении. Вестник Концерна ВКО «Алмаз – Антей». 2015;(2):82-89.

For citation:


Konovalchik A.P. Application of supercomputer technologies for solving allocation of space objects in a digital image. Journal of «Almaz – Antey» Air and Defence Corporation. 2015;(2):82-89. (In Russ.)

Просмотров: 38


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2542-0542 (Print)