A problem of degradation in the accuracy of video matching, which is caused when videos contain video patterns commonly appearing in various videos or video patterns in which features cannot be acquired stably, is solved. In order to solve this problem, a visual feature extraction unit extracts a visual feature to be used for identification of a video based on features of a plurality of pairs of sub-regions in the video, and a confidence value calculation unit calculates a confidence value of the visual feature based on the features of the plurality of pairs of sub-regions. When matching is performed, visual features are compared with each other in consideration of the confidence value.