The video descriptor generation device includes a first extraction unit, a second extraction unit, and a feature combining unit. The first extraction unit extracts a first feature for each picture which is a frame or a field of a video. The second extraction unit extracts a second feature from a region defined by an edge of an image included in the video. The feature combining unit combines the first feature and the second feature to generate a video descriptor.