1. A video descriptor generation device, comprising: an each-picture feature extraction unit that extracts a feature from a video for each picture which is a frame or a field, and outputs an each-picture feature; an inter-picture feature difference calculation unit that calculates an inter-picture feature difference, which is a difference between features of pictures, from the each-picture features of the video as a difference feature, and calculates a difference feature information amount indicating an information amount that is necessary for describing the difference feature; an additional feature extraction unit that calculates a feature to be added as an additional feature from the video; and a feature combining unit that generates a video descriptor including the additional feature and the difference feature upon volume of the difference feature information amount being smaller that a certain criterion, wherein the additional feature extraction unit calculates the additional feature only when the volume of the difference feature information amount is smaller than the certain criterion.