Nonparametric imaging tracker

• US 4,868,871 A
• Filed: 08/13/1987
• Issued: 09/19/1989
• Est. Priority Date: 08/13/1987
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Watson, Thomas M. III
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Lobo, Ian J.
• Application Number:
  US07/085,053
• Time in Patent Office: 768 Days
• Field of Search: 382/1, 382/48, 358/126, 358/125, 358/105, 364/516
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: H04N 19/20 using video object coding

Abstract

A nonparametric imaging tracker is disclosed that first declares (10) a reference subimage comprising a plurality of image pixels, each pixel having a numerical light intensity level. The tracker then finds (12) a reference distribution of intensity levels in the reference subimage. A plurality of candidate subimages each having a plurality of pixels are then acquired (20). The intensity level distribution of each candidate subimage is compared to the reference distribution, and a statistic for each candidate subimage is computed based on this comparison (26, 28). One of the candidate subimages is then selected based on the value of its statistic (30, 36, 40). A preferred comparison and statistic calculation sequence includes the Kolmogorov-Smirnov test.

Claims

1. An imaging tracker, comprising:

means for declaring a reference subimage including a two-dimensional region of intensities within an image;

means for determining a reference distribution of intensities in said reference subimage;

means for acquiring a plurality of candidate subimages;

means for determining a candidate distribution of intensities for each of said candidate subimages;

means for comparing each said candidate distribution to said reference distribution;

means for computing a statistic for each candidate subimage, said statistic being a single number based on the comparison of said candidate distribution and said reference distribution; and

means for selecting one of said candidate subimages based on its respective statistic.

2. A nonparametric imaging tracker for tracking a designated object within a scene, comprising:

an attainer for attaining a reference subimage of said object from an initial image of said scene;

a finder for determining a reference intensity distribution for said reference subimage;

an acquirer for acquiring a plurality of candidate subimages within an image received subsequent to receiving said initial image;

said finder operable to determine an intensity distribution for each candidate subimage;

a calculator for calculating a statistic for each candidate subimage, said statistic being a single number based on a comparison of a respective candidate intensity distribution with said reference intensity distribution; and

a selector for selecting one of said candidate subimages as a subimage of said object based on the value of each said candidate statistic.

3. The tracker of claim 2, wherein said statistical distribution finder is operable to produce an intensity level histogram for said reference subimage and for each candidate subimage, each histogram being a compilation of the number of pixels in the sampled input image having a particular intensity level for each of a plurality of different intensity levels, each reference and candidate intensity distribution integrated from a respective histogram.

4. The imaging tracker of claim 3, wherein said finder further comprises an estimator for interpolating said histogram to obtain a corrected histogram, said corrected histograms input into said calculator.

5. The imaging tracker of claim 2, wherein a search pattern is derived by said acquirer from a predicted new position of said object, said acquirer is operable to acquire candidate subimages at selected points in said search pattern.

6. The imaging tracker of claim 2, wherein:

said reference intensity level distribution comprises a linear array having a plurality of reference gray level members, each candidate intensity distribution comprising a like linear array of candidate gray level members;

said calculator for each candidate subimage, computing the difference of each reference gray level member with respect to a respective candidate gray level member to produce an array of difference members, said calculator selecting one of said difference members as said statistic for the respective candidate subimage.

7. The imaging tracker of claim 6, wherein each said difference member comprises an absolute difference between a candidate gray level member and a respective reference of gray level member, said statistic of any candidate subimage comprising the largest of said absolute differences for the last said candidate subimage.

8. The imaging tracker of claim 2, wherein a statistic indicating a complete distribution match is equal to a predetermined optimum value, a predetermined breaklock limit for said statistic displaced from said optimum value, a breaklock indicator indicating that said object is not found if said statistic is not between said breaklock limit and said optimum value.

9. The imaging tracker of claim 8, wherein a search pattern is derived by said acquirer from a predicted new position of said object, said acquirer operable to acquire candidate subimages at selected points in said search pattern;

a search pattern expander for expanding said search pattern responsive to said breaklock indicator indicating that said object is not found, a new set of candidate subimages thereafter being acquired by said acquirer at selected points in said expanded search pattern.

10. The imaging tracker of claim 2, and further comprising:

an object location updater for updating the location of said object responsive to said selector selecting one of said candidate subimages.

11. The imaging tracker of claim 2, and further comprising:

a reference distribution updater for updating said reference distribution with data from said selected candidate subimage.

12. The imaging tracker of claim 11, wherein the value of said selected candidate subimage statistic is used to control the operation of said reference distribution updater.

13. The imaging tracker of claim 11, wherein said reference distribution updater synthesizes a new reference distribution based on a weighted average of a current reference distribution and said intensity distribution of said selected candidate subimage.

14. The imaging tracker of claim 13, wherein said reference distribution updater is operable to assign weights on said current reference distribution and said intensity distribution of said selected candidate subimage as a function of the value of said selected candidate subimage statistic.

15. A nonparametric imaging tracker for tracking an object within a scene, comprising:

an acquirer for acquiring an initial reference subimage of said object;

a quantifier for determining a gray level for each of a plurality of pixels in said reference subimage;

a finder for finding a reference gray level histogram of said reference subimage;

an integrator for integrating said reference gray level histogram to yield a reference gray level distribution of said reference subimage;

said acquirer operable to acquire a plurality of candidate subimages, each said candidate subimage having a plurality of pixels;

said quantifier operable to determine a gray level for each pixel in each candidate subimage, said finder operable to find a candidate gray level histogram for each candidate subimage, said integrator operable to integrate a candidate gray level distribution for each candidate subimage;

a calculator for calculating a Kolmogorov-Smirnov statistic for each candidate subimage;

a selector for selecting the lowest of said Kolmogorov-Smirnov statistics; and

an object location updater for updating the location of said object in said scene based on the location of said selected candidate subimage.

16. The imaging tracker of claim 15, wherein candidate subimages are each centered on respective loci in a search pattern based on a predicted new position of said object within said scene.

17. The imaging tracker of claim 15, wherein said Kolmogorov-Smirnov statistic for each candidate subimage is calculated based on the following formula:

##EQU3## where R is a linear array of gray level members of a reference gray level distribution, S is a linear array of gray level members of a candidate gray level distribution, and I is a distribution index of said reference gray level members and said candidate gray level members.

18. The imaging tracker of claim 15, wherein said Kolmogorov-Smirnov statistic for each candidate subimage is calculated based on the following formula:

##EQU4## where R is a linear array of gray level members of a reference gray level distribution, S is a linear array of gray level members of a candidate gray level distribution, and I is a distribution index of said reference gray level members and said candidate gray level members.

19. The imaging tracker of claim 15, wherein said Kolmogorov-Smirnov statistic for each candidate subimage is calculated based on the following formula:

##EQU5## where R is a linear array of gray level members of a reference gray level distribution, S is a linear array of gray level members of a candidate gray level distribution, and I is a distribution index of said reference gray level members and said candidate gray level members.

20. A method for tracking an object in a scene comprising the steps of:

declaring a reference subimage of said object comprising a plurality of image pixels, each pixel having a numerical intensity level;

finding a reference distribution of intensity levels in the reference subimage;

acquiring a plurality of candidate subimages each having a plurality of pixels;

finding a candidate subimage distribution of intensity levels for each of the candidate subimages;

comparing each candidate subimage distribution to the reference distribution;

computing a statistic for each candidate subimage, said statistic being a single number based on said step of comparing; and

selecting one of the candidate subimages based on its respective statistic.

21. The method of claim 20, and further including the step of acquiring said reference subimage from an autonomous reference image attainer.

22. The method of claim 20, and further comprising the steps of:

finding a gray level histogram having a plurality of gray level histogram members for the reference subimage and for each candidate subimage;

computing a gray level distribution having a plurality of gray level distribution members for the reference subimage and for each candidate subimage based on numerical integration of the values of the respective gray level histograms; and

computing a statistic for each candidate subimage based on a comparison of each gray level distribution member of the reference distribution with a corresponding gray level distribution member of the respective candidate histogram.

23. The method of claim 22, and further including the steps of:

applying an estimator to each gray level histogram to obtain a corrected gray level histogram; and

using said corrected gray level histogram in said computation of said gray level distribution.

24. The method of claim 20, wherein said step of comparing distributions comprises for each candidate subimage, computing the absolute value of the difference of the value of each gray level member of the respective candidate distribution with a corresponding value of a gray level member of the reference distribution to obtain an array of absolute difference members.

25. The method of claim 23, wherein said step of computing the statistic for each candidate comprises the step of selecting the maximum of said gray level difference members.

26. The method of claim 20, wherein said step of comparing comprises the step of subtracting the value of each reference gray level distribution member from the value of a corresponding candidate gray level distribution member, to obtain an array comprising a gray level difference members.

27. The method of claim 26, wherein said step of computing the statistic for each candidate subimage comprises the step of selecting the maximum of said gray level difference members.

28. The method of claim 20, wherein said step of selecting one of the candidate subimages includes the further steps of:

determining the smallest of said candidate subimage statistics; and

selecting the candidate subimage corresponding to the smallest candidate statistic.

29. The method of claim 20, and further including the steps of:

selecting the candidate subimage statistic that is closest to an optimum value;

determining whether the selected statistic is within a breaklock displacement of the optimum value;

declaring the object not to be found if the selected statistic is not within the breaklock displacement; and

declaring a new object location to be the location of the corresponding candidate subimage if the selected statistic is within the breaklock displacement.

30. The method of claim 29, and further including the steps of:

if the object is declared not to be found, expanding a search pattern;

acquiring a new plurality of new candidate subimages centered on loci in the expanded search pattern; and

repeating said steps of comparing, computing, selecting and determining for the new candidate subimages.

31. The method of claim 29, and further including the steps of:

if the object is not found, acquiring a plurality of new candidate subimages from subsequent images; and

repeating said steps of comparing, computing, selecting and determining for the new candidate subimages.

32. A method for tracking an imaged object within a scene, comprising the steps of:

obtaining an initial reference subimage of the object comprising a plurality of pixels, each pixel having a numerical gray level;

finding a reference gray level histogram for the reference subimage;

computing a reference gray level distribution from the reference gray level histogram;

storing the reference gray level distribution;

acquiring a plurality of candidate subimages within a new image of the scene;

finding a candidate gray level histogram for each of the candidate subimages;

computing candidate gray level distribution from each candidate gray level histogram;

computing a Kolmogorov-Smirnov statistic Δ

₂ for each candidate subimage according to the following formula;

##EQU6## wherein R is a linear array of reference distribution gray level members, S is a linear array of candidate distribution gray level members, and I is a gray level member index;

selecting the smallest of the statistics; and

declaring a new object location in the scene based on the locus of the corresponding candidate subimage.