MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER
An algorithm is presented for labeling the connected components of an image represented by a quadtree. The algorithm proceeds by exploring all possible adjacencies for each node once and only once. Once this is done, any equivalences generated by the adjacency labeling phase are propagated. Analysis of the algorithm reveals that its worst case average execution time is bounded by a quantity proportional to the product of the log of the regions diameter and the number of blocks comprising the area connected by the components.