Method and apparatus for performing a clean background subtraction

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.

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.