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

[0002] This application is a continuation-in-part patent application, based on prior copending provisional application Ser. No. 60/019,271, filed Jun. 7, 1996, the benefit of the filing date of which is hereby claimed under 35 U.S.C. §119(e).

[0003] The present invention relates to a method for “pulling” or extracting an image of one or more foreground objects from a composite image in which the foreground objects are in front of a background, and more particularly, to a method for pulling the one or more foreground objects from recorded images of the one or more objects disposed in front of two differently colored backgrounds.

[0004] In the motion picture industry, pulling a matte of a foreground object from a scene, i.e., extracting an image of the object from a background, and combining (compositing) the pulled matte with another entirely different background has proven to be difficult. Historically, an image of a foreground object was pulled with a matte created from a strip of monochrome film that was transparent for those portions of a scene that contained the desired object and opaque everywhere else. In this way, when the matte was placed together with another strip of film that included the complete scene (foreground object and background), only the foreground object would be illuminated (visible on a projection screen). A holdout matte is the complement of a matte because it is opaque for those portions of a scene that contain the foreground object(s) and transparent everywhere else. Thus, the holdout matte may be employed to pull a matte of the image of the background so that another foreground object may be combined with the pulled matte to create a new composite image. Furthermore, a matte and a holdout matte may have regions that are partially transparent, so that the foreground object and/or the background may be partially illuminated.

[0005] New scenes are often created by compositing an extracted (uncomposited) foreground object with a separately recorded background. A significant benefit of compositing is that if the foreground object needs alteration, the entire scene does not have to be re-recorded with the background. Instead, the individual foreground object may be manipulated and separately re-recorded. Also, if an object is not recorded with a camera, but has been optically scanned into a video memory, compositing may be the only way to incorporate the object into a composite image of a desired scene.

[0006] In the prior art, several techniques have been employed to extract an image of a foreground object from a background with varying degrees of success. One technique employs special types of light sources, such as sodium, infrared, and ultraviolet, to simultaneously record multiple images of a foreground object disposed over a single background on multiple strips of film. The multiple film images provide information about particular attributes of the foreground object so that the object's matte may be more easily pulled. However, employing special light sources to simultaneously record multiple images of a foreground object on different strips of film with multiple cameras or with a single camera that is modified to record on multiple strips of film simultaneously is difficult and expensive.

[0007] Another prior art technique teaches recording one image of a foreground object onto a single strip of film. The technique employs a uniform backing color behind a foreground object to pull a matte of the object. Petros Vlahos, an early pioneer of the motion picture and video industries, invented the Color Difference Technique™, which is the most commonly employed single film image technique for pulling a matte of a foreground object. Vlahos developed this technique so that editors in the film industry could inexpensively produce an image of separately recorded foreground objects combined with a new background. The technique provides for recording an image of a foreground object(s) in front of a background that has a pure and uniform color, such as blue, green, or yellow. Since blue is the most frequently employed pure and uniform color for backgrounds, the Color Difference Technique™ is commonly referred to as “blue screen matting.” Next, an operator manipulates a set of controls to pull a matte of those portions (foreground objects) of the image that do not contain the pure and uniform color. The pulled matte is the image of the foreground object and the matte may be combined with another separately recorded background to create a new composite image. Thus, the Color Difference Technique™ enables the separate recording of a foreground object within a film studio, so that a pulled matte of the object may be added to a new background at a later date. This aspect of the Color Difference Technique™ can be particularly important when creating a composite image that has a background, which is inherently expensive or dangerous to produce.

[0008] One disadvantage of the Color Difference Technique™ is that a background having a pure and uniform color is expensive to manufacture, and the impurities in the color of the background will adversely effect the quality of the matte pulled of the foreground object. Another disadvantage is that the coloring of the foreground object is restricted to those colors not represented in the background. Since the Color Difference Technique™ can only pull a matte of those portions of a foreground object that do not have the same color as the background, the matte will have a “hole” in any portion of the object that includes the background's color. For example, if a user of the Color Difference Technique™ employs a blue background to pull a matte of an actor having blue eyes of the same blue color as the background, the eyes of the actor will appear as transparent holes in the matte. Thus, the Color Difference Technique™ is an imperfect solution to the problem of pulling a matte of a foreground object.

[0009] Vlahos also developed an apparatus, the Ultimatte™, that applied the concepts of the Color Difference Technique™ to the production of video images. In addition to determining the color coordinates for each point (pixel) of an uncomposited foreground object, the Ultimatte™ provides for calculating an alpha channel of the object so that a digital matte may be accurately pulled of the object for video. The alpha channel is the digital equivalent of the holdout matte that is used to remove a foreground object from a scene in the film industry. However, the alpha channel is used in video to provide shape and transparency to a foreground object. A zero value in the alpha channel value for a pixel causes the pixel to be transparent, and as the alpha value approaches 100%, the pixel becomes increasingly more opaque, at the color specified for the pixel.

[0010] In accord with the present invention, a method is defined for extracting an image of a foreground object from composite digitized images, using a computer. The method includes the steps of recording a first composite image in which the foreground object is disposed in front of a first background having a first arbitrary coloring. A second composite image is then recorded 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. A set of color coordinates are obtained for each point in the first composite image and in the second composite image; the color coordinates define a color for each point. Finally, the set of color coordinates for each point in each of the first and the second composite images is triangulated, 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.

[0011] One of the features of the present invention is that the image of the foreground object may include a shadow of the foreground object that is cast on the first and the second backgrounds.

[0012] The file of this patent contains at least one drawing executed in color. Copies of this patent with color drawing(s) will be provided by the Patent and Trademark Office upon request and payment of the necessary fee.

[0013] The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following. detailed description, when taken in conjunction with the accompanying drawings, wherein:

[0014] FIG. 1 is a schematic block diagram showing the relative disposition of a camera and a background for implementing the first step of the preferred embodiment;

[0015] FIG. 2 is a schematic block diagram illustrating the second step of the preferred embodiment;

[0016] FIG. 3 is a schematic block diagram depicting the third step of the preferred embodiment;

[0017] FIG. 4 is a schematic block diagram showing the fourth step of the preferred embodiment;

[0018] FIG. 5 is a flow chart showing the overall steps of the present method for pulling a matte of a foreground object using two different background scenes;

[0019] FIG. 6 is a flow chart illustrating the steps used to pull a matte of a foreground object from n different backgrounds;

[0020] FIG. 7A is a color picture of a foreground object (goblet) disposed over a background of pure blue color;

[0021] FIG. 7B is a color picture of the goblet disposed over a background of pure black color;

[0022] FIG. 7C is color picture of an uncomposited image (pulled matte) of the goblet;

[0023] FIG. 7D is a color picture of the pulled matte of the goblet composited over a new background having a plurality of colors;

[0024] FIG. 7E is a color picture of the goblet disposed over a portion of a known background;

[0025] FIG. 7F is a color picture of the portion of the known background without the goblet;

[0026] FIG. 7G is a color picture of the goblet disposed over another portion of the known background;

[0027] FIG. 7H is a color picture of the other portion of the known background without the goblet;

[0028] FIG. 7I is a color picture of an uncomposited image (pulled matte) of the goblet;

[0029] FIG. 7J is a color picture of the pulled matte of the goblet composited over a new background having a plurality of colors;

[0030] FIG. 8A is a color picture of a first background that has a varying color;

[0031] FIG. 8B is a color picture of a second background that has a varying color;

[0032] FIG. 8C is a color picture of foreground objects (goblet and cups that have a blue color) disposed over the first background;

[0033] FIG. 8D is a color picture of foreground objects disposed over the second background;

[0034] FIG. 8E is a color picture of an uncomposited image (pulled matte) of the foreground objects;

[0035] FIG. 8F is a color picture of the pulled matte of the foreground objects composited over a new background having a plurality of colors;

[0036] FIG. 9 is a color picture of a composite image that contains nine sprites, the mattes of which were pulled using the preferred embodiment of the present invention;

[0037] FIG. 10A is graph that represents the red solution space for a point of an image of a foreground object;

[0038] FIG. 10B is a graph that represents the green solution space for the point of the image of the foreground object;

[0039] FIG. 10C is a graph that represents the blue solution space for the point of the image of the foreground object.

[0040] The present invention uses triangulation to determine an alpha (α) channel of a foreground object thereby pulling a matte of the object from a composited image of the object and a background. The preferred embodiment triangulates the images of at least four pictures to determine the α channel, the four pictures being: (1) a picture of a first background; (2) a picture of the foreground object in front of the first background; (3) a picture of a second background; and (4) a picture of the foreground object in front of the second background. Although the preferred embodiment employs only two pairs of images (four pictures) for triangulation, additional pairs of images may optionally be employed in determining the value of the α channel for the foreground object. Significantly, the accuracy of this value for the α channel increases as the number of pairs of images that are triangulated increases.

[0041] Triangulating a foreground object in front of multiple backgrounds is not easily accomplished with live actors or other moving foreground objects, because the distance and direction of the lighting must be substantially identical for each recorded image. Also, the exposure setting for the camera (analog or digital) must be constant for each recorded image. Another important limitation is that the color of pixels of one background must be different from the color of corresponding pixels in the other background(s). However, since the colors of the multiple backgrounds may be any arbitrary color, color impurities in the background will not affect the accuracy of the triangulation process. For example, a first background could be a collage of color swatches and the second background might be a brightly colored landscape, so long as each corresponding pixel has a different arbitrary color. In contrast, the prior art solutions require one specially prepared background that has the same pure or substantially uniform color for each pixel, such as a solid blue color.

[0042] Furthermore, the constant lighting may create a shadow of the foreground object on the background during the recording of a composited image. The preferred embodiment of the present invention includes the shadow of the foreground object as part of the matte that is pulled from the composited image. Thus, the foreground object and its shadow may be disposed over the background of the final composite image.

[0043] Mathematical Model

[0044] As noted above, the present invention allows a matte of a foreground object to be pulled from two or more single film composite images of the object. Unlike a multiple film composite image, a single film composite image does not contain explicit information about the foreground object or the background. A mathematical model is employed that enables the determination of explicit information for each image element that will define an uncomposited image of a foreground object. Note that in the following discussion, the “color of an image” generally refers to the color of each element (pixel or point) in the image, each of which may be different.

[0045] The color of each point in an image is represented by the three primary color coordinates (R, G, B) and an α channel. The color coordinates are assumed to have been premultiplied by the α channel. An important feature of a pre-multiplied α formulation is that the math applied to the three primary color coordinates red, green, and blue (R, G, B) is the same as that applied to the α coordinate. For any image element the notation C_i=[R_iG_iB_iα_i] is used and each of the four coordinates is assumed to be bounded from 0 to 1. If only the color components are required, the notation c_i=[R_iG_iB_i] is used.

[0046] The first modeled image required by this technique is a composited foreground image (i.e., a foreground object against a background) that has a color C_f. The second modeled image required is of the background, which has a color C_k. Furthermore, the foreground image color C_fis a composite of the background color C_k, and a color C_oof an uncomposited foreground object. Since C_ois an uncomposited foreground color, this foreground object, in isolation from any background, is at least partially transparent whenever the background color C_kshows through. The equation C_f=C_o+(1−α_o)C_k(using standard vector algebra) expresses the point-by-point foreground image color as a composite of C_kand C_o. The present invention assumes α_f=α_k=1 for C_fand C_k, i.e., the given foreground image and background image are opaque and rectangular. The notation described above facilitates defining the matting problem solved by the present invention as explained below.

[0047] Given C_fand C_kat corresponding points in two or more composite images, and assuming that C_f=C_o+(1−α_o)C_k, determine C_o.

[0048] The equation for C_fabove, is referred to as the Matting Equation and the uncomposited foreground object color C_o, which is pre-multiplied by the α_ochannel, is a solution to the Matting Problem.

[0049] Uncomposited foreground objects (those with elements or points for which α_o>0 and having the color C_o) are commonly known as sprites in the video industry. Once a solution C_o(including the α_ochannel) is found for each pixel (image element) of the sprite, that sprite can be composited over a new background C_bwith the expression C=C_o+(1−α_o)C_b. Thus, solving the Matting Equation enables the determination of the color C so that a new composite image of the foreground object disposed over the new background may be produced.

[0050] In contrast to the present invention, the prior art only employs one foreground image color, C_f, to calculate the α_ochannel of an uncomposited foreground object. Pulling a matte of a foreground object from a single film image, as typically practiced in a film or video effects house, is intrinsically difficult. In fact, there is an infinity of solutions, which implies that there is no algorithmic method for pulling a matte from a given foreground object. Instead, the prior art employs a human operator and/or image processing software that “knows” a correct matte. The operator is provided with a set of controls usable to “home in” on a matte of the foreground object. Thus, the success of a matting machine in the prior art is determined by the cleverness of its designers in selecting and providing a set of controls that enable the operator to home in on the matte of the foreground object.

[0051] A mathematical proof of the infinity of solutions for pulling a matte from a single film image is as follows. For the red component, R_fis an interpolation from R_kto R_owith a weight α_o, i.e., R_f=R_o+(1−α_o)R_k; similar relations hold for the green and blue components G_fand B_f. A complete solution requires R_o, G_o, B_o, and α_o. There are three equations and four unknowns, which is an incompletely specified problem, and hence, an infinity of solutions exist. This problem is unsolvable without more information. However, there are three solutions for special cases where an answer to the Matting Problem does exist.

[0052] Solution 1: No Blue

[0053] In the prior art, the Matting Problem may be solved when the background is a substantially pure color, such as red, green, or blue, and the foreground object does not include the color of the background.

[0054] If c_ois known to contain no blue, c_o=[R_oG_o0], and c_kcontains only blue, c_k=[0 0 B_k], then

[0055] c_f=c_o+(1−α_o)c_k=[R_oG_o(1−α_o)B_k].

[0056] Thus, solving the B_f=(1−α_o)B_kequation for α_ogives solution $C_o=\left[\begin{array}{cccc}{R}_f& G_f& 0& 1-\frac{B_f}{B_k}\end{array}\right],\mathrm{if}{B}_k\ne 0.$

[0057] This example is exceedingly ideal. The restriction to foreground objects with no blue is quite serious, excluding all grays but black, about two-thirds of all hues, and all pastels or tints of the remaining hues (because white contains blue). Basically, it is only valid for one plane of a three dimensional (3D) RGB colorspace, the RG plane.

[0058] The assumption of a perfectly flat and perfectly blue background color is not realistic. Even very carefully prepared “blue screens” used in cinema special effects as backgrounds have slight spatial brightness variations and also have some red and green impurities (background impurities). A practical solution for brightness variations, in the case of repeatable shots, is to film a pass without the foreground object to produce a record of B_kat each point to be used for computing C_o, after a second pass with the object. Historically, pure blue was arbitrarily chosen as the background color and represents an idealization of customary film and video practice.

[0059] Solution 2: Gray or Flesh

[0060] In the prior art, the matting problem may be solved if the foreground object c_ois known to be gray colored or either R_oor G_oequals B_o. In fact, there is a solution to the matting problem if R_oor G_o=aB_o+bα_o, and if the color of the background c_kis pure blue with aB_k+b≠0. Only the solution C_ois derived below, for the green case, since the solution for red can be derived in a similar fashion:

[0061] The conditions, rewritten in color primary coordinates, are:

[0062] c_f=[R_oaB_o+bα_oB_o+(1−α_o)B_k].

[0063] Eliminate B_ofrom the expressions for G_fand B_fto solve for α_o: $C_o=\left[\begin{array}{cccc}{R}_f& G_f& B_{\Delta }+{\alpha }_o{B}_k& \frac{G_f-{\mathrm{aB}}_{\Delta }}{{\mathrm{aB}}_k+b}\end{array}\right],\mathrm{if}{\mathrm{aB}}_k+b\ne 0.$

[0064] A very useful equation is: C_Δ=C_f−C_k.

[0065] The special case of C_obeing gray colored clearly satisfies Solution 2, with a=1 and b=0 for both R_oand G_o. Thus, it is not surprising that science fiction space movies effectively use the blue screen process because many of the foreground objects are neutrally colored spacecraft. This technique works adequately with desaturated foreground objects having a color tending towards gray, typical of many real-world objects.

[0066] A particularly important foreground element in film and video is flesh, which typically has color [d 0.5d 0.5d]. The flesh tones of all races tend to have the same ratio of primaries, so that the value of d is the darkening or lightening factor. This is a non-gray example satisfying Solution 2, so it is not surprising that the blue screen process also works for the special case in which C_ois flesh colored.

[0067] Solution 3: Triangulation

[0068] The third solution of triangulation is implemented by the present invention and is not employed by any of the prior art techniques. Suppose c_ois known against two different shades of background color. Then, a complete solution exists, as noted below, which does not require any special information about c₀.

[0069] Let B_kand B_kbe two shades of a blue background color, i.e., B_k=cB_kand B_k=dB_kfor 0≦d≦c≦1. Assume c₀is known against these two shades. Also, c_kcan be black, i.e., d=0. Then, there exists a solution C_oto the Matting Problem, as shown below.

[0070] The assumption that c_ois known against two shade of B_kis equivalent to the following:

[0071] c_f=[R_oG_oB_o+(1−α_o)B_k]

[0072] c_f=[R_oG_oB_o+(1−α_o)B_k].

[0073] The expressions for B_fand B_fcan be combined and B_oeliminated to show ${\alpha }_o=1-\frac{B_{f_1}-B_{f_2}}{B_{k_1}-B_{k_2}},$

[0074] where the denominator is not 0 since the two background shades are different. Then $R_o=R_{f_1}=R_{f_2}{G}_o=G_{f_1}=G_{f_2}{B}_o=\frac{B_{f_2}{B}_{k_2}-B_{f_1}{B}_{k_2}}{B_{k_1}-B_{k_2}}$

[0075] completes the solution. In the case of C_kbeing black, C_o=C_ffor C_o=C_f−(1−α_o)C_kbecause C_k=0.

[0076] No commonly used matting technique asks that the foreground object be filmed or imaged against two arbitrarily different backgrounds. For computer controlled shots, it is a possibility, but not usually done. If passes of a computer controlled camera are employed to solve the problem of a non-uniformly colored background mentioned earlier, then the triangulation solution will require four passes. FIGS. 7A-7D illustrate the four passes that must be recorded to eliminate the non-uniformly colored background problem when employing the triangulation solution.

[0077] The shadow of a foreground object is a part of that object to the extent that it is disposed over the background. Also, it is extremely difficult to perform darkening of a background that emits light, without changing the shadow of the foreground object. A solution to the background shadow problem for the special case where the triangulation solution applies requires a more precise method, which is presented below.

[0078] Generalizations of Solution 3 (Triangulation)

[0079] The preceding solutions are all special cases of the generalization obtained by putting the Matting Equation into a matrix form: $C_o\left[\begin{array}{cccc}1& 0& 0& t_1\\ 0& 1& 0& t_2\\ 0& 0& 1& t_3\\ -R_k& -G_k& -B_k& t_4\end{array}\right]=\left[\begin{array}{cccc}{R}_{\Delta }& G_{\Delta }& B_{\Delta }& T\end{array}\right],$

[0080] where a fourth column has been added in two places to convert an underspecified problem into a completely specified problem. Let

[0081] {overscore (t)}=[t₁t₂t₃t₄].

[0082] The matrix equation has a solution C_oif the determinant of the 4×4 matrix is non-zero, or

[0083] t₁R_k+t₂G_k+t₃B_k+t₄={overscore (t)}·C_k≠0.

[0084] Since α_Δ=0 always, standard linear algebra gives the following solution: $\begin{array}{c}{\alpha }_o=\frac{T-\left(t_1{R}_{\Delta }+t_2{G}_{\Delta }+t_3{B}_{\Delta }\right)}{\stackrel{\_}{t}·C_k}\\ =\frac{T-\stackrel{\_}{t}·C_{\Delta }}{\stackrel{\_}{t}·C_k}\\ =1-\frac{\stackrel{\_}{t}·C_f-T}{\stackrel{\_}{t}·C_k}.\end{array}$

[0085] Then c_o=c_Δ+α_oc_k, from the Matting Equation.

[0086] Solutions 1 and 2 are obtained by using the following two options, respectively, for {overscore (t)} and T, where the condition on {overscore (t)}·C_kis given in parentheses:

[0087] {overscore (t)}=[0010]; T=0; (B_k≠0)

[0088] {overscore (t)}=[0−1ab]; T=0; (−G_k+aB_k+b≠0).

[0089] The latter condition reduces to that derived for Solution 2 by the choice of a pure blue background color, i.e., G_k=0. The general result is a theorem for which these solutions are corollaries, specifically:

[0090] Theorem 1. There is a solution C_oto the Matting Problem if there is a linear condition {overscore (t)}·C_o=0 on the color of the uncomposited foreground object, with {overscore (t)}·C_k≠0.

[0091] Proof. T=0 in the matrix equation above gives ${\alpha }_o=1-\frac{\stackrel{\_}{t}·C_f}{\stackrel{\_}{t}·C_k}.$

[0092] Geometrically, Theorem 1 means that all solutions C_olie on a plane, and that C_kdoes not lie on that plane.

[0093] Solution 3 above can also be seen to be a special case of the general matrix formulation with these choices and condition, where by extended definition, C_Δ=C_f−C_k, i=1 or 2:

[0094] {overscore (t)}=[001−B_k]; T=B_Δ; (B_k−B_k≠0),

[0095] with C_k=[0 0 B_k1] and on the right side, the matrix is: [R_fG_fB_ΔB_Δ]

[0096] This solution too is a corollary of a more general one in which C_kis not restricted to a shade of blue.

[0097] Theorem 2. There is a solution C_oto the Matting Problem if the uncomposited foreground object is known against two distinct background colors C_kand Ck_k, where C_kis arbitrary, C_kis a shade of pure blue, and B_k−B_k≠0.

[0098] Proof. This is just the matrix equation above, with {overscore (t)} and T defined as for Solution 3, but with C_kgeneralized to [R_kG_kB_k1] and with the right side of the matrix equation being: [R_ΔG_ΔB_ΔB_Δ]. Thus, as was true for Solution 3, ${\alpha }_o=\frac{B_{{\Delta }_2}-B_{{\Delta }_1}}{B_{k_1}-B_{k_2}}=1-\frac{B_{f_1}-B_{f_2}}{B_{k_1}-B_{k_2}}.$

[0099] The following generalization of Theorem 2 (i.e., Theorem 3) uses all of the C_kbackground color information.

[0100] Theorem 3 (Difference of Sums). Let the sum of the color coordinates of any color C_abe Σ_a=R_a+G_a+B_a. There is a solution C_oto the Matting Problem if the uncomposited foreground object is known against two distinct background colors C_kand C_k, where both are arbitrary and

[0101] Σ_k−Σ_k=(R_k−R_k)+(G_k−G_k)+(B_k−B_k)≠0

[0102] Proof. Change {overscore (t)} and {overscore (T)} in the proof of Theorem 2 to {overscore (t)}=[1 1 1 −Σ_k]; T=Σ_Δ.

[0103] This gives {overscore (t)}·C_o=Σ_o−α_oΣ_k=Σ_f−Σ_k, which is obtained by adding the three primary color equations in the Matting Equation, C_o−α_oC_k=C_Δ. The solution is: $\begin{array}{c}{\alpha }_o=\frac{{\Sigma }_{{\Delta }_1}-{\Sigma }_{{\Delta }_2}}{{\Sigma }_{k_1}-{\Sigma }_{k_2}}\\ =1-\frac{{\Sigma }_{f_1}-{\Sigma }_{f_2}}{{\Sigma }_{k_1}-{\Sigma }_{k_2}}\\ =1-\frac{\left(R_{f_1}-R_{f_2}\right)+\left(G_{f_1}-G_{f_2}\right)+\left(B_{f_1}-B_{f_2}\right)}{\left(R_{k_1}-R_{k_2}\right)+\left(G_{k_1}-G_{k_2}\right)+\left(B_{k_1}-B_{k_2}\right)}\end{array}$  c_o=c_Δ+α_oc_k=c_f−(1−α_o)c_k, or c_o=c_f−(1−α_o)c_k

[0104] The conditions of Theorem 3 are quite broad because only the sums of the primary color coordinates of the two background colors have to differ. In fact, a constant background color is not even required. The difference of the sums technique has been successfully employed to pull a matte on an object against a background of randomly colored pixels and then against that same random background but darkened by 50 percent. FIGS. 8A-8F shows the application of the technique in a realistic case.

[0105] The triangulation problem, with the complete information from the two shots against different background colors, can be expressed by this non-square matrix equation for an over determined system: $C_o\left[\begin{array}{cccccc}1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 1\\ -R_{k_1}& -G_{k_1}& -B_{k_1}& -R_{k_2}& -G_{k_2}& -B_{k_2}\end{array}\right]=\begin{array}{c}\left[\begin{array}{cccccc}-R_{{\Delta }_1}& -G_{{\Delta }_1}& -B_{{\Delta }_1}& -R_{{\Delta }_2}& G_{{\Delta }_2}& B_{{\Delta }_2}\end{array}\right].\end{array}$  [R_ΔG_ΔB_ΔR_ΔG_ΔB_Δ].

[0106] The Theorem 3 form is obtained by adding the last three columns of the matrix and the last three elements of the vector.

[0107] The standard least squares way to solve this is to multiply both sides of the equation by the transpose of the matrix yielding: $C_o\left[\begin{array}{cccc}2& 0& 0& -\left(R_{k_1}+R_{k_2}\right)\\ 0& 2& 0& -\left(G_{k_1}+G_{k_2}\right)\\ 0& 0& 2& -\left(B_{k_1}+B_{k_2}\right)\\ -\left(R_{k_1}+R_{k_2}\right)& -\left(G_{k_1}+G_{k_2}\right)& -\left(B_{k_1}+B_{k_2}\right)& \Lambda \end{array}\right]=\begin{array}{c}\left[\begin{array}{cccc}{R}_{{\Delta }_1}+R_{{\Delta }_1}& G_{{\Delta }_1}+G_{{\Delta }_2}& B_{{\Delta }_1}+B_{{\Delta }_2}& \Gamma \end{array}\right]\end{array}$ $\mathrm{where}\Lambda =R_{k_1}^2+G_{k_1}^2+B_{k_1}^2+R_{k_2}^2+G_{k_2}^2+B_{k_2}^2\mathrm{and}\Gamma =-\left(R_{k_1}{R}_{{\Delta }_1}+G_{k_1}{G}_{{\Delta }_1}+B_{k_1}{B}_{{\Delta }_1}+R_{k_2}{R}_{{\Delta }_2}+G_{k_2}{G}_{{\Delta }_2}+B_{k_2}{B}_{{\Delta }_2}\right)$  [R_Δ+R_ΔG_Δ+G_ΔB_Δ+B_ΔΓ]

[0108] where

[0109] Λ=R_k²+G_k²+B_k²+R_k²+G_k²+B_k²

[0110] and

[0111] Γ=−(R_kR_Δ+G_kG_Δ+B_kB_Δ+R_kR_Δ+G_kG_Δ+B_kB_Δ)

[0112] Inverting the symmetric matrix and multiplying both sides by the inverse gives a least squares solution C_oif the determinant of the matrix, 4((R_k−R_k)²+(G_k−G_k)²+(B_k−B_k)²), is non-zero. Thus, the most powerful result is obtained in Theorem 4.

[0113] Theorem 4 (Least squares). There is a solution C_oto the Matting Problem if the uncomposited foreground object is known against two arbitrary background colors C_kand C_kwith non-zero distance between them: (R_k−R_k)²+(G_k−G_k)²+(B_k−B_k)²≠0 (i.e., they are distinct).

[0114] The desired alpha channel α_ocan be shown to be: ${\alpha }_o=1-\frac{\begin{array}{c}\left(R_{f_1}-R_{f_2}\right)\left(R_{k_1}-R_{k_2}\right)+\left(G_{f_1}-G_{f_2}\right)\left(G_{k_1}-G_{k_2}\right)+\\ \left(B_{f_1}-B_{f_2}\right)\left(B_{k_1}-B_{k_2}\right)\end{array}}{{\left(R_{k_1}-R_{k_2}\right)}^2+{\left(G_{k_1}-G_{k_2}\right)}^2+{\left(B_{k_1}-B_{k_2}\right)}^2}.$

[0115] The expressions of Theorems 3 and 4 for α_oare symmetric with respect to the two backgrounds, reflected in the two expressions for c_o(in the proof of Theorem 3).

[0116] Theorems 2 and 3 are really just special cases of Theorem 4. For Theorem 2, the two colors are required to have different blue coordinates. For Theorem 3, (difference of the sums solution) corresponding points in each image have two arbitrary colors that do not have the same summed (Σ) value for the coordinates associated with each point. In practice, it has been observed that the simpler conditions of Theorem 3 often hold and permit use of computations less rigorous than those required for Theorem 4.

[0117] Theorem 4, the least squares solution, allows the use of very general backgrounds. In fact, two images of a foreground object moving across a fixed but varied background can satisfy Theorem 4, as shown in FIGS. 7E-7J. If the foreground object can be registered frame to frame as it moves from one side to the other, then the background relative to two different positions of the object can serve as the two backgrounds.

[0118] Notice that the Theorem 3 and 4 techniques lead to a background shadows solution whereas simple darkening of the background might not deal with shadows properly. As discussed above, the illumination levels and the direction of the lighting must be the same for the two backgrounds so that the shadows are the same densities and directions. The over determined linear system described above summarizes all information about two images of the foreground object against two different background colors. A third image of the foreground object against a third background color could be included as well, replacing the 4×6 matrix with a 4×9 matrix and the 1×6 right-hand vector with a 1×9 vector. Then the same least squares technique would be applied to find a solution for this even more over determined problem. Similarly, a fourth, fifth, etc. image of the foreground object against even more backgrounds of different colors could be used. Although an over determined system may be subject to numerical instabilities in its solution, in reducing the present invention to practice none were experienced. If numerical instabilities did arise, a technique of singular value decomposition may be used such as that disclosed in Numerical Recipes in C, PRESS, W. H., TEUKOLOSKY, S. A., VETTERLING, W. T., and FLANNERY, B. P., Cambridge University Press, Cambridge, 1988, p. 59.

[0119] Theorem 5—General Matting Case with n Backing Colors. There is a solution C_oto the Matting Problem if the uncomposited foreground object is known against n arbitrary background colors C_k, C_k, . . . , C_k, where:

[0120] nΣ(R_k²+G_k²+B_k²)−(Σ²R_k+Σ²G_k+Σ²B_k)≠0

[0121] All sums are taken over i from 1 to n, and the sum squared symbol Σ²means to take the sum over all i, as usual, then square the result.

[0122] It can be shown that this condition is equivalent to: “The sum of all possible pairwise color distances (squared) is non-zero,” which is equivalent to: “At least two of the C_kmust be distinct,” which is a relatively “loose” condition.

[0123] The alpha value for the Theorem 5 least squares technique can be shown to be: ${\alpha }_0=1-\frac{\begin{array}{c}n\sum \left(R_{f_i}{R}_{k_i}+G_{f_i}{G}_{k_i}+B_{f_i}{B}_{k_i}\right)-\\ \left(\sum R_{f_i}\sum R_{k_i}+\sum G_{f_i}\sum G_{k_i}+\sum B_{f_i}\sum B_{k_i}\right)\end{array}}{n\sum \left(R_{k_i}^2+G_{k_i}^2+B_{k_i}^2\right)-\left(\sum {}^{2}R_{k_i}+\sum {}^{2}G_{k_i}+\sum {}^{2}B_{k_k}\right)}$

[0124] These results are readily derived using the same least squares and linear algebra techniques as used for the case n=2 in Theorem 4. This alpha can also be shown to be equivalent to: ${\alpha }_0=1-\frac{\begin{array}{c}\sum _{j<i}[\left(R_{f_i}-R_{f_j}\right)\left(R_{k_i}-R_{k_j}\right)+\\ \left(G_{f_i}-G_{f_j}\right)\left(G_{k_i}-G_{k_j}\right)+\left(B_{f_i}-B_{f_j}\right)\left(B_{k_i}-B_{k_j}\right)]\end{array}}{\sum _{j<i}{\left(R_{k_i}-R_{k_j}\right)}^2+{\left(G_{k_i}-G_{k_j}\right)}^2+{\left(B_{k_i}-B_{k_j}\right)}^2}$

[0125] Here the sums are taken over all i from 1 to n and over all j from 1 to i−1. So this form is in terms of color differences as in the statement and solution of Theorem 4. Notice that the denominator of the preceding equation is the sum of the Euclidean distances (squared) between all possible color pairs.

[0126] Bounding the Value of the Alpha Channel

[0127] It might seem that the problems, which have Solutions 1 and 2, and Theorem 1 generalizations, are unrealistically restrictive of foreground object colors. However, much of the real-world work approaches the conditions of these solutions and generalization. Situations arising from Solution 3, and Theorems 2-4 generalizations, require a doubling of recorded images, which may be difficult to achieve. If the search space of possible solutions for deriving α_oin the general single-background case is bounded, Solutions 1 and 2, and Theorem 1 may be implemented when the premises are less than ideal.

[0128] Any C_ooffered as solution must satisfy the physical limits on color. It must be that for a color component red, 0≦R_o≦α_o(since R_ois premultiplied by α_o). Similar relationships are true of the green and blue components, G_oand B_o. The Matting Equation gives R_f=R_o+(1−α_o)R_k. The inequalities for R_oapplied to this expression give:

[0129] (1−α_o)R_k≦R_f≦(1−α_o)R_k+α_o,

[0130] with the left side being the expression for R_o=0 and the right for R_o=α_o. Similar inequalities apply to G_fand B_f.

[0131] For a given C_o, FIG. 10A is the red color space, FIG. 10B is the green color space, and FIG. 10C is the blue color space. FIGS. 10A-10C show all regions of valid combinations of α_o, R_f, G_f, and B_fusing equality in the relationship(s) above as boundaries. The color c_kfor FIGS. 10A-10C is taken to be the slightly impure blue [0.1 0.2 0.98].

[0132] The dashed vertical lines in FIGS. 10A-10C represent a given c_fin this figure, [0.8 0.5 0.6]. The dotted horizontal lines represent the minimum α_ofor each of R_f, G_f, and B_f, which gives valid results for R_o, G_o, and B_o, respectively. Let these three α_o's be α_R, α_G, and α_B. Since only one α_ois generated per color, the following relationship must be true:

[0133] α_o≧max(α_R, α_G, α_B).

[0134] The α_othat satisfies this relationship at equality α_min, and for any α_o≧α_minwill be a valid one. Notice that although the range of possible α_o's is reduced by this derivation, there are still an infinity of valid ones to choose from, and hence, an infinity of solutions.

[0135] If R_f>R_k, as in the example of FIG. 10A, then α_Rcorresponds to R_o=α_o, on the right side of the inequalities noted above for R_fand α_o. If R_f<R_kthen α_Rcorresponds to R_o=0, on the left side of these inequalities. Thus, ${\alpha }_R=\{\begin{array}{c}1-\frac{R_f}{R_k},\mathrm{if}{R}_f<R_k\\ \frac{R_{\Delta }}{1-R_k},\mathrm{if}{R}_f>R_k\\ 0,\mathrm{if}{R}_f=R_k\end{array}$

[0136] In the example of FIGS. 10A-10C, α_min≈0.78. For the special case of pure blue background, α_min=max(R_f, G_f, 1−B_f). So long as a valid α_oexists, a foreground object color can be derived from the given c_fby c_o=c_Δ+α_oc_kas before.

[0137] An upper bound may also be established for α_oby extending the assumption presented in U.S. Pat. No. 4,100,569 (Vlahos).

[0138] The Vlahos assumption, when valid, has B_o≦a₂G_o. The rearrangement of the Matting Equation above for the green channel is then:

[0139] G_o=G_f−(1−α_o)G_k.

[0140] Another rearrangement, this time for the blue channel, gives: ${\alpha }_o=1+\frac{B_o-B_f}{B_k}\le 1+\frac{a_2{G}_o-B_j}{B_k}.$

[0141] Combining these two relationships, by substituting the equation for G_ointo the inequality for α_oand solving, gives: ${\alpha }_o\le 1-\frac{B_f-a_2{G}_f}{B_k-a_2{G}_k},$

[0142] clamped to [0, 1] if necessary. Recall that 0.5≦a₂≦1.5 typically. Let α_oat equality be α_max. Then, in the example of FIGS. 10A-10C, a₂=1 yields α_max≈0.87, which constrains the possible solutions a bit more so that: 0.78≦α_o≦0.87.

[0143] Bounding the upper and lower possible values for α_overifies the determined value provided by the solutions discussed above. Also, the mathematical computations employed to derive the value of α_omay be reduced when the solution space is bounded.

[0144] Implementation of Triangulation

[0145] With reference to FIG. 1, apparatus 100 for implementing a first step of the preferred embodiment for triangulating single film images having two different backgrounds is shown. A camera 102 is disposed a predefined distance x1 from a first background 110. If camera 102 is digital, it will preferably be coupled to a computer 104 so that a digital image recorded by the camera is directly inputted to the computer. Alternatively, the digital image may be stored on memory media and later transferred into computer 104. However, if camera 102 is an analog device, a recorded analog image will be provided to a digitizer 116 for scanning. Once the analog image is processed by the digitizer, a corresponding digital image will be supplied to computer 104. A display 106 is coupled to computer 104 so that received and processed images may be viewed by a user. A stationary light source 108 provides a constant light that is incident upon a first background 110, which is shown positioned directly in front of a second background 112. An image or picture of first background 110 is recorded by camera 102. (Note that in this disclosure and the claims that follow, the term “picture” is considered synonymous with the noun “image.”)

[0146] Moving now to a FIG. 2, a second arrangement 100 of the apparatus is shown. An object 114 is positioned in the region between camera 102 and first background 110 and disposed at a distance x3 from camera 102 and at a distance x2 from the surface of first background 110. Light source 108 provides a constant light that illuminates object 114 and first background 110 in the same manner as when recording the image of only the first background (FIG. 1). An image of object 114 and first background 110 is recorded by camera 102.

[0147] In FIG. 3, a third step of the preferred embodiment for triangulating single film images having two different backgrounds is shown relative to an apparatus 100′. Relative to FIG. 2, first background 110 has been removed, and object 114 is now disposed between camera 102 and second background 112. Distance x1′ between camera 102 and second background 112 is approximately equal to the distance x1 between camera 102 and first background 110 in FIG. 2. Further, a distance x2′ between the front surface of object 114 and second background 112 approximately equals the distance x2 between object 114 and first background 110 as shown in FIG. 2. Typically, the thickness of first background 110 is so small that any differences in the distances x1 and x1′, or x2 and x2′ are insignificant. Light source 108 illuminates object 114 and second background 112 in the same manner as when recording the image of first background 110 and object 114. An image of object 114 and second background 110 is thus recorded by camera 102.

[0148] FIG. 4 shows a fourth step of the preferred embodiment for triangulating single film images having two different backgrounds. Object 114 has been removed from the position between camera 102 and second background 112 as shown in FIG. 3. The distance x1′ between camera 102 and second background 112 remains approximately equal to the distance x1 between camera 102 and first background 110 as depicted in FIG. 2. Light source 108 illuminates second background 112 in the same manner as when recording the image of second background 112 and object 114. An image of second background 110 is recorded by camera 102.

[0149] At each step in the preferred embodiment for triangulating single film images, an image recorded by camera 102 is provided to computer 104 so that two pairs of images, one with and one without object 114, are recorded against two different backgrounds.

[0150] In FIG. 5, a flow chart depicts an overview 200 of the steps of the preferred embodiment for pulling a matte of object 114 by triangulating two pairs of single film images having two different backgrounds, as depicted in FIGS. 1-4. A block 202 provides for recording an image of the first background. In a block 204, an image is recorded of object 114 disposed in front of first background 110. Next, in a block 206, an image is recorded of object 114 disposed in front of second background 112. In a block 208, an image is recorded of second background 112 alone. A decision block 210 provides for determining whether the four images were digitally recorded. If not, the procedure advances to a block 212, which the four images are converted into a digital format that is recognizable by computer 104. The computer corrects any misalignment of the four digitized images by registering each pixel within each image with each corresponding pixel in each of the other images as noted in a block 214. A block 216 indicates that a matte of the object is pulled from the four digitized images by employing an appropriate triangulation solution. Additionally, block 216 is implemented if the determination at block 210 is true. The pulled matte of object 114 may then be employed to produce a new composite image.

[0151] The triangulation of the recorded images may employ at least two different techniques to pull a matte of object 114. As discussed above, Theorem 3 (difference of the sums) may be used if the sums of each color coordinate for each pixel in the image of the first background minus the sums of each color coordinate of each corresponding pixel in the image of the second background do not equal zero. Alternatively, Theorem 4 (least squares) may be employed if the colors of the backgrounds are different, i.e., the sum of the squares of the differences between each color coordinate for each pixel in the image of the first background and each color coordinate of each corresponding pixel in the second background do not equal zero. Theorem 3 is less computationally intensive than Theorem 4. However, Theorem 4 may be more accurate in determining a value for the alpha channel of the image of object 114 than Theorem 3 if more than two pairs of images having different backgrounds are employed to pull a matte of the object.

[0152] Looking now to FIG. 6, a functional block diagram shows a generalized overview 200′ of the steps for pulling a matte of object 114 by triangulating n pairs of single film images having n different backgrounds. A block 220 notes that the value n is initially set to zero. In a block 222, a variable (nmax) is initialized with an integer value equal to or greater than two, corresponding to the number n of the different backgrounds that will be recorded. In a block 224, the value of n is incremented by one. A block 226 provides for recording an image of a background n. Next, in a block 228, an image of a foreground object disposed in front of a background n is recorded. A determination is made whether the value of n is equal to the value of nmax in a decision block 230. If not, the procedure advances to a block 232 in which the value of n is incremented by one. Stepping to a block 234, an image of the foreground object disposed over a new background n (as incremented) is recorded. In a block 236, an image is recorded of the new background alone. Moving to a decision block 238, a determination is made whether the value of n is equal to nmax. If not, returning to block 224, the procedure recursively implements the steps described above.

[0153] Once the determination at decision block 238 is true or if the determination at decision block 230 is true, the procedure continues with a decision block 240. Decision block 240 determines whether the recorded images are digital or analog. If the recorded images are analog images, a block 242 provides for converting each analog image into an image that has a digital format recognizable by the computer.

[0154] Any misalignment of the four digitized images is corrected in a block 244 by registering each pixel within each image with each corresponding pixel of each of the other images. This step is extremely important for analog images because the movement of film and resulting variation is the plane of the film within a camera can cause misalignment of sequentially recorded images. Moving to a block 246, a matte of the foreground object is pulled from the digitized images by triangulating the corresponding pixels of the single film images having n different backgrounds. Block 246 is also implemented if the determination at decision block 240 is true. As discussed above, at least two different techniques (Theorem 3 and Theorem 4) may be used to triangulate corresponding pixels. The pulled matte of the foreground object may then be employed to produce a new composite image.

[0155] The color images presented in FIGS. 7A-7D fit the criteria of Theorem 2 (actually the Solution 3 special case) perfectly because the given blue foreground (FIG. 7A) and black (FIG. 7B) foreground images were manufactured by compositing the foreground object over perfectly pure blue and black backgrounds, respectively. As predicted by Theorem 2, the foreground object was extracted in its original form (FIG. 7C), with only small least significant bit errors being visible in the new composite image (FIG. 7D). Similarly, FIGS. 7E-7J illustrate the successful implementation of the preferred embodiment with a rigidly moving foreground object disposed over an arbitrarily colored background.

[0156] FIGS. 8A-8D provide a set of color images (film) of foreground objects disposed over two different backgrounds, and the two backgrounds alone. Each background has a predominate color that varies across its breadth. FIG. 8E is the pulled matte of the foreground objects, and FIG. 8F is a new composite image of the objects. The camera was locked down for recording the two images (FIGS. 8C-8D) required by Theorem 3 (sum of differences) and Theorem 4 (least squares) and the two extra images (FIGS. 8A-8B), which are necessary for calibrating the color of the images of the two backgrounds as discussed above. Furthermore, the same exposure and illumination was used for recording the four images, and a remote-controlled shutter guarded against slight camera movements.

[0157] The resulting image of FIG. 8F demonstrates the effectiveness of the preferred embodiment, but it is nevertheless flawed due to misregistration introduced during the filming process. A primary source of the misregistration may be caused by the slight misalignment of the film in the camera as sequential exposures (images) are recorded. If pin registration had been employed in the filming and digitization (scanning) of the film images, the misregistration in FIG. 8F would have been corrected. Additionally, the foreground objects in front of different backgrounds have a slightly different brightness, relative to one another, which is an artifact caused by scanning.

[0158] FIG. 9 is a composite image of nine sprites. The matte for each sprite was pulled with the preferred embodiment of the present invention i.e., recording an image of each foreground object over two different backgrounds and triangulating the color values of the images to pull the matte.

[0159] It is important to note from the Theorem 3 and 4 expressions for α_othat both triangulation techniques are quite sensitive to brightness and misregistration errors. If the foreground colors differ where they should be equal, then α_ois decreased from its correct value of 1, permitting some object transparency. In general, the triangulation techniques tend to err towards increased transparency.

[0160] Another manifestation of misregistration error is called the “fine line” problem. Consider a thin dark line with bright surroundings in a foreground image recorded against one background, or the complement, a thin bright line in dark surroundings. Such a line in slight misregistration with itself against the other background may differ dramatically in brightness at the pixels along the line, and will be seen by the triangulation solution. Since misregistration error tends toward transparency, the error will cause the appearance of a fine transparent line in a pulled matte of a foreground object. Thus, effective use of the preferred embodiment implies that pin-registered filming and digitization or a digital camera should be employed to ensure positional constancy between the four filmed images. Additionally, the lighting of the foreground object and the camera exposure should be precisely controlled so that a constant brightness for each foreground object is provided during the recording of the images on a film strip (or other recording medium).

[0161] Since the preferred embodiment is intended to work with non-moving objects (excluding rigid motions, such as simple translation), brightness variations and other sources of noise may be reduced by averaging the values of several repeatedly recorded images at each step of the recording process. Rigidly moving an object includes rotating and linearly displacing the object so that a constant distance is maintained between the object and the camera during the recording of multiple images. Further, a digital camera may be employed to record the images so that scanning artifacts are eliminated, and so that the frequency with which recorded images are misregistered is reduced.

[0162] Although the present invention has been described in connection with the preferred form of practicing it, those of ordinary skill in the art will understand that many modifications can be made thereto within the scope of the claims that follow. Accordingly, it is not intended that the scope of the invention in any way be limited by the above description, but instead be determined entirely by reference to the claims that follow.