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 method for generating a digital representation of an image feature in multimedia content, the method comprising:
receiving from a source of multimedia content a sequence of image data that is combined into frames, time stamped, and stored as received frames on a user personal device;
reducing the received frames to selected frames that represent the multimedia content to be processed on the user personal device based on temporal coherence of the multimedia content across multiple time stamped frames;
determining center coordinates (centerx, centery) of an interest point in an image feature and a scale in an X-direction (Sx) and a scale in a Y-direction (Sy) for the image feature detected in a frame of the selected frames;
establishing a grid of blocks located at the (centerx, centery) coordinates of the image feature with spatial extent of JSx by KSy, wherein each block contains a grid of pixels and wherein J and K are multiplication factors which determine size of the neighborhood around the interest point;
computing M functions of pixel intensity values of the pixels in each grid of pixels to produce M function results for each block; and
generating a first digital representation of the image feature as a concatenation of the M function results for each block of the established grid of blocks, wherein the concatenation produces the first digital representation as a first N dimension descriptor of the image feature.
2. The method of claim 1 further comprising:
adjusting individually the Sx, Sy, and (centerx, centery) coordinates by a pre-specified error percentage to account for image distortions and to generate for each adjustment at least a second N dimension descriptor as a concatenation of the M functions for each block of the established grid of blocks as adjusted according to the pre-specified error percentage.
3. The method of claim 2 , wherein the first N dimension descriptor and the second N dimension descriptor are stored in a media content database on the user personal device as part of a set of N dimension descriptors that represent other image features in the selected frames that represent the multimedia content.
4. The method of claim 2 , wherein the first N dimension descriptor and the second N dimension descriptor are used to search a media content database on the user personal device having sets of N dimension descriptors for different multimedia content.
5. The method of claim 1 further comprising:
computing the M functions as multiple intensity differences between each pixel in a block's grid of pixels and another pixel at a pre-specified pixel offset.
6. The method of claim 1 further comprising:
computing, for each pixel in the block's grid of pixels, weighted gradient values in the x direction and weighted gradient values in the y direction that are combined to produce the M function results.
7. The method of claim 1 further comprising:
applying a first threshold to the first N dimension descriptor to produce a first N dimension signature;
combining dimensions of the first N dimension descriptor to produce a first combined dimension descriptor, and
applying a second threshold to the first combined dimension descriptor to produce a first traversal hash signature.
8. The method of claim 7 further comprising:
storing the first N dimension signature and the second N dimension signature at a location in a media content database on the user personal device addressable by the first traversal hash signature.
9. The method of claim 7 further comprising:
searching a media content database on the user personal device using the first traversal hash signature in a query to find reference N dimension signatures that are within a specified signature distance from the first N dimension signature that accompanies the first traversal hash signature in the query.
10. A method for generating a digital representation of an image feature in multimedia content, the method comprising:
receiving from a source of multimedia content a sequence of image data that is combined into frames, time stamped, and stored as received frames on a user personal device;
reducing the received frames to selected frames that represent the multimedia content to be processed on the user personal device based on temporal coherence of the multimedia content across multiple time stamped frames;
determining center coordinates (centerx, centery) of an image feature and a scale in an X-direction (Sx) and a scale in a Y-direction (Sy) for the image feature detected in a frame of the selected frames;
establishing a Bx by By grid of pixels located at the (centerx, centery) coordinates of the image feature with spatial extent of JSx by KSy, wherein the Bx by By grid of pixels is sub-divided into blocks, each block having a subset of pixels from the Bx by By grid of pixels and wherein J and K are multiplication factors which determine size of a neighborhood around the (centerx, centery) coordinates;
generating a first digital representation of the image feature as a concatenation of results from M gradient functions calculated for each block of the established Bx by By grid of pixels, wherein the concatenation produces the first digital representation as a first N dimension descriptor of the image feature; and
applying a first threshold to the first N dimension descriptor to generate a binary first N dimension signature representation of the image feature.
11. The method of claim 10 further comprising:
adjusting individually the Sx, Sy, and (centerx, centery) coordinates by a pre-specified error percentage to account for image distortions and to generate for each adjustment at least a second N dimension descriptor as a concatenation of results from the M gradient functions for each block of the established Bx by By grid of pixels as adjusted according to the expected error percentage; and
applying the first threshold to the second N dimension descriptor to generate a binary second N dimension signature representation of the image feature.
12. The method of claim 11 , wherein the binary first N dimension signature and the binary second N dimension signature are stored in a media content database on the user personal device as part of a set of binary N dimension signatures that represent other image features in the selected frames that represent the multimedia content.
13. The method of claim 11 , wherein the binary first N dimension signature and the binary second N dimension signature are stored in a media content database on a server remote from the user personal device as part of a set of binary N dimension signatures that represent other image features in the selected frames that represent the multimedia content.
14. The method of claim 11 , wherein the binary first N dimension signature and the binary second N dimension signature are used to search a media content database on the user personal device having sets of binary N dimension signatures for different multimedia content.
15. The method of claim wherein 11 , the binary first N dimension signature and the binary second N dimension signature are used to search a media content database on the user personal device having sets of binary N dimension signatures for different multimedia content; and
upon determining the search of the media content database on the user personal device was not successful, searching for the binary first N dimension signature and the binary second N dimension signature on a media content database on a remote server.
16. The method of claim 10 further comprising:
computing multiple intensity differences for each pixel in each block having a subset of pixels from the Bx by By grid of pixels to another pixel in both x and y directions for a pre-specified pixel offset; and
computing weighted sum combinations of the multiple intensity differences as x-gradient values and as a y-gradient values to produce the results from the M gradient functions.
17. The method of claim 10 further comprising:
combining dimensions of the first N dimension descriptor to produce a first combined dimension descriptor; and
applying a second threshold to the first combined dimension descriptor to produce a first traversal hash signature.
18. The method of claim 17 further comprising:
storing the first N dimension signature and the second N dimension signature at a location in a media content database on the user personal device addressable by the first traversal hash signature.
19. The method of claim 17 further comprising:
searching a media content database on the user personal device using the first traversal hash signature in a query to find reference N dimension signatures that are within a specified signature distance from the first N dimension signature that accompanies the first traversal hash signature in the query.
20. A computer readable non-transitory medium storing a computer program which causes a computer system to perform a method for generating a digital representation of an image feature in multimedia content, the method comprising:
receiving from a source of multimedia content a sequence of image data that is combined into frames, time stamped, and stored as received frames on a user personal device;
reducing the received frames to selected frames that represent the multimedia content to be processed on the user personal device based on temporal coherence of the multimedia content across multiple time stamped frames;
determining center coordinates (centerx, centery) of an image feature and a scale in an X-direction (Sx) and a scale in a Y-direction (Sy) for the image feature detected in a frame of the selected frames;
establishing a Bx by By grid of pixels located at the (centerx, centery) coordinates of the image feature with spatial extent of JSx by KSy, wherein the Bx by By grid of pixels is sub-divided into blocks, each block having a subset of pixels from the Bx by By grid of pixels and wherein J and K are multiplication factors which determine size of a neighborhood around the (centerx, centery) coordinates;
generating a first digital representation of the image feature as a concatenation of results from M gradient functions calculated for each block of the established Bx by By grid of pixels, wherein the concatenation produces the first digital representation as a first N dimension descriptor of the image feature; and
applying a first threshold to the first N dimension descriptor to generate a binary first N dimension signature representation of the image feature.