“GrabCut” — Interactive Foreground Extraction using Iterated Graph CutsBy Carsten Rother, Vladimir Kolmogorovand Andrew Blake at Microsoft Research Cambridge, UKSIGGRAPH 2004Slides by David Anthony TorresComputer Science and Engineering — University of California at San DiegoObject Extraction• Deal with efficient, interactive extraction of a foreground object from a complex background.• Goal is to produce a “good” automatic extraction with as little user interaction as possible.• Performance is measured by! Accurate segmentation of the object.! Subjectively convincing extraction when faced with blur, transparency. ! Free of color bleeding in from the background.Object Extraction• Useful because, historically, extraction of objects from images requires a lot of user interaction.• Interactive segmentation tools have been developed:! Magic Wand (in Adobe Photoshop)! Intelligent Scissors (a.k.a. Live Wire, Magnetic Lasso)! Bayes Matting and Knockout! Graph Cut • This paper extends the Graph Cut algorithm so lets look at that first:GraphCut for a Monochrome Image• User provides a trimap T = { TF , TB , TU } which partitions the image into 3 regions: foreground, background, unknown.TFTUTB• The image is an array z = (z1,…zN) of grey values indexed by the single index n.• The segmentation of the image is an alpha-channel, or, a series of opacity values α=(α1,…, αN) at each pixel with 0 ≤αn ≤1.• The parameter θ describes the foreground/background grey-level distributions. i.e. a pair of histogram of gray values: {(; ), 0,1}hzθαα==z• Note that these histograms are directly assembled from the trimaps TBand TF• Re-pose the segmentation task:! The segmentation task is to infer the unknown opacity values α from image z and the model θ.{(; ), 0,1}hzθαα==zSegmentation by Energy Minimization• An energy function E is defined so that its minimum corresponds to a good segmentation.• This is captured by a “Gibbs” energy of the form:E(α,θ,z) = U(α,θ,z) + V(α,z)E(α,θ,z) = U(α,θ,z) + V(α,z)• U evaluates the fit of the opacity α to the data z! i.e. it gives a good score (low score) if α looks like it’s consistent with the histogram.• V is a smoothness term which penalizes if there is too much disparity between neighboring pixel values. (,,) log( ; )nnnUz hzαθ α=−∑• Given the energy model we can obtain a segmentation by finding • Which can be solved using a minimum cut algorithm which gives you a hard segmentation, α = {0,1}, of the object.!arg min ( , )Eαααθ=E(α,θ,z) = U(α,θ,z) + V(α,z)•Edge weights are labeled with U( ) and V ( )Min-CutHow GrabCut adds to Graph Cut• The monochrome image model is replaced for color by a Gaussian Mixture Model (GMM) in place of histograms.• One shot min-cut solution is replaced by an iterative procedure that alternates between estimation and parameter learning• Allow for incomplete labeling, i.e. the user need only specify the background trimap TB (and implicitly the unknown map TU )• This amounts to one less user interaction step that was required in previous versions.From this …To this …[Specifying foreground and background][Specifying background only]Adding the Color Model• Each pixel znis now in RGB color space• Color space histograms are impractical so we use a Gaussian Mixture Model (GMM)! 2 Full-covariance Gaussian mixtures with K components (K ~ 5).! One for foreground, one for background.• Add to our model a vector k ={ k1… kN}, with kiin {1 … K}• kiassigns the pixel zito a unique GMM component (Either from F.G. or B.G. as α dictates)New Energy Model• Must incorporate k into our model: E(α,k,θ,z) = U(α,k,θ,z) + V(α,z)whereU(α,k,θ,z) = ∑nD(αn,kn,θ,zn)• D(αn,kn,θn,zn)= – log p(zn| αn,kn,θ) – log π(αn,kn)• Where π(·) is a set of mixture weights which satisfy the constraint:New Energy Model•Our θ becomes θ={π(α,k), µ(α,k), Σ(α,k), α=0,1, k=1…K}• Total of 2K Gaussian componentsweightsmeans cov.fg/bg.mixturecomponentAnd now … the Algorithm:Iterative Minimization• find knby iterating through all values 1…K. (K is small)Iterative Minimization• For example, to find the Gaussian parameters for a component k in the foreground:!Find the set of pixels Zkassigned to k by the k-vector.!Find µ,Σ, in the standard fashion.!Update the weights at π(α,k):= |Zk| / ∑k |Zk|Iterative Minimization•Now that k and θ are known, we can solve for the opacity values using a minimum-cut algorithm, and reapply the min-cut until convergence.• Each iteration eats away at the unknown region and continues to minimize the energy function.iterationUser Editing• If the segmentation is imprecise, the user can constrain pixels to the foreground/background• Then we run min-cut (or the entire procedure) again to produce a final segmentation.Summary of Algorithm• Start with TBand TUas inputs.• We use the input to initialize the foreground and background GMMs• Using the GMM’s we solve an energy minimization problem via min-cut, which corresponds to an initial segmentation of the object,T’Band T’U.• Repeat the procedure with T’Band T’Uas inputs until convergence (TF=T’U).• User interaction then repeat either min-cut or all steps.Border Matting• After the selection is made, the authors also implement a border matting tool.• For time purposes I wont go into details.• Basic idea is to use another energy-minimization solution to estimate the appropriate value of pixels along the boundaries of the