This paper presents a novel example-based colorization algorithm for natural images. For colorization, images are divided into image patches and then patches are categorized as flat, texture, and boundary patches based on their edge property. Different feature descriptors are then assigned to the flat and texture categories for a neighbor search. Through a weighted summation of the K nearest neighbors searched from reference image patches, the color information of flat and texture patches in a gray input image is synthesized. Using the synthesized color information, pixels belonging to a flat or a texture patch are initially colorized. All of the image pixels including the remaining boundary pixels are then subsequently colorized and refined using bilateral filters. A gamut-adaptive color space conversion scheme from the processed YUV to the RGB color space is also proposed to improve the naturalness of the color in the display. The experimental results show that the proposed algorithm successfully alleviates incorrect colorization in the boundary regions and improves color consistency in homogeneous regions compared to existing algorithms. In addition, the final RGB values of the colorized images maintain the original luminance and synthesized hue values well, resulting in more plausible and compelling colorization results in the displayed images.