Pyramidal Connected Component Labeling of Image

In this paper, a new logarithmic-time algorithm is presented which simultaneously assigns labels to all connected components of a binary image. The main advantage of the proposed algorithm is to propagate information in the logarithmic order by using the graph pyramid structure. The irregular combinatorial pyramid is employed to construct the hierarchy and the maximum independent edge sets (MIES) are used to create this pyramid structure in parallel. To assign a label to each connected component, instead of the common linear-time raster scan techniques, only two traversings of the existing pyramid are needed. First, contracting each connected component to a single vertex maintaining all connectivity relations at the top of the pyramid and assign a new label to each vertex. Second, to go top-down and to propagate this unique label into each individual pixel of the binary image. In addition, no relabeling is needed throughout the whole process as it is needed by other algorithms. Finally, the experimental results show the proposed algorithm outperforms the other state-of-the-arts for large images.