An image processing apparatus reduces two input images to be compared by the predetermined number of times to generate two image groups, extracts a plurality of feature points and a local feature amount of each feature point from these image groups, and determines a combination of feature points in which local feature amounts are similar to each other, between the image groups. Then, the image processing apparatus determines a relation of a reasonable combination, assigns high weights to the reasonable combination, and calculates a similarity degree between the two input images.