Hash-based media search

Abstract

A method of identifying an item of video content involves providing a spatial hash value and a temporal hash value for each image in a video collection. Each hash value is based on a measure of the entropy in differences between pixel values. A table of the pair of hash values against timecode is created and ordered according to one of the hash values. A search for a given pair of hash values can then be confined to that part of the table that matches the first value.

1 . A system for identifying an item of video content, the apparatus comprising:
 a query sequence processor configured to define a plurality of query sequences by a traveling window of search images of a plurality of temporally separated images of the video content, and to form a pair of search hash values for each of the plurality of query sequences, wherein the pair of search hash values comprises:
 a spatial search hash value relating to difference values between pixel values within each search image in the respective query sequence, and 
 a temporal search hash value relating to difference values between a pixel value in a first search image in the respective query sequence and a corresponding pixel value in a second search image that is temporally separated within the respective query sequence; 
   a relational database configured to store a look up table that defines ordered search data corresponding to a first hash value of the pair of search hash values for each query sequence; and   a search processor configured to search the ordered search data that corresponds to a sought hash value of the first hash value of the pair of search hash values to locate a sought hash value of a second hash value of the respective pair of hash values.   
     
     
         2 . The system according to  claim 1 , wherein the query sequence processor is configured to execute instructions stored on a memory to define the plurality of query sequences and to determine the pair of search hash values for each of the plurality of query sequences. 
     
     
         3 . The system according to  claim 1 ,
 wherein each of the respective spatial search hash value comprises a function of a measure of entropy in the respective difference values between the pixel values within each search image in the respective query sequence, and   wherein each of the respective temporal search hash values comprises a function of a measure of entropy in the respective difference values between the pixel value in a plurality of first search images in the respective query sequence and the corresponding pixel value in a plurality of second search images in the respective query sequence.   
     
     
         4 . The system according to  claim 1 ,
 wherein the relational database is further configured to store a first look up table that defines an association between temporal positions of each of the plurality of query sequences in the plurality of temporally separated search images and respective hash value pairs ordered according to the respective first has values of each pair of search hash values, and   wherein the second look up table defines a portion of the ordered search data in the first look up table that corresponds to a particular value of the first hash value of each pair of search hash values each of the plurality of query sequences.   
     
     
         5 . The system according to  claim 4 , wherein the search processor coupled is configured to search only the portion of ordered search data in the second look up table that corresponds to the sought hash value of the respective first hash value to locate the sought hash value of the respective second hash value. 
     
     
         6 . The system according to  claim 1 , wherein each respective spatial sought hash value comprises a function of a measure of entropy in difference values between pixel values within a sought image aggregated over sought images within a sought query sequence. 
     
     
         7 . The system according to  claim 1 , wherein each respective temporal sought hash value comprises a function of a measure of entropy in difference values between a pixel value in a first sought image and a pixel value in a second sought image that temporally separated from the first sought image, with the difference values being aggregated over sought images within a sought query sequence. 
     
     
         8 . The system according to  claim 1 ,
 wherein a hash value comprises a function of frequencies of occurrence of difference values between pixel values, and   wherein respective spatial difference-value frequencies are summed over a group of search images to form the respective spatial search hash values and over a sought sequence to form the respective sought hash value.   
     
     
         9 . The system according to  claim 1 ,
 wherein a hash value comprises a function of frequencies of occurrence of difference values between pixel values, and   wherein respective temporal difference-value frequencies are summed over a group of search images to form the temporal search hash value and over a sought sequence to form the respective sought hash value.   
     
     
         10 . The system according to  claim 1 , wherein the query sequence processor is configured to form the difference values between pixel values within each search image based on one or more respective fingerprints of the respective search images. 
     
     
         11 . A system for identifying an item of video content, the apparatus comprising:
 a query sequence processor configured to define a plurality of query sequences by a traveling window of search images of a plurality of temporally separated images of the video content, and to form a pair of search hash values for each of the plurality of query sequences, wherein the pair of search hash values comprises a spatial search hash value and a temporal search hash value;   a relational database configured to store a look up table that defines ordered search data corresponding to a first hash value of the pair of search hash values for each query sequence; and   a search processor configured to search the ordered search data that corresponds to a sought hash value of the first hash value of the pair of search hash values to locate a sought hash value of a second hash value of the respective pair of hash values.   
     
     
         12 . The system according to  claim 11 , wherein the query sequence processor is configured to execute instructions stored on a memory to define the plurality of query sequences and to determine the pair of search hash values for each of the plurality of query sequences. 
     
     
         13 . The system according to  claim 11 , wherein the query sequence processor is further configured to:
 form each respective spatial search hash value based on difference values between pixel values within each search image in the respective query sequence; and   form each respective temporal search hash value based on difference values between a pixel value in a first search image in the respective query sequence and a corresponding pixel value in a second search image that is temporally separated within the respective query sequence.   
     
     
         14 . The system according to  claim 13 ,
 wherein each of the respective spatial search hash value comprises a function of a measure of entropy in the respective difference values between the pixel values within each search image in the respective query sequence, and   wherein each of the respective temporal search hash values comprises a function of a measure of entropy in the respective difference values between the pixel value in a plurality of first search images in the respective query sequence and the corresponding pixel value in a plurality of second search images in the respective query sequence.   
     
     
         15 . The system according to  claim 13 ,
 wherein the relational database is further configured to store a first look up table that defines an association between temporal positions of each of the plurality of query sequences in the plurality of temporally separated search images and respective hash value pairs ordered according to the respective first has values of each pair of search hash values, and   wherein the second look up table defines a portion of the ordered search data in the first look up table that corresponds to a particular value of the first hash value of each pair of search hash values each of the plurality of query sequences.   
     
     
         16 . The system according to  claim 15 , wherein the search processor coupled is configured to search only the portion of ordered search data in the second look up table that corresponds to the sought hash value of the respective first hash value to locate the sought hash value of the respective second hash value. 
     
     
         17 . The system according to  claim 11 , wherein each respective spatial sought hash value comprises a function of a measure of entropy in difference values between pixel values within a sought image aggregated over sought images within a sought query sequence. 
     
     
         18 . The system according to  claim 11 , wherein each respective temporal sought hash value comprises a function of a measure of entropy in difference values between a pixel value in a first sought image and a pixel value in a second sought image that temporally separated from the first sought image, with the difference values being aggregated over sought images within a sought query sequence. 
     
     
         19 . The system according to  claim 11 ,
 wherein a hash value comprises a function of frequencies of occurrence of difference values between pixel values, and   wherein respective spatial difference-value frequencies are summed over a group of search images to form the respective spatial search hash values and over a sought sequence to form the respective sought hash value.   
     
     
         20 . The system according to  claim 11 ,
 wherein a hash value comprises a function of frequencies of occurrence of difference values between pixel values, and   wherein respective temporal difference-value frequencies are summed over a group of search images to form the temporal search hash value and over a sought sequence to form the respective sought hash value.   
     
     
         21 . The system according to  claim 11 , wherein the query sequence processor is configured to form the difference values between pixel values within each search image based on one or more respective fingerprints of the respective search images. 
     
     
         22 . A system for identifying an item of video content, the apparatus comprising:
 means for defining a plurality of query sequences by a traveling window of search images of a plurality of temporally separated images of the video content;   means for forming a pair of search hash values for each of the plurality of query sequences, wherein the pair of search hash values comprises:
 a spatial search hash value relating to difference values between pixel values within each search image in the respective query sequence, and 
 a temporal search hash value relating to difference values between a pixel value in a first search image in the respective query sequence and a corresponding pixel value in a second search image that is temporally separated within the respective query sequence; 
   means for storing a look up table that defines ordered search data corresponding to a first hash value of the pair of search hash values for each query sequence; and   means for searching the ordered search data that corresponds to a sought hash value of the first hash value of the pair of search hash values to locate a sought hash value of a second hash value of the respective pair of hash values.