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.