Method and apparatus for tracking a movable object

• US 7,929,728 B2
• Filed: 12/05/2005
• Issued: 04/19/2011
• Est. Priority Date: 12/03/2004
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Hsu, Steve, Kumar, Rakesh, Guo, Yanlin, Sawhney, Harpreet, Shan, Ying
• Primary Examiner(s): Le; Brian Q
• Assistant Examiner(s): NAKHJAVAN, SHERVIN K
• Application Number:
  US11/295,688
• Publication Number:
  US 20060204035A1
• Time in Patent Office: 1,961 Days
• Field of Search: 382/103, 382/159, 382/165, 382/199, 382/218, 382/224, 348/169
• 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
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 2201/08 Detecting or categorising vehicles

Abstract

A method and apparatus for tracking a movable object using a plurality of images, each of which is separated by an interval of time is disclosed. The plurality of images includes first and second images. The method and apparatus include elements for aligning the first and second images as a function of (i) at least one feature of a first movable object captured in the first image, and (ii) at least one feature of a second movable object captured in the second image; and after aligning the first and second images, comparing at least one portion of the first image with at least one portion of the second image.

Claims

1. A method for tracking an object using a plurality of images, each of which is separated by an interval of time, wherein the plurality of images comprises a first image and a second image, the method comprising:

detecting from the first image at least one first feature associated with a first movable object;

classifying the at least one first feature in accordance with its orientation to a first heading associated with the first movable object;

assigning a first descriptor to the at least one first feature;

detecting from the second image at least one second feature associated with a second movable object;

classifying the at least one second feature in accordance with its orientation to a second heading associated with the second object, wherein the first and second headings are in the same direction;

assigning a second descriptor to the at least one second feature;

correlating the at least one first feature and the at least one second feature as a function of the first and second descriptors to align the first image with the second image; and

matching a first patch of the first image to a local distribution of second patches comprising;

computing for the first patch a first score that is associated with a spatial arrangement of the first patch;

computing for the second patches respective second scores that are associated with respective spatial arrangements of the second patches;

aggregating the second scores to form an aggregate score;

forming a single score between the first patch and the aggregate score; and

discarding the second patches when the single score fails to exceed a dynamic threshold, otherwise

maintaining the second patches as a match.

2. The method of claim 1, further masking the first and second images image to produce first and a second masked images, respectively, wherein comparing at least one portion of the first image with at least one portion of the second image comprises:

comparing all of the first masked image with all of the second masked image.

3. The method of claim 1, wherein the first and second descriptors comprise respective first and second affine invariant line feature descriptors.

4. The method of claim 1, further comprising:

defining the first and second headings.

5. The method of claim 4, wherein defining the first and second headings comprises:

obtaining first metadata associated with the first image, wherein the first metadata comprises the first heading; and

obtaining second metadata associated with the second image, wherein the second metadata comprises the second heading.

6. The method of claim 1, wherein comparing at least one portion of the first image with at least one portion of the second image comprises:

performing flexible template matching.

7. The method of claim 6, wherein the quasi-rigid alignment uses a flow-field that is interpolated from a plurality of sparse correspondences between the at least one feature of the first movable object and the at least one feature of the second movable object.

8. The method of claim 1, further comprising:

performing initial motion estimation using metadata associated with the first image.

9. The method of claim 1, wherein the first and second images comprise at least one learning sequence of images and at least one query sequence of images, respectively, and wherein aligning the first and second images comprises:

performing a quasi-rigid alignment of the at least one learning sequence of images and the at least one query sequence of images.

10. The method of claim 9, wherein performing the quasi-rigid alignment comprises:

detecting from the first image a plurality of first line segments associated with the at least one feature of the first movable object;

classifying the plurality of first line segments in accordance with their orientation to a first heading associated with the first movable vehicle;

forming from the plurality of first line segments at least one first line;

assigning a first descriptor to the at least one first line;

detecting from the second image at plurality of second line segments associated with the at least one feature of the second movable object;

classifying the plurality of second line segments in accordance with their orientation to a second heading associated with the second movable vehicle, wherein the first and second headings are in the same direction;

assigning a second descriptor to the at least one second line; and

performing a warp of the first and second images as a function of the first and second descriptors.

11. The method of claim 1, wherein comparing at least one portion of the first image with at least one portion of the second image comprises computing at least one oriented energy band;

and computing at least one normalized correlation.

12. The method of claim 1, further comprising:

generating a constrained interpolated flow field as a function of the at least one first feature associated with the first movable object and the at least one second feature associated with the second movable object.

13. The method of claim 1, wherein the at least one first feature and the at least one second feature are edges.

14. The method of claim 13, wherein the first and second descriptors are first and second band images, respectively, formed by collecting samples around a band along detected edges in each of the first image and the second image.

15. The method of claim 14, wherein the samples indicate intensity/color transitions from one side to the other of a line segment belonging to an edge.

16. The method of claim 14, wherein the step of correlating the at least one first and the at least one second features as a function of the first and second descriptors to align the first image with the second image further comprises employing a normalized correlation between the first and second band images to establish line correspondences between the first image and the second image.

17. The method of claim 16, wherein the patch captures a spatial arrangement or edge energy and orientations within the patch.

18. The method of claim 1, wherein a patch is represented using at least one oriented energy filter output.

19. An apparatus for tracking an object using a plurality of images, each of which is separated by an interval of time, wherein the plurality of images comprises a first image and a second image, the apparatus comprising a computer processor configured for:

detecting from the first image at least one first feature associated with a first movable object;

classifying the at least one first feature in accordance with its orientation to a first heading associated with the first movable object;

assigning a first descriptor to the at least one first feature;

detecting from the second image at least one second feature associated with a second movable object;

classifying the at least one second feature in accordance with its orientation to a second heading associated with the second movable object, wherein the first and second headings are in the same direction;

assigning a second descriptor to the at least one second feature;

correlating the at least one first feature and the at least one second feature as a function of the first and second descriptors to align the first image with the second image; and

matching a first patch of the first image to a local distribution of second patches comprising;

computing for the first patch a first score that is associated with a spatial arrangement of the first patch;

computing for the second patches respective second scores that are associated with respective spatial arrangements of the second patches;

aggregating the second scores to form an aggregate score;

forming a single score between the first patch and the aggregate score; and

discarding the second patches when the single score fails to exceed a dynamic threshold, otherwise

maintaining the second patches as a match.

20. The apparatus of claim 19, wherein the computer processor is further configured for masking the first and second images to produce first and second masked images, respectively, wherein the means for comparing at least one portion of the first image with at least one portion of the second image comprises:

a means for comparing all of the first masked image with all of the second masked image.