Media fingerprinting and identification system

1. A method for media content identification in multimedia content, the method comprising:

generating an N-dimension reference signature and a compact traversal hash reference signature based on an N-dimension reference descriptor for a reference media content feature identified in a frame of a reference video sequence;

storing the N-dimension reference signature and a link to the reference media content feature at a location in a reference database that is addressable by the compact traversal hash reference signature;

generating an N-dimension query signature and a compact traversal hash query signature based on an N-dimension query descriptor for a query media content feature selected from a monitored video sequence; and

searching the reference database using the compact traversal hash query signature to select reference signatures that are within a specified signature distance from the N-dimension query signature.

2. The method of claim 1 , wherein the selected reference signatures are marked as candidate reference signatures and the reference media content feature is a reference image feature.

3. The method of claim 2 further comprising:

sorting the candidate reference signatures according to a count of times that a closely matching signature appears in the candidate reference signatures to find a likely matching reference media content feature, wherein the reference media content feature is a member of a plurality of reference media content features stored in the reference database.

4. The method of claim 2 further comprising:

determining a plurality of scores, wherein each score is based on a distance between the N dimension query signature and a different one of the candidate reference signatures; and

comparing the plurality of scores with a score threshold to determine whether a reference media content feature associated with a score is a true positive match or a false positive match.

5. The method of claim 1 further comprising:

generating the N-dimension query descriptor for the query media content feature identified in a frame of video data received on a portable device, wherein the query media content feature is a query image feature;

quantizing the N-dimension query descriptor with a first threshold to form the N-dimension query signature;

combining dimensions of the N-dimension query descriptor to generate a combined descriptor; and

quantizing the combined descriptor with a second threshold to form the compact traversal hash query signature.

6. The method of claim 1 further comprising:

augmenting the compact traversal hash query signature with bit information that identifies a spatial location of the query media content feature.

7. The method of claim 1 further comprising:

augmenting the compact traversal hash query signature with bit information that identifies a scale value in the x-direction (sx) and a scale value in the y-direction (sy) of the query media content feature.

8. The method of claim 1 further comprising:

augmenting the compact traversal hash query signature with bit information that identifies a peak polarity of the query media content feature that indicates whether the query media content feature is a light coloring on a dark background or a dark coloring on a light background.

9. The method of claim 1 further comprising:

augmenting the compact traversal hash query signature with bit information based on a histogram of pixel intensity values in a pixel area that encompasses the query media content feature.

10. The method of claim 1 further comprising:

searching a reference multimedia clip database on a remote server accessible by a portable device using the traversal hash query signature to find remote reference signatures that are within a specified signature distance from the N-dimension query signature.

11. The method of claim 1 further comprising:

generating on a server remote from a portable device an N-dimension reference signature and a compact traversal hash reference signature based on an N-dimension reference descriptor for a selected reference media content feature as used in a frame of a reference video sequence; and

storing the N-dimension reference signature and a link to the reference media content feature at a location in a reference database on the remote server that is addressable by the compact traversal hash reference signature, wherein the reference media content feature is a member of a plurality of reference media content features.

12. A method for storing a plurality of identified image features in a reference database, the method comprising:

determining a location of a center of a region of interest for each identified image feature of the plurality of image features, wherein the region of interest for each identified image feature is specified by dimensions within an image frame and by a scale in the x-direction (sx) and a scale in the y-direction (sy);

creating for each identified image feature an image grid of Bx by By subregions at the center location according to the sx and sy values and each Bx by By subregion having a grid made up of Cx by Cy pixels;

computing x-gradient values based on pixel intensity differences in the x-direction and y-gradient values based on pixel intensity differences in the y-direction in each grid of Cx by Cy pixels;

concatenating weighted sums of the x-gradient values with weighted sums of the y-gradient values for each Bx by By subregion to create an N-dimension image feature descriptor for each identified image feature of the plurality of image features; and

storing the N-dimension image feature descriptors and their associated identified image feature of the plurality of image features in the reference database.

13. The method of claim 12 further comprising:

combining dimensions of each N-dimension image feature descriptor to generate a combined image feature descriptor for each identified image feature of the plurality of image features; and

quantizing each of the combined image feature descriptors with a traversal hash threshold to form a compact traversal hash image feature signature for each identified image feature of the plurality of image features, wherein each N-dimension image feature descriptor and its associated identified image feature of the plurality of image features is stored in the reference database according to the compact traversal hash image feature signature.

14. The method of claim 12 , wherein the reference database is located on a portable device.

15. The method of claim 12 further comprising:

adjusting individually the sx and sy values and center location for each identified image feature of the plurality of image features to account for an expected error margin due to a known type of image distortion;

generating a second N-dimension image feature descriptor for each identified image feature of the plurality of image features according to the functions of each Bx by By subregion as adjusted according to the expected error margin.

16. A computer readable non-transitory medium storing a computer program which causes a computer system to perform a method for image identification in multimedia content received from a source external to a portable device, the method comprising:

generating on a portable device an N-dimension reference signature and a compact traversal hash reference signature based on an N-dimension reference descriptor for a reference image feature identified in a frame of a reference video sequence;

storing the N-dimension reference signature and a link to the reference image feature at a location in a reference database on the portable device that is addressable by the compact traversal hash reference signature;

generating on the portable device an N-dimension query signature and a compact traversal hash query signature based on an N-dimension query descriptor for a query image feature selected from a monitored video sequence; and

searching the reference database on the portable device using the compact traversal hash query signature to select reference signatures that are within a specified signature distance from the N-dimension query signature, the selected reference signatures are marked as candidate reference signatures.

17. The computer readable non-transitory medium of claim 16 , wherein the reference database is located on a remote server accessible by the portable device.

18. The computer readable non-transitory medium of claim 16 further comprising:

creating in an image a grid of Bx by By subregions centered at an interest point of a region of interest that encompasses the query image feature, the region of interest having dimensions specified by a scale x (sx) value and scale y (sy) value, wherein each subregion having a grid of Cx by Cy pixel positions;

computing x-gradient values based on pixel intensity differences in an x direction and y-gradient values based on pixel intensity differences in a y direction in each grid of Cx by Cy pixel positions; and

concatenating weighted sum of x-gradient values with weighted sum of y-gradient values for each subregion of the Bx by By subregions to create the N-dimension query descriptor.

19. The computer readable non-transitory medium of claim 18 further comprising:

changing the scale sx value and the scale sy value by a multiplicative factor for the grid of Bx by By subregions to generate a second N-dimension query descriptor for the same query image feature; and

using a first traversal hash reference signature determined from the N-dimension query descriptor and a second traversal hash reference signature determined from the second N-dimension query descriptor to improve chances of finding reference images that are similar to the query image feature.

20. The computer readable non-transitory medium of claim 16 further comprising:

organizing in the reference database a traversal hash signature array to contain a plurality of compact traversal hash reference signatures, wherein each compact traversal hash reference signature identifies a cluster of N-dimension reference signatures each having a link to an associated reference image feature.

21. A method for converting received media content into a multi-dimensional vector, the method comprising:

detecting a feature of the received media content according to the type of media content being received;

classifying aspects of the detected feature, wherein each classified aspect is a dimension of the detected feature;

quantifying each aspect to generate a multi-dimensional vector representing the detected feature; and

applying a first threshold to the multi-dimensional vector to generate a signature having the same number of dimensions as the multi-dimensional vector, in parallel combining values of various dimensions of the multi-dimensional vector to generates a reduced number of combined dimensions, and applying a second threshold to the reduced number of combined dimensions to generate a traversal hash signature.

22. The method of claim 21 , wherein the type of media content being received includes a plurality of documents.

23. The method of claim 21 , wherein the type of media content being received includes a plurality of object views.

24. The method of claim 21 , wherein the type of media content being received includes a plurality of records of recorded events.

25. The method of claim 21 further comprising:

determining a next activity in a user session based on a decision tree according to the classified aspects of the detected feature, wherein the type of media content being received includes a plurality of activities in the user session.

26. The method of claim 21 further comprising:

learning by inference a next activity in a user session based on a rules based system according to prior classified aspects of the detected feature, wherein the type of media content being received includes a plurality of activities recorded in the user session.

27. The method of claim 21 , wherein the received media content includes documents, events, and activity for learning by inference that are individually classified by the multi-dimensional vector.