GPGPU ACCELERATION OF PROFILE CREATION FOR THREE-DIMENSIONAL VECTOR VIDEO

Abstract

The paper discusses optimization of method for determining the parameters of three dimensional vector video by implementing it for graphic processor unit. Performance of the method is estimated in comparison to the computation on general-purpose processor.

Full Text

Введение При разработке системы воспроизведения трехмерного векторного видео важной задачей является составление профилей, с помощью которых осуществляется модификация параметров шейдерных программ [1]. Задача ресурсоемка, и вычисление результата не может быть осуществлено в реальном времени во время работы приложения, для которого составляется профиль. Самым длительным этапом является вычисление метрики. Для ускорения работы алгоритма предлагается перенести ее вычисление на графический процессор (GPU). Метод составления профилей Метод автоматизированного составления профиля основан на сравнении изображений, получаемых с исходными параметрами шейдеров и после применения шейдеров с модифицированными параметрами. Для каждой шейдерной программы необходимо найти правильные типы значений, передаваемых в ее параметры. Для реализации стереоскопических эффектов важными являются параметры, содержащие проекционные матрицы [3]. Тем самым задача сводится к поиску типа матриц среди параметров шейдерной программы. Поиск типов параметров в методе осуществляется путем их перебора для каждого отдельного параметра. Предположение о правильности выбранного типа проверяется путем оценки схожести изображений, получаемых при визуализации кадра из видеопотока, без модификации параметров и с модификацией параметров согласно сделанному предположению об их типе. Выбранный кадр V из исходного видеопотока модифицируется с помощью преобразования T(V, S), которое изменяет множество параметров S шейдерных программ, относительно которых было сделано предположение о соответствии их определенному типу. Исходный кадр V и модифицированный кадр V проходят процесс растеризации R(V), результатом которого являются два изображения I и I соответственно. Изображения представляют собой функцию яркости в заданной точке I = f (x, y). Они сравниваются с помощью некоторой метрики. Результатом применения этой метрики является множество D, состоящее из двух интегральных величин, которое передается в функцию принятия решения A(D): D = {DB,DS}, (1) / ч fl, DB<bmnDr>sm ; A(d) = \ в т s т (2) V ' [0, DB>bmKjDs<sm, К ’ где bm и Sm - граничные значения компонент метрики. Алгоритм вычисления метрики для двух изображений осуществляет обработку исходных данных в несколько шагов. Под исходными данными подразумеваются два изображения: получаемое при исходных параметрах визуализации 1о и получаемое при модифицированных параметрах визуализации 1т. Из исходных изображений методом рассеивания рассчитываются цветовые гистограммы H(/) и H(Im). Первичная оценка расстояния между изображениями выполняется с помощью расстояния Бхаттачарья DB(Ho, Hm). Метрика уточняется с помощью сравнения множеств контрольных точек на исходных изображениях. Множества контрольных точек Po и Pm, получаемые из изображений Io и Im соответственно, используются для вычисления расстояния DS(Po, Pm). Для обнаружения точек используется метод SURF, реализация которого также доступна для GPU [3-4]. «Инфокоммуникационные технологии» Том 11, № 3, 2013 88 Цыганов А.А. GPGPU реализация Архитектура современных графических адаптеров спроектирована для осуществления векторных операций с данными в виде многомерных массивов. Она позволяет достичь высокой скорости работы с памятью при использовании векторных SIMD процессоров, обладающих независимыми L1 и L2 кэшами. По сравнению с процессором общего назначения GPU имеет меньшее количество ступеней конвейеров и меньший объем кэша. Обмен данными между видеопамятью и памятью общего назначения осуществляется через PCI-E 16 шину. Выборка данных в кэш осуществляется по 256-битной шине. В результате эффективность научных алгоритмов на GPU зависит от эффективности использования видеопамяти и кэша [7]. Основными задачами GPU реализации метода являются минимизация количества операций обмена данными между видеопамятью и памятью общего назначения. Коммуникации между центральным процессором и графическим ядром негативно влияют на производительность [5-6]. Для их снижения все данные, используемые различными этапами алгоритма, однократно загружаются в видеопамять [7]. Результат работы алгоритма также остается в видеопамяти и доступен следующим этапам. Суть разрабатываемого метода заключается в эффективном использовании кэш-памяти видеоадаптера и равномерной загрузке ядер потокового графического процессора. Передача ресурсов между этапами алгоритма осуществляется через видеопамять, что ускоряет их обработку с помощью GPU (см. рис. 1). Общая память Видеопамять 4 H(I0),H(Im) I Db(I0> Im) £ V Db(I0, Ui) 4 P P roj Jrm Ds(P о,Р m) ç V -Ds(P0,Pm) Рис. 1. Обмен данными между общей памятью и видеопамятью Изображения Io и Im загружаются в видеопамять для обработки. На их основе вычисляются гистограммы, используемые для расчета первой компоненты метрики с помощью расстояния Бхаттачарья. Те же исходные изображения используются алгоритмом SURF для получения множеств ключевых точек, на основе которых рассчитывается вторая компонента метрики. Обратно в общую память выгружаются лишь рассчитанные компоненты метрики. Их размер крайне мал, а чтение видеопамяти не прерывает выполнение процессов вычисления на GPU, что приводит к высокой эффективности параллельных вычислений. Вычисление гистограмм Вычисление компоненты метрики DB выполняется с помощью гистограмм H(Io) и H(IS) соответствующих изображений. Расчет гистограмм на GPU может быть выполнен как с использованием классических шейдерных программ, так и с использованием технологии CUDA для вычислений общего назначения на графическом процессоре. Использование технологии CUDA описано в [8-9]. Эти алгоритмы обеспечивают более высокую производительность, чем те, что основаны на использовании обычных средств графических программных интерфейсов, как это показано в [10]. В качестве примера второго подхода можно привести [2]. Так как основной задачей метода является ускорение расчета метрики, то наиболее подходящими являются методы на основе CUDA. В частности, метод Подложнюка реализован в CUDA SDK. Метод кэш эффективен и не содержит этапов выгрузки данных в общую память, что позволяет его интегрировать в процесс вычисления компонент метрики. В этом методе исходные данные разделяются на блоки между исполняемыми на GPU потоками. Результат обработки данных каждым потоком сохраняется в индивидуальной гистограмме. В финальном проходе все гистограммы, созданные разными потоками, объединяются в одну. Для эффективного использования общей памяти потоков каждая индивидуальная гистограмма создается для группы потоков, называемой тросом. Это позволяет хранить в памяти гистограммы большего объема, вплоть до 6 килобайт на аппаратной архитектуре G80. На основе полученных гистограмм вычисляется расстояние Бхаттачарья для двух статистических множеств. Оно выражается формулой «Инфокоммуникационные технологии» Том 11, № 3, 2013 Цыганов А. А. 89 (3) !=0 где n - количество элементов гистограммы. Вычисление суммы произведений элементов гистограмм может быть осуществлено с помощью свертки массивов исходных данных на GPU. Предлагается использование оптимизированного метода параллельной свертки на CUDA, описанного в [12]. Поиск ключевых точек Второй компонент метрики DS рассчитывается с использованием алгоритма SURF [13]. С его помощью осуществляется поиск двух множеств ключевых точек P и P’, имеющихся на оригинальном и модифицированном кадрах соответственно. Значение компоненты определяется следующим выражением: Ds = \Р U Р'\ (4) SURF является одним из самых распространенных и эффективных алгоритмов поиска ключевых точек изображений. Он применяется в системах автоматического распознавания и слежения за объектами, системах видеорегистрации, совмещения панорамных изображений и во многих других областях компьютерного зрения. Алгоритм может обрабатывать изображения в HD-разрешении со скоростью более 30 кадров в сек. Обнаружение ключевых точек в SURF осуществляется с помощью аппроксимации определителя матрицы Гессе. Аппроксимация выполняется наложением блочных фильтров на изображение. Это позволяет эффективно использовать интегральное представление изображения II, которое определяется как iüx,j<,y Il{x,y)= £/(,-,у). i=0,j=0 (5) Вычисление интегрального представления на GPU является самым длительным этапом работы алгоритма SURF и может быть осуществлено с помощью алгоритма пирамиды моментов, как это описано в [4]. Само построение интегрального изображения является задачей префиксной суммы. Алгоритм пирамиды моментов предлагает решение этой задачи на GPU в два этапа. На первом этапе осуществляется проход снизу вверх, в ходе которого строится пирамида изображений, каждое из которых разбивается на четыре вдвое меньше по ширине и высоте, чем на предыдущем уровне. Содержимое изображений задается тремя компонентами U(k), H(k), V(k): U^{x,y)^U^{2x,2y) Uik~l)(2x + l,2y) £/(i_l)(2jc,2j> + l) £/(*_i)(2jc + 1,2j> + 1), H^(x,y) = U^{2x,2y) + U('k~l)(2x + \,2y\ + + + (6) (7) V{k)(x, y) = и{к-1)(2х,2у)+и{к-1\2х;2у +1), (8) где k - уровень пирамиды, x и y - координаты изображения. Две полусуммы H(k) и V(k) используются для вычисления суммы четных строк и столбцов, используя формулы: Х{к\х,у) = ^Н{%у), (9) i=0 y-l rV(x,y)=Zv<»(x,j). (10) )=0 Используя полученную пирамиду изображений, производится обратный проход сверху вниз. При этом для вычисления значений используются четыре варианта формулы, зависящие от четности аргументов. При четных x и y W{k\x,y) = Wk+\ при нечетном X и четном у ), (11) wM{x,y) = Wk+1( + Yk+l( (12) ), при четном X и нечетном у W{k\x,y) = Wk+\ ) + Хк+\ ), (13) при нечетныххиу Wik\x,y) = wk+l( + хк+\ ) + Yk+l ( ) (14) + «Инфокоммуникационные технологии» Том 11, № 3, 2013 90 Цыганов А.А. Значения верхнего уровня принимаются равными нулю. Используя интегральное изображение, ключевые точки определяются путем поиска экстремумов определителя матриц Гессе. Для этого применяются блочные фильтры, описанные в [13]. Для их вычисления на GPU требуется всего 17 текстурных выборок на пиксель. Нахождение локального максимума Гессианы производится методом соседних точек 3^3x3. Каждая найденная ключевая точка описывается дескриптором, представляющим собой нормализованный вектор, вычисляемый с помощью фильтров Хаа-ра аналогично блочным фильтрам для определителя матрицы Гессе. С помощью дескрипторов осуществляется сравнение элементов множеств P и P’, на основе чего по выражению (4) вычисляется значение DS. Результаты Исследование эффективности реализации рассматриваемого алгоритма на графическом процессоре показывает значительное сокращение времени выполнения при использовании GPU. Зависимость времени выполнения от количества параметров шейдерных программ представлена на рис. 2. Рис. 2. Диаграмма времени обработки данных Использование ресурсов графического процессора позволяет значительно ускорить работу системы автоматизированного составления профилей для трехмерного векторного видео. Для видеоускорителя GeeForce GTX260 и центрального процессора AMD Phenom II X4 945 удалось добиться ускорения в среднем в 4,3 раза. Это позволяет сравнять длительность этапов автоматизированного составление профилей и проверки результата.