Method and apparatus for tracking multiple objects in a video sequence

• US 6,879,705 B1
• Filed: 07/14/2000
• Issued: 04/12/2005
• Est. Priority Date: 07/14/1999
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Tao, Hai, Sawhney, Harpreet Singh, Kumar, Rakesh
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): NAKHJAVAN, SHERVIN K
• Application Number:
  US09/615,971
• Time in Patent Office: 1,733 Days
• Field of Search: 382/103, 382/160, 382/190, 382/206, 348/135, 348/169, 348/208.14, 342/76, 342/96, 342/99, 342/101, 342/197, 342/337.07, 340/539.13, 345/621, 345/625, 345/630, 345/632, 700/29, 700/31
• US Class Current: 382/103
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

A method and apparatus for tracking multiple objects in a video sequence. The method defines a group of objects as a configuration, selects a configuration for a current video frame, predicts a configuration using a two-level process and computes the likelihood of the configuration. Using this method in an iterative manner on a sequence of frames, tracks the object group through the sequence.

Claims

1. A method for tracking multiple objects in a video sequence comprising:

selecting an initial configuration comprising a plurality of objects, where the initial configuration represents an initial relationship among the objects in said plurality of objects;

predicting a current configuration, where the current configuration represents a current relationship among the objects in said plurality of objects; and

computing a likelihood for the current configuration.

2. The method of claim 1 wherein said predicting step comprises performing an object level prediction.

3. The method of claim 1 wherein said predicting step comprises performing a configuration level prediction.

4. The method of claim 3 wherein said configuration level prediction handles object addition and deletion from a current configuration.

5. The method of claim 1 wherein the predicting step comprises:

determining a percentage of the objects that are covered by the current configuration;

determining a number of current configurations that correspond to the objects; and

maximizing said percentage and minimizing said number to identify an optimal current configuration.

6. The method of claim 5 wherein said percentage determining step comprises solving:

$\mathrm{\gamma <br><br>}=\frac{<br><br>A\bigcap <br><br>\left(\stackrel{m}{\underset{i=1}{\bigcup <br><br>}}<br><br>B_i\right)+b<br><br>}{<br><br>A<br><br>+b}.$

7. The method of claim 5 wherein said percentage determining step comprises solving:

$\mathrm{\xi <br><br>}=\frac{<br><br>A\bigcap <br><br>\left(\stackrel{m}{\underset{i=1}{\bigcup <br><br>}}<br><br>B_i\right)+c<br><br>}{\left(<br><br>\stackrel{m}{\underset{i=1}{\bigcup <br><br>}}<br><br>B_i<br><br>+a\right)}.$

8. The method of claim 1 wherein multiple objects in a video sequence are represented by said configuration comprising a plurality of modeled objects.

9. A method of producing probability distributions of states for multiple objects in a video sequence comprising:

performing hierarchical sampling of at least one frame of video in said video sequence, wherein said sampling is performed in an object configuration and individual object states, said objected configuration representing a relationship among plurality of object within a scene; and

repeating said sampling for each frame of video in said video sequence to track objects within the video sequence.

10. A computer readable medium containing a program that when executed by a processor, causes an image processing system to perform a method comprising:

selecting an initial configuration comprising a plurality of objects, where the initial objects;

predicting a current configuration, where the current configuration represents a current relationship among the objects in said plurality of object; and

computing a likelihood for the current configuration.

11. The method of claim 10 wherein said predicting step comprises performing an object level prediction.

12. The method of claim 10 wherein said predicting step comprises performing a configuration level prediction.

13. The method of claim 12 wherein said configuration level prediction handles object addition and deletion from a current configuration.

14. The method of claim 10 wherein the predicting step comprises:

determining a percentage of the objects that are covered by the current configuration;

determining a number of current configurations that correspond to the objects;

maximizing said percentage and minimizing said number to identify an optimal current configuration.

15. The method of claim 14 wherein said percentage determining step comprises solving:

$\mathrm{\gamma <br><br>}=\frac{<br><br>A\bigcap <br><br>\left(\stackrel{m}{\underset{i=1}{\bigcup <br><br>}}<br><br>B_i\right)+b<br><br>}{<br><br>A<br><br>+b}.$

16. The method of claim 14 wherein said percentage determining step comprises solving:

$\mathrm{\xi <br><br>}=\frac{<br><br>A\bigcap <br><br>\left(\stackrel{m}{\underset{i=1}{\bigcup <br><br>}}<br><br>B_i\right)+c<br><br>}{\left(<br><br>\stackrel{m}{\underset{i=1}{\bigcup <br><br>}}<br><br>B_i<br><br>+a\right)}.$

17. The method of claim 10 when wherein multiple objects in a video sequence are ion comprising a plurality of modeled objects.