Unsupervised Image Classification with a Hierarchical EM Algorithm

Annabelle Chardin, Patrick PérezICCV 1999 · OpenReview

Abstract

This work is undertaken in the context of hierarchical stochastic models for the resolution of discrete inverse problems from low level vision. Some of these models lie on the nodes of a quadtree which leads to non-iterative inference procedures. Nevertheless, if they circumvent the algorithmic drawbacks of grid-based models (computational load and/or great dependance on the initialization), they admit modeling shortcomings (cumbersome and somehow artificial). We investigate a new hierarchical stochastic model which benefits from both the spatial and hierarchical prior modeling. The independence graph is based on a tree which has been pollarded with nodes at the coarsest resolution exhibiting a grid-based interaction structure. For this class of model, we address the critical problem of parameter estimation. To this end, we derive an EM algorithm on the hybrid structure which mixes an exact EM algorithm on each subtree and a low cost Gibbs EM algorithm on the coarse spatial grid. Experiments on a synthetic image and multispectral satellite images are reported.

Introduction

In computer vision, inverse problems such as image classification—the process of assigning labels to pixels—frequently employ Markov Random Fields (MRFs). These models are adept at capturing local dependencies between neighboring pixels. However, standard grid-based MRFs suffer from two primary limitations: slow information propagation across the image and a high sensitivity to initialization, often leading to convergence at local optima.

To address these issues, hierarchical models like quadtrees are often used to facilitate rapid global information exchange. While efficient, pure tree structures can introduce artificial constraints and "blocking artifacts" that do not align with natural image geometry. This paper proposes a hybrid model that integrates the spatial flexibility of MRFs with the computational efficiency of hierarchical structures.

The Hybrid Hierarchical Model

The core innovation of this research is the "pollarded" tree structure. Unlike a standard quadtree that converges to a single root node, this model truncates the tree at a coarse level. The nodes at this level are then organized into a traditional rectangular spatial grid.

Comparison between a standard quadtree (a) and the proposed hybrid structure (b) featuring a coarse spatial grid.

This architecture allows each site on the coarse grid to serve as the root of a subtree branching down to individual pixels at the finest resolution. This hybrid approach maintains local spatial consistency through the top-level grid while leveraging the tree structure for global information integration.

The Hybrid EM Algorithm

Estimating model parameters without human supervision requires a specialized Expectation-Maximization (EM) algorithm. The authors developed a two-part procedure:

  1. Sub-tree Inference: An exact, non-iterative "two-sweep" procedure (upward and downward) is performed on the subtrees, similar to the Forward-Backward algorithm used in Hidden Markov Models.
  2. Coarse Grid Inference: A "Gibbsian EM" is applied to the coarse top-level grid. By using sampling only at this reduced resolution, the algorithm captures non-causal spatial interactions without the heavy computational burden typically associated with grid-based sampling.

Experimental Results

The model was evaluated using both synthetic and real-world datasets. The synthetic data consisted of a $256 \times 256$ image with five classes and Gaussian noise, providing a ground truth for comparison. Real-world testing utilized multispectral SPOT satellite imagery of the Bay of Lannion, France, categorized into eight land-cover types.

Performance metrics and parameter estimation comparing the hybrid model against standard spatial EM algorithms.

As shown in the performance tables, the hybrid hierarchical models achieved exceptional accuracy on synthetic data, reaching 98-99%, compared to approximately 88-91% for standard spatial Gibbsian EM. Furthermore, the hybrid approach demonstrated a massive speed advantage: while a high-quality spatial EM took 25 minutes to converge, the hybrid model reached superior results in just 48 to 87 seconds. On satellite data, the model maintained a high classification accuracy of approximately 89%.

Conclusion

The hybrid hierarchical model successfully bridges the gap between spatial MRFs and tree-based models. By "pollarding" the quadtree and applying a mixed EM algorithm, the researchers achieved significant gains in both classification accuracy and processing speed. Future work will focus on automating the selection of the optimal number of levels in the hierarchy and improving the model's ability to distinguish between highly similar spectral classes.

Summary updated

Abstract

This work is undertaken in the context of hierarchical stochastic models for the resolution of discrete inverse problems from low level vision. Some of these models lie on the nodes of a quadtree which leads to non-iterative inference procedures. Nevertheless, if they circumvent the algorithmic drawbacks of grid-based models (computational load and/or great dependance on the initialization), they admit modeling shortcomings (cumbersome and somehow artificial). We investigate a new hierarchical stochastic model which benefits from both the spatial and hierarchical prior modeling. The independence graph is based on a tree which has been pollarded with nodes at the coarsest resolution exhibiting a grid-based interaction structure. For this class of model, we address the critical problem of parameter estimation. To this end, we derive an EM algorithm on the hybrid structure which mixes an exact EM algorithm on each subtree and a low cost Gibbs EM algorithm on the coarse spatial grid. Experiments on a synthetic image and multispectral satellite images are reported.
BibTeX
@inproceedings{chardin1999unsupervised,
  author = {Annabelle Chardin and Patrick Pérez},
  title = {{Unsupervised Image Classification with a Hierarchical EM Algorithm}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {1999},
  url = {https://openreview.net/forum?id=SkVn_efubr},
}
Figure