Processing digital video using trajectory extraction and spatiotemporal decomposition

• US 8,050,454 B2
• Filed: 12/29/2006
• Issued: 11/01/2011
• Est. Priority Date: 12/29/2006
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kozintsev, Igor, Polito, Marzia, Yi, Haoran
• Primary Examiner(s): KOZIOL, STEPHEN R
• Application Number:
  US11/618,410
• Publication Number:
  US 20080159590A1
• Time in Patent Office: 1,768 Days
• Field of Search: 382/100, 382/103, 382/190, 725/113, 348/143, 345/473, 345/475
• US Class Current: 382/103
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30241 Trajectory
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• 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

Abstract

Methods to process digital video using trajectory extraction and spatiotemporal decomposition for search and retrieval of video are described. An example method extracts interest point data from data representing a plurality of video frames. The interest point data is extracted from each of the video frames independent of the other video frames. Subsequent to extracting the interest point data, the example method links at least some of the interest point data to generate corresponding trajectory information. The example method also clusters the trajectory information to form clustered trajectory information and extracts a representative feature index from the clustered trajectory information.

Claims

1. A method comprising:

extracting interest point data from data representing a plurality of video frames, wherein the interest point data is extracted from each of the video frames independent of the other video frames;

subsequent to the extracting of the interest point data, linking at least some of the interest point data to generate corresponding trajectory information by;

linking first interest point data from a first video frame to second interest point data from a second video frame that is separated from the first video frame by a quantity of intermediate video frames, and

linking third interest point data from the second video frame to fourth interest point data from a third video frame that is separated from the second video frame by the same quantity of intermediate video frames;

clustering the trajectory information to form clustered trajectory information;

extracting, via a processor, a representative feature index from the clustered trajectory information; and

indexing the video frames in a database to be searchable based on the representative feature index.

2. The method as defined in claim 1, wherein extracting the interest point data from the data representing the plurality of video frames comprises extracting a set of distinct points from each of the video frames.

3. The method as defined in claim 1, wherein extracting the representative feature index from the clustered trajectory information comprises decomposing video data into a plurality of spatiotemporal regions.

4. The method as defined in claim 1, wherein linking at least some of the interest point data to generate corresponding trajectory information comprises linking data between at least two of the video frames.

5. The method as defined in claim 4, wherein linking the data between the at least two of the video frames comprises comparing similarity scores associated with the video frames and forming a link between the at least two frames based on the comparison.

6. The method as defined in claim 1, wherein clustering the trajectory information comprises clustering the trajectory information into at least one of foreground or background clusters.

7. The method as defined in claim 1, wherein clustering the trajectory information comprises clustering the trajectory information based on at least one of temporal or spatial information.

8. The method as defined in claim 7, wherein at least one of the temporal or spatial information comprises clues.

9. A method comprising:

processing a plurality of video frames composing a video segment to extract spatial information from each of the video frames;

subsequent to processing the plurality of video frames to extract the spatial information, linking at least some of the spatial information between at least some of the video frames to generate trajectory information by;

linking first interest point data from a first video frame to second interest point data from a second video frame that is separated from the first video frame by a quantity of intermediate video frames, and

linking third interest point data from the second video frame to fourth interest point data from a third video frame that is separated from the second video frame by the same quantity of intermediate video frames;

extracting, via a processor, a representative feature index from the trajectory information; and

indexing the video frames in a database to be searchable based on the representative feature index.

10. The method as defined in claim 9, wherein processing the plurality of video frames to extract the spatial information comprises extracting a set of distinct points from each of the video frames.

11. The method as defined in claim 9, wherein extracting the representative feature index from the trajectory information comprises decomposing video data into a plurality of spatiotemporal regions.

12. The method as defined in claim 9, wherein linking the at least some of the spatial information to generate the trajectory information comprises linking data between at least two of the video frames.

13. An article of manufacture storing machine accessible instructions which, when executed, cause a machine to:

process a plurality of video frames composing a video segment to extract spatial and temporal information from each of the video frames;

subsequent to processing the video frames, extract the spatial information, linking at least some of the spatial information between at least some of the video frames to generate trajectory information by;

linking first interest point data from a first video frame to second interest point data from a second video frame that is separated from the first video frame by a quantity of intermediate video frames, and

linking third interest point data from the second video frame to fourth interest point data from a third video frame that is separated from the second video frame by the same quantity of intermediate video frames;

extract a representative feature index from the trajectory information; and

index the video frames in a database to be searchable based on the representative feature index.

14. The article of manufacture as defined in claim 13, wherein the instructions, when executed, cause the machine to process the plurality of video frames to extract the spatial information by extracting a set of distinct points from each of the video frames.

15. The article of manufacture as defined in claim 14, wherein the instructions, when executed, cause the machine to extract the representative feature index from the trajectory information by decomposing video data into a plurality of spatiotemporal regions.