Near-duplicate video retrieval

Abstract

A similarity of a first video to a second video may be identified automatically. Images are received from the videos, and divided into sub-images. The sub-images are evaluated based on a feature common to each of the sub-images. Binary representations of the images may be created based on the evaluation of the sub-images. A similarity of the first video to the second video may be determined based on a number of occurrences of a binary representation in the first video and the second video.

1 - 20 . (canceled) 
     
     
         21 . A system comprising:
 one or more processors;   memory coupled to the one or more processors; and   an analysis component stored in the memory and operable on the one or more processors, the analysis component configured to:
 receive a first image from a first video; 
 divide the first image into a first plurality of sub-images; 
 determine a feature common to the first plurality of sub-images; 
 score the first plurality of sub-images based at least in part on the feature; 
 create a first binary representation of the first image based at least in part on the scoring of the first plurality of sub-images; 
 create a second binary representation of a second image based at least in part on a scoring of a second plurality of sub-images from the second image; 
 generate a visual shingle for the first video using the first binary representation of the first image and the second binary representation of the second image; and 
 determine a similarity of the first video to a second video based at least in part on a number of occurrences of the visual shingle in the first video and a number of occurrence of the visual shingle in the second video. 
   
     
     
         22 . A system as recited in  claim 21 , wherein the analysis component is further configured to create the second binary representation of the second image by performing steps comprising:
 receiving the second image from the first video;   dividing the second image into the second plurality of sub-images;   determining a feature common to the second plurality of sub-images;   scoring the second plurality of sub-images based at least in part on the feature common to the second plurality of sub-images; and   creating the second binary representation of the second image using the scoring of the second plurality of sub-images.   
     
     
         23 . A system as recited in  claim 21 , wherein an individual binary value of the first binary representation represents a rank relationship between a first sub-image from the first plurality of sub-images to at least a second sub-image from the first plurality of sub-images. 
     
     
         24 . A system as recited in  claim 21 , wherein the analysis component is further configured to output the similarity of the first video to the second video. 
     
     
         25 . A system as recited in  claim 21 , wherein the analysis component is configured to generate the visual shingle for the first video by combining the first binary representation of the first image with the second binary representation of the second image. 
     
     
         26 . A system as recited in  claim 21 , wherein the analysis component is configured to divide the first image into the first plurality of images by dividing the first image into a two-dimensional matrix that includes the first plurality of sub-images. 
     
     
         27 . A system as recited in  claim 21 , wherein the feature common to the first plurality of sub-images comprises a global feature representing a gray-level intensity of information for individual sub-images from the first plurality of sub-images. 
     
     
         28 . A system as recited in  claim 21 , wherein the analysis component is configured to determine the similarity by:
 generating a first histogram based at least in part on the number of occurrences of the visual shingle in the first video;   generating a second histogram based at least in part on the number of occurrences of the visual shingle in the second video; and   determining the similarity by comparing the first histogram to the second histogram.   
     
     
         29 . A system as recited in  claim 21 , wherein the analysis component is further configured to:
 determine a similarity of the first video to a third video based at least in part on the number of occurrences of the visual shingle in the first video and a number of occurrence of the visual shingle in the third video; and   rank the first video, the second video, and the third video based at least in part on the number of occurrences of the visual shingle in the first video, the number of occurrences of the visual shingle in the second video, and the number of occurrences of visual shingle in the third video.   
     
     
         30 . A method comprising:
 receiving first video that includes at least a first image and a second image;   scoring a first plurality of sub-images from the first image based at least in part on a feature common to the first plurality of sub-images;   scoring a second plurality of sub-images from the second image based at least in part on a feature common to the second plurality of sub-images;   creating a binary representation of the first image based at least in part on the scoring of the first plurality of sub-images;   creating a binary representation of the second image based at least in part on the scoring of the second plurality of sub-images;   generating a visual shingle for the first video based at least in part the binary representation of the first image and the binary representation of the second image; and   determining a similarity of the first video to a second video using the visual shingle.   
     
     
         31 . A method as recited in  claim 30 , wherein determining the similarity comprises determining a number of occurrences of the visual shingle in the first video and a number of occurrences of the visual shingle in the second video. 
     
     
         32 . A method as recited in  claim 30 , wherein generating the visual shingle for the first video comprises combining the binary representation of the first image with the binary representation of the second image. 
     
     
         33 . A method as recited in  claim 30 , further comprising extracting the first image and the second image from the first video. 
     
     
         34 . A method as recited in  claim 30 , wherein the feature common to the first plurality of sub-images comprises at least one of special information, color information, or temporal information. 
     
     
         35 . A method as recited in  claim 30 , wherein determining the similarity comprises:
 generating a first histogram based at least in part on a number of occurrences of the visual shingle in the first video;   generating a second histogram based at least in part on a number of occurrences of the visual shingle in the second video; and   determining the similarity by comparing the first histogram to the second histogram.   
     
     
         36 . A method as recited in  claim 30 , further comprising outputting the similarity. 
     
     
         37 . One or more computer-readable media storing computer-executable instructions that, when executed on one or more processors, configure a computer to perform acts comprising:
 receiving a first video that includes at least a first image and a second image;   creating a binary representation of the first image based at least in part on a feature that is common to a plurality of sub-images of the first image;   creating a binary representation of the second image based at least in part on a feature that is common to a plurality of sub-images of the second image; and   generating a visual shingle for the first video based at least in part the binary representation of the first image and the binary representation of the second image; and   determining a similarity of the first video to a second video using the visual shingle.   
     
     
         38 . One or more computer-readable media as recited in  claim 37 , wherein determining the similarity comprises determining a number of occurrences of the visual shingle in the first video and a number of occurrences of the visual shingle in the second video. 
     
     
         39 . One or more computer-readable media as recited in  claim 37 , wherein generating the visual shingle for the first video comprises combining the binary representation of the first image with the binary representation of the second image. 
     
     
         40 . One or more computer-readable media as recited in  claim 37 , the acts further comprising outputting the similarity of the first video to the second video.