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