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 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 an image signature to be used for identifying the image based on the extracted region features of the respective sub-regions, using, for at least one pair of sub-regions, a method different from that used for another pair of sub-regions.