10.14489/vkit.2018.01.pp.024-033

DOI: 10.14489/vkit.2018.01.pp.024-033

Кушнир О. А., Середин О. С.
ПАРАЛЛЕЛЬНЫЕ РЕАЛИЗАЦИИ АЛГОРИТМА СРАВНЕНИЯ БИНАРНЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ОПИСАНИЯ СКЕЛЕТОВ ЦЕПОЧКАМИ ПРИМИТИВОВ
(c. 24-33)

Аннотация. Рассмотрены способы ускорения работы метода сравнения бинарных изображений на основе описания скелетов объектов цепочками примитивов. Обосновано применение параллельных вычислений на персональном компьютере с использованием технологии OpenMP и библиотек для работы с потоками стандарта языка программирования C++11. Проведены эксперименты для оценки ускорения, полученного параллельными реализациями алгоритма сравнения бинарных изображений, относительно последовательной версии.

Ключевые слова: бинарное изображение; сравнение форм; скелет; цепочка примитивов; функция парного сравнения; параллельные вычисления.

Kushnir O. A., Seredin O. S.
PARALLEL IMPLEMENTATIONS OF THE BINARY IMAGE COMPARISON ALGORITHM BASED ON SKELETON PRIMITIVE CHAINS
(pp. 24-33)

Abstract. The skeleton is a useful descriptor for solving Computer Vision problems based on shape matching. Skeleton matching is a rather computationally expensive task, so some ways of reducing computations are appreciated, especially in case of video stream processing. There are two main methods of speeding up an algorithm – the first one is the analytical, by improving the algorithm and reducing the number of operations in it; and the second one is the technical, by parallelizing some parts of the source code. In this work we propose the technical way of speeding up the previously suggested skeleton matching algorithm based on skeleton primitive chains alignment. We review two parallel computing techniques for the systems with shared memory – OpenMP and C++11 multithreading – and prove that they are proper for our skeleton matching algorithm which could be used on ordinary multicore PCs. Then we show which part of the algorithm would be parallelized. As a conclusion we discuss experimental results achieved on two parallel versions of the algorithm.

Keywords: Binary image; Shape matching; Skeleton; Chain of primitives; Pairwise comparison function; Parallel computing.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

О. А. Кушнир, О. С. Середин (Тульский государственный университет, Тула, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

O. A. Kushnir, O. S. Seredin (Tula State University, Tula, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Blum H. A Transformation for Extracting New Descriptors of Shape // Models for the Perception of Speech and Visual Form 19 (5). 1967. P. 362 – 380.
2. Местецкий Л. М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. М.: ФИЗМАЛИТ, 2009. 288 с.
3. Кушнир О. А., Середин О. С. Функция парного сравнения скелетных графов, заданных цепочками примитивов // Известия ТулГУ. Серия «Технические науки», вып. 2. Тула: ТулГУ, 2013. С. 197 – 207.
4. Kushnir O., Seredin O. Shape Matching Based on Skeletonization and Alignment of Primitive Chains // Analysis of Images, Social Networks and Texts. Fourth International Conference, AIST 2015, Yekaterinburg, Russia, April 9 – 11, 2015, Revised Selected Papers. Communications in Computer and Information Science, V. 542, Springer. P. 118 – 130.
5. Рогов А. А., Быстров М. Ю. Структурное распознавание бинарных изображений с использованием скелетов // Математические методы распознавания образов: сб. докл. 15-й Всероссийской конференции, Петрозаводск, 2011 г. М.: МАКС Пресс, 2011. С. 420 – 423.
6. Кушнир О. А. Параметрическое описание радиальной функции скелета бинарного изображения для задачи сравнения форм // Вестник компьютерных и информационных технологий. 2016. № 2. С. 3 – 12.
7. Кушнир О. А., Середин О. С., Степанов А. В. Экспериментальное исследование параметров регуляризации и аппроксимации скелетных графов бинарных изображений // Машинное обучение и анализ данных. В 3 т. T. 1. 2014. № 7. C. 817 – 827.
8. Chapman B., Jost G., Van Der Pas R. Using OpenMP: Portable Shared Memory Parallel Programming. MIT press, 2008. 384 р.
9. Butenhof D. R. Programming with POSIX threads. Addison-Wesley Professional, 1997. 381 р.

Eng

1. Blum H. (1967). A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, 19(5), pp. 362-380.
2. Mestetskii L. M. (2009). Continuous morphology of binary images: figures, skeletons, circulars. Moscow: FIZMALIT. [in Russian language]
3. Rogov A. A., Bystrov M. Iu. (2011). Structural recognition of binary images using skeletons. Mathematical methods of pattern recognition: proceedings of the 15th All-Russian Conference, (pp. 420-423). Petrozavodsk. Moscow: MAKS Press. [in Russian language]
4. Kushnir O. A., Seredin O. S. (2013). Function pairwise comparison of skeletal graphs, formed with a chain of primitives. Izvestiia TulGU, seriia «Tekhnicheskie nauki, (2), pp. 197-207. [in Russian language]
5. Kushnir O., Seredin O. (2015). Shape matching based on skeletonization and alignment of primitive chains. Analysis of Images, Social Networks and Texts. Fourth International Conference, AIST 2015, Yekaterinburg, Russia, April 9 – 11, 2015, Revised Selected Papers. Communications in Computer and Information Science, V. 542, (pp. 118-130). Springer.
6. Kushnir O. A. (2016). Раrametric representation оf binary image skeleton radial function for shape matching problem. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (2), pp. 3-12. [in Russian language]
7. Kushnir O. A., Seredin O. S., Stepanov A. V. (2014). Experimental study of regularization parameters of approximation skeletal diagrams of binary images. Mashinnoe obuchenie i analiz dannykh, Vol. 1, (7), pp. 817-827. [in Russian language]
8. Chapman B., Jost G., Van Der Pas R. (2008). Using OpenMP: portable shared memory parallel programming. MIT press.
9. Butenhof D. R. (1997). Programming with POSIX threads. Addison-Wesley Professional

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

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

Для заказа скопируйте doi статьи:

10.14489/vkit.2018.01.pp.024-033

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2018.01.pp.024-033

and fill out the form