
%% bare_jrnl_compsoc.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE Computer
%% Society journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE!
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/




% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
% The Computer Society usually requires 10pt for submissions.
%
\documentclass[10pt,journal,letterpaper,compsoc]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[12pt,journal,compsoc]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  % \usepackage[nocompress]{cite}
\else
  % normal IEEE
  % \usepackage{cite}
\fi
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.
%
% Note that some packages require special options to format as the Computer
% Society requires. In particular, Computer Society  papers do not use
% compressed citation ranges as is done in typical IEEE papers
% (e.g., [1]-[4]). Instead, they list every citation separately in order
% (e.g., [1], [2], [3], [4]). To get the latter we need to load the cite
% package with the nocompress option which is supported by cite.sty v4.0
% and later. Note also the use of a CLASSOPTION conditional provided by
% IEEEtran.cls V1.7 and later.





% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
   \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
%\usepackage{graphicx}
\usepackage{epsfig}
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
\usepackage[cmex10]{amsmath}
\usepackage{amsthm}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}

%\theoremstyle{definition}
%\newtheorem{def}[thm]{Definition}

% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%\usepackage[tight,normalsize,sf,SF]{subfigure}
%\else
%\usepackage[tight,footnotesize]{subfigure}
%\fi
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. Computer Society papers
% use a larger font and \sffamily font for their captions, hence the
% additional options needed under compsoc mode. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.


%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false]{caption}
%  \usepackage[font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false]{caption}
%  \usepackage[font=footnotesize]{subfig}
%\fi
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.




%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley and Jeff Goldberg.
% This package may be useful when used in conjunction with IEEEtran.cls'
% captionsoff option. Some IEEE journals/societies require that submissions
% have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.3.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% For subfigure.sty:
% \let\MYorigsubfigure\subfigure
% \renewcommand{\subfigure}[2][\relax]{\MYorigsubfigure[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat/subfig command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%\title{Optimizing Multi-scale Random Fields using Context}
%\title{Globally Optimal Multi-Scale Random Fields for Contour Grouping}
%\title{Globally Optimal Multi-Scale Random Fields for Object Detection}
%\title{Globally Optimal Multi-Scale Random Fields for Object Boundary Detection}
\title{Multi-Scale Random Fields \\for Grouping Object Boundaries}

\author{ChengEn~Lu,
        Nagesh~Adluru,~\IEEEmembership{Student Member,~IEEE,}
        and~Longin~Jan~Latecki,~\IEEEmembership{Senior Member,~IEEE}% <-this % stops a space
\IEEEcompsocitemizethanks{\IEEEcompsocthanksitem C. Lu is with the
Department of Electrical and Computer Engineering, Wuhan University, China.\protect\\
% note need leading \protect in front of \\ to get a newline within \thanks as
% \\ is fragile and will error, could use \hfil\break instead.
E-mail: chengenlu@gmail.com
\IEEEcompsocthanksitem N. Adluru and L.J. Latecki are with Temple University.}% <-this % stops a space
\thanks{This work was supported in part by the NSF Grant No. IIS-0534929 and
by the DOE Grant No. DE-FG52-06NA27508.}}

% note the % following the last \IEEEmembership and also \thanks -
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
%
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
\markboth{Grouping Object Boundaries using MSRF}%
{Shell \MakeLowercase{\textit{Lu et al.}}}
\IEEEcompsoctitleabstractindextext{%
\begin{abstract}
%\boldmath
We introduce a new interpretation of multiscale random fields
(MSRFs) that admits efficient optimization in the framework of
regular (single level) random fields (RFs). It is based on a new
operator, called append, that combines certain sets of random
variables (RVs) to single RVs. We assume that a MSRF can be
decomposed into trees that link RVs at different pyramid levels. The
append operator is then applied to map RVs in each tree structure to
a single RV. We demonstrate the usefulness of the proposed approach
on a challenging task involving grouping contours of target shapes
in images. It provides a natural representation of multiscale
contour models, which is needed in order to cope with unstable
contour decompositions. The append operator allows us to find
optimal image segment labels using classical RFs optimization
methods like relaxation labeling or Markov Chain Monte Carlo (MCMC).
However, our application of contour grouping admits a globally
optimal solution under certain realistic assumptions. Hence, we
present a globally optimal and efficient way of searching through
the space of labeling assignments by exploring both local and global
shape similarity.
\end{abstract}
\begin{IEEEkeywords}
Grouping contour parts, object detection, random fields, consistent
labeling.
\end{IEEEkeywords}}


% make the title area
\maketitle

\IEEEdisplaynotcompsoctitleabstractindextext
\IEEEpeerreviewmaketitle

\section{Introduction}\label{sec:intro}
We decompose a given closed contour of a model shape into a group of
contour parts, and match the resulting contour parts to edge
segments in a given edge image. Our contour decomposition of the
model is flexible and admits a hierarchical tree structure similar
to shape-trees of \cite{pedro07}. Thus our model can adapt to
different configurations of contour parts in edge images. The
proposed MSRF interpretation allows us to formulate the problem of
grouping contour parts into object boundaries as a label assignment
problem. Since some interactions of RVs make them compete for the
best possible label assignment it allows us to examine multiple
composition hypotheses of model parts in the image. Thus a
successful grouping of parts is possible even if significant contour
parts are missing or are distorted. The competition is made possible
by the proposed append operator. It appends the competing random
variables (RVs) to a single new RV. Since the connectivity relation
between each pair of model parts is known, the label assignment with
the competition for best labels allows us to accurately group
boundaries in real images possible. The advantages of using parts as
tokens for matching over alternative techniques based on point
matching (\cite{chui2003}) are at least twofold: It permits more
robust deformable matching (i.e., the global shape will not be
changed even when some segments shift or rotate a little). It is
more stable than point matching, since contour parts are more
informative than points as shape cues.


The proposed MSRF for grouping boundaries of objects in cluttered
images is built on multi-scale object model contour parts. The field
potentials are defined by their labels from the set of contour parts
(identified by low-level linking) in the image. There are three main
challenges in optimizing the field energy.
\begin{enumerate}
\item[(1)] Our model decomposition results in a MSRF with complex interactions
(competing and compatible) among RVs across scales and within each
scale.
\end{enumerate}
This results in a more complex graph structure than regular MSRFs.
It is needed to cope with unstable contour extraction in real
images, since contour fragment extraction in images can be
inaccurate and most of the reference object parts might only have
incomplete match with image edge fragments. Our solution is to allow
each model contour part to have different incomplete, by still
acceptable matches to image edge fragments. Therefore, our contour
models are divided into groups, and each group has a tree structure.
This tree structure defines a Multiscale Random Field (MSRF).
Moreover, the unstable contour extraction in real images implies
that any energy function based on a shape similarity measure between
model contours and image edge fragments is highly nonlinear.
\begin{enumerate}
\item[(2)] Consequently, the energy is non-submodular.
\item[(3)] The random field does not satisfy Ising/Potts model,
since our approach requires unique label assignments.
\end{enumerate}
Hence many standard graph-cut based optimization methods are not
applicable. Also since we want full labeling partial optimal methods
like QPBO (Quadratic Pseudo Boolean Optimization)
\cite{rother07,kolmogrov07} and TRW (Tree Re-Weighted message
passing) \cite{komodakis07} are not suitable. Many generalized and
efficient MCMC (Markov Chain Monte Carlo) samplers for non
Ising/Potts model are not applicable when field potentials depend on
label assignments. For the first challenge we introduce a new
operator called \emph{append operator} that combines sets of
competing random variables (RVs) to a single RV. This allows us to
simplify the structure of the MSRF into as a single scale random
field on the "appended" RVs.

To address the second and third challenges, we present an efficient
way of searching through the space of $O(n^m)$ labeling assignments
using both local and global shape similarity. $m, n$ are the number
of model and image contour parts respectively. We use a two phase
search strategy for labeling assignments: In the first phase we find
$k$ most likely labels for each of the RV using local label-RV
compatibility. In the second phase these likely labels are used to
efficiently search for best final labels for all the RVs. The first
phase uses contour part similarity based on local shape descriptors
while the second phase uses global shape similarity involving the
model and image contour parts selected in the first phase.

Under the assumption that the $k$ most likely labels contain the
globally optimal labeling, the proposed approach guarantees to find
the globally optimal assignment in $O(mk)$. Thus even if $k=n$ the
search takes asymptotically polynomial time. The selection of the
first $k$ most likely labels is based on local shape similarity. In
the proposed approach, it is sufficient that local shape similarity
is successful in label assignment of only one model contour segment
to ensure globally optimal label assignment. As our experimental
results demonstrate, this is a realistic assumption for detecting
objects of various classes in cluttered images. Consequently, local
shape similarity can significantly help identifying the context
needed for computing global shape similarity.




The major contributions of the paper are: (1) Proposing a new append
operator for simplifying the MSRF structure of the multi-scale
contour parts of the model. (2) Efficient optimization of the field
energy using both local and global shape information, which under
realistic assumption leads to globally optimal label assignments.
(3) Improving shape context to deal with errors in the low-level
linking that is used identifying contour parts. We conclude the
introduction with an algorithmic overview of our approach. The
algorithmic flow is shown in Fig. \ref{fig:algorithm-overview}.
\begin{figure}[htb]
\begin{center}
\includegraphics*[width=1\linewidth]{figs/alg2.eps}
\end{center}
\caption{Overview of our algorithm: (1) Edge extraction. (2) Edge
linking. (3) MSRF optimization using append operator and two-phase
search with each model. (4) Grouping the boundary in the image using
MSRF with minimum energy.} \label{fig:algorithm-overview}
\end{figure}
For a given input image an edge image is computed using
\cite{MartinFTM01}. Then the edge-pixels are linked to form chains
which form the set of labels. We currently use publicly available
code (\cite{KovesiMATLABCode}). Other sophisticated linking
algorithms like \cite{Tamrakar:Kimia:ICCV07,shi:ICCV07} could also
be used. Each model in the set of models is decomposed into
multi-scale contour parts forming an MSRF. Then each of these MSRFs
is optimized using our append operator and two-phase search for
labeling assignments. Finally the MSRF with minimum energy is chosen
and the labeling assignment is used to group the boundary in the
image.

\textbf{(Needs to be rewritten at the end because it keeps
changing).} The rest of the paper is organized as follows: \S
\ref{sec:msrf} explains the multi-scale representation of the model
contour parts. \S \ref{sec:two-phase} describes the details of our
two-phase optimization of the MSRF energy. Finally experimental
results are presented in \S \ref{sec:exp-results} followed by
conclusion and discussions in \S \ref{sec:concl-disc}.






\section{Related Work}
\subsection{Contours and Object Detection}\label{sec:contours-detection}
\IEEEPARstart{C}{ontours} are very useful in encoding shape of
objects and shape is crucial for object detection and recognition.
Object detection and recognition by shape has a long history in
computer vision. The basic idea is to extract some shape features
and define distances between shapes using those features. Many
heuristics are used in designing the features and distances so that
the distances can be used to label or classify objects in accord
with human perception. Some examples include
\cite{Siddiqi98,Belongie02,Ling07,bai08pami,yang08}. Though such
methods have some invariance capabilities to handle some
deformations they cannot handle clutter and artifacts which commonly
occur in real images. It is important to note that this is not their
limitation per se because they are designed assuming the objects are
already separated from the clutter or background. Separating objects
from background has been a low-level vision problem for many years
but for fully automatic segmentation it has to be combined with a
recogntion process. Hence researchers have been focussing on unified
approaches for object recognition and segmentation
\cite{Borenstein02,Leibe03,Kumar05,Zhuowen:2005,wang07}. Unifying
object detection/recognition and segmentation/grouping typically
involves adding high-level prior about shapes of objects to the
low-level discriminative approaches used for segmentation and/or
grouping \cite{Kumar05,hongzhi06,adluru:latecki:ICCV07,olga08}. It
also involves quantifying low-level tasks for improved
detection/recognition \cite{tu04,marina05,hongzhi08}.

Detecting objects can be at various precision levels starting from
roughly detecting bounding boxes around the objects to finding the
boundaries of the objects and even to finding the full interior
contours of the objects. Object detection involving contours can
provide a basis for better high-level applications which require
more precision like medical imaging, human robot interactions etc.
The first step in detecting object boundaries is extracting contour
parts from images. Contour grouping has received quite an amount of
attention for several decades and is still an active research as
documented by recent articles
\cite{shi:ICCV07,Trinh:Kimia:ICCV07,Tamrakar:Kimia:ICCV07,Hoiem_2007_5826,Stein_2007_5836,basri:ICCV07}.
Several saliency measures based on Gestalt principles have been used
in grouping contours \cite{williams99}. Contour parts are then
grouped to form object boundaries using methods that are essentially
trying to perform shape matching in real images. For example,
\cite{shotton05,Opelt06} use Chamfer distance (\cite{borgefors88})
to match fragments of contours learnt from training images to edge
images, but their results are typically grassy contours.
\cite{mcneill06} represents parts learnt from semi-supervised
training as point-sets and establishes probabilistic point
correspondences to the points in edge images. Their main limitation
is the sequential initialization of parts. \cite{ferrari08} uses a
network of nearly straight contour fragments and sliding window
search. \cite{Thayananthan03shapecontext} modified shape context
\cite{Belongie02} to incorporate edge orientations and Viterbi
optimization for better matching in clutter, but this approach has
limitations related to initializing the model contour.
\cite{pedro07} presented a shape-tree based elastic matching among
two shapes and extended it to match a model and cluttered image by
identifying contour parts (smooth curves) using \cite{pedro06}, but
they have a computationally expensive "stitching" of parts that
match to shape-tree of the model. More recently \cite{qihui08}
formulated the shape matching of contours (identified using
\cite{shi:ICCV07}) in clutter as a set-set matching problem. They
present an approximate solution to the hard combinatorial problem by
using a voting scheme (\cite{wang07,leibe05}) and a relaxed context
selection scheme using linear programming. They use shape context
\cite{Belongie02} as shape descriptor. Another direction of research
is to use local symmetry as shape constraint and to
\emph{sequentially} group object boundaries in particle filter
framework \cite{adluru:latecki:ICCV07}. An excellent framework for
deformable template matching has been recently proposed in
\cite{wu08}. They use \emph{generative models} using Gabor wavelets
which actively pursue for the template in the image. One of their
current limitations is requiring bounding boxes for the pursuit.
Also they do not necessarily look for precise object boundaries.

In this paper we focus on grouping contour parts into object
boundaries. We currently identify contour parts using Peter Kovesi's
low-level edge linker \cite{KovesiMATLABCode}. Other low-level
linkers like \cite{Tamrakar:Kimia:ICCV07,shi:ICCV07} can also be
used. As in all of the techniques described above the assumption is
that the parts have reasonable shape information that does not need
to be perfect though. Our approach can cope with significant amount
of wrongly identified edge segments, representing either relevant
contour segments incorrectly split into too many parts, missing
relevant contour parts, or contour segments of two or more different
objects incorrectly merged into one segment.



\subsection{Random Fields in Computer Vision}\label{sec:rfcv}
Stochastic modeling of images and in particular random field (RF)
modeling has been very attractive for many important subproblems in
computer vision \cite{geman86,Stan08}. For example random fields
have been used for image denoising (\cite{geman84}), texture
modeling (\cite{zhu98}), image segmentation (\cite{Tu02}),
perceptual organization (\cite{Zhu99PAMI}), object recognition
(\cite{tu04}) and image parsing (\cite{Zhuowen:2005}). RF modeling
involves defining the field elements (random variables) and
interactions among them. The interaction potentials are defined
using neighborhood compatibilities of random variables (RVs) as well
as their labels which depends on the specific application. The goal
then becomes understanding the behavior of the field for a given
image. Statistical methods try to understand the distribution of the
field energies and deterministic methods try to find desired energy
states (typically minimum energy or maximum log-likelihood of the
energy) of the fields. For example \cite{barbu:2007} generalized
Swendsen-Wang sampler for drawing samples from reasonably complex
posteriors of the fields, but they cannot be efficient when the
field potentials involve labels. \cite{Boykov-Veksler01} introduced
graph-cut based approximation of the minimum energy with guaranteed
behavior on a restrictive but widely applicable class of energies
\cite{Kolmogrov04}. The main limitation though is that they require
energies to be submodular (satisfy Ising/Potts model). There have
been extensions of graph-cuts for non-submodular energies using
Quadratic Pseudo Boolean Optimization (QPBO). But their extensions
obtain only partial labeling of the RVs and work only if the number
of non-submodular interactions are very few
\cite{rother07,kolmogrov07}. Modeling using high-level shape
information results in more complex potentials over scales in the
fields for all such methods. There have been methods that solve a
\emph{relaxed version} of a more general problem called the
consistent labeling problem (\cite{nadel86}). They relax the
requirement of labels being discrete, which admits the usage of
simplex methods to compute the label assignments. A classical
example is relaxation labeling introduced by Rosenfeld et. al.
\cite{Rosenfeld76}. There has been flurry of research in
understanding the process and advantages of the relaxation, e.g.,
\cite{hummel83,pelillo97jmiv,wanghancock2008}. Most of relaxation
methods are local minimizers (\cite{stanli97jmiv}) except for very
restrictive interaction potentials \cite{leary1983,bozma1988}. For
restricted interactions namely unary and binary interactions linear
programming (LP) relaxation techniques like belief propagation (BP)
(\cite{pearl1988,Yedidia00generalizedbelief}) and tree re-weighted
message passing (TRW) (\cite{komodakis07}) have been developed.
Recently a comparative study of energy minimization techniques on
binary interactive fields demonstrated that graph-cuts outperform
TRW, BP and also Iterated Conditional Modes (ICM)
\cite{szeliski2008}.

\subsection{Multiscale Image Representations}\label{sec:overview}
Images have different information and different scales and the
inferential uncertainties change over scales \cite{yingwu07}.
Multi-scale representation of images is very useful and many
researchers have been using multi-scale random field modeling of
images \cite{Bouman94,willsky02,He04,Ferreira07}. Different
techniques have been used in exploiting multi-scale/multiresolution
models including very popular spectral clustering methods
\cite{stellayu04,Cour:cvpr05} and MCMC methods \cite{barbu04}.
However, the main hurdle in using multi-scale models is maintaining
consistent information across scales \emph{efficiently} especially
involving complex high-level modeling.

Our MSRF has $m$-ary interactions where $m\geq4$ is the number of
model contour parts and hence the standard methods involving binary
interactions are not suitable for our MSRF. Since our energy
function is not submodular, we introduce an efficient solution to a
non-relaxed (discrete) version of the one-one labeling problem, in
which each model contour part is assigned a \emph{unique} label from
the set of image contour parts.

The main difference between MSRFs as known in the literature and the
proposed MSRF is in the interpretation of the connections between
different RVs. In the proposed approach, the random variables (RVs)
can be linked such that they \emph{compete} for label assignments,
while in the existing approaches the goal is to \emph{propagate}
their label assignments, which is usually achieved by averaging. For
example, usually the label assignment of a parent node is enforced
to be compatible with the label assignment of its children by
averaging. In contrast, in the proposed MSRF the parent node and all
its children compete for the best possible label assignment.

\section{MSRF Based Grouping}\label{sec:msrf}
In this section we explain how we build the MSRF on an object model
and formulate the grouping of contour parts as a labeling assignment
problem.
\subsection{MAP-MRF Labeling}\label{sec:map-mrf-labeling}
Markov random field (MRF) theory, a branch of probability theory,
provides a foundation for the characterization of spatial,
contextual constraints and the derivation of the probability
distributions of interacting features \cite{stanli97jmiv}. The
labeling problem can be formulated as a \emph{Maximum a posteriori}
(MAP) maximization problem of field posterior or equivalently
minimization of the field energy. If $F=\{F_1,F_2,\ldots,F_m\}$ is
the set of random variables (RVs) in the field,
$X=\{x_1,x_2,\ldots,x_n\}$ is the set of labels that the RVs get
assigned then the field posterior $p(F=f)$ satisfies Gibbs
distribution:
\begin{align}\label{eq:gibbs}
p(F=f)&=p(F_1=f_1,\ldots,F_m=f_m)\nonumber\\
&=p(f)=\frac{1}{Z}\times e^{\frac{-U(f)}{T}}
\end{align}
where $f$ is a particular configuration i.e.
$f=\{f_1,f_2,\ldots,f_m\}$ s.t. $f_i:F_i\to X$, $Z$ is a normalizing
constant defined as:
\begin{equation}
Z=\sum_{f\in\mathcal{F}}e^{\frac{-U(f)}{T}}
\end{equation}
$T$ is a global control parameter called the temperature that
controls the precision of the posterior and $U(f)$ is the field
energy defined by interaction potentials of RVs in the set of
cliques $\mathcal{C}$ defined as:
\begin{equation}
U(f)=\sum_{c\in \mathcal{C}}V_{|c|}(f)=\sum_{F_i\in c\in
\mathcal{C}}V_{|c|}(\{f_i\})
\end{equation}
The MAP goal thus is to find optimal labeling configuration
$f^\ast$:
\begin{equation}\label{eq:max}
f^\ast=\underset{f\in \mathcal{F}}{\operatorname{argmax}}~p(f)
\end{equation}
Or equivalently:
\begin{equation}\label{eq:min}
f^\ast=\underset{f\in \mathcal{F}}{\operatorname{argmin}}~U(f)
\end{equation}
$\mathcal{F}$ is the space of labeling assignment configurations. If
we allow assigning same label to multiple RVs then $\mathcal{F}=X^m$
and $|\mathcal{F}|=n^m$. If the RVs get assigned unique labels then
$|\mathcal{F}|=P(n,m)=n(n-1)\ldots(n-m)$ assuming $n>m$.

The Markovian nature of a RF characterizes the conditional
independence of RVs given their neighborhoods. A RF is MRF if and
only if its posterior satisfies Gibbs distribution Eq.
\eqref{eq:gibbs} (\cite{besag74}). If the neighborhoods of RVs
involves tree structured hierarchy then the RFs are called MSRFs. If
there is conditional independence across different scales of RVs
then the MSRF is called Markov MSRF. An MRF can be also be viewed as
a graph $G=(F,E)$ where the set of RVs ($F$) form nodes and their
neighborhoods define the set of edges ($E$). The edge weights
represent interaction potentials between two RVs.

\subsection{Grouping as Labeling}\label{sec:grouping-labeling}
In our application we group contour parts in the image into object
boundaries. These parts form the set of labels
$X=\{x_1,x_2,\ldots,x_n\}$. To handle both deformations and noise in
the images, the object model is decomposed into hierarchical contour
parts $S=\{s_1,s_2,\ldots,s_m\}$. A RV is defined on each of the
decomposed part. This gives us the set of RVs
$F=\{F_1,F_2,\ldots,F_m\}$. The neighborhoods are both spatial and
hierarchical and hence the random field defined over our model parts
is a MSRF. Our decomposition assumes conditional independence
required for the field to be Markov. As shown in Fig.
\ref{fig:algorithm-overview} an MSRF is built on each of the object
models and an optimal labeling assignment is found. The MSRF with
maximum posterior or minimum energy is chosen and the contextual
relations among its RVs can be used to group the labels (contour
parts) in the image to full boundaries. Since we assign an image
segment $x_i\in X$ to at most one model segment $s_j\in S$, each RV
gets a unique label and hence the cardinality of our configuration
space $\mathcal{F}$ is $P(n,m)$. Observe that this is in contrast to
set-to-set matching of \cite{qihui08}. One-one matching is key to
our discrete optimization also. Since our decomposition of model is
hierarchical and our random field has competing and compatible
interactions across scales one-one matching suffices. A sample
decomposition of the swan model and the corresponding MSRF can be
seen in Fig. \ref{fig:swan-msrf}.
\begin{figure}[htb]
\begin{center}
\begin{tabular}{c}
\includegraphics*[width=0.5\linewidth]{figs/swandecomp.eps}\\
\includegraphics*[width=1\linewidth]{figs/swanmsrf2.eps}
\end{tabular}
\end{center}
\caption{\textbf{(The figure will be changed finally to show some
deformations also.)}Top: Hierarchical decomposition of swan model
into categorical parts. Bottom: Corresponding MSRF. The $F_i^js$
form the set of RVs $F$. There are two types of interactions among
the RVs in the field: compatible (shown in green) and competing
(shown in red). The competing RVs are grouped into appended RVs,
$\{\oplus T_is\}$. The interactions among the appended RVs are built
based on the interactions among $F_i^js$. See text for more
details.} \label{fig:swan-msrf}
\end{figure}
Hierarchical shape decompositions have been used for shape
recognition. For example curvature scale-space (CSS)
(\cite{mokhtarian92,ueda93,mokhtarian97world}), triangulated graphs
(\cite{amit96,pedro05}). Our decomposition has three main steps.
\textbf{(1) Identifying salient contour parts:} We break the model
contour at salient points for example by using discrete curve
evolution (DCE) \cite{Latecki99} or by using curvatures
\cite{hairong08}. We note that we use a \emph{single} hand-drawn
model for each object as in \cite{ferrari06,qihui08}. Hence the
salient parts can be obtained manually also. The identified salient
parts are the children of the full model. For example in Fig.
\ref{fig:swan-msrf} you can see the swan model is decomposed into
four salient parts represented by the RVs $\{F_i^1\}_{i=1}^4$.
\textbf{(2) Subdividing the salient contour parts:} The contour
parts identified by low-level might not be at same resolution as the
parts in the model. Hence the salient parts and the deformed salient
parts are subdivided further into smaller parts. For example the RVs
$\{F_i^0\}_{i=1}^6$ in Fig. \ref{fig:swan-msrf}. \textbf{(3)
Deforming salient parts:} The salient parts are \emph{individually}
deformed by translating and rotating and the newly deformed parts
become the children of the salient parts. Besides the flexibility
used in our shape similarity measures these deformed parts allow for
robust deformation. An improved shape context matching is also used
to cope up with the unstable decomposition problem as explained in
\S \ref{sec:two-phase}.

The RVs in the field have two different types of interactions namely
compatible and competing. If two RVs are connected by competing
interaction then only one of the RVs gets labeled and the other does
not. So the optimal labeling labels only one of the RVs in a clique
of competing RVs. There is a subtle difference between partial
labeling (because of competing interactions) and partial optimal
solutions obtained by methods like QPBO (\cite{kolmogrov07}): their
some labels are "unknown" while in our case we "know" that the RVs
don't get a label (or get a sink label). The corresponding graph
structure of the MSRF is fully connected. The compatible and
competing interactions resemble And/Or graphs
(\cite{hanzhu05,zhumumford07,chen08nips}) but our graph structure is
much more general because we can have compatible interactions across
scales and competing interactions in the same scale. Also we have
augmented MSRF structure in the sense the child RVs can interact
with non-parent RVs in a higher layer. This is similar to augmented
pyramidal graph structure of \cite{Bouman94}. Standard optimization
tools cannot be applied for the reasons discussed in \S
\ref{sec:intro}. For efficient optimization of the complex MSRF we
use append operator and a two phase search for label assignments
explained in \S \ref{sec:msrf-opt}. Once an optimal labeling is
obtained the corresponding labels in the image form the "group of
contours of the object". A sample grouping is shown in Fig.
\ref{fig:sample-apple}.
\begin{figure}[htb]
\begin{center}
\begin{tabular}{cc}
\includegraphics*[width=0.5\linewidth]{figs/swandecomp.eps}&
\includegraphics*[width=0.5\linewidth]{figs/aal_label.eps}
\end{tabular}
\end{center}
\caption{Left: Decomposed apple model. Right: Grouped contours in an
image.} \label{fig:sample-apple}
\end{figure}

\section{Discrete Optimization of Random Fields}\label{optimalRF}
In this section we explain how we optimize the RF posterior shown in
Eq. \ref{eq:max} so that we assign unique labels to RVs. We perform
a discrete optimization by cleverly searching through the space of
$P(n,m)$ configurations of $\mathcal{F}$.

Our goal is to find a discrete labeling assignment configuration
$f=(f_1, \dots, f_m) \in \mathcal{F}$ that maximizes the probability
$p(F=f)=p(F_1 =f_1, \dots, F_m=f_m)$, i.e.,
\begin{equation}\label{eq:discrete}
f^\ast = (f_1^\ast, \ldots, f_m^\ast) = \underset{(f_1, \ldots,
f_m)\in \mathcal{F}}{\operatorname{argmax}} p(F_1=f_1, \ldots,
F_m=f_m)
\end{equation}

The key idea of the proposed approach is to map each label
assignment to a point in a plane (or in general a low dimensional
Euclidian space). A particular mapping $C: F \times X \to R^2$ used
in our application of interest: contour grouping based on contour
part correspondence will be defined in Section <??>. For the
derivations in this section it suffice to say that $C(F_i,x_j) =
q_{ij} \in R^2 $ is a point representing the assignment $F_i=x_j$.
The idea is that $q_{ij}$ carries the centroid of the model shape to
the image based on the correspondence between the model contour
segment $s_i$ and the image edge segment $x_j$.

We observe that we have $mn$ centroids induced by $C$, i.e., $| C(F
\times X) | = mn$.

Let $K$ be a fixed integer and let $NN_K(q_{ij})$ denote $K$ nearest
neighbors (NN) of the point $q_{ij}$ in $C(F\times X) \subset R^2$.
A key assumption of the proposed approach is that there exists a
small constant $m\leq K<<n$ such that for all $f^\ast$s in Eq.
\eqref{eq:discrete} we have
\begin{equation}\label{eq:assumption}
\exists_{1 \leq i \leq m} \ \forall_{1 \leq j  \leq m} \ \
C(F_j,f_j^\ast) \in NN_K(C(F_i,f_i^\ast))
\end{equation}

Thus, if $f^\ast$ maximizes Eq. \eqref{eq:discrete}, then there
exists a centroid $C(F_i,f_i^\ast)$ whose $K$ nearest neighbors are
the centroids obtained from optimal assignments to all $F_j$s.

Therefore to find the optimal assignment, we need to examine $K$ NN
of each point in $C(F \times X)$. The $K$ centroids around each
point can be classified into $m$ classes based on the associated RV
($F_i\in F$). Let $c_1,c_2,\ldots,c_m$ be the number of centroids of
each class. The total number of configurations than can map to this
cluster then becomes the total number of ways the centroids can be
permuted into sequences of length $m$ which is $c_1c_2\ldots c_m$.
We have $\sum_{i=1}^m c_i=K$. Therefore an upper bound on the the
number of ways is $\left(\frac{K}{m}\right)^m$ since $\forall_i \
c_i\leq\frac{K}{m}$.

Since $|C(F\times X)|=nm$ the search complexity is
$mn\left(\frac{K}{m}\right)^m$ which is polynomial in $m$ and $n$
since $K$ is a small constant $K << n$ and
$\left(\frac{K}{m}\right)^m$ is bounded by a constant, as we will
show in a simple theorem \ref{thm:bound}.

We will maximize Eq. \eqref{eq:discrete} by an efficient search over
all possible assignments $f$.

It is important to note that in case where $K$ gets it maximum value
of $nm$ the search complexity becomes $O(n^m)$. The key to our
method is to exploit the geometrical properties of the image to keep
$K<<n$, in most cases to under $30$. In ideal case $K=m$.


\begin{thm}\label{thm:bound}
$O(\left(\frac{K}{m}\right)^m)=e^{K/e}$.
\end{thm}
\begin{proof}
Let $u=\left(\frac{K}{m}\right)^m$. $u$ takes maximum values when
$\frac{\partial\ln u}{\partial m}=0$.
\begin{align*}
&\ln u=m\ln\frac{K}{m}\\
\Rightarrow&\frac{\partial\ln u}{\partial m}=-1+\ln \frac{K}{m}
\end{align*}
Therefore $u$ takes maximum value at $m=\frac{K}{e}$ and the maximum
value is $e^{K/e}$.
\end{proof}



\section{Optimizing the MSRF}\label{sec:msrf-opt}
\textbf{(Definitely needs more work.)} In this section we explain
our append operator which simplifies the structure of an MSRF by
treating groups of competing RVs as one RV. In case of a continuous
relaxation of labeling our append operator produces a mixture of
distributions of the individual RVs while in discrete case it gives
a perspective of classifying RVs into categories...

In this section we explain how we minimize the potential of the MSRF
as described in Eq. \eqref{eq:min}. Our RF has two types of cliques:
(1) Single-site or unary and (2) $m$-ary where $m$ is the number of
model contour parts or in other words the number of RVs in the
field. Therefore the potential to be minimized is:
\begin{equation}\label{eq:our-potential}
U(f)=\sum_{R_i\in \mathcal{R}}V_1(f_i)+\sum_{\{R_i\}\in
\mathcal{C}_m}V_m(\{f_i\})
\end{equation}
where $\mathcal{C}_m$ is the set of $m$-ary cliques. When a model is
decomposed into a single scale all the interaction potentials are
compatible while competing interactions arise when the model is
decomposed into multi-scale. As discussed in \S \ref{sec:rfcv}
standard methods used to optimize RFs are not applicable in our case
since the interaction potentials are non-submodular and we need
full-labeling of the RF. Hence we introduce a two phase search. The
idea behind a two-phase search is to use the unary potentials to
roughly guide us to a "reasonable" labeling and then use the $m$-ary
potentials to pick the best one. The assumption is that the pruning
done by using unary potentials does not lose the globally optimal
labeling configuration. An overview is shown in Fig.
\ref{fig:two-phase-overview}. The first phase is common for both
single and multi-scale decompositions since it only involves unary
potentials. The second phase uses our \emph{append} operator for
"appending" the RVs with competing interactions.
\begin{figure}[htb]
\begin{center}
\includegraphics*[width=1\linewidth]{figs/twophasesflowchart.eps}
\end{center}
\caption{Overview of our two phase search algorithm. \textbf{(Figure
will be refined and details will be added in the caption.)}}
\label{fig:two-phase-overview}
\end{figure}
\subsection{The First Phase}\label{sec:first-phase}
In the first phase each RV i.e. model contour part finds $k$ most
likely labels that is $k$ most similar edge segments from the image.
Any reasonable local shape descriptor can be used to compute the
matching score. The more distinctive the better it is. In our case
we use very simple sequence of tangent directions along the segments
as a shape descriptor and use OSB \textbf{(citation will be added).}
to compute the matching score between the model contour part and
edge segment in the image. In other words for each RV we pick $k$
labels that have $k$ least unary potentials.
\begin{equation}\label{eq:unary}
V_1(f_i)=V_1(R_i=f_i)=LocalShapeDistance(R_i,f_i)
\end{equation}
Since the model contours have a full order, we use tangent
directions in the range $[0,2\pi]$. So each edge segment in the
image is matched in two different orientations and the best is
picked. Also using sequence of tangent directions makes our local
shape matching is scale invariant. For every model contour each of
these $k$ likely labels produces a scaled centroid of the object in
the image plane. There are several ways to obtain the centroids. In
our case we obtain the scale from the ratio of the lengths of the
image and model contour parts. The using the relation between the
model contour part and the centroid is used along with the estimated
scale to estimate the position of the centroid in the image plane.
There will be $km$ such centroids. These centroids provide important
cues to exploit the structure of search space of $P(n,m)$
configurations of the label assignments in our second phase of
search.
\subsection{The Second Phase}\label{sec:second-phase}
In the second phase we use $m$-ary potentials along with the
centroids obtained in the first phase to guide our search. As
mentioned before RVs interact with competing and compatible
interactions. We first introduce a new append operator to treat
cliques of competing RVs into one single append RV. If the MSRF can
be decomposed into $\mathcal{K}$ competing cliques as:
\begin{equation}
\mathcal{R}=\{\{R_i^0\}_{i=1}^{m_0},\{R_i^1\}_{i=1}^{m_1},\ldots,\{R_i^\mathcal{\mathcal{K}}\}_{i=1}^{m_\mathcal{K}}\}
\end{equation}
where $m_j$ is the number of RVs in the $j^{th}$ competing clique.
Then the append operator simplifies the MSRF into having only
$\mathcal{K}$ RVs as:
\begin{equation}
\oplus \mathcal{R}=\{\oplus T_1,\ldots,\oplus T_\mathcal{K}\}
\end{equation}
For example in Fig. \ref{fig:swan-msrf} there are four append RVs in
the simplified MSRF while in the original there are ten RVs. Two
append RVs are compatible if and only if there is at least one
compatible relation among the two sets of "appended" RVs. There are
no competing interactions among the new append RVs.

Now we use the $km$ centroids to obtain the final labeling
assignment for the $\mathcal{K}<m$ append RVs. Labeling an append RV
involves labeling only one of its appended RVs. The following
theorem and its proof explain our second phase search.
\begin{thm}
If the number of model contour parts is $m$ and $n$ is the number of
edge segments in the image then the upper bound on the number of
labeling configurations to be searched is
$O(nme^{\frac{\mathcal{N}}{e}})$. $\mathcal{N}$ is the number of
centroids that are used to form a cluster.
\end{thm}
\begin{proof}
Each label assignment to a RV gives a centroid. Hence there are a
total of $nm$ centroids. Each labeling configuration (that is label
assignment to all RVs) gives rise to a cluster of centroids.
According to our assumption the optimal labeling configuration gives
rise a dense cluster of centroids with $\mathcal{N}$ centroids.

Hence the goal now becomes searching through clusters of centroids
for feasible and optimal configuration. The number of clusters is
$nm$. Each cluster has a total of $\mathcal{N}$ centroids. The
centroids can be classified into $m$ classes based on the associated
RV. Let $c_1,c_2,\ldots,c_m$ be the number of centroids of each
class. The total number of configurations than can map to this
cluster then becomes the total number of ways the centroids can be
permuted into sequences of length $m$ which is $c_1\cdot
c_2\cdot\cdot c_k$. We have $\sum_{i=1}^m c_i=\mathcal{N}$.
Therefore an upper bound on the the number of ways is
$\left(\frac{\mathcal{N}}{m}\right)^m$.

Now for a given $\mathcal{N}$ which can be empirically chosen based
no the dataset we show an upper bound on
$\left(\frac{\mathcal{N}}{m}\right)^m$. Let
$u=\left(\frac{\mathcal{N}}{m}\right)^m$. $u$ takes maximum values
when $\frac{d\ln u}{dm}=0$.
\begin{align*}
&\ln u=m\ln\frac{\mathcal{N}}{m}\\
\Rightarrow&\frac{d\ln u}{dm}=-1+\ln \frac{\mathcal{N}}{m}
\end{align*}
Therefore $u$ takes maximum value at $m=\frac{\mathcal{N}}{e}$ and
the maximum value is $e^{\frac{\mathcal{N}}{e}}$.

Hence the total complexity is upper bounded by
$O(nme^{\frac{\mathcal{N}}{e}})$. It is important to note that in
case where $\mathcal{N}$ gets it maximum value of $nm$ the search
complexity becomes $O(n^m)$. The key to our method is to exploit the
geometrical properties of the image to keep $\mathcal{N}$ low in
most cases to under $30$.
\end{proof}
Its clear that if for each of the RV the $k$ likely labels has the
final globally optimal label then our two-phase search guarantees to
find the final global optimal assignment. The key contribution is
that \emph{design} of this search space which can be searched
through in a brute force way in a very efficient way. The value of
$\mathcal{N}$ needs to be set according to our confidence in the
scale estimation when computing the centroids. The more precise our
scale estimation the lesser $\mathcal{N}$ can be. Each of the label
configuration is used to compute the $m$-ary potential using our
improved shape context and the best configuration is chosen.
\section{Implementation Details}\label{sec:imp-details}
\subsection{Edge Linking}
Given an edge map by edge detector, it is not easy to get good
contour components based on it, especially when the edge map
includes a lot of noise, as Fig. \ref{figPBEdge} shows.

\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{figs/edge_linking/pb_edgemap.eps}
\begin{tabular}{c c}
(a) Original image. &  \quad (b) PB edge result.
\end{tabular}
\caption{An image and its edge map.}\label{figPBEdge}
\end{center}
\end{figure}

Fig. \ref{figPBEdge}(b) is the edge map using the method of PB [],
which is a very popular edge detector. A morphologic close operator
is applied to the edge map to make the edges more continuous. Then
we need to express it in the form of components. About how to
express it with components, there are two many possibilities, hence
first we need to define the rules of the components.

\begin{itemize}
\item \textbf{Definition 1} The length of each contour component
should be long. Definition 2 Contour components should be simple.

\item \textbf{Definition 2} Contour components should be simple.

\end{itemize} The two definitions are very easy to
understand. Definition 1 indicates that too short contour will be
deemed as noise, for noise is short and discrete generally, the
connotative meaning of Definition 1 is that short edges should be
connected to long edges if possible. Definition 2 defines the
connect rule, which means that contour components should be
connected with low curvature. And the contour components with high
curvature should be splitted. With this definition the edge map can
be expressed with fixed components, and the components will be very
convenient to be used for further matching.

The two definitions can be better understood by Fig.9.
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{figs/edge_linking/edge_rules.eps}
\caption{Improve edges by edge linking (from left to right, top to
down: (a),(b),(c) and (d)).}\label{figEdgeRule}
\end{center}
\end{figure}

According to these rules, first an edge linking [] step is
implemented, the edge map is converted to components marked with
different color as Fig. \ref{figEdgeLinkProcess} (a) illustrates. A
lot of short edges have been removed, and each joint will introduce
a break point for each edge; Then the contour components are further
improved by linking proper components, as Fig.
\ref{figEdgeLinkProcess}(b) illustrates; Then components with high
curvature are splitted, as Fig. \ref{figEdgeLinkProcess}(c)
illustrates; Again by removing short components we get results as
Fig. \ref{figEdgeLinkProcess}(d) shows. The components are then
ready for matching.

\begin{figure}[h]
\begin{center}
\includegraphics[width=9cm]{figs/edge_linking/edge_linking.eps}
\caption{Improve edges by edge linking (from left to right:
(a),(b),(c) and (d)).}\label{figEdgeLinkProcess}
\end{center}
\end{figure}

\subsection{Cliques: represented by center points}

A clique of Markov Random Field represents a set of components that
have neighbor relations. It is natural to use the idea of centroid
to represent the cliques $C$. Assignments from different contour
parts should have geometric consistency. Given a fixed scale, Each
assignment $(s_i, x_j)$ predicts an center point $cen_{i,j}$ in the
image, as Fig. \ref{figCentroid}(b) illustrates.

We use $u_{i,j}$ to indicate whether $s_i$ is assigned to $x_j$.
\begin{equation}
u_{i,j}  = \left\{ {\begin{array}{*{20}l}
   1, \quad if \ \ s_i \ \ matches \ \  x_j \\
   0, \quad otherwise \\
\end{array}} \right.
\end{equation}
and $U$ indicates an union of assignments.

For the correct configuration $\widehat U$ of matching, all the
predicted center $cen_{i,j}$ should be close to each other, it is
represented as:
\begin{equation}\label{eqCen1}
\forall u_{i,j}, u_{i',j'} \in \widehat U, \quad \|cen_{i,j}u_{i,j}
- cen_{i',j'}u_{i',j'}\| < d
\end{equation}
For the convenience of calculation, we set a center point
$cen^{ref}$ as reference point, which is one center point predicted
by a salient assignment $f_{i_o} = j_o$. Then we replace
\ref{eqCen1} with:
\begin{equation}\label{eqCen2}
\forall u_{i,j} \in \widehat U, \quad \|cen_{i,j}u_{i,j} -
cen^{ref}| < d_{max}
\end{equation}

An example is given in Fig. \ref{figCentroid}(c). The reference
point is indicated by the 'red star' point, the center points
predicted by the correct configuration are indicated by the color
spot, there are very close to the reference point.

Benefit from the low complexity of one-to-one matching, we can
maintain a lot of reference points for a image, it highly reduces
the risk of missing optimal configuration. The reference points are
center points predicted by some salient assignment, i.e. the two
assigned segments that are more similar to each other. The transform
scale is also evaluated by the salient assignments.

The similar is measured by the tangent direction of sample points on
contour segments using Smith-Waterman 's time series method.[](more
discussion about unary similarity?)

Each contour segment in the model find two assignment, assume that
there are $m$ segments in the model, we will maintain $2m$ cliques,
then a brute force searching for the optimal configuration is
implemented within each cliques.

\begin{figure}[h]
\begin{center}
\begin{tabular}{c c}
\includegraphics[width=3cm]{figs/centroid/model_giraffe.eps} &
\includegraphics[width=5cm]{figs/centroid/steltope_edge.eps} \\
(a) & (b)\\
\end{tabular}
\includegraphics[width=6cm]{figs/centroid/cenp_range.eps}\\
(c)\\
\caption{A clique is represented by the set of some center points
within a certain range.}\label{figCentroid}
\end{center}
\end{figure}

\subsection{Calculate Energy using Shape Context}
We have got the dynamic centroids. Assume that for a reference point
$rp$, we get a clique of $N_{rp}$ nearest points, say $C \equiv
\{c_1, c_2, \dots, c_{N_{rp}}\}$. Each point $c_k$ corresponds to an
assignment $F_i = j$, where $i$ is a node on the model graph, and it
further belongs to a tree $T_m$. Assume that there are $M$ trees in
the model, say $T = \{T_1, T_2, \dots, T_M\}$. We implement a brute
force searching in the clique $C$. Each time we select $M$ points
from the clique, they have disparate correspondence in $T$. Which
make a configuration of one-to-one matching for each $T_m$. Assume
the configuration is $\widehat{f} = \{f_{i_1} = j_1, f_{i_2} = j_2,
\dots, f_{i_M} = j_M\}$ which is the contribution of $M$ points in
clique $C$, then the configuration tells two set of contour segment
selection, they are contour segments from model $\widehat{s} =
\{s_{i_1}, s_{i_2}, \dots, s_{i_M}\}$ and contour segments from
image $\widehat{x} = x_{i_1}, x_{j_2}, \dots, x_{j_M}$.

We aim at finding out one configuration from all cliques $C$s that
minimizes the energy function $U(f|X) = \sum _{c \in C} V_c(f)$. It
can be expressed as

\begin{equation}
\mathop {\min }\limits_{\widehat{f} \in C_1, C_2, \dots}
\sum\limits_{c \in \widehat{s}, \widehat{x}}V_{c}\widehat{f}
\end{equation}

Shape Context (SC) [] has been proved to be a very good approach to
measure the similarity between shapes. Here, it is employed to
measure the shape distance between the selected contour set
$\widehat{s}$ from model and $\widehat{x}$ from image, the score is
severed as the energy score:
\begin{equation}
U(\widehat{f}|X) = \sum\limits_{c \in \widehat{s},
\widehat{x}}V_{c}\widehat{f} = SC(\widehat{s}, \widehat{x})
\end{equation}
In which $SC$ denotes the shape distance resulted from Shape
Context.

\subsection{Improve the Matching accuracy by sample points reduction}
\begin{figure}[h]
\begin{center}
\begin{tabular}{c c}
\includegraphics[height=3cm]{figs/newsc/model.eps} &
\includegraphics[height=3cm]{figs/newsc/straford_map.eps}\\
(a) & (b)\\
\end{tabular}
\begin{tabular}{c c c}
\includegraphics[height=2cm]{figs/newsc/model_scmap.eps} &
\includegraphics[height=2cm]{figs/newsc/straford_map_equalsample_mg.eps}
&
\includegraphics[height=2cm]{figs/newsc/straford_oversample_mg.eps}\\
(c) & (d) & (e)
\end{tabular}
\caption{Improve shape matching by sample points
reduction.}\label{figNewSC}
\end{center}
\end{figure}

The multi-scale decomposition of model contributes to a flexible
model, which offers a more suitable shape matching compare to a
single scale model. However, on the side of image, it is very hard
to do such things. Edge linking is low level processing, we try to
link short edges to form relative long and straight chains. However,
there also may exist some long edges such as the red edge in Fig.
\ref{figNewSC}(b). A part of this edge is belongs to the neck of
swan, another part belongs to noise. This extra part will influence
the matching score if the general Shape Context algorithm is
adopted. The matching result is shown in Fig. \ref{figNewSC}(d).
Where, we apple uniform sampling for selected contour segments both
in the model and image, say 50 points are chosen via uniform
sampling. For a general Shape Context, it implement a 50 to 50
points matching, and shape distance score is given by the matching
process. However, some points belong to noise (Fig.
\ref{figNewSC}(d)), we got a score of 13.44, and if we draw a
bounding box of the detection result, almost half of the bounding
box area will contribute to noise.

We introduce a novel Shape Context measurement as a remedy to this
problem. We replace selecting equal sample points with unequal
sample point from the set of contour segments both in model and
image. The sample points in image are more than those in model.
Although Shape Context approach only offers uniform matching (the
number sample points in model and image should equal to each other),
we still can build a non-square matrix to calculate the cost between
points. Then, by removing some extra points in image, we will obtain
a square matrix which permits us to calculate the shape distance
score. We aim to remove the points belonging to noise and reserve
useful points as many as we can.

\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{figs/newsc/newscmap2.eps}
\caption{The flowchart of our improved Shape
Context.}\label{figSCReduction}
\end{center}
\end{figure}

As Fig. \ref{figSCReduction} illustrates, we sample 50 points in
model and 62 points in image. The Shape Context algorithm builds a
50 by 62 matrix, each matrix element represents the shape distance
between two points (see Fig. (\ref{figSCReduction})(c)). In which,
red color represents a high cost, and blue color represent low lost.
We sort the cost matrix by column. Each point in image finds 5
lowest cost, it means that each point in image finds 5 most similar
points in model. Then a 5 by 62 matrix is built (see Fig.
(\ref{figSCReduction})(e))). We observe that the image points
belonging to noise usually have higher cost than useful points.
Then, we remove the extra 12 points with higher cost from image
points, it means that we remove 12 columns from the matrix in Fig.
(\ref{figSCReduction})(c). Finally, a 50 by 50 matrix is build, and
the final result is given in Fig. (\ref{figSCReduction})(g). The
noise points are well removed. We obtain a lower energy of 10.66
compared to general Shape Context (energy is 13.44). Some more
examples of the improved Shape Context can be found in Fig.
\ref{figNewSCMoreExample}.
\begin{figure}[h]
\begin{center}
%\begin{tabular}{c c c}
\includegraphics[width=2cm]{figs/newsc/high_model.eps}
\includegraphics[width=3cm]{figs/newsc/high_equal.eps}
\includegraphics[width=3cm]{figs/newsc/high_over.eps}\\
\includegraphics[width=2cm]{figs/newsc/big_model.eps}
\includegraphics[width=3cm]{figs/newsc/big_equal.eps}
\includegraphics[width=3cm]{figs/newsc/big_over.eps}\\
\includegraphics[width=2cm]{figs/newsc/whooper_model.eps}
\includegraphics[width=3cm]{figs/newsc/whooper_equal.eps}
\includegraphics[width=3cm]{figs/newsc/whooper_over.eps}\\
%\end{tabular}
\caption{Some more examples of the improved Shape Context for images
with extra long contours.}\label{figNewSCMoreExample}
\end{center}
\end{figure}

It is worth to note that for images with few noise, the improved
Shape Context will influence the cost and matching. Sometimes the
cost is less than general Shape Context (see the first row of Fig.
\ref{figNewSCNoNoise}), and sometimes the cost is higher (see the
second row of Fig. \ref{figNewSCNoNoise}). The influence is not too
much, and both of the two examples still give very reasonable points
reduction results, Compared to the model, both of the images have
dissimilar parts at the root of neck, and the removed points mainly
concentrate in this area.

\begin{figure}[h]
\begin{center}
%\begin{tabular}{c c c}
\includegraphics[width=2cm]{figs/newsc/high_model.eps}
\includegraphics[width=3cm]{figs/newsc/mute_equal.eps}
\includegraphics[width=3cm]{figs/newsc/mute_over.eps}\\
\includegraphics[width=2cm]{figs/newsc/big_model.eps}
\includegraphics[width=3cm]{figs/newsc/wyndley_equal.eps}
\includegraphics[width=3cm]{figs/newsc/wyndley_over.eps}\\
%\end{tabular}
\caption{Results of improved Shape Context for images with few
noise.}\label{figNewSCNoNoise}
\end{center}
\end{figure}

\subsection{Complexity evaluation}
There are mainly three stages needing some computation. The
preprocess of edges is linear associated to the total length(count
by pixels) of the edges, usually, it costs us about 2 seconds on
edges linking on a personal computer with a 2.3G CPU using Matlab.

Time series is used to calculate the unary similarity between couple
of segments. We use Smith-Waterman's method [] to obtain the unary
similarity. For one pair of segments $(s_i, x_j)$, where $s_i$ is
from model and $x_j$ is from image, we consider that each segment is
a directed segment. Then, we need calculate Smith-Waterman's method
twice to obtain the similarity. The complexity is proportional to
$m_s \times n_s$, where the complexity, where $m_s$ and $n_s$ is the
number of sample points for segment $s_i$ and $x_j$. We assume that
there is $m$ segment in the model and $n$ segment in the image. Then
the total calculation time is proportional to $m \times n \times m_s
\times n_s$. Usually, we take 20 sample points from each segments.
The Smith-Waterman method cost about 0.01 second for one pair of
segments $(s_i, x_j)$ on our 2.3G CPU computer. Usually, there are
usually no more than 10 segments in the model, and dozes of segments
in the image. Then the total time for this stage may reach up to
several seconds.

The calculating time for those two stages mentioned above won't vary
too much, However, in the stage of brute force measuring each
configuration with Shape Context, things are different. The
calculating time at this stage is: $\sum_{i = 1}^{N_C} t_C(i)$.
Where, $N_C$ is the number of cliques, the size is fixed to $2m$,
i.e., twice of the segment number in the model. $t_C(i)$ represent
calculating time for each clique $C_i$.

We implement a brute force calculation for all configurations $f_T
\longrightarrow X$. The complexity increase exponentially with the
size of $C_i$. Fig. \ref{figComplexity} and Table
\ref{tblComplexity} illustrate the numbers of configurations
according to size of and the number of tree structures of model in
the \emph{worst case}. A clique size of 30 may lead to 62077 times
calculation.

The size of cliques should be well restricted. Fortunately, the
clique size is associated to the number of segments in the model,
and usually there are around 10 segments in the model. We
experientially set the clique size between [15, 20].

Although 1568 (the upper bound for clique size 20) is not a big
number, the calculating time is still very high. Shape Context costs
about 0.1 second for one calculation, if we consider 20 cliques, the
total time may reach to $1568 \times 0.1 \times 20 = 3136 sec$,
which is still unacceptable. In our work, we precalculate the energy
using time series as the reference score, this is easily
accomplished by several addition of unary similarity score, the can
be ignored.

Then we can select 100 configurations with higher reference score,
and apply Shape Context to them. The configurations with lowest
energy is selected as the final configuration.

In addition, the number of tree structures also influences the
complexity a lot, in our work, we also mostly keep four tree
structures in the model. Then the upper bound of calculation times
is 3167 for clique size 30, and 625 for clique size 20.

In the experiments, we always fix the clique size to 20. And the
average time for each image is around 15 seconds, including
everything.

\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm]{figs/complexity/complexity.eps}
\caption{Times of calculation according to different size of
cliques.}\label{figComplexity}
\end{center}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  Clique Size & 10 & 15 & 20 & 25 & 30 \\
  \hline
  tree number:4 & 39 & 198 & 625 & 1526 & 3164 \\
  max value & 40 & 249 & 1568 & 9865 & 62077 \\
  \hline
\end{tabular}
\caption{Max times of calculation and times when number of trees is
equal to 4. (precison: 1)}\label{tblComplexity}
\end{center}
\end{table}

\section{Experimental Results}\label{sec:exp-results}
We perform our detection approach using only one hand-drawn model
without negative training images. To evaluate our performance, we
choose the challenging ETHZ Shape Classes [] containing five diverse
object categories with 255 images in total. Each images has one or
more object instances. All categories have significant scale chages,
illumination changes and intra-class variations. Morevoer, many
objects are surrounded by extensive background clutter and have
interior contours. We have the same experimental setup as [Qihui
ECCV08], using only a single hand-drawn model for each class.

We first decompose models to multiscale level, and then edge linking
and breaking are applied to all of the edge images. Some noise with
short edge length are automatically removed. Then the edge-segments
are ready for matching. Assume there are $m$ segments in the model,
and $n$ edge segments in the image. $m$ varies from 5 to 10 for
different model shapes. We build a $m \times n$ similarity matrix by
comparing the tangent direction of 20 sample points on each segments
using Smith-Waterman's method. Each index is an possible assignment
from model to image. It predicts a center points and a scale. We
initialize $2m$ reference points from these center points. For each
reference point, it has a corresponding scale. we re-estimate all
center points according to the scale of reference point. We create a
cluster for each reference point by searching 20 nearest points.
Brute force searching is applied to each cluster to find the best
configuration. To reduce calculation, we threshold all
configurations with unary similarity (evaluated previously by
tangent direction). The configurations with the similarity score
higher than the threshold are further evaluated by our improved
Shape Context to find the optimal configuration. Shape context for
contour selection has 12 polar angles, 5 radial bins and fixed
direction. We sample 50 points from model segments and 60 points
from image edge segments. The scale is evaluated again by Shape
Context. Precision vs Recall (P/R) curve is used for quantitative
evaluation.

We make comparisons with Contour Selection [Qihui ECCV08] on each
object category. Both methods involve shape decomposition, edge
linking and shape matching with Shape Context. The advantage of
Contour Selection is set-to-set matching which allows many to many
matching. The shortages are that the complexity is relatively high,
even though Linear Programming is applied. Being restricted to their
algorithm, Shape Context is performed just on several control
points. Which means that the energy score is sensitive to control
points, thus control points should be well designed. The size of
model template should be specified previously, thus the method is
not really scale-invariant.

The strategy of model decomposition and edge linking of our method
make it possible for one-to-one matching. Our multiscale model and
improved Shape Context make a flexible configuration, and it well
alleviates the problem of one-to-one matching. The complexity is
much lower than set-to-set matching. It allows us to use full Shape
Context to do shape matching. Which is better than Shape Context on
several control points. In addition, the improved Shape Context
helps us remove noise of imperfect edge segments.


Our final result can be found in Fig. \ref{figExpContourSelection}.
As a comparison, the P/R curves of Contour Selection are also given.
ETHZ dataset provides the ground truth bounding box for each image.
In the experiments for our method, when a bounding box of a detected
result covers more than 50\% of the ground truth bounding box, it is
deemed to be a correct detection. Our algorithm are better in two
categories and similar in the other three categories. We also make a
table to compare the precision. We calculate the precision under
under a fixed Recall 80\%. The precisions are given in Table
\ref{tblExpvsCoutourSelection}. It is worth to mention that for our
method, the average processing time for one image is around 15
seconds on a computer with 2.3G CPU and Matlab. The processing time
for Contour Selection is 2-3 minutes since the complexity is much
more higher.


\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{figs/experiments/vsUppen1.eps}\\
\caption{Comparison with ECCV08:Contour Selection on ETHZ dataset.
Both methods use only one hand-drawn model shape to retrieve objects
from entire 255 images. Both method involves shape decomposition,
edge-linking, and shape matching. Our method have significantly
better performance on the categories of 'Applelogos' and 'Mugs', and
have comparable performance on the categories of 'Bottles',
'Giraffes' and 'Swans'. Note that our method is fully
scale-invariant and Contour Selection should set the scale of
transform previously. And our algorithm is more time efficient,
since set-to-set matching is much more complex than one-to-one
matching. The processing time for our method is averagely 15 seconds
per image on a 2.3G CPU personal computer, and Contour Selection
takes about 2-3 minutes per image. }\label{figExpContourSelection}
\end{center}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
  \hline
   %after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   \  & Applelogos & Mugs & Bottles & Swans & Giraffes \\
  \hline
  Our Precision & \textbf{94\%} & \textbf{47\%} & 79\% & 46\% & 56\% \\
  Contour Selection & 50\% & 28\% & 78\% & 46\% & 58\% \\
  \hline
\end{tabular}
\caption{Comparison of precision with Contour Selection [], we
compare the precision by fixing the recall to
80\%.}\label{tblExpvsCoutourSelection}
\end{center}
\end{table}
\section{Conclusion And Discussions}\label{sec:concl-disc}
We introduce a novel multi-scale random field interpretation to
handle contour grouping problem. Since edges, and consequently,
contour parts vary significantly in real images, it is necessary to
make decomposition of model contours into segments flexible. The
proposed multi-scale construction permits us to have a very flexible
decomposition that can adapt to different configurations of contour
parts in the image. We applied the new algorithm to the ETHZ data
set to illustrate the application potential of the proposed method.

\bibliographystyle{IEEEtran}
\bibliography{Z:/RobotMappingWriting/Bib/RobotMapping/EMrobot,Z:/RobotMappingWriting/Bib/RobotMapping/FFS,Z:/RobotMappingWriting/Bib/Shape/shape,Z:/RobotMappingWriting/Bib/Shape/contours,Z:/RobotMappingWriting/Bib/BMI/bmi,Z:/RobotMappingWriting/Bib/Shape/seg,Z:/RobotMappingWriting/Bib/Shape/Symmetry}

%\begin{IEEEbiography}{ChengEn Lu}
%Biography text here.
%\end{IEEEbiography}
%\begin{IEEEbiography}{Nagesh Adluru}
%Biography text here.
%\end{IEEEbiography}
%\begin{IEEEbiography}{Longin Jan Latecki}
%Biography text here.
%\end{IEEEbiography}
\end{document}
