A color estimation method for a gray-level image is proposed by giving a few color pixels. It is known that a density value in the gray-level image will be calculated by linear combination of an RGB vector of the color image. The problem dealt with in this study can be formulated as an ill-posed problem which searches for an RGB vector from a density value as a solution. By assuming a restricted condition to minimize the total of the color difference defined among adjacent pixels, the color will be optimized by the probabilistic relaxation method. The performance of the proposed method is verified by experiments. The proposed algorithm works very well when the solution is known with confidence in a few percents of the image.