Image and Video Matting: A Survey - Jue W

1 Foundations and TrendsR insampleVol. xx, No xx (xxxx) 1 78c xxxx xxxxxxxxxDOI: xxxxxxImage and Video matting : A SurveyJue Wang1and Michael F. Cohen21 Adobe Systems Incorporated, 801 North 34th Street, Seattle, WA 98103,USA, Research, One Microsoft Way, Redmond, WA 98052, refers to the problem of accurate foreground estimation inimages and Video . It is one of the key techniques in many Image editingand film production applications, thus has been extensively studiedin the literature. With the recent advances of digital cameras, usingmatting techniques to create novel composites or facilitate other editingtasks has gained increasing interests from both professionals as wellas consumers. Consequently, various matting techniques and systemshave been proposed to try to efficiently extract high quality mattesfrom both still images and Video Survey provides a comprehensive review of existing Image andvideo matting algorithms and systems, with an emphasis on the ad-vanced techniques that have been recently proposed.

2 The first part ofthe Survey is focused on Image matting . The fundamental techniquesshared by many Image matting algorithms, such as color samplingmethods and matting affinities, are first analyzed. Image matting tech-niques are then classified into three categories based on their underlyingmethodologies, and an objective evaluation is conducted to reveal theadvantages and disadvantages of each category. A unique Accuracy analysis is presented as a practical guidance for readers to prop-erly choose matting tools that best fit their specific requirements second part of the Survey is focused on Video matting . The diffi-culties and challenges of Video matting are first analyzed, and variousways if combine matting algorithms with other Video processing tech-niques for building efficient Video matting systems are reviewed.

3 Keycontributions, advantages as well as limitations of important systemsare , special matting systems that rely on capturing additional fore-ground/background information to automate the matting process arediscussed. A few interesting directions for future matting research arepresented in the The matting ProblemExtracting foreground objects from still images or Video sequencesplays an important role in many Image and Video editing applications,thus it has been extensively studied for more than twenty years. Ac-curately separating a foreground object from the background involvesdetermining both full and partial pixel coverage, also known aspulling amatte,ordigital matting . This problem was mathematically establishedby Porter and Duff in 1984 [28]. They introduced the alpha channel asthe means to control the linear interpolation of foreground and back-ground colors for anti-aliasing purposes when rendering a foregroundover an arbitrary background.

4 Mathematically, the observed imageIz(z=(x, y)) is modelled as a convex combination of foreground imageFzand background imageBzby using the alpha matte z:Iz= zFz+(1 z)Bz( )where zcan be any value in [0,1]. If z= 1 or 0, we call pixelzdefinite foregroundordefinite background, respectively. Otherwise wecall pixelzmixed. In most natural images, although the majority ofpixels are either definite foreground or definite background, accurately12 Introductionestimating alpha values for mixed pixels is essential for fully separatingthe foreground from the only a single input Image , all three values ,FandBare un-known and need to be determined at every pixel location. The knowninformation we have for a pixel are the three dimensional color vectorIz(assuming it is represented in some 3D color space), and the unknownvariables are the three dimensional color vectorsFzandBz,andthescalar alpha value z.

5 matting is thus inherently an under-constrainedproblem, since 7 unknown variables need to be solved from 3 knownvalues. Most matting approaches rely on user guidance and prior as-sumptions on Image statistics to constrain the problem to obtain goodestimates of the unknown variables. Once estimated correctly, the fore-ground can be seamlessly composed onto a new background, by simplyreplacing the original backgroundBwith a new background imageB in equation Binary Segmentation vs. MattingIf we constrain the alpha values to be only 0 or 1 in equation ,the matting problem then degrades to another classic problem: binaryimage/ Video segmentation, where each pixel fully belongs to either fore-ground or background. This problem has been extensively studied sinceearly 1960s, resulting in a large volume of related literature.

6 Althoughmatting is modelled as a more general problem than binary segmen-tation, which is theoretically harder to solve, most existing mattingalgorithms avoid the segmentation problem by having atrimapas an-other input in addition to the original Image . The trimap may be man-ually specified by the user, or produced by other binary segmentationapproaches. The trimap reduces the dimension of the solution spaceof the matting problem, and leads the matting algorithms to generateuser-desired binary segmentation and alpha matting are closely cou-pled problems, in this Survey for Image matting we will assume thata rough foreground segmentation is given, thus we mainly focus onhow to accurately estimate alpha values for truly mixed pixels. Wewill however discuss binary segmentation techniques in the context The Trimap3 Fig.

7 A matting example. From left to right: input Image ; user specified trimap; extractedmatte; estimated foreground colors; a new composite. Results are generated by the RobustMatting algorithm [48]. Video matting systems since they play a more central role in recentvideo matting The TrimapWithout any additional constraints, it is obvious that the total numberof valid solutions to equation is infinite. For a trivial solution, onecan set all zstobe1andallFzstobeidenticaltoI(z)s as a validsolution, which simply means the whole Image is fully occupied bythe foreground. Of course this solution is probably not consistent withwhat a human being will perceive from the input Image . To properlyextract semantically meaningful foreground objects, almost all mat-ting approaches start by having the user segment the input Image intothree regions: definitely foregroundRf, definitely backgroundRbandunknownRu.

8 This three-level pixel map is often referred to as matting problem is thus reduced to estimatingF,Band for pix-els in the unknown region based on known foreground and backgroundpixels. An example of a trimap is shown in Figure of requiring a carefully specified trimap, some recently pro-posed matting approaches allow the user to specify a few foregroundand background scribbles as user input to extract a matte. This in-trinsically defines a very coarse trimap by marking the majority pixels(pixels haven t been marked by the user) as of the important factors effecting the performance of a mattingalgorithm is how accurate the trimap is. Ideally, the unknown regionin the trimap should only cover truly mixed pixels. In other words, theunknown region around the foreground boundary should be as thin as4 Introductionpossible to achieve the best possible matting results.

9 This is somewhatobvious since the more accurate the trimap is, the less number of un-known variables need to be estimated, and the more known foregroundand background information is available to use. However, accuratelyspecifying a trimap requires significant amounts of user effort and isoften undesirable in practice, especially for objects with large semi-transparent regions or holes. Thus a big challenge for designing a suc-cessful matting algorithm is how to achieve a good trade-off betweenthe accuracy of the matte and the amount of the user effort we will see later, different algorithms have totally different charac-teristics in this accuracy-efficiency is worth mentioning that the recently proposed Spectral mattingalgorithm [23] can automatically extract a matte from an input imagewithout any user input.

10 However, as the authors agreed, the automaticapproach has a number of limitations including erroneous results forimages with highly-textured backgrounds. Thus in practice, user spec-ified trimaps are typically necessary to achieve high quality The User InterfaceA properly designed user interface is critical to the success of an in-teractive system. Surprisingly, although the matting problem has beenstudied for more than two decades, very little research has been doneon exploring good user interfaces for the matting task. Most of the ex-isting matting systems work in an offline mode, where in the interactiveloop, the user first specifies a trimap, the invokes matting algorithmsto compute a matte. If the result is not satisfactory, the user thenrefines the trimap and runs the algorithm again. On the other hand,recently-proposed matting algorithms mainly focus on how to improvethe quality of the matte by introducing more sophisticated analysisand optimization methods, thus they are generally slow.