The image signature extraction device includes an extraction unit and a generation unit. The extraction unit extracts region features from respective sub-regions in an image in accordance with a plurality of pairs of sub-regions in the image, the pairs of sub-regions including at least one pair of sub-regions in which both a combination of shapes of two sub-regions of the pair and a relative position between the two sub-regions of the pair differ from those of at least one of other pairs of sub-regions. The generation unit generates, based on the extracted region features of the respective sub-regions, an image signature to be used for identifying the image.