Image Segmentation in Linear Time using the Potts Model

A computational method is described which efficiently segments digital grayscale images using the Q-state Ising (or Potts) model. Since the Ising model was first proposed in 1925, physicists have studied lattice models to gain deep insights into ordered/disordered systems. Some researchers have realized that digital images may be modeled in much the same way as these physical systems (i.e., as a square lattice of numerical values). A major drawback in using this technique for image segmentation is that it processes in exponential time. Advances have been made via certain approximations to reduce the segmentation process to power-law time. However, real-time processing (such as for sonar imagery) requires much greater efficiency. We describe an energy minimization technique using four Potts (Q-Ising) models which processes in linear time. The technique is demonstrated on acoustic seafloor images as well as medical images.