Audio fingerprinting
View Patent ↗A machine may be configured to generate one or more audio fingerprints of one or more segments of audio data. The machine may access audio data to be fingerprinted and divide the audio data into segments. For any given segment, the machine may generate a spectral representation from the segment; generate a vector from the spectral representation; generate an ordered set of permutations of the vector; generate an ordered set of numbers from the permutations of the vector; and generate a fingerprint of the segment of the audio data, which may be considered a sub-fingerprint of the audio data. In addition, the machine or a separate device may be configured to determine a likelihood that candidate audio data matches reference audio data.
1. A method comprising:
generating a spectral representation of a segment of audio data, the spectral representation indicating energy values for a set of frequencies;
multiplying each energy value by a corresponding weight factor determined based on an ordinal position of a corresponding frequency within the set of frequencies;
using a processor, generating a sparse vector that contains a zero value for each frequency in the set of frequencies except for representing a first group of highest energy values from a first portion of the set of frequencies with a common value and representing a second group of highest energy values from a second portion of the set of frequencies with the common value, the first group being determined based on ranked energy values for frequencies above a threshold frequency, the second group being determined based on ranked energy values for frequencies below the threshold frequency;
generating an ordered set of permutations of the sparse vector, each permutation in the ordered set of permutations being generated in a corresponding manner that repositions instances of the common value to permutate the sparse vector;
generating an ordered set of numbers from the ordered set of permutations of the sparse vector, each number in the ordered set of numbers representing a corresponding permutation by indicating a position of an instance of the common value within the corresponding permutation; and
generating a fingerprint of the segment of the audio data based on the ordered set of numbers generated from the ordered set of permutations of the sparse vector.
2. The method of claim 1 , wherein:
each energy value among the energy values in the spectral representation has a corresponding frequency among the set of frequencies.
3. The method of claim 2 , wherein:
the corresponding weight factor of each energy value is the square root of the ordinal position of its frequency within the set of frequencies.
4. The method of claim 1 , wherein:
the sparse vector is a binary vector that represents the first and second groups of highest energy values with ones as the common value.
5. The method of claim 1 further comprising:
determining the first and second groups of highest energy values; wherein
the determining of the first group of highest energy levels includes ranking energy values for the frequencies above the threshold frequency in the spectral representation of the segment of audio data; and
the determining of the second group of highest energy values includes ranking energy values for the frequencies below the threshold frequency in the spectral representation of the segment of audio data.
6. The method of claim 5 , wherein:
the determining of the first group of highest energy values includes determining the 0.5% highest ranked energy values for frequencies of at least the threshold frequency of 1700 Hz in the spectral representation of the segment of audio data.
7. The method of claim 5 , wherein:
the determining of the second group of highest energy values includes determining the 0.5% highest ranked energy values for frequencies below the threshold frequency of 1700 Hz in the spectral representation of the segment of audio data.
8. A non-transitory machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to perform operations comprising:
generating a spectral representation of a segment of audio data, the spectral representation indicating energy values for a set of frequencies;
multiplying each energy value by a corresponding weight factor determined based on an ordinal position of a corresponding frequency within the set of frequencies;
generating a sparse vector that contains a zero value for each frequency in the set of frequencies except for representing a first group of highest energy values from a first portion of the set of frequencies with a common value and representing a second group of highest energy values from a second portion of the set of frequencies with the common value, the first group being determined based on ranked energy values for frequencies above a threshold frequency, the second group being determined based on ranked energy values for frequencies below the threshold frequency;
generating an ordered set of permutations of the sparse vector, each permutation in the ordered set of permutations being generated in a corresponding manner that repositions instances of the common value to permutate the sparse vector;
generating an ordered set of numbers from the ordered set of permutations of the sparse vector, each number in the ordered set of numbers representing a corresponding permutation by indicating a position of an instance of the common value within the corresponding permutation; and
generating a fingerprint of the segment of the audio data based on the ordered set of numbers generated from the ordered set of permutations of the sparse vector.
9. A system comprising:
a frequency module configured to generate a spectral representation of a segment of audio data, the spectral representation indicating energy values for a set of frequencies;
a processor configured by a vector module to:
multiply each energy value by a corresponding weight factor determined based on an ordinal position of a corresponding frequency within the set of frequencies; and
generate a sparse vector that contains a zero value for each frequency in the set of frequencies except for representing a first group of highest energy values from a first portion of the set of frequencies with a common value and representing a second group of highest energy values from a second portion of the set of frequencies with the common value, the first group being determined based on ranked energy values for frequencies above a threshold frequency, the second group being determined based on ranked energy values for frequencies below the threshold frequency;
a scrambler module configured to generate an ordered set of permutations of the sparse vector, each permutation in the ordered set of permutations being generated in a corresponding manner that repositions instances of the common value to permutate the sparse vector;
a coder module configured to generate an ordered set of numbers from the ordered set of permutations of the sparse vector, each number in the ordered set of numbers representing a corresponding permutation by indicating a position of an instance of the common value within the corresponding permutation; and
a fingerprint module configured to generate a fingerprint of the segment of the audio data based on the ordered set of numbers generated from the ordered set of permutations of the sparse vector.
10. The system of claim 9 , wherein:
the vector module is configured to determine the first and second groups of highest energy values,
the determining of the first group of highest energy levels including ranking energy values for the frequencies above the threshold frequency in the spectral representation of the segment of audio data; and
the determining of the second group of highest energy values including ranking energy values for the frequencies below the threshold frequency in the spectral representation of the segment of audio data.
11. The method of claim 1 , wherein:
the generating of the ordered set of permutations generates each permutation in the ordered set of permutations by transforming the sparse vector in a manner unique within the ordered set of permutations.
12. The method of claim 1 , wherein:
the generating of the ordered set of numbers includes generating each number in the ordered set of numbers based on the lowest position of any instance of the common value within the corresponding permutation for the number being generated.
13. The method of claim 12 , wherein:
the generating of each number in the ordered set of numbers includes calculating a remainder from a modulo operation performed on a numerical representation of the lowest position occupied by any instance of the common value within the corresponding permutation for the number being generated.
14. The method of claim 1 , wherein:
the generating of the fingerprint of the segment includes storing the ordered set of numbers in order and with a reference to a timestamp of the segment relative to the audio data.
15. The method of claim 14 , wherein:
the storing of the ordered set of numbers in order includes storing each of multiple ordered subsets of the ordered set in a corresponding hash table that corresponds to the timestamp of the segment.
16. The method of claim 1 , wherein:
the fingerprint of the segment of the audio data is a first reference fingerprint of a first reference segment that precedes a second reference segment among multiple reference segments of reference audio data; and
the method further comprises:
generating a second reference fingerprint of the second reference segment;
accessing candidate audio data that includes multiple candidate segments among which are a first candidate segment and a second candidate segment subsequent to the first candidate segment;
generating a first candidate fingerprint of the first candidate segment and a second candidate fingerprint of the second candidate segment; and
determining a likelihood that the candidate audio data matches the reference audio data based on:
the first candidate fingerprint matching the first reference fingerprint,
the second candidate fingerprint matching the second reference fingerprint, and
the first reference segment preceding the second reference segment in conjunction with the first candidate segment preceding the second candidate segment.
17. The method of claim 16 , wherein:
each of the multiple reference segments overlaps an adjacent reference segment by a non-zero quantity of audio samples; and
each of the multiple candidate segments overlaps an adjacent candidate segment by the non-zero quantity of audio samples.
18. The method of claim 16 , wherein:
the first reference segment precedes the second reference segment by a reference time span;
the first candidate segment precedes the second candidate segment by the reference time span; and
the determining of the likelihood is based on the first candidate segment preceding the second candidate segment by the reference time span by which the first reference segment precedes a second reference segment.
19. The method of claim 16 , wherein:
the first reference segment precedes the second reference segment by a reference time span;
the first candidate segment precedes the second candidate segment by a candidate time span equivalent to the reference time span.
20. The non-transitory machine-readable storage medium of claim 8 , wherein:
the fingerprint of the segment of the audio data is a first reference fingerprint of a first reference segment that precedes a second reference segment among multiple reference segments of reference audio data; and
the operations further comprise:
generating a second reference fingerprint of the second reference segment;
accessing candidate audio data that includes multiple candidate segments among which are a first candidate segment and a second candidate segment subsequent to the first candidate segment;
generating a first candidate fingerprint of the first candidate segment and a second candidate fingerprint of the second candidate segment; and
determining a likelihood that the candidate audio data matches the reference audio data based on:
the first candidate fingerprint matching the first reference fingerprint,
the second candidate fingerprint matching the second reference fingerprint, and
the first reference segment preceding the second reference segment in conjunction with the first candidate segment preceding the second candidate segment.
21. The system of claim 9 , wherein:
the fingerprint of the segment of the audio data is a first reference fingerprint of a first reference segment that precedes a second reference segment among multiple reference segments of reference audio data;
the fingerprint module is further configured to:
generate a second reference fingerprint of the second reference segment;
access candidate audio data that includes multiple candidate segments among which are a first candidate segment and a second candidate segment subsequent to the first candidate segment; and
generate a first candidate fingerprint of the first candidate segment and a second candidate fingerprint of the second candidate segment; and
the system further comprises:
a match module configured to:
determine a likelihood that the candidate audio data matches the reference audio data based on:
the first candidate fingerprint matching the first reference fingerprint,
the second candidate fingerprint matching the second reference fingerprint, and
the first reference segment preceding the second reference segment in conjunction with the first candidate segment preceding the second candidate segment.