Constellation model

The constellation model is a probabilistic, generative model for category-level object recognition in computer vision. Like other part-based models, the constellation model attempts to represent an object class by a set of N parts under mutual geometric constraints. Because it considers the geometric relationship between different parts, the constellation model differs significantly from appearance-only, or "bag-of-words" representation models, which explicitly disregard the location of image features. The problem of defining a generative model for object recognition is difficult. The task becomes significantly complicated by factors such as background clutter, occlusion, and variations in viewpoint, illumination, and scale. Ideally, we would like the particular representation we choose to be robust to as many of these factors as possible. In category-level recognition, the problem is even more challenging because of the fundamental problem of intra-class variation. Even if two objects belong to the same visual category, their appearances may be significantly different. However, for structured objects such as cars, bicycles, and people, separate instances of objects from the same category are subject to similar geometric constraints. For this reason, particular parts of an object such as the headlights or tires of a car still have consistent appearances and relative positions.…

The constellation model is a probabilistic, generative model for category-level object recognition in computer vision. Like other part-based models, the constellation model attempts to represent an object class by a set of N parts under mutual geometric constraints. Because it considers the geometric relationship between different parts, the constellation model differs significantly from appearance-only, or "bag-of-words" representation models, which explicitly disregard the location of image features. The problem of defining a generative model for object recognition is difficult. The task becomes significantly complicated by factors such as background clutter, occlusion, and variations in viewpoint, illumination, and scale. Ideally, we would like the particular representation we choose to be robust to as many of these factors as possible. In category-level recognition, the problem is even more challenging because of the fundamental problem of intra-class variation. Even if two objects belong to the same visual category, their appearances may be significantly different. However, for structured objects such as cars, bicycles, and people, separate instances of objects from the same category are subject to similar geometric constraints. For this reason, particular parts of an object such as the headlights or tires of a car still have consistent appearances and relative positions. The Constellation Model takes advantage of this fact by explicitly modeling the relative location, relative scale, and appearance of these parts for a particular object category. Model parameters are estimated using an unsupervised learning algorithm, meaning that the visual concept of an object class can be extracted from an unlabeled set of training images, even if that set contains "junk" images or instances of objects from multiple categories. It can also account for the absence of model parts due to appearance variability, occlusion, clutter, or detector error. 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 N_i\, represents the number of parts of type 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 x^m\, . Suppose that the object will be composed of F\, distinct foreground parts. For notational simplicity, we assume here that F = T\, , though the model can be generalized to F > T\, . A hypothesis h\, is then defined as a set of indices, with h_i = j\, , indicating that point x_{ij}\, is a foreground point in X^o\, . The generative probabilistic model is defined through the joint probability density p(X^o,x^m,h)\, . To parametrize the joint probability density, Weber & Welling introduce the auxiliary variables b\, and n\, , where b\, is a binary vector encoding the presence/absence of parts in detection ( b_i = 1\, if h_i > 0\, , otherwise b_i = 0\, ), and n\, is a vector where n_i\, denotes the number of background candidates included in the i^{th} row of X^o\, . Since b\, and n\, are completely determined by h\, and the size of X^o\, , we have p(X^o,x^m,h) = p(X^o,x^m,h,n,b)\, . By decomposition, 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, p(n) = \prod_{i=1}^T \frac{1}{n_i!}(M_i)^{n_i}e^{-M_i} where M_i\, is the average number of background detections of type i\, per image. Depending on the number of parts F\, , the probability p(b)\, can be modeled either as an explicit table of length 2^F\, , or, if F\, is large, as F\, independent probabilities, each governing the presence of an individual part. The density p(h|n,b)\, is modeled by 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 H(b,n)\, denotes the set of all hypotheses consistent with b\, and n\, , and N_f\, denotes the total number of detections of parts of type f\, . This expresses the fact that all consistent hypotheses, of which there are \textstyle \prod_{f=1}^F N_f^{b_f} , are equally likely in the absence of information on part locations. And finally, p(X^o,x^m|h,n) = p_{fg}(z)p_{bg}(x_{bg})\, where z = (x^ox^m)\, are the coordinates of all foreground detections, observed and missing, and x_{bg}\, represents the coordinates of the background detections. Note that foreground detections are assumed to be independent of the background. p_{fg}(z)\, is modeled as a joint Gaussian with mean \mu\, and covariance \Sigma\, . \Theta = \{\mu, \Sigma, p(b), M\}\, are estimated using expectation maximization. \mu\, and \Sigma\, , we recall, are the mean and covariance of the joint Gaussian p_{fg}(z)\, , p(b)\, is the probability distribution governing the binary presence/absence of parts, and M\, is the mean number of background detections over part types. 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 \Theta\, . Since this is difficult to achieve analytically, EM iteratively maximizes a sequence of cost functions, 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: \tilde{\mu} = \frac{1}{I} \sum_{i=1}^I E[z_i] \tilde{\Sigma} = \frac{1}{I} \sum_{i=1}^I E[z_iz_i^T] - \tilde{\mu}\tilde{\mu}^T \tilde{p}(\bar{b}) = \frac{1}{I} \sum_{i=1}^I E[\delta_{b,\bar{b}}] \tilde{M} = \frac{1}{I} \sum_{i=1}^I E[n_i] 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}

The method of Fergus et al.

In Weber et al., shape and appearance models are constructed separately. Once the set of candidate parts had been selected, shape is learned independently of appearance. The innovation of Fergus et al. is to learn not only two, but three model parameters simultaneously: shape, appearance, and relative scale. Each of these parameters are represented by Gaussian densities. R = \frac{p(\mbox{Object}|X,S,A)}{p(\mbox{No object}|X,S,A)} = \frac{p(X,S,A|\mbox{Object})p(\mbox{Object})}{p(X,S,A|\mbox{No object})p(\mbox{No object})} \approx \frac{p(X,S,A|\Theta)p(\mbox{Object})}{p(X,S,A|\Theta_{bg})p(\mbox{No object})} where \Theta_{bg} is the background model. This ratio is compared to a threshold T\, to determine object presence/absence. The likelihoods are factored as follows: p(X,S,A|\Theta) = \sum_{h \in H} p(X,S,A,h|\Theta) = \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}} Each part p\, has an appearance modeled by a Gaussian density in the appearance space, with mean and covariance parameters \Theta_p^{app} = \{c_p,V_p\} , independent of other parts' densities. The background model has parameters \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, p(A|X,S,h,\Theta) = p(A|h,\Theta)\, . The ratio of the appearance terms reduces to \frac{p(A|X,S,h,\Theta)}{p(A|X,S,h,\Theta_{bg})} = \frac{p(A|h,\Theta)}{p(A|h,\Theta_{bg})} = \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 h\, is the hypothesis for the indices of foreground parts, and b\, is the binary vector giving the occlusion state of each part in the hypothesis. 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 \Theta^{\mbox{shape}} = \{\mu,\Sigma\}\, . The background model \Theta_{bg}\, is assumed to be a uniform distribution over the image, which has area \alpha\, . Letting f\, be the number of foreground parts, \frac{p(X|S,h,\Theta)}{p(X|S,h,\Theta_{bg})} = G(X(h)|\mu,\Sigma)\alpha^f The scale of each part p\, relative to a reference frame is modeled by a Gaussian density with parameters \Theta^{\mbox{scale}} = \{t_p,U_p\}\, . Each part is assumed to be independent of other parts. The background model \Theta_{bg}\, assumes a uniform distribution over scale, within a range r\, . \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 \frac{p(h|\Theta)}{p(h|\Theta_{bg})} = \frac{p_{\mbox{Poiss}}(n|M)}{p_{\mbox{Poiss}}(N|M)} \frac{1}{^nC_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. The task of learning the model parameters \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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373112441 under CC BY-SA 4.0; modifications have been made.