Method of image background replacement

[0001] 1. Field of the Invention

[0002] This invention relates to image processing for image capture systems, more particularly to replacing backgrounds in captured images.

[0003] 2. Background of the Invention

[0004] New applications for video technology are appearing every day. Video conferencing has become commonplace, users can easily download video clips from the Internet, and camcorders are inexpensive and widely used. As more of these applications develop, the ability to edit and change the nature of the images becomes more important.

[0005] One editing tool that remains unavailable to most of these applications is background replacement. Typically, background replacement occurs on video images filmed in front of a blue screen. The foreground and background pixels are easily identified and the new background is put in place using computers or specially designed video devices. However, for most people, filming or capturing images in front of a blue screen is impractical.

[0006] The blue screen process is expensive and inconvenient. A special studio for video conferencing restricts the availability of video conferencing facilities and requires extra cost. Most people publishing on the Internet would find use of a blue screen prohibitive, as would most typical users of camcorders. However, all of these applications can benefit from background replacement. People video conferencing could replace the background of their office with a background for reasons of privacy, security or aesthetics. Internet publishers could insert images into Web pages more seamlessly, without use of backgrounds or sets. Camcorder users could record videos and edit the backgrounds at home.

[0007] Therefore, a less expensive and more easily accessible technique for background replacement is needed.

[0008] One embodiment of the invention is a technique for background replacement. The input image or images are analyzed and a preliminary classification of the pixels is made. The classification identifies whether the pixels are more likely foreground or background. After the preliminary classification is made, a more refined process is applied that makes the final determination. Finally, the new background pixels are applied to the image, replacing the previous background pixels. The new image is composed with feathering to ensure smooth edges and transitions. The new image is then output for viewing.

[0009] It is an advantage of the invention in that it allows background replacement with no extra equipment or special settings.

[0010] It is an advantage of the invention in that it provides background replacement quickly, allowing real-time processing.

[0011] It is an advantage of the invention in that it is able to adjust for camera exposure changes and accurate in determining background pixels from foreground pixels.

[0014] One embodiment of a process for video background replacement is shown in FIG. 1. An input device in 10 is used to capture images. Devices such as these include digital cameras, camcorders, film cameras, video conferencing cameras, etc. In step 10 the current background is recorded without any foreground object or objects.

[0015] The device 10 then takes incoming frames or an incoming frame of the image with the foreground objects as the input image in step 12. For digital cameras, the input image would be that one image captured by the image input device. The input devices that are video images may capture one or more frames to use as the input image or in the input image analysis.

[0016] The input image is then analyzed using a probability function that measures the likelihood of the pixel being foreground or background. One example of such a probability function is: $P\left(p_{x,y}\in \mathrm{Foreground}\right)=\{\begin{array}{cc}\Phi \left(a·\sqrt{{\left(r_{x,y}-r_{x,y}^{\prime }\right)}^2+{\left(g_{x,y}-g_{x,y}^{\prime }\right)}^2}+b·I_{x,y}-I_{x,y}^{\prime }+c\right)& \mathrm{if}{I}_{x,y}>\eta \\ \Phi \left(d·I_{x,y}-I_{x,y}^{\prime }+f\right)& \mathrm{else}\end{array}$
and
Φ(u)=min(max(0.5+sign(u)·u²,0),1)
where r and g are the chromatic components and l is the intensity of the pixel p; r′, g′ and l′ are their counter parts of pixel p′ in the pre-recorded background image, and a, b, c, d, f, and η are constants. The values of these constants are tuned by experiments to determine their optimal values.

[0017] It is not necessary to restrict this process to chromatic or normalized RGB color space. Use of YC_bC_r is also possible. In the YC_bC_r example, the same formulas would be used, with the substitutions of Y for l, C_b for g and C_r for r.

[0018] Regardless of the color space used for determining the preliminary classification of a pixel, a probability map is generated that indicates the likelihood of a pixel being foreground or background. The probability map produces a value of a pixel between 0 and 1, where 0 is the foreground and 1 is the background in this particular example. These probabilities could have a threshold applied that would segment the pixels into either the foreground or background. However, this may lead to false classifications because of ambiguity in certain regions in foreground objects and the background.

[0019] Therefore, it is desirable to refine the classification result by utilizing certain context information in space. One may apply morphological filtering to eliminate isolated mis-classified pixels. Other techniques are also available for this post-processing refinement in step 16. One such technique is anisotropic diffusion, which is discussed below.

[0020] Anisotropic diffusion encourages smoothing within boundaries and discourages smoothing across boundaries. In this example, the following anisotropic diffusion equation will be used:
P_t=div(c(x,y,t)∇P)=c(x,y,t)ΔP+∇c·∇P,
where div denotes the divergence operator, and ∇ and Δ denote the gradient and Laplacian operators, respectively, with respect to the space variables. The continuous diffusion equation may be discretized on a square lattice. Using a 4-nearest-neighbors discretization of the Laplacian operator, the equation becomes:
P_x,y^t+1=P_x,y^t+λ[c_N·∇_NP+c_S·∇_SP+c_E·∇_EP+c_W·∇_WP]_x,y^t
and
∇_NP_x,y=P_x,y−1−P_x,y
∇_SP_x,y=P_x,y+1−P_x,y
∇_EP_x,y=P_x+1,y−P_x,y
∇_WP_x,y=P_x−1,y−P_x,y
where 0≦λ≦¼ for numeric stability reason, N, S, E, W denote North, South, East and West, respectively. The conduction coefficients c_N, c_S, c_E, c_W may be computed as follows:
c_Nx,y=g(|∇_NI_x,y|)
c_Sx,y=g(|∇_SI_x,y|)
c_Ex,y=g(|∇_EI_x,y|)
c_Wx,y=g(|∇_WI_x,y|)

[0021]
and $g\left(\nabla I\right)-\frac{1}{1+{\left(\nabla I/K\right)}^2}$

where K is a constant, e.g., K=1000.

[0022] This refined probability map from step 16 is then used to overlay foreground pixels on a new background. Some type of blending or feathering process should be used. Feathering as used here denotes any kind of process that does not just overlay the pixels with no comparison whatsoever between the foreground and background. Specifically, in this example, a weighted average over the pixel value of the input image and the pixel value of the new background is applied. The weights are determined by the probability value from the probability map.

[0023] The example of this feathering algorithm for a given location (x,y) in the output image, has the following formulas:
R_x,y^output=P(p_x,y∈Foreground)·R_x,y^input+(1−P(p_x,y∈Foreground))·R_x,y^{new background}
G_x,y^output=P(p_x,y∈Foreground)·G_x,y^input+(1−P(p_x,y∈Foreground))·G_x,y^{new background}
B_x,y^output=P(p_x,y∈Foreground)·B_x,y^input+(1−P(p_x,y∈Foreground))·B_x,y^{new background}

[0024] Once the feathering is complete in step 18, the output image with the new background is produced. While the input may be a video image, this technique can be used for printed output as well, such as paper, postcards, photographic paper, etc.

[0025] Several modifications of this process are possible. As mentioned previously, the above example relies upon RGB color space for discussion purposes. Other types of processing, including YC_bC_r, can be used. The selection of the number of frames used is also left up to the designer. It is possible that several frames could be analyzed with associated motion analysis as well, to ensure the highest accuracy of the fore/back ground classification. The use of the nearest neighbor is not limited to four neighbors. The selection of these specifics is left to the designer based upon the computational power of the system and the requirements of the final image.

[0026] Similarly, while the above process relies upon anisotropic diffusion for the refinement of classification, other types of refinements are available, such as morphological filtering, as mentioned above.

[0027] Application of this invention results in several options for users. A video conference participant can shield the actual background of the room from those at the receiving end of the image, for privacy or security reasons.

[0028] A Web publisher can generate transparent images in GIF format much more quickly than presently possible. Current techniques involve a pixel by pixel designation by the user to identify foreground and background pixels, a painstaking and tedious process. These same techniques are required when consumers using digital cameras want to crop and move objects in their digital images, whether video or still. These problems are eliminated by the application of this invention.

[0029] Thus, although there has been described to this point a particular embodiment for a method to perform background replacement, it is not intended that such specific references be considered as limitations upon the scope of this invention except in-so-far as set forth in the following claims.