Parallel border tracking in binary images using GPUs

Border tracking in binary images is an important kernel for many applications. There are very efficient sequential algorithms, most notably, the algorithm proposed by Suzuki et al., which has been implemented for CPUs in well-known libraries. However, under some circumstances, it would be advantageo...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2022-05, Vol.78 (7), p.9817-9839
Main Authors: Garcia-Molla, Victor M., Alonso-Jordá, Pedro, García-Laguía, Ricardo
Format: Article
Language:English
Subjects:
Algorithms
Borders
Central processing units
Compilers
Computer Science
CPUs
Interpreters
Processor Architectures
Programming Languages
Rectangles
Tracking
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Border tracking in binary images is an important kernel for many applications. There are very efficient sequential algorithms, most notably, the algorithm proposed by Suzuki et al., which has been implemented for CPUs in well-known libraries. However, under some circumstances, it would be advantageous to perform the border tracking in GPUs as efficiently as possible. In this paper, we propose a parallel version of the Suzuki algorithm that is designed to be executed in GPUs and implemented in CUDA. The proposed algorithm is based on splitting the image into small rectangles. Then, a thread is launched for each rectangle, which tracks the borders in its associated rectangle. The final step is to perform the connection of the borders belonging to several rectangles. The parallel algorithm has been compared with a state-of-the-art sequential CPU version, using two different CPUs and two different GPUs for the evaluation. The computing times obtained show that in these experiments with the GPUs and CPUs that we had available, the proposed parallel algorithm running in the fastest GPU is more than 10 times faster than the sequential CPU routine running in the fastest CPU.
ISSN:0920-8542
1573-0484
DOI:10.1007/s11227-021-04260-y