Method for tracking a video object in a time-ordered sequence of image frames

• US 6,724,915 B1
• Filed: 03/13/1998
• Issued: 04/20/2004
• Est. Priority Date: 03/13/1998
• Status: Expired due to Term

• Current Assignee: Siemens AG
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Toklu, Candemir, Liou, Shih-Ping
• Primary Examiner(s): Patel, Jayanti K.
• Application Number:
  US09/039,007
• Time in Patent Office: 2,230 Days
• Field of Search: 382/162, 382/168, 382/172, 382/174, 382/181, 382/199, 382/203, 382/209, 382/218, 382/232, 382/236, 382/238, 382/242, 382/291, 382/300, 382/103, 382/107, 348/169, 348/218, 348/407.1, 348/411.1, 348/412--42, 348/699, 348/703
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/248 involving reference images or patches

Abstract

A method for tracking a video object in a time-ordered sequence of image frames, comprises the steps of (a) identifying the object to be tracked in a first frame and determining its shape in the first frame; (b) selecting another frame, referred to as the last frame and identifying the shape of the object in the last frame; (c) selecting a number of intermediate frames between the first and last frames; (d) automatically identifying the shape of the object in the intermediate frames; and (e) interpolating between all of the frames in the sequence so as to determine the trajectory of the object in all of the frames.

Claims

1. A method for tracking a video object in a time-ordered sequence of image frames, comprising the steps of:

(a) identifying an object to be tracked in said time-ordered sequence of frames;

(b) selecting starting and ending frames for said object;

(c) marking a boundary of said object in said starting and ending frames;

(d) defining and determining a shape, a marker, and a location for said object;

(e) computing a model histogram for said object from colors associated with said object within said boundary;

(f) tracking said object'"'"'s shape, marker and location in a subset of frames in between said starting and ending frames;

(g) using linear interpolation to find a corresponding marker and location for said object for frames in between the starting and ending frames and in which said object is not tracked;

wherein the step (f) comprises;

selecting frames in which said object is to be tracked;

selecting two reference frames for a frame being processed from frames already processed based on their distances in time to said frame being processed and their confidence to said frame being processed;

making a first predication of the location and marker of said object and a confidence level of tracking in said frame being processed from those for said reference frames;

selecting from templates for said reference frames a references template for pattern matching;

identifying a second prediction of the location and marker of said object by back-projecting said model histogram into said current frame and fusing said two marker and frame predictions based on spatial relations to find a search space to look for said object in said frame being processed;

identifying the marker of the object in the frame being processed by matching said reference template to colors in said frame being processed;

updating the confidence level of the tracking in the frame being processed; and

finding the shape and location of the object in the frame being processed using histogram back-projection.

2. A method for tracking a video object as recited in claim 1, where step (b) comprises:

computing the index of a frame to be processed next based on the strategy;

forward, backward, or bi-directional, and a current time step size;

finding the two closest frames in time among the processed ones, which can be both in the same direction—

forward or backward direction—

or in different directions, whose confidence levels of tracking are above a predetermined threshold; and

updating said time step size if bi-directional tracking strategy has been selected.

3. A method for tracking a video object in a time-ordered sequence of image frames, comprising the steps of:

(a) identifying said object to be tracked in a first frame determining its shape in said first frame and obtaining a color histogram for said video object;

(b) selecting another frame, referred to as the last frame and identifying the shape of the said object in said last frame;

(c) identifying a predetermined location and marker for said object so as to determine its trajectory and global motion in frames between the first and last frames and forming respective templates and respective boundaries for said object as defined in said last and first frames;

(d) finding said location, marker and shape for said object, in a subset of frames in between said first and last frames;

(e) determining, in every frame, said location, marker and shape for said object from said location, marker and shape in said subset of frames using linear interpolation in time;

wherein step (d) comprises;

(f) making a first prediction of marker and object location in a frame being processed from those for neighboring previously processed frames;

(g) making a second prediction of marker and object location in said frame being processed based on histogram back-projection;

(h) fusing said first and second predictions for marker and object location in said frame being processed to find a search space for template matching;

(i) matching templates for finding marker and object location of said object in said frame being processed; and

(j) identifying the boundary of said object in said frame being processed.

4. A method for tracking an object in a time-ordered sequence of image frames, comprising the steps of:

acquiring a boundary of said object in last and first frames of said sequence;

forming respective templates for said object as defined in said last and first frames;

computing a model color histogram from said respective templates;

selecting a current frame from said sequence for processing next;

selecting two reference frames;

determining whether said current frame is equal to one of said last and first frames and the current time step size;

if so, utilizing said object'"'"'s location and shape marker in said current frame to make a first prediction of said object'"'"'s location and shape in said two reference frames and to set a confidence level based on matching of said templates;

selecting from said reference frames a reference template for matching;

deriving a second prediction of location by histogram back-projection;

utilizing two location and shape predictions from said first and second predictions and said confidence level, set a search window;

applying matching between said templates so as to identify a shape marker for said object in said current frame;

updating said confidence level in said current frame based on results of said matching between said templates;

updating the location and shape in said current frame; and

interpolating the current marker location of said object in any unprocessed frame in said sequence from the two marker locations in the two neighboring in time processed frames.