System and method for optimization of audio fingerprint search
A system and method are presented for optimization of audio fingerprint search. In an embodiment, the audio fingerprints are organized into a recursive tree with different branches containing fingerprint sets that are dissimilar to each other. The tree is constructed using a clustering algorithm based on a similarity measure. The similarity measure may comprise a Hamming distance for a binary fingerprint or a Euclidean distance for continuous valued fingerprints. In another embodiment, each fingerprint is stored at a plurality of resolutions and clustering is performed hierarchically. The recognition of an incoming fingerprint begins from the root of the tree and proceeds down its branches until a match or mismatch is declared. In yet another embodiment, a fingerprint definition is generalized to include more detailed audio information than in the previous definition.
1. A method for classifying audio, comprising:
receiving, by a computing system comprising a processor and memory, an incoming audio stream;
dividing, by the computing system, the incoming audio stream into a plurality of frames;
extracting, by the computing system, a plurality of incoming audio fingerprints from the plurality of frames of the incoming audio stream, each of the incoming audio fingerprints comprising: a first plurality of values at a first resolution; and a second plurality of values at a second resolution, the second resolution being higher than the first resolution;
searching, by the computing system, a database of known audio fingerprints to identify known audio fingerprints similar to the incoming audio fingerprints, the database comprising a fingerprint tree comprising a plurality of nodes, each node of the plurality of nodes being associated with: a cluster of similar known audio fingerprints; and a centroid corresponding to an average of the similar known audio fingerprints of the cluster, the searching comprising:
computing fingerprint distances between the first values at the first resolution of an incoming audio fingerprint of the incoming audio stream and the centroids of a plurality of nodes to identify a most similar node:
determining the most similar node is associated with one or more child nodes;
in response to determining that the most similar node is associated with one or more child nodes repeating the searching on the one or more child nodes; and
in response to determining that the most similar node is not associated with child nodes, returning the most similar node as a matching node, and
classifying the incoming audio stream based on a classification associated with the matching node of the fingerprint tree.
2. The method of claim 1 , wherein the values of each of the audio fingerprints comprise energy and time derivatives of perceptual filter bank values.
3. The method of claim 1 , wherein the frames overlap.
4. The method of claim 1 , wherein the frames are non-overlapping.
5. The method of claim 1 , wherein the frames have a length of 20 ms.
6. The method of claim 1 , wherein the fingerprint tree is generated by:
computing a plurality of fingerprint distances between the known audio fingerprints;
clustering the known audio fingerprints based on the computed fingerprint distances to generate a plurality of clusters; and
assigning the clusters to the nodes of the fingerprint tree.
7. The method of claim 6 , wherein the centroid comprised a frequently occurring binary value at each fingerprint location to the cluster.
8. The method of claim 6 , wherein the fingerprint distances between the known audio fingerprints are computed using a Hamming distance.
9. The method of claim 1 , wherein the fingerprint distances are computed using a Hamming distance.
10. The method of claim 1 , further comprising applying a mask to check fingerprints within the matching node of the fingerprint tree.
11. A system for classifying audio, comprising:
a processor; and
memory storying instructions that, when executed by the processor, cause the processor to:
receive an incoming audio stream;
divide the incoming audio stream into a plurality of frames;
extract a plurality of incoming audio fingerprints from the plurality of frames of the incoming audio stream, each of the incoming audio fingerprints comprising: a first plurality of values at a first resolution; and a second plurality of values at a second resolution, the second resolution being higher than the first resolution;
search database of known audio fingerprints to identify known audio fingerprints similar to the incoming audio fingerprints, the database comprising a fingerprint tree comprising a plurality of nodes, each node of the plurality of nodes being associated with: a cluster of similar known audio fingerprints; and a centroid corresponding to an average of the similar known audio fingerprints of the cluster, the search comprising:
computing fingerprint distances between the first values at the first resolution of an incoming audio fingerprint of the incoming audio stream and the centroids of a plurality of nodes to identify a most similar node;
determining if the most similar node is associated with one or more child nodes;
in response to determining that the most similar node is associated with one or more child nodes repeating the searching on the none or more child nodes; and
in response to determining that the most similar node is not associated with child nodes, returning the most similar node as a matching node, and
classify the incoming audio stream based on a classification associated with the matching node of the fingerprint tree.
12. The system of claim 11 , wherein the values of each of the audio fingerprints comprise energy and time derivatives of perceptual filter bank values.
13. The system of claim 11 , wherein the frames overlap.
14. The system of claim 11 , wherein the frames are non-overlapping.
15. The system of claim 11 , wherein the frames have a length of 20 ms.
16. The system of claim 11 , wherein the fingerprint tree is generated by:
computing a plurality of fingerprint distances between the known audio fingerprints;
clustering the known audio fingerprints based on the computed fingerprint distances to generate a plurality of clusters; and
assigning the clusters to the nodes of the fingerprint tree.
17. The system of claim 16 , wherein the centroid comprises a frequently occurring binary value at each fingerprint location in the cluster.
18. The system of claim 16 , wherein the fingerprint distances between the known audio fingerprints are computed using a Hamming distance.
19. The system of claim 11 , wherein the fingerprint distances are computed using a Hamming distance.
20. The system of claim 11 , further comprising applying a mask to check fingerprints within the matching node of the fingerprint tree.