An image signature matching device, comprising: a matching unit for matching an image signature of a first image and an image signature of a second image which are generated by a generation method including: extracting region features from respective sub-regions of a plurality of predetermined pairs of sub-regions in an image; for each of the pairs of sub-regions, quantizing a difference value between the region features of two sub-regions forming a pair, wherein when performing quantization, the difference value is quantized to a particular quantization value if an absolute value of the difference value is smaller than a predetermined value; and using a collection of elements which are quantization values calculated for the respective pairs of sub-regions as an image signature to be used for discriminating the image, wherein the matching unit matches the image signature of the first image and the image signature of the second image in such a manner that a weight of an element having the particular quantization value is reduced, said method being characterized in that the plurality of predetermined pairs of sub-regions includes at least one pair of sub-regions in which both a combination of shapes of two sub-regions of the pair and a relative positional relation between the two sub-regions of the pair differ from those of at least one of the other pairs of sub-regions, each pair of sub-regions is associated with each dimension composing an image signature respectively, and each pair of sub-regions is categorized into one of a plurality of types that is a group consisting of the dimensions having a region pattern determined by combinations of shapes between the sub-regions in the pair, a threshold is determined independently for each type, and by using said threshold, a difference value between region features of two sub-regions forming a pair is quantized. a matching unit for matching an image signature of a first image and an image signature of a second image which are generated by a generation method including: extracting region features from respective sub-regions of a plurality of predetermined pairs of sub-regions in an image; for each of the pairs of sub-regions, quantizing a difference value between the region features of two sub-regions forming a pair, wherein when performing quantization, the difference value is quantized to a particular quantization value if an absolute value of the difference value is smaller than a predetermined value; and using a collection of elements which are quantization values calculated for the respective pairs of sub-regions as an image signature to be used for discriminating the image, wherein the matching unit matches the image signature of the first image and the image signature of the second image in such a manner that a weight of an element having the particular quantization value is reduced, said method being characterized in that the plurality of predetermined pairs of sub-regions includes at least one pair of sub-regions in which both a combination of shapes of two sub-regions of the pair and a relative positional relation between the two sub-regions of the pair differ from those of at least one of the other pairs of sub-regions, each pair of sub-regions is associated with each dimension composing an image signature respectively, and each pair of sub-regions is categorized into one of a plurality of types that is a group consisting of the dimensions having a region pattern determined by combinations of shapes between the sub-regions in the pair, a threshold is determined independently for each type, and by using said threshold, a difference value between region features of two sub-regions forming a pair is quantized.