PROJECTION BASED HASHING THAT BALANCES ROBUSTNESS AND SENSITIVITY OF MEDIA FINGERPRINTS

• US 20110299721A1
• Filed: 05/25/2011
• Published: 12/08/2011
• Est. Priority Date: 06/02/2010
• Status: Active Grant

• Current Assignee: Dolby Laboratories Licensing Corporation (Dolby Laboratories Incorporated)
• Original Assignee: Dolby Laboratories Licensing Corporation (Dolby Laboratories Incorporated)
• Inventors: Radhakrishnan, Regunathan, Bauer, Claus, He, Junfeng
• Granted Patent: US 8,542,869 B2
• Time in Patent Office: Days
• US Class Current: 382/100
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames

Abstract

Multiple candidate feature components of media content or projection matrices (or other hash functions, e.g., non-linear projections) are identified. Each of the candidate projection matrices (or other hash functions) includes an array of coefficients that relate to the candidate features. A subgroup of the candidate features or the projection matrices (or other hash functions) are selected based at least partially on an optimized combination of at least two characteristics of the candidate features or projection matrices (or other hash functions). Media fingerprints that uniquely identify the media content are derived from the selected optimized subgroup. Optimal projection matrices (or other hash functions) may be designed. Performance or sensitivity (e.g., search time) characteristics of the fingerprints are thus balanced with robustness characteristics thereof.

Claims

1. A method, comprising:

identifying a plurality of candidate features that are components of one or more of audio or video content and a plurality of candidate projection matrices, wherein each of the candidate projection matrices comprise an array of coefficients that relate to the candidate features;

selecting a subgroup of the projection matrices, based at least in part on an optimized combination of at least two characteristics of the candidate features or the projection matrices; and

deriving fingerprints that uniquely identify the audio or video content from the selected optimized projection matrices subgroup.

2. The method as recited in claim 1 wherein the selection of the subgroup of the projection matrices based, at least in part, on the optimized combination of characteristics thereof comprises:

computing a performance measurement for each of at least two subgroups of the plurality of candidate features or the projection matrices wherein the performance measurement is based, at least in part, on a sensitivity value and a robustness value associated with each of the at least two subgroups, and a parameter related to one or more of a cost/benefit balancing or a trade off between the sensitivity value and a robustness value;

comparing the performance measurements of the at least two feature subgroups or the projection matrices; and

based on the comparison, identifying a performance measurement that corresponds to one of the at least two feature subgroups or the projection matrices as an optimal performance measurement;

wherein one feature subgroup is selected from among the at least two feature subgroups or the projection matrices based, at least in part, on the identification of the optimal performance measurement.

3. The method as recited in claim 2 wherein:

a population of the plurality of candidate projection matrices comprises a number N;

the optimal subgroup is populated by a number W of the N projection matrices;

the number N is greater than the number W; and

the selecting step comprises, upon the selection of a most optimal feature subgroup from among the N candidate features or the projection matrices, recursively performing the selecting step, wherein a subsequent next most optimal, in relation to the most optimal, subgroup is selected from among the remaining candidate features or the projection matrices.

4. The method as recited in claim 3 wherein the selecting step further comprises continuing the recursive repetition over subsequently remaining candidate features or the projection matrices until the W optimal subgroups are all identified or selected.

5. The method as recited in claim 4 wherein the recursive repetition comprises:

a) computing a first subgroup performance measurement for a current subgroup of the projection matrices based, at least in part, on a robustness value and a sensitivity value of the current candidate subgroup;

b) computing a subgroup performance measurement for a candidate subgroup, which is subsequent to the first candidate subgroup, from the remaining projection matrices based, at least in part, on the robustness value and the sensitivity value of the subsequent candidate subgroup;

c) combining each of the candidate projection matrices that remain after the first current candidate projection matrix subgroup performance measurement computation with the original current subgroup, wherein new candidate projection matrix subgroups, each subsequent in relation to the original candidate features or the projection matrices subgroup and each uniquely corresponding to one and only one of each of the remaining candidate projection matrices, is formed; and

d) computing a subgroup performance measurement for each of the new candidate projection subgroups, based, at least in part, on the robustness value and the sensitivity value of the subsequent candidate subgroup.

6. The method as recited in claim 5 wherein the recursive repetition comprises:

e) comparing each of the new subgroup performance measurements with the current or original subgroup of the candidate features or the projection matrices and each other of the new subgroup performance measurements;

wherein it is determined whether one of the new computed subgroup performance measurements exceeds or is more optimal than the current or original subgroup of the candidate features or the projection matrices or each of the other new computed subgroup performance measurements.

7. The method as recited in claim 6 wherein the recursive repetition further comprises:

f) upon the comparison determining that one of the new subgroup performance measurements exceeds or is more optimal than the current or original subgroup of the or each of the other new computed subgroup performance measurements, updating the current or original candidate subgroup, wherein the new subgroup, which is determined to have the performance measurement that exceeds or is more optimal than the current or original subgroup, is added thereto to comprise an updated current optimized subgroup.

8. The method as recited in claim 7 wherein the recursive repetition further comprises:

g) upon the comparison, further determining whether W items remain in the optimal subgroup.

9. The method as recited in claim 8 wherein the recursive repetition further comprises:

h) upon the further determination that less than W projection matrices remain in the optimal subgroup, adding one additional candidate projection matrix, to the most optimal subgroup, wherein a newly updated current optimal subgroup of candidate projection matrices s formed; and

i) repeating steps a) through g) over the newly updated current optimal projection matrices subgroup.

10. The method as recited in claim 2 wherein the performance measurement computation for each of at least two subgroups of the plurality of candidate features comprises:

deriving a first fingerprint codeword based on a subgroup of features in an original instance of media content;

deriving one or more additional fingerprint codewords based on a subgroup of features in a content instance that comprises a modification of the original media content; and

for each of the one or more additional fingerprint codewords derived from the modified content instance, computing a difference between each of the one or more additional codewords, wherein a set of corresponding difference values is generated, wherein the corresponding difference values, wherein the difference values relate to a Hamming similarity between the first fingerprint codeword and the one or more additional codewords;

wherein the robustness value is based, at least in part, on the computed difference values.

11. The method as recited in claim 2 wherein the performance measurement computation for each of at least two subgroups of the plurality of candidate features or the projection matrices wherein the performance measurement is based, at least in part, on a sensitivity value and a robustness value associated with each of the at least two subgroups further comprises:

deriving a first set of projected values that correspond to the original media content instance based on the subgroup of features in the original instance of media content and the projection matrices;

deriving a second set of projected values that correspond to the modified media content instance based on the subgroup of features in the modified instance of media content and the projection matrices;

computing a difference between one or more of;

the features in the original media content instance and the features in the modified media content instance;

or

the first set of original media content instance projected values and the second set of modified media content instance projected values;

wherein the robustness is determined based on the computed difference.

12. The method as recited in claim 2, further comprising computing the sensitivity value of the optimal subgroup;

wherein the computation of the optimal subgroup sensitivity comprises;

for each image of a plurality of images, or for each audio content portion of a plurality of audio content portions, which respectively comprise the video or audio content, deriving a plurality of fingerprint codewords, each codeword comprising a number n of bits, based on the optimal subgroup of image or audio content portion features;

analyzing a distribution of the codewords over a set of possible codewords that each comprise n bits; and

determining the sensitivity value based on a minimal distribution of the codewords over the set of possible n-bit codewords.

13. The method as recited in claim 1, further comprising:

identifying a plurality of candidate projection matrices that relate to values, which correspond to one or more features that comprise components of underlying media content;

selecting an optimal subgroup of projection matrices from the plurality of candidate projection matrices;

wherein the selection of the optimal subgroup of the projection matrices is based, at least in part, on the optimized combination of characteristics thereof comprises dynamic programming; and

deriving fingerprints based on the selected optimal projection matrices.

14. The method as recited in claim 13, wherein the selecting step comprises:

computing a performance measurement for each subgroup of at least two subgroups of the plurality of candidate projection matrices;

wherein the performance measurement is based, at least in part, on;

a sensitivity value associated with each of the subgroups;

a robustness value associated with each of the subgroups; and

a parameter that relates to a balance of, or a trade-off between the sensitivity value and the robustness value;

identifying an optimal performance measurement for at least one of the subgroups; and

selecting the identified optimally performing subgroup for the plurality of projection matrices.

15. A method comprising:

extracting a plurality of N features from media content that comprises one or more of audio or video content, wherein N comprises a first positive integer;

computing a set of K optimal projection matrices from the N media content features, wherein K comprises a second positive integer; and

deriving media fingerprints from the media content with the computed K optimal projection matrices.

16. The method as recited in claim 15, wherein the computation of the K optimal projection matrices from the N media content features comprises:

balancing a sensitivity attribute of the media fingerprints and a robustness attribute of the media fingerprints;

wherein the sensitivity attribute and the robustness attribute are balanced with a cost function that optimizes a trade-off between the sensitivity attribute and the robustness attribute.

17. The method as recited in claim 15, wherein the computation of the K optimal projection matrices from the N media content features comprises:

computing a measurement of the sensitivity attribute based on a current set of the K optimal projection matrices and the set of N extracted features.

18. The method as recited in claim 17, wherein the sensitivity measurement is computed based, at least in part, on mutual information that is shared within, or exists between elements of, the set of K projected values.

19. The method as recited in claim 18, wherein the sensitivity measurement computation comprises:

projecting each of the N extracted features onto the current set of K optimal projection matrices.

20. The method as recited in claim 18, wherein the mutual information comprises a negentropy attribute that relates to the current set of K candidate projection matrices.

21. The method as recited in claim 20 wherein the sensitivity measurement computation further comprises:

computing a set of non-quadratic function values for each of the K optimal projection matrices;

computing a first average over the computed non-quadratic function values;

computing a non-quadratic function value for a set K pseudorandom values that have a Gaussian distribution;

computing a second average for the non-quadratic function values over the set K Gaussian-distributed pseudorandom values; and

computing a difference between the first average and the second average, wherein the negentropy attribute relates to the computed difference.

22. The method as recited in claim 20, wherein the computation of the K optimal projection matrices from the N media content features comprises:

computing a measurement of the robustness attribute based on a current set of the K candidate projection matrices and the set of N extracted features.

23. The method as recited in claim 22, where in the robustness measure computation comprises computing a Laplacian feature matrix that is based on the set of N extracted features and a set of weights, wherein the Laplacian feature matrix relates to a spatial neighborhood property of an area that surrounds or is in proximity to the extracted content features.

24. The method as recited in claim 23, wherein the Laplacian feature matrix computation comprises:

determining a set of weighting values that relate to the spatial neighborhood; and

computing a Laplacian Matrix based, at least in part, on the set of weighting values; and

computing a matrix product between based on the extracted features and the Laplacian matrix.

25. The method as recited in claim 23, further comprising:

updating the current set of K optimal projection matrices based, at least in part, on one or more of;

the computation of the robustness measurement;

or

the computation of the sensitivity measurement.

26. The method as recited in claim 25, wherein the current set of K optimal projection matrices are updated based on at least one of:

one or more Karush_Kuhn_Tucker (KKT) conditions that are imposed on the cost function, which relate to a combination of the robustness and sensitivity measurement;

or a Newton approximation method.

27. The method as recited in claim 26, further comprising:

comparing the current set of optimal projection matrices to a previous set of projection matrices wherein, prior to the computation of the current optimal projection matrices set, the previous set comprises a prior optimal projection matrices set; and

computing a difference between the current set of optimal projection matrices and the previous set of projection matrices.

28. The method as recited in claim 27, further comprising:

comparing the difference that is computed between the current set of optimal projection matrices and the previous set of projection matrices to a threshold value; and

upon the comparison, wherein the difference between the current set of optimal projection matrices and the previous set of projection matrices is less than the threshold value, initializing the derivation of the media fingerprints from the media content with the current optimal projection matrices set.

29. The method as recited in claim 28 wherein, upon the comparison, wherein the difference between the current set of optimal projection matrices and the previous set of projection matrices is greater than or equal to the threshold value, the method further comprises the steps of:

a) repeating the computation of the optimal projection matrices set wherein the current set of optimal projection matrices is modified;

b) comparing the modified current set of optimal projection matrices to the previous set of projection matrices;

c) computing a difference between the modified current set of optimal projection matrices and the previous set of projection matrices;

d) comparing the difference that is computed between the modified current set of optimal projection matrices and the previous set of projection matrices to the threshold value; and

e) iteratively repeating the steps a) through d) until the difference between the modified current set of optimal projection matrices and the previous set of projection matrices is less than the threshold value.

30. A method, comprising:

identifying a plurality of candidate features that are components of one or more of audio or video content and a plurality of candidate hash functions, wherein each of the candidate hash functions comprise an array of coefficients that relate to the candidate features;

selecting a subgroup of the hash functions, based at least in part on an optimized combination of at least two characteristics of the candidate features or the hash functions; and

deriving fingerprints that uniquely identify the audio or video content from the selected optimized hash functions subgroup.

31. A method comprising:

extracting a plurality of N features from media content that comprises one or more of audio or video content, wherein N comprises a first positive integer;

computing a set of K optimal hash functions from the N media content features, wherein K comprises a second positive integer; and

deriving media fingerprints from the media content with the computed K optimal hash functions.

32. The method as recited in claim 31 wherein the hash functions comprise one or more non-linear projections.

33. The method as recited in claim 31 wherein the hash functions comprise one or more projection matrices.