Tracking objects between images

• US 9,691,158 B1
• Filed: 11/08/2013
• Issued: 06/27/2017
• Est. Priority Date: 05/23/2011
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Feldman, Bryan E., Ramkumar, Gurumurthy D., Senthamil, Nalin Pradeep, Dhua, Arnab Sanat Kumar
• Primary Examiner(s): Bhatnagar, Anand
• Application Number:
  US14/076,053
• Time in Patent Office: 1,327 Days
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• 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/248 involving reference images or patches
• CPC Class Codes: G06T 7/254 involving subtraction of images

Abstract

Systems and methods track one or more points between images. A point for tracking may be selected, at least in part, on a determination of how discriminable the point is relative to other points in a region containing the point. A point of an image being tracked may be located in another image by matching a patch containing the point with another patch of the other image. A search for a matching patch may be focused in a region that is determined based at least in part on an estimate of movement of the point between images. Points may be tracked across multiple images. If an ability to track one or more points is lost, information about the points being tracked may be used to relocate the points in another image.

Claims

1. A computing device comprising:

a camera;

one or more processors;

a memory device including instructions that, when executed by the one or more processors, cause the computing device to;

acquire a first image and a second image by the camera;

identify a first point in the first image;

determine a first patch in the first image using a feature detector, the first patch including the first point and being associated with a first feature descriptor;

identify a set of candidate points in the second image;

determine a set of patches in the second image using the feature detector, each patch of the set of patches including a respective candidate point from the set of candidate points, each patch of the set of patches being associated with a respective feature descriptor;

determine a candidate point from the set of candidate points that corresponds to the first point in the first image, the determined candidate point being determined based at least in part on a second feature descriptor associated with a second patch of the candidate point matching the first feature descriptor associated with the first point above a predetermined matching threshold;

determine that the candidate point and the first point satisfy at least one geometric constraint; and

generate a confirmation indicating at least that the candidate point and the first point satisfy at least one geometric constraint.

2. The computing device of claim 1, wherein the instructions when executed further cause the computing device to:

determine a tracking score based on a proximity of the feature descriptor associated with the patch including the first point and the feature descriptor associated with the patch including the determined candidate point;

determine that the tracking score is below a threshold; and

in response to determining the tracking score is below the threshold, generate a notification indicating an inability to track the first point between the first image and the second image.

3. The computing device of claim 1, wherein the feature descriptor is determined using one of a scale-invariant feature transform (SIFT) feature descriptor, a speeded up robust features descriptor (SURF), or a vector that describes one or more invariant features.

4. The computing device of claim 1, wherein determining the candidate point is based at least in part on a proximity of the feature descriptor associated with in the patch that includes the determined candidate point and the feature descriptor associated with the patch that includes the first point.

5. The computing device of claim 1, wherein the instructions when executed to identity the first point further cause the computing device to:

identify at least one of an edge, a corner, a blob, or a ridge, and

associate the at least one of the edge, the corner, the blob, or the ridge with the first point.

6. A computer-implemented method, comprising:

receiving a first image and a second image;

identifying a first point in the first image;

determining a first patch in the first image using a feature detector, the first patch including the first point and being associated with a first feature descriptor;

identifying a set of candidate points in the second image;

determining a set of patches in the second image using the feature detector, each patch of the set of patches including a respective candidate point from the set of candidate points, each patch of the set of patches being associated with a respective feature descriptor; and

determining a candidate point from the set of candidate points that corresponds to the first point in the first image, the determined candidate point being determined based at least in part on a second feature descriptor associated with a second patch of the candidate point matching the first feature descriptor associated with the first point above a predetermined matching threshold.

7. The computer-implemented method of claim 6, further comprising:

determining a tracking score based on a proximity of the feature descriptor associated with the patch including the first point and the feature descriptor associated with the patch including the determined candidate point;

determining that the tracking score is below a threshold; and

in response to determining that the tracking score is below a threshold, generating a notification indicating an inability to track the first point between the first image and the second image.

8. The computer-implemented method of claim 6, wherein the feature descriptor is determined using one of a scale-invariant feature transform (SIFT) feature descriptor, a speeded up robust features descriptor (SURF), or a vector that describes one or more invariant features.

9. The computer-implemented method of claim 6, wherein the determined candidate point is based at least in part on a proximity of the feature descriptor associated with the patch that includes the determined candidate point and the feature descriptor associated with the patch that includes the first point.

10. The computer-implemented method of claim 6, further comprising:

determining that the candidate point and the first point satisfy at least one geometric constraint; and

generating a confirmation indicating at least that the candidate point and the first point satisfy at least one geometric constraint.

11. The computer-implemented method of claim 6, further comprising:

determining that an object appears in the first image;

determining that the object does not appear in the second image; and

initiating at least one object tracking process in response to determining that the object does not appear in the second image.

12. The computer-implemented method of claim 6, wherein determining the candidate point further includes:

determining that a relative position of the candidate point is located within a predetermined radius of a position of the first patch.

13. A non-transitory computer readable storage medium storing instructions, the instructions when executed by a processor causing the processor to:

acquire a first image and a second image, the second image being acquired after the first image;

identify a first point in the first image;

determine a first patch in the first image using a first feature detector, the first patch including the first point and being associated with a first feature descriptor;

identify a set of candidate points in the second image;

determine a set of patches in the second image using a second feature detector, each patch in the set of patches being associated with a feature descriptor, each patch of the set of patches including a representative candidate point from the set of candidate points, each patch of the set of patches being associated with a respective feature descriptor; and

determine a candidate point from the set of candidate points that corresponds to the first point in the first image, the determined candidate point being determined based at least in part on a second feature descriptor associated with a second patch of the candidate point matching the first feature descriptor associated with the first point above a predetermined threshold.

14. The non-transitory computer readable storage medium of claim 13, wherein the instructions further cause the processor to:

determine a tracking score based on a proximity of the feature descriptor associated with the patch including the first point and the feature descriptor associated with the patch including the determined candidate point;

determine that the tracking score is below a threshold; and

in response to determining the tracking score is below the threshold, generate a notification indicating an inability to track the first point between the first image and the second image.

15. The non-transitory computer readable storage medium of claim 13, wherein the feature descriptor is determined using one of a scale-invariant feature transform (SIFT) feature descriptor, a speeded up robust features descriptor (SURF), or a vector that describes one or more invariant features.

16. The non-transitory computer-readable storage medium of claim 13, wherein the determined candidate point is determined based at least in part on a proximity of the feature descriptor associated with the patch that includes the determined candidate point and the feature descriptor associated with the patch that includes the first point.

17. The non-transitory computer readable storage medium of claim 13, wherein the instructions further cause the processor to:

determine that the candidate point and the first point satisfy at least one geometric constraint; and

generate a confirmation, indicating at least that the candidate point and the first point satisfy at least one geometric constraint.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further cause the processor to:

determine that an object in the first image did not appear in an image appearing subsequent to the first image and prior to the second image, wherein the images are displayed in a predetermined order.

19. The non-transitory computer-readable storage medium of claim 13, wherein the determined candidate point is determined in response to the feature descriptor associated with the second patch that includes the determined candidate point being within a predetermined radius of the feature descriptor associated with the patch that includes the first point.

20. The non-transitory computer-readable storage medium of claim 13, wherein the first feature detector is a same type of feature detector as the second feature detector.