Media fingerprinting and identification system
View Patent ↗The overall architecture and details of a scalable video fingerprinting and identification system that is robust with respect to many classes of video distortions is described. In this system, a fingerprint for a piece of multimedia content is composed of a number of compact signatures, along with traversal hash signatures and associated metadata. Numerical descriptors are generated for features found in a multimedia clip, signatures are generated from these descriptors, and a reference signature database is constructed from these signatures. Query signatures are also generated for a query multimedia clip. These query signatures are searched against the reference database using a fast similarity search procedure, to produce a candidate list of matching signatures. This candidate list is further analyzed to find the most likely reference matches. Signature correlation is performed between the likely reference matches and the query clip to improve detection accuracy.
1. A method comprising:
obtaining, by one or more computing devices, a plurality of query signatures of a query media clip;
searching, by the one or more computing devices, a reference database using the plurality of query signatures so as to identify a first set of reference signatures that match the plurality of query signatures;
determining, by the one or more computing devices, a media clip identifier corresponding to a reference signature of the first set of reference signatures, wherein the media clip identifier identifies a reference media clip;
determining, by the one or more computing devices, a secondary index value corresponding to the reference signature;
searching, by the one or more computing devices, the reference database using the media clip identifier and the secondary index value so as to identify a second set of reference signatures that correspond to the reference media clip;
determining, by the one or more computing devices, a score for the reference media clip based on the plurality of query signatures and the second set of reference signatures;
determining, by the one or more computing devices, that the score satisfies a threshold; and
based on the determining that the score satisfies the threshold, providing, by the one or more computing devices, an indication that the reference media clip is a match to the query media clip.
2. The method of claim 1 , wherein searching the reference database using the plurality of query signatures so as to identify the first set of reference signatures that match the plurality of query signatures comprises:
for one or more query signatures of the plurality of query signatures, searching the reference database using the plurality of query signatures so as to identify reference signatures that are within a specified signature distance of the query signature.
3. The method of claim 1 , wherein searching the reference database using the plurality of query signatures comprises:
generating a traversal hash signature for a query signature of the plurality of query signatures; and
searching the reference database using the traversal hash signature.
4. The method of claim 1 , wherein the reference database stores an indication of the media clip identifier in association with the reference signature, and wherein determining the media clip identifier comprises determining the media clip identifier based on the indication of the media clip identifier stored by the reference database.
5. The method of claim 1 , wherein the secondary index value comprises a timestamp, and wherein searching the reference database using the secondary index value comprises searching the reference database using the timestamp.
6. The method of claim 5 , wherein the reference database stores an indication of the timestamp in association with the reference signature, and wherein determining the secondary index value corresponding to the reference signature comprises determining the timestamp based on the indication of the timestamp stored by the reference database.
7. The method of claim 5 , further comprising:
determining that an additional reference signature of the first set of reference signatures corresponds to the media clip identifier; and
determining an additional timestamp corresponding to the additional reference signature,
wherein the searching of the reference database using the media clip identifier and the secondary index value is further based on the additional timestamp.
8. The method of claim 7 , wherein searching the reference database so as to identify the second set of reference signatures comprises searching the reference database so as to identify reference signatures that correspond to a segment of the reference media clip between the timestamp and the additional timestamp.
9. The method of claim 1 , wherein the reference signatures of the first set of reference signatures correspond to a plurality of reference media clips.
10. The method of claim 9 , wherein reference database stores respective reference signatures for each of the plurality of reference media clips, wherein the respective reference signatures stored in the reference database are indexed by a primary index and by a secondary index that is different from the primary index, and wherein the secondary index is based on media clip identifiers and timestamps.
11. A non-transitory computer-readable medium having stored therein instructions that are executable to cause a computing system to perform functions comprising:
obtaining a plurality of query signatures of a query media clip;
searching a reference database using the plurality of query signatures so as to identify a first set of reference signatures that match the plurality of query signatures;
determining a media clip identifier corresponding to a reference signature of the first set of reference signatures, wherein the media clip identifier identifies a reference media clip;
determining a secondary index value corresponding to the reference signature;
searching the reference database using the media clip identifier and the secondary index value so as to identify a second set of reference signatures that correspond to the reference media clip;
determining a score for the reference media clip based on the plurality of query signatures and the second set of reference signatures;
determining that the score satisfies a threshold; and
based on the determining that the score satisfies the threshold, providing an indication that the reference media clip is a match to the query media clip.
12. The non-transitory computer-readable medium of claim 11 , wherein searching the reference database using the plurality of query signatures so as to identify the first set of reference signatures that match the plurality of query signatures comprises:
for one or more query signatures of the plurality of query signatures, searching the reference database using the plurality of query signatures so as to identify reference signatures that are within a specified signature distance of the query signature.
13. The non-transitory computer-readable medium of claim 11 , wherein searching the reference database using the plurality of query signatures comprises:
generating a traversal hash signature for a query signature of the plurality of query signatures; and
searching the reference database using the traversal hash signature.
14. The non-transitory computer-readable medium of claim 11 , wherein the reference database stores an indication of the media clip identifier in association with the reference signature, and wherein determining the media clip identifier comprises determining the media clip identifier based on the indication of the media clip identifier stored by the reference database.
15. The non-transitory computer-readable medium of claim 11 , wherein the secondary index value comprises a timestamp, and wherein searching the reference database using the secondary index value comprises searching the reference database using the timestamp.
16. The non-transitory computer-readable medium of claim 15 , wherein the reference database stores an indication of the timestamp in association with the reference signature, and wherein determining the secondary index value corresponding to the reference signature comprises determining the timestamp based on the indication of the timestamp stored by the reference database.
17. The non-transitory computer-readable medium of claim 15 , wherein the functions further comprise:
determining that an additional reference signature of the first set of reference signatures corresponds to the media clip identifier; and
determining an additional timestamp corresponding to the additional reference signature,
wherein the searching of the reference database using the media clip identifier and the secondary index value is further based on the additional timestamp.
18. The non-transitory computer-readable medium of claim 17 , wherein searching the reference database so as to identify the second set of reference signatures comprises searching the reference database so as to identify reference signatures that correspond to a segment of the reference media clip between the timestamp and the additional timestamp.
19. A computing system comprising:
a processing unit; and
a non-transitory computer-readable medium having stored therein instructions that are executable to cause the computing system to perform functions comprising:
obtaining a plurality of query signatures of a query media clip,
searching a reference database using the plurality of query signatures so as to identify a first set of reference signatures that match the plurality of query signatures,
determining a media clip identifier corresponding to a reference signature of the first set of reference signatures, wherein the media clip identifier identifies a reference media clip,
determining a secondary index value corresponding to the reference signature,
searching the reference database using the media clip identifier and the secondary index value so as to identify a second set of reference signatures that correspond to the reference media clip,
determining a score for the reference media clip based on the plurality of query signatures and the second set of reference signatures,
determining that the score satisfies a threshold, and
based on the determining that the score satisfies the threshold, providing an indication that the reference media clip is a match to the query media clip.
20. The computing system of claim 19 , wherein searching the reference database using the plurality of query signatures so as to identify the first set of reference signatures that match the plurality of query signatures comprises:
for one or more query signatures of the plurality of query signatures, searching the reference database using the plurality of query signatures so as to identify reference signatures that are within a specified signature distance of the query signature.
21. The computing system of claim 19 , wherein searching the reference database using the plurality of query signatures so as to identify the first set of reference signatures that match the plurality of query signatures comprises:
for one or more query signatures of the plurality of query signatures, searching the reference database using the plurality of query signatures so as to identify reference signatures that are within a specified signature distance of the query signature.
22. The computing system of claim 19 , wherein searching the reference database using the plurality of query signatures comprises:
generating a traversal hash signature for a query signature of the plurality of query signatures; and
searching the reference database using the traversal hash signature.
23. The computing system of claim 19 , wherein the reference database stores an indication of the media clip identifier in association with the reference signature, and wherein determining the media clip identifier comprises determining the media clip identifier based on the indication of the media clip identifier stored by the reference database.
24. The computing system of claim 19 , wherein the secondary index value comprises a timestamp, and wherein searching the reference database using the secondary index value comprises searching the reference database using the timestamp.
25. The computing system of claim 24 , wherein the reference database stores an indication of the timestamp in association with the reference signature, and wherein determining the secondary index value corresponding to the reference signature comprises determining the timestamp based on the indication of the timestamp stored by the reference database.
26. The computing system of claim 24 , wherein the functions further comprise:
determining that an additional reference signature of the first set of reference signatures corresponds to the media clip identifier; and
determining an additional timestamp corresponding to the additional reference signature,
wherein the searching of the reference database using the media clip identifier and the secondary index value is further based on the additional timestamp.
27. The computing system of claim 26 , wherein searching the reference database so as to identify the second set of reference signatures comprises searching the reference database so as to identify reference signatures that correspond to a segment of the reference media clip between the timestamp and the additional timestamp.