This invention has as its object to allow high-precision and high-speed retrieval in consideration of position information of image feature amounts upon retrieving similar images based on image feature amounts, even when the position information includes some differences. To achieve such object, an image processing apparatus according to this invention has the following arrangement. That is, an image processing apparatus for calculating a similarity between different image data, includes a first generation unit configured to generate feature amount matrices on the basis of feature amounts of the image data acquired by dividing the different image data into a plurality of blocks, a calculation unit configured to calculate a distance between feature sequences which form the generated feature amount matrices by DP matching, and a second generation unit configured to generate a line penalty matrix by two-dimensionally arranging the calculated distances between the feature sequences, and calculates a similarity between the different image data by DP matching using the line penalty matrix.