Нижегородский государственный университет им. Н.И. Лобачевского Лаборатория Информационных технологий (ITLab) Разработка параллельной реализации трекинга объектов с использованием библиотеки Intel Array Building Blocks Список участников Кайнов Олег Ларцов Иван Ханова Татьяна Руководитель Кустикова Валентина

2 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Содержание Терминология Постановка задачи Схема решения задачи Описание последовательной реализации Схема распараллеливания этапов алгоритма Описание параллельной реализации –Скорость работы при вызове call и обычном вызове Результаты экспериментов –Сравнение последовательной и параллельной реализации

3 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Постановка задачи Цель: Оценить эффективность применения Intel Array Building Blocks для трекинга объектов. Задачи: Реализовать схему двумерного сопровождения объектов с использованием библиотеки OpenCV. Разработать параллельную версию алгоритма, используя библиотеку Intel Array Building Blocks. Оценить время работы параллельной версии.

4 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема решения задачи Преобразование кадров видео в оттенки серого Построение модели фона на основе имеющегося буфера кадров Для каждого следующего кадра видео: Вычитание фона из текущего кадра Бинаризация изображения Обновление модели фона Преобразование кадра видео в оттенки серого

5 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Преобразование кадра в оттенки серого Переводим трехканальное изображение в одноканальное по формуле c некоторыми коэффициентами. где- соответсвующие каналы изображения, - весовые коэффициенты каналов.

6 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Построение модели фона На основе массива одноканальных изображений строим первую модель фона. - первый кадр фона. - k-й кадр видео.

7 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Построение бинаризованного изображения Вычитаем фон из очередного кадра. Отсекаем пиксели со значением больше порогового.

8 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Морфология Избавление бинаризованного изображения от шумов с помощью эрозии.

9 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Обновление модели фона Для каждого кадра видео обновляем модель фона по формуле. То есть, сложим текущие кадры фона с весовыми коэффициентами.

10 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации Чтобы начать обрабатывать потоковое видео, нужно создать кадр фона по первым n кадрам исходного видео. Каждый кадр, который будет использоваться в построении модели фона, нужно будет конвертировать в черно-белый кадр. Для создания кадра фона будем использовать модель фона с использованием усреднения. - i-й пиксель фона. - i-й пиксель j-ого кадра.

11 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации Конвертирование кадра в черно-белый кадр void ConvertToGrayscale(IplImage* grayFrame, const IplImage* image,const double r,const double g,const double b); Создание кадра фона с использованием усреднения IplImage* BGModelAve(IplImage** src, const int n); bgr…frame p…bg bgrbgr pppppppp … … … … ppppppppp ppppppppp ppppppppp ppppppppp

12 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации После создания первоначального кадра фона для каждого последующего кадра видео будем выполнять последовательность действий. 1. Конвертировать в черно-белый кадр. 2. Найти различия между полученным кадром и текущим кадром фона. 3. К полученному кадру разницы применить сглаживающий фильтр. 4. Проклассифицировать множество пикселей на фоновые и не фоновые – бинаризовать изображение. 5. Отобразить полученный кадр. 6. Обновить кадр фона.

13 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации Вычисление разности фона и текущего кадра void Diff(const IplImage* bg, const IplImage* frame, unsigned char* const diff); Получение бинаризованной маски void ClipPix(IplImage* mask,unsigned char* const diff, const char t); …bbbbbbbbb background …fffffffff frame …dddddddd diff - = d tresh

14 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации Для уменьшения количества «случайных» белых пикселей – шума – применим метод математической морфологии сужение. void Erosion(IplImage* src, IplImage* out, bool* mask, int maskWidth, int maskHeigth); Маска – двумерный массив (матрица) интенсивностей пикселей. Рассмотрим пиксель.. Шаблон – двумерный булев массив.

15 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации ? да нет Таким образом обрабатываем все пиксели маски.

16 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации Основываясь на методе поиска границ Канни рисует границы маски на исходном кадре. void CannyTrack(IplImage * src, IplImage * mask, const double lowThresh, const double highThresh, unsigned char track_r, unsigned char track_g, unsigned char track_b); В данном методе используется OpenCV-функция void cvCanny(const CvArr* image, CvArr* edges, double threshold1, double threshold2, int aperture_size); Данная функция «обводит» сегменты из определенного заданного порога интенсивности пикселей. Затем нужно перенести полученные границы на исходный кадр, отобразив их соответствующим цветом.

17 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание последовательной реализации После того как кадр с отрисованными границами отображен, нужно пересчитать кадр фона. Для этого создадим циклический буфер, который будет состоять из n предыдущих кадров фона. Чтобы получить новый кадр фона, вставим на место самого старого фона текущий и пересчитаем фон. IplImage* UpdateBGModel(IplImage* grayFrame, IplImage** src, const int n, const unsigned int OldFramePosition, double* const w) Начало буфера

18 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма Во многих функциях производилось одно и тоже действие над каждым пикселем кадра Данные функции могут быть хорошо распараллелены, если массив интенсивностей мы представим как тип dense И будем применять к нему метод map(). Изначально имеем IplImage которая имеет поле ImageData, которое является массивом интенсивности. Используем биндинг: dense img_arbb; IplImage* img = cvCreateImage(img_size,DEPTH,CHANNELS); bind(img_arbb,(uchar*)img->imageData,img_size);

19 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма Конвертирование в черно-белое изображение void ConvertToGrayscale(IplImage* grayFrame, const IplImage* image,const double r,const double g, const double b) Для каждого элемента полученного dense-контейнера можно сделать следующее: умножить на соответствующий коэффициент его и его соседей, а потом сложить. Каждый третий такой пиксель в массиве (так как трехканальное изображение) и будет пикселем черно-белого кадра. bgr p Текущий Правый сосед Левый сосед bgr p bgrbgr pppppppp void Conv(arbb::f32 &a) { a=neighbor(a,1)*r+a*g+neighbor(a,-1)*b; } Ядро:

20 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма Вычисление разности фона и текущего кадра void difference(const dense &a, const dense &b, dense &c) В данной функции вызывается ядро map(): void diff(i8 a, i8 b, u8 &c) Получение бинаризованной маски void ClipPix(const dense &a, dense &b, const u8 t) Ядро map(): void Clip(const i8 &a, i8 &b, const u8 t)

21 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма Для обновления фона мы сохраняем предыдущие n кадров фона и текущий кадр в циклическом буфере: dense mainFramesBuffer_arbb Он содержит (n+1)·ImgHeight·ImgWidth элементов u8. Также есть массив коэффициентов: dense coefficients В исходной формуле ……bnbn fb1b1 b2b2 ……… ImgSize = ImgHeight·ImgWidth

22 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма Рассмотрим реализацию обновления фона 1. Для каждого i-го пикселя фона: 2. Сформировать вектор из i-х пикселей кадров из циклического буфера. 3. Умножить полученный вектор на вектор коэффициентов. wwwwwwwww * =

23 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма 3. Теперь нужно просуммировать все координаты ветора, чтобы получить i-й пиксель фона. 4. Так как буфер циклический, циклически подвинуть массив коэффициентов вправо на один элемент. dense UpdateBGModel(dense &mainFramesBuffer, dense &coefficients, const int width, const int height, const int n) = wwwwwwwww

24 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема распараллеливания алгоритма Создание кадра фона с использованием усреднения dense Average(const dense &src, int n, int size) Данная функция аналогична функции обновления фона, за исключением того, что все коэффициенты равны 1/n

25 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Обзор ArBB ArBB предоставляет два типа параллелизма: параллелизм по данным и параллелизм по потокам. ArBB использует собственный тип для хранения однотипных массивов данных: dense-контейнеры. Есть две специальных ArBB-функции, обеспечивающие работу со скалярными и векторными ArBB-типами: map и call. Функция map обеспечивает векторизацию, или параллелизм по данным, которая вызывается поэлементно для каждого из элементов контейнера. Call, по сути, является аналогом обычного вызова функции в С.

26 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Описание параллельной реализации При первом вызове функции происходит компиляция кода этой функции в реальном времени с учетом особенностей текущего процессора (SSE, AVX) Все функции, использующие контейнеры и\или переменные ArBB, должны вызываться с помощью call Когда функция вызывается с помощью call, происходит передача управления библиотеке ArBB, она берет на себя задачу контроля вычислений. После завершения работы функции контроль возвращается основному приложению. Функция, вызванная с помощью map для контейнера, выполняется поэлементно для каждого элемента контейнера (Параллелизм по данным)

27 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Пример реализации ArBB функции Функция получает двумерный контейнер с данными, результат усреднения по столбцам сохраняет во второй контейнер void AverageTwoDim (const dense &a, dense &res) { _if (res.length()==a.num_cols()) { _for (usize i=0, i

28 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Сравнение способов вызова ArBB-функций по времени исполнения

29 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Выводы. Исходя из экспериментов, очевидно, нужно использовать вызовы функций, использующих ArBB, с помощью call. Пример: void difference(const dense &a, const dense &b, dense &c){ map(diff)(a, b, c); } void diff(const i8 &a, const i8 &b, u8 &c){ i32 cf = a - b; c = (u8)cf; } Пример вызова: call(difference)(a,b,c);

30 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Схема работы параллельной версии Т.к. вызов функции с использованием map необходимо производить из функции, вызванной с помощью call, то схема вызова функций такая: Основное приложение – вызов с помощью call – вызов map Основное приложение Вызовы map Контейнеры

31 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Сравнение параллельной и последовательной версий

32 Н. Новгород, 2011 г. Разработка параллельной реализации схемы двумерного сопровождения объектов с использованием библиотеки Intel Array Building Blocks Выводы В процессе выполнения работ мы разработали последовательную и параллельную реализацию. Также было разработано демонстрационное приложение с графическим интерфейсом. Библиотека Intel Array Building Blocks для решения практических задач на данных момент не приспособлена.