Extracting a matte of a foreground object from multiple backgrounds by triangulation

• US 6,301,382 B1
• Filed: 06/06/1997
• Issued: 10/09/2001
• Est. Priority Date: 06/07/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Alvy Ray, Blinn, James F.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US08/870,940
• Time in Patent Office: 1,586 Days
• Field of Search: 382/162, 382/163, 382/167, 382/154, 382/284, 348/586-587, 348/592, 348/578, 348/584, 348/590, 348/577, 345/435, 345/114, 358/540, 358/450
• US Class Current: 382/162
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: H04N 5/275 Generation of keying signals
• CPC Class Codes: H04N 9/75 Chroma key

Abstract

A method for pulling (extracting) a matte of an image of a foreground object from a composite image, using a computer. An image of the foreground object is recorded over at least two backgrounds having arbitrarily different coloring. Each point of one background must have a color that is different than the color of a corresponding point in the other backgrounds. The images may be recorded with an analog camera and digitized with a scanner or recorded with a digital camera. Images should be registered during recording and digitization to eliminate misalignment of corresponding points in each recorded image. A triangulation of corresponding points of each recorded image is performed so that an alpha value (opacity) and a set of color coordinates for each point of an uncomposited image of the foreground object may be determined using either a difference of sums technique or a least squares technique. To facilitate the triangulation, images are recorded of each background alone, without the foreground object. The lighting and distances between the camera and object, and between the object and backgrounds should remain constant during the image recording process.

Claims

1. A method for extracting an image of a foreground object from composite images, using a computer, comprising the steps of:

(a) recording a first composite image that includes the foreground object disposed in front of a first background having a first arbitrary coloring;

(b) recording a second composite image that includes the foreground object disposed in front of a second background having a second arbitrary coloring that is different than the first arbitrary coloring;

(c) obtaining a set of color coordinates for each point in the first composite image and in the second composite image, said color coordinates defining a color for each point; and

(d) triangulating the set of color coordinates for each point in each of the first and the second composite images, the step of triangulating returning an alpha value and a set of color coordinates for each point in the image of the foreground object, to define the image of the foreground object apart from any background.

2. The method of claim 1, further comprising the step of digitizing the first composite image and the second composite image to produce the set of color coordinates for each point in each of the first and the second composite images.

3. The method of claim 2, further comprising the step of aligning each point of the first composite image with a corresponding point disposed within the second composite image.

4. The method of claim 1, wherein the step of triangulating comprises the steps of:

(a) recording a first background image that includes the first background, but not the foreground object;

(b) recording a second background image that includes the second background, but not the foreground object; and

(c) determining a set of color coordinates for each point in the first background image and for each point in the second background image, the set of color coordinates that define the foreground object apart from any background being determined as a function of the set of color coordinates for each of the points in the first and the second background images and in the first and second composite images.

5. The method of claim 1, wherein, the set of color coordinates for each of the first and the second composite images indicate values for a red color, a green color, and a blue color, at each of the points in said images.

6. The method of claim 5, wherein each point in the first background image has a color that is different than that of a corresponding point in the second background image, so that a sum of differences between the values for the red color, the green color and the blue color, respectively, for corresponding points in the first background and the second background is not equal to zero.

7. The method of claim 5, wherein each point in the first background image has a color that is different than that of a corresponding point in the second background image, so that a sum of squared differences between the values for the red color, the green color and the blue color, respectively, for corresponding points in the first background and the second background is not equal to zero.

8. The method of claim 1, wherein a constant illumination of the foreground object and the first and second background is employed during the steps of recording the first and the second composite images.

9. The method of claim 1, wherein a camera is used to record the first and the second composite images, and wherein substantially constant distances are maintained between the foreground object and the camera, and between the foreground object and the first and second backgrounds during the step of recording the first and the second composite images with the camera.

10. The method of claim 1, wherein the first background is an arbitrary pure color and the second background is a different, but otherwise arbitrary pure color.

11. The method of claim 4, wherein the step of triangulating employs a difference of sums technique to determine the value of the alpha channel and the set of color coordinates for each point in the image of the foreground object, as a function of said sets of color coordinates for the first and second composite images, and for the first and second background images.

12. The method of claim 4, wherein the step of triangulating employs a least squares technique to determine the value of the alpha channel and the set of color coordinates for each point in the image of the foreground object, as a function of the sets of color coordinates for the first and second composite images, and for the first and second background images.

13. The method of claim 1, further comprising the steps of:

(a) determining a lower limit of the alpha value for each point in the image of the foreground object as a function of the set of color coordinates for the point;

(b) determining an upper limit of the alpha value for each point in the image of the foreground object as a function of the set of color coordinates for the point;

(c) employing said lower limit and said upper limit to define a range for the alpha value at each point in the image of the foreground object.

14. The method of claim 1, further comprising the steps of:

(a) recording a first scene of the foreground object disposed in front of a first portion of a background but not in front of a second portion of the background, the first and second portions of said background having a different coloring, a section of said first scene that includes the foreground object disposed in front of the first portion of the background being employed to define the first composite image and another section of said first scene that includes the second portion of the background being employed to define a second background image; and

(b) recording a second scene of the foreground object disposed in front of the second portion of the background, but not in front of the first portion of the background, a section of said second scene that includes the foreground object disposed in front of the second portion of the background being employed to define the second composite image and another section of said second scene that includes the first portion of the background being employed to define a first background image; and

(c) obtaining a set of color coordinates for each point in the first background image and for each point in the second background image, the set of color coordinates that define the foreground object apart from any background being determined as a function of the set of color coordinates for;

(i) each point in the first and second background images; and

(ii) each point in the first and second composite images.

15. The method of claim 14, further comprising the step of rigidly moving the foreground object relative to the background when recording the first and second scenes.

16. The method of claim 14, wherein the first portion and the second portions of the background overlap.

17. The method of claim 1, further comprising, the steps of:

(a) similarly recording a plurality of images of a scene for each composite image;

(b) obtaining a plurality of sets of color coordinates for each point of said plurality of images;

(c) averaging said plurality of sets of color coordinates to produce the set of color coordinates for each point in each composite image.

18. The method of claim 1, further comprising the steps of:

(a) recording n minus two additional composite images, each of said additional composite images including the foreground object disposed in front of a different background having an arbitrary coloring that is different than the arbitrary coloring of any other backgrounds;

(b) obtaining a set of color coordinates for each point in the additional composite images, said color coordinates defining a color for each point; and

(c) triangulating the set of color coordinates for each point in each of the first, the second, and the n minus two additional composite images, the step of triangulating returning the alpha value and the set of color coordinates for each point in the image of the foreground object.

19. The method of claim 1, wherein the image of the foreground object includes a shadow of the foreground object cast on the first and the second backgrounds.

20. A system for extracting an image of a foreground object from composite images, comprising:

(a) a processor;

(b) an interface, coupled to the processor, for input of digitized signals corresponding to the composite images;

(b) a memory coupled to the processor, for storing machine instructions and data defined by said digitized signals, said machine instructions causing the processor to implement a plurality of functions using the digitized signals, including;

(i) entering data into the memory corresponding to the digitized signals that define a composite image of the foreground object disposed in front of a first background having a first arbitrary coloring;

(ii) entering data into the memory corresponding to the digitized signals that define a second composite image of the foreground object disposed in front of a second background having a second arbitrary coloring that is different than the first arbitrary coloring; and

(iii) using the data stored in the memory, triangulating a set of color coordinates for each point in each of the first and the second composite images, returning an alpha value and a set of color coordinates for each point in the image of the foreground object, to define the image of the foreground object apart from any background.

21. The system of claim 20, further comprising an analog camera to record the first and the second composite images;

and a digitizer to convert said first and second composite images into the digital signal that is input to the interface.

22. The system of claim 20, further comprising a digital camera that produces the digital signal defining the first and the second composite images.

23. The system of claim 20, wherein the functions further include using the digitized signals while aligning each point of the first composite image with a corresponding point disposed within the second composite image.

24. The system of claim 20, wherein while triangulating the data stored in memory, the processor:

(a) enters data into the memory, said data corresponding to the digitized signals that define a first background image including the first background, but not the foreground object;

(b) enters data into the memory, said data corresponding to the digitized signals that define a second background image including the second background, but not the foreground object; and

(c) determines a set of color coordinates for each point in the first background image and for each point in the second background image, the set of color coordinates that define the foreground object apart from any background being determined as a function of;

(i) the set of color coordinates for each of the points in the first and the second background images; and

(ii) the set of color coordinates for each of the points in the first and second composite images.

25. The system of claim 20, wherein, the set of color coordinates for each of the first and the second composite images indicate values for a red color, a green color, and a blue color, at each of the points in said images.

26. The system of claim 25, wherein each point in the first background image has a color that is different than that of a corresponding point in the second background image, so that a sum of differences between the values for the red color, the green color and the blue color, respectively, for corresponding points in the first background and the second background, is not equal to zero.

27. The system of claim 20, wherein each point in the first background image has a color that is different than that of a corresponding point in the second background image, so that a sum of squared differences between the values for the red color, the green color and the blue color, respectively, for corresponding points in the first background and the second background, is not equal to zero.

28. The system of claim 20, wherein a constant illumination of the foreground object and of the first and second background is employed during the recording of the first and the second composite images that are defined by the digitized signals.

29. The system of claim 20, wherein substantially constant distances are maintained between the foreground object and a camera, and between the foreground object and the first and second backgrounds, during the recording of the first and the second composite images that are defined by the digitized signals.

30. The system of claim 20, wherein the first background is an arbitrary pure color and the second background is a different, but otherwise arbitrary pure color.

31. The system of claim 24, wherein triangulating the data stored in memory further includes a difference of sums technique to determine the value of the alpha channel and the set of color coordinates for each point in the image of the foreground object, as a function of said sets of color coordinates for the first and second composite images, and for the first and second background images.

32. The system of claim 24, wherein while triangulating the data stored in memory, a least squares technique is used to determine the value of the alpha channel and the set of color coordinates for each point in the image of the foreground object, as a function of:

(a) the sets of color coordinates for the first and second composite images; and

(b) the sets of color coordinates for the first and second background images.

33. The system of claim 24, wherein while triangulating the data stored in memory, the processor:

(a) determines a lower limit of the alpha value for each point in the image of the foreground object as a function of the set of color coordinates for the point;

(b) determines an upper limit of the alpha value for each point in the image of the foreground object as a function of the set of color coordinates for the point; and

(c) employs said lower limit and said upper limit to define a range for the alpha value at each point in the image of the foreground object.

34. The system of claim 20, wherein while triangulating the data stored in memory, the processor:

(a) stores data in the memory, said data corresponding to the digitized signals that define a first scene of the foreground object disposed in front of a first portion of a background but not in front of a second portion of the background, said background having a coloring that changes between the first and second portions of the background, a section of said first scene that includes the foreground object disposed in front of the first portion of the background being employed by the processor to define the first composite image, and another section of said first scene that includes the second portion of the background being employed by the processor to define a second background image; and

(b) store data into the memory, said data corresponding to the digitized signals that define a second scene of the foreground object disposed in front of the second portion of the background but not in front of the first portion of the background, a section of said second scene that includes the foreground object disposed in front of the second portion of the background being employed to define the second composite image and another section of said second scene that includes the first portion of the background being employed to define a first background image; and

(c) determine a set of color coordinates for each point in the first background image and for each point in the second background image, the set of color coordinates that define the foreground object apart from any background being determined as a function of the set of color coordinates for each of the points in the first and the second background images and in the first and second composite images.

35. The system of claim 34, wherein the functions implemented by the processor further include storing data in the memory corresponding to the digitized signals that define the foreground object being rigidly moved relative to the background, when recording the first and the second scenes.

36. The system of claim 20, wherein the functions implemented by the processor further include:

(a) storing data in the memory, said data corresponding to the digitized signals that define a plurality of similarly recorded images of a scene for each composite image;

(b) storing data in the memory, said data corresponding to the digitized signals that define a plurality of sets of color coordinates for each point in said plurality of images;

(c) averaging said plurality of sets of color coordinates to produce the set of color coordinates for each point in each composite image.

37. The system of claim 20, wherein the functions implemented by the processor further include:

(a) recording n minus two additional composite images, each of said additional composite images including the foreground object disposed in front of a different background having an arbitrary coloring that is different than the arbitrary coloring of any other backgrounds;

(b) producing a set of color coordinates for each point in the additional composite images, said color coordinates defining a color for each point; and

(c) triangulating the set of color coordinates for each point in each of the first, the second, and the n minus two additional composite images, the step of triangulating returning the alpha value and the set of color coordinates for each point in the image of the foreground object.

38. An article of manufacture adapted for use with a computer, for extracting an image of a foreground object from at least two composite images, comprising:

(a) a memory medium adapted to be used with the computer; and

(b) a plurality of machine instructions stored on the memory medium, said machine instructions, when executed by a computer, causing the computer to implement a plurality of functions, including;

(i) storing data, said data corresponding to the digitized signals that define a composite image of the foreground object disposed in front of a first background having a first arbitrary coloring;

(ii) storing data, said data corresponding to the digitized signals that define a second composite image of the foreground object disposed in front of a second background having a second arbitrary coloring that is different than the first arbitrary coloring; and

(iii) using the data that was stored, triangulating the set of color coordinates for each point in each of the first and the second composite images, returning an alpha value and a set of color coordinates for each point in the image of the foreground object, to define the image of the foreground object apart from any background.

39. The article of manufacture of claim 38, wherein the functions further include aligning each point of the first composite image with a corresponding point disposed within the second composite image.

40. The article of manufacture of claim 38, wherein while triangulating the data stored, the machine instructions cause the computer to:

(a) store data corresponding to the digitized signals that define a first background image, including the first background, but not the foreground object;

(b) store data corresponding to the digitized signals that define a second background image, including the second background, but not the foreground object; and

(c) determining a set of color coordinates for each point in the first background image and for each point in the second background image, the set of color coordinates that define the foreground object apart from any background being determined as a function of the set of color coordinates for each of the points in the first and the second background images and in the first and second composite images.

41. The article of manufacture of claim 38, wherein, the set of color coordinates for each of the first and the second composite images indicate values for a red color, a green color, and a blue color, at each of the points in said images.

42. The article of manufacture of claim 38, wherein each point in the first background image has a color that is different than that of a corresponding point in the second background image, so that a sum of differences between the values for a red color, a green color and a blue color, respectively, for corresponding points in the first background and the second background, is not equal to zero.

43. The article of manufacture of claim 38, wherein each point in the first background image has a color that is different than that of a corresponding point in the second background image, so that a sum of squared differences between the values for a red color, a green color and a blue color, respectively, for corresponding points in the first background and the second background, is not equal to zero.

44. The article of manufacture of claim 38, wherein a constant illumination of the foreground object and the first and second background is employed during the recording of the first and the second composite images that are defined by the digitized signals.

45. The article of manufacture of claim 38, wherein substantially constant distances are maintained between the foreground object and a camera, and between the foreground object and the first and second backgrounds during the recording of the first and the second composite images that are defined by the digitized signals.

46. The article of manufacture of claim 38, wherein the first background is an arbitrary pure color and the second background is a different, but otherwise arbitrary pure color.

47. The article of manufacture of claim 40, wherein while triangulating the data, the machine instructions cause the computer to employ a difference of sums technique to determine the value of the alpha channel and the set of color coordinates for each point in the image of the foreground object, as a function of:

(a) said sets of color coordinates for the first and second composite images; and

(b) said sets of color coordinates for the first and second background images.

48. The article of manufacture of claim 40, wherein while triangulating the data, the machine instructions cause the computer to employ a least squares technique to determine the value of the alpha channel and the set of color coordinates for each point in the image of the foreground object, as a function of:

(a) the sets of color coordinates for the first and second composite images; and

(b) the sets of color coordinates for the first and second background images.

49. The article of manufacture of claim 38, wherein the functions further include:

(a) determining a lower limit of the alpha value for each point in the image of the foreground object as a function of the set of color coordinates for the point;

(b) determining an upper limit of the alpha value for each point in the image of the foreground object as a function of the set of color coordinates for the point; and

(c) employing said lower limit and said upper limit to define a range for the alpha value at each point in the image of the foreground object.

50. The article of manufacture of claim 38, wherein while triangulating the data, the machine instructions cause the computer to:

(a) enter data that define a first scene of the foreground object disposed in front of a first portion of a background, but not disposed in front of a second portion of the background, said first and second portions of the background having different coloring, a section of said first scene that includes the foreground object disposed in front of the first portion of the background being employed to define the first composite image, and another section of said first scene that includes the second portion of the background being employed to define a second background image; and

(b) enter data that define a second scene of the foreground object disposed in front of the second portion of the background, but not in front of the first portion of the background, a section of said second scene that includes the foreground object disposed in front of the second portion of the background being employed to define the second composite image, and another section of said second scene that includes the first portion of the background being employed to define a first background image; and

(c) determine a set of color coordinates for each point in the first background image and for each point in the second background image, the set of color coordinates that define the foreground object apart from any background being determined as a function of;

(i) the set of color coordinates for each of the points in the first and the second background images; and

(ii) the set of color coordinates for each of the point in the first and second composite images.

51. The article of manufacture of claim 38, wherein the functions further include entering data that define the foreground object being rigidly moved relative to the background, when recording the first and the second scenes.

52. The article of manufacture of claim 38, wherein the functions further include:

(a) entering data that define a plurality of similarly recorded scenes for each composite image;

(b) entering data that define a plurality of sets of color coordinates for each point of said plurality of scenes;

(c) averaging said plurality of sets of color coordinates to produce the set of color coordinates for each point in each composite image.

53. The article of manufacture of claim 38, wherein the functions further include:

(a) recording n minus two additional composite images, each of said additional composite images including the foreground object disposed in front of a different background having an arbitrary coloring that is different than the arbitrary coloring of any other backgrounds;

(b) producing a set of color coordinates for each point in the additional composite images, said color coordinates defining a color for each point; and

(c) triangulating the set of color coordinates for each point in each of the first, the second, and the n minus two additional composite images, returning the alpha value and the set of color coordinates for each point in the image of the foreground object.