1. An image processing apparatus comprising: a reduced-scale image generation unit configured to generate a reduced-scale image of first image data; a color space division unit configured to determine a plurality of bins by dividing predetermined color space, the plurality of bins being used for generating frequency distributions; a first frequency distribution generation unit configured to generate, for all pixels included in the reduced-scale image, a first frequency distribution by counting a number of pixels that belong to each of the bins determined by said color space division unit; a detection unit configured to detect an edge region from the first image data; a second frequency distribution generation unit configured to generate, for pixels included in the edge region detected by said detection unit, a second frequency distribution by counting a number of pixels that belong to each of the bins determined by said color space division unit; a determination unit configured to select N bins based on the generated first frequency distribution and the generated second frequency distribution, and configured to determine N types of pixel values respectively corresponding to the selected N bins; and a substitution unit configured to substitute each of pixels included in the first image data using the determined N types of pixel values.