More than 100 million individuals around the world suffer from color vision deficiency (CVD). Image recoloring algorithms have been proposed to compensate for CVD. This study has proposed a new recoloring algorithm to make up shortages of contrast enhancement and naturalness preservation of the state-of-the-art methods. The recoloring task is formulated as an optimization problem that is solved by using the colors in a simulated CVD color space to maximize contrast and to preserve the original color as much as possible. In addition, the dominant colors are extracted for recoloring. They are then propagated to the whole image so that the optimization problem could be solved at a reasonable cost independent of the image size. In the quantitative evaluation, the results of the proposed method are competitive with those of the best existing method. The evaluation involving subjects with CVD demonstrates that the proposed method outperforms the state-of-the-art method in preserving both the information and the naturalness of images.