Technique for tracking objects through a series of images

• US 6,400,830 B1
• Filed: 02/06/1998
• Issued: 06/04/2002
• Est. Priority Date: 02/06/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Avery, Brian Lyndall, Christian, Andrew Dean
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/020,044
• Time in Patent Office: 1,579 Days
• Field of Search: 382/103, 382/107, 382/199, 382/209, 382/225, 382/236, 382/254, 382/260-262, 382/275, 348/29, 348/34, 348/155, 348/169, 348/607, 345/473
• US Class Current: 382/103
• 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: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition

Abstract

A technique for tracking objects through a series of images is disclosed. In one embodiment, the technique is realized by obtaining at least first and second representations of a plurality of pixels, wherein at least one grouping of substantially adjacent pixels has been identified in each of the first and second representations. Each identified grouping of substantially adjacent pixels in the first representation is then matched with an identified grouping of substantially adjacent pixels in the second representation.

Claims

1. A method for tracking objects through a series of images, wherein each image includes a plurality of pixels, and wherein each pixel is defined by digitized intensity and digitized color, the method comprising the steps of:

averaging a plurality of images of entire scenes and therefrom establishing a background image of an entire scene containing no objects of interest,

storing the averaged background image as a plurality of pixels,

receiving first and second representations of the images'"'"' plurality of pixels,

processing the digitized intensity and the digitized color of each pixel,

with respect to the stored averaged background image pixels, grouping substantially adjacent pixels according to their processed intensity and their color, thereby forming at least one first identified grouping of substantially adjacent pixels within the first representation and at least one second grouping of substantially adjacent pixels within the second representation,

matching the first and second groupings of substantially adjacent pixels thereby defining and tracking an identified grouping of substantially adjacent pixels,

determining if the identified grouping is a grouping of interest, and

updating the averaged background image by averaging in the pixels from the first and the second representations minus any identified grouping of interest.

2. The method as defined in claim 1, wherein the step of matching each identified grouping of substantially adjacent pixels in the first representation with an identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

3. The method as defined in claim 2, wherein said step of calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score based upon a size comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

4. The method as defined in claim 2, wherein said step of calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score based upon a location comparison of each identified grouping of substantially adjacent pixels within the first representation and each identified grouping of substantially adjacent pixels within the second representation.

5. The method as defined in claim 2, wherein said step of calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score based upon an aspect ratio comparison of each identified grouping of substantially adjacent pixels in the representation and each identified grouping of substantially adjacent pixels in the second representation.

6. The method as defined in claim 2, wherein said step of calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score based upon a texture comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

7. The method as defined in claim 2, wherein said step of calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score based upon a velocity comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

8. The method as defined in claim 2, wherein said step of calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the step of:

calculating a score based upon a color comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

9. The method as defined in claim 8, wherein the first representation represents differences between a third representation of a plurality of pixels and a fourth representation of a plurality of pixels, wherein second representation represents differences between a fifth representation of a plurality of pixels and the fourth representation of a plurality of pixels, wherein the step of calculating a score based upon a color comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation includes the steps of:

color sampling pixel areas in the third and the fifth representations corresponding to pixel areas in each identified grouping of substantially adjacent pixels in the first and the second representations;

averaging the color sampled pixel areas; and

comparing the averaged color sampled pixel areas.

10. The method as defined in claim 9, wherein the step of color sampling pixel areas in the third and the fifth representations corresponding to pixel areas in each identified grouping of substantially adjacent pixels in the first and the second representations includes the step of:

color sampling pixel areas in a predefined pattern in the third and the fifth representations.

11. The method as defined in claim 9, further comprising the step of:

combining a subset of the compared averaged color sampled pixel areas to provide a measure of color accuracy.

12. The method as defined in claim 2, further comprising the step of:

comparing each score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation to a threshold value.

13. The method as defined in claim 12, further comprising the steps of:

listing each score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation according to a score value;

matching an identified grouping of substantially adjacent pixels in the first representation and an identified grouping of substantially adjacent pixels in the second representation according to highest score values; and

removing the matched identified groupings from the listing.

14. The method as defined in claim 13, further comprising the step of:

tracking the matched identified groupings through the series of images.

15. An apparatus for tracking objects through a series of images, wherein each image includes a plurality of pixels, and wherein each pixel is defined by digitized intensity and digitized color, comprising:

a background image of an entire scene containing no objects of interest, wherein the background image is an average of a plurality of images,

means for storing the background image as a plurality of pixels,

a first and a second representations of the images'"'"' plurality of pixels,

a processor that processes the digitized intensity and the digitized color of each pixel from the first and the second representations into groupings of substantially adjacent pixels to provide, with respect to the averaged background image, an at least one first identified grouping of substantially adjacent pixels within the first representation and at least one second grouping of substantially adjacent pixels within the second representation,

a matcher for matching the first and second groupings of substantially adjacent pixels thereby defining an identified grouping of substantially adjacent pixels, and

means for determining if the identified grouping is a grouping of interest, and

means for updating the averaged background image by averaging in the pixels from the first and the second representations minus any identified grouping of interest.

16. The apparatus as defined in claim 15, wherein the matcher includes a calculator for calculating a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

17. The apparatus as defined in claim 16, wherein the calculator calculates a score based upon a size comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

18. The apparatus as defined in claim 16, wherein the calculator calculates a score based upon a location comparison of each identified grouping of substantially adjacent pixels within the first representation and each identified grouping of substantially adjacent pixels within the second representation.

19. The apparatus as defined in claim 16, wherein the calculator calculates a score based upon an aspect ratio comparison of each identified grouping of substantially adjacent pixels in the representation and each identified grouping of substantially adjacent pixels in the second representation.

20. The apparatus as defined in claim 16, wherein the calculator calculates a score based upon a texture comparison of each identified grouping of substantially adjacent pixels in the representation and each identified grouping of substantially adjacent pixels in the second representation.

21. The apparatus as defined in claim 16, wherein the calculator calculates a score based upon a velocity comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

22. The apparatus as defined in claim 16, wherein the calculator calculates a score based upon a color comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

23. The apparatus as defined in claim 22, wherein the first representation represents differences between a third representation of a plurality of pixels and a fourth representation of a plurality of pixels, wherein second representation represents differences between a fifth representation of a plurality of pixels and the fourth representation of a plurality of pixels, wherein the calculator includes:

a sampler for color sampling pixel areas in the third and the fifth representations corresponding to pixel areas in each identified grouping of substantially adjacent pixels in the first and the second representations;

an averager for averaging the color sampled pixel areas; and

a comparer for comparing the averaged color sampled pixel areas.

24. The apparatus as defined in claim 23, wherein the sampler color samples pixel areas in a predefined pattern in the third and the fifth representations.

25. The apparatus as defined in claim 23, further comprising:

a combiner for combining a subset of the compared averaged color sampled pixel areas to provide a measure of color accuracy.

26. The apparatus as defined in claim 16, further comprising:

a comparer for comparing each score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation to a threshold value.

27. The apparatus as defined in claim 26, further comprising:

a lister for listing each score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation according to a score value;

a matcher for matching an identified grouping of substantially adjacent pixels in the first representation and an identified grouping of substantially adjacent pixels in the second representation according to highest score values; and

a remover for removing the matched identified groupings from the listing.

28. The apparatus as defined in claim 27, further comprising:

a tracker for tracking the matched identified groupings through the series of images.

29. An article of manufacture for tracking objects through a series of images, wherein each image includes a plurality of pixels, and wherein each pixel is defined by digitized intensity and digitized color, the apparatus comprising:

a computer readable storage medium; and

computer programming stored on the storage medium;

wherein, the stored computer programming is configured to be readable from the computer readable storage medium by a computer and thereby cause the computer to operate so as to;

establish a background image of an entire background image containing no objects of interest by averaging a plurality of images of entire scenes,

store the averaged background image as a plurality of pixels,

a first and a second representation of the images'"'"' plurality of pixels,

process the digitized intensity and digitized color of each pixel,

with respect to the stored averaged background image pixels, group substantially adjacent pixels according to their processed intensity and their processed color, thereby forming at least one first identified grouping of substantially adjacent pixels within the first representation and at least one second grouping of substantially adjacent pixels within the second representation,

match the first and second groupings of substantially adjacent pixels thereby defining an identified grouping of substantially adjacent pixels,

determine if the identified grouping is a grouping of interest, and

updating the averaged background image by averaging in the pixels from the first and the second representations minus any identified grouping of interest.

30. The article of manufacture as defined in claim 29, further causing the computer to operate so as to:

calculate a score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

31. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

calculate a score based upon a size comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

32. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

calculate a score based upon a location comparison of each identified grouping of substantially adjacent pixels within the first representation and each identified grouping of substantially adjacent pixels within the second representation.

33. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

calculate a score based upon an aspect ratio comparison of each identified grouping of substantially adjacent pixels in the representation and each identified grouping of substantially adjacent pixels in the second representation.

34. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

calculate a score based upon a texture comparison of each identified grouping of substantially adjacent pixels in the representation and each identified grouping of substantially adjacent pixels in the second representation.

35. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

calculate a score based upon a velocity comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

36. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

calculate a score based upon a color comparison of each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation.

37. The article of manufacture as defined in claim 36, wherein the first representation represents differences between a third representation of a plurality of pixels and a fourth representation of a plurality of pixels, wherein second representation represents differences between a fifth representation of a plurality of pixels and the fourth representation of a plurality of pixels, further causing the computer to operate so as to:

color sample pixel areas in the third and the fifth representations corresponding to pixel areas in each identified grouping of substantially adjacent pixels in the first and the second representations;

average the color sampled pixel areas; and

compare the averaged color sampled pixel areas.

38. The article of manufacture as defined in claim 37, further causing the computer to operate so as to:

color sample pixel areas in a predefined pattern in the third and the fifth representations.

39. The article of manufacture as defined in claim 37, further causing the computer to operate so as to:

combine a subset of the compared averaged color sampled pixel areas to provide a measure of color accuracy.

40. The article of manufacture as defined in claim 30, further causing the computer to operate so as to:

compare each score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation to a threshold value.

41. The article of manufacture as defined in claim 40, further causing the computer to operate so as to:

list each score between each identified grouping of substantially adjacent pixels in the first representation and each identified grouping of substantially adjacent pixels in the second representation according to a score value;

match an identified grouping of substantially adjacent pixels in the first representation and an identified grouping of substantially adjacent pixels in the second representation according to highest score values; and

remove the matched identified groupings from the listing.

42. The article of manufacture as defined in claim 41, further causing the computer to operate so as to:

track the matched identified groupings through the series of images.