Connected Component Labeling Using Quadtrees
Hanan Samet · Journal of the ACM · 1981
An algorithm is presented for labehng the connected components of an image represented by a quadtree.The algorithm proceeds by exploring all possible adjacenoes for each node once and only once.As soon as this ~s done, any equivalences generated by the adjacency labeling phase are propagated Analysis of the algorithm reveals that its average executmn tune ~s of the order (W + B.log B) where B and W correspond to the number of blocks comprising the foreground and background, respecuvely, of the image