Method and apparatus for performing a clean background subtraction

• US RE42,256 E1
• Filed: 01/09/2009
• Issued: 03/29/2011
• Est. Priority Date: 10/15/1997
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Elet Systems LLC
• Inventors: Edwards, Jeffrey L.
• Primary Examiner(s): Le; Brian Q
• Application Number:
  US12/351,762
• Time in Patent Office: 809 Days
• Field of Search: 382/209, 382/190, 382/217, 382/195, 382/197, 382/199, 382/282, 382/294, 382/173, 382/201, 382/293, 382/256, 382/257, 345/474, 345/473, 345/629, 700/83
• US Class Current: 382/173
• CPC Class Codes: G06K 9/00369 Recognition of whole body, e.g. static pedestrian or occupant recognition G06K9/00342 takes precedence
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

A background subtraction apparatus of the present invention includes a key point locator for locating key points on a known object type, a boundary point locator for locating boundary points of the known object that make up the edges of the known object, and an edge processor for processing the edges to provide a clean-edged extraction of the known object from a background image. Preferably, the key point locator includes an alignment detector for detecting alignment of an image of the known object type with a skeleton image. Still more preferably, the skeleton image is an exoskeleton image and the known object type is a human being.

Claims

1. A method for subtracting a background comprising:

locating key points on an image of a known object type;

determining line segments between the key points;

locating boundary points of the image that comprise edges of the known object by using the line segments;

eliminating pixel gaps between the boundary points;

connecting the boundary points to obtain a closed loop of pixels;

processing the edges to provide a clean-edged extraction of the image from a background image, including using an alpha image to determine a key point, which is selected based on a similarity score for a region in the alpha image; and

reducing noise from the edges of the known object, after determining the key points, using an edge strength, the alpha image, and the line segments by aligning a snake to the line segments;

wherein at least one key point is located based at least in part on a key point template comprising a plurality of pixels and specially configured for that key point; and

wherein the pixels in the specially configured key point template that make up a shape associated with the key point have a first value and the other pixels in the specially configured key point template have a second value.

2. A method for subtracting a background as recited in claim 1 further including aligning the image with a skeleton image prior to locating the key points.

3. A method for subtracting a background as recited in claim 1 wherein locating boundary points includes scanning the image in directions dependent upon the orientation of the line segments.

4. A method for subtracting a background as recited in claim 1 wherein the key points include primary key points and secondary key points located based on the primary key points.

5. A method for subtracting a background as recited in claim 1 wherein locating the key points includes using a general search area.

6. A method for subtracting a background as recited in claim 1 wherein locating the key points includes using a general search area and a Summed Area Table.

7. A method for subtracting a background as recited in claim 1 wherein locating the key points includes:

locating primary key points;

determining whether the primary key points are in acceptable locations;

repeating locating primary key points if the primary key points are determined not to be in acceptable locations;

locating secondary key points based on the primary points;

determining whether the secondary points are in acceptable locations;

repeating locating secondary key points if the secondary key points are determined not to be in acceptable locations.

8. A method for subtracting a background as recited in claim 1 further including aligning the image of the known object type with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image.

9. A method for subtracting a background as recited in claim 1 further including:

aligning the image of the known object type with a skeleton image prior to locating the key points;

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image.

10. A method for subtracting a background as recited in claim 1 further including:

aligning the image with a skeleton image prior to locating the key points;

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points.

11. A method for subtracting a background as recited in claim 1 further including:

aligning the image with a skeleton image prior to locating the key points;

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points plus a pad of pixels.

12. A method for subtracting a background as recited in claim 1 further including aligning the image with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image and the known object type is a human being.

13. A method for subtracting a background as recited in claim 1 further including aligning the image with a skeleton image prior to locating the key points, wherein:

the skeleton image is an outline image;

the known object type is a human being; and

the key points include primary key points at extremities of the image and secondary key points near a torso of the image.

14. A method for subtracting a background as recited in claim 1 wherein processing the edges includes filtering the edges.

15. A background subtraction apparatus comprising:

an image acquisition device for acquiring an image of a known object type; and

a processor configured to;

locate key points on the image;

determine line segments between the key points;

locate boundary points of the image that comprise edges of the known object by using the line segments;

eliminate pixel gaps between the boundary points;

connect the boundary points to obtain a closed loop of pixels;

process the edges to provide a clean-edged extraction of the image from a background image including using an alpha image to determine a key point, which is selected based on a similarity score for a region in the alpha image; and

reduce noise from the edges of the known object, after determining the key points, using an edge strength, the alpha image, and the line segments by aligning a snake to the line segments;

wherein at least one key point is located based at least in part on a key point template comprising a plurality of pixels and specially configured for that key point; and

wherein the pixels in the specially configured key point template that make up a shape associated with the key point have a first value and the other pixels in the specially configured key point template have a second value.

16. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to align the image with a skeleton image.

17. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to scan the image in directions dependent upon the orientation of the line segments.

18. A background subtraction apparatus as recited in claim 15 wherein the key points include primary key points and secondary key points located based on the primary key points.

19. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to locate the key points using a general search area.

20. A background subtraction apparatus as recited in claim 15 the processor is further configured to locate the key points using a general search area and a Summed Area Table.

21. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to:

locate primary key points;

repeat locating primary key points if the primary key points are determined not to be in acceptable locations;

locate secondary key points based on the primary key points;

determine whether the secondary key points are in acceptable locations;

repeat locating secondary key points if the secondary key points are determined not to be in acceptable locations.

22. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to align the image of the known object type with a skeleton image, wherein the skeleton image is an outline image.

23. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to:

align the image of the known object type with a skeleton image prior to locating the key points;

scan the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image.

24. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to:

align the image with a skeleton image prior to locating the key points;

scan the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points.

25. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to:

align the image with a skeleton image prior to locating the key points;

scan the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points plus a pad of pixels.

26. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to align the image with a skeleton image, wherein the skeleton image is an outline image and the known object type is a human being.

27. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to align the image with a skeleton image, wherein:

the skeleton image is an outline image;

the known object type is a human being; and

the key points include primary key points at extremities of the image and secondary key points near a torso of the image.

28. A background subtraction apparatus as recited in claim 15 wherein the processor is further configured to filter the edges.

29. A non-transitory computer-readable storage medium having computer implemented process instructions stored thereon that, if executed by a computer, cause the computer to perform a method for subtracting a background, the method comprising:

locating key points on an image of a known object type, including using an alpha image to determine a key point, which is selected based on a similarity score for a region in the alpha image;

determining line segments between the key points;

locating boundary points of the image that comprise edges of the known object by using the line segments;

eliminating pixel gaps between the boundary points;

connecting the boundary points to obtain a closed loop of pixels;

processing the edges to provide a clean-edged extraction of the image from a background image; and

reducing noise from the edges of the known object, after determining the key points, using an edge strength, the alpha image, and the line segments by aligning a snake to the line segments;

wherein at least one key point is located based at least in part on a key point template comprising a plurality of pixels and specially configured for that key point; and

wherein the pixels in the specially configured key point template that make up a shape associated with the key point have a first value and the other pixels in the specially configured key point template have a second value.

30. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions include instructions for aligning the image with a skeleton image prior to locating the key points.

31. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions for locating boundary points include instructions for scanning the image in directions dependent upon the orientation of the line segments.

32. The non-transitory computer-readable storage medium recited in claim 29, wherein the key points include primary key points and secondary key points located based on the primary key points.

33. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions for locating the key points include instructions for using a general search area.

34. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions for locating the key points include instructions for using a general search area and a Summed Area Table.

35. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions for locating the key points include instructions for:

locating primary key points;

determining whether the primary key points are in acceptable locations;

repeating locating primary key points if the primary key points are determined not to be in acceptable locations;

locating secondary key points based on the primary points;

determining whether the secondary points are in acceptable locations; and

repeating locating secondary key points if the secondary key points are determined not to be in acceptable locations.

36. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions include instructions for aligning the image of the known object type with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image.

37. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions include instructions for:

aligning the image of the known object type with a skeleton image prior to locating the key points; and

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image.

38. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions include instructions for:

aligning the image with a skeleton image prior to locating the key points; and

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points.

39. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions further include instructions for:

aligning the image with a skeleton image prior to locating the key points; and

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points plus a pad of pixels.

40. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions further include instructions for aligning the image with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image and the known object type is a human being.

41. The non-transitory computer-readable storage medium recited in claim 29, wherein the instructions further include instructions for aligning the image with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image;

wherein the known object type is a human being; and

wherein the key points include primary key points at extremities of the image and secondary key points near a torso of the image.

42. The non-transitory computer-readable storage medium recited in claim 29, wherein processing the edges includes filtering the edges.

43. A computer-implemented method for subtracting an image of a known object type from a background image, the method comprising:

locating, with a computer, key points on an image of a known object type based on a similarity score for a region in an alpha image of the known object type and a template of a key point;

determining line segments between the key points;

locating boundary points of the image of the known object that comprise edges of the known object by using the line segments;

eliminating pixel gaps between the boundary points;

reducing noise from the edges of the image of the known object, after determining the key points, using an edge strength, the alpha image, and the line segments by aligning a snake to the line segments; and

connecting the boundary points to obtain a closed loop of pixels;

wherein the template comprises a plurality of pixels and is specially configured for that key point; and

wherein the pixels in the template that make up a shape associated with the key point have a first value, and the other pixels in the template have a second value.

44. The method of claim 43, the method further comprising determining if the image of the known object is aligned with a skeleton image prior to locating the key points.

45. The method of claim 43, wherein locating boundary points includes scanning the image in directions dependent upon the orientation of the line segments.

46. The method of claim 43, wherein the key points include primary key points and secondary key points located based on the primary key points.

47. The method of claim 43, wherein locating the key points includes using a general search area.

48. The method of claim 43, wherein locating the key points includes using a general search area and a Summed Area Table.

49. The method of claim 43, wherein locating the key points includes:

locating primary key points;

determining whether the primary key points are in acceptable locations;

repeating locating primary key points if the primary key points are determined not to be in acceptable locations;

locating secondary key points based on the primary points;

determining whether the secondary points are in acceptable locations; and

repeating locating secondary key points if the secondary key points are determined not to be in acceptable locations.

50. The method of claim 43, further comprising determining if the image of the known object type is aligned with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image.

51. The method of claim 43, further comprising:

prompting a user to align the image of the known object type with a skeleton image prior to locating the key points; and

scanning the image in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image.

52. The method of claim 43, further comprising:

prompting a user to align the image of the known object type with a skeleton image prior to locating the key points; and

scanning the image of the known object type in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points.

53. The method of claim 43, further comprising:

prompting a user to align the image of the known object type with a skeleton image prior to locating the key points; and

scanning the image of the known object type in directions dependent upon the orientation of the line segments, beginning at an offset away from the skeleton image;

wherein the offset is determined by a bounding box whose corners are set by the key points plus a pad of pixels.

54. The method of claim 43, further comprising prompting a user to align the image of the known object type with a skeleton image prior to locating the key points, wherein the skeleton image is an outline image and the known object type is a human being.

55. The method of claim 43, further comprising prompting a user to align the image of the known object type with a skeleton image prior to locating the key points;

wherein the skeleton image is an outline image;

wherein the known object type is a human being; and

wherein the key points include primary key points at extremities of the image and secondary key points near a torso of the image.

56. The method of claim 43, further comprising filtering the edges.

57. A background subtraction apparatus, comprising:

means for acquiring an image of a known object type;

means for locating key points on an image of a known object type based on a similarity score for a region in an alpha image of the known object type and a template of a key point;

means for determining line segments between the key points;

means for locating boundary points of the image of the known object that comprise edges of the known object by using the line segments;

means for eliminating pixel gaps between the boundary points;

means for reducing noise from the edges of the image of the known object, after determining the key points, using an edge strength, the alpha image, and the line segments by aligning a snake to the line segments; and

means for connecting the boundary points to obtain a closed loop of pixels;

wherein the template comprises a plurality of pixels and is specially configured for that key point; and

wherein the pixels in the template that make up a shape associated with the key point have a first value, and the other pixels in the template have a second value.

58. A background subtraction apparatus, comprising:

an image acquisition device for acquiring an image of a known object type; and

a processor configured to;

locate key points on an image of a known object type based on a similarity score for a region in an alpha image of the known object type and a template of a key point;

determine line segments between the key points;

locate boundary points of the image of the known object that comprise edges of the known object by using the line segments;

eliminate pixel gaps between the boundary points;

reduce noise from the edges of the image of the known object, after determining the key points, using an edge strength, the alpha image, and the line segments by aligning a snake to the line segments; and

connect the boundary points to obtain a closed loop of pixels;

wherein the template comprises a plurality of pixels and is specially configured for that key point; and

wherein the pixels in the template that make up a shape associated with the key point have a first value, and the other pixels in the template have a second value.

59. The apparatus recited in claim 58, wherein the processor is further configured to align the image with a skeleton image prior to locating the key points.

60. The apparatus recited in claim 58, wherein the processor is further configured to:

locate primary key points;

determine whether the primary key points are in acceptable locations;

repeat locating primary key points if the primary key points are determined not to be in acceptable locations;

locate secondary key points based on the primary points;

determine whether the secondary points are in acceptable locations; and

repeat locating secondary key points if the secondary key points are determined not to be in acceptable locations.