Back to articles
Volume: 28 | Article ID: art00017
Block Equivalence Algorithm for Labeling 2D and 3D Images on GPU
  DOI :  10.2352/ISSN.2470-1173.2016.2.VIPC-240  Published OnlineFebruary 2016

In this paper we propose a block equivalence algorithm for connected component labeling of 2D and 3D images on GPU. Usage of square pixel blocks in our solution allows reducing twice computational complexity in comparison with existing label equivalence methods. In contrast to well-known block-based algorithms, we don’t rely on decision tables to reduce amount of memory accesses. Instead, we propose a different technique based on pixel scan mask that better suits to GPU architecture. We show, theoretically and experimentally, that our approach outperforms many existing CPU and GPU algorithms for connected component labeling. We also demonstrate, how to extend our method to label 3D volumetric images and that it has significant performance advantage over a simple label equivalence algorithm.

Subject Areas :
Views 21
Downloads 1
 articleview.views 21
 articleview.downloads 1
  Cite this article 

Sergey Zavalishin, Ilia Safonov, Yury Bekhtin, Ilia Kurilin, "Block Equivalence Algorithm for Labeling 2D and 3D Images on GPUin Proc. IS&T Int’l. Symp. on Electronic Imaging: Visual Information Processing and Communication VII,  2016,

 Copy citation
  Copyright statement 
Copyright © Society for Imaging Science and Technology 2016
Electronic Imaging
Society for Imaging Science and Technology
7003 Kilworth Lane, Springfield, VA 22151 USA