1. A video signature generation device, comprising: a visual feature extraction unit which extracts a visual feature to be used for identification of a video based on features of a plurality of pairs of sub-regions in the video; and a confidence value calculation unit which calculates a confidence value of the visual feature based on the features of the plurality of pairs of sub-regions.