1. An image processing apparatus for processing input image data, comprising: a selection unit configured to select, as a comparative cluster to be compared with a pixel of interest in the input image data, a cluster for which an absolute value of a difference between a component sum of the pixel of interest and a component sum of a representative value of the cluster is not more than a first threshold value; a calculation unit configured to calculate a color distance between the pixel of interest and the representative value of each of the comparative clusters selected by said selection unit; a classification unit configured to classify the pixel of interest to a cluster corresponding to a minimum value of the color distances calculated by said calculation unit, if the minimum value of the color distances is not more than a second threshold value; and a generation unit configured to generate a new cluster to which the pixel of interest is to be classified, if all the color distances calculated by said calculation unit are larger than the second threshold value.