A relaxation algorithm for removing impulse noise from highly corrupted images is proposed, where a nonlinear probabilistic model is used to reduce the ambiguity of each pixel based on the contextual information. Each pixel is given three labels which stand for ‘‘positive corruption,’’ ‘‘no corruption,’’ and ‘‘negative corruption.’’ The initial probabilities of a pixel whose gray level lies in the middle intensity range of the whole image are simply given some fixed values. Those of a pixel whose gray level lies in the upper or lower part of the intensity range are determined by its gray level and the difference with the median value in a 3×3 window. To display the image after each iteration, the gray level of a pixel with high no-corruption probability is set to its original value approximately, while the gray level of a pixel with high corruption probability will be replaced by the average value of its neighbor pixels with high no-corruption probabilities. Experimental results show that this algorithm can effectively remove both positive and negative impulse noise with very high probability and is superior in performance to some other methods for highly corrupted images.