РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНОГО АЛГОРИТМА ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ

IMPLEMENTATION OF A PARALLEL IMAGE FILTERING ALGORITHM

Anton Gavrunov

Student, Institute of Engineering and Digital Technologies, Belgorod State National Research University,

Russia, Belgorod

АННОТАЦИЯ

Цели. реализации параллельного алгоритма фильтрации изображений. Методы. Методы исследования алгоритма решения задачи. Использовались теоретические и эмпирические методы Результаты. выполнить ряд задач, относящихся к реализации алгоритма фильтрации изображения (кросс-корреляции). Обсуждение. В ходе работы был сделан вывод, что данная задача показывает лучший результат только в том случае, если расчеты будут проходить на большом количестве данных.

ABSTRACT

Goals. implementation of a parallel image filtering algorithm. Methods. Methods for studying the algorithm for solving the problem. Theoretical and empirical methods were used. Results. perform a number of tasks related to the implementation of the image filtering algorithm (cross-correlation). Discussion. In the course of the work, it was concluded that this task shows the best result only if the calculations are carried out on a large amount of data.

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

Keywords: function, algorithm, processor, correlation, memory size, OpenMP, array.

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

Математически алгоритм описывается следующим образом: S - последовательность байт источника, длины W_s x H_s - ширины и высоты исходного изображения, T - последовательность байт шаблона, длины W_t x H_t - ширины и высоты шаблонного изображения. b - минимальное требуемое значение корреляции Для каждой точки (w, h) исходного изображения по формуле, представленной на рисунке 1, вычисляется нормализованная кросс корреляция r.

Рисунок 1. Нормализованная кросс корреляция

Конкретно метод нормализованной кросс корреляции предполагает выходное значение от -1 до 1, где -1 означает, что изображения противоположны (напр. кодируются числовыми значениями с противоположными знаками), 0 - отсутствие корреляции, 1 - полное совпадение. Это позволяет задать фильтр на выходные значения, к примеру 90% совпадение. Последовательность Y_i постоянна и равна T, а X_i генерируется в зависимости от w, h из S. Если r > b, то (w, h) добавляется в результирующий массив.

При распараллеливании алгоритма нужно знать, как взаимодействуют отдельные части алгоритма: какие части ожидают данные от других и т.п. Для этого используем схему операций-операндов. (Рисунок 2)

Если рассматривать вычисление корреляции как атомарную операцию, то схема выглядит следующим образом:

Рисунок 2. Схема операция-операнд

Алгоритм состоит из двух частей. Функция для вычисления корреляции между двумя равными по высоте и ширине изображениями, и клиентского кода, который будет обрабатывать результаты этих вычислений. Алгоритм построен на рисунке 3.

Рисунок 3. Блок-схема алгоритма

Из ранее приведенной схемы операция-операнд видно, что при вычислении корреляции пара координат (x, y) преобразуется в вещественное число, при выполнении промежуточных вычислений не происходит никакого изменения общего состояния.

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

Сразу после вычисления корреляции результат обрабатывается вызывающей стороной. Перед нами стоит задача сохранить все подходящие результаты в коллекцию. std::vector не гарантирует потокобезопасность для метода push_back, поэтому требуется внешняя синхронизация.

Исходные данные последовательной версии алгоритма:

1. S и T - изображения, источник и шаблон соответственно
2. Xt - ширина шаблона в пикселях,
3. Yt - высота шаблона в пикселях.
4. Xs - ширина источника в пикселях,
5. Ys - высота источника в пикселях.
6. r - количество сэмплов в одном пикселе. При разработке программы положим r = 3

Обозначим за F(int, int) функцию нахождения корреляции между изображениями S и T в точке

Вычисляемые данные:

7. Xn = Xs - Xt;
8. Yn = Ys - Yt;
9. ОДЗ для F(x,y) - X ∈ [0; Xn), Y ∈ [0; Yn)

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

Рассмотрим возможные стратегии распределения задач: блочная и построчная. Первая предполагает деление задачи на части по X и Y. Например, изображение 64х64 можно разбить на блоки 2х2, получится 1024 независимые задачи. Как будут разделяться данные по этим задачам?

Как показано на рисунке, при допустимом X ∈ [2; 5] и Y ∈ [1;3] для вычисления требуются данные [27; 38] ∪ [48;59] ∪ [69; 80]. Поскольку в случае с изображениями оптимально хранить данные непрерывным блоком в памяти, чтобы избежать двойного обращения к памяти, из 54 переданных сэмплов 18 никак не будут использоваться при вычислениях.

Рисунок 4. Схема передаваемых данных

Вторая предполагает деление задачи по Y, X принимается за всю ширину строки. Изображение 64х64 будет разбито максимум на 64 подзадачи. При этом лишние данные передаваться вовсе не будут.

Далее зеленым указаны данные изображения, которые будут использованы только на 0-м узле, синим - только на 1-м и фиолетовым - на обоих.

Рисунок 5. Схема передаваемых данных (оптимальный алгоритм)

Таким образом могут быть переданы пиксели изображения. Псевдокод алгоритма, который равномерно распределяет данные по узлам:

n = количество узлов

целое = Yn / n

остаток = Yn / n

повторить n раз:

добавить целое в размеры задач если остаток != 0

уменьшить остаток на 1

увеличить последний размер задачи на 1

конец если

конец повторить

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

1. Talmi, Mechrez, Zelnik-Manor (2016). "Template Matching with Deformable Diversity Similarity" [электронный ресурс] // URL: https://docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/template_matching/template_matching.html (дата обращения: 09.12.2020)
2. OpenMP introduction [электронный ресурс] // URL: http://jakascorner.com/blog/2016/04/omp-introduction.html (дата обращения: 11.12.2020)
3. Boost.MPI documentation [электронный ресурс] // URL: https://www.boost.org/doc/libs/1_72_0/doc/html/mpi.html (дата обращения: 13.12.2020)
4. Учебник по OpenMP [электронный ресурс] // URL: https://pro-prof.com/archives/4335 (дата обращения: 11.12.2020)
5. Основы MPI [электронный ресурс] // URL: https://habr.com (дата обращения: 15.12.2020)
6. MPI. Вводный курс [электронный ресурс] // URL: http://www.ssd.sscc.ru/old/old/kraeva/MPI.html (дата обращения: 10.12.2020)