Method and apparatus for tracking a movable object

• US 20060204035A1
• Filed: 12/05/2005
• Published: 09/14/2006
• 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
• Granted Patent: US 7,929,728 B2
• Time in Patent Office: Days
• 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 first and second images, the method comprising:

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

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

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

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

classifying the at least one second feature in accordance with its 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 feature;

correlating the at least one first and the at least one second features as a function of the first and second descriptors; and

comparing at least one portion of the first image with at least one portion of the second image.

2. The method of claim 1, wherein comparing at least one portion of the first image with at least one portion of the second image provides any of (i) a positive indication of a match between the first and second objects captured by the first and second images, respectively, and (ii) a negative indication of a match between the first and second objects captured by the first and second images, respectively.

3. The method of claim 1, further masking the first and second images to produce first and 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.

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

5. The method of claim 1, further comprising:

defining the first and second headings.

6. The method of claim 5, 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.

7. 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:

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

8. The method of claim 7, wherein matching a first patch of the first image to a local distribution of second patches comprises:

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.

9. The method of claim 8, wherein matching a first patch of the first image to a local distribution of second patches comprises:

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

maintaining the second patches as a match when the single score exceed a dynamic threshold.

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

performing flexible template matching.

11. The method of claim 1, further comprising:

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

12. 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.

13. The method of claim 11, 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;

rejecting at least one outlier of the plurality of first line segments;

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;

rejecting at least one outlier of the plurality of second line segments;

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

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.

14. The method of claim 10, 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.

15. 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.

16. The method of claim 1, further comprising:

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

17. 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 first and second images, the apparatus comprising:

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

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

means for assigning a first descriptor to the at least one first feature,

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

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

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

means correlating the at least one first and the at least one second features as a function of the first and second descriptors; and

means for comparing at least one portion of the first image with at least one portion of the second image.

18. The apparatus of claim 17, further comprising a means for comparing at least one portion of the first image with at least one portion of the second image so as to provide any of (i) a positive indication of a match between the first and second objects captured by the first and second images, respectively, and (ii) a negative indication of a match between the first and second objects captured by the first and second images, respectively.

19. The apparatus of claim 17, further comprising means 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.

20. The apparatus of claim 17, further comprising:

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

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

means for aggregating the second scores to form an aggregate score;

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

means for maintaining the second patches as a match when the single score exceed a dynamic threshold.