Media fingerprinting and identification system
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 computer-implemented method comprising:
establishing, using a video fingerprinting system, a rectangular grid of blocks overlaying pixels of a frame of a reference video, wherein each block of the rectangular grid of blocks includes a grid of pixels, and wherein boundaries of the rectangular grid of blocks are defined such that some of the blocks of the rectangular grid of blocks include different numbers of pixels;
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective intensity values corresponding to pixels included within the respective blocks of the rectangular grid of blocks;
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective block values based on the respective intensity values;
generating, using the video fingerprinting system, fingerprint data for the frame based on the respective block values; and
storing, in a reference database, the fingerprint data in association with an identifier of the reference video.
2. The computer-implemented method of claim 1 , wherein the rectangular grid of blocks has a spatial extent, in pixels, of J×K, wherein J is an integer that is greater than one, and wherein K is an integer that is greater than one.
3. The computer-implemented method of claim 2 , wherein determining, for respective blocks of the rectangular grid of blocks, respective block-descriptor values based on the respective intensity values comprises computing, for respective blocks of the rectangular grid of blocks, L respective block values based on the respective intensity values, wherein L is an integer that is greater than or equal to one.
4. The computer-implemented method of claim 3 , wherein generating the fingerprint data for the frame based on the respective block values comprises deriving a descriptor from the L block values for multiple blocks of the rectangular grid of blocks.
5. The computer-implemented method of claim 4 , wherein generating the fingerprint data for the frame based on the respective block values further comprises determining a signature using the descriptor.
6. The computer-implemented method of claim 4 , wherein deriving the descriptor from the L block values for the multiple blocks comprises concatenating the L block values for the multiple blocks.
7. The computer-implemented method of claim 1 , wherein, for a given block of the respective blocks, determining the respective intensity values corresponding to pixels included within the given block comprises:
subdividing the block into an M×M grid of pixels, wherein M is an integer that is greater than one; and
for each sub-grid area of the M×M grid of pixels, combining intensity values of pixels of the sub-grid area to produce a re-sampled intensity value, and
wherein the block value for the given block is determined based on the re-sampled intensity value.
8. A computer-implemented method comprising:
establishing, using a video fingerprinting system, a rectangular grid of blocks overlaying pixels of a frame of a query video, wherein each block of the rectangular grid of blocks includes a grid of pixels, and wherein boundaries of the rectangular grid of blocks are defined such that some of the blocks of the rectangular grid of blocks include different numbers of pixels;
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective intensity values corresponding to pixels included within the respective blocks of the rectangular grid of blocks;
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective block values based on the respective intensity values;
generating, using the video fingerprinting system, fingerprint data for the frame based on the respective block values; and
identifying a reference video corresponding to the query video using the fingerprint data and a reference database.
9. The computer-implemented method of claim 8 , wherein the reference database stores reference fingerprint data for the reference video, and wherein identifying the reference video using the fingerprint data comprises comparing the fingerprint data with the reference fingerprint data.
10. A non-transitory computer-readable medium having stored therein instructions that are executable by one or more computers to cause a video fingerprint system to perform functions comprising:
establishing a rectangular grid of blocks overlaying pixels of a frame of a reference video, wherein each block of the rectangular grid of blocks includes a grid of pixels, and wherein boundaries of the rectangular grid of blocks are defined such that some of the blocks of the rectangular grid of blocks include different numbers of pixels;
determining, for respective blocks of the rectangular grid of blocks, respective intensity values corresponding to pixels included within the respective blocks of the rectangular grid of blocks;
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective block values based on the respective intensity values;
generating fingerprint data for the frame based on the respective block values; and
storing, in a reference database, the fingerprint data in association with an identifier of the reference video.
11. The non-transitory computer-readable medium of claim 10 , wherein the rectangular grid of blocks has a spatial extent, in pixels, of J×K, wherein J is an integer that is greater than one, and wherein K is an integer that is greater than one.
12. The non-transitory computer-readable medium of claim 11 , wherein determining, for respective blocks of the rectangular grid of blocks, respective block-descriptor values based on the respective intensity values comprises computing, for respective blocks of the rectangular grid of blocks, L respective block values based on the respective intensity values, wherein L is an integer that is greater than or equal to one.
13. The non-transitory computer-readable medium of claim 12 , wherein generating the fingerprint data for the frame based on the respective block values comprises deriving a descriptor from the L block values for multiple blocks of the rectangular grid of blocks.
14. A non-transitory computer-readable medium having stored therein instructions that are executable by one or more computers to cause a video fingerprint system to perform functions comprising:
establishing a rectangular grid of blocks overlaying pixels of a frame of a query video, wherein each block of the rectangular grid of blocks includes a grid of pixels, and wherein boundaries of the rectangular grid of blocks are defined such that some of the blocks of the rectangular grid of blocks include different numbers of pixels;
determining, for respective blocks of the rectangular grid of blocks, respective intensity values corresponding to pixels included within the respective blocks of the rectangular grid of blocks;
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective block values based on the respective intensity values;
generating fingerprint data for the frame based on the respective block values; and
identifying a reference video corresponding to the query video using the fingerprint data and a reference database.
15. The non-transitory computer-readable medium of claim 14 , wherein the reference database stores reference fingerprint data for the reference video, and wherein identifying the reference video using the fingerprint data comprises comparing the fingerprint data with the reference fingerprint data.
16. A video fingerprinting system comprising:
a processing unit; and
a computer-readable medium having stored therein instructions that are executable by one or more computers to cause the video fingerprinting system to perform functions comprising:
establishing a rectangular grid of blocks overlaying pixels of a frame of a reference video, wherein each block of the rectangular grid of blocks includes a grid of pixels, and wherein boundaries of the rectangular grid of blocks are defined such that some of the blocks of the rectangular grid of blocks include different numbers of pixels,
determining, for respective blocks of the rectangular grid of blocks, respective intensity values corresponding to pixels included within the respective blocks of the rectangular grid of blocks,
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective block values based on the respective intensity values,
generating fingerprint data for the frame based on the respective block values, and storing, in a reference database, the fingerprint data in association with an identifier of the reference video.
17. The video fingerprinting system of claim 16 , wherein the rectangular grid of blocks has a spatial extent, in pixels, of J×K, wherein J is an integer that is greater than one, and wherein K is an integer that is greater than one.
18. The video fingerprinting system of claim 17 , wherein determining, for respective blocks of the rectangular grid of blocks, respective block-descriptor values based on the respective intensity values comprises computing, for respective blocks of the rectangular grid of blocks, L respective block values based on the respective intensity values, wherein L is an integer that is greater than or equal to one.
19. A video fingerprinting system comprising:
a processing unit; and
a computer-readable medium having stored therein instructions that are executable by one or more computers to cause the video fingerprinting system to perform functions comprising:
establishing a rectangular grid of blocks overlaying pixels of a frame of a query video, wherein each block of the rectangular grid of blocks includes a grid of pixels, and wherein boundaries of the rectangular grid of blocks are defined such that some of the blocks of the rectangular grid of blocks include different numbers of pixels,
determining, for respective blocks of the rectangular grid of blocks, respective intensity values corresponding to pixels included within the respective blocks of the rectangular grid of blocks,
determining, for respective blocks of the rectangular grid of blocks, using the video fingerprinting system, respective block values based on the respective intensity values,
generating fingerprint data for the frame based on the respective block values, and
identifying a reference video corresponding to the video using the fingerprint data and a reference database.
20. The video fingerprinting system of claim 19 , wherein the reference database stores reference fingerprint data for the reference video, and wherein identifying the reference video using the fingerprint data comprises comparing the fingerprint data with the reference fingerprint data.