\newif\ifsolution
\newif\ifgrading

\newenvironment{CourseTitle}[1]{
\huge CS 231A Computer Vision (Fall 2011)\\Problem Set #1
\ifgrading
\ \\ \ \\ \large\bf Master Set
\else
    \ifsolution
    \ \\ \ \\ \large\bf Solution Set
    \fi
\fi
}

\solutiontrue
%\solutionfalse
\gradingtrue
%\gradingfalse

\documentclass[11pt]{article}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{.125in}
\setlength{\textwidth}{6.25in}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{subfig}
\usepackage{graphicx}

\usepackage{algorithmic}
\usepackage{algorithm}
\newcommand{\argmax}{\operatornamewithlimits{arg \ max}}
\newcommand{\argmin}{\operatornamewithlimits{arg \ min}}
\newcommand{\maximize}{\operatornamewithlimits{maximize}}
\newcommand{\minimize}{\operatornamewithlimits{minimize}}
\newcommand{\tab}{\hspace*{2em}}
\begin{document}

\title{\CourseTitle{4}}
\date{\LARGE Due: Nov. $30^{\text{th}}$, 2011 (9:30am)}
\maketitle


\section{Part-based models for Object Recognition (50 points)}

	One approach to object recognition is to use a deformable part-based model. Unlike global features (e.g. bag of
words), a part-based model encodes relative spatial locations of different parts of an object, as shown in
Fig.~\ref{fig:parts}(a). The deformable nature of the model allows for relative spatial movement between the parts.
Given a test image, the algorithm will find the best match for each part in the image while also considering the cost of
deforming the relations between the parts.  In this problem you will explore how to pose this problem in a statistical
framework. Further, given a set of training images, you will show how the model $\theta$ can be learned.

	\begin{figure}[h!]
		\centering
		\includegraphics[width=5in]{part_models.pdf} \
		\caption{\textbf{(a)} An illustration of the parameters of an example deformable part-based model. Note that there
is a connection parameter $c_{ij}$ corresponding to each edge $e_{ij}$, and an appearance parameter $u_i$ corresponding
to each vertex $v_i$. \\\textbf{(b)} Three training images showing the part locations and the last image depicting the
learned structure model.}
		\label{fig:parts}
	\end{figure}
	
	A pictorial structure model is a type of part-based model where an object is given by a collection of parts with
connections between certain pairs of parts. A pictorial structure model is a graph structure with vertices $V=\{v_1,
\ldots, v_n\}$ corresponding to the $n$ parts in the model. It is parameterized by $\theta = \{u, E,c\}$ where $u=\{u_1,
\ldots, u_n\}$ are appearance parameters (such as patches), $E = \{e_{ij}\}$ is the set of edges indicating whether
parts are connected, and $c =\{c _{ij} \mid (v_i,v_j) \in E\}$ are connection parameters. Each part $v_i$ has its own
appearance parameter $u_i$ (the specifics of this parameter are not needed to solve this problem).  For a given image,
we would like to find the object configuration $L=(l_1, \ldots, l_n)$, where each $l_i$ specifies the location of part
$v_i$.

In this problem, we specifically find $p(L \mid I, \theta)$ which denotes the probability of an object configuration
given an image $I$, and a model $\theta$.  Using Bayes Rule we have $ p( L \mid I, \theta) \propto p( I \mid L, \theta)
p(L \mid \theta) $ where $p(I \mid L, \theta)$ defines the likelihood of seeing a particular image given that an object
is at some location, and $p(L \mid \theta)$ is the likelihood that an object is at a particular location.

To get some intuition of this model let's consider scanning this model over an image. Given a learned model $\theta$,
there are two components to evaluate for our model configuration corresponding to each of the probability terms above
(from Bayes Rule).  First, for each part $i$,  we compare our appearance parameter $u_i$ to the image $I$ and get a
measure for how likely the location of the corresponding part is.  Second, given a model $\theta$ we can calculate the
likelihood of a object configuration $L$. An intuitive way to think of how $c_{ij}$ describes the relation between two
parts is to think of the connections between the parts as springs and $c_{ij}$ as the measure of stiffness of those
springs. Although we do not know the location of each part given an image we have a general idea of how the object
locations will appear relative to each other, and we have a way of measuring how likely a given part is to appear at
each location using $u$.
		
\begin{itemize}
	
	\item[(a)]  Write $p(I \mid L ,\theta)$ as a function of $I, u_i, E, c_{ij}$ and $l_i$. Assume that the parts do not
overlap. \\\emph{Hint: What information is not needed to evaluate the likelihood of an image given a part configuration,
and the model?}
	
	\item[(b)] For this part $p(L \mid \theta)$ has the form \[ p(L \mid \theta) = \frac{\prod_{(v_i,v_j) \in E}
p(l_i,l_j \mid \theta) }{\prod_{v_i \in V} p(l_i \mid \theta)^{\text{deg } v_i -1} }\] where deg $v_i$ is the degree of
vertex $v_i$ in the graph defined by $E$.  Also $l_i$ denotes the location of part $i$. In addition, assume that there
is no information associated with the absolute location of an individual part.

Represent $p(L \mid \theta)$ in terms of $I, u_i, E, c_{ij}$ and $l_i$. Use the expression for $p(L \mid \theta)$ and
the assumption given above.

	\item[(c)] In the previous parts of this problem we have assumed that our model $\theta$ is known. In this part you will derive how we learn this model given training images.  Specifically use the maximum likelihood (ML) estimation to find the model $\theta^* =(u^*,E^*,c^*)$.
	\begin{itemize}
		\item[(i)] Write down the ML estimate for $\theta^*$.

Assume that you are given $m$ i.i.d. (independent and identically distributed) training images. Use the expressions you found in parts (a) and (b) to simplify your answer.

Note that we do not expect you to find a closed form solution for $\theta^*$. You only have to pose the optimization problem whose solution is $\theta^*$.  If it helps you to understand the problem you can assume that the distributions are all Gaussian.
		
		\item[(ii)] Show that our estimate for $\theta^*$ can be found by solving two separate maximization problems.  Show how to find our estimates for $u_i^*$,$E^*$, $c_{ij}^*$ from these problems.  Again, in this problem you do not need to provide a closed form solution, you only need to set up the optimization problems.  \\
		
% 		\item[(iii)] \textbf{Extra Credit (1\%)}: Give a method for finding $E^*$ and $c^*$ in accordance with the ML
% estimate of $\theta^*$ separately.  First assume that $E$ is a fully connected graph, using this find an estimate for
% $c_{ij}^*$.  Using these values for your $c_{ij}^*$'s find an estimate for $E^*$. \emph{Hint: Pose} $E^*$ \emph{as a
% common graph problem. }

	\end{itemize}
	
	\item[(d)] A question that you should always be asking yourself when you see a new recognition algorithm is what the
method is invariant to, and how it accomplishes these invariances. Specifically, is the method developed in this
problem invariant to scale, intensity, affine transformation and/or rotation? Provide justification for your answers in
a few sentences.
 		
\end{itemize}
\
\ifsolution
\large
\\\textbf{Solution:}\\
\normalsize
\begin{itemize}

	\item[(a)]  Assuming that our parts do not overlap it is we can write \[ p(I \mid L, \theta) = p(I \mid L, u) = \displaystyle\prod_{i=1}^n p(I \mid l_i,u_i) \] where the first equality holds from the observation that no information is gained from either $E$ or $c$ because we already know the location of our object.
	
	\item[(b)] Since we do not assign any value to the information of an absolute part location we have $p(l_i \mid \theta) = 1$ using this we write \[p(L \mid \theta) \ = \displaystyle
	\prod_{(v_i,v_j) \in E} p(l_i,l_j \mid \theta) \  =  \displaystyle\prod_{(v_i,v_j) \in E} p(l_i,l_j \mid c_{ij} )\] where the last equality holds because the appearance $u$ adds no information here and the information from $E$ is already captured in the product condition.

	\item[(c)]
		\begin{itemize}
		
			\item[(i)]  First we need to write down the ML estimate for $\theta^*$ given $m$ training images which is \[ \theta^* = \argmax_{\theta} \displaystyle\prod_{k=1}^m p(I^k \mid L^k, \theta)p(L^k \mid \theta)  \]
			\item[(ii)] The ML estimate can be broken into two separate for $u$ and one for $E,$ and $c$. First lets consider finding the estimate for $u$.  Our estimate for $u$ can be found by using $p(I \mid L,u)$ because this is the only term which $u$ appears. Simplifying we can find each $u_i$ due to \[ p(I \mid L, u) =  \displaystyle\prod_{i=1}^n p(I \mid l_i,u_i) \]   thus our ML estimate is given by\[ u_i^* = \argmax_{u_i}  \displaystyle\prod_{k=1}^n p(I^k \mid l_i^k,u_i) \]
			
			Now considering the second problem is the following maximization problem \[c^* , E^* = \argmax_{E,c}
\displaystyle\prod_{(v_i,v_j) \in E} p(l_i,l_j \mid c_{ij} )\]
		
% 			\emph{Extra Credit} For this part we see that $E$ and $C$ only appear in the $p(L \mid \theta)$ term.  However
% they appear there together and we would like to estimate them separately.  If we notice that $E^*$ depends on $c^*$
% but $c^*$ does not depend on $E^*$ we can estimate $c^*$ first.  We see that our estimate $c^*$ can be decomposed into
% estimate for $c_{ij}^*$ and is given by \[  c_{ij}^* = \argmax_{c_{ij}} \displaystyle\prod_{k=1}^m p(l_i^k,l_j^k \mid
% c_{ij}) \] Now we consider estimating $E^*$.  Remembering that the $c_{ij} $ indicate how strong the connection
% between parts and that $E$ defines a graph, we follow the hint and will use a function of $c_{ij}$ to define weights
% of a graph and then find the minimal spanning tree.  Currently though our problem is \[ E^* =   \argmax_E
% \displaystyle\prod_{(v_i,v_j) \in E} \ \displaystyle\prod_{k=1}^m p(l_i^k,l_j^k \mid c_{ij}^*)   \] using logarithms
% we can rewrite this as
% 			\begin{align*}
% 			   E^* &=   \argmax_E  \displaystyle\sum_{(v_i,v_j) \in E} \ \displaystyle\sum_{k=1}^m \log \left [
% p(l_i^k,l_j^k \mid c_{ij}^*) \right ] \\
% 			   &= \argmin_E  \displaystyle\sum_{(v_i,v_j) \in E} \ \displaystyle\sum_{k=1}^m -\log \left [ p(l_i^k,l_j^k
% \mid c_{ij}^*) \right ]
% 			 \end{align*}
% 			  as a note this will yield the same maximum $E$ because log is monotonically increasing.  Now we can apply an
% algorithm to find the minimal spanning tree to find $E^*$.
			
		
		\end{itemize}
		
		\item[(d)]  Since the way we compare appearance it not given in precise detail, we do not know whether our method
is invariant to intensity (it is safe to assume that it is though).  Since we are using only the relative locations of
the part models we are invariant to rotation.  We are slightly invariant to affine transformations as long as they
aren't too large, resulting in significant occlusion of part (say a profile view of a human body), again because our
model can adjust for deformations.  The same reasoning applies to minor occlusions.
		
		%To extend this framework to capture multiple instances of the same object we could look at the second most likely configuration, and check if it is above a certain threshold.  This is a basic attempt at recognizing multiple instances of the same object.

\end{itemize}
\fi
\ifgrading
\
\large
\\\textbf{Grading Guideline:}\\ \ \\
\normalsize
Total (50 points)\\
(a) (10 points)\\
\tab(5 points) CORRECT FORMULA\\
\tab(5 points) CORRECT EXPLANATION\\
(b) (10 points)\\
\tab(5 points) CORRECT FORMULA\\
\tab(5 points) CORRECT EXPLANATION\\
(c) (25 points)\\
\tab(i) (5 points)\\
\tab\tab(5 points) CORRECT FORMULA\\
\tab(ii) (20 points)\\
\tab\tab(5 points) CORRECT FORMULA for u ML estimate\\
\tab\tab(5 points) CORRECT DERIVATION for u ML estimate\\
\tab\tab(5 points) CORRECT FORMULA for c,E ML estimate\\
\tab\tab(5 points) CORRECT DERIVATION for c,E ML estimate\\
% \tab(c)(iii) (1 extra credit)\\
(d) (5 points)\\
\tab -1 for each: INCORRECT scale; intensity; affine transformation; rotation;\\
\fi

\section{Scene Classification and Matching Using ObjectBank (50 points)}

\begin{figure}[b!]
	\centering
	\includegraphics[width=6in]{oboverview.png} \
	\caption{Diagram of computation pipeline for ObjectBank representation of an image. }
	\label{fig:sail}
\end{figure}	

	In this problem you will experiment with a low-level (based on local image features) and high-level (based on object relevance) approach to scene classification. Furthermore, you will explore the use of different feature vectors with a linear kernel support vector machine (SVM) in order to improve classification performance.  The scene classification will be performed on a given subset of the UIUC Sports data-set.  The dataset along with all other materials for this problem can be downloaded from the course web page (\verb!PS4_data.zip!).
	
	One of the most exciting branches of modern Computer Vision research is the description of the entire scene depicted in an image. While there are many available solutions to object detection and image description, a conclusive approach to describe the semantic contents of a natural scene has not yet emerged. However, ObjectBank~\cite{LiSuLimFeiFei, LiSuXingFeiFei} is a new technology that has demonstrated very good results with a relatively simple approach.
	
	ObjectBank (OB) is similar to an array of filters in traditional signal processing insofar that it is an array of object detectors applied to one image. However, instead of outputting a simple measure of the signal inside a frequency band, the output of an object detector is a 3-dimensional response map which quantifies the presence of an object as a function of resolution and (x,y)-coordinates. These response maps can be concatenated to create an overall description of a scene in terms of the presence of objects. For example, Fig.~\ref{fig:sail} shows some sample responses from a test image of sailboats. The``Sailboat" filter has several large responses that correlate to the location of the actual boats, the``Water" filter has a uniformly large response, and the``Bear" filter demonstrates effectively zero signal. These object detector results can be concatenated into a cohesive Feature Vector for the image, which can then be fed into an SVM or other classification technique.
	
\begin{algorithm}[t!]                      % enter the algorithm environment
\caption{Create ObjectBank Feature Vector}          % give the algorithm a caption
\label{alg1}                           % and a label for \ref{} commands later in the document
\begin{algorithmic}                    % enter the algorithmic environment
\STATE $FeatureVector \Leftarrow []$
\FOR {detector $d$ in DetectorSet}
\STATE $ResponseMap \Leftarrow Detect(d,image)$
\STATE $SPMPoints \Leftarrow Compress(ResponseMap)$
\STATE $FeatureVector.Append(SPMPoints)$
\ENDFOR
\end{algorithmic}
\end{algorithm}


\begin{figure}[b!]
\vspace{-5mm}
	\centering
	\includegraphics[width=3.5in]{SPM.png} \
	\caption{Overview of the Spatial Pyramid Kernel in which histograms of interest point (denoted by the three markers) are created for each subdivision in a 2-level pyramid. The method used in ObjectBank is very similar, except it only extracts the local max inside each subdivision. }
\label{fig:spm}
\end{figure}	


	One of the complications of this technique is the need for data compression or reduction. Each object detector yields an output of roughly 12,000 datapoints, and with 177 objects currently in the ObjectBank, the feature vector (dimension = $12000*177\approx 2.1 mil$) would be high dimensional and unlikely to work in a standard machine learning technique due to overfitting, etc. The current solution for this problem is to continually subdivide the image and extract the maximum value in each subdivision in a modification of the Spatial Pyramid Matching (SPM)~\cite{lazebnik06} technique as shown in Fig.~\ref{fig:spm}.
	
	For the purposes of this assignment, we will ``black box" the detection portion of the system. \emph{If you are curious to learn more, please refer to the following papers: ~\cite{Felz08, LiSuLimFeiFei, LiSuXingFeiFei} (not required for this assignment)}

\textbf{Note: You need to print \& submit your code for all parts of this problem to receive full credit as the final results have already been provided in the starter code. You do not need to submit any files that were not modified by you.}

\begin{itemize}


	\item[(a)] Before exploring the object-based approach of ObjectBank, you will experiment with the low-level bag of words (BoW) representation. That is, you will create a feature vector using the BoW approach discussed in class and train a linear SVM to classify  scenes.

We have provided you with a pre-trained code-book to form the feature vector. Assign each SIFT descriptor to its nearest code-book entry using $L_2$ distance and aggregate the results in a histogram to form the BoW feature. Use the Liblinear SVM package (same as PS0) to train and test your classifier on the given subset of the UIUC Sports data-set.  To compare your classification accuracy to the one we obtained, run the \verb!Problem2a.m! script.
	
	\item[(b)]  Using your result in part (a) as a benchmark, we will implement ObjectBank in several steps. We have given you the response maps corresponding to the data-set in the folder  \verb!response_maps!.  To speed up the processing of the data, we will be using only 50 of the 177 objects for this assignment.
	
	\begin{itemize}

		\item[(i)]  To motivate the switch from BoW to OB use a 0-level SPM to create your feature vector (i.e. select the max of each response map and add it to the feature vector). Train a linear SVM and compare the classification accuracy to the one we obtain for this part, and the result that you obtained for part (a). The code and specific instructions for this part of the assignment are in \verb!Problem2bi.m!.

		\item[(ii)]  Now use a 2-level SPM to form the feature vector form the given response maps.  Train a linear SVM and compare your performance results to the given benchmark. The code and specific instructions for this part of the assignment are in \verb!Problem2bii.m!.
		
	\end{itemize}

\begin{figure}[b!]
	\centering
	\subfloat[]{\includegraphics[height=1.2in]{football.jpeg}} \
	\subfloat[]{\includegraphics[height=1.2in]{volleyball.jpeg}} \
\vspace{-3mm}
	\caption{Sample Test Images}
	\label{fig:coke}
\end{figure}

	\item[(c)]  Assume that you are given a single image (without a label) and asked to find the ``most similar" image from your dataset (also without labels). How would you approach this problem? Describe and implement a method \textbf{using the OB response maps} to generate features for the purpose of selecting the closest semantic match to the given image. Essentially, we would like to build a Google for images without using textual input.
	
This problem is intended to be more open-ended and provide a lot of room for creativity. To begin with, be clear on the type of similarity you are trying to achieve. Some possible definitions are pixel-by-pixel accuracy, OB feature correspondence, or local image-patch matching. Once you have a sense of your metric, you could try several approaches that we have discussed in the course: clustering, norm of differences, 1-vs-all SVMs, correlation, etc.. To get full credit for this problem, please write a clear description of your methodology and an explanation of trade-offs compared to other methods to demonstrate your understanding of the material.

The sample data that you are given in this problem is a mix of data with clear ground truths (i.e., a picture of people playing badminton should match with another picture of people playing badminton) and intentionally poor matches. It is interesting to note what matches you get and to share insights into why the results make sense to you. Please submit your code, a description of your method, and a printout of image match results displayed by \verb!Problem2c.m!.
	
\end{itemize}

\ifgrading
\
\large
\\\textbf{Grading Guideline:}\\ \ \\
\normalsize
Total (50 points)\\
(a) (10 points)\\
\tab(7 points) CORRECT CompileBoW.m\\
\tab(3 points) CORRECT Problem2a.m\\
(b) (20 points)\\
\tab(15 points) CORRECT MaxGetSpatialPyramid.m\\
\tab(5 points) CORRECT Problem2bi.m Problem2bii.m\\
(c) (20 points)\\
\tab(9 points) REASONABLE approach\\
\tab(7 points) REASONABLE result\\
\tab(3 points) REASONABLE explanation\\
\tab(1 points) documentation\\
\fi

\bibliographystyle{plain}
\bibliography{Problem-Set-4-solutions}

\end{document} 