Tracking objects between images

• US 9,824,459 B2
• Filed: 05/26/2017
• Issued: 11/21/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., Senthamil, Nalin Pradeep, Dhua, Arnab Sanat Kumar, Ramkumar, Gurumurthy D.
• Primary Examiner(s): BHATNAGAR, ANAND P
• Application Number:
  US15/606,247
• Publication Number:
  US 20170263003A1
• Time in Patent Office: 179 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 an image by the camera;

identify a plurality of image points of the image;

determine a feature score for individual image points of the plurality of image points using a feature detector, the feature score representing a degree of distinctiveness of an image point;

select a plurality of candidate points from the plurality of image points based at least in part on the feature score for the individual image points;

determine a patch score for individual candidate points of the plurality of candidate points, the patch score representing a degree of similarity between a first patch of the image and a second patch of the image, the first patch surrounding a candidate point of the plurality of candidate points;

determine a spatial distribution of the plurality of candidate points; and

select a tracking point from the plurality of candidate points based at least in part on the patch scores of the individual candidate points and the spatial distribution.

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

identify a search window around the candidate point, the first and second patches of the image being within the search window; and

compare the first patch to one or more other patches of the image within the search window including the second patch to determine the patch score.

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

determine a match score between the first patch and individual patches of the one or more other patches, the match score representing a degree of similarity between the first patch and an individual patch of the one or more other patches; and

determine the patch score based at least in part on the match score representing a highest degree of similarity.

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

divide the image into a plurality of bins, wherein distribution of the plurality of candidate points amongst the bins represents the spatial distribution of the plurality of candidate points;

select, from a first bin, a first candidate point of the plurality of candidate points as a first tracking point; and

select, from a second bin, a second candidate point from the plurality of candidate points as a second tracking point.

5. The computing device of claim 4, wherein the first bin and second bin are separated by at least a threshold geometric distance or a relative geometric distance.

6. The computing device of claim 4, wherein the second bin is randomly selected from the plurality of bins.

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

acquire an additional image by the camera; and

identify at least one active tracking point in the additional image, the at least one active tracking point corresponding to the at least one tracking point selected from the image.

8. A computer-implemented method, comprising:

acquiring an image by a camera of a computing device;

identifying a plurality of image points of the image;

determining a feature score for individual image points of the plurality of image points using a feature detector, the feature score representing a degree of distinctiveness of an image point;

selecting a plurality of candidate points from the plurality of image points based at least in part on the feature score for the individual image points;

determining a patch score for individual candidate points of the plurality of candidate points, the patch score representing a degree of similarity between a first patch of the image and a second patch of the image, the first patch surrounding a candidate point of the plurality of candidate points;

determining a spatial distribution of the plurality of candidate points; and

selecting a tracking point from the plurality of candidate points based at least in part on the patch scores of the individual candidate points and the spatial distribution.

9. The computer-implemented method of claim 8, further comprising:

identifying a search window around the candidate point, the first and second patches of the image being within the search window; and

comparing the first patch to one or more other patches of the image within the search window including the second patch to determine the patch score.

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

determining a match score between the first patch and individual patches of the one or more other patches, the match score representing a degree of similarity between the first patch and an individual patch of the one or more other patches; and

determining the patch score based at least in part on the match score representing a highest degree of similarity.

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

dividing the image into a plurality of bins, wherein distribution of the plurality of candidate points amongst the bins represents the spatial distribution of the plurality of candidate points;

selecting, from a first bin, a first candidate point of the plurality of candidate points as a first tracking point; and

selecting, from a second bin, a second candidate point from the plurality of candidate points as a second tracking point.

12. The computer-implemented method of claim 11, wherein the first bin and second bin are separated by at least a threshold geometric distance or a relative geometric distance.

13. The computer-implemented method of claim 11, wherein the second bin is randomly selected from the plurality of bins.

14. The computer-implemented method of claim 8, further comprising:

acquiring an additional image by the camera; and

identifying at least one active tracking point in the additional image, the at least one active tracking point corresponding to the at least one tracking point selected from the image.

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

acquire an image by a camera of a computing device;

identify a plurality of image points of the image;

determine a feature score for individual image points of the plurality of image points using a feature detector, the feature score representing a degree of distinctiveness of an image point;

select a plurality of candidate points from the plurality of image points based at least in part on the feature score for the individual image points;

determine a patch score for individual candidate points of the plurality of candidate points, the patch score representing a degree of similarity between a first patch of the image and a second patch of the image, the first patch surrounding a candidate point of the plurality of candidate points;

determine a spatial distribution of the plurality of candidate points; and

select a tracking point from the plurality of candidate points based at least in part on the patch scores of the individual candidate points and the spatial distribution.

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

identify a search window around the candidate point, the first and second patches of the image being within the search window; and

compare the first patch to one or more other patches of the image within the search window including the second patch to determine the patch score.

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

determine a match score between the first patch and individual patches of the one or more other patches, the match score representing a degree of similarity between the first patch and an individual patch of the one or more other patches; and

determine the patch score based at least in part on the match score representing a highest degree of similarity.

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

divide the image into a plurality of bins, wherein distribution of the plurality of candidate points amongst the bins represents the spatial distribution of the plurality of candidate points;

select, from a first bin, a first candidate point of the plurality of candidate points as a first tracking point; and

select, from a second bin, a second candidate point from the plurality of candidate points as a second tracking point.

19. The non-transitory computer readable storage medium of claim 18, wherein the first bin and second bin are separated by at least a threshold geometric distance or a relative geometric distance.

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

acquire an additional image by the camera; and

identify at least one active tracking point in the additional image, the at least one active tracking point corresponding to the at least one tracking point selected from the image.