The image signature extraction device includes a first feature extraction means for extracting, from an image, first features corresponding to the respective dimensions of a feature vector; a second feature extraction means for extracting, from the image, second features which are different from the first features, corresponding to the respective dimensions of a feature vector; a feature type determination means for analyzing at least one of the image and the extracted first features as a subject for analysis to determine whether or not the feature vector constituted of the extracted first features has effectiveness in discriminating an image, and if the feature vector has the effectiveness, determining the first features to be the type of the features used for the respective dimensions, while if the feature vector does not have the effectiveness, determining the second feature to be the type of the features used for at least part of the dimensions and determining the first features to be the type of the features used for the remaining dimensions; and a feature vector generation means for generating a feature vector of the image from the extracted first features and the extracted second features, according to the determined type of the features used for the respective dimensions.