Media fingerprinting and identification system

1. A method of searching reference multimedia signatures that represent audio and video content of reference multimedia clips for a corresponding query multimedia clip, the method comprising:

generating an N dimension signature based on an N dimension descriptor and a traversal hash signature based on a combination of dimensions of the N dimension descriptor for each feature identified in a set of reference multimedia clips;

storing each N dimension signature and a link to a corresponding reference multimedia clip at a location in a reference signature database addressable by the traversal hash signature;

generating an N dimension query signature based on an N dimension query descriptor and a traversal hash query signature based on a combination of dimensions of the N dimension query descriptor for a query multimedia clip; and

searching the reference signature database using the traversal hash query signature to find similar signatures that are within a specified signature distance, wherein the similar signatures are aggregated in a candidate list of closely matching signatures that correspond to similar reference multimedia clips.

2. The method of claim 1 , wherein a multimedia clip comprises image pixel data, video pixel data, or audio waveform data.

3. The method of claim 1 , further comprising:

generating an N dimension descriptor for at least one feature of a reference multimedia clip; and

quantizing each dimension of the N dimension descriptor to generate the N dimension signature.

4. The method of claim 3 , further comprising:

creating a Bx by By grid having Bx*By blocks located at the center of the at least one feature, the at least one feature having dimensions specified by a scalex and a scaley multiplication factors, each block having a Cx by Cy pixel grid;

computing multiple intensity differences for each pixel in the Cx by Cy pixel grid to another pixel in both x and y directions for a specified pixel offset that is greater than 1;

computing weighted sum combinations of the multiple intensity differences as x-gradient values and as a y-gradient values; and

generating the N dimension descriptor as a concatenation of combinations of the x-gradient values and y-gradient values for each block of the Bx*By blocks.

5. The method of claim 4 , wherein the combinations of the x-gradient values and y-gradient values are combinations of a positive sum of x-gradient value, a negative sum of x-gradient values, a positive sum of y-gradient values, and a negative sum of y-gradient values for each of the Bx*By blocks, wherein the N dimension descriptor is an N=4*Bx*By dimension descriptor.

6. The method of claim 4 , wherein the scalex multiplication factor or the scaley multiplication factor or both are adjusted to account for an expected error margin of +/−D %, wherein D % represents effects of image distortions.

7. The method of claim 4 , wherein the location of the center of the feature is adjusted to account for an expected error margin of +/−D %, wherein D represents effects of image distortions.

8. The method of claim 1 , further comprising:

combining multiple dimensions of the N dimension descriptor to form combined values; and

comparing the combined values with a traversal hash threshold to form the traversal hash signature.

9. The method of claim 8 , further comprising:

combining multiple dimensions of the N dimension query descriptor to form query combined values; and

comparing the query combined values with the traversal hash threshold to form the traversal hash query signature.

10. The method of claim 1 , wherein the traversal hash signature includes additional bits representing a quadrant having the center of an underlying feature and a scale of the underlying feature.

11. The method of claim 1 , wherein the traversal hash signature includes a polarity value that indicates whether the underlying feature is a light coloring on a dark background or a dark coloring on a light background.

12. The method of claim 1 , further comprising:

sorting the candidate list according to a count of the number of times a closely matching signature appears in the candidate list to find likely reference multimedia clip match signatures.

13. The method of claim 12 , further comprising:

determining a plurality of scores, wherein each score is based on a distance between the N dimension query signature and a different one of the likely reference multimedia clip match signatures; and

comparing the plurality of scores with a score threshold to determine whether a reference multimedia clip associated with a score is a true positive match or a false positive match.

14. The method of claim 1 , further comprising:

counting a frequency of occurrence of multimedia clip identifications associated with each closely matching signature in the candidate list; and

sorting by the frequency of occurrence to find T likely reference multimedia clip matches, where T=1 or T>1.

15. The method of claim 1 , further comprises:

generating features from the multimedia clips;

computing one or more descriptors for each of the generated features; and

computing one or more signatures and associated traversal hash signatures for each of the one or more descriptors.

16. The method of claim 1 , further comprising:

storing a secondary copy of each N dimension signature for each corresponding reference multimedia clip according to a multimedia id and timestamp as a secondary index, wherein the traversal hash signature is a primary index.

17. The method of claim 16 , further comprises,

comparing the N dimension query signature to signatures in the reference signature database associated with the traversal hash signature to find similar signatures that are within a specified signature distance.

18. A method of forming accurate descriptors of features in multimedia clips, the method comprising:

determining a scale and a location of the center parameters for each feature of a plurality of features selected from a frame from a multimedia clip;

creating a Bx by By grid having Bx*By blocks located at the center of each feature and each block having a Cx by Cy pixel grid;

computing for each block, functions of multiple intensity differences between each pixel in a block's Cx by Cy pixel grid and another pixel for a specified pixel offset that is greater than 1 and based on the scale and location of center parameters;

generating a first N dimension descriptor as a concatenation of the functions for each block of the Bx*By blocks; and

adjusting individually the scale and location of center parameters to account for an expected error margin due to image distortions to generate at least a second N dimension descriptor as a concatenation of the functions for each block of the Bx*By blocks as adjusted according to the expected error margin.

19. The method of claim 18 , wherein the scale is specified by a scalex and a scaley multiplication factors and the multiple intensity differences are computed in both x and y directions based on the scalex, scaley, and location of center parameters.

20. The method of claim 19 , wherein the functions of the multiple intensity differences are combinations of a positive sum of x-gradient value, a negative sum of x-gradient values, a positive sum of y-gradient values, and a negative sum of y-gradient values for each of the Bx*By blocks, wherein the x-gradient values are weighted sum of combinations of the multiple intensity differences in the x direction and the y-gradient values are weighted sum of combinations of the multiple intensity differences in the y direction and N is equal to 4*Bx*By.

21. A non-transitory computer readable medium storing a computer program which causes a computer system to perform a method of searching reference multimedia signatures that represent audio and video content of reference multimedia clips for a corresponding query multimedia clip, the method comprising:

generating an N dimension signature based on an N dimension descriptor and a traversal hash signature based on a combination of dimensions of the N dimension descriptor for each feature identified in a set of reference multimedia clips;

storing each N dimension signature and a link to a corresponding reference multimedia clip at a location in a reference signature database addressable by the traversal hash signature;

generating an N dimension query signature based on an N dimension query descriptor and a traversal hash query signature based on a combination of dimensions of the N dimension query descriptor for a query multimedia clip; and

searching the reference signature database using the traversal hash query signature to find similar signatures that are within a specified signature distance, wherein the similar signatures are aggregated in a candidate list of closely matching signatures that correspond to similar reference multimedia clips.

22. The non-transitory computer readable medium of claim 21 , further comprising:

generating an N dimension descriptor for at least one feature of a reference multimedia clip;

creating a Bx by By grid having Bx*By blocks located at the center of the at least one feature, the at least one feature having dimensions specified by a scalex and a scaley multiplication factors, each block having a Cx by Cy pixel grid;

computing multiple intensity differences for each pixel in the Cx by Cy pixel grid to another pixel in both x and y directions for a specified pixel offset that is greater than 1;

computing weighted sum combinations of the multiple intensity differences as x-gradient values and as a y-gradient values;

generating the N dimension descriptor as a concatenation of combinations of the x-gradient values and y-gradient values for each block of the Bx*By blocks; and

quantizing each dimension of the N dimension descriptor to generate the N dimension signature.

23. The non-transitory computer readable medium of claim 22 , wherein the combinations of the x-gradient values and y-gradient values are combinations of a positive sum of x-gradient value, a negative sum of x-gradient values, a positive sum of y-gradient values, and a negative sum of y-gradient values for each of the Bx*By blocks, wherein the N dimension descriptor is an N=4*Bx*By dimension descriptor.

24. The non-transitory computer readable medium of claim 22 , wherein the scalex multiplication factor or the scaley multiplication factor or both are adjusted to account for an expected error margin of +/−D %, wherein D % represents effects of image distortions.

25. The non-transitory computer readable medium of claim 22 , wherein the location of the center of the feature is adjusted to account for an expected error margin of +/−D %, wherein D % represents effects of image distortions.

26. The non-transitory computer readable medium of claim 21 , further comprising:

storing a secondary copy of each N dimension signature for each corresponding reference multimedia clip according to a multimedia id and timestamp as a secondary index, wherein the traversal hash signature is a primary index.

27. The non-transitory computer readable medium of claim 26 , further comprises:

comparing the N dimension query signature to signatures in the reference signature database associated with the traversal hash signature to find similar signatures that are within a specified signature distance.

28. A method for creating a media database, the method comprising:

generating a plurality of signatures from descriptors of selected media content;

selecting a signature from the plurality of signatures based on a distribution of bit values in the selected signature and on values of a corresponding descriptor;

generating a traversal hash signature from the corresponding descriptor; and

storing the selected signature in a media database at a location within a set of contiguous locations based on the traversal hash signature used as a primary index.

29. The method of claim 28 , further comprising:

storing a second copy of the selected signature in the media database at another location within a set of contiguous locations based on a multimedia identification value and a timestamp of the media content associated with the selected signature.

30. The method of claim 28 , further comprising:

selecting a signature from the plurality of signatures that are associated with a corresponding descriptor made up of descriptor values and identified by a function of the descriptor values that meets or exceeds a threshold value.

31. The method of claim 28 , further comprising:

computing an average distance between a feature center location and M selected near features' center locations to determine a spatial diversity value, wherein the average distance, or “closeness” indicates the density of features in terms of location; and

eliminating signatures that are too close based on an established threshold for closeness.

32. The method of claim 28 , further comprising:

computing signature bit distance values between each signature for a current frame in the media database and each signature in a following frame in the media database;

determining whether the signature bit distance values are less than or equal to a first robustness threshold R; and

eliminating signatures that have bit distance values greater than R that are not temporally robust.

33. The method of claim 28 , further comprising:

computing hash bit distance values between each traversal hash signature for a current frame in the media database and each traversal hash signature in a following frame in the media database;

determining whether the hash bit distance values are less than or equal to a second robustness threshold Q; and

eliminating traversal hash signatures that have bit distance values greater than Q that are not temporally robust.