Connected Component Labeling Using Quadtrees

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