Proposes deterministic psuedo annealing (DPA), a variation of simulated annealing. The method is an extension of relaxation labeling, a once popular framework for a variety of computer vision problems. The authors present its application to textured image segmentation. The basic idea is to introduce weighted labelings, which assign a weighted combination of labels to any site, and then to build a merit function of all the weighted labels. This function, a polynomial with non-negative coefficients, is an extension to a compact domain of R/sup N/ of an application defined on the finite (but very large) set of labelings; its only extrema under suitable constraints correspond to discrete labelings. DPA consists of changing the constraints, and thus the domain, so as to convexify this function, find its unique global maximum, and then track down the solution until the original constraints are restored, thus obtaining usually good discrete labeling.>