Method and Apparatus for Multi-Dimensional Content Search and Video Identification

• US 20080313140A1
• Filed: 06/18/2008
• Published: 12/18/2008
• Est. Priority Date: 06/18/2007
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Stojancic, Mihailo M., Merchant, Shashank, Pereira, Jose Pio
• Granted Patent: US 8,171,030 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06F 16/7854 using shape G06F16/7837 takes precedence
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/10 Segmentation; Edge detection motion-based segmentation G06T7/215
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 20/41 Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items segmenting video sequences G06V20/49
• CPC Class Codes: G06V 20/44 Event detection
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

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.

Claims

1. A method of organization of a multi-dimensional video using a compact hash of multi-dimensional vector signature as a traversal index, the method comprising;

generation of a robust hash as a traversal index from multiple parameters extracted from a region of interest in a frame or from a frame of a video sequence; and

storing multiple associated data or signatures at a leaf node of a multi-dimensional video database.

2. The method of claim 1 further comprising:

using as traversal indexes a shape signature for a region around the selected keypoint or a frame or gradient signature or a combination of i) each keypoint of image'"'"'s global shape signature and ii) the motion description around the regions around the keypoint, and iii) global signatures of the image.

3. The method of claim 2 further comprising:

computing a set of histograms to generate the shape signature while using the center of a frame or the selected keypoint, as a reference for the shape signature; and

creating a weighted sum of features extracted at points on the contour shape in each sector of multiple rings around the center of the frame and having a reference orientation around a selected axis.

4. The method of claim 1 where the traversal index of the multi-dimensional video database uses pivot values around cluster centers.

5. The method of claim 1 where the database is generated from multiple views and aspects of an object.

6. The method of claim 1 wherein the traversal index is generated from the shape signature of a region around a selected object in the image frame.

7. The method of claim 6 further comprising:

computing a set of histograms to generate the shape signature while using the center as a point on a contour shape; and

creating a weighted sum of features extracted at points on the contour shape in each sector of multiple rings around the center and having a reference orientation around a selected axis.

8. The method of claim 1 wherein the generation of the traversal index comprises;

generating the traversal index from multiple parameters extracted from an object or object bounding boxes in a frame of a video sequence.

9. The method of claim 1, wherein the region around a selected region of interest is used to generate the traversal index and the leaf node stores the location and size of the region.

10. The method of claim 1 wherein the traversal index uses a single bit or a few bits per each dimension for multi-dimensional vector.

11. The method of claim 1 wherein the traversal index uses signatures generated from unique video sequence or other multi-dimensional content, the signatures based on content in selected 2 frames.

12. The method of claim 1 wherein the frames could be selected using any descriptive parameter of the video including sum of mean absolute difference (MAD) between frames and selecting the parameter minima or maxima.

13. The method of claim 1 wherein signatures from a selected 2 frames are combined and used as a single combined signature, wherein the single combined signature reduces the correlation cost of storage and processing required between the large set of possible sequences.

14. The method of claim 1 wherein the signature is centered around a region of interest and includes shape, gradient and motion feature histograms in sectors and bins.

15. The method of claim of 1 wherein the signature is generated based on a set of local features around the region of interest.

16. The method of claim 15 wherein the local features include a set of features formed within the region of interest and second order gradient features within the region of interest.

17. The method of claim of 15 wherein the signature is generated based on local features around the region of interest as well as global features around the region of interest, wherein the global features include texture and color of the image.

18. The method of claim 15 wherein the local features comprise first and second order gradient features.

19. The method of claim of 1 and wherein the signature is generated based on local features around the region of interest wherein the local features comprise shape features within the region of interest and the local features based on motion direction.

20. A method to post process signatures and associated data between a video sequence of interest or an object region associated with a query object or a video sequence to increase accuracy and confidence of a video sequence match, the method comprising:

calculating the distance between the signatures of the query and original video features including a region around a keypoint, or an object or a frame;

correlating changes in signatures between a query and a database entry for a matching frame, object, or structure to provide a factor in a sequence correlation score; and

providing a sequence correlation in time using differences in frame numbers between pairs of matching query and original video signatures.

21. The method of claim 20 further comprising:

calculating a unique information value of signatures and selecting signatures having high unique information content that retain differentiating information between video sequences or items of interest.

22. The method of claim 20 wherein the correlation is performed in space using the location and scale of the matching feature points or objects of pairs of matching original and query signatures.

23. A method of generating a likelihood score for a pair of query frames or regions and correlating between matching frames of the query and original video, the method comprising:

generating a correlation score based on an individual frame similarity score;

generating a time correlation using relative differences in frame numbers of the original video and the query video; and

generating a correlation between the original video and the query video by using a change in signatures of each sequence of frames in the query video and in the original video, wherein the original video is an entry in a video database.

25. The method of claim 23 wherein the correlation score between the query video sequence and original video sequence includes a factor of a change in the signatures of the each sequence in the query or that includes during the signature score computation a correlation that emphasizes the matches between changing information of the query signature.

24. The method of 23 where time correlation uses the relative time rate between the original and query as determined by the first few matching signatures between the original and query video.

26. A method to convert documents or activity such as online user session information or any natural event or activity into multi-dimensional vectors, the method comprising:

classifying documents, events, activity for learning by inference by a multi-dimensional vector; and

expecting certain behavior or next state in an activity, wherein the expected next state or the certain behavior is generated by a decision tree or a rule based system that takes as input one or more identified documents or classifications.

27. The method of 26 wherein identification of a video or object is used along with other user and online website parameters to predict a user state or a user activity interest.