\documentclass[10pt,onecolumn,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{Supplemental Materials for `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

\section{Relationship between fully connected \CRF~and global color model.}
In many figure-ground segmentation methods,
such as GrabCut \cite{04TogRotherGrabcut},
two global colour models are explicitly used,
one for the foreground and one for background.
Each colour model is derived from the respective region label,
e.g. 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 (e.g. 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 fast computation.


Let us define the define parts of $g(i,j)$ in \equref{equ:similarity} as
\begin{eqnarray}
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 now define a specific version of the GrabCut functional as follows:
\begin{eqnarray}\label{equ:GrabCut}
E(x,\Theta_B,\Theta_F) = \sum_{i \in N} \psi_i(x_i)
    + w_2 \sum_{i  < j} g_2(i,j) [x_i \neq x_j]  + \nonumber \\
    w_1 \sum_{i \in N}  ( P_B(I_i;\Theta_B) [x_i = 0] + 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 large $\theta_\gamma$ then
the spatial smoothing term $g_2$ approximates well
the traditional $8$-connect Ising prior of Grabcut.

You can observe that the only difference between the GrabCut
functional and the fully connected CRF is the term $g_1$ in
\equref{equ:fullEnergy} and the sum over color model neg. log.
likelihoods in \equref{equ:GrabCut}.

Let us define the following Parsen-Density estimator:
\begin{eqnarray}
P'_B(I_i) = \frac{1}{|N_B|} \sum_{j \in N_B} K(I_i,I_j) \\
\textrm{with kernel:} K(a,b) = -\frac{1}{2} \exp ( \frac{-|a-b|^2}{2\theta_\beta^2})
\end{eqnarray}
Here $N_{B}$ is the set of pixel-indices
which have an associated background label,
\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}{|N_F|} \sum_{j \in N_F} K(I_i,I_j)$.


We can now state the following theorem 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 in the OneCut article \cite{OneCutICCV13}. In the OneCut article 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{|N_F|}{|N_B|} = 1$ are preferred, i.e. 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 incorrectly scaled density estimators is very similar, since both approximations  are negligible if the ratio $\frac{|N_F|}{|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, i.e. $|p_i - p_j|$ and image colours, i.e. $|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$, i.e. $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.

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


\end{document}
