When designing hardware, it is often desirable to represent images as economically as possible. Due to this, algorithms have been developed to create reduced palette images. Much better viewing results can be obtained by first reconstructing a full color image from the reduced palette image. This creates a need for a palette restoration algorithm. This paper develops an algorithm to reconstruct high resolution color image data from reduced color palette images. The algorithm is based on stochastic regularization using a non-Gaussian Markov random field model for the image data. This results in a constrained optimization algorithm that is solved using an iterative constrained gradient descent computational algorithm. During each iteration the potential update must be projected onto the constraint space. In this paper a projection operator that maps a vector onto a quantized constraint space is developed. Results of the proposed palette restoration algorithm have indicated that it is effective for the reconstruction of palettized images. Quantitative as well as visual results of the experiments are presented.