Tracking objects between images

Patent metadata

Field	Value
Publication number	US-9824459-B2
Application number	US-201715606247-A
Country	US
Kind code	B2
Filing date	May 26, 2017
Priority date	May 23, 2011
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

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.

First claim

What is claimed is:

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 o

Assignees

• A9 Com Inc

Inventors

• Feldman Bryan E
• Senthamil Nalin Pradeep
• Dhua Arnab Sanat Kumar
• Ramkumar Gurumurthy D

Classifications

• G06T7/254

  involving subtraction of images · CPC title

• G06T7/248 Primary

  involving reference images or patches · CPC title

• G06T7/20 Primary

  Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51) · CPC title

• G06T2207/10016

  Video; Image sequence · CPC title