Method to differentiate and classify fingerprints using fingerprint neighborhood analysis
Techniques are described that exclude use of “stop-fingerprints” from media database formation and search query to an automatic content recognition (ACR) systems based on media content fingerprints updated by stop-fingerprint analysis. A classification process is presented which takes in fingerprints from reference media files as an input and produces a modified set of fingerprints as an output by applying a novel stop-fingerprint classification algorithm. Architecture for the distributed stop-fingerprint generation is presented. Various cases, as stop-fingerprints generation for the entire reference database, stop-fingerprints generation for the individual reference fingerprint files, and temporal fingerprint classification obtained through intermediate steps of the temporal fingerprint classification algorithm are presented. A hash-based signature classification algorithm is also described.
1. A method for classification of multimedia fingerprints, the method comprising:
establishing a stop-fingerprint rule for multimedia fingerprint neighborhood analysis; and
classifying multimedia fingerprints into unique fingerprints and non-unique fingerprints by applying the stop-fingerprint rule on each reference fingerprint in a reference multimedia fingerprint database,
wherein applying the stop-fingerprint rule on each reference fingerprint in the reference multimedia fingerprint database comprises, for each reference fingerprint performing operations comprising:
determining, for each stop fingerprint in a stop-fingerprint database, a respective fingerprint distance between the reference fingerprint and the stop fingerprint,
determining, for the reference fingerprint, a set of neighboring fingerprints within the stop-fingerprint database, wherein the set of neighboring fingerprints comprises the stop fingerprints within the stop-fingerprint database for which the respective fingerprint distance is less than a first threshold value;
determining a quantity of stop fingerprints in the set of neighboring fingerprints;
performing a comparison of the quantity of stop fingerprints in the set of neighboring fingerprints to a second threshold value;
if the quantity of stop fingerprints in the set of neighboring fingerprints is less than the second threshold value, then classifying the multimedia fingerprint as one of the unique fingerprints; and
if the quantity of stop fingerprints in the set of neighboring fingerprints is greater than the second threshold value, then classifying the multimedia fingerprint as one of the non-unique fingerprints,
wherein the reference fingerprints are split across a plurality of processors, each processor having a part of the reference multimedia fingerprint database.
2. The method of claim 1 , wherein the non-unique fingerprints are classified as stop-fingerprints and the unique fingerprints are classified as non-stop-fingerprints.
3. The method of claim 1 , wherein the reference fingerprints for all reference multimedia content are available at a single processor.
4. The method of claim 2 , wherein classifying of the multimedia fingerprints into stop-fingerprints and non-stop-fingerprints is done by a single processor.
5. The method of claim 1 , wherein each processor queries to each other processor to request details of the quantity of stop fingerprints within a specified range of stop-fingerprint distance locally stored on each processor.
6. The method of claim 5 , wherein after collecting the details from all of the plurality of processors, the stop-fingerprint rule is applied to the reference fingerprints.
7. The method of claim 1 , wherein a fingerprint set for signature classification is confined to a set of fingerprints coming from a single reference media file.
8. The method of claim 7 , where the signature classification is done by comparing fingerprints from the fingerprint set against a specified set of reference fingerprints.
9. The method of claim 1 , wherein each fingerprint distance is a Hamming distance.
10. The method of claim 9 , wherein each fingerprint distance is a distance weighted neighborhood score of a fingerprint to be evaluated based on a number of neighbor fingerprints where the Hamming distance is N.
11. A method for temporal stop-fingerprint classification, the method comprising:
selecting fingerprints having timestamps that meets a time window criteria;
measuring a fingerprint distance from each fingerprint that meets the time window criteria to fingerprints in a fingerprint reference database; and
classifying each fingerprint that meets the time window criteria and has at least a selected number of fingerprints within a threshold distance as a non-unique stop-fingerprint, wherein classifying each fingerprint that meets the time window criteria comprises, for each fingerprint that meets the time window criteria, performing operations comprising:
determining, for the fingerprint, a set of neighboring fingerprints, wherein the set of neighboring fingerprints comprises the fingerprints for which the fingerprint distance is less than a first threshold value,
determining a quantity of fingerprints in the set of neighboring fingerprints;
performing a comparison of the quantity of fingerprints in the set of neighboring fingerprints to a second threshold value,
if the quantity of fingerprints in the set of neighboring fingerprints is less than the second threshold value, then classifying the fingerprint as a unique non-stop fingerprint, and
if the quantity of fingerprints in the set of neighboring fingerprints is greater than the second threshold value, then classifying the fingerprint as the non-unique stop-fingerprint,
wherein the fingerprints in the reference fingerprint database are split across a plurality of processors, each processor having a part of the reference fingerprint database.
12. The method of claim 11 , wherein a temporal stop-fingerprints calculation is performed within the same reference content and within the time window criteria.
13. The method of claim 11 , wherein every fingerprint that meets the time window criteria is compared for stop-fingerprint classification with all fingerprints from the same reference multimedia content.
14. The method of claim 11 , wherein if two fingerprints each having an associated timestamp that is within the time window criteria, then the two fingerprints are compared for stop-fingerprint classification.
15. The method of claim 14 , wherein if a difference in timestamps of the two fingerprints to be compared is less than the time window criteria, and if the fingerprint distance between the two fingerprints is less than a threshold distance, then the two fingerprints are classified as neighbors.
16. The method of claim 14 , wherein if a first timestamp of a first fingerprint of the two fingerprints in consideration is t1 and a second timestamp of a second fingerprint of the two fingerprints in consideration is t2 where t2<t1, and |t1−t2|<T then the two fingerprints would be termed as neighbors and compared only if the fingerprint distance between the two fingerprints is less than the threshold distance.
17. A method for hash key utilization for stop-fingerprint classification, the method comprising:
generating fingerprints and associated hash keys;
measuring a fingerprint distance from each fingerprint with a hash key to fingerprints having the same hash key selected from a fingerprint reference database; and
classifying each fingerprint with the hash key that has a selected number of fingerprints within a threshold distance as a non-unique stop-fingerprint, wherein classifying each fingerprint with the hash key comprises, for each fingerprint with the hash key, performing operations comprising:
determining, for the fingerprint, a set of neighboring fingerprints, wherein the set of neighboring fingerprints comprises the fingerprints for which the fingerprint distance is less than a first threshold value;
determining a quantity of fingerprints in the set of neighboring fingerprints;
performing a comparison of the quantity of fingerprints in the set of neighboring fingerprints to a second threshold value;
if the quantity of fingerprints in the set of neighboring fingerprints is less than the second threshold value, then classifying the fingerprint as a unique non-stop fingerprint; and
if the quantity of fingerprints in the set of neighboring fingerprints is greater than the second threshold value, then classifying the fingerprint as the non-unique stop-fingerprint.
18. The method of claim 17 , wherein the stop-fingerprint classification, limited to the fingerprints that have the same hash key, reduces computational complexity for fingerprint search operations.
19. The method of claim 17 , wherein a smart device performs (i) the generating the fingerprints and the associated hash keys, (ii) the measuring the fingerprint distance, and (iii) the classifying each fingerprint with the hash key that has the selected number of fingerprints within the threshold distance as the non-unique stop-fingerprint.