Robust hashing of digital media data
View Patent ↗A robust hashing method is applied to media data (e.g., video, image, and/or audio data), producing a hash output that is robust with respect to at least one attribute of the media data. A histogram is generated for the media data and the histogram is hashed using a weighted hashing procedure. The histogram can be derived from a plurality of randomized versions of the media file, each randomized version of the media file altered to a random extent with respect to the attribute. The histogram can also be derived from a plurality of feature descriptors computed for the media data that are coarsely encoded with respect to the attribute. The weighted hashing procedure includes assigning a weight to components of the histogram and applying a plurality of hash functions to a number of versions of each component, the number of versions based on the assigned weight.
1. A method for generating a fingerprint for a media file, the method executed by at least one computer system and comprising:
creating from the media file by the at least one computer system, a plurality of randomized versions of the media file, each randomized version of the media file altered to a random extent with respect to an attribute of the media file;
generating, in a memory of the at least one computer system, a histogram from the plurality of randomized versions of the media file, the histogram having a plurality of bins each associated with a different feature of the plurality of randomized versions of the media file, and each bin storing a count of the randomized versions of the media file that have the feature associated with the bin;
generating the fingerprint for the media file based on the histogram, wherein generating the fingerprint comprises:
creating a number of altered versions of each bin;
applying a first hash function to the number of altered versions of each bin to generate a plurality of outputs for the first hash function;
determining a smallest output for the first hash function; and
storing a first data element representative of the altered version that yielded the determined smallest output for the first hash function; and
storing the fingerprint to a non-transitory computer-readable storage medium.
2. The method of claim 1 , wherein generating the histogram for the media file based on the plurality of randomized versions further comprises:
determining the count of the randomized media versions of the media file for each defined bin, each count indicating a number of randomized versions that produce a particular output value when a particular hash function is applied.
3. The method of claim 1 , wherein the randomized attribute comprises an amount of media data to be cropped from the media file.
4. The method of claim 1 , wherein the number of altered versions of a bin is based on the count determined for the bin.
5. The method of claim 1 , wherein the number of altered versions of a bin is based on a global weight associated with a set of features specified by the bin.
6. The method of claim 1 , further comprising:
applying a second hash function to the number of altered versions of each bin to generate a plurality of outputs for the second hash function;
determining a smallest output for the second hash function; and
storing a second data element representative of the altered version that yielded the determined smallest output for the second hash function.
7. The method of claim 6 , wherein the first hash function and the second hash function are part of a family of hash functions, the first hash function having a first seed value and the second hash function having a second seed value.
8. The method of claim 6 , further comprising:
assigning the media file to a cluster of media files based on an output vector comprising at least the first and second data elements.
9. The method of claim 8 , wherein assigning the media file to a cluster of media files based on the output vector comprises:
calculating a number of matching entries for the output vector for the media file and a second output vector for a second media file.
10. A non-transitory computer-readable storage medium storing computer-executable code, the computer-executable code when executed by a processor causing the processor to perform a process for generating a fingerprint for a media file, the process comprising:
creating from the media file, a plurality of randomized versions of the media file, each randomized version of the media file altered to a random extent with respect to an attribute of the media file;
generating a histogram from the plurality of randomized versions of the media file, the histogram having a plurality of bins each associated with a different feature of the randomized versions of the media file, and each bin storing a count of the randomized versions of the media file that have the feature associated with the bin;
generating the fingerprint for the media file based on the histogram, wherein generating the fingerprint comprises:
creating a number of altered versions of each bin;
applying a first hash function to the number of altered versions of each bin to generate a plurality of outputs for the first hash function;
determining a smallest output for the first hash function; and
storing a first data element representative of the altered version that yielded the determined smallest output for the first hash function; and
storing the fingerprint.
11. The non-transitory computer-readable storage medium of claim 10 , wherein generating the histogram for the media data based on the plurality of randomized versions further comprises:
determining the count of the randomized media versions of the media file for each defined bin, each count indicating a number of randomized versions that produce a particular output value when a particular hash function is applied.
12. The non-transitory computer-readable storage medium of claim 10 , wherein the randomized attribute comprises an amount of media data to be cropped from the media file.
13. The non-transitory computer-readable storage medium of claim 10 , wherein the number of altered versions of a bin is based on the count determined for the bin.
14. The non-transitory computer-readable storage medium of claim 10 , wherein the number of altered versions of a bin is based on a global weight associated with a set of features specified by the bin.
15. The non-transitory computer-readable storage medium of claim 10 , further comprising:
applying a second hash function to the number of altered versions of each bin to generate a plurality of outputs for the second hash function;
determining a smallest output for the second hash function; and
storing a second data element representative of the altered version that yielded the determined smallest output for the second hash function.
16. The non-transitory computer-readable storage medium of claim 15 , wherein the first hash function and the second hash function are part of a family of hash functions, the first hash function having a first seed value and the second hash function having a second seed value.
17. The non-transitory computer-readable storage medium of claim 15 , the process further comprising:
assigning the media file to a cluster of media files based on an output vector comprising at least the first and second data elements.
18. The non-transitory computer-readable storage medium of claim 17 , wherein assigning the media file to a cluster of media files based on the output vector comprises:
calculating a number of matching entries for the output vector for the media file and a second output vector for a second media file.