\documentclass[10pt,twocolumn,letterpaper]{article}

\usepackage{cvpr}
\usepackage{times}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{dsfont}
\usepackage{algorithm}
\usepackage{cite}
\usepackage{algorithmic}
\usepackage{multirow}
\usepackage{overpic}
\usepackage{subfigure}
\usepackage{soul}
\usepackage[normalem]{ulem} 
% Include other packages here, before hyperref.

% If you comment hyperref and then uncomment it, you should delete
% egpaper.aux before re-running latex.  (Or just hit 'q' on the first latex
% run, let it finish, and you should be clear).
\usepackage[pagebackref=true,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{373} % *** Enter the CVPR Paper ID here
\def\httilde{\mbox{\tt\raisebox{-.5ex}{\symbol{126}}}}

\graphicspath{{./Imgs/}}

\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{\cmm}[1]{#1}
%\newcommand{\dnew}[1]{#1}
\newcommand{\todo}[1]{{\textcolor{red}{#1}}}
\newcommand{\sArt}{state-of-the-art}
\newcommand{\myPara}[1]{\vspace{.15in}\textbf{#1}}
\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$}


% A general point please use the discipline of bold for vectors, Cap bold for matrices and non bold for scalar


% Pages are numbered in submission mode, and unnumbered in camera-ready
\ifcvprfinal\pagestyle{empty}\fi

\begin{document}

%%%%%%%%% TITLE
\title{BING: Binarized Normed Gradients for Objectness Estimation at 300fps}

\author{Ming-Ming Cheng \quad Ziming Zhang \quad Philip~Torr\\
Oxford Brookes Vision Group, Oxford, United Kingdom\\
{\tt\small http://mmcheng.net/}}

\maketitle
%\thispagestyle{empty}

%%%%%%%%% ABSTRACT
\begin{abstract}
    Training a generic objectness measure to produce a small set of candidate object windows,
    has been shown to speed up the classical sliding window object detection paradigm.
    We observe that generic objects with well-defined closed boundary,
    share surprisingly strong correlation in normed gradients space,
    when resizing their corresponding image windows into a small fixed size.
    Based on this observation and computational reasons,
    we propose to resize an image window to
    $8 \times 8$ and use the normed gradients as a simple 64D feature to describe it,
    %
    for explicitly training a generic objectness measure.
    %
    We further show how the binarized version of this feature,
    namely binarized normed gradients (BING),
    can be used for efficient objectness estimation,
    which requires only a few atomic operations ({\eg \sc add, bitwise shift}, etc.).
    %
    Experiments on the challenging PASCAL VOC 2007 dataset show that our method
    efficiently (300fps on a single laptop CPU) generates
    a small set of category-independent, high quality object windows,
    yielding $96.2\%$ object detection rate (DR) with 1,000 proposals.
    With increase of the numbers of proposals and color spaces for computing BING features,
    our performance can be further improved to $99.5\%$ DR.
\end{abstract}


\section{Introduction}


As one of the most important areas in computer vision,
object detection has made great strides in recent years.
%
However, most \sArt~detectors still require each \emph{category specific} classifiers
to evaluate many image windows in a sliding window fashion \cite{dalal2005histograms,felzenszwalb2010object}.
%
In order to reduce the number of windows each classifier needs to consider,
training an objectness measure which is \emph{generic over categories}
has recently becomes popular
\cite{alexe2010object,endres2010category,van2011segmentation,zhang2011proposal,alexe2012measuring,uijlings2013selective,endres2013category}.
{\em Objectness} is usually represented as a value which
reflects how likely an image window covers an object of \emph{any category} \cite{alexe2012measuring}.
%
A generic objectness measure has great potential to be used in a pre-filtering process to
significantly improve:
i) the computational efficiency by reducing the search space, and
ii) the detection accuracy by allowing the usage of strong classifiers during testing.
However, designing a good generic objectness measure method is difficult, which should:
\begin{itemize}
  \item achieve \textbf{high object detection rate} (DR), as any undetected objects at this stage
    cannot be recovered later;
  \item produce \textbf{small number of proposals} for reducing computational time of subsequent detectors; % during testing
  \item obtain \textbf{high computational efficiency} so that the method can be easily
    involved in various applications, especially for realtime and large-scale applications;
  \item have \textbf{good generalization ability} to unseen object categories,
    so that the proposals can be reused by many category specific detectors to greatly reduce
    the computation for each of them.% \sout{for multi-class object detection}.
\end{itemize}
To the best of our knowledge, no prior method can  satisfy all these ambitious goals simultaneously.

%so far there is no such a method that satisfies these ambitious goals simultaneously.



Research from cognitive psychology \cite{55ARP/Teuber_physiological,04nature/Wolfe_attributesVisual}
and neurobiology~\cite{85HN/KochVisualAttention,95ARN/DesimoneNeuralMachanisms}
suggest that humans have a strong ability to perceive objects before identifying them.
%
Based on the human reaction time that is observed and the biological signal transmission time that is estimated,
human attention theories hypothesize that the human vision system processes only
parts of an image in detail, while leaving others nearly unprocessed.
%
This further suggests that before identifying objects, there are simple mechanisms in
the human vision system to select possible object locations.

In this paper, we propose a surprisingly simple and powerful feature ``BING''
to help the search for objects using objectness scores.
%
Our work is motivated by the things-versus-stuff distinction
\cite{forsyth1996finding,heitz2008learning,alexe2012measuring}:
as opposed to amorphous background stuff,
objects are stand-alone things with well-defined closed boundaries and centers.
%
We observe that generic objects with well-defined closed boundaries
share surprisingly strong correlation in the normed gradient space
(see \figref{img:NG} and \secref{sec:Methodology}),
after resizing of their corresponding
image windows to small fixed size (\eg $8 \times 8$).
%
Therefore, in order to efficiently quantify the objectness of an image window,
we resize it to \sz~ and use the normed gradients
as a simple 64D feature for learning a generic objectness measure in a cascaded \svm~framework.
%
We further show how the binarized version of the NG feature,
namely binarized normed gradients (\textbf{BING}) feature,
can be used for efficient objectness estimation of image windows,
which requires only a few atomic CPU operations ({\ie \sc add, bitwise shift}, etc.).
The  BING feature's simplicity, contrast with recent state of the art techniques
\cite{alexe2012measuring,uijlings2013selective,endres2013category}
which seek increasingly sophisticated  features to obtain greater discrimination,
while using advanced speed up techniques to make the computational time tractable.
%This simplicity, allows us to achieve large improvements in computational
%time, without  sacrificing performance (the performance actually improves).


We have extensively evaluated our method on the PASCAL VOC2007 dataset \cite{pascal-voc-2007}.
The experimental results show that our method efficiently (300fps on a single laptop CPU)
generates a small set of data-driven, category-independent, high quality object windows,
yielding $96.2\%$ detection rate (DR) with 1,000 windows ($\approx 0.2\%$ of full sliding windows).
With increase of the number of object windows to 5,000,
and estimating objectness in 3 different color spaces, our method can achieve $99.5\%$ DR.
%
Following \cite{alexe2012measuring,uijlings2013selective,endres2013category},
we also verify the generalization ability of our method.
When training our objectness measure on 6 object categories
and testing on other 14 \emph{unseen} categories,
we observed similar high performance as in standard settings (see \figref{fig:PlotDR}).
%
Compared to most popular alternatives
\cite{alexe2012measuring,uijlings2013selective,endres2013category},
the BING features allow us to  achieves better DR using a smaller set of proposals,
is much simpler and $1000+$ times faster,
while being able to predict \emph{unseen} categories.
This fulfills afore mentioned requirements of a good objectness detector.
%
Our source code will be published with the paper.% immediately after paper acceptance.


\section{Related works}

Being able to perceive objects before identifying them
is closely related to bottom up visual attention (saliency).
According to how saliency is defined, we broadly classify
the related research into three categories: fixation prediction,
salient object detection, and objectness proposal generation.

\vspace{-.1in}
\paragraph{Fixation prediction} models aim at predicting saliency points
of human eye movement \cite{borji2012quantitative,Judd12}.
Inspired by neurobiology research about early primate visual system,
Itti \etal \cite{98pami/Itti} proposed one of the first
computational models for saliency detection,
which estimates center-surrounded difference across multi-scale image features.
Ma and Zhang~\cite{03ACMMM/Ma_Contrast-based} proposed a fuzzy growing model
to analyze local contrast based saliency.
%
Harel et al.~\cite{nips/HarelKP06} proposed normalizing center-surrounded
feature maps for highlighting conspicuous parts.
Although fixation point prediction models have achieved remarkable development,
the prediction results tends to highlight edges and corners rather than
the entire objects. Thus, these models are not suitable for generating object proposals for detection purpose.


\vspace{-.1in}
\paragraph{Salient object detection}
models try to detect the most salient and attention-grabbing object in a scene,
and then segment the whole extent of that object \cite{borjisalient}.
%
Liu \etal \cite{10pami/Liu_Learning} combined local, regional, and global saliency
measurements in a CRF framework and derived a binary segmentation.
Achanta \etal \cite{09cvpr/Achanta_FTSaliency} localized salient regions using a frequency-tuned approach.
%
Cheng \etal \cite{11cvpr/Cheng_Saliency,ChengPAMI} proposed a salient object %\cite{ChengGroup}
detection and segmentation method based on region contrast analysis and iterative
graph based segmentation.
%
More recent research also tried to produce high quality saliency maps
in a filtering based framework \cite{PerazziKPH12} or consider
hierarchical structures \cite{YanJia13}.
%
Such salient object segmentation for simple images with large, centered objects achieved great success,
and it can be used as a cheap tool to process large number of Internet images or
build robust applications \cite{tog09/ChenCT_Sketch2Photo,11tog/HuangArcimboldo,11tog/ChiaColorization,he2012mobile}
by automatically selecting good results \cite{ChengPAMI,ChengGroup}.
%
However, these approaches are less likely to work for complicated
images where many objects are presented and they are rarely dominant
(e.g. VOC \cite{pascal-voc-2007}).


\vspace{-.1in}
\paragraph{Objectness proposal generation} methods avoid making decisions
early on, by proposing a small number (e.g. 1,000) of category-independent proposals,
that are expected to cover all objects in an image \cite{alexe2012measuring,uijlings2013selective,endres2013category}.
Producing rough segmentations \cite{endres2010category,carreira2012cpmc}
as object proposals has been shown to be
an effective way of reducing search spaces for category-specific classifiers,
whilst allowing the usage of strong classifiers to improve accuracy.
However, these two methods are computationally expensive,
requiring 2-7 minutes per image.
%
Alexe \etal \cite{alexe2012measuring} proposed a cue integration approach
to get better prediction performance more efficiently.
Zhang \etal \cite{zhang2011proposal} proposed a cascaded ranking SVM approach
with orientated gradient feature for efficient proposal generation.
Uijlings \etal \cite{uijlings2013selective} proposed a selective
search approach to get higher prediction performance.
%
We propose a simple and intuitive method which generally achieves
better detection performance than others,
and is 1,000+ times faster than most popular alternatives
\cite{alexe2012measuring,uijlings2013selective,endres2013category} (see \secref{sec:Experiments}).


In addition, for efficient sliding window object detection, keeping
the computational cost feasible is very important \cite{maji2008classification,vedaldi2012efficient}.
Lampert \etal \cite{lampert2008beyond}
presented an elegant branch-and-bound scheme for detection.
However, it can only be used to speed up classifiers that users can provide a good bound
on highest score. Also, some other efficient classifiers \cite{dalal2005histograms} and
approximate kernels \cite{maji2008classification,vedaldi2012efficient}
have been proposed.
These methods aim to reduce computational cost of evaluating one window,
and naturally can be combined with objectness proposal methods to further reduce the cost.




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

Inspired by the ability of human vision system which efficiently perceives objects before identifying them
\cite{55ARP/Teuber_physiological,04nature/Wolfe_attributesVisual,85HN/KochVisualAttention,95ARN/DesimoneNeuralMachanisms},
we introduce a simple 64D normed gradients (NG) feature (\secref{sec:BG}),
as well as its binary approximation, \ie binarized normed gradients (BING) feature (\secref{sec:BING}),
for efficiently capturing the objectness of an image window.

%We follow the general idea of the two stages cascaded \svm~design in \cite{zhang2011proposal}.
To find generic objects within an image, we scan over
%explicitly represent an image as a collection of overlapping windows
various \emph{quantized sizes} (scales and aspect ratios\footnote{In all experiments, we test
36 quantized target window sizes $\{(W_o, H_o)\}$, where $W_o, H_o \in \{10, 20, 40, 80, 160, 320\}$.
We resize the input image to 36 sizes so that \sz~ windows in the resized smaller images
(from which we extract features), correspond to target windows.}).
%The location $l$ of a window is given by its size $i$ and position $(x, y)$.
%Thus the entire image can be represented as the collection of feature vectors $\{\mathbf{g}_l\}$,
%where $\mathbf{g}_l$ is a NG feature at location $l = (i,x,y)$.
%During testing,
Each window is scored with a linear model $\mathbf{w}\in \mathbb{R}^{64}$ (\secref{sec:Learning}),
\begin{equation}\label{equ:score}
  s_l = \langle\mathbf{w},\mathbf{g}_l\rangle,  \vspace{-.05in}
\end{equation}
\begin{equation}\label{equ:location}
  l = (i,x,y),
\end{equation}
where $s_l$, $\mathbf{g}_l$, $l$, $i$ and $(x,y)$ are filter score,
NG feature, location, size and position of a window respectively.
Using non-maximal suppression (NMS), we select a
small set of proposals from each size $i$.
%
Some sizes (\eg $10 \times 500$) are less likely than others to
contain an object instance  (\eg $100 \times 100$).
Thus we define the
%To allow proposals from the quantized sizes which occur more often
%to be globally top ranked in the final proposal set,
%we further re-rank these proposals according to their calibrated scores (\ie
objectness score (\ie calibrated filter score) as
\begin{equation}\label{equ:calibration}
  o_l = v_i \cdot s_l + t_i,
\end{equation}
where $v_i, t_i \in \mathbb{R}$ are sperately learnt  coefficient and a bias terms
for each quantised size $i$ (\secref{sec:Learning}).
Note that  calibration using \equref{equ:calibration}, although very fast, is only required
when re-ranking the small set of final proposals.


\subsection{Normed gradients (NG) and objectness}\label{sec:BG}


%As opposed to amorphous background stuff,
Objects are stand-alone things with well-defined closed boundaries and centers
\cite{forsyth1996finding,heitz2008learning,alexe2012measuring}.
%
When resizing windows corresponding to real world objects to a small fixed size
(\eg $8 \times 8$, chosen for computational reasons that will be explained in \secref{sec:BING}),
the norm (\ie magnitude) of the corresponding image gradients shows a strong correlation,
because of the little variation that closed boundaries could present in such abstracted view.
As demonstrated in \figref{img:NG},
although the cruise ship and the person have huge difference in terms of color,
shape, texture, illumination \etc,
they do share clear correlation in normed gradient space.
%
To utilize this observation for efficiently predicting the existence of object instances,
%\ie the objectness scores of image windows,
we firstly resize the input image to different \emph{quantized sizes}
%(scale and aspect ration, see \secref{sec:details} and \figref{img:NG}b)
and calculate the normed gradients of each resized image.
%
The values in an \sz~ region of these resized normed gradients maps are defined as a
64D \textbf{\emph{normed gradients (NG)}} feature of its corresponding window.


Our NG feature, as a dense and compact objectness feature
for an image window, has several advantages.
%
Firstly, no matter how an object changes its position, scale and aspect ratio,
its corresponding NG feature will remain roughly unchanged because of
the normalized support region of this feature.
In other words, NG features are insensitive to change of translation, scale and aspect ratio,
which will be very useful for detecting objects of  arbitrary categories. %different object instances.
And these insensitivity properties are what a good objectness proposal generation method should have.
%
Secondly, the dense compact representation of the NG feature makes it
very efficient to be calculated and verified,
thus having great potential to be involved in realtime applications.


The cost of introducing such advantages to NG feature is the loss of discriminative ability.
Lucky, the resulted false-positives will be processed by subsequent category specific detectors.
In \secref{sec:Experiments}, we show that our method results in a small
set of high quality proposals that cover $96.2\%$ true object
windows in the challenging VOC2007 dataset.


\begin{figure}
  \centering
  \begin{overpic}[width=\linewidth]{TAG.pdf}
    \put(10,43){(a) source image}
    \put(1,0){(b) normed gradients maps}
    \put(58,54){(c) $8 \times 8$ NG features}
    \put(52,0){(d) learned model $\mathbf{w} \in \mathbb{R}^{8\times 8}$}
  \end{overpic}\\
  \caption{Although object (red) and non-object (green) windows
    present huge variation in the image space (a),
    in proper scales and aspect ratios where they correspond to a small fixed size (b),
    their corresponding normed gradients, \ie a NG feature (c), share strong correlation.
    %
    We learn a single 64D linear model (d) for selecting object proposals
    based on their NG features.
  }\label{img:NG}
\end{figure}


\subsection{Learning objectness measurement with NG}\label{sec:Learning}

To learn an objectness measure of image windows,
we follow the general idea of the two stages cascaded \svm \cite{zhang2011proposal}.

\vspace{-.1in}
\paragraph{Stage I.}
We learn a single model $\mathbf{w}$ for \equref{equ:score}  using linear \svm\cite{fan2008liblinear}.
%
NG features of the ground truth object windows and random sampled background
windows are used as positive and negative training samples respectively.


\vspace{-.1in}
\paragraph{Stage II.}
To learn $v_i$ and $t_i$ in \equref{equ:calibration} using a linear \svm~\cite{fan2008liblinear},
we evaluate \equref{equ:score} at size $i$ for training images
and use the selected (NMS) proposals as training samples,
their filter scores as 1D features,
and check their labeling using training image annotations
(see \secref{sec:Experiments} for evaluation criteria).


\vspace{-.15in}
\paragraph{Discussion.} As illustrated in \figref{img:NG}d,
the learned  linear model $\mathbf{w}$ (see \secref{sec:Experiments}
for experimental settings), looks %remarkably
similar  to the multi-size center-surrounded patterns\cite{98pami/Itti}
hypothesized as  biologically plausible architecture of primates
\cite{85HN/KochVisualAttention,04nature/Wolfe_attributesVisual,gottlieb1998representation}.
The large weights along the borders of $\mathbf{w}$ favor a boundary that separate
an object (center) from its background (surrounded).
Compared to manually designed center surround patterns \cite{98pami/Itti},
our learned $\mathbf{w}$  captures a more sophisticated, natural prior. For example,
lower object regions  are more often occluded   than upper parts. This is
represented by $\mathbf{w}$ placing  less confidence in the lower regions.


%{Binarization for efficient inference}
\subsection{Binarized normed gradients (BING)}\label{sec:BING}

To make use of recent advantages in model binary approximation
\cite{hare2012efficient,szhengFacialFG2013},
we propose an accelerated version of NG feature,
namely binarized normed gradients (BING),
to speed up the feature extraction and testing process.
%
Our learned linear model $\mathbf{w}\in\mathbb{R}^{64}$ can be approximated with a set of basis
vectors $\textbf{w} \approx \sum_{j=1}^{N_w} \beta_j \mathbf{a}_j$ using \algref{alg:Model},
where $N_w$ denotes the number of basis vectors,
$\mathbf{a}_j \in \{-1, 1\}^{64}$ denotes a basis vector,
and $\beta_j\in\mathbb{R}$ denotes the corresponding coefficient.
By further representing each $\mathbf{a}_j$ using a binary vector and its complement:
$\mathbf{a}_j = \mathbf{a}_j^+ - \overline{\mathbf{a}_j^+}$,
where $\mathbf{a}_j^+ \in \{0,1\}^{64}$,
a binarized feature $\mathbf{b}$ could be tested using fast
{\sc bitwise and} and {\sc bit count} operations (see \cite{hare2012efficient}),
\begin{equation}\label{equ:modelApro}
  \langle\mathbf{w}, \mathbf{b} \rangle \approx \sum\nolimits^{N_w}_{j=1} \beta_j(2 \langle \mathbf{a}_j^+, \mathbf{b} \rangle  - |\mathbf{b}|).
\end{equation}


\begin{algorithm} [t]
    \begin{algorithmic}%[1]
        \STATE \textbf{Input:} $\mathbf{w}$, $N_w$
        \STATE \textbf{Output:} $\{\beta_j\}_{j=1}^{N_w}$, $\{\mathbf{a}_j\}^{N_w}_{j=1}$
        \STATE \textbf{Initialize residual:} $\varepsilon = \mathbf{w}$
        \FOR{$j$ = 1 to $N_w$}
            \STATE $\mathbf{a}_j = $sign$(\varepsilon)$
            \STATE $\beta_j = \langle \mathbf{a}_j, \varepsilon \rangle / \|\mathbf{a}_j\|^2$ \hfill (project $\varepsilon$ onto $\mathbf{a}_j$)
            \STATE $\varepsilon \leftarrow \varepsilon - \beta_j \mathbf{a}_j$ \hfill (update residual)
        \ENDFOR
    \end{algorithmic}
    \caption{Binary approximate model $\mathbf{w}$\cite{hare2012efficient}.
    }\label{alg:Model}
\end{algorithm}

\begin{algorithm}[b]
    \begin{algorithmic}%[1]
        \STATE \textbf{Comments:} see \figref{img:BING} for illustration of variables
        \STATE \textbf{Input:} binary normed gradient map $b_{W \times H}$
        \STATE \textbf{Output:} BING feature matrix $\mathbf{b}_{W \times H}$
        \STATE \textbf{Initialize:} $\mathbf{b}_{W \times H} = 0, \mathbf{r}_{W \times H} = 0$
        \FORALL{position $(x,y)$ in scan-line order}
            \STATE $\mathbf{r}_{x,y} = (\mathbf{r}_{x-1,y} \ll 1) \mid b_{x,y}$
            \STATE $\mathbf{b}_{x,y} = (\mathbf{b}_{x,y-1} \ll 8) \mid \mathbf{r}_{x,y}$
        \ENDFOR
    \end{algorithmic}
    \caption{Get BING features for $W \times H$ positions.
    }\label{alg:BING}
\end{algorithm}

The key challenge is how to binarize and calculate our NG features efficiently.
We approximate the normed gradient values (each saved as a {\sc byte} value)
using the top $N_g$ binary bits of the {\sc byte} values.
%
Thus, a 64D NG feature $\mathbf{g}_l$ can be approximated by $N_g$
\textbf{\emph{binarized normed gradients (BING)}} features as % (see \figref{img:BING})
\begin{equation}\label{equ:BING}
  \mathbf{g}_l = \sum\nolimits^{N_g}_{k=1} 2^{8-k}\mathbf{b}_{k,l}. % = \sum\nolimits^{N_g}_{k=1} 2^{8-k}\mathbf{b}_{k,i,x,y}
\end{equation}
Notice that these BING features have different weights according to its corresponding bit position
in {\sc byte} values.




Naively getting an \sz~ BING feature requires a loop computing access to 64 positions.
%
By exploring two special characteristics of an $8 \times 8$ BING feature,
we develop a fast BING feature calculation algorithm (\algref{alg:BING}),
which enables using atomic updates ({\sc bitwise shift} and {\sc bitwise or})
to avoid the loop computing.
%
First, a BING feature $\mathbf{b}_{x,y}$ and its last row $\mathbf{r}_{x,y}$
could be saved in a single {\sc int64} and a {\sc byte} variables, respectively.
Second, adjacent BING features and their rows have a simple cumulative relation.
%
As shown in \figref{img:BING} and \algref{alg:BING}, the operator
{\sc bitwise shift} shifts $\mathbf{r}_{x-1,y}$ by one bit, automatically
through the bit which does not belong to $\mathbf{r}_{x,y}$,
and makes room to insert the new bit $b_{x,y}$ using the {\sc bitwise or} operator.
Similarly {\sc bitwise shift} shifts $\mathbf{b}_{x,y-1}$ by 8 bits automatically through
the bits which do not belong to $\mathbf{b}_{x,y}$,
and makes room to insert $\mathbf{r}_{x,y}$.


Our efficient BING feature calculation shares the \emph{cumulative} nature
with the famous integral image representation \cite{viola2001rapid}.
Instead of calculating a single scalar value over an arbitrary rectangle range
\cite{viola2001rapid},
our method uses a few atomic operations (\eg {\sc add}, {\sc bitwise}, \etc)
to calculate \emph{a set of binary patterns}
over an \sz~ fixed range.



The filter score \equref{equ:score} of an image window corresponding to BING features $\mathbf{b}_{k,l}$
can be efficiently tested using:
\vspace{-.04in}
\begin{equation}\label{equ:scoreFast}
  s_{l} \approx \sum\nolimits^{N_w}_{j=1} \beta_j \sum\nolimits^{N_g}_{k=1} C_{j,k}, \vspace{-.04in}
\end{equation}
where $C_{j,k} = 2^{8-k} (2\langle\mathbf{a}_j^+, \mathbf{b}_{k,l}\rangle - |\mathbf{b}_{k,l}|)$
can be tested using fast {\sc bitwise} and {\sc popcnt sse} operators.


\begin{figure}
  \vspace{-.1in}
  \raggedright
  \hspace{0.3in}
  \begin{overpic}[width=.6\linewidth]{bTAG.pdf}
    \put(70, 53){{$\mathbf{b}_{k,i,x,y}\in \{0,1\}^{8 \times 8}$}}
    \put(70, 45){{shorthand: $\mathbf{b}_{x,y}$ or $\mathbf{b}_{k,l}$ }}
    \put(70, 33){{$\mathbf{r}_{k,i,x,y} \in \{0,1\}^{8}$}}
    \put(70, 25){{shorthand:  $\mathbf{r}_{x,y}$ or $\mathbf{r}_{k,l}$ }}
    \put(70, 10){{$b_{k,i,x,y} \in \{0,1\}$}}
    \put(70, 2){{shorthand: $b_{x,y}$}}
  \end{overpic}
  \caption{Illustration of variables: a BING feature $\mathbf{b}_{x,y}$,
    its last row $\mathbf{r}_{x,y}$ and last element $b_{x,y}$.
    Notice that the subscripts $i,x,y,l,k$, introduced in \equref{equ:location}
    and \equref{equ:BING}, are locations of the whole vector rather
    than index of vector element.
    We can use a single atomic variable ({\sc int64} and {\sc byte}) to represent a BING feature
    and its last row,
    enabling efficient feature computation (\algref{alg:BING}).
  }\label{img:BING}
\end{figure}



\vspace{-.1in}
\paragraph{Implementation details.}\label{sec:details}
%The quantization sizes are chosen so that an \sz~  fixed size window corresponds to
%quantized object sizes $S(W_0/\eta^m,H_0/\eta^n)$,
%where $W_0 \times H_0$ is the minimal interested object size,
%$\eta \in (0, 1)$ is the quantization accuracy\footnote{
%Such quantization scheme has been proven in \cite{zhang2011proposal}
%that any object window can be quantized into at least one quantized size
%so that the intersection-over-union (\intu) score \cite{pascal-voc-2007}
%is no less than $\eta$.}
%and $m, n \in \{0, 1, \dots\}$ is naturally bounded by maximal interested object size.
%In all our experiments, we use $\eta = 0.5$,
%and test window sizes from $10 \times 10$ to $500 \times 500$ pixels,
%resulting in $36$ quantized sizes.
%%It is easy to proof that the number of pixels (positions) in all these sizes
%%sum up to $O(N)$, where $N$ is the number of pixels in the input image.
We use the 1-D  mask $[-1, 0, 1]$ to find image gradients $g_x$ and $g_y$ in
horizontal and vertical directions,
while calculating normed gradients using $\min(|g_x| + |g_y|, 255)$
and saving them in {\sc byte} values. % avoid {\sc float} type operations.
By default, we calculate gradients in RGB color space.
%
%In our experiments, adding orientation information slightly decrease the
%prediction performance and we only use gradient magnitude.
%
In our C++ implementation, {\sc popcnt sse} instructions and {\sc openmp} options
are enabled.
% POPCNT SSE4
%\cmm{$8 \times 8$ filter size is used for efficient binarization as described in \secref{sec:BING}.}



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


We extensively evaluate our method on VOC2007 \cite{pascal-voc-2007}
using the DR-\#WIN \footnote{DR-\#WIN \cite{alexe2012measuring} means detection rate (DR) given \#WIN proposals.
This evaluation metric is also used in \cite{endres2013category,uijlings2013selective}
with slightly different names.
An object is considered as being covered by a proposal if the strict PASCAL
criterion is satisfied. That is, the \intu \cite{pascal-voc-2007}
score is no less than 0.5.}
evaluation metric,
and compare our results with 3 \sArt~methods\footnote{These 3 methods
have been evaluated on the same benchmark
and shown to outperform other alternative objectness proposal methods
\cite{harzallah2009combining,endres2010category,vedaldi2009multiple,felzenszwalb2010object,carreira2012cpmc},
saliency measures \cite{98pami/Itti,hou2007saliency},
interesting point detectors \cite{mikolajczyk2004scale},
and HOG detector \cite{dalal2005histograms}
(see \cite{alexe2012measuring} for these comparisons).}
\cite{alexe2012measuring,zhang2011proposal,uijlings2013selective} in terms of proposal quality,
generalize ability, and efficiency.
%
As demonstrated by \cite{uijlings2013selective,alexe2012measuring},
a small set of coarse locations with high detection rate (DR) are sufficient for effective
object detection,
and it allows expensive features and complementary cues to be involved in detection to achieve better quality and higher efficiency than traditional methods.
%
% In this section, we extensively evaluate the quality, generalization ability,
% and efficiency of our method.
%
Note that in all comparisons,
we use the authors' public implementations\footnote{Implementations and
results can be seen at the websites of the original authors:
\href{http://cms.brookes.ac.uk/research/visiongroup/code.php}{http://cms.brookes.ac.uk/research/visiongroup/code.php},
\href{http://groups.inf.ed.ac.uk/calvin/objectness/}{http://groups.inf.ed.ac.uk/calvin/objectness/},
\href{http://disi.unitn.it/~uijlings/}{http://disi.unitn.it/$\sim$uijlings/}, and
\href{http://vision.cs.uiuc.edu/proposals/}{http://vision.cs.uiuc.edu/proposals/}.
}
with their suggested parameter settings.


\vspace{-.1in}
\paragraph{Proposal quality comparisons.}


Following \cite{alexe2012measuring,zhang2011proposal,uijlings2013selective},
we evaluate DR-\#WIN on VOC2007 test set,
which consists of 4,952 images with bounding box annotation for the object instances from 20 categories.
The large number of objects and high variety of categories, viewpoint, scale, position, occlusion,
and illumination, make this dataset very suitable to our evaluation as we want to
find \emph{all} objects in the images.
%
\figref{fig:PlotDR} shows the statistical comparison between our method and \sArt~ alternatives:
OBN \cite{alexe2012measuring}, SEL \cite{uijlings2013selective}, and CSVM \cite{zhang2011proposal}.
As observed by \cite{uijlings2013selective},
increasing the divergence of proposals by collecting the results from different parameter settings
would improve the DR at the cost of increasing the number of proposals (\#WIN).
%
SEL \cite{uijlings2013selective} uses 80 different parameters to get combined results
and achieves 99.1\% DR using more than 10,000 proposals.
Our method achieves 99.5\% DR using only 5,000 proposals
by simply collecting the results from 3 color spaces (\emph{BING-diversified} in \figref{fig:PlotDR}):
{\sc rgb, hsv}, and {\sc gray}.
%
As shown in these DR-\#WIN statistics,
our simple method achieves better performance than others, in general,
and is \textbf{more than three orders of magnitude (\ie 1,000+ times) faster} than most popular alternatives
\cite{alexe2012measuring,uijlings2013selective,endres2013category}
(see \tabref{tab:Time}).
We illustrate sample results with varies complexity in \figref{fig:Vissual}.



\begin{figure}
  \centering
  \footnotesize
  \begin{overpic}[width=\linewidth]{DR_WIN_P.pdf}
    \put(73,35){BING-diversified}
    \put(73,31){BING-generic}
    \put(73,27){BING}
    \put(73,23){OBN \cite{alexe2012measuring}}
    \put(73,19.5){SEL \cite{uijlings2013selective}}
    \put(73,15.5){CSVM \cite{zhang2011proposal}}
    \put(73,11.5){Random guess}
%    \put(11,66){\begin{tabular}{r|l}  \hline
%        Method & Speed  \\ \hline
%        BING   & \textbf{300 fps} \\ \hline
%        OBN    & 0.32 fps \\ \hline
%        SEL    & 0.09 fps \\ \hline
%        CSVM   & 0.76 fps \\ \hline
%    \end{tabular}}
  \end{overpic}\\
  \caption{Tradeoff between \#WIN and DR (see \cite{alexe2012measuring} for
    more comparisons with other methods
    \cite{harzallah2009combining,endres2010category,vedaldi2009multiple,felzenszwalb2010object,carreira2012cpmc,98pami/Itti,hou2007saliency,dalal2005histograms}
    on the same benchmark).
    Our method achieves $96.2\%$ DR using 1,000 proposals,
    and $99.5\%$ DR using 5,000 proposals. This figure is best viewed in color.
  }\label{fig:PlotDR}
\end{figure}

\begin{figure*}
  \centering
  \includegraphics[height=.1355\linewidth]{ilu/000467_Match.jpg} \hfill
  \includegraphics[height=.1355\linewidth]{ilu/000693_Match.jpg} \hfill
  \includegraphics[height=.1355\linewidth]{ilu/000719_Match.jpg} \hfill
  \includegraphics[height=.1355\linewidth]{ilu/001282_Match.jpg} \hfill
  \includegraphics[height=.1355\linewidth]{ilu/002105_Match.jpg}
  \\ \vspace{.03in}
  \includegraphics[height=.187\linewidth]{ilu/001652_Match.jpg} \hfill
  \includegraphics[height=.187\linewidth]{ilu/001760_Match.jpg} \hfill
  \includegraphics[height=.187\linewidth]{ilu/004362_Match.jpg} \hfill
  \includegraphics[height=.187\linewidth]{ilu/007368_Match.jpg} \hfill
  \includegraphics[height=.187\linewidth]{ilu/007969_Match.jpg} \hfill
  \includegraphics[height=.187\linewidth]{ilu/008099_Match.jpg} \hfill
  \includegraphics[height=.187\linewidth]{ilu/009674_Match.jpg}
  \\ \vspace{.03in}
  \includegraphics[height=.141\linewidth]{ilu/002111_Match.jpg} \hfill
  \includegraphics[height=.141\linewidth]{ilu/002168_Match.jpg} \hfill
  \includegraphics[height=.141\linewidth]{ilu/002429_Match.jpg} \hfill
  \includegraphics[height=.141\linewidth]{ilu/002510_Match.jpg} \hfill
  \includegraphics[height=.141\linewidth]{ilu/002773_Match.jpg}
  \\ \vspace{.03in}
  \includegraphics[height=.138\linewidth]{ilu/002821_Match.jpg} \hfill
  \includegraphics[height=.138\linewidth]{ilu/002860_Match.jpg} \hfill
  \includegraphics[height=.138\linewidth]{ilu/002904_Match.jpg} \hfill
  \includegraphics[height=.138\linewidth]{ilu/002981_Match.jpg} \hfill
  \includegraphics[height=.138\linewidth]{ilu/004629_Match.jpg}
  \\ \vspace{.03in}
  \includegraphics[height=.1285\linewidth]{ilu/006863_Match.jpg} \hfill
  \includegraphics[height=.1285\linewidth]{ilu/007599_Match.jpg} \hfill
  \includegraphics[height=.1285\linewidth]{ilu/007994_Match.jpg} \hfill
  \includegraphics[height=.1285\linewidth]{ilu/008249_Match.jpg} \hfill
  \includegraphics[height=.1285\linewidth]{ilu/008354_Match.jpg}
  \\ \vspace{.03in}
  \includegraphics[height=.1395\linewidth]{ilu/008367_Match.jpg} \hfill
  \includegraphics[height=.1395\linewidth]{ilu/008504_Match.jpg} \hfill
  \includegraphics[height=.1395\linewidth]{ilu/009514_Match.jpg} \hfill
  \includegraphics[height=.1395\linewidth]{ilu/009602_Match.jpg} \hfill
  \includegraphics[height=.1395\linewidth]{ilu/009903_Match.jpg} \\
  \caption{Illustration of the true positive object proposals for VOC2007 test images.
    See \figref{fig:PlotDR} for statistical results.
  }\label{fig:Vissual}
\end{figure*}


\vspace{-.1in}
\paragraph{Generalize ability test.}
Following \cite{alexe2012measuring}, we show that our objectness proposals are \textbf{\emph{generic}} over
categories by testing our method on images containing objects whose categories are not used for training.
%
Specifically, we train our method using 6 object categories (\ie bird, car, cow, dog, and sheep)
and test it using the rest 14 categories (\ie aeroplane, bicycle, boat, bottle, bus, chair,
dining-table, horse, motorbike, person, potted-plant, sofa, train, and tv-monitor).
In \figref{fig:PlotDR}, the statistics for training and testing on same or different
object categories are represented by {\it BING} and {\it BING-generic},
respectively. As we see, the behavior of these two curves are almost identical,
%similar to the results in \cite{alexe2012measuring},
which demonstrates the \emph{generalize} ability  of our proposals.

Notice that the recent work \cite{google10K_Class} enables 20 seconds
testing time for detecting $100,000$ object classes, by reducing
the computational complexity of traditional multi-class detection from $O(LC)$ to $O(L)$,
where $L$ is the number of locations or window proposals and
$C$ is the number of classifiers.
The ability of our method to get a small set of high quality proposals of any category
(including both trained and unseen categories),
could be used to further reduce the computational complexity significantly by
reducing $L$.

%Leave to the journal version
%Since our method is extremely efficient, it is very suitable for processing very large
%image collections, e.g. ImageNet \cite{deng2009imagenet}.
%We use the model trained on VOC2007 to directly predict \todo{XXX} bounding box annotated
%ImageNet 2012 images.
%The \todo{XXX} DR at 1,000 windows shows the strong generalization ability of our method.


\newcommand{\obn}{{\cite{alexe2012measuring}}}
\newcommand{\csvm}{{\cite{zhang2011proposal}}}
\newcommand{\category}{{\cite{endres2013category}}}
\newcommand{\sel}{{\cite{uijlings2013selective}}}
\begin{table}[b]
    \centering
    \begin{tabular}{c||c|c|c|c|c} \hline\hline
          \Rows{Method}  &           & OBN  &  CSVM & SEL  & Our     \\
                         & \category & \obn & \csvm & \sel & BING     \\ \hline
          Time \small{(seconds)}       &    89.2   & 3.14 & 1.32  & 11.2 & \textbf{0.003}  \\ \hline \hline
    \end{tabular}\\ \vspace{.05in}
    \caption{Average computational time on VOC2007.
    }\label{tab:Time}
\end{table}



\vspace{-.1in}
\paragraph{Computational time.}
As shown in \tabref{tab:Time}, our method is able to efficiently
propose a few thousands high quality object windows at 300fps,
while other methods require several seconds for one image.
%
Note that these methods are usually considered to be highly efficient \sArt~algorithms and difficult to further speed up.
%
%Moreover, our training on VOC2007 training set only takes about 20 seconds
%(excluding xml file loading time),
%%which is much faster than $3+$ hours training time of \cite{zhang2011proposal}
%which is even faster than testing a single image using some alternative methods
%\cite{endres2010category,carreira2012cpmc}.
Moreover, our training on $2501$ images (PASCAL VOC2007) takes
much less time (20 seconds excluding xml loading time)
than testing a single image using some \sArt~alternatives methods
\cite{endres2010category,carreira2012cpmc} (typically $2+$ minutes).


As shown in \tabref{tab:TimePerWin},
with the binary approximation to the learned linear filter (\secref{sec:BING}) and BING features,
computing response score for each image window only needs a fixed small number of atomic
operations.
It is easy to see that the number of positions at each quantized scale and aspect ratio
is equivalent to $O(N)$,
where $N$ is the number of pixels in images.
Thus, Computing response scores at all scales and aspect ratios also has the computational complexity $O(N)$.
Further, extracting BING feature and computing response score at each potential position (\ie an image window)
can be calculated with information given by its 2 neighboring positions (\ie left and upper).
This means that the space complexity is also $O(N)$.
%
We compare our running time with baseline methods
\cite{alexe2012measuring,zhang2011proposal,uijlings2013selective,endres2013category}
on the same laptop with an Intel i7-3940XM CPU.

\newcommand{\gIlu}[1]{\textcolor[rgb]{0.8,0.8,0.8}{#1}}
\newcommand{\Coln}[2]{\multicolumn{#1}{c|}{{#2}}}
\begin{table}[t]
    \centering
    \small
    \begin{tabular}{c||c|c|c|c|c|c|c} \hline\hline
                   &      \Coln{3}{\sc bitwise}           & \Cols{\sc float} & \multicolumn{2}{c}{{\sc int,byte}}     \\ \cline{2-8}
                   & {\sc shift}  & $|$, $\&$ & {\sc cnt} &  $+$     & $\times$ & $+,-$    & $\min$   \\ \hline
       {Gradient}  &   \gIlu{0}   & \gIlu{0}  & \gIlu{0}  & \gIlu{0} & \gIlu{0} &  9       &   2      \\ \hline
       {Get BING}  &    12        &    12     & \gIlu{0}  & \gIlu{0} & \gIlu{0} & \gIlu{0} & \gIlu{0} \\ \hline
       {Get score} &   \gIlu{0}   &    8      &    12     &   1      &   2      & 8 & \gIlu{0} \\ \hline \hline
    \end{tabular}\\ \vspace{.05in}
    \caption{Average number of atomic operations for computing objectness of each image window
        at different stages: calculate normed gradients, extract BING features, and get objectness score.
    }\label{tab:TimePerWin}
%    \normalsize
%    \begin{tabular}{c||c|c|c|c|c|c} \hline\hline
%          ($N_w,N_g$) & (2,2) & (2,3) & (2,4) & (3,2) & (3,3) & (3,4)   \\ \hline
%          DR (\%)     &  95.6 & 95.9  & 96.2  &  95.8 &  96.2 &  96.1   \\ \hline \hline
%    \end{tabular}\\ \vspace{.05in}
%    \caption{Average result quality (DR using 1000 proposals) at different approximation levels, measured by $N_w$ and $N_g$ in \secref{sec:BING}.
%    }\label{tab:TimeQuality}
    \vspace{-.15in}
\end{table}


\begin{table}
    \centering
    \begin{tabular}{c||c|c|c|c|c|c} \hline\hline
          ($N_w,N_g$) & (2,2) & (2,3) & (2,4) & (3,2) & (3,3) & (3,4)   \\ \hline
          DR (\%)     &  95.6 & 95.9  & 96.2  &  95.8 &  96.2 &  96.1   \\ \hline \hline
    \end{tabular}\\ \vspace{.05in}
    \caption{Average result quality (DR using 1000 proposals) at different approximation levels, measured by $N_w$ and $N_g$ in \secref{sec:BING}.
    }\label{tab:TimeQuality}
\end{table}


We further illustrate in \tabref{tab:TimeQuality} how different approximation
levels
influence the result quality and computational time.
%
According to this comparison, we use $N_w = 2$ and $N_g = 4$ in all the experiments.



\section{Conclusion and Future Work}

We present a surprisingly simple, fast, and high quality objectness
measure by using \sz~ binarized normed gradients (BING) features,
with which computing the objectness of each image window at any scale and aspect ratio
only needs a few atomic (\ie~{\sc add, bitwise,} etc.) operations.
%
Evaluation results using the most widely used benchmark (VOC2007) and evaluation
metric (DR-\#WIN) show that our method not only
outperforms other \sArt~methods, but also runs more than three orders of magnitude faster than most popular alternatives
\cite{alexe2012measuring,uijlings2013selective,endres2013category}.
%



\vspace{-.1in}
\paragraph{Limitations.}
Our method predicts a small set of object bounding boxes.
Thus, it shares similar limitations as all other bounding box based
objectness measure methods \cite{alexe2012measuring,zhang2011proposal}
and classic sliding window based object detection methods
\cite{dalal2005histograms,felzenszwalb2010object},
%
For some object categories,
a bounding box might not localize the object instances as accurately as a segmentation region,
\cite{endres2010category,carreira2012cpmc,endres2013category},
\eg a snake, wires, \etc


\vspace{-.1in}
\paragraph{Future works.}
The high quality and efficiency of our method make it
suitable for realtime multi-category object detection applications
and large scale image collections (e.g. ImageNet \cite{deng2009imagenet}).
%
The binary operations and memory efficiency make our method suitable to run on low power devices \cite{hare2012efficient,szhengFacialFG2013}.


Our speed-up strategy by reducing the number of windows is complementary to other
speed-up techniques which try to reduce the classification time required for each location.
%
It would be interesting to explore the combination of our method
with \cite{google10K_Class} to enable
realtime detection of thousands of object categories on a single machine.


We have demonstrated how to get a small set (\eg 1,000) of proposals to
cover nearly all (\eg $96.2\%$) potential object regions,
using very simple BING features.
%
It would be interesting to introduce other additional cues to further
reduce the number of proposals while maintaining high detection rate, and explore more applications using BING.


To encourage future works, we will release our C++ source code immediately
after paper acceptance,
and integrate it in the next version of OpenCV.



{\small
\bibliographystyle{ieee}
\bibliography{ObjectnessBING}
}

\end{document}


% See http://people.csail.mit.edu/nwadhwa/ & http://www.klab.caltech.edu/
% for more ideas about pushing this work towards a nature paper.
