International Journal of Computer Vision

Learning Sparse FRAME Models for Natural Image Patterns

Jianwen Xie ¹   Wenze Hu ²    Song-Chun Zhu ¹    Ying Nian Wu ¹

¹ University of California, Los Angeles (UCLA), USA     ² Google Inc, USA

Paper | Latex | Talk

1. Inhomogeneous FRAME

1.1 Model

We start from modeling roughly aligned images of object patterns from the same category, such as images in each category of Fig 1. Let {Im, m = 1,...,M} be a set of training training images. We use the notation Bx,s,α to denote a basis function such as Gabor wavelet centered at pixel x, and tuned to scale s and orientation α. We assume that s and α take values within a finite and properly discretized range. The inner product <I, Bx,s,α> can be considered the filter response of I at pixel x to a filter tuned to scale s and orientation α. All basis functions are normalized to have unit l2 norm. The inhomogeneous FRAME model is probability distribution defined on image I (1) where λx,s,α is a coefficient of the absolute value of the response, q(I) is a known reference distribution such as a Gaussian white noise model, Z(λ) is the normalizing constant. Fig 1. Training images. The inhomogeneous FRAME is a generative model that seeks to represent and generate object patterns shown above. Two categories of training sets: 6 hummingbirds and 12 Cats.

1.2 Learning

The FRAME model is a special case of the exponential family model, and the parameter λ={λ_x,s,α, ∀x,s,α} can be estimated from the training images by MLE. The MLE can be obtained by the stochastic gradient algorithm analyzed by Younes (1999) [1]. Let λ^(t) be the current estimate of λ, and let {_m, m = 1,...,} be a sample of synthesized images drawn from p(I; λ^(t) ). Then we can update λ by

(2)

where is the step size. The synthesized images {_m, m = 1,...,} can be drawn from p(I; λ^(t) ) by Hamiltonian Monte Carlo (HMC) [2]. The ratio of the normalizing constants

(3)

can be approximated by averaging over the sampled images {_m}. Starting from λ⁽⁰⁾ = 0 and log Z(λ⁽⁰⁾) = 0, we can compute log Z(λ^(t)) along the learning process by iteratively updating its value as follows:

(4)

Figure 2 illustrates the learning process by showing the synthesized images with λ being updated by the algorithm. The synthesized image starts from Gaussian white noises sampled from q(I), then gradually gets similar to the observed images in the overall shape and appearance.

2. Sparse FRAME

2.1 Model

In model (1), the (x,s,α) in _x,s,α is over all the pixels x and all the scales s and orientations α. We call such a model the dense FRAME. It is possible to sparsify the model by selecting only a small set of (x,s,α) so that _x,s,α is restricted to this selected subset, while such a selected subset of basis functions should be enough to interpret or reconstruct the training images. More explicitly, we can write the sparsified model as

Deformable Shared Sparse Coding (5) Sparsified inhomogeneous FRAME (6)

where n is the number of selected basis function, λ={λ_i, i=1,...,n} are the coefficients, and { B_xi,si,αi , i=1,...,n} is the selected set of basis functions shared by training images. We may allow these shared basis functions to perturb their locations and orientations to account for shape deformations. (Δx_m,i , Δα_m,i) are the perturbations of the location and orientation of the i-th basis function in the m-th image. Both Δx_m,i and Δα_m,i are assumed to vary within limited ranges.

2.2 Learning

The learning algorithm consists of two stages. (1) Selecting B = {B_xi,si,αi , i=1,...,n} by deformable shared sparse coding. (2) Estimating λ={λ_i, i=1,...,n} given selected B.

Stage 1: We want to select the basis functions B = {B_xi,si,αi , i=1,...,n} by minimizing the sum of reconstruction errors of all training images

(7)

We can extend the matching pursuit algorithm [3] to select basis functions to code multiple images simultaneously, while inferring local perturbations by local max pooling [4]:

Deformable shared matching pursuit algorithm

Stage 2 : After selecting B = {B_xi,si,αi , i=1,...,n}, we can then model {I_m} by the sparse FRAME model (6), by estimating λ at MLE. p(I; B, λ) in (6) now served as the deformable template in that the log-likelihood ratio of the I_m is

(8)

which serves as the template matching score, where we allow each selected B_i to perturb its location and orientation in view of (5), with the perturbations inferred by local max pooling. Again, let λ^(t) be the current estimate of λ, and let {_m, m = 1,...,} be the synthesized images drawn from p(I; λ^(t) ) by parallel chains. Then we can update λ by

(9)

The learned p(I; λ^(t) ) models the appearance of the undeformed template. So there is an explicit separation between appearance and shape variations.After we learn λ and compute Z(λ) as in (4), we can use the learned model as a deformable template to be matched to the testing image, where the template matching score at each location can be computed like (8).

Fig 4. Synthesis. Synthesized images generated by the learned sparse FRAME model. With HMC and warm start, they are produced by =36 parallel chains. The images are 100 × 100. The number of selected wavelets is 300. Fig 3. Reconstruction. The images are 100 x 100. The number of selected wavelets is 300. The first row are symbolic sketches of selected Gabor wavelets at different scales, where each selected Gabor wavelet is symbolized by a bar. The first 4 sketches correspond to 4 different scales. The last one is the superposition of the 4 scales, where smaller scales appear darker. The remainder display five examples of the observed images, the deformed sketches, the reconstructed images, and the residual images.

3. Synthesis by FRAME

Figure 5 and Figure 6 displays some images generated by the dense models and the sparse models learned from roughly aligned training images respectively. All the synthesized images are generated by the HMC algorithm along the learning process.

Fig 5. Dense model. Images generated by the learned dense FRAME models. Typical sizes of the images are 70 × 70. We run single chain in the learning process. Typical number of training images for each category is around 10. Fig 6. Sparse model. Images generated by the learned sparse FRAME models. Typical sizes of the images are 80 × 80. Number of selected wavelets is 300.

4. Geometric Transformation

We can obtain the geometrically transformed versions of the learned model by directly applying the operations of dilation, rotation, flipping, or even changing the aspect ratio to B = {B_xi,si,αi , i=1,...,n} without changing the values of λ. This amounts to simple affine transformations of (x_i,s_i,α_i, i=1,...,n). Figure 7 shows some examples of geometric transformations of the sparse FRAME model: flipping and rotation.

Fig 7. Geometric transformation. Each case shows the synthesized images and the symbolic sketch templates of the transformed models, which are derived from the learned model. Left: 360 degrees rotation. Middle: 360 degrees rotation. Right: left/right flipping.

5. Detection

The learned model can be used to detect the object in a testing image by deformable template matching. We can scan the template over the image domain D, and at each location X ∈ D, we match the template to the image patch within the bounding box centered at X by computing the template matching score based on (8). We then choose the location X that achieves the maximum template matching score as the center of the detected object. We also allow geometric transformation of template in detection, which includes rotation, scaling and left-right flipping. Figure 8 shows examples of detection.

Fig 8. Detection by template matching. Left top: a synthesized image generated by the model trained on 8 roughly aligned images with 250 wavelets. (The lack of regional contrasts in the synthesized image is due to the fact that no DoG wavelets are used). Left bottom: a model template represented by symbolic sketches of selected Gabor wavelets. Right: testing images where the objects are located by the bounding boxes.

6. Clustering

Model-based clustering can be accomplished by EM-type algorithm that fits mixtures of sparse FRAME models. Figure 9 and Figure 10 illustrate 5 experiments. The EM-type algorithm usually converges within 3-5 iterations. For each cluster, we generate 144 parallel chains in learning.

7. Unsupervised learning of codebooks

We can learn a codebook of sparse FRAME models from non-aligned images without annotation, by adopting the method of [6]. The learning algorithm iterates the following two steps: (1) Image encoding: given the current codebook, encode the training images by spatially translated, rotated, scaled versions of the models (templates) in the codebook. (2) Codebook re-learning: re-learn each model in the codebook from the image patches currently covered by this template. Figure 11 and 12 illustrate experiments of codebook learning. For the experiments in Figure 12, we select a small number wavelets of a single scale, so the synthesized images mainly capture the edge patterns.

Fig 11. Codebook learning (interpretation by reconstruction). The first row displays the synthesized images (100 × 100) from the mixture models. The second row displays training images and the third row shows their reconstructions by the mixture models.

Fig 12. Codebook learning (interpretation by sketching). In each experiment, synthesized images (100 × 100) from the models of the learned codebook are displayed together with the training images and their sketches by the learned models, where each Gabor wavelet is illustrated by a bar. Lotus experiment: each model has 30 wavelets, learned from 7 images. Cat experiment: each model has 40 wavelets, learned from 20 images.

8. Object Classification Using learned Codebooks

8.1 "Bag-of-word" Representation by A Learned Codebook

The learned codebook of sparse FRAME models can serve as "words" in the "bag-of-word" method for object classification. Suppose we have a codebook of T models {B^(t) , t=1, ..., T} learned from training images. For each image I_m, we denote R^(t)_m(X,S,A)=L(I_m|B^(t)_X,S,A) as the log-likelihood of B^(t) at location X, scale S, and orientation A, both S and A are assumed to take values within a finite and properly discretized range. Let r^(t)_m(A)=max(max_X,S R^(t)_m(X,S,A), 0) be the maximum score at orientation A. Then each image I_m can be represented by a T×N_A-dimensional feature vector (r^(t)_m(A), t=1,...,T, ∀A), where N_A is the number of possible values A can take. After extracting features, we can use any discriminative method to train classifiers (e.g. linear logistic regression or SVM [7]) on such feature vectors for object classification. Spatial pyramid matching (SPM) [8] can also be utilized to further boost the classification performance.

8.2 Binary Classification

8.3 Multi-class Classification

Our second set of experiments is on the LHI-Animal-Faces dataset [12], which consists of around 2200 images for 20 categories of animal or human faces. We randomly select half of the images per class for training and the rest for testing. We learn a codebook of 10 sparse FRAME models for each category in an unsupervised way. We then combine the codebooks of all the categories (in total 20 × 10 = 200 codewords). The maps of the template matching scores from the models in the combined codebook are computed for each image, and they are then fed into SPM, which equally divides an image into 1, 4, 16 areas, and concatenates the maximum scores at different image areas into a feature vector. We use multi-class SVM to train image classifiers based on the feature vectors, and then evaluate the classification accuracies of these classifiers on the testing data using the one-versus-all rule. Table 3 lists four published results [12] on this dataset obtained by other methods: (a) HoG feature trained with SVM, (b) Hybrid Image Template (HIT) [12], (c) multiple transformation invariant HITs (Mixture of HIT) [12], and (d) part-based HoG feature trained with latent SVM [13]. Our method outperforms the other methods in terms of classification accuracy on this dataset.

8.4 Domain Transfer

Conclusion

The sparse FRAME model has the following properties.

(1) It can reconstruct the training images.

(2) It can synthesize new images.

(3) It separates shape deformations and appearance variations.

(4) It gives interpretable sketches.

(5) Dictionaries or codebooks of models can be learned in unsupervised manner.

(6) It combines rich traditions of harmonic analysis and Markov random field models.

References