Method and apparatus for real-time matting using local color estimation and propagation

Embodiments of the present invention provide systems, methods, and computer storage media directed to operations to facilitate real-time matting using local color estimation and propagation. In accordance with embodiments described herein, an unknown region is estimated based on a set of received boundary points (a zero-level contour that separates the foreground object from the background) and additional contours based on increasing distances from the zero-level contour. The background and foreground colors for each pixel in the unknown region can be estimated and utilized to propagate the foreground and background colors to the appropriate contours in the unknown region. The estimated background and foreground colors may also be utilized to determine the opacity and true background and foreground colors for each pixel in the unknown region which results in an image matted in real-time.

BACKGROUND

Accurately separating a foreground image from background image requires estimating full and partial pixel coverage, a process referred to as matting. Matting is often used to separate a foreground image (such as a person) from a background image (such as a particular setting). This process can be difficult because pixels in an unknown region (the area around the boundary of a foreground object and the background in an image) are a blend of foreground and background colors. Estimating the opacity and true background and foreground colors in the unknown region to give the combined image a smooth and blended appearance is the goal of matting.

Studio quality matting can be achieved in a professional studio (e.g., a Hollywood movie set) utilizing a very large, single-colored background screen. The background can be any color that is uniform and distinct, but green and blue backgrounds are most commonly used. The actor or person being filmed in front of the screen cannot wear clothing that is similar in color to the screen or the matting process may not work properly. Unfortunately, such a large, single-colored background screen is impractical for a home studio (or any user that lacks the professional skills and resources typical in a professional studio). Further, when a foreground is against a solid colored background (e.g., a green screen), the light being reflected from the background can contaminate the foreground, creating a “halo” of the background colors along the edges of the foreground. The process of despillling refers to removing the artifacts from the foreground by estimating the true foreground color for the pixels.

SUMMARY

Embodiments of the present invention relate to facilitating real-time matting using local color estimation and propagation. As described in embodiments herein, an unknown region is estimated based on a set of received boundary points (a zero-level contour that separates the foreground object from the background) and additional contours based on increasing distances from the zero-level contour. Pixels inside the unknown region are often a blend of both foreground and background colors (for example, thin strands of hair). By applying the technique described herein, the background and foreground colors for each pixel in the unknown region can be estimated and utilized to propagate the foreground and background colors to the appropriate contours in the unknown region. The estimated background and foreground colors may also be utilized to determine the opacity and true background and foreground colors for each pixel in the unknown region which results in an image matted in real-time.

DETAILED DESCRIPTION

Embodiments of the present invention relate to facilitating real-time matting using local color estimation and propagation. In particular, embodiments of the present invention enable an ordinary user (e.g., a person utilizing a computing device without the need for sophisticated studio quality equipment or a green screen) to blend various image elements (e.g., a foreground of an image with different backgrounds) in real-time and in high quality. Because pixels along a region where the background meets the foreground (i.e., the unknown region) are often a blend of both foreground and background colors (for example, thin strands of hair), the technique described herein enables the background and foreground colors for each pixel in the unknown region to be estimated. These estimated background and foreground colors can be utilized to propagate the foreground and background colors to the appropriate contours in the unknown region. The estimated background and foreground colors may also be utilized to determine the opacity and true background and foreground colors for each pixel in the unknown region which results in an image with combined foreground and background elements blended or matted in real-time. Consequently, a user in a home-studio, without the benefit of a sophisticated studio quality equipment or a green screen can, in real-time, create images or videos that replaces the background with a desired background. In this way, the user may create a high-quality image or video having a particular foreground subject combined with any background the user desires. For example, the user can create videos that include the user speaking in front of a national monument, at the beach, in the mountains, near famous people, and the like.

To do so, at a high level, an unknown region (the area between a foreground object and the background in an image) is initially estimated based on a set of received boundary points (a zero-level contour that separates the foreground object from the background). Background and foreground contours (of the zero-level contour) are generated based on a contour traversal of increasing distances from the set of boundary points. Using local samples taken from the neighboring pixels in the outermost background contours, the true background colors can be estimated for each of the pixels in the outermost contour. Similarly, using the neighboring pixels in the innermost foreground contours, true foreground colors can be estimated for each of the pixels in the innermost contour. Each of the true background colors and the true foreground colors are propagated to the unknown region to estimate the background and foreground colors for all pixels in the unknown region. These estimates ultimately produce the matte for the image in real-time.

Among other components not shown, the environment100may include user device(s)112A-112N, camera114, database116, and matting and despilling engine118. It should be understood that the environment100shown inFIG. 1is an example of one suitable computing system environment. Each of the components shown inFIG. 1may be implemented via any type of computing device, such as computing device1900described with reference toFIG. 19, for example. The components may communicate with each other via a network110, which may include, without limitation, one or more local area networks (LANs) and/or wide area networks (WANs). Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet.

It should be understood that any number of user devices, cameras, databases, and matting and despilling engines may be employed within the computing environment100within the scope of the present invention. Each may comprise a single device or multiple devices cooperating in a distributed environment. For instance, the matting and despilling engine118may be provided via multiple devices arranged in a distributed environment that collectively provide the functionality described herein. Additionally, other components not shown may also be included within the network environment.

The user device(s)112A-112N may be any type of device suitable for facilitating real-time matting of an image. Such computing devices may include, without limitation, a computer such as computing device1900described below with reference toFIG. 19. For instance, the user device112may be a desktop computer, a laptop computer, a tablet computer, a mobile device, or any other device having network access. As shown, the user device(s)112A-112N can include a display screen configured to display information to the user of the user device(s)112A-112N, for instance, information relevant to facilitating real-time matting of an image.

Generally, a user may employ the user device(s)112A-112N to communicate with camera114, database116, and/or matting and despilling engine118and initiate real-time matting of an image. The image may be captured by camera114, user device(s)112A-112N, or stored by user device(s)112A-112N or database116. Components of the matting and despilling engine118can be in any form being executed on the user device(s)112A-112N. For instance, the matting and despilling engine118can operate by way of a web browser executing on user device(s)112A-112N or as an application, or portion thereof, being executed on the user device(s)112A-112N.

The camera114may be any type of device capable of capturing images or video. Although the camera is depicted inFIG. 1as a separate device, it is contemplated each of the user device(s)112A-112N may include a camera. Further, although the camera is depicted in communication with each of the components inFIG. 1via network110, it is contemplated that the images or video may be communicated directly to user device(s)112A-112N rather than via network110. As described in more detail below, images or video captured by the camera114may be matted in real-time by matting and despilling engine118.

The database116may be any type of server device capable of hosting one or more images, videos, and the like, and serving the one or more images, videos, and the like, to computing devices, such as the user device11user device(s)112A-112N or matting and despilling engine118. By way of example, and not limitation, the database116may be a server maintaining one or more backgrounds that a user can combine with one or more foregrounds captured by camera114by utilizing matting and despilling engine118.

As described in more detail below, the matting and despilling engine118can facilitate real-time matting of an image. Although the matting and despilling engine118is described as facilitating real-time matting of an image, it is contemplated that a user may employ the matting and despilling engine118to facilitate real-time matting of a video. Upon generation of a matted image or video, the matted image or video can be presented via the user device(s)112A-112N.

Components of the matting and despilling engine118may include, without limitation, a processing unit, internal system memory, and a suitable system bus for coupling various system components, including one or more data stores for storing information (e.g., files and metadata associated therewith). The matting and despilling engine118typically includes, or has access to, a variety of computer-readable media. By way of example, and not limitation, computer-readable media may include computer-storage media and communication media. The computing system environment100is merely exemplary. While the matting and despilling engine118is illustrated as a single unit, one skilled in the art will appreciate that the matting and despilling engine118is scalable. For example, the matting and despilling engine118may in actuality include a plurality of computing devices in communication with one another. The single unit depictions are meant for clarity, not to limit the scope of embodiments in any form. As another example, the components described herein can be included in the user device such that the user device performs, e.g., via an integrated matting and despilling engine, the functionality of real-time matting of an image.

As already mentioned, the matting and despilling engine118is generally configured to facilitate real-time matting of an image. Typically, matting and despilling engine118communicates with the camera114, user device(s)112A-112N, and/or database116to receive an image having a segmentation boundary between the foreground and background of the image and create a new image with a new background in real-time. In accordance with embodiments described herein, the matting and despilling engine118can include a boundary component120, an estimation component122, and an output component124. It should be understood that this and other arrangements described herein are set forth only as examples. Other arrangements and elements (e.g., machines, interfaces, functions, orders, and groupings of functions, etc.) can be used in addition to or instead of those shown, and some elements may be omitted altogether. Further, many of the elements described herein are functional entities that may be implemented as discrete or distributed components or in conjunction with other components, and in any suitable combination and location. Various functions described herein as being performed by one or more entities may be carried out by hardware, firmware, and/or software. For instance, various functions may be carried out by a processor executing instructions stored in memory.

In some embodiments, one or more of the illustrated components/modules may be implemented as stand-alone applications. In other embodiments, one or more of the illustrated components/modules may be integrated directly into the operating system of the matting and despilling engine118. The components/modules illustrated inFIG. 1are exemplary in nature and in number and should not be construed as limiting. Any number of components/modules may be employed to achieve the desired functionality within the scope of embodiments hereof. Further, components/modules may be located on any number of servers, computing devices, or the like. By way of example only, the matting and despilling engine118might reside on a server, cluster of servers, or a computing device remote from or integrated with one or more of the remaining components.

The matting and despilling engine118may be any type of computing device, or incorporated into a computing device, that can access a network (e.g., network110). For instance, the matting and despilling engine118may be a desktop computer, a laptop computer, a tablet computer, a mobile device, a server, or any other device, or portion thereof, having network access. In some embodiments, the matting and despilling engine118is provided by the user device(s)112A-112N. Generally, a user may employ the matting and despilling engine118via the user device112to, among other things, create new images or videos by combining a foreground from a first image or video with a background from a second image or video.

To illustrate the above example, a user may have an image containing a particular foreground object (e.g., a child). The image may have a background that is not ideal or may include unwanted objects. However, utilizing the matting and despilling engine118, the particular foreground object may be combined with any background in real-time to create a new image. In another example, a user may be involved in a video presentation or a video conference. The user may be in an office that is messy and does not want viewers of the video presentation or participants of the video conference to see the messy office. Accordingly, the user may employ the matting and despilling engine118to capture the user (i.e., the foreground object) in a new background (e.g., a clean office) in real-time to provide the appearance to the viewers or participants that the user is actually in a clean office.

As previously mentioned, in embodiments, the matting and despilling engine118includes a boundary component120, an estimation component122, and an output component124to facilitate real-time matting of an image. In particular, the matting and despilling engine118communicates with the camera114, user device(s)112A-112N, and/or database116to receive an image having a segmentation boundary between the foreground and background of the image, such as by using a video compositing, motion graphics design, and animation tool (e.g., ADOBE After Effects). The matting and despilling engine118may also communicate with the camera114, user device(s)112A-112N, and/or database116to receive a background that will be matted with the foreground to create a new image. Once the foreground and the background have been received, the matting and despilling engine118combines them to create the new image.

The boundary component120is generally configured to generate points of a bound on either side of the segmentation boundary. After the set of boundary points has been received that separates the foreground from the background of an image, boundary component120generates points of a band (i.e., the unknown band) by expanding and contracting the boundary points of the segmentation in the background and foreground regions. A matting radius, configurable by a user, defines the extent of the expansion/contraction used in the algorithm to generate the points.

In some embodiments, the points are generated first in the background region and then in the foreground region. In other embodiments, the points are generated first in the foreground region and then in the background region. Background points may be generated utilizing the following algorithm:

Initialize currentPostProcessPoints with segmentation boundary points

Add currentPostProcessPoints to contours_of_postProcessPoints_Bg*

Initialize distance to 1

Repeat until distance=matting_radiusInitialize nextPostProcessPoints as an empty listFor point in currentPostProcessPointsfor neighbor_point in the immediate 8 membered neighborhoodif neighbor_point is not visited and neighbor_point is a background point*a. Add neighbor_point to nextPostProcessPointsb. Add neighbor_point as a child of pointc. Mark neighbor_point as a visited pointIncrease distance by 1set currentPostProcessPoints to nextPostProcessPointsadd nextPostProcessPoints to contours_of_postProcessPoints_Bg at distanceEnd repeat

When points are generated in the foreground region, only those neighbor points are added to nextPostProcessPoints which are foreground points. The result may be stored in contours_of_postProcessPoints_Fg. Referring now toFIGS. 2-7, the process of generating the band is illustrated. As shown inFIG. 2, the initial set of boundary points200is received. The initial set of boundary points200represents the contour of the foreground object (in this example, a silhouette of a person).

Referring next toFIG. 3, a grid300illustrates the immediate eight membered neighborhood of pixels. In this example, points are being generated in the background region first. As shown, the points in the grid300that are background points are points302,304,306are added to the first background contour of the band. InFIG. 4, the initial set of boundary points400is illustrated along with the first background contour410of the band.

InFIG. 5, the grid500illustrates the immediate eight membered neighborhood of pixels that is utilized to generate the second background contour. As illustrated, the points in the grid500that are background points502,504,506are added to the second background contour of the band. InFIG. 6, the initial set of boundary points600is illustrated along with the first background contour610and the second background contour620of the band.FIG. 7illustrates the complete band comprising the initial set of boundary points700, the first background contour710, the second background contour720, the first foreground contour730, and the second foreground contour740.

Referring back toFIG. 2, the estimation component122is generally configured to estimate the background and foreground colors for each pixel in the band. This enables opacity to be calculated for each pixel generated by the boundary component120, thereby enabling matting and despilling to be performed for each pixel. Initially, estimation component122begins at the outermost background contour and estimates the background color of each pixel as an average of the color of background points in the neighborhood of the pixel. For clarity, the neighborhood with respect to estimation for the outermost contour is defined as background points which are not in the band. For interior contours, the neighborhood with respect to estimation is defined as background points in the contour at the next contour (e.g., for the first background contour710ofFIG. 7, the neighborhood of background points is the background points in the second background contour720).

As shown inFIG. 8, the background color is being estimated as an average of neighboring background pixels for the outermost contour (i.e., pixel800). In the outermost contour, pixels808,810,812,814,816that are in the band are not in the neighborhood of pixel800. Estimation component122utilizes the average color of pixels802,804,806to estimate the background color of pixel800. This estimation of the background color of pixel800can be applied by output component124, as described below, to propagate the estimated background color to pixel800.

As shown inFIG. 9, the background color is being estimated as an average of neighboring background pixels for the next contour (i.e., pixel900). For estimation of this contour, pixels908,910,912,914,916are not in the neighborhood of pixel900. Estimation component122utilizes the average color of pixels902,904,906to estimate the background color of pixel900. This estimation of the background color of pixel900can be applied by output component124, as described below, to propagate the estimated background color to pixel900. In a similar fashion, beginning at the contour closest to the initial set of boundary points, the background color of each contour point in the foreground contours is estimated.

Estimation component122estimates the foreground colors by initially beginning at the innermost foreground contour and moving towards the initial set of boundary points. The estimated foreground color for each pixel in the contour can be estimated as a linear combination of: 1) an average of the colors of foreground points in its neighborhood (for the innermost contour, the neighborhood is defined as foreground points which are not in the band; for interior contours, the neighborhood is defined as foreground points in the contour at the next contour (e.g., for the first foreground contour730ofFIG. 7, the neighborhood of foreground points is the foreground points in the second foreground contour730); and 2) an estimated color difference that is the difference in estimated background color for the pixel and the observed color of the pixel (a shifted foreground color is calculated by shifting the observed color in the direction of the color difference by an empirically decided factor. In some embodiments, the weight in the linear combination is empirically set to a default of 0.5 and is editable by the user.

Referring back toFIG. 2, the output component124is generally configured to initially propagate the estimated background colors to each pixel in the band. As shown inFIGS. 10 and 11, the estimated background color has been applied to each of the background contours1010,1020as well as each of the foreground contours1110,1120. The output component124is also generally configured to propagate the estimated foreground colors to each pixel in the band. The output component124performs despilling on the image by substituting the foreground color estimates in the matting band of the output image. After the despilling phase, the matte (α1) can be calculated by output component124by solving the matting equation: Ii=αiFi+(1−αi)βi, where Iirefers to the observed color of the pixel. To solve the matting equation, the estimated foreground (Fi) and background values (Bi) are substituted in the equation.

As shown inFIG. 12, the foreground colors have been estimated as a linear combination of a shifted color and an average color and have been propagated to each foreground contour1210,1220. InFIG. 13, the foreground colors have been estimated and propagated to each contour1310,1320,1330,1340,1350.

Once the foreground and background colors have been propagated in this way and the matte is calculated using the matting equation, matting has been achieved in real-time, as described herein. This enables the image having the selected foreground object and the new background object to appear to have a boundary that is blended and smooth. In some embodiments, the quality of the real-time matting is improved when the background of the original image or video is solid colored in the vicinity around the foreground object (but can have other colored objects away from the foreground object), or in other words, on content with low spatial frequencies.

Referring next toFIGS. 14-15, illustrative screenshots1400,1500are provided. InFIG. 14, a foreground object1410has been combined with a background1420. As shown, the boundary between the foreground object1410and the background1420includes points1420,1430,1440,1450that do not appear well blended or smooth. Turning toFIG. 15, after undergoing the real-time matting process, each of the illustrative troublesome points that appeared in the original combined image are now well blended and smooth points1520,1530,1540,1550.

InFIG. 16, an illustrative screenshot is provided that includes a customization tool1610. The customization tool1610enables the user to define setting that control the matting and despilling process. In embodiments, an Edge Filter Radius tool enables the user to select a matting radius or the number of contours which are generated inside and outside the received segmentation boundary, a Matte Bias tool enables the user to select the weight used estimating the linear combination of a shifted color and an average color (as described herein), and/or a Despill Amount tool enables the user to select the weight used for calculating the shifted color (as described herein).

Turning now toFIG. 17, a flow diagram is provided that illustrates a method1700for facilitating real-time matting of an image, according to embodiments provided herein. Initially, at block1710, a set of boundary points for a segmentation is received. The segmentation separates the foreground from the background of an image. The set of boundary points for the segmentation may represent a blend of background and foreground colors.

Points of a band are generated, at block1712, by expanding and contracting the boundary points of the segmentation in the background and foreground regions. In some embodiments, a configurable matting radius is received from a user. The configurable matting radius defines the expanding and contracting of the boundary points in the background and foreground regions to generate points of the band. For example, the number of contours generated depends on the matting radius selected by the user. As described herein, the matting radius is two. However, it should be appreciated that the matting radius can be set to any desired number of contours. Initially, a first background contour level of neighboring background points may be generated. Next, a second background contour level of neighboring background points may be generated. Further, a first foreground contour level of neighboring foreground points may be generated. Finally, a second foreground contour level of neighboring foreground points may be generated.

At block1714, background and foreground colors for each pixel in the band are estimated. To do so, an average of colors of background points in a neighborhood of each pixel may be estimated. The neighborhood may be a set of points adjacent to a particular pixel.

Based on the estimated background and foreground colors, an opacity and true foreground colors for the image are determined at block1716. In embodiments, opacity and true foreground colors for the output image are determined based on the estimates of the background and foreground colors of the image. Based on the opacity and true foreground colors, an output image is provided at block1718. The output image is processed with real-time matting.

With reference now toFIG. 18, a flow diagram is provided that illustrates a method1800for facilitating real-time matting of an image, according to embodiments provided herein. Initially, as indicated at block1810, a matting radius is utilized that identifies an unknown region of an image. A set of boundary points may be received for a segmentation that separates the foreground from the background of an image. The matting radius may be utilized to generate points of a band by expanding and contracting the boundary points of the segmentation in the background and foreground regions. Background and foreground colors for each pixel in the band may be estimated. Background colors for each pixel in the band may be estimated based on an average of colors of background points in a neighborhood of each pixel. Based on the estimated background and foreground colors, true foreground colors for the image may be determined.

An alpha mask and despilling is determined, at block1812, in the unknown region of the image. The alpha mask corresponds to an opacity in the unknown region of the image and is based on the estimated background and foreground colors for each pixel in the band. An output image corresponding to a real-time matting and despilling version of the image may be provided. The output image is based on the opacity and true foreground colors.

With reference toFIG. 19, computing device1900includes a bus1910that directly or indirectly couples the following devices: memory1912, one or more processors1914, one or more presentation components1916, input/output (I/O) ports1918, input/output components1920, and an illustrative power supply1922. Bus1910represents what may be one or more busses (such as an address bus, data bus, or combination thereof). Although the various blocks ofFIG. 19are shown with lines for the sake of clarity, in reality, delineating various components is not so clear, and metaphorically, the lines would more accurately be grey and fuzzy. For example, one may consider a presentation component such as a display device to be an I/O component. Also, processors have memory. The inventor recognizes that such is the nature of the art, and reiterates that the diagram ofFIG. 19is merely illustrative of an exemplary computing device that can be used in connection with one or more embodiments of the present invention. Distinction is not made between such categories as “workstation,” “server,” “laptop,” “hand-held device,” etc., as all are contemplated within the scope ofFIG. 19and reference to “computing device.”

Memory1912includes computer-storage media in the form of volatile and/or nonvolatile memory. The memory may be removable, non-removable, or a combination thereof. Exemplary hardware devices include solid-state memory, hard drives, optical-disc drives, etc. Computing device1900includes one or more processors that read data from various entities such as memory1912or I/O components1920. Presentation component(s)1916present data indications to a user or other device. Exemplary presentation components include a display device, speaker, printing component, vibrating component, etc.

As can be understood, embodiments of the present invention provide for, among other things, facilitating real-time matting of an image. The present invention has been described in relation to particular embodiments, which are intended in all respects to be illustrative rather than restrictive. Alternative embodiments will become apparent to those of ordinary skill in the art to which the present invention pertains without departing from its scope.