1. A video signature extraction device, comprising: a memory storing computer program instructions; and one or more computer processors configured to process the computer program instructions to: extract a first feature as an each-picture visual feature from a first picture, among a plurality of pictures each of the plurality of pictures being a frame or a field of an input video; calculate an image change value in a time direction for each of a plurality of regions included in the first picture, among the plurality of pictures; obtain one or more change regions having the image change value greater than a predetermined threshold among the each of the plurality of the regions; generate change region information which designates the obtained one or more change regions; extract a second feature as an each-region visual feature from each of the one or more change regions designated by the change region information; and extract a video signature including the each-picture visual feature, the each-region visual feature, and the change region information.