Computer program and apparatus for motion-based object extraction and tracking in video

• US 8,488,839 B2
• Filed: 03/16/2007
• Issued: 07/16/2013
• Est. Priority Date: 11/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: VideoSurf, Inc. (Microsoft Corporation)
• Inventors: Sharon, Eitan, Brandt, Achi
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): CONWAY, THOMAS A
• Application Number:
  US11/687,341
• Publication Number:
  US 20080118108A1
• Time in Patent Office: 2,314 Days
• Field of Search: None
• 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/215 Motion-based segmentation
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments

Abstract

A computer program and apparatus function to extract objects from a video by identifying regions to be tracked, tracking the regions across several frames, calculating motions of the regions, and identifying new regions to be tracked. Regions of a selected frame of the video that are appropriate for tracking are selected. Tracking of the identified regions is then performed across frames subsequent to the selected frame of the video. Motions of the identified regions are calculated, and new regions for tracking are identified.

Claims

1. A non-transitory computer usable medium having computer readable program code embodied therein for extracting objects from a video, the computer readable program code including:

computer readable program code for causing the computer to identify regions of a selected frame of the video appropriate for tracking movement of one or more salient objects appearing in the video;

computer readable program code for causing the computer to track identified regions across frames subsequent to said selected frame of the video;

computer readable program code for causing the computer to calculate motions of the identified regions including reacquiring tracking of a previously identified salient object for which tracking had been lost;

computer readable program code for causing the computer to identify new regions for tracking;

computer readable program code for causing the computer to collect tracking information related to the movement of the salient objects into one or more object-related tubes, each tube comprising a starting frame for which tracking of a salient object began though an ending frame at which tracking is terminated; and

the code identifying common salient objects to join corresponding object-related tubes;

computer readable program code for causing the computer to assign a weight to each object-related tube;

computer readable program code for causing the computer to receive search criteria specifying a target object and identifying videos having object related tubes satisfying the search criteria; and

computer readable program code for causing the computer to display videos having object-related tubes that match the target object and the corresponding weight associated with the target object.

2. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to identify regions of a selected frame of the video appropriate for tracking includes computer readable program code for causing the computer to extract local motion estimations for various points in the selected frame across said frames subsequent to said selected frame.

3. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to track said identified regions across said frames subsequent to said selected frame of the video includes computer readable program code for causing the computer determine whether a moveable object is trackable.

4. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to track said identified regions across said frames subsequent to said selected frame of the video includes computer readable program code for causing the computer determine whether one of said frames subsequent to said selected frame is substantially different from said selected frame.

5. The computer usable medium according to claim 1 wherein computer readable program code for causing the computer to calculate motions of the identified regions includes computer readable program code for causing the computer determine a motion of each of the identified regions of the selected frame across said frames subsequent to said selected frame.

6. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to calculate motions of the identified regions includes computer readable program code for causing the computer group together ones of said identified regions based on their common motion to generate more complex regions of interest.

7. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to calculate motions of the identified regions includes computer readable program code for causing the computer determine a camera motion and factor said camera motion out to identify salient objects that move differently from said camera motion.

8. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to calculate motions of the identified regions includes computer readable program code for causing the computer identify a salient object and continue tracking of said salient object.

9. The computer usable medium according to claim 1 wherein said computer readable program code for causing the computer to calculate motions of the identified regions includes computer readable program code for causing the computer to receiving user input designating a salient object of interest.

10. The computer usable medium according to claim 1 wherein each tube includes object related information including at least luminance, texture, shape, and motion information.

11. The computer usable medium according to claim 1 wherein the weight is determined based on at least one of any of:

the amount of time or the number of frames by which the salient objects are tracked relative to the total video length in comparison to one or more other tracked objects;

the volume or space occupied within the frames by the salient objects; and

the amount, speed and nature of the salient objects.

12. The computer usable medium according to claim 1 wherein the computer readable program code tracks movement of multiple salient objects and the code causing the computer to collect tracking information related to the movement and information related to the multiple salient objects, and each tube includes tracking information related to the multiple salient objects.

13. The computer program usable medium according to claim 1 wherein said computer readable program code for causing the computer to track said identified regions across said frames subsequent to said selected frame of the video includes a step of determining a motion of each of the identified regions of the selected frame across said frames subsequent to said selected frame.

14. The computer usable medium according to claim 13 wherein said step of determining a motion of each of the identified regions includes computer readable program code for causing the computer fit said identified regions to said frames subsequent to said selected frame.

15. The computer usable medium according to claim 13 wherein said step of determining a motion of each of the identified regions includes computer readable program code for causing the computer estimate local motion within said selected frame.

16. An apparatus for extracting objects from a video comprising:

a local tracking engine configured to identify regions of a selected frame of the video appropriate for tracking movement of one or more salient objects appearing in the video, said local tracking engine including a motion calculation engine; and

an interframe tracking engine receiving said identified regions from said local tracking engine and configured to identify regions across frames subsequent to said selected frame of the video, said motion calculation engine is configured to calculate motions of the identified regions including reacquiring tracking of a previously identified salient object for which tracking had been lost, said motion calculation engine configured to;

identify new regions for tracking based on determining whether one or more previously tracked salient objects have become untrackable, changes in the movement of the salient objects, new salient objects and changes in interactions between the salient objects; and

a tracking information collection engine, the tracking information collection engine collecting tracking information related to the movement of the salient objects into one or more object-related tubes, each tube comprising a starting frame for which object tracking began though an ending frame at which tracking was terminated; and

identify common salient objects to join corresponding object-related tubes.

17. The apparatus according to claim 16 wherein said local tracking engine includes a frame segmentation engine configured to segment at least one frame of the video to partition the at least one frame into coherent regions.

18. The apparatus according to claim 16 wherein said local tracking engine includes a local motion estimation engine configured to extract local motion estimations for various points in the selected frame across said frames subsequent to said selected frame.

19. The apparatus according to claim 16 wherein said local tracking engine includes a motion calculation engine configured to determine a motion of each of the identified regions of the selected frame across said frames subsequent to said selected frame.

20. The apparatus according to claim 16 wherein said local tracking engine includes an interframe motion estimation engine configured to determine whether one of said frames subsequent to said selected frame is substantially different from said selected frame.

21. The apparatus according to claim 16 wherein said motion calculation engine includes an interframe calculation engine configured to determine a motion of each of the identified regions of the selected frame across said frames subsequent to said selected frame.

22. The apparatus according to claim 16 wherein said motion calculation engine includes a region grouping engine configured to group together ones of said identified regions based on their common motion to generate more complex regions of interest.

23. The apparatus according to claim 16 wherein said motion calculation engine includes a relative motion determination engine configured to determine a camera motion and factor said camera motion out to identify salient objects that move differently from said camera motion.

24. The apparatus according to claim 16 wherein said motion calculation engine includes a region grouping engine configured to identify a salient object and control tracking of said salient object.

25. The apparatus according to claim 16 wherein said motion calculation engine includes a user input device for receiving user input designating a salient object of interest.