1. An information processing apparatus comprising: holding means for holding a plurality of images; input means for inputting a query image; feature amount acquisition means for dividing the query image into a plurality of blocks, and calculating plural kinds of feature amounts including a luminance feature amount and an edge feature amount for each of the divided blocks; variance calculation means for calculating a variation of all feature amounts belonging to an identical kind, for each of the plural kinds; similarity calculations means for calculating a similarity between the query image and an image of interest held in said holding means for each of the plural kinds; weight calculation means for calculating a weight value for each of the plural kinds, wherein the weight value is larger for a kind with a large variation and is smaller for a kind with a small variation; weighting means for weighting the similarity calculated for each of the plural kinds by using the weight value calculated for each of the plural kinds, respectively; and retrieving means for retrieving a similar candidate, from said holding means, by using the weighted similarities.