A video search device, comprising: a receiver for receiving input of a still image in which a reference object is depicted, a first reference position and a second reference position being marks of the reference object in the still image, and a first target position and a second target position within a frame image contained in a video; an extractor for extracting a reference image, being an extracted image of the reference object and being an image depicted in a reference region, the boundary line of which divides the reference object from a background in the still image, based on the first reference position and the second reference position; and a searcher for searching for similar frame images contained in videos and in which local images similar to the reference image are depicted, finding a first start position and a second start position, the locations of which correspond to the first reference position and the second reference position in the reference region, in a local region, being a region in which the local image similar to the reference image is depicted, in the similar frame image, tracing a first movement track along which a first noteworthy pixel, being a pixel positioned at the fist start position in the similar frame image, moves and a second movement track along which a second noteworthy.pixel, being a pixel positioned at the second start position in the similar frame image, moves in the video, by scanning frame images contained in the video including the similar frame image from the similar frame image, and searching a target frame image at which the first movement track reaches the neighborhood of the first target position and the second movement track reaches the neighborhood of the second target position. a receiver for receiving input of a still image in which a reference object is depicted, a first reference position and a second reference position being marks of the reference object in the still image, and a first target position and a second target position within a frame image contained in a video; an extractor for extracting a reference image, being an extracted image of the reference object and being an image depicted in a reference region, the boundary line of which divides the reference object from a background in the still image, based on the first reference position and the second reference position; and a searcher for searching for similar frame images contained in videos and in which local images similar to the reference image are depicted, finding a first start position and a second start position, the locations of which correspond to the first reference position and the second reference position in the reference region, in a local region, being a region in which the local image similar to the reference image is depicted, in the similar frame image, tracing a first movement track along which a first noteworthy pixel, being a pixel positioned at the fist start position in the similar frame image, moves and a second movement track along which a second noteworthy.pixel, being a pixel positioned at the second start position in the similar frame image, moves in the video, by scanning frame images contained in the video including the similar frame image from the similar frame image, and searching a target frame image at which the first movement track reaches the neighborhood of the first target position and the second movement track reaches the neighborhood of the second target position.