A video signature extraction device includes an each-picture feature extraction unit which extracts a feature of each picture, which is a frame or a field, as an each-picture visual feature from an input video; a time axial direction change region extraction unit which analyzes an image change in a time direction with respect to predetermined regions in a picture from the video, obtains a region having a large image change, and generates change region information which is information designating the region; an each-region feature extraction unit which extracts a feature of the region corresponding to the change region information as an each-region visual feature from the video; and a multiplexing unit which multiplexes the each-picture visual feature, the each-region visual feature, and the change region information, and generates a video signature.