Tracking objects between images

• US 10,032,286 B2
• Filed: 10/18/2017
• Issued: 07/24/2018
• 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
• Application Number:
  US15/787,545
• Publication Number:
  US 20180040134A1
• Time in Patent Office: 279 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;

receive first image data captured using the camera;

select a first tracking point within an area of the first image data;

compare a first patch of pixels surrounding the first tracking point within the area with a second patch of pixels within the area to determine a similarity score;

determine a distinctiveness of the first tracking point based at least in part the similarity score;

receive second image data captured using the camera; and

determine a second tracking point in the second image data corresponding to the first tracking point.

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

determine respective measures of similarity between the first patch of pixels and a plurality of other patches of pixels within the area; and

determine the distinctiveness of the first tracking point based at least in part on the measures of similarity.

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

compare the first patch with a plurality of patches of the second image data within a search window.

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

determine a matching patch in the plurality of patches based at least in part on a measure of similarity between the first patch and the matching patch.

5. The computing device of claim 3, wherein the area is the same size as the search window.

6. The computing device of claim 3, further comprising:

a motion-based sensor providing data, the data used to estimate a location of the search window in the second image data.

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

compare the first patch with patches of the second image data within a search window until a matching patch is determined, the first patch and the matching patch having a measure of similarity meeting or exceeding a threshold.

8. The computing device of claim 1, wherein the first tracking point is associated with a representation of an object in the first image data, and wherein the instructions, when executed, further cause the computing device to:

detect an absence of points in the second image data corresponding to the first tracking point; and

indicate that at least a portion of the representation of the object is not in the second image data.

9. A computer-implemented method, comprising:

receiving image data;

determining a plurality of candidate points based on the image data;

determining respective distinctiveness for the plurality of candidate points by comparing a patch of pixels surrounding a candidate point with other patches of pixels within a window containing the candidate point;

determining a spatial distribution of the plurality of candidate points;

selecting a tracking point from the plurality of candidate points based at least in part on the respective distinctiveness scores and the spatial distribution; and

identifying points corresponding to the tracking point in a plurality of frames of the image data.

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

comparing a patch of pixels surrounding the tracking point with an array patches within a search window of a subsequent frame of the plurality of frames; and

determine a matching patch in the array of patches based at least in part on a measure of similarity between the patch of pixels surrounding the tracking point and the matching patch.

11. The computer-implemented method of claim 10, wherein the window containing the tracking point is the same size as the search window.

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

comparing a patch of pixels surrounding the tracking point in a first frame of the plurality of frames to a patch of pixels surrounding a corresponding point in a second frame of the plurality of frames, wherein the second frame is subsequent to the first frame in a sequence; and

determining a tracking score based on the comparison.

13. The computer-implemented method of claim 12, further comprising:

determining that the tracking score is below a threshold; and

selecting a new tracking point.

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

selecting the new tracking point based on the distinctiveness and a spatial position of the new tracking point.

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

receive image data;

determine a plurality of candidate points based on the image data;

determine respective distinctiveness scores for the plurality of candidate points by comparing a patch of pixels surrounding a candidate point with other patches of pixels within a window containing the candidate point;

determine a spatial distribution of the plurality of candidate points;

select a tracking point from the plurality of candidate points based at least in part on the respective distinctiveness scores and the spatial distribution; and

identify points corresponding to the tracking point in a plurality of frames of the image data.

16. The non-transitory computer readable storage medium of claim 15, the instructions when executed by a processor further causing the processor to:

compare a patch of pixels surrounding the tracking point with an array patches within a search window of a subsequent frame of the plurality of frames; and

determine a matching patch in the array of patches based at least in part on a measure of similarity between the patch of pixels surrounding the tracking point and the matching patch.

17. The non-transitory computer-readable storage medium of claim 16, wherein the window containing the tracking point is the same size as the search window.

18. The non-transitory computer readable storage medium of claim 15, the instructions when executed by a processor further causing the processor to:

compare a patch of pixels surrounding the tracking point in a first frame of the plurality of frames to a patch of pixels surrounding a corresponding point in a second frame of the plurality of frames, wherein the second frame is subsequent to the first frame in a sequence; and

determine a tracking score based on the comparison.

19. The non-transitory computer-readable storage medium of claim 18, the instructions when executed by a processor further causing the processor to:

determine that the tracking score is below a threshold; and

select a new tracking point.

20. The non-transitory computer-readable storage medium of claim 19, the instructions when executed by a processor further causing the processor to:

select the new tracking point based on the distinctiveness and a spatial position of the new tracking point.