Method and apparatus for multi-dimensional content search and video identification
View Patent ↗A multi-dimensional database and indexes and operations on the multi-dimensional database are described which include video search applications or other similar sequence or structure searches. Traversal indexes utilize highly discriminative information about images and video sequences or about object shapes. Global and local signatures around keypoints are used for compact and robust retrieval and discriminative information content of images or video sequences of interest. For other objects or structures relevant signature of pattern or structure are used for traversal indexes. Traversal indexes are stored in leaf nodes along with distance measures and occurrence of similar images in the database. During a sequence query, correlation scores are calculated for single frame, for frame sequence, and video clips, or for other objects or structures.
1. A method of storing a video clip in a multi-dimensional content database, the method comprising:
partitioning a multi-dimensional content database by a plurality of pivots, wherein each pivot is a center point around which corresponding vector signatures are organized and wherein each pivot is coupled to a plurality of leaf nodes;
generating a multi-dimensional vector signature from pre-specified and measurable characteristics that are extracted from a region of interest in a frame of a video clip having multi-dimensional content and that exceed a pre-specified threshold, wherein the multi-dimensional vector signature includes a compare pivot component that supports traversal from a pivot selected from the plurality of pivots to a leaf node selected from a plurality of associated leaf nodes;
storing data associated with the video clip at the selected leaf node of the multi-dimensional content database wherein the selected pivot is coupled to the plurality of associated leaf nodes including the selected leaf node; and
accessing the data associated with the video clip utilizing the multi-dimensional vector signature to select a pivot by matching the compare pivot component to the selected pivot and having an address to the data stored in the selected leaf node of the multi-dimensional content database.
2. The method of claim 1 further comprising:
dividing up the region of interest into segments, wherein the region of interest contains a contour of an image;
computing a set of histograms for data characteristics of each segment; and
comparing each of the histogram of the set of histograms to a threshold to generate the multi-dimensional vector signature for the region of interest.
3. The method of claim 1 , wherein multi-dimensional signatures from two selected frames are combined and used as a single combined signature, wherein the single combined signature is distinguishable from signatures generated from an individual frame to identify the video clip from a large set of video clips.
4. The method of claim 1 , wherein the video clip is a sequence of video frames comprising multi-dimensional data.
5. The method of claim 1 , wherein frames are selected using a descriptive parameter of the video clip including a sum of mean absolute difference (MAD) between frames and selecting the frames based on the descriptive parameter minima or maxima.
6. The method of claim 1 , wherein frames are selected from a compressed video stream based on a rate of information change which can be tracked using a sum of differences of the change between frames.
7. The method of claim 1 , wherein the multi-dimensional vector signature is generated based on first and second order gradient features along two orthogonal axes at a point of interest in the region of interest.
8. The method of claim 1 , wherein the multi-dimensional vector signature is generated based on first and second order gradient features along two orthogonal axes at points of interest and phase relationships between pixels on a contour shape in the region of interest.
9. The method of claim 8 , wherein the multi-dimensional vector signature is generated based on color similarity of pixels in the region of interest.
10. The method of claim 1 , wherein the data associated with the video clip stored at the leaf node includes an object location and size information.
11. A method of generating a likelihood score for matching frames of a query video clip and an original video clip, the method comprising:
generating similarity measures between a queries of a video clip and an original video clip based on, for each query, an amount that an individual frame similarity score exceeds a threshold score and represents clips with a high degree of similarity, wherein the original video clip is an entry in a video database;
generating a time correlation using relative differences in frame numbers for queries i and j and associated original video frames for the queries i and j, wherein the queries of the video clip includes a sequence of queries 0, 1, 2, . . . , i, . . . j, . . . where j>i in the sequence; and
generating a correlation score between the original video clip and the queries of the video clip based on a summation from the first element to the last element of a combination of the similarity measures according to the time correlation for matching signature pairs in the sequence of queries 0, 1, 2, . . . , i, . . . j, . . . , wherein each signature pair includes a query signature and an original video signature and their associated frame numbers.
12. The method of claim 11 , wherein a sequence window length having a correlation score that exceeded a threshold and passed a false positive analysis is selected as representing a likely matching video sequence of video frames comprising multi-dimensional data.
13. The method of claim 11 , wherein the time correlation uses a relative time rate between the original video clip and the queries of the video clip as determined by a first few matching signatures between the original video clip and the queries of the video clip.
14. The method of claim 11 , wherein the correlation score between the queries of the video clip and original video clip includes a factor of a change in the signatures of the each sequence in the queries of the video clip.
15. The method of claim 11 , wherein the correlation score between the queries of the video clip and the original video clip includes, during the signature score computation, a correlation that emphasizes the matches between changing information of the query signature using an entropy between correlated queries i and j.
16. The method of claim 11 , wherein the combination of the similarity measures includes:
a frame correlation measure between query frames for queries i and j and the associated original video frames for the queries i and j.
17. A method to identify a document, the method comprising:
converting classified categories of recorded document data representing aspects of the recorded document data into a multi-dimensional vector signature, wherein each aspect provides a dimension of the multi-dimensional vector signature;
determining uniqueness is high for the multi-dimensional vector signature by analysis of a term frequency of signatures within a specified distance of the multi-dimensional vector signature that indicates a number of similar multi-dimensional vector signatures within the specified distance is less than a specified value;
using a hash of the multi-dimensional vector signature having high uniqueness as an address to data stored in a leaf node of a content database to access an associated signature at the leaf node of the content database; and
correlating the associated signature with stored signatures obtained in a search of the content database to identify the document that was recorded.
18. The method of claim 17 wherein the converting comprises:
classifying the recorded document data into categories representing aspects of the recorded document data into a plurality of dimensions of the document; and
combining the plurality of dimensions to generate the multi-dimensional vector.
19. The method of claim 17 , wherein identification of a video clip is used along with other user and online website parameters to predict a user state or a user activity interest.
20. The method of claim 17 , wherein the search of the content database produces nearest matching results that are used to generate one or more correlation scores.
21. The method of claim 20 , based on the one or more correlation scores likely matching document data are evaluated in a second database search.
22. The method of claim 17 , wherein the search of the content database is performed to find uniqueness which is directly related to the number of similar signatures found within a specified distance measure.
23. A method to identify a match between a query object and stored object data, the method comprising:
calculating a distance between signatures of a query object and signatures of stored object data in a database to generate a similarity score for signatures within the calculated distance, wherein a signature of an object is generated using weighted values on contours of the object within an identified region of interest;
determining a unique information content value is high by analysis of a term frequency of the signatures of the query object within the calculated distance that indicates a number of similar signatures within the calculated distance is less than a specified value; and
selecting signatures from the stored object data having similarity scores that exceed a threshold and a calculated high unique information content value for the query object and for the identified region of interest, wherein the selected unique signatures retain differentiating information for each of the stored object data in the database.
24. The method of claim 23 further comprising:
identifying candidate matching frames based on the selected unique signatures; and
correlating changes in the unique signatures between the query object and the stored object data associated with the candidate matching frames as a factor in a sequence correlation score to identify a likely matching stored object data.
25. The method of claim 23 , wherein the unique information content value is directly related to a number of similar signatures within a given distance measure.
26. The method of claim 23 , wherein the signatures of the stored object data that have high unique information content value are retained compared to signatures of the stored object data that have lower unique information content value, wherein the unique information content value is a measure based on a statistical evaluation of similar signatures within a given distance measure.