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 an object detected in a video clip in a multi-dimensional content database, the method comprising:
generating a shape signature using multi-bit histogram bins reduced to single bit histogram bins in sectored rings around a keypoint of an object detected in a frame of the video clip; and
storing data associated with the object in the video clip at a leaf node of the multi-dimensional content database having a plurality of leaf nodes, wherein the shape signature is used as an address to access the data associated with the object in the video clip from the leaf node.
2. The method of claim 1 further comprising:
dividing up a 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 shape signature for the region of interest.
3. The method of claim 1 , further comprising:
combining multi-dimensional signatures from two selected frames in the video clip as a single combined shape signature, wherein the single combined shape signature is unique and 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 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.
6. The method of claim 1 , wherein the shape signature is generated based on an intensity gradient features at the keypoint.
7. The method of claim 1 , wherein the shape signature is generated based on phase relationships between pixels on a contour shape in the a region of interest around the keypoint.
8. The method of claim 7 , wherein the signature is generated based on color similarity of pixels in the region of interest.
9. The method of claim 1 further comprising:
comparing a value of each bin of the multi-bit histogram bins to a threshold to determine a single bit hash value for the histogram bins in the sectored rings around the keypoint of the object.
10. The method of claim 1 further comprising:
partitioning the multi-dimensional content database according to the shape signature acting as a traversal index address to access the data from the leaf node.
11. A method of determining how likely a query video clip matches an original video clip, the method comprising:
generating a signature distance measure as a sum of differences in dimensions between an individual query signature generated from a frame of the query video clip and a selected original signature generated from a frame of the original video clip that when compared to a threshold indicates the frame of the query video clip and the frame of the original video clip are likely similar frames, wherein the original video clip is an entry in a video database and wherein a signature is comprised of multiple dimensions of an image in a frame of a video;
generating a time correlation to compare the likely similar frames of the query video clip and the original video clip by selecting different close-by frames of the original video clip and the query video clip to determine whether a close-by frame provides an improved distance measure indicating an better pair of matching frames; and
generating additional distance measurements and time correlations between a sequence of different frames of the query video clip and the original video clip to determine how likely the query video clip matches the original video clip.
12. The method of claim 11 , wherein the threshold is a value learned for a specified sequence of frames (sequence window length) having matching frames.
13. The method of claim 11 , wherein the time correlation uses a relative time rate between the original video clip and the query video clip as determined by a first few matching signatures between the original video clip and the query video clip.
14. The method of claim 11 , wherein the additional distance measurements and time correlations between the sequence of different frames of the query video clip and original video clip identifies gaps between frames of the query video clip that are similar to gaps between frames of the original video clip.
15. The method of claim 11 , wherein the determination of how likely the query video clip matches the original video clip includes a confidence value determined from rules based on learning a probability.
16. A method to identify a recorded event, the method comprising:
selecting data frames of the recorded event that are processed to form at least one query signature for each selected data frame, wherein each query signature is formatted into classified categories of aspects of the recorded event;
for a selected data frame, comparing the at least one query signature with signatures selected from a database to determine a number of database signatures that are similar to the at least one query signature within a pre-specified distance measure, wherein the number of database signatures that are similar indicates how unique the query signature is and identifies the query signature as a unique query signature among the database signatures; and
correlating the unique query signature for each selected data frame in a database search to identify the recorded event.
17. The method of claim 16 wherein the converting comprises:
formatting the classified categories representing the aspects of the recorded event into a plurality of dimensions of the event; and
combining the plurality of dimensions to generate the at least one query signature for each selected data frame.
18. The method of claim 16 , wherein identification of the recorded event is used along with other user and online website parameters to predict a user state or a user activity interest.
19. The method of claim 16 , wherein the database search produces nearest matching results that are used to generate one or more correlation scores.
20. The method of claim 19 , based on the one or more correlation scores likely matching video clips are processed to generate one or more sequence correlation scores, wherein a sequence correlation in time provides the one or more sequence correlation scores using differences in frame numbers between pairs of matching query and the nearest matching results.
21. The method of claim 16 , wherein the identified unique query signature is determined from a measurement that the number of database signatures that are similar to the at least one query signature within the pre-specified distance measure is less than a pre-specified value.