This paper proposes a novel scheme to virtually restore the colors of ancient murals. Our approach integrates artificial intelligence techniques with digital image processing methods. The knowledge related to the mural colors is first categorized into four types. A hybrid frame and rule-based approach is then developed to represent knowledge and to infer colors. An algorithm that takes into account color similarity and spatial proximity is developed to segment mural images. A novel color transformation method based on color histograms is finally proposed to restore the colors of murals. A number of experiments based on real images have demonstrated the validity of the proposed scheme for color restoration.