Parallel Labeling for Image Processing

There is a large literature of parallel algorithms for pixel connectivity and connected component labeling applications in image processing. But many of these are useless for spin models:

1. Pixel connectivity is a special case of component labeling, and some of the algorithms cannot be generalized.

2. Most computer science analysis of algorithms concentrates on worse case complexity. We are interested only in average time complexity to label a large number of configurations.

3. Algorithms with optimal asymptotic efficiencies are not necessarily optimal on real machines. For one ``asymptotically optimal'' parallel component labeling algorithm, need processors to get a speedup of 1!

4. Some algorithms may work well on small, regular objects, but not on large, irregular spin model clusters.