Several texture segmentation algorithms based on deterministic and stochastic relaxation principles, and their implementation on parallel networks are described. The segmentation process is posed as an optimization problem and two different optimality criteria are considered. The first criterion involves maximizing the posterior distribution of the intensity field given the label field (maximum a posteriori estimate). The posterior distribution of the texture labels is derived by modeling the textures as Gauss Markov random fields (GMRFs) and characterizing the distribution of different texture labels by a discrete multilevel Markov model. A stochastic learning algorithm is proposed. This iterated hill-climbing algorithm combines fast convergence of deterministic relaxation with the sustained exploration of the stochastic algorithms, but is guaranteed to find only a local minimum. The second optimality criterion requires minimizing the expected percentage of misclassification per pixel by maximizing the posterior marginal distribution, and the maximum posterior marginal algorithm is used to obtain the corresponding solution. All these methods implemented on parallel networks can be easily extended for hierarchical segmentation; results of the various schemes in classifying some real textured images are presented.