SMOOTH CURVE EXTRACTION BY MEAN-FIELD ANNEALING

In this paper, we attack the figure-ground discrimination problem from a combinatorial optimization perspective. In general, the solutions p roposed in the past solved this problem only partially: either the mat hematical model encoding the figure-ground problem was too simple or t he optimization methods that were used were not efficient enough or th ey could not guarantee to find the global minimum of the cost function describing the figure-ground model. The method that we devised and wh ich is described in this paper is tailored around the following contri butions. First, we suggest a mathematical model encoding the figure-gr ound discrimination problem that makes explicit a definition of shape (or figure) based on cocircularity, smoothness, proximity, and contras t. This model consists of building a cost function on the basis of ima ge element interactions. Moreover, this cost function fits the constra ints of an interacting spin system, which in turn is a well suited phy sical model to solve hard combinatorial optimization problems. Second, we suggest a combinatorial optimization method for solving the figure -ground problem, namely mean field annealing which combines the mean f ield approximation and annealing. Mean field annealing may well be vie wed as a deterministic approximation of stochastic methods such as sim ulated annealing. We describe in detail the theoretical bases of this method, derive a computational model, and provide a practical algorith m. Finally, some experimental results are shown for both synthetic and real images.