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

\usepackage{cvpr}
\usepackage{times}
\usepackage{url}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{array}

% 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=false]{hyperref}


\def\I{{\bf I}}
\def\B{{\bf B}}
\def\R{{\bf R}}
\def\H{{\bf H}}
\def\A{{\bf A}}
\def\corr{{\rm corr}}
\def\E{{\rm E}}
\def\P{{\bf P}}
\def\H{{\bf H}}
\def\J{{\bf J}}
\def\SUM1{{\bf SUM1}}
\def\MAX1{{\bf MAX1}}
\def\SUM2{{\bf SUM2}}
\def\MAX2{{\bf MAX2}}
\def\SUM3{{\bf SUM3}}
\def\mI{{\bf mI}}

\cvprfinalcopy % *** Uncomment this line for the final submission

\def\cvprPaperID{585} % *** Enter the CVPR Paper ID here
\def\httilde{\mbox{\tt\raisebox{-.5ex}{\symbol{126}}}}

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

%%%%%%%%% TITLE
\title{Unsupervised Learning of Dictionaries of Hierarchical Compositional Models}

\author{Jifeng Dai$^{1,4}$, Yi Hong$^{2}$, Wenze Hu$^{3}$, Song-Chun Zhu$^{4}$, and Ying Nian Wu$^{4}$\\
$^{1}$Tsinghua University, China\\
{\tt\small daijifeng001@gmail.com}\\
$^{2}$ WalmartLab, USA\\
{\tt\small yihongucla@gmail.com}\\
$^{3}$Google Inc, USA\\
{\tt\small wenzehu@google.com}\\
$^{4}$University of California, Los Angeles (UCLA), USA\\
{\tt\small \{sczhu, ywu\}@stat.ucla.edu}}


\maketitle
%\thispagestyle{empty}

%%%%%%%%% ABSTRACT
\begin{abstract}

This paper proposes an unsupervised method for learning dictionaries of hierarchical compositional models for representing natural images. Each model is in the form of a template that consists of a small group of part templates that are allowed to shift their locations and orientations relative to each other, and each part template is in turn a composition of Gabor wavelets that are also allowed to shift their locations and orientations relative to each other. Given a set of unannotated training images, a dictionary of such hierarchical templates are learned so that each training image can be represented by a small number of templates that are spatially translated, rotated and scaled versions of the templates in the learned dictionary. The learning algorithm iterates between the following two steps: (1) Image encoding by a template matching pursuit process that involves a bottom-up template matching sub-process and a top-down template localization sub-process. (2) Dictionary re-learning by a shared matching pursuit process. Experimental results show that the proposed approach is capable of learning meaningful templates, and the learned templates are useful for tasks such as domain adaption and image cosegmentation.

\end{abstract}

% introduction part
\section{Introduction}

{\bf Motivation.} Learning dictionaries of representational units for describing natural images is one of the most fundamental problems in vision. One of the most successful framework for solving this problem is sparse coding \cite{olshausen1996emergence,olshausen2001learning}. By enforcing sparsity of the coefficients in the linear representations of natural image patches, a dictionary of Gabor-like basis functions can be learned, so that each training image patch can be represented or approximated by a linear combination of a small number of basis functions selected from the dictionary. An important question then is how to continue to learn higher-level representational units based on the learned basis functions. Such representation units may capture frequently occurring patterns that are more specific about the objects and scenes. They may lead to sparser representations, and they may be useful for object recognition and scene understanding.


\begin{figure}
  \centering
    \includegraphics[width=0.5\textwidth]{./image/illustration.pdf}\\
  \caption{(a) Three hierarchical compositional templates learned from 24 camel images without annotation. Each of the templates is composed of 9 part templates, and each part template is composed of a set of Gabor wavelets. Each Gabor wavelet is illustrated by a bar at the same location and orientation and with the same length as that wavelet. (b) 5 samples of the input images. (c) Encoding of the sample images by the activated deformed templates.}
  \label{Fig:illustration}
\end{figure}


{\bf Overview of our method.} Our goal is to develop an unsupervised method for learning such representational units, based on the simple observation that the basis functions (Gabor wavelets) selected for representing the training images form various compositional patterns, and the composition can be hierarchical. Thus we propose to model the representational units as hierarchical compositions of Gabor wavelets. Fig. \ref{Fig:illustration} illustrates the basic idea. A small dictionary of three hierarchical compositional templates (head, body and leg) are learned from a set of input images of camels that are not a priori aligned or annotated. Each hierarchical compositional template is composed of a group of part templates that are allowed to shift their locations and orientations relative to each other. Each part template is in turn composed of a group of Gabor wavelets (illustrated by bars in Fig. \ref{Fig:illustration} ) that are allowed to shift their locations and orientations relative to each other. These templates capture distinct and specific image patterns and the same template is matched to similar image patches in different images by spatial translations, rotations, scalings and deformations. We focus on unsupervised learning of dictionaries of such templates.

{\bf Experiments and performances.} We have tested the proposed approach for image representation, domain transfer and cosegmentation. Experimental results show that the proposed approach is capable of learning meaningful representational units. Higher accuracies than previous approaches are achieved on the four domain benchmark \cite{saenko2010adapting} for domain transfer, and on the ImageNet \cite{deng2009imagenet} dataset for cosegmentation.

{\bf Prior work.} Hierarchical compositional models are very popular for modeling patterns of objects, see \cite{fidler2007towards,schlecht2007inferring,zhu2008unsupervised,todorovic2008unsupervised,geman2002composition,zhu2010latent,si2013learning} for some examples. Many existing approaches to learning hierarchical compositional models are usually supervised where the object bounding boxes are given \cite{felzenszwalb2010object,zhu2010latent} or weakly supervised where images are labeled and roughly aligned \cite{fidler2007towards,si2013learning}. In this paper, we learn dictionaries of hierarchical compositional templates from unaligned natural images without annotations, which is more challenging. In comparison to our past work, \cite{hong2012unsupervised} is concerned with learning templates with only one layer of deformations, while \cite{si2013learning} is concerned with learning a single template instead of learning a dictionary of multiple templates.

Our work bears some similarities to \cite{fidler2007towards, zhu2008unsupervised}, which seek to organize the compositions of Gabor wavelets or edgelets into hierarchical structures. The hierarchical structures in \cite{fidler2007towards, zhu2008unsupervised} are learned layer-by-layer in a bottom-up manner. Once the lower layers are learned, they are fixed in the subsequent learning of higher layers. In our iterative learning algorithm, the part templets are re-learned and the Gabor wavelets are re-selected in each iteration, so the learning is more top-down than bottom-up. Please refer to Fig. \ref{Fig:iteration} for the iterative learning process.

Our work is also related to \cite{ahuja2007extracting,lin2009layered,lee2010skewed,hong2012unsupervised,singh2012unsupervised,li2013harvesting,Liu2013GRASP}, where repeated patterns are learned from the input images. In \cite{singh2012unsupervised,li2013harvesting}, a set of HOG templates are learned from multiple input images of the same object category. In \cite{Liu2013GRASP}, recurring tuples of visual words are extracted from single image with repetitive patterns. Unlike our method, they learn simple rigid templates from the images. Our method learns a dictionary of hierarchical deformable templates, which are more flexible.

\section{Hierarchical Compositional Model}

\begin{figure}
  \centering
  \begin{tabular}{cc}
    \includegraphics[width=0.5\textwidth]{./image/AOT_evolution_6.png}\\
  \end{tabular}
  \caption{Visual elements in the layered dictionaries, which form a hierarchical
compositional structure.}
  \label{Fig:layered_dictionary}
\end{figure}

We represent an image $\I$ using a dictionary of hierarchical compositional templates. As shown in Fig. \ref{Fig:layered_dictionary}, each hierarchical compositional template is decomposed into a set of shiftable part templates, and each part template is further decomposed into a set of shiftable Gabor wavelets. The representational units at different layers of the model can be organized in layered dictionaries $\Delta^{(j)}$. Table \ref{table:primitives} defines the dictionaries and elements, their parameters and the allowed ranges of values, which we shall elaborate in the following.

\subsection{Layered dictionaries}

\begin{table*}
\begin{center}
\scalebox{.85}{
\begin{tabular}{>{\centering}m{2cm}  >{\centering}m{2.5cm}  >{\centering}m{3.5cm}  >{\centering}m{5.5cm} >{\centering\arraybackslash}m{2.5cm}}
\noalign{\smallskip}\hline \noalign{\smallskip}
\textbf{Layer ID} & \textbf{Template type} & \textbf{Parameters} & \textbf{Deformation Range}  & \textbf{Template Size} \\
\noalign{\smallskip}\hline \noalign{\smallskip}
${\Delta^{(5)}}$, ${\Delta^{(4)}}$ & Hierarchical compositional template & ${\rm Activated \, template} \, t_k \newline \widetilde{L_k} = ({\rm position} \, \widetilde{X_k}, \newline {\rm scale} \, \widetilde{S_k}, \newline {\rm orientation} \, \widetilde{O_k})$ & $\widetilde{X_k} \in {\rm image \, domain} \, \Lambda \newline \widetilde{S_k} = \{0.8,1,1.2\} \newline \widetilde{O_k} = \{-2,-1,0,1,2\}\times \pi/16$ & $120 \times 120$ pixels\\
\noalign{\smallskip}\hline \noalign{\smallskip}
${\Delta^{(3)}}$, ${\Delta^{(2)}}$ & Part template & $L = ({\rm position} \, X, \newline {\rm scale} \, S, \newline {\rm orientation} \, O)$ & $\delta X = \{-2,0,2\} \times \{-2,0,2\} \, {\rm pixels} \newline \delta O = \{-1,0,1\}\times \pi/16$ & $40 \times 40$ pixels\\
\noalign{\smallskip}\hline \noalign{\smallskip}
${\Delta^{(1)}}$, ${\Delta^{(0)}}$ & Gabor wavelet & $l = ({\rm position} \, x, \newline {\rm scale} \, s, \newline {\rm orientation} \, o)$ & $\delta x = \{-1,0,1\} \times \{-1,0,1\} \, {\rm pixels} \newline \delta o = \{-1,0,1\}\times \pi/16$ & $13 \times 13$ pixels\\
\noalign{\smallskip}\hline \noalign{\smallskip}
\end{tabular}}
\end{center}
\caption{List of visual concepts used in our hierarchical compositional templates, their parameters, deformation ranges.}
\label{table:primitives}
\end{table*}

$\Delta^{(5)}$ is the dictionary of hierarchical compositional templates
\begin{equation}
\Delta^{(5)} = \{H^{(t)}, t=1, ..., T\}.
\end{equation}
The hierarchical templates capture the frequently occurring patterns in the input images.


$\Delta^{(4)}$ contains the spatially translated, rotated and scaled versions of the hierarchical compositional templates in $\Delta^{(5)}$ for image representation. For an image $\I$, we encode it by $K$ activated templates, which are spatially translated, rotated and scaled copies of the hierarchical compositional templates picked from $\Delta^{(5)}$. Let $H_{\widetilde{L_k}}^{(t_k)}$ be the $k$-th activated template of type $t_k$,  let $\widetilde{L_k} = (\widetilde{X_k}, \widetilde{S_k}, \widetilde{O_k})$ be its geometric attribute, where $\widetilde{X_k}$ is the location, $\widetilde{S_k}$ is the scale, and $\widetilde{O_k}$ is the orientation  of the activated template. Then the set $\partial H^{(t)} = \{H_{\widetilde{L_k}}^{(t_k)}, t_k=t\}$ forms an equivalent class of $H^{(t)}$.  $\Delta^{(4)}$ is the union of all possible activated templates:
\begin{equation}
\Delta^{(4)} = \cup \, \partial H^{(t)}, \quad \mathrm{for} \quad H^{(t)} \in \Delta^{(5)}.
\end{equation}


$\Delta^{(3)}$ denotes the dictionary of part templates of the activated hierarchical compositional templates in $\Delta^{(4)}$. Let $P^{(t,v)}$ denote the $v$-th part template within $dH^{(t)} \in \Delta^{(4)}$, then $dH^{(t)}$ can be decomposed into
\begin{equation}
\begin{aligned}
dH^{(t)} =  (P_{L_{v}}^{(t,v)}, v=1, ..., V),
\end{aligned}
\nonumber
\end{equation}
where $V$ is the number of part templates, $L_{v}=(X_{v}, S_{v}, O_{v})$ is the geometric attribute of the $v$-th part template, where $X_{v}$, $S_{v}$ and $O_{v}$ are the relative position, scale and orientation respectively. Here we fix the model structure by assigning $9$ non-overlapping part templates arranged into a $3 \times 3$ grid to each hierarchical compositional template. Then $\Delta^{(3)}$ is the collection of all the part templates
\begin{equation}
\begin{aligned}
\Delta^{(3)} = \{P^{(t,v)}, t=1, ..., T, v=1, ..., V\}.
\end{aligned}
\end{equation}

$\Delta^{(2)}$ includes all the shifted part templates. We allow each $P^{(t,v)}$ in $\Delta^{(3)}$ to translate and rotate within a small bounded range to account for object deformations in different images. Let $\delta L=(\delta X, 0, \delta O)$ be the shift within the bounded range, then we derive a set of shifted part templates $\{P^{(t,v)}_{\delta L}\}$ for each $P^{(t,v)}$ in $\Delta^{(3)}$. Let $\partial P^{(t,v)}$ denote the equivalent class of $P^{(t,v)}$ subject to bounded shifts. Then $\Delta^{(2)}$ is the union of all the shifted part templates
\begin{equation}
\begin{aligned}
\Delta^{(2)} = \cup \, \partial P^{(t,v)}, \quad \mathrm{for} \quad P^{(t,v)} \in \Delta^{(3)}.
\end{aligned}
\end{equation}

$\Delta^{(1)}$ contains the Gabor wavelets in the deformed part templates in $\Delta^{(2)}$. Following the active basis model in \cite{wu2010learning}, the basis elements $B$ are chosen to be Gabor wavelets at different positions and orientations. A deformed part template $dP^{(t,v)} \in \Delta^{(2)}$ is decomposed into a group of Gabor wavelets with zero mean and unit $\ell_2$ norm
\begin{equation}
\begin{aligned}
    dP^{(t,v)} = (B_{l_{t,v,i}}, i = 1, ..., n),
\end{aligned}
\nonumber
\end{equation}
where $B_{l_{t,v,i}}$ is the $i$-th Gabor wavelet with geometric attribute $l_{t,v,i}=(x_{t,v,i}, s_{t,v,i}, o_{t,v,i})$. Here the geometric attribute $l_{t,v,i}$ for each $B_{l_{t,v,i}}$ is not prefixed, but to be learned from the input images. Therefore, $\Delta^{(1)}$ is a set of Gabor wavelet elements decomposed from $\Delta^{(2)}$
\begin{equation}
\begin{aligned}
    \Delta^{(1)} = \{B_{l_{t,v,i}} \in dP^{(t,v)}, \quad dP^{(t,v)} \in \Delta^{(2)}\}.
\end{aligned}
\end{equation}

$\Delta^{(0)}$ contains the shifted Gabor wavelets in $\Delta^{(1)}$, which ground the templates onto image pixels. For each wavelet $B_{l} \in \Delta^{(1)}$, we allow translations and rotations within bounded ranges and derive a shifted set $\partial B_l = \{B_{l+\delta l}\}$, where $\delta l = (\delta x, 0, \delta o)$. Then $\Delta^{(0)}$ is the union of all these shifted Gabor wavelets
\begin{equation}
\begin{aligned}
    \Delta^{(0)} = \cup \, \partial B_l, \quad \mathrm{for} \quad B_l \in \Delta^{(1)},
\end{aligned}
\end{equation}
where each Gabor wavelet is the translated and rotated version of the original one.

As a summary, dictionaries $\Delta^{(j)}, j=5,4,3,2,1,0$ form a hierarchical compositional representation of the visual patterns. $\Delta^{(5)}$ is decomposed to $\Delta^{(3)}$, and $\Delta^{(3)}$ is decomposed to $\Delta^{(1)}$. $\Delta^{(4)}$ is the activated and shifted version of $\Delta^{(5)}$; while $\Delta^{(2)}$ and $\Delta^{(0)}$ are the shifted versions of $\Delta^{(3)}$ and $\Delta^{(1)}$ respectively.


\subsection{Probabilistic modeling}

Given an input image $\I$, we encode the visual patterns in $\I$ by $K$ activated hierarchical compositional templates that are shifted instances of the templates in the dictionary. For now, let us assume that these $K$ templates as well as their part templates and Gabor wavelets do not overlap with each other. The issue of overlapping will be considered later, which will not add anything conceptually.

Let $\Lambda^{(k)}$ be the image domain covered by the $k$-th activated and deformed hierarchical compositional template $H_{\widetilde{L_k}}^{(t_k)} \in \Delta^{(4)}$ to encode image $\I$. Then the image domain $\Lambda$ of $\I$ can be divided into
\begin{equation}
\begin{aligned}
    \Lambda = \Lambda^{(0)}\, \cup \, [\cup_{k=1}^{K} \Lambda^{(k)}],
\end{aligned}
\end{equation}
where $\Lambda^{(0)}$ refers to the image domain not covered by any templates.


Each activated  template is further divided into part templates, which are also allowed to shift to encode the input image. Let $\Lambda^{(k,v)}$ be the image domain covered by the shifted part template $P^{(t_k,v)}_{dL_{k,v}} \in \Delta^{(2)}$, where $dL_{k,v} = \widetilde{L_k}+L_{v}+\delta L_{k,v}$. Then the image domain $\Lambda^{(k)}$ covered by $H_{\widetilde{L_k}}^{(t_k)}$ is divided into
\begin{equation}
\begin{aligned}
    \Lambda^{(k)} = \cup_{v=1}^{V} \Lambda^{(k,v)}.
\end{aligned}
\end{equation}


Each shifted part template $P^{(t_k,v)}_{dL_{k,v}}$ is further divided into shiftable Gabor wavelets to ground onto image pixels. Let $\Lambda^{(t,v,i)}$ be the image domain covered by the shifted Gabor wavelet $B_{dl_{k,v,i}} \in \Delta^{(0)}$, where $dl_{k,v,i} = dL_{k,v}+l_{t_k,v,i}+\delta l_{k,v,i}$. Then the image domain $ \Lambda^{(k,v)}$ covered by $P^{(t_k,v)}_{dL_{k,v}}$ is divided into
\begin{equation}
\begin{aligned}
    \Lambda^{(k,v)} = \Lambda^{(k,v,0)}\, \cup \, [\cup_{i=1}^{n} \Lambda^{(k,v,i)}],
\end{aligned}
\end{equation}
where $\Lambda^{(k,v,0)}$ refers to the empty pixels inside $\Lambda^{(k,v)}$ not occupied by the Gabor wavelets.

Let $\Lambda_S=\cup_{k,v,i} \Lambda^{(k,v,i)}$ denote the pixels covered by the Gabor wavelets in image $\I$, which correspond to the sketchable image areas, and let $\overline{\Lambda_S}=\{\Lambda^{(0)} \cup [\cup_{k,v} \Lambda^{(k,v,0)}]\}$ denote the pixels not covered by the Gabor wavelets, which correspond to the non-sketchable image areas. The image is divided into two components
\[  \I = (\I(\Lambda_S), \; \I(\overline{\Lambda_S})).
\]

The activation and deformation states of the dictionaries at different layers form the encoding $W = (t_{k}, \widetilde{L}_{k}, \delta L_{k,v}, \delta l_{k,v,i}, \forall k,v,i)$ of image $\I$. Here we define a probability model $p(\I|W)$ over $W$. Due to the tree structure of the hierarchical compositional model and the non-overlapping assumption, $p(\I|W)$ can be factorized as follows by assuming independence between the parts,
\begin{equation}
\begin{aligned}
& p(\I|W) = p(\I(\overline{\Lambda_S}),\I(\Lambda_S)|W) \\
&= p(\I(\overline{\Lambda_S})) p(\I(\Lambda_S) | W) \\
&= p(\I(\overline{\Lambda_S}))\prod_{k,v,i} p \left(\I(\Lambda^{(k,v,i)}) | B_{dl_{k,v,i}} \right).\label{eqn::densityFinal}
\end{aligned}
\end{equation}

Following the active basis model \cite{wu2010learning}, we take a reference model $q(\I)$ for generic natural images, which can be factorized into the product of the patch probabilities $q \left( \I(\Lambda^{(k,v,i)}) \right)$ as well as $q(\I(\overline{\Lambda_S}))$ under independence assumption.

We compute the probability ratio
\begin{equation}
\frac{p(\I|W)}{q(\I)} = \frac{\prod_{k,v,i} p \left(\I(\Lambda^{(k,v,i)}) | B_{dl_{k,v,i}} \right) }{\prod_{k,v,i} q \left( \I(\Lambda^{(k,v,i)}) \right)}.
\label{eqn::pqpt}
\end{equation}
Since $p(\I(\overline{\Lambda_S}))$ uses the same model as $q(\I(\overline{\Lambda_S}))$, it is canceled in the ratio.

As each image patch $\I(\Lambda^{(k,v,i)})$ is still high dimensional, we project it to a one dimensional probability ratio along the  response of basis function $B_{dl_{k,v,i}}$
\[
r_{k,v,i} = \left\| \left<\I(\Lambda^{(k,v,i)}), B_{dl_{k,v,i}} \right> \right\|^2,
\]
and the latter follows a one-dimensional exponential distribution \cite{wu2010learning},
\begin{equation}
\begin{aligned}
& \frac{p \left(\I(\Lambda^{(k,v,i)}) | B_{dl_{k,v,i}} \right) }{q \left(\I(\Lambda^{(k,v,i)}) \right)}
=  \frac{p(r_{k,v,i})}{q(r_{k,v,i})} \\
& = \frac{1}{Z_{t_{k},v,i}} \exp \left\{\lambda_{t_k,v,i} h(r_{k,v,i}) \right\}.
\label{eqn::pqB}
\end{aligned}
\end{equation}
The above model has four aspects.
\begin{itemize}
\item $q(r)$ is a histogram of filter responses pooled over a set of natural images. It has high probabilities near zero and has heavy tail.

\item $h$ is a sigmoid transform that saturates at $\tau$:
\[ h(x)=\tau\left[2/(1+e^{-2x/\tau})-1\right]. \]
It has high response when the patch coincides with an edge/bar feature in the image.

\item $\lambda_{t,v,i}$ reflects the importance of the corresponding Gabor wavelet element in the learned shape template, and should be estimated by maximum likelihood so that the expectation $E_{\lambda_{t,v,i}}[h(r)]$ matches the corresponding observed mean response from covered image patches.

\item $Z_{t,v,i}$ can be computed using numerical integration to normalize the 1D probability
$p(r) = q(r) \frac{1}{Z_{t,v,i}} \exp\{\lambda_{t,v,i} h(r)\}.$
\end{itemize}


Let $\Theta = (\lambda_{t,v,i}, \Delta^{(j)}, \forall t,v,i,j)$ be the parameters for the hierarchical compositional model, the log-likelihood ratio of image $\I$ encoded by $W$ is
\begin{equation}
\begin{aligned}
& l(\I|W, \Theta)= \log \frac{p(\I|W)}{q(\I)}\\
& = \sum_{k=1}^{K}\sum_{v=1}^{V}\sum_{i=1}^{n} \left [ \lambda_{t_k,v,i} h(r_{k,v,i}) -\log Z_{t_k,v,i} \right ].\\
\label{eq::log_ratio}
\end{aligned}
\end{equation}

\begin{figure}
  \centering
    \includegraphics[width=0.45\textwidth]{./image/iteration.pdf}\\
  \caption{Learned hierarchical compositional templates during 10 iterations on 14 input images.}
  \label{Fig:iteration}
\end{figure}

\section{Unsupervised Learning}

In this section, we present the unsupervised learning algorithm for learning a dictionary of the hierarchical templates from a set of unannotated images $\{\I^{(m)}, m=1,\cdots,M\}$. The unsupervised learning algorithm seeks to minimize the total energy function $- \sum_{m=1}^{M}l(\I^{(m)}|W^{(m)}, \Theta)$ over $\{W^{(m)}, \forall m\}$ and $\Theta$. The algorithm iterates the following two steps. (I) Image encoding: Given $\Theta$, infer $W^{(m)}$ for each $\I^{(m)}$. (II) Re-learning: Given $\{W^{(m)}, \forall m\}$, estimate $\Theta$. Examples of the learned templates during iterations are shown in Fig. \ref{Fig:iteration}.

\subsection{Image encoding}

During the image encoding step, we assume the dictionaries of templates and the corresponding parameters are known and fixed. Firstly, we calculate a series of template matching score maps $\mathrm{SUM1}$, $\mathrm{MAX1}$, $\mathrm{SUM2}$, $\mathrm{MAX2}$, $\mathrm{SUM3}$ by a bottom-up template matching sub-process:

\hspace{0cm}
\hrule depth 0.8pt
\textbf{Procedure} Template matching
\hrule
\begin{algorithmic}
\small
     \State \textbf{Up-1} compute the Gabor wavelet matching score $\mathrm{SUM1}$ of $B$ on the image $\I$:
     $$\mathrm{SUM1}(l)=|\langle \I, B_{l}\rangle|^2.$$
     \State \textbf{Up-2} compute $\mathrm{MAX1}$ by local maximization to account for the shifts of Gabor wavelets:
     $$\mathrm{MAX1}(l)=\max_{\delta l}\mathrm{SUM1}(l+\delta l).$$
    \State \textbf{Up-3} for $t=1, ..., T, v=1, ..., V$, compute matching scores $\mathrm{SUM2}_{t,v}$ of  the part template $P^{(t,v)}$ on $\I$:
         $$\begin{aligned}
             \mathrm{SUM2}&_{t,v}(L) =\sum_{i=1}^{n} [ \lambda_{t,v,i}
             h(\mathrm{MAX1}(L+l_{t,v,i})) - \log Z(\lambda_{t,v,i})].
         \end{aligned}$$
     \State \textbf{Up-4} for $t=1, ..., T, v=1, ..., V$, compute $\mathrm{MAX2}_{t,v}$ of $P^{(t,v)}$ by local maximization to account for shifts of part templates:
     $$\mathrm{MAX2}_{t,v}(L)=\max_{\delta L}\mathrm{SUM2}_{t,v}(L+\delta L).$$
     \State  \textbf{Up-5} for $t=1, ..., T$, compute the matching score $\mathrm{SUM3}_{t}$ of the hierarchical compositional template $H^{(t)}$ on $\I$:
     $$\begin{aligned}
         \mathrm{SUM3}&_{t}(\widetilde{L}) = \sum_{v=1}^{V} \mathrm{MAX2}_{t,v}(\widetilde{L}+L_{v}).
     \end{aligned}$$
\end{algorithmic}
\hrule
\hspace{0cm}

Suppose the $k$-th activation of shape templates in the image $\I$ is known to be $H^{(t_{k})}$, then the geometric attributes of $H^{(t_{k})}$ and its part templates $P^{(t_{k},v)}$ can be determined by a top-down template localization sub-process:


\hspace{0cm}
\hrule depth 0.8pt
\textbf{Procedure} Template localization
\hrule
\begin{algorithmic}
\small
     \State \textbf{Down-1} localize the hierarchical compositional template $H^{(t_{k})}$ in the image $\I$:
     $$\widetilde{L}_{k}=\arg\max_{\widetilde{L}}\mathrm{SUM3}_{t_{k}}(\widetilde{L}).$$
     \State \textbf{Down-2} localize the part templates in the image $\I$:
     $$\delta L_{k,v}=\arg\max_{\delta L}\mathrm{SUM2}_{t_{k},v}(\widetilde{L}_k+L_{v}+\delta L), \forall v$$.
\end{algorithmic}
\hrule
\hspace{0cm}


Finally, a template matching pursuit process is performed to sequentially select hierarchical compositional templates to encode $\I$.

\begin{algorithm}[H]
\caption{Template matching pursuit}
\label{alg:Template_matching_pursuit}
\begin{algorithmic}[1]
\small
     \State Initialize the maps of template matching scores $\mathrm{SUM3}_{t}(\widetilde{L})$ for all $(\widetilde{L}, t)$ by the template matching sub-process. Let $k \leftarrow 1$.
     \State Select the next best hierarchical compositional template by finding the global maximum of the maps: $t_{k} = \arg\max_{t} [ \max_{\widetilde{L}} \mathrm{SUM3}_{t}(\widetilde{L}) ]$.
     \State Localize the selected template $H^{(t_{k})}$ in the image $\I$ by the template localization sub-process and get $\{\widetilde{L}_{k}, \delta L_{k,v}\, \forall v \}$.
     \State Let the selected arg-max template inhibit overlapping candidate templates. If the candidate template $H_{\widetilde{L}}^{(t)}$ overlaps with $H_{\widetilde{L}_{k}}^{(t_{k})}$, then set $\mathrm{SUM3}_{t}(\widetilde{L}) \leftarrow -\infty$.
     \State Stop if all $\mathrm{SUM3}_{t}(\widetilde{L}) \le 0$. Otherwise let $k \leftarrow k + 1$, and go to Step 2.
\end{algorithmic}
\end{algorithm}

In practice, it is desirable to allow some limited overlapping between the $K$ hierarchical compositional templates that encode $\I$. If not, some salient patterns of $\I$ may fall through the cracks between the templates. On the other hand, we do not want to allow excessive overlap. Otherwise the learned part templates will be too redundant, and we will need a lot of them to encode different visual patterns. In practice, given a selected template $H_{\widetilde{L}_{k}}^{(t_{k})}$, we set $\mathrm{SUM3}_{t}(\widetilde{L}) \leftarrow -\infty$ if $\|\widetilde{X}-\widetilde{X}_{t_k}\|_2 \le \rho D$, where $D$ is the side length of hierarchial compositional templates, and $\rho D$ is the preset overlapping distance (default setting: $\rho = .4$).

\subsection{Re-learning}


Given current encoding $\{W^{(m)}, \forall m\}$ on images $\{\I^{(m)}, \forall m\}$, we re-learn the hierarchical compositional templates. For each template $H^{(t)}$, we extract the image patches covered by part templates within it. Let $\{\widehat{\I}_{u,t,v}, u=1, ..., U\}$ be the cropped aligned image patches covered by $P^{(t,v)}$, the shared matching pursuit algorithm sequentially selects the Gabor wavelets and estimates the associated parameters. Each iteration seeks the maximal increase of the total log-likelihood. The algorithm is as follows.

\begin{algorithm}[H]
\caption{Shared matching pursuit}
\label{alg:Shared_matching_pursuit}
\begin{algorithmic}[1]
\small
     \State Initialize $i \leftarrow 0$. For $u = 1, ..., U$, initialize the response maps $\widehat{R}_{u,t,v}(l) \leftarrow | \langle \widehat{\I}_{u,t,v}, B_{l}\rangle |^2$ for all $l$.
     \State $i \leftarrow i + 1$. Select the next basis function by finding
        \[
        l_{t,v,i} = \arg\max_{l} \sum_{u=1}^{U} \max_{\delta l} h(\widehat{R}_{u,t,v}(l+\delta l)),
        \]
        where $\max_{\delta l}$ is local maximum pooling within the bounded range of perturbations.
     \State For $u = 1, ..., U$, given $l_{t,v,i}$, infer the perturbations by retrieving the arg-max in the local maximum pooling of Step 2:
        \[
        \delta l_{u,t,v,i} = \arg\max_{\delta l} \widehat{R}_{u,t,v}(l_{t,v,i}+\delta l).
        \]
        Let $dl_{u,t,v,i} = l_{t,v,i}+\delta l_{u,t,v,i}$ and the response $r_{u,t,v,i} \leftarrow \widehat{R}_{u,t,v}(dl_{u,t,v,i})$. Then let the arg-max wavelet inhibit nearby wavelet by setting $\widehat{R}_{u,t,v}(l) \leftarrow 0$ if the correlation $|\langle B_{l}, B_{dl_{u,t,v,i}}\rangle|^2> \epsilon$ (default: $\epsilon = .1$ to enforce the approximate orthogonality of Gabor wavelets).
     \State Compute $\lambda_{t,v,i}$ by solving the maximum likelihood equation
     $
      E_{\lambda_{t,v,i}}[h(r)] = \sum_{u=1}^{U} h(r_{u,t,v,i})/U.
     $
     And derive the corresponding $Z_{t,v,i}$ by solving
     $
     p(r) = q(r) \frac{1}{Z_{t,v,i}} \exp\{\lambda_{t,v,i} h(r)\}.
     $
     \State Stop if $\lambda_{t,v,i} [\sum_{u=1}^{U} h(r_{u,t,v,i})/U] - \log Z_{t,v,i} \le 0$, else go back to Step 2.
\end{algorithmic}
\end{algorithm}



\section{Experiments}

The code and results can be downloaded from \url{http://www.stat.ucla.edu/~jifeng.dai/research/HCM.html}.

\subsection{Image representation}

\begin{figure}
\centering
\subfloat[]{\includegraphics[width=.28\textwidth]{image/experiment_1_1.pdf}}\\
\subfloat[]{\includegraphics[width=.4\textwidth]{image/experiment_1_2.pdf}}\\
\subfloat[]{\includegraphics[width=.4\textwidth]{image/experiment_1_4.pdf}}\\
\caption{Learning hierarchical compositional templates and performing image encoding of: (a) single image with repetitive patterns; (b) images of the same object category (23 input images); (c) images of different object categories (30 input images).}
\label{fig:exp_representation}
\end{figure}

Fig. \ref{fig:exp_representation} shows experimental results of the proposed approach on image representation. Hierarchical compositional templates are learned from single image with repetitive patterns (Fig. \ref{fig:exp_representation} (a)), input images of the same object category (Fig. \ref{fig:exp_representation} (b)), and input images of different categories (Fig. \ref{fig:exp_representation} (c)) respectively. It can be seen that the learned hierarchical compositional templates are quite meaningful.

\subsection{Domain transfer}


\begin{table*}[htdp]
\caption{Classification accuracies on the four domain benchmark.}

\begin{center}

\subfloat[Classification accuracies on single source four domains benchmark ( C: caltech, A: amazon, D: DSLR, W: webcam)]{
\scalebox{0.8}{
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Methods & C $\rightarrow$ A & C $\rightarrow$ D & A $\rightarrow$ C & A $\rightarrow$ W & W $\rightarrow$ C & W $\rightarrow$ A & D $\rightarrow$ A & D $\rightarrow$ W \\
\hline
Metric \cite{saenko2010adapting} & 33.7 $\pm$ 0.8 & 35.0 $\pm$ 1.1 & 27.3 $\pm$ 0.7 & 36.0 $\pm$ 1.0 & 21.7 $\pm$ 0.5 & 32.3 $\pm$ 0.8 & 30.3 $\pm$ 0.8 & 55.6 $\pm$ 0.7 \\
SGF \cite{gopalan2011domain} & 40.2 $\pm$ 0.7 & 36.6 $\pm$ 0.8 & 37.7 $\pm$ 0.5 & 37.9 $\pm$ 0.7 & 29.2 $\pm$ 0.7 & 38.2 $\pm$ 0.6 & 39.2 $\pm$ 0.7 & 69.5 $\pm$ 0.9 \\
GFK \cite{gong2012geodesic} & 46.1 $\pm$ 0.6 & 55.0 $\pm$ 0.9 & 39.6 $\pm$ 0.4 & 56.9 $\pm$ 1.0 & 32.8 $\pm$ 0.1 & 46.2 $\pm$ 0.6 & 46.2 $\pm$ 0.6 & \textbf{80.2 $\pm$ 0.4}\\
FDDL \cite{yang2011fisher} & 39.3 $\pm$ 2.9 & 55.0 $\pm$  2.8 & 24.3 $\pm$ 2.2 & 50.4 $\pm$ 3.5 & 22.9 $\pm$ 2.6 & 41.1 $\pm$ 2.6 & 36.7 $\pm$ 2.5 & 65.9 $\pm$ 4.9 \\
Landmark \cite{gong2013C} & 56.7 & 57.3 & 45.5 & 46.1 & 35.4 & 40.2 & - & -\\
MMDT \cite{hoffman2013efficient} & 49.4 $\pm$ 0.8 & 56.5 $\pm$  0.9 & 36.4 $\pm$ 0.8 & 64.6 $\pm$ 1.2 & 32.2 $\pm$ 0.8 & 47.7 $\pm$ 0.9 & 46.9 $\pm$ 1.0 & 74.1 $\pm$ 0.8 \\
SDDL \cite{shekhar2013generalized} & 49.5 $\pm$ 2.6 & \textbf{ 76.7 $\pm$ 3.9} & 27.4 $\pm$ 2.4 & \textbf{72.0 $\pm$ 4.8} & 29.7 $\pm$ 1.9 & 49.4 $\pm$ 2.1 & 48.9 $\pm$ 3.8 & 72.6 $\pm$ 2.1 \\
Our method & \textbf{ 68.3 $\pm$ 2.3 }& 57.4 $\pm$ 6.0 & \textbf{52.7 $\pm$ 3.0} & { 54.8 $\pm$ 2.8} & \textbf{42.2 $\pm$ 3.1} & \textbf{57.1 $\pm$ 3.5} & \textbf{60.1 $\pm$ 3.2 } & 79.7 $\pm$ 2.5 \\
\hline

\end{tabular}
}
}



\subfloat[Classification accuracies on multiple sources three domains benchmark ]{
\scalebox{0.8}{
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Source & Target &SGF \cite{gopalan2011domain} & RDALR \cite{jhuo2012robust} & FDDL \cite{yang2011fisher} & SDDL \cite{shekhar2013generalized} & Our method \\
\hline
DSLR, amazon   & webcam & 52 $\pm$ 2.5 & 36.9 $\pm$ 1.1 & 41.0 $\pm$ 2.4 & \textbf{57.8 $\pm$ 2.4} &\textbf{57.8 $\pm$ 2.4} \\
amazon, webcam & DSLR   & 39 $\pm$ 1.1 & 31.2 $\pm$ 1.3 & 38.4 $\pm$ 3.4 & 56.7 $\pm$ 2.3 &\textbf{60.6 $\pm$ 2.3} \\
webcam, DSLR   & amazon & 28 $\pm$ 0.8 & 20.9 $\pm$ 0.9 & 19.0 $\pm$ 1.2 & 24.1 $\pm$ 1.6 &\textbf{34.6 $\pm$ 1.4} \\
\hline
\end{tabular}
}
}
\end{center}
\label{table::transfer}
\end{table*}

We also test the proposed approach for the task of domain transfer on the four domain dataset. The original dataset \cite{saenko2010adapting} contains 31 object categories where for each category, images are captured using high quality DSLR cameras, low quality webcams, and also collected from amazon.com.  Using commonly used image descriptors, these images are considered as from different domains as classifiers trained from one domain will perform poorly on other domains. More recently, researchers further combine this dataset with the Caltech 256 dataset, making it a four domain dataset. We use the evaluation protocol in \cite{gong2012geodesic} to randomly select the training data from specific training and testing domains, and learn a dictionary of 3 templates for each of the object category to construct a codebook. The templates as well as their parts in the codebook are then fed to the spatial pyramid matching method \cite{lazebnik2006beyond}, which equally partition an image into 1,4, and 16 regions, and concatenates the maximum template and part matching scores at different image regions into a feature vector. We use this feature vector and the multi-class SVM to build image classifiers, and apply these classifiers in testing domains to evaluate the classification accuracy. Table \ref{table::transfer} shows the classification results of the proposed approach and several recent approaches \cite{saenko2010adapting,gopalan2011domain,gong2012geodesic,yang2011fisher,gong2013C,hoffman2013efficient,shekhar2013generalized}. It can be seen that our method performs better than the other methods on 8 out of 11 sub tasks. Note that this accuracy is achieved using the learned hierarchical compositional templates by itself without integrating additional features. This experiment suggests that object representations learned using our method can be transferred to different domains efficiently.


\subsection{Cosegmentation}

\begin{table}
    \caption{Correctly labeled pixel ratios on the ImageNet dataset.}
    \centering
    \scalebox{0.8}{
    \begin{tabular}{|p{1.5cm}|p{1.0cm} | p{1.0cm} | p{1.0cm}| p{1.0cm}|}
    \hline
    & Ours & \cite{kuettel2012segmentation} & \cite{dai2013cosegmentation} & \cite{rother2004grabcut}\\
    \hline
    Average & \textbf{79.0} & 77.1 & 76.9 & 71.0\\
    \hline
    \end{tabular}}
    \label{Tab:ImageNet_accuracy}
\end{table}

\begin{figure*}
\centering
\includegraphics[width=.9\textwidth]{image/experimental_result_ImageNet.pdf}
\caption{Examples of image encoding and cosegmentation by the hierarchical compositional templates on ImageNet.}
\label{fig:exp_cosegmentation}
\end{figure*}

In addition, we follow  \cite{dai2013cosegmentation} and test the proposed approach for cosegmentation on the ImageNet dataset \cite{deng2009imagenet}. ImageNet is a challenging large-scale dataset of object classes. The original ImageNet dataset does not have ground-truth annotations of segmentation. In \cite{kuettel2012segmentation}, a subset of ImageNet is labeled with ground-truth segmentations. The test set contains $10$ random images from each of $446$ classes, for a total of $4460$ images. It is very challenging due to limited training examples per class, huge visual variability and cluttered backgrounds. In \cite{kuettel2012segmentation}, 60k images annotated with bounding boxes, 440k images with class labels and the semantic structure of class labels in ImageNet are utilized to provide strong supervision for segmentation propagation.

We perform cosegmentation on the full test set without any additional supervision. 3 templates are learned on the images of each class, which help to align objects in different images as in \cite{dai2013cosegmentation}. In this way, the learned hierarchical compositional templates provide vital top-down information for cosegmentation. Segmentation accuracy is measured by the correctly labeled pixel ratio, following the criterion in \cite{kuettel2012segmentation}. As shown in Table \ref{Tab:ImageNet_accuracy}, our approach delivers the state of the art average accuracy of 79.0\%, which is 1.9\%, 2.1\%, and 8.0\% higher than the supervised segmentation propagation algorithm in \cite{kuettel2012segmentation}, the cosegmentation and cosketch approach in \cite{dai2013cosegmentation} and the Grabcut \cite{rother2004grabcut} baseline respectively. Note that the previous state of the art result in \cite{kuettel2012segmentation} is achieved with the help of abundant supervision, whereas our approach outperforms it without any additional supervision. Some image encoding and cosegmentation examples of the proposed approach are shown in Fig. \ref{fig:exp_cosegmentation}.

\section{Conclusion}

We propose an unsupervised approach for learning hierarchical compositional templates as representational units for natural images.  Experimental results show that  the proposed approach is capable of learning meaningful representational units, which are useful for various vision tasks.\\

\noindent{\textbf{Acknowledgments}. The work is supported by NSF DMS 1310391, ONR MURI N00014-10-1-0933, DARPA MSEE FA8650-11-1-7149.}

{\small
\bibliographystyle{ieee}
\bibliography{egbib}
}

\end{document}
