A Fast and Robust Cluster Update Algorithm for Image Segmentation in Spin-Lattice Models Without Annealing. Visual...

Image segmentation in spin-lattice models relies on the fast and reliable assignment of correct labels to those groups of spins that represent the same object. Commonly used local spin-update algorithms are slow because in each iteration only a single spin is flipped and a careful annealing schedule has to be designed in order to avoid local minima and correctly label larger areas. Updating of complete spin clusters is more efficient, but often clusters that should represent different objects will be conjoined. In this study, we propose a cluster update algorithm that, similar to most local update algorithms, calculates an energy function and determines the probability for flipping a whole cluster of spins by the energy gain calculated for a neighborhood of the regarded cluster. The novel algorithm, called energy-based cluster update (ECU algorithm), is compared to its predecessors. A convergence proof is derived, and it is shown that the algorithm outperforms local update algorithms by far in speed and reliability. At the same time it is more robust and noise tolerant than other versions of cluster update algorithms, making annealing completely unnecessary. The reduction in computational effort achieved this way allows us to segment real images in about 1-5 sec on a regular workstation. The ECU-algorithm can recover fine details of the images, and it is to a large degree robust with respect to luminance-gradients across objects. In a final step, we introduce luminance dependent visual latencies (Opara and Worgotter, 1996; Worgotter, Opara, Funke, and Eysel, 1996) into the spin-lattice model. This step guarantees that only spins representing pixels with similar luminance become activated at the same time. The energy function is then computed only for the interaction of the regarded cluster with the currently active spins. This latency mechanism improves the quality of the image segmentation by another 40%. The results shown are based on the evaluation of gray-level differences. It is important to realize that all algorithmic components can be transferred easily to arbitrary image features, like disparity, texture, and motion.