Apparatus and method for identifying and tracking objects with view-based representations

• US 6,526,156 B1
• Filed: 09/03/1997
• Issued: 02/25/2003
• Est. Priority Date: 01/10/1997
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Black, Michael J., Jepson, Allan D.
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US08/923,436
• Time in Patent Office: 2,001 Days
• Field of Search: 382/103, 382/107, 382/115, 382/118, 382/228, 382/276, 382/294
• US Class Current: 382/103
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/251 involving models
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 10/76 based on eigen-space representations, e.g. from pose or different illumination conditions; Shape manifolds

Abstract

A system tracks and identifies view-based representations of an object through a sequence of images. As the view of the object changes due to its motion or the motion of its recording device, the object is identified by matching an image region containing the object with a set of basis images represented by an eigenspace. The eigenspace is generated from a training set of images which records different views of the object. The system identifies the object in the image region by simultaneously computing a transformation that aligns the image region with the eigenspace, and computing coefficients of a combination of linear eigenvectors that reconstruct the image region. This identification and tracking system operates when views of the object in the image are deformed under some transformation with respect to the eigenspace. Matching between the image region and the eigenspace is performed using a robust regression formulation that uses a coarse to fine strategy with incremental refinement. As the incremental refinement registers the image region with the eigenspace, the identification of a match between the object in an image region and the eigenspace improves. The transformation that warps the image region of a current image frame into alignment with the eigenspace is then used to track the object in a subsequent image frame.

Claims

1. An apparatus for identifying and tracking an object recorded in a sequence of images, comprising:

a memory for recording a set of training images;

the images in the set of training images recording different views of the object;

means for generating a set of basis images corresponding to the set of training images recorded in said memory;

the set of basis images characterizing variations of the views of the object in the set of training images; and

means for evaluating each image in the sequence of images to identify changes in view and structure of the object while tracking the object through the sequence of images with tracking parameters and identification coefficients;

said evaluating means incrementally refining the tracking parameters and the identification coefficients by aligning, matching, and reconstructing a view of the object in the image with the views of the object represented in the set of basis images.

2. The apparatus according to claim 1, wherein said evaluating means comprises:

means for computing a warped image by applying a transformation to a first image in the sequence of images;

means for matching the set of basis images with the warped image;

said matching means providing the identification coefficients that define which basis images in the set of basis images characterize the view of the object in the warped image;

means for generating a first reconstructed image using a combination of images in the set of basis images defined by the identification coefficients provided by said matching means;

means for estimating the tracking parameters that identify motion of the object between the warped image and the first reconstructed image; and

means for refining the transformation with the tracking parameters estimated by said motion estimation means.

3. The apparatus according to claim 2, further comprising means for updating the identification coefficients, said updating means computing a second warped image with said applying means using the refined transformation.

4. The apparatus according to claim 2, wherein said computing means uses the transformation to provide an estimated location of the object in a second image in the sequence of images;

said computing means providing the estimated location to track the object between the first image and the second image.

5. The apparatus according to claim 2, further comprising:

means for generating a multi-scale set of images and a multi-scale set of basis images; and

means for evaluating the multi-scale set of images and the multi-scale set of basis images from a coarse resolution to a fine resolution, said evaluating means refining the transformation with said refining means at each resolution.

6. The apparatus according to claim 2, wherein the identification coefficients provided by said matching means provides an estimate of the view of the object in a second image in the image sequence.

7. The apparatus according to claim 1, wherein the view of the object in the image in the sequence of images is different from the views of the object in the training set of images.

8. The apparatus according to claim 1, wherein the object in the training set of images has a common orientation and scale.

9. The apparatus according to claim 1, wherein the set of basis images is an eigenspace.

10. A method for identifying and tracking an object recorded in a sequence of images, comprising the steps of:

recording in a memory a set of training images;

the images in the set of training images recording different views of the object;

generating a set of basis images corresponding to the set of training images recorded by said recording step;

the set of basis images characterizing variations of the different views of the object in the set of training images; and

evaluating each image in the sequence of images to identify changes in view and structure of the object while tracking the object through the sequence of images with tracking parameters and identification coefficients;

said evaluating step incrementally refining the tracking parameters and the identification coefficients by aligning, matching, and reconstructing a view of the object in the image with the views of the object represented in the set of basis images.

11. The method according to claim 10, wherein said evaluating step further comprises the step of computing a transformation that aligns the view of the object in a first image in the sequence of images with a view of the object in the set of basis images.

12. The method according to claim 11, wherein said evaluating step tracks the object in a second image in the sequence of images with the transformation.

13. The method according to claim 10, wherein said evaluating step further comprises the step of computing the identification coefficients that define which basis images in the set of basis images best approximate each image in the sequence of images.

14. The method according to claim 10, further comprising the steps of:

formulating a first reconstructed image that recovers features of the object in the image; and

generating an outlier image that identifies points in the image that are excluded in the first reconstructed image.

15. The method according to claim 14, further comprising the step of generating a second reconstructed image by matching the outlier image with the set of basis images;

the second reconstructed image recovering portions of the image that are omitted from the first reconstructed image.

16. The method according to claim 10, wherein said evaluating step comprises the step of minimizing the following objective function:

$E<br><br>\left(c,a\right)=\underset{x}{\sum <br><br>}<br><br>\mathrm{\rho <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(I<br><br>\left(x+u<br><br>\left(x,a\right)\right)-\left[U<br><br>\text{\hspace{1em}<br><br>}<br><br>c\right]<br><br>\left(x\right),\mathrm{\sigma <br><br>}\right),$

where,

ρ

=an error norm;

σ

=a scale parameter;

I=an image in the sequence of images;

x=position [x,y] in the image I;

u(x,a)=a transformation;

a=tracking parameters of the transformation;

U=the set of basis images; and

c=identification coefficients of the set of basis images U.

17. The method according to claim 10, wherein said evaluating step comprises the steps of:

applying a transformation to the image in the sequence of images;

said applying step computing a warped image;

matching the set of basis images with the warped image;

said matching step providing the identification coefficients that define which basis images in the set of basis images characterize the view of the object in the warped image;

generating a reconstructed image using a combination of images in the set of basis images defined by the identification coefficients provided by said matching step;

estimating the tracking parameters that identify motion of the object between the warped image and the reconstructed image; and

refining the transformation with the tracking parameters estimated by said motion estimation step.

18. The method according to claim 17, further comprising the steps of:

generating a multi-scale set of images and a multi-scale set of basis images; and

calculating the multi-scale set of images and the multi-scale set of basis images from a coarse resolution to a fine resolution, said evaluating step refining the transformation with said refining step at each resolution.

19. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for identifying and tracking an object recorded in a sequence of images, said method steps comprising:

recording in a memory a set of training images;

the images in the set of training images recording different views of the object;

generating a set of basis images corresponding to the set of training images recorded by said recording step;

the set of basis images characterizing variations of the different views of the object in the set of training images; and

evaluating each image in the sequence of images to identify changes in view and structure of the object while tracking the object through the sequence of images with tracking parameters and identification coefficients;

said evaluating step incrementally refining the tracking parameters and the identification coefficients by aligning, matching, and reconstructing a view of the object in the image with the views of the object represented in the set of basis images.

20. The program storage device as recited in claim 19, wherein said method evaluating step further comprise the steps of:

applying a transformation to the image in the sequence of images;

said applying step computing a warped image;

matching the set of basis images with the warped image;

said matching step providing the identification coefficients that define which basis images in the set of basis images characterize the view of the object in the warped image;

generating a reconstructed image using a combination of images in the set of basis images defined by the identification coefficients provided by said matching step;

estimating the tracking parameters that identify motion of the object between the warped image and the reconstructed image; and

refining the transformation with the tracking parameters estimated by said motion estimation step.