We have developed a robust segmentation algorithm for textured images: those composed of regions of two distinct textures. The region image (the extension of the natural patches) Is modeled by a binary Besag-Marklow random field (MRF) characterized by a single parameter, whereas the covering textures are modeled by two spatially independent Gaussian random variables with region-dependent means and variances. The model parameters are unknown and assumed to be between know lower and upper bounds. The iterated conditional modes (ICM) algorithm is adopted and is made robust by using the maximin (worstcase) method. Our main theoretical result is given as the least-favorable operating point theorem. In the present study, we obtain the least favorable operating point for the mean parameters of the two spatially independent Gaussian random variables. Simulation studies show that the Algorithm has a uniform and low segmentation error over the entire Range of the model parameters. The most useful features of the Algorithm are that its use does not require full knowledge of the Model parameters or their estimates and that it can be implemented In a massively parallel manner.