An initial similarity candidate calculator calculates a similarity between first and second images, which are expressed by quantized DCT coefficients, on the basis of at least first and second image feature amounts of the first and second images. A coefficient conversion processor executes a coefficient conversion process for at least one of the first and second image feature amounts. Based on an image feature amount obtained by that process, a similarity calculator calculates a similarity between the first and second images. Then, a final similarity between the first and second images is determined from the calculated similarities.