Basic generative model

Weber & Welling here introduce the concept of foreground and background. Foreground parts correspond to an instance of a target object class, whereas background parts correspond to background clutter or false detections.

Let T be the number of different types of parts. The positions of all parts extracted from an image can then be represented in the following "matrix,"

${\displaystyle X^{o}={\begin{pmatrix}x_{11},x_{12},{\cdots },x_{1N_{1}}\\x_{21},x_{22},{\cdots },x_{2N_{2}}\\\vdots \\x_{T1},x_{T2},{\cdots },x_{TN_{T}}\end{pmatrix}}}$

where ${\displaystyle N_{i}\,}$ represents the number of parts of type ${\displaystyle i\in \{1,\dots ,T\}}$ observed in the image. The superscript o indicates that these positions are observable, as opposed to missing. The positions of unobserved object parts can be represented by the vector ${\displaystyle x^{m}\,}$. Suppose that the object will be composed of ${\displaystyle F\,}$ distinct foreground parts. For notational simplicity, we assume here that ${\displaystyle F=T\,}$, though the model can be generalized to ${\displaystyle F>T\,}$. A hypothesis ${\displaystyle h\,}$ is then defined as a set of indices, with ${\displaystyle h_{i}=j\,}$, indicating that point ${\displaystyle x_{ij}\,}$ is a foreground point in ${\displaystyle X^{o}\,}$. The generative probabilistic model is defined through the joint probability density ${\displaystyle p(X^{o},x^{m},h)\,}$.

Model details

The rest of this section summarizes the details of Weber & Welling's model for a single component model. The formulas for multiple component models^[8] are extensions of those described here.

To parametrize the joint probability density, Weber & Welling introduce the auxiliary variables ${\displaystyle b\,}$ and ${\displaystyle n\,}$, where ${\displaystyle b\,}$ is a binary vector encoding the presence/absence of parts in detection (${\displaystyle b_{i}=1\,}$ if ${\displaystyle h_{i}>0\,}$, otherwise ${\displaystyle b_{i}=0\,}$), and ${\displaystyle n\,}$ is a vector where ${\displaystyle n_{i}\,}$ denotes the number of background candidates included in the ${\displaystyle i^{th}}$ row of ${\displaystyle X^{o}\,}$. Since ${\displaystyle b\,}$ and ${\displaystyle n\,}$ are completely determined by ${\displaystyle h\,}$ and the size of ${\displaystyle X^{o}\,}$, we have ${\displaystyle p(X^{o},x^{m},h)=p(X^{o},x^{m},h,n,b)\,}$. By decomposition,

${\displaystyle p(X^{o},x^{m},h,n,b)=p(X^{o},x^{m}|h,n,b)p(h|n,b)p(n)p(b)\,}$

The probability density over the number of background detections can be modeled by a Poisson distribution,

${\displaystyle p(n)=\prod _{i=1}^{T}{\frac {1}{n_{i}!}}(M_{i})^{n_{i}}e^{-M_{i}}}$

where ${\displaystyle M_{i}\,}$ is the average number of background detections of type ${\displaystyle i\,}$ per image.

Depending on the number of parts ${\displaystyle F\,}$, the probability ${\displaystyle p(b)\,}$ can be modeled either as an explicit table of length ${\displaystyle 2^{F}\,}$, or, if ${\displaystyle F\,}$ is large, as ${\displaystyle F\,}$ independent probabilities, each governing the presence of an individual part.

The density ${\displaystyle p(h|n,b)\,}$ is modeled by

${\displaystyle p(h|n,b)={\begin{cases}{\frac {1}{\textstyle \prod _{f=1}^{F}N_{f}^{b_{f}}}},&{\mbox{if }}h\in H(b,n)\\0,&{\mbox{for other }}h\end{cases}}}$

where ${\displaystyle H(b,n)\,}$ denotes the set of all hypotheses consistent with ${\displaystyle b\,}$ and ${\displaystyle n\,}$, and ${\displaystyle N_{f}\,}$ denotes the total number of detections of parts of type ${\displaystyle f\,}$. This expresses the fact that all consistent hypotheses, of which there are ${\displaystyle \textstyle \prod _{f=1}^{F}N_{f}^{b_{f}}}$, are equally likely in the absence of information on part locations.

And finally,

${\displaystyle p(X^{o},x^{m}|h,n)=p_{fg}(z)p_{bg}(x_{bg})\,}$

where ${\displaystyle z=(x^{o}x^{m})\,}$ are the coordinates of all foreground detections, observed and missing, and ${\displaystyle x_{bg}\,}$ represents the coordinates of the background detections. Note that foreground detections are assumed to be independent of the background. ${\displaystyle p_{fg}(z)\,}$ is modeled as a joint Gaussian with mean ${\displaystyle \mu \,}$ and covariance ${\displaystyle \Sigma \,}$.

Classification

The ultimate objective of this model is to classify images into classes "object present" (class ${\displaystyle C_{1}\,}$) and "object absent" (class ${\displaystyle C_{0}\,}$) given the observation ${\displaystyle X^{o}\,}$. To accomplish this, Weber & Welling run part detectors from the learning step exhaustively over the image, examining different combinations of detections. If occlusion is considered, then combinations with missing detections are also permitted. The goal is then to select the class with maximum a posteriori probability, by considering the ratio

${\displaystyle {\frac {p(C_{1}|X^{o})}{p(C_{0}|X^{o})}}\propto {\frac {\sum _{h}p(X^{o},h|C_{1})}{p(X^{o},h_{0}|C_{0})}}}$

where ${\displaystyle h_{0}\,}$ denotes the null hypothesis, which explains all parts as background noise. In the numerator, the sum includes all hypotheses, including the null hypothesis, whereas in the denominator, the only hypothesis consistent with the absence of an object is the null hypothesis. In practice, some threshold can be defined such that, if the ratio exceeds that threshold, we then consider an instance of an object to be detected.

Model learning

After the preliminary step of interest point detection, feature generation and clustering, we have a large set of candidate parts over the training images. To learn the model, Weber & Welling first perform a greedy search over possible model configurations, or equivalently, over potential subsets of the candidate parts. This is done in an iterative fashion, starting with random selection. At subsequent iterations, parts in the model are randomly substituted, the model parameters are estimated, and the performance is assessed. The process is complete when further model performance improvements are no longer possible.

At each iteration, the model parameters

${\displaystyle \Theta =\{\mu ,\Sigma ,p(b),M\}\,}$

are estimated using expectation maximization. ${\displaystyle \mu \,}$ and ${\displaystyle \Sigma \,}$, we recall, are the mean and covariance of the joint Gaussian ${\displaystyle p_{fg}(z)\,}$, ${\displaystyle p(b)\,}$ is the probability distribution governing the binary presence/absence of parts, and ${\displaystyle M\,}$ is the mean number of background detections over part types.

M-step

EM proceeds by maximizing the likelihood of the observed data,

${\displaystyle L(X^{o}|\Theta )=\sum _{i=1}^{I}\log \sum _{h_{i}}\int p(X_{i}^{o},x_{i}^{m},h_{i}|\Theta )dx_{i}^{m}}$

with respect to the model parameters ${\displaystyle \Theta \,}$. Since this is difficult to achieve analytically, EM iteratively maximizes a sequence of cost functions,

${\displaystyle Q({\tilde {\Theta }}|\Theta )=\sum _{i=1}^{I}E[\log p(X_{i}^{o},x_{i}^{m},h_{i}|{\tilde {\Theta }})]}$

Taking the derivative of this with respect to the parameters and equating to zero produces the update rules:

${\displaystyle {\tilde {\mu }}={\frac {1}{I}}\sum _{i=1}^{I}E[z_{i}]}$

${\displaystyle {\tilde {\Sigma }}={\frac {1}{I}}\sum _{i=1}^{I}E[z_{i}z_{i}^{T}]-{\tilde {\mu }}{\tilde {\mu }}^{T}}$

${\displaystyle {\tilde {p}}({\bar {b}})={\frac {1}{I}}\sum _{i=1}^{I}E[\delta _{b,{\bar {b}}}]}$

${\displaystyle {\tilde {M}}={\frac {1}{I}}\sum _{i=1}^{I}E[n_{i}]}$

E-step

The update rules in the M-step are expressed in terms of sufficient statistics, ${\displaystyle E[z]\,}$, ${\displaystyle E[zz^{T}]\,}$, ${\displaystyle E[\delta _{b,{\bar {b}}}]\,}$ and ${\displaystyle E[n]\,}$, which are calculated in the E-step by considering the posterior density:

${\displaystyle p(h_{i},x_{i}^{m}|X_{i}^{o},\Theta )={\frac {p(h_{i},x_{i}^{m},X_{i}^{o}|\Theta )}{\textstyle \sum _{h_{i}\in H_{b}}\int p(h_{i},x_{i}^{m},X_{i}^{o}|\Theta )dx_{i}^{m}}}}$

Feature representation

Whereas the preliminary step in the Weber et al. method is to search for the locations of interest points, Fergus et al. use the detector of Kadir and Brady^[12] to find salient regions in the image over both location (center) and scale (radius). Thus, in addition to location information ${\displaystyle X\,}$ this method also extracts associated scale information ${\displaystyle S\,}$. Fergus et al. then normalize the squares bounding these circular regions to 11 x 11 pixel patches, or equivalently, 121-dimensional vectors in the appearance space. These are then reduced to 10-15 dimensions by principal component analysis, giving the appearance information ${\displaystyle A\,}$.

Model structure

Given a particular object class model with parameters ${\displaystyle \Theta \,}$, we must decide whether or not a new image contains an instance of that class. This is accomplished by making a Bayesian decision,

${\displaystyle R={\frac {p({\mbox{Object}}|X,S,A)}{p({\mbox{No object}}|X,S,A)}}}$

${\displaystyle ={\frac {p(X,S,A|{\mbox{Object}})p({\mbox{Object}})}{p(X,S,A|{\mbox{No object}})p({\mbox{No object}})}}}$

${\displaystyle \approx {\frac {p(X,S,A|\Theta )p({\mbox{Object}})}{p(X,S,A|\Theta _{bg})p({\mbox{No object}})}}}$

where ${\displaystyle \Theta _{bg}}$ is the background model. This ratio is compared to a threshold ${\displaystyle T\,}$ to determine object presence/absence.

The likelihoods are factored as follows:

${\displaystyle p(X,S,A|\Theta )=\sum _{h\in H}p(X,S,A,h|\Theta )=}$

${\displaystyle \sum _{h\in H}\underbrace {p(A|X,S,h,\Theta )} _{\mbox{Appearance}}\underbrace {p(X|S,h,\Theta )} _{\mbox{Shape}}\underbrace {p(S|h,\Theta )} _{\mbox{Rel. Scale}}\underbrace {p(h|\Theta )} _{\mbox{Other}}}$

Appearance

Each part ${\displaystyle p\,}$ has an appearance modeled by a Gaussian density in the appearance space, with mean and covariance parameters ${\displaystyle \Theta _{p}^{app}=\{c_{p},V_{p}\}}$, independent of other parts' densities. The background model has parameters ${\displaystyle \Theta _{bg}^{app}=\{c_{bg},V_{bg}\}}$. Fergus et al. assume that, given detected features, the position and appearance of those features are independent. Thus, ${\displaystyle p(A|X,S,h,\Theta )=p(A|h,\Theta )\,}$. The ratio of the appearance terms reduces to

${\displaystyle {\frac {p(A|X,S,h,\Theta )}{p(A|X,S,h,\Theta _{bg})}}={\frac {p(A|h,\Theta )}{p(A|h,\Theta _{bg})}}}$

${\displaystyle =\prod _{p=1}^{P}\left({\frac {G(A(h_{p})|c_{p},V_{p})}{G(A(h_{p})|c_{bg},V_{bg})}}\right)^{b_{p}}}$

Recall from Weber et al. that ${\displaystyle h\,}$ is the hypothesis for the indices of foreground parts, and ${\displaystyle b\,}$ is the binary vector giving the occlusion state of each part in the hypothesis.

Shape

Shape is represented by a joint Gaussian density of part locations within a particular hypothesis, after those parts have been transformed into a scale-invariant space. This transformation precludes the need to perform an exhaustive search over scale. The Gaussian density has parameters ${\displaystyle \Theta ^{\mbox{shape}}=\{\mu ,\Sigma \}\,}$. The background model ${\displaystyle \Theta _{bg}\,}$ is assumed to be a uniform distribution over the image, which has area ${\displaystyle \alpha \,}$. Letting ${\displaystyle f\,}$ be the number of foreground parts,

${\displaystyle {\frac {p(X|S,h,\Theta )}{p(X|S,h,\Theta _{bg})}}=G(X(h)|\mu ,\Sigma )\alpha ^{f}}$

Relative scale

The scale of each part ${\displaystyle p\,}$ relative to a reference frame is modeled by a Gaussian density with parameters ${\displaystyle \Theta ^{\mbox{scale}}=\{t_{p},U_{p}\}\,}$. Each part is assumed to be independent of other parts. The background model ${\displaystyle \Theta _{bg}\,}$ assumes a uniform distribution over scale, within a range ${\displaystyle r\,}$.

${\displaystyle {\frac {p(S|h,\Theta )}{p(S|h,\Theta _{bg})}}=\prod _{p=1}^{P}G(S(h_{p})|t_{p},U_{p})^{d_{p}}r^{f}}$

Occlusion and statistics of feature detection

${\displaystyle {\frac {p(h|\Theta )}{p(h|\Theta _{bg})}}={\frac {p_{\mbox{Poiss}}(n|M)}{p_{\mbox{Poiss}}(N|M)}}{\frac {1}{^{n}C_{r}(N,f)}}p(b|\Theta )}$

The first factor models the number of features detected using a Poisson distribution, which has mean M. The second factor serves as a "book-keeping" factor for the hypothesis variable. The last factor is a probability table for all possible occlusion patterns.

Learning

The task of learning the model parameters ${\displaystyle \Theta =\{\mu ,\Sigma ,c,V,M,p(b|\Theta ),t,U\}\,}$ is accomplished by expectation maximization. This is carried out in a spirit similar to that of Weber et al. Details and formulas for the E-step and M-step can be seen in the literature.^[11]