Bi-Directional Tracking Using Trajectory Segment Analysis

• US 20070086622A1
• Filed: 04/27/2006
• Published: 04/19/2007
• Est. Priority Date: 10/14/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sun, Jian, Shum, Heung-Yeung, Tang, Xiaoou, Zhang, Weiwei
• Granted Patent: US 7,817,822 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes

Abstract

The present video tracking technique outputs a Maximum A Posterior (MAP) solution for a target object based on two object templates obtained from a start and an end keyframe of a whole state sequence. The technique first minimizes the whole state space of the sequence by generating a sparse set of local two-dimensional modes in each frame of the sequence. The two-dimensional modes are converted into three-dimensional points within a three-dimensional volume. The three-dimensional points are clustered using a spectral clustering technique where each cluster corresponds to a possible trajectory segment of the target object. If there is occlusion in the sequence, occlusion segments are generated so that an optimal trajectory of the target object can be obtained.

Claims

1. At least one computer-readable media storing computer-executable instructions for performing a method, the method comprising:

determining two keyframes of a video sequence;

obtaining a first state for a target object within one of the two keyframes and a second state for the target object within the other keyframe; and

tracking the target object in the frames from the one keyframe to the other keyframe based on the first and second state.

2. The computer-readable media of claim 1, wherein the tracking of the target object comprises:

performing two-dimensional extraction on the frames to obtain a plurality of local two-dimensional (2D) modes for the target object;

performing three-dimensional trajectory segment extraction based on the sparse set of local 2D modes to obtain a plurality of three-dimensional trajectory segments for the target object;

performing occlusion analysis based on the plurality of trajectory segments to obtain at least one occlusion segment that connects two disjoint trajectory segments of the plurality of trajectory segments; and

performing trajectory optimization in a coarse to fine manner to obtain an optimal trajectory for the target object based on the trajectory segments and the occlusion segment.

3. The computer-readable media of claim 2, wherein performing the two-dimensional extraction comprises:

computing an evidence surface; and

applying a mean shift algorithm to compute a gradient direction of the computed evidence surface that results in the local 2D modes for the target object.

4. The computer-readable media of claim 3, wherein three-dimensional trajectory segment extraction comprises:

converting the two-dimensional modes into three-dimensional points within a three-dimensional volume;

partitioning the three-dimensional points into clusters using a spectral clustering technique that uses K eigenvectors simultaneously for K-class clustering; and

obtaining the meaningful trajectory segments based on the clusters.

5. A computer-implemented method comprising:

designating a start and an end frame within a video sequence;

obtaining an initial state for a target object within the start frame and a final state for the target object within the end frame;

performing two-dimensional extraction on the frames starting with the start frame and ending with the end frame to obtain a sparse set of local two-dimensional modes for the target object in the frames based on the initial state and the final state; and

performing three-dimensional trajectory segment extraction based on the sparse set of local two-dimensional (2D) modes to obtain a plurality of three-dimensional trajectory segments for the target object.

6. The computer-implemented method of claim 5, wherein performing the two-dimensional extraction comprises:

computing an evidence surface; and

applying a mean shift algorithm to compute a gradient direction of the computed evidence surface that results in the local 2D modes for the target object.

7. The computer-implemented method of claim 6, further comprising pre-filtering the frames using a color histogram of the target object before applying the mean shift algorithm.

8. The computer-implemented method of claim 6, further comprising determining a plurality of starting position by uniformly sampling locations in the frame and running the mean shift algorithm independently from each starting position.

9. The computer-implemented method of claim 8, wherein uniformly sampling comprises setting a spatial sampling interval to be slightly smaller than half the size of the target object.

10. The computer-implemented method of claim 6, further comprising rejecting one of the local 2D modes if the corresponding evidence is less than a pre-determined value.

11. The computer-implemented method of claim 6, further comprising merging local 2D modes into one local 2D mode when the two local 2D modes are within a certain distance of each other.

12. The computer-implemented method of claim 5, wherein performing three-dimensional trajectory segment extraction comprises:

converting the two-dimensional modes into three-dimensional points within a three-dimensional volume;

partitioning the three-dimensional points into clusters using a spectral clustering technique that uses K eigenvectors simultaneously for K-class clustering; and

obtaining the meaningful trajectory segments based on the clusters.

13. The computer-implemented method of claim 12, further comprising performing occlusion analysis based on the plurality of trajectory segments to obtain at least one occlusion trajectory segment that connects two disjoint trajectory segments of the plurality of trajectory segments.

14. The computer-implemented method of claim 13, wherein performing occlusion analysis comprises:

a) building a tree with an empty root node for the tree;

b) adding one trajectory containing an object template in the key frame to the tree as an active node;

c) adding remaining trajectories to a candidate list;

d) excluding trajectories in the candidate list based on whether the trajectories are parallel to the trajectory that corresponds to the active node;

e) while there is an active node in the tree, selecting one of the trajectories from the candidate list as a current active node;

f) determining at least one Q-best occlusion segment;

g) adding the at least one Q-best occlusion segment to the candidate list if the Q-best segment does not reach a desired trajectory segment; and

h) repeating e-g until the Q-best segment reaches the desired trajectory segment; and

i) connecting the trajectories and the Q-best occlusion segment to make a complete trajectory for the target object.

15. The computer-implemented method of claim 13, further comprising performing trajectory optimization in a coarse to fine manner to obtain an optimal trajectory for the target object based on the meaningful trajectory segments and the occlusion trajectory segment.

16. The computer-implemented method of claim 15, wherein performing the trajectory optimization in the coarse manner comprises spatially down-sampling the frames and uniformly sampling the positions around the trajectory segments in each frame using three discrete scaling factors to obtain the optimal trajectory.

17. The computer-implemented method of claim 5, wherein performing the trajectory optimization in the fine manner comprises uniformly sampling the positions around the optimal trajectory using five discrete levels of scaling factors in each frame to obtain a final optimal trajectory.

18. A computing device, comprising:

a processor;

a memory into which a plurality of instructions are loaded, the plurality of instructions performing a method for tracking a target object within a video sequence when executed by the processor, the video sequence being decomposed into several short sequences, the shorter sequences having a start frame and an end frame, the method comprising;

a) generating a set of local two-dimensional modes for each frame of one short sequence, each local 2D mode identifying a location within the frame that has visual statistics similar to the target object identified in the start frame;

b) obtaining a plurality of three-dimensional trajectory segments for the target object based on the set of local two-dimensional modes;

c) obtaining at least one occlusion segment that connects two disjointed trajectory segments of the plurality of three-dimensional trajectory segments; and

d) determining an optimal trajectory based on the plurality of three-dimensional trajectory segments and the at least one occlusion segment.

19. The system of claim 18, wherein obtaining the plurality of three-dimensional trajectory segments comprises converting the set of local two-dimensional modes into three-dimensional points in a three-dimensional volume, partitioning the three-dimensional points into clusters using spectral clustering, and obtaining the three-dimensional trajectory segments based on the clusters.

20. The system of claim 19, wherein obtaining the at least one occlusion segment comprises performing a bi-directional tree-growing process.