\documentclass[10pt,twocolumn,letterpaper]{article}
\usepackage{cvpr}
\usepackage{times}
\usepackage{epsfig}
\usepackage{graphicx}\graphicspath{{./Imgs/}}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{dsfont}
\usepackage{algorithm}
\usepackage{cite}
\usepackage{algorithmic}
\usepackage{multirow}
\usepackage{overpic}
\usepackage{subfigure}
\usepackage{soul}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage[pagebackref=false,breaklinks=true,letterpaper=true,colorlinks,bookmarks=true]{hyperref}
\setcounter{tocdepth}{4}

\usepackage{enumitem}
\setenumerate[1]{itemsep=0pt,partopsep=0pt,parsep=\parskip,topsep=1pt}
\setitemize[1]{itemsep=0pt,partopsep=0pt,parsep=\parskip,topsep=2pt}
\setdescription{itemsep=0pt,partopsep=0pt,parsep=\parskip,topsep=5pt}
%\cvprfinalcopy % *** Uncomment this line for the final submission
\def\cvprPaperID{648} % *** Enter the CVPR Paper ID here
\def\httilde{\mbox{\tt\raisebox{-.5ex}{\symbol{126}}}}


\renewcommand{\tabcolsep}{.7mm}

\newcommand{\figref}[1]{Fig. \ref{#1}}
\newcommand{\tabref}[1]{Tab. \ref{#1}}
\newcommand{\equref}[1]{(\ref{#1})}
\newcommand{\secref}[1]{Sec. \ref{#1}}
\newcommand{\algref}[1]{Alg. \ref{#1}}
\newcommand{\cmm}[1]{\textcolor[rgb]{0,0.6,0}{#1}}
\newcommand{\dnew}[1]{\textcolor[rgb]{0,0.6,0.6}{#1}}
\newcommand{\todo}[1]{{\textcolor{red}{#1}}}
\newcommand{\sArt}{state-of-the-art}
\newcommand{\Rows}[1]{\multirow{2}{*}{#1}}
\newcommand{\Cols}[1]{\multicolumn{2}{c|}{#1}}
\renewcommand{\algorithmicforall}{\textbf{for each}}
\newcommand{\intu}{{\sc int-uion}}
\newcommand{\svm}{{\sc svm}}
\newcommand{\delete}[1]{}
\newcommand{\sz}{$8 \times 8$}
\newcommand{\CRF}{{\sc crf}}
\newcommand{\SalGC}{GC \cite{13IccvChengSaliency}}
\newcommand{\GrabCutGPU}{GrabCut \cite{CudaGrabCut}}
\newcommand{\DataMSRA}{{\sc msra1000} \cite{09CvprFTSaliency,10pamiLearningSal}}
\newcommand{\DataGrabCut}{{\sc grabcut} \cite{04TogRotherGrabcut}}
\newcommand{\GrabCut}{GrabCut \cite{04TogRotherGrabcut}}
\newcommand{\OneCut}{OneCut \cite{OneCutICCV13}}
\newcommand{\addFigure}[1]{\includegraphics[height=0.053\textwidth]{{#1}}}
\DeclareMathOperator*{\argmin}{\mbox{argmin}}



\ifcvprfinal\pagestyle{empty}\fi



%\graphicspath{{./Imgs/}}

\begin{document}

\title{Saliency-driven GrabCut in Realtime} % Replace with your title

\author{Ming-Ming Cheng$^1$ \quad Carsten Rother$^2$  \quad Victor Adrian Prisacariu$^1$
\quad Shuai Zheng$^1$  \\ \quad Shahram Izadi$^3$   \quad Philip~Torr$^1$\\
$^1$The University of Oxford \quad $^2$TU Dresden  \quad $^3$Microsoft Research}

\maketitle

\begin{abstract}
Figure-ground segmentation from bounding box input,
provided either automatically or manually, % by a user,
has been extremely popular in the last decade and
influenced various applications.
%including object recognition and image editing.
A lot of research has focused on high-quality segmentation,
using complex formulations which often lead to slow techniques,
and often hamper practical usage.
%and are less relevant for interactive applications.
In this paper we demonstrate a very fast segmentation technique
which still achieves very high quality results.
We show that by combing two simple ideas we are able to achieve an order
of magnitude (10x) speed-up with respect to the closest competitor,
and at the same time achieve a considerably higher accuracy. 
%performance rate.
Our first idea is to include a simple salient object prior
which is motivated by recent work in the field of salient object detection.
Our second idea is to replace the iterative refinement of global colour
models by a densely connected \CRF.
We motivate this decision by showing that a dense \CRF~implicitly models
an unnormalised global colour model.
%\keywords{Image segmentation, Saliency, Dense CRF, GrabCut}
\end{abstract}


\section{Introduction}\label{sec:Intro}


Figure-ground image segmentation from bounding box input,
provided either automatically \cite{IccvChai2013Symbiotic,11CvprSalRC}
or manually \cite{04TogRotherGrabcut},
has been extremely popular in the last decade and influenced various
computer vision and computer graphics applications,
including image editing \cite{lalonde2007photo},
object detection \cite{shotton2005contour},
image classification \cite{winn2005object},
photo composition \cite{Tog09Sketch2Photo},
scene understanding \cite{kohli2009robust},
automatic object class discovery \cite{zhu2012unsupervised},
and fine-grained categorization \cite{IccvChai2013Symbiotic}.
%
In order to achieve high quality results,
recent methods have focused on complex formulations
\cite{09IccvJointSeg,lempitsky2009image,OneCutICCV13},
which typically leads to slow techniques.


In this works we aim to design a very fast figure-ground image segmentation
technique which still achieves high quality results.
%
Our method relies on two insights about the problem.
%\ie salient object prior and fully connected \CRF.
First, given a user provided bounding box constraint,
the target object region often stands out as a non-ambiguous salient object
\cite{10pamiLearningSal}.
%
This salient object prior assumption enables a good initial estimation 
for the target object region by borrowing ideas from 
\sArt~salient object detection techniques
\cite{10pamiLearningSal,09CvprFTSaliency,11CvprSalRC,perazzi2012saliency,13IccvChengSaliency}.
%
We reformulate the salient object detection problem,
aiming to maximize the amount of information generated within the 
specified bounding box while still maintaining real-time efficiency 
(\secref{sec:unary}).
%
Second, we observe that a dense \CRF~implicitly models an unnormalized global colour model,
the explicit estimation of which often leads to slow optimization
(\secref{sec:Representation}).
%
This enables us to replace the iterative refinement of global colour
models \cite{04TogRotherGrabcut} with a densely connected \CRF,
for which very efficient inference techniques have been recently developed
\cite{krahenbuhl2011efficient}.


Following recent advances in GrabCut segmentation \cite{OneCutICCV13},
we extensively evaluate our method on two standard benchmarks,
the \DataGrabCut~and the \DataMSRA~datasets,
containing 50 and 1000 images, respectively,
with corresponding binary segmentation masks.
%
Our formulation achieves $F_\beta = 92.8\%$ and $F_\beta = 95.5\%$
on the \DataGrabCut~and the \DataMSRA~dataset respectively,
where the $F_\beta$ represents the harmonic mean of precision and recall.
%
Along with generating better segmentations,
our method enables real-time CPU processing
which is (10$\times$ on average) faster
than its closest competitor \cite{OneCutICCV13}.
%

\section{Related work}\label{sec:RelatedWorks}

Here we review related work
that performs interactive figure-ground segmentation
\cite{boykov2001interactive,rother2011interactive}.
%
Among the many different approaches proposed over the years,
the most successful technique incorporates a per-pixel appearance model
and pairwise consistency constraints \cite{blake2004interactive},
and uses graph cut for efficient energy minimization \cite{boykov2004experimental}.

Rother \etal \cite{04TogRotherGrabcut} proposed the first bounding box
based segmentation system that optimised both the appearance model and the segments,
using initial appearance models computed from a given bounding box.
%
It was shown by Vicente \etal \cite{09IccvJointSeg} that
it is possible to reformulate the GrabCut energy functional
\cite{04TogRotherGrabcut} in closed form as a higher order MRF,
by maximizing over global appearance parameters.
This was possible by switching from a GMM to a histogram representation
for the appearance model.
However, the optimization of the higher-order MRF is unfortunately NP-hard.
Nevertheless, the proposed dual decomposition technique is able to achieve globally optimality in about $60\%$ of cases.
%
Recently, OneCut \cite{OneCutICCV13} by Tang \etal has
derived a similar formulation.
They argue, however, that the part of the  higher-order MRF that
make the problem NP-hard, \ie~the volume regularization term,
is not relevant in practical applications.
Hence, they drop this term and can guarantee a  globally optimal solution.
%
It is important to note, that on an abstract level our paper
has exactly the same reasoning.
We show that the GrabCut functional and a densely connected CRF formulation
are the same under some approximations.
We then argue and show that these approximations are not too critical
for practical scenarios.
%
%In this work we aim to build a foreground segmentation system that can achieve
%better segmentation results and run faster,
%by utilizing salient object prior assumption \cite{10pamiLearningSal}
%and efficient mean field based inference \cite{krahenbuhl2011efficient}.

Our method is inspired by the active research field of 
visual attention modelling.
We refer the reader to a recent survey paper \cite{borji2013state} for
details about the three major branches of this area:
fixation prediction \cite{Judd12},
salient object detection \cite{borji2012salient},
and objectness estimation \cite{BingObj2014}.
Here we discuss recent advancements in the most related areas of salient object detection and segmentation.
%
Liu \etal \cite{10pamiLearningSal} proposed a \CRF~framework that combines multiple saliency measures
for an effective salient object detection.
Achanta \etal \cite{09CvprFTSaliency} proposed a frequency tuned approach 
to detect salient object regions.
%
Cheng \etal \cite{11CvprSalRC} proposed a
salient object detection method by modelling the global contrast of a
region to all other regions in the image.
A filtering based framework \cite{perazzi2012saliency} and
an efficient data representation \cite{13IccvChengSaliency}
have also been used for the salient object detection task.
%
Although these methods have successfully achieved accurate salient
object detection and segmentation results on
images with a \textit{single} non-ambiguous object,
dealing with more complicated images with \textit{multiple} objects remains a
challenging issue.
%
Moreover, such methods are designed for unsupervised salient object segmentation,
so they do not explicitly explore the background prior available in interactive segmentation applications.

\section{Methodology}\label{sec:Method}

We formulate the figure-ground segmentation problem as a binary
label Conditional Random Field (\CRF) problem.
The \CRF~is defined over the random variables 
$\mathbf{X} = \{X_1, X_2, ..., X_n\}$,
where each $X_i \in \{0, 1\}$, 0 for background and 1 for foreground,
represents a binary label of the pixel 
$i\in \mathcal{N}=\{1,2,...,n\}$ such that each random variable 
corresponds to an image pixel.
%
We denote with $\mathbf{x}$ a joint configuration of these random variables,
and $\mathbf{I}$ the observed image data.
%
Based on the general formulation of \cite{krahenbuhl2011efficient},
a fully connected binary label \CRF~can be defined as:
\begin{equation}\label{equ:energy}
E(\mathbf{x}) = \sum\nolimits_{i \in \mathcal{N}} \psi_i (x_i)
+ \sum\nolimits_{i < j} \psi_{ij} (x_i, x_j),
\end{equation}
where $i$ and $j$ are pixel indices, % ranging from $1$ to $n$ and
$\psi_i$ and $\psi_{ij}$ are unary (see \secref{sec:unary})
and pairwise (see \secref{sec:pairewise}) potentials respectively.


\subsection{Saliency aware unary term estimation} \label{sec:unary}
The unary term $\psi_i$ measures the cost of assigning a
binary label $x_i$ to the pixel $i$, defined as,
\begin{equation}\label{equ:unary}
  \psi_i = - \log ( S(x_i) ),
\end{equation}
where $S(x_i) \in (0, 1)$ will be estimated in a saliency aware fashion.
%
Different from other \sArt~figure-ground segmentation approaches,
which pay more attention to the iterative optimization \cite{04TogRotherGrabcut}
or to finding the globally minimal solution for the energy function
\cite{lempitsky2008image,09IccvJointSeg,OneCutICCV13},
we focus on the complementary task of efficiently obtaining better
unary potentials.
%
We argue that although pairwise terms are very informative and important,
previous approaches have primarily tried to get the best results
according to the noisy unary.
%
Using an incorrect unary term, even if we manage to find the globally optimal solution for the entire energy function,
we might still obtain incorrect results.
%
We therefore believe that the unary terms should receive at least the same amount of attention as the pairwise ones.

For object segmentation in complicated images with multiple objects, 
the target typically stands out as a non-ambiguous salient region 
\cite{10pamiLearningSal} within the specified bounding box. 
This saliency assumption however has yet to be explored in the
current interactive image segmentation literature. %  \cite{borji2012salient,borji2013state}
%
We initially considered using the \sArt~salient object detection method
to find the saliency map from the image region cropped
according to the selected bounding box.
%
However, directly using traditional saliency detection methods 
in the bounding box
scenario does not explicitly use the background prior,
\ie~the fact that pixels outside the selection window belong to the background.
This leads to a suboptimal appearance model estimation and missing parts
for regions with similar appearance to background.
%
We show examples of such images in the top two rows of \figref{fig:Unary},
and statistical results in \tabref{tab:Results}.

%\renewcommand{\addFigure}[1]{\includegraphics[height=0.1123\textwidth]{SalMap/#1}}
%\newcommand{\addFigures}[3]{\rotatebox{90}{\hspace{#2} #3} & \addFigure{0_5_5255_#1} & \addFigure{1_28_28351_#1} & \addFigure{1_34_34382_#1} & \addFigure{1_55_55762_#1} & \addFigure{1_60_60933_#1} & \addFigure{1_61_61579_#1} & \addFigure{2_86_86600_#1}}
\begin{figure*}[t!]
    \centering
%    \renewcommand{\arraystretch}{1.1}
%    \begin{tabular*}{\linewidth}{cccccccc}
%        \addFigures{S.jpg}{.18in}{source} \\
%        \addFigures{P.png}{.21in}{\cite{13IccvChengSaliency}} \\
%        \addFigures{P1.png}{.14in}{$w_s=1$} \\
%        \addFigures{P2.png}{.14in}{$w_s=2$} \\
%        \addFigures{P4.png}{.14in}{$w_s=4$} \\
%    \end{tabular*}
    \includegraphics[width=\textwidth]{ImgN/SalSample.pdf}
    \caption{Sample results for global contrast 
        saliency estimation \cite{13IccvChengSaliency}
        and saliency aware unary maps with different $w_s$ values
        (see also \equref{equ:Sal}).
    }\label{fig:Unary}
\end{figure*}

For an effective use of both background and saliency priors for segmentation,
we need to carefully consider what are the major underlying hints
contained by two priors, and use them in an efficient and unified way.
%
The background prior not only tells us that the pixels outside the
bounding box could be excluded from possible object regions,
but it also supplies robust samples for understanding the background
appearance.
%
One of the most effective feature for salient object region detection 
is that the region should have high contrast with respect to
the entire image, \ie~global contrast.
Such cues have been extensively explored in the \sArt~
salient object detection methods
\cite{09CvprFTSaliency,11CvprSalRC,perazzi2012saliency,13IccvChengSaliency}.

For foreground labeling, we propose the following equations
to capture both background and saliency priors,
\begin{align}\label{equ:Sal}
    S(x_i=1) = \frac{P(\Theta_B,I_i)}{P(\Theta_B,I_i) + w_s  P(\Theta_F,I_i)},
\end{align}
where $P(\Theta_B,I_i)$ and $P(\Theta_F,I_i)$ represent
the probability of a pixel color $I_i$
belonging to the background color model $\Theta_B$
and the foreground color model $\Theta_F$, respectively.
%
The parameter $w_s$ is a scalar value that indicates how
salient the target object should be.
The larger $w_s$ is the more salient an object should be in order
to get a high value of $S(x_i=1)$.
For background labeling, we use $S(x_i=0)= 1-S(x_i=1)$.
Notice that due to the nature of the bounding box interaction,
$\Theta_B$ is trained from confident background samples.
%
Other pixels (containing both foreground and background pixels)
are used to train a less confident foreground color model
$\Theta_F$ .



In \figref{fig:Unary}, we show results obtained using different values of $w_s$.
When $w_s = 1$, \equref{equ:Sal} represents the value used in a standard GrabCut implementation
\cite{04TogRotherGrabcut,CudaGrabCut,bradski2008learning}.
When $w_s > 1$, the value $S(x_i) \in (0,1)$ in \equref{equ:Sal}
measures the saliency of an unknown pixel $x_i$ with respect to
all other pixels, while at the same time giving a larger weight to nearby background pixels,
which is the most effective feature in \sArt~salient object detection methods
\cite{09CvprFTSaliency,11CvprSalRC,perazzi2012saliency,13IccvChengSaliency}.
%
In our experiments we use $w_s = 2$, obtained using 5-fold cross validation.

\subsection{Fully connected pairwise term} \label{sec:pairewise}

The pairwise term $\psi_{ij}$ encourages similar and nearby pixels to take consistent labels.
We use a contrast sensitive two kernel potential:
\begin{align}\label{equ:pairwise}
  \psi_{ij} & = [x_i \neq x_j] g(i,j), \\
  g(i,j) & = w_1 \cdot g_1(i, j) + w_2 \cdot g_2(i,j) \label{equ:similarity}
\end{align}
where the Iverson bracket $[\cdot]$ is $1$ for a true condition and
$0$ otherwise, and the similarity function \equref{equ:similarity} 
is defined in terms of color vectors
$I_i, I_j$ and position values $p_i, p_j$:
\begin{align}
  g_1(i, j) & = \exp \left( -{|p_i - p_j|^2}/{\theta_\alpha^2}
        -{|I_i - I_j|^2}/{\theta_\beta^2} \right),
        \label{equ:PixelSimi} \\
  g_2(i, j) & = \exp \left( -{|p_i - p_j|^2}/{\theta_\gamma^2} \right).
        \label{equ:smoothness}
\end{align}
Here, \equref{equ:PixelSimi} models the appearance similarity and
encourages nearby pixels with similar color to have the same binary label.
\equref{equ:smoothness} encourages smoothness and helps remove
small isolated regions.
The degree of nearness, similarity, and smoothness are controlled by
$\theta_\alpha, \theta_\beta$ and $\theta_\gamma$, respectively.
Intuitively, $\theta_\alpha \gg \theta_\gamma$ should be satisfied if the
first term manages the long range connections and the second term
measures the local smoothness. These parameters are learned via cross validation.


\subsection{Implementations}
\label{sec:Representation}

%Here we discus some important design choices and implementation details.

\paragraph{Color modelling: GMMs vs. Histogram.}
Effective color modelling is very important for good segmentation results.
Among many different models suggested in the literature,
two of the most popular ones are histograms \cite{boykov2001interactive}
and Gaussian Mixture Models (GMMs) \cite{blake2004interactive,04TogRotherGrabcut}.
%
Some important recent works use histogram
\cite{OneCutICCV13,09IccvJointSeg} representations.

In \cite{09IccvJointSeg}, the authors suggest that the
MAP estimation with the GMM model is in effect an ill-posed problem,
since fitting a Gaussian to the color of a single pixel may result in
an infinite likelihood (see \cite{bishop2006pattern}).
%
As explained in \cite{rother2011interactive},
this can be avoided by adding a small constant to the covariance matrix.
%
Compared to histograms, GMMs can better adapt to the colours of the image,
while still being effective at capturing small appearance differences between foreground and background.
Furthermore, the histogram representation will treat different colours equally differently,
ignoring the color values of the histogram bins, \eg~two pixels of a banana might have slightly different color
and be quantised to different bins, even if they are different from the background, with typically
a much larger color difference.
%
We experimentally verify the above discussion via extensive evaluations
in \secref{sec:CompareQulity}. %\vv{this part needs to be rewritten}


\paragraph{Efficient GMM estimation.}
As in both the OpenCV \cite{bradski2008learning} and Nvidia CUDA implementation \cite{CudaGrabCut},
typical GMM estimation can be very computationally expensive,
due to the large amount of data samples (pixels) used to train the GMMs.
%
In the salient object detection community, more efficient GMM estimation methods have recently been developed
\cite{13IccvChengSaliency}.
The estimation is made more efficient using an intermediate
histogram based representation.
Since natural images typically cover a very small portion of all possible colours,
uniformly quantizing the image colours (with each channel divided into 12 parts)
and then choosing the most frequent color bins until $95\%$ of image pixels
are covered, typically results in a small histogram
(an average of $85$ histogram bins has been reported \cite{11CvprSalRC}
for the \DataMSRA~benchmark).
%
Instead of using hundreds of thousands of image pixels to train the GMM,
we can use this small number of histogram bins as weighted samples to train the color GMM,
enabling efficient GMM estimation.

\paragraph{Efficient \CRF~inference.}
Our \CRF~formulation satisfies the general form of the fully connected
pairwise \CRF~with Gaussian edge potentials \cite{krahenbuhl2011efficient}.
This enables to use highly efficient Gaussian filtering \cite{AdamsPermutohedral10}
to perform message passing in the mean field framework.
%
Instead of computing the exact Gibbs distribution:
\begin{equation}\label{equ:Gibbs}
  P(\mathbf{X}) \propto \exp \left( - E(\mathbf{x}) \right)
\end{equation}
of the \CRF,
we can find a mean field approximation $Q(X)$ of the true distribution
$P(\mathbf{X})$,
that maximizes the KL-divergence $\mathbf{D}(Q||P)$ among all distributions
$Q$ that can be expressed as a product of the independent marginal,
$Q(\mathbf{X}) = \Pi_i Q_i(X_i)$ \cite{koller2009probabilistic}.
Minimizing the KL-divergence, while constraining $Q(\mathbf{X})$ and
$Q(X_i)$ to be valid distributions, yields the following iterative
update equation:
\begin{equation}\label{equ:update}
  Q_i(x_i = l) = \frac{1}{Z_i} \exp (\sum_{j \neq i} g(i, j) Q_j(l')
    - \psi_i (x_i)),
\end{equation}
where $l,l' \in \{0,1\}$ and $l' = 1 - l$ are binary variables.
Naive estimation of the above equation for all image pixels have
a high computational complexity,
which is quadratic in the number of pixels.
We can rewrite the last term of \equref{equ:update} 
by adding and then subtracting $Q_i(l')$ so that
\begin{equation}\label{equ:updateFilter}
  \sum_{j \neq i} g(i, j) Q_j(l')
  =  \sum_{j \in \mathcal{N}} g(i, j) Q_j(l') - Q_i(l')
\end{equation}
where $\sum_{j \in \mathcal{N}} g(i, j) Q_j(l')$ 
is essentially a Gaussian filter,
whose value for all image pixels can be calculated efficiently using
fast filtering techniques
(\eg~\cite{koller2009probabilistic,krahenbuhl2011efficient}).
This reduces the complexity of the mean field inference,
enabling it to be linear to the number of pixels.


\section{Relationship between fully connected \CRF~and global color model.}
In many figure-ground segmentation methods,
\eg GrabCut \cite{04TogRotherGrabcut},
two (foreground and background) global colour models are explicitly used.
Each colour model is derived from its respective region label.
%\eg~the background colour model is derived from all pixels
%which are labelled as background.
This coupling between the pixel labelling and the global colour
model leads to a very challenging optimisation,
since both parts need to be inferred jointly.
In GrabCut this is done in an iterative fashion,
while %the later work of
\cite{09IccvJointSeg} uses dual decomposition.
%which has the added advantage that, in some cases,
%it might lead to global optimality.
However, both the iterative and dual decomposition optimisations are slow, 
with the latter taking up to minutes per frame.

In this work we replace the global colour model
with a single optimization of fully connected \CRF.
This is based on the insight that a fully connected
\CRF~and a standard low-connected (\eg 8-connected)
\CRF~with associated foreground and background global colour models
are very closely related.
%
This observation suggested that we can avoid the computational
expensive process of global color model estimation,
and use the efficient inference for fully connected \CRF~to
enable very fast computation.


%Let us define the define parts of $g(i,j)$ in \equref{equ:similarity} as
%\begin{eqnarray}
%\hat{g}_1(i,j) = \exp (\frac{-|I_i-I_j|^2}{2 \theta_\beta^2}) \\
%g_2(i,j) = \exp (\frac{-|p_i-p_j|^2}{2 \theta_\gamma^2})
%\end{eqnarray}
%
%In the following we consider a specific form of our fully connected CRF,
%where $\theta_{\alpha} \rightarrow \infty$. This gives our full energy as
%\begin{eqnarray}\label{equ:fullEnergy}
%E(x) = \sum_{i \in N} \psi_i(x_i) + w_1 \sum_{i  < j} g_1(i,j) [x_i \neq x_j] +   \nonumber \\
%w_2 \sum_{i  < j} g_2(i,j) [x_i \neq x_j]
%\end{eqnarray}
%where $N$ is the set of all pixel-indices in the image.
%Note that this is only a minor change to the energy since the spatial
%smoothness term $g_2$ is still present, but only once and not twice.


Let us consider a specific form of our fully connected \CRF,
where $\theta_{\alpha} \rightarrow \infty$, \ie 
\begin{equation}\label{equ:newG1}
  \hat{g}_1(i,j) = \exp \left({-|I_i-I_j|^2}/{\theta_\beta^2}\right).
\end{equation}
This gives our full energy as
\begin{eqnarray}\label{equ:fullEnergy}
E(x) = E_1(x) + w_1 \sum\nolimits_{i  < j} \hat{g}_1(i,j) [x_i \neq x_j], \\
E_1(x) = \sum\nolimits_{i \in \mathcal{N}} \psi_i(x_i) + 
    w_2 \sum\nolimits_{i  < j} g_2(i,j) [x_i \neq x_j].
\end{eqnarray}
Note that this is only a minor change to the energy \equref{equ:energy} 
since the spatial smoothness term $g_2$ is still present, 
but only once and not twice.
%
Let us now define a specific version of the GrabCut functional as follows:
\begin{eqnarray}\label{equ:GrabCut}
E(x,\Theta_B,\Theta_F) = E_1(x) + w_1 \sum_{i \in \mathcal{N}}  
    ( P_B(I_i;\Theta_B) [x_i = 0] \nonumber \\ 
    + P_F(I_i;\Theta_B) [x_i = 1] ).
\end{eqnarray}
Here $\Theta_{F/B}$ are the foreground and background Gaussian
mixture models respectively,
and $P_{F/B}(I_i;\Theta_{F/B})$ is the negative log probability
of the color $I_i$ under the respective Gaussian mixture model.
%Note, the term $\psi_i(x_i)$ is the saliency term which is the same in
%\equref{equ:fullEnergy} and \equref{equ:GrabCut}.
Furthermore, if we choose a small $\theta_\gamma$ then
the spatial smoothing term $g_2$ approximates well
the traditional $8$-connect Ising prior of Grabcut.

The only difference between the GrabCut function 
and the fully connected CRF  is the term $\hat{g}_1$ in
\equref{equ:fullEnergy} and the sum over the negative log probability 
in \equref{equ:GrabCut}.

Let us define the following Parsen-Density estimator:
\begin{eqnarray}
P'_B(I_i) = \frac{1}{|\mathcal{N}_B|} \sum\nolimits_{j \in \mathcal{N}_B} K(I_i,I_j) \\
\textrm{with kernel: } K(I_i,I_j) = -\frac{1}{2} \exp ( \frac{-|I_i-I_j|^2}{2\theta_\beta^2})
\end{eqnarray}
Here $\mathcal{N}_{B}$ is the set of background pixels,
\ie $x_i=0$. Note that $P'_B(I_i)$ is
the average kernel-distance of the color $I_i$ at pixel $i$
with all colors that are assigned to background.
The Parsen-Density estimator for foreground is defined similar:
$P'_F(I_i) = \frac{1}{|\mathcal{N}_F|} \sum_{j \in \mathcal{N}_F} K(I_i,I_j)$.
%
We can now state the following theorem
(see supplemental material for the corresponding proof)
that relates %the two formulations
\equref{equ:fullEnergy} and \equref{equ:GrabCut}.

{\bf Theorem.} The minimizer $x$ of \equref{equ:fullEnergy} and \equref{equ:GrabCut} is the same if we replace the global color-model functions $P_{F}(I_i;\Theta_{F})$ and  $P_{B}(I_i;\Theta_{B})$ in \equref{equ:GrabCut} by unnormalised Parsen-Density estimators $|N_F| P'_F(I_i)$  and  $|N_B| P'_B(I_i)$, respectively.

%{\bf Proof.} (can be in sup.mat)
%Let us look only at the function $\sum_{i  < j} g_1(i,j) [x_i \neq x_j]$, which is part of \equref{equ:fullEnergy} but not \equref{equ:GrabCut}. The minimizer for the function can be re-written as follows:
%\begin{eqnarray}
%\arg \min_x  \sum_{i  < j} g_1(i,j)  [x_i \neq x_j] = \\
%\arg \min_x  \sum_{i  < j} g_1(i,j) [x_i \neq x_j] - \sum_{i < j} g_1(i,j) = \\
%\arg \min_x  \sum_{i  < j} -g_1(i,j)  [x_i = x_j] = \\
%\arg \min_x  \sum_{i \in N} (\sum_{j \in N} -\frac{1}{2} g_1(i,j)  [x_i = x_j] ) = \\
%\arg \min_x  \sum_{i \in N} (\sum_{j \in N_B} K(I_i,I_j)    [x_i = 0] + \nonumber \\
%\quad \sum_{j \in N_F} K(I_i,I_j)    [x_i = 1]) = \label{equ:opti} \\
%\arg \min_x  \sum_{i \in N}  ( |N_B| P'_B(I_i) [x_i = 0] + |N_F| P'_F(I_i) [x_i = 1]  ). \label{equ:Last}
%\end{eqnarray}
%This concludes the proof.
%
%The remaining question is: What is the effect of the "unnormalized" Destiny estimator.  First of all, observe that what we optimize for $g_1$ is \equref{equ:opti}. Ideally we would like to have \equref{equ:Last} for $g_1$ but without the weights $|N_F|$ and $|N_B|$  since this we would correspond to a proper Parsen-Density estimator. It can be seen that if the ratio of $\frac{|N_F|}{|N_B|} = 1$ then we also have a proper density estimation, since all weights can be globally re-scaled. This means that we can computer the global minimizer $x$ for \equref{equ:fullEnergy} and analyze its ratio. If the ratio is close to $1$, it means that it is closer to a proper density estimation. In fact we observe that this ratio is 1.5 and 1.2 for MSRA1000 and GRABCUT benchmarks respectively.

It is very important to note that this discussion is very similar 
to the discussion of the OneCut \cite{OneCutICCV13},
in which they re-write the GrabCut functional 
and remove the "balancing term" from the functional 
in order to guarantee global optimality. 
This balancing term enforces that the segmentations 
with a ratio $\frac{|\mathcal{N}_F|}{|\mathcal{N}_B|} = 1$ are preferred, 
\ie it penalizes segmentations with extreme ratios. 
They observe empirically that removing this term does not affect results. 
We argue that ignoring the balancing term and 
having scaled density estimators is very similar, 
since both approximations are negligible if the ratio 
$\frac{|\mathcal{N}_F|}{|\mathcal{N}_B|} = 1$. 
Furthermore, we also get empirically good results.





%Consider the energy in \equref{equ:energy}.
%By subtracting a large constant $\sum_{i< j} g(i,j)$ and changing
%the summation of the pairwise terms,
%the minimizer $x$ of $E(x)$ is not affected.
%Formally this is written as:
%\begin{align}
%  & \argmin_\mathbf{x} E(\mathbf{x}) \nonumber \\
%= & \argmin_\mathbf{x} \sum_{i \in \mathcal{N}} \psi_i (x_i) +
%\sum_{i < j} g(i, j) [x_i \neq x_j]  - \sum_{i < j} g(i,j) \nonumber \\
%= & \argmin_\mathbf{x} \sum_{i \in \mathcal{N}} \psi_i (x_i) -
%\sum_{i < j} g(i, j) [x_i = x_j] \nonumber \\
%= & \argmin_\mathbf{x} \sum_{i \in \mathcal{N}} \psi_i (x_i) +
%\frac{1}{2} \sum_{i \in \mathcal{N}} \Big( \sum_{j \in \mathcal{N}}
%- g(i, j) [x_i = x_j] \Big) \nonumber
%\end{align}
%
%We define the new unary term for the variable $x_i$ as $\psi_i ' (x_i) = \sum_{j \in \mathcal{N}} - g(i, j) [x_i = x_j]$.
%It can be seen from \equref{equ:similarity} that $g(i,j)$ depends on differences in pixel location, \ie~$|p_i - p_j|$ and image colours, \ie~$|I_i - I_j|$. The differences on pixel location have the effect of smoothing the labeling and are ignored in the following.
%Concerning the differences in image colour we obtain the term:
%\begin{equation}
%\psi_i ' (x_i) = \sum_{j \in \mathcal{N}} - exp (\frac{-|I_i - I_j|^2}{2\theta_\beta^2}) [x_i = x_j] \ .
%\label{equ_psid}
%\end{equation}
%This unary term evaluates the color at a pixel $i$, \ie~$I_i$, under a specific unnormalised global color model. This color model is an
%unnormalised Parzen-window estimator with an ``exp-quadratic'' kernel. We therefore define a Parzen-window density estimator $f$ for foreground color as:
%\begin{equation}
%f(I_i) = \frac{1}{n} \sum_{j \in \mathcal{N}} K(I_i - I_j) [1 = x_j] \ ,
%\label{equ_psid2}
%\end{equation}
%where $n$ is the number of all foreground pixels, and kernel
%$K(*) = -exp(\frac{-|*|^2}{2\theta_\beta^2})$.
%The Parzen-window density estimator $f$ for background follows analogously.
%We call this an unnormalized Parzen window estimator,
%since the difference between \equref{equ_psid} and \equref{equ_psid2}
%lies in the normalization $\frac{1}{n}$.
%This depends on the labeling, so it can not be determined up-front.
%However, we note that if the number of foreground and
%background pixels in the final solution is the same,
%the normalization can be ignored.
%We have found this to be the case often in real world scenarios,
%since the bounding box around the object is generally tight.
%For instance, in the datasets we use for testing, this ratio is $1.5$ and $1.2$ for \DataMSRA~ and \DataGrabCut~ benchmarks respectively.

\section{Experiments}\label{sec:Experiments}

We extensively evaluate our method on two well known benchmarks
(\DataMSRA~and \DataGrabCut),
and compare our results with the \sArt~alternatives \cite{04TogRotherGrabcut,OneCutICCV13},
in terms of segmentation quality and efficiency.

\newcommand{\Coln}[2]{\multicolumn{#1}{|c}{{#2}}} % \Coln{2}{sample}
\newcommand{\Colnn}[2]{\multicolumn{#1}{c|}{{#2}}} % \Coln{2}{sample}
\renewcommand{\Rows}[2]{\multirow{#1}{*}{#2}}
\begin{table}[b]
    \centering
    \begin{tabular}{c|c|c|c|c|c} \hline\hline
        \Colnn{2}{}    &\Coln{2}{\DataMSRA}&\Coln{2}{\DataGrabCut} \\ \cline{3-6}
        \Colnn{2}{}  &$F_\beta$& Time  &$F_\beta$& Time \\ \hline
\Rows{3}{CPU}&\GrabCut & 0.945 & 1.22  & 0.909   & 2.02 \\ \cline{2-6}
             &\OneCut  & 0.949 & 0.664 & 0.900   & 1.70 \\ \cline{2-6}
             & Ours    & 0.955 & 0.075 & 0.928   & 0.143\\ \hline
        GrabCut  & \cite{CudaGrabCut}(GMM) & 0.949   & 0.072 &  0.927   & 0.130\\ \cline{2-6}
        CUDA    & \cite{CudaGrabCut}(Hist.)& 0.889    & 0.065 &  0.714    & 0.116\\ \hline
       %\SalGC~+ MeanField& 0.924    & 0.076 &  0.813    & 0.145\\ \hline
       %OursGPU          &          &       &           &      \\ \hline
       \hline
    \end{tabular}\\ \vspace{.05in}
    \caption{Average precision, recall, $F_\beta$, and processing time (measured in seconds)
        on two well known benchmarks (see \figref{fig:Samples} for sample results).
        Tested on a desktop computer with Intel Xeon E5645 2.40GHz CUP,
        GeForce GTX 770 GPU and 4 GB RAM.
        % Results for both dataset could be downloaded from: http://mmcheng.net/mftp/Papers/RealTimeGrabCutResults.zip
    }\label{tab:Results}
\end{table}

%\renewcommand{\addFigure}[1]{\includegraphics[width=0.131\textwidth]{SampleD#1}}
%\renewcommand{\addFigures}[3]{\rotatebox{90}{\hspace{#2} #3} & \addFigure{#1.jpg} & \addFigure{#1_CudaG.png} & \addFigure{#1_CudaH.png} & \addFigure{#1_GC.png} & \addFigure{#1_OneCut.png} & \addFigure{#1_GCMF.png} & \addFigure{#1_GT.png}}
\begin{figure*}[t!]
    \centering
%    \begin{tabular*}{\linewidth}{cccccccc}
%        \addFigures{2/0_7_7923}{.15in}{(a)} \\
%        %\addFigures{2/0_12_12921}{.11in}{(b)} \\
%        \addFigures{2/0_21_21299}{.15in}{(b)} \\
%        \addFigures{2/3_106_106258}{.4in}{(c)} \\
%        %\addFigures{2/3_106_106263}{.20in}{(e)} \\
%        \addFigures{2/4_136_136642}{.4in}{(d)} \\
%        \addFigures{2/5_145_145486}{.17in}{(e)} \\ \vspace{-.18in} \\
%        \hline \vspace{-.14in} \\
%        \addFigures{1/124080}{.14in}{(f)} \\
%        \addFigures{1/153093}{.14in}{(g)} \\
%        \addFigures{1/banana2}{.15in}{(h)} \\
%        %\addFigures{1/grave}{.24in}{(k)} \\
%        & input & (i) & (ii) & (iii) & (iv) & (v) & g-truth
%    \end{tabular*}
    \includegraphics[width=\textwidth]{ImgN/ResultsSample.pdf}
    \caption{Sample results for images from  \DataMSRA~(a-g) and
        \DataGrabCut~(h-k) benchmarks,
        using different methods: (i) \GrabCutGPU GMM), (ii) \GrabCutGPU Hist.),
        (iii) \GrabCut, (iv) \OneCut, and (v) Ours.
    }\label{fig:Samples}
\end{figure*}


%\renewcommand{\addFigure}[1]{\includegraphics[height=0.135\textwidth]{TopFail/{#1}}}
\begin{figure*}[t!]
    \centering
%    \begin{tabular*}{\linewidth}{ccccc|ccc}
%        \begin{sideways} ~ ~ input \end{sideways} &
%        \addFigure{16_1_30_30051.jpg} &
%        \addFigure{17_1_30_30277.jpg} &
%        \addFigure{43_1_37_37508.jpg} & & &
%        \addFigure{6_0_9_9496.jpg} &
%        \addFigure{44_1_50_50477.jpg} \\
%        \begin{sideways} ~ ~ g-truth \end{sideways} &
%        \addFigure{16_1_30_30051_GT.png} &
%        \addFigure{17_1_30_30277_GT.png} &
%        \addFigure{43_1_37_37508_GT.png} &   & &
%        \addFigure{6_0_9_9496_GT.png} &
%        \addFigure{44_1_50_50477_GT.png} \\
%        \begin{sideways} ~our results \end{sideways} &
%        \addFigure{16_1_30_30051_GCMF.png} &
%        \addFigure{17_1_30_30277_GCMF.png} &
%        \addFigure{43_1_37_37508_GCMF.png} &   & &
%        \addFigure{6_0_9_9496_GCMF.png} &
%        \addFigure{44_1_50_50477_GCMF.png} \\
%        \multicolumn{5}{c|}{(a) g-truth is of high quality} &
%        \multicolumn{3}{c}{(b) g-truth is of low quality}
%    \end{tabular*}
    \includegraphics[width=\textwidth]{ImgN/Failing2.pdf}
    \caption{Examples for top 50 `failing examples' shows that our results
        are very often comparable to ground truth annotations:
        (a) ground truth mask in MSRA1000 benchmark \cite{09CvprFTSaliency} is preferred,
        (b) our segmentation results is preferred.
    }\label{fig:TopFailingCase2}
\end{figure*}

\subsection{Segmentation Quality Comparison}\label{sec:CompareQulity}
We evaluate the binary segmentation performance of each method given
a user bounding box around the object of interest.
The \DataGrabCut~ benchmark contains 50 images with bounding box and
binary mask annotations.
For \DataMSRA~benchmark,
we export the bounding box annotation from its binary mask ground truth,
and use this bounding box as input to each method.

To objectively evaluate our method, we compare our results with the
two other \sArt~methods for bounding box-based figure-ground segmentation
\ie~GrabCut \cite{04TogRotherGrabcut} and OneCut\cite{OneCutICCV13}.
For GrabCut, we use the CPU implementation from OpenCV \cite{bradski2008learning}
and two highly optimised commercial GPU implementations from Nvidia \cite{CudaGrabCut}
(one uses a GMM color model and another one uses a histogram color model).
Average precision, recall, and F-Measure are compared against the
entire ground truth datasets,
with F-Measure defined as harmonic mean of precision and recall:
\begin{equation}\label{equ:FMeasure}
  F_\beta = \frac{(1+\beta^2)\mbox{Precision} \times \mbox{Recall}}
        {\beta^2 \times \mbox{Precision} + \mbox{Recall}}.
\end{equation}

\tabref{tab:Results} shows the average precision, recall, and $F_\beta$
values (we use $\beta^2 = 0.3$ as in \cite{09CvprFTSaliency,11CvprSalRC,OneCutICCV13}).
Visual examples of input bounding boxes and segmentation results are
shown in \figref{fig:Samples}.
Among the baseline methods, the commercial GPU GrabCut implementation
from Nvidia \cite{CudaGrabCut} achieves the best segmentation results.
%
Although faster computationally,
the histogram representation has limited ability to precisely capture
appearance differences,
resulting in significantly worse segmentation results than the
GMM based representation.
%
The comparison between the two versions of Nvidia's commercial implementation
clearly verifies our discussion in \secref{sec:Representation}.
%
In both the benchmarks,
our method consistently produces better segmentation results
than all other alternatives.

The adoption of the fully connected pairwise term \cite{krahenbuhl2011efficient},
enables our methods to capture correlation between pixels with similar appearance
even if they are spatially further away from each other.
%
Modelling such long distance consistency constraints,
rather than only modelling $4$ or $8$ neighbours for each pixel,
enables our method to produce fine detailed results which could
not easily be achieved by \sArt~interactive figure-ground
segmentation tools such as GrabCut \cite{04TogRotherGrabcut} or OneCut \cite{OneCutICCV13}.
Notice that the fine details of the target object regions are successfully
segmented in \figref{fig:Samples}(b) and \figref{fig:Samples}(d).

Due to explicitly enforcing color separation between foreground
and background, similar in spirit to enforcing the foreground to become salient,
only OneCut provides results similar to our own.
Both methods recover more accurate fine object boundaries
than the other methods, \eg~\figref{fig:Samples}(a-c).
However, on average, our method produces better results than
OneCut, possibly due to the more powerful color model representation.
%
Extending the OneCut method to incorporate GMMs
for representing colours
is non-trivial and known to be a NP-hard problem \cite{OneCutICCV13,09IccvJointSeg}.


\subsection{Computational time}
As shown in \tabref{tab:Results} our method is \textbf{$10\times$}
faster than any other current CPU based implementation.
Implementing a GPU version to fully explore the parallel nature of the algorithm is a promising direction for future work.

Due to the use of the very efficient GMM representation of \cite{13IccvChengSaliency},
the most computationally expensive part of our algorithm is the mean field based
inference \cite{krahenbuhl2011efficient},
which could be efficiently solved using advanced bilateral filtering techniques
\cite{AdamsPermutohedral10}.
It is worth mentioning that the mean field based inference is an intrinsically parallel algorithm, and
thus can be made further efficient using graphics hardware (GPU) or multi-core CPUs.
In our current implementation we use {\sc openmp} instructions to
parallelize across multiple CPU cores.


\subsection{Limitations}


%\renewcommand{\addFigure}[2]{\includegraphics[height=#1\textwidth]{GtShift/{#2}}}
\begin{figure}[b]
  \centering
%  \addFigure{.148}{35_98012_Ilu.png}
%  \addFigure{.148}{7_95684_Ilu.png}
%  \addFigure{.148}{22_95588_Ilu.png}\\ \vspace{.01in}
%  \addFigure{.162}{38_97915_Ilu.png}
%  \addFigure{.162}{3_95642_Ilu.png}
%  \addFigure{.162}{11_97770_Ilu.png}
  \includegraphics[width=\linewidth]{ImgN/Failing1.pdf}
  \\
  \caption{We found ground truth errors in the MSRA1000 benchmark \cite{09CvprFTSaliency}
    as shown above (the red lines on top of each image illustrate the contour of the ground truth mask).
    After a manual check, we found 9 such errors
    from all the annotations of 1000 images,
    %their ranking in our top `failing cases' list being
    %3, 7, 10, 11, 21, 22, 35, 38, and 52, i.e.
    all such ground truth errors are found in the top 6\% `failing cases'.
  }\label{fig:TopFailingCase1}
\end{figure}


The high accuracy of our method ($F_\beta = 95.5\%$ for the
\DataMSRA~benchmark and $F_\beta = 92.8\%$ for the \DataGrabCut~benchmark),
indicates that most results of our methods are very similar
to the ground truth.
%
This make it feasible to visualise and study all the clearly
failing examples even for a large benchmark such as \DataMSRA.
%\vv{this sentence needs to be rewritten}
We do this by studying the top 50 `failing examples',
which are automatically selected as the results with lowest $F_\beta$ values
according to ground truth.
%
We found that the \DataMSRA~benchmark,
although used as standard benchmark for figure-ground segmentation
(having currently 700+ citations),
contains some clear ground truth errors as shown in \figref{fig:TopFailingCase1}
(where ground truth masks appear shifted due to unknown reasons).
%
Note that, besides these errors (less than $1\%$),
which we could easily detect from top $6\%$ `failing cases',
most of the other ground truth annotations are of very high quality.


\figref{fig:TopFailingCase2}(a) shows typical examples of top 'failing cases'.
%
In the first example, the shadow part occurs only inside the bounding box
and its appearance is quite different compared with pixels outside the bounding boxes, forcing the algorithm consider it as an object region.
%
In the other two failure cases,
some foreground regions have a large portion of similar
appearance regions outside the bounding box,
which confuses the algorithm and leads to missing regions
for the target object.
%
%Encouraging saliency (or figure-ground color separations)
%might result in some isolated small regions
%(for example, if one zooms into the results,
%small dots can be seen in results of our method and OneCut),
%when compared with GrabCut.
%These unwanted small regions, might be removed by simple post-processing,
%such as median filtering.
%
%After removing the images with incorrect ground truth data,
%we perform a user study for the other 42 images
%in the top 50 `failing cases'.
%
%For each image, we show our results and ground truth results in random order,
%and ask three users (university student major in computer science)
%to select his/her preferred segmentation given the illustrated bounding box.
%
We went through top $50$ 'failing cases' and found $12$ cases
with low quality (see also \figref{fig:TopFailingCase2}) and
$8$ cases with wrong mistakes (see also \figref{fig:TopFailingCase1}).


\section{Conclusions} \label{sec:Evaluation}
We have presented an efficient figure-ground image segmentation method,
which simultaneously models the salient object prior assumption
and uses fully connected \CRF~ for effective label consistency modelling.
Formally, we show that: a fully connected \CRF,
as used in this work, and a standard low-connected, \eg~8-connected,
\CRF~with associated foreground and background global colour models 
are very related.
%
This motivated us to replace the global colour model in the traditional
GrabCut framework with a single optimization of a fully connected \CRF.
%
Extensive evaluation on two well known benchmarks,
\DataMSRA~and \DataGrabCut,
demonstrates that our methods is able to get more accurate
segmentation results compared to other \sArt~alternative methods,
while achieving an order of magnitude speed-up
with respect to the closest competitor.

Further introducing a bounding box prior \cite{lempitsky2009image},
or other CPU high order terms \cite{vineet2012filter}
could be useful future additions to our framework.
%
Currently, the weight $w_s$ in \equref{equ:Sal} is set to a
fixed value for the entire dataset,
so another interesting area of future work is to learn
to compute image specific weights.

{\small \bibliographystyle{ieee} \bibliography{RealTimeGrabCut}}


\end{document}
