Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing

Long Zhu, Yuanhao Chen, Alan L. Yuille

Introduction

In the mid-2000s, the computer vision community grappled with representing objects that exhibit high variability in appearance, scale, and rotation. While Probabilistic Context-Free Grammars (PCFGs) excelled at representing hierarchical structures (like the parts of an object), and Markov Random Fields (MRFs) effectively captured local spatial relationships, combining them into a learnable, unsupervised framework remained a major challenge.

This paper presents a significant step forward by bridging the gap between flexible probabilistic grammars and the spatial constraints of MRFs. The authors tackle the "structure induction" problem: enabling a machine to analyze unlabeled images and discover not just where an object is, but what its underlying structural parts are, without prior geometric instruction. The result is an unsupervised method for learning "AND-OR" graph models that can perform complex object inference in under one second.

Methodology: Structure Induction

The core of the proposed system is an algorithm called Structure Induction (or "Structure Pursuit"), which builds a probabilistic grammar using an AND-OR graph. In this architecture, OR nodes represent variations (e.g., "this object is a face OR a bike"), while AND nodes represent the decomposition of an object into its constituent parts.

To achieve scale and rotation invariance, the model eschews single pixels in favor of triplets of features. Because three points form a triangle whose internal angles remain constant regardless of zoom or rotation, this geometric approach provides built-in invariance. The system extracts these features using the Kadir-Brady operator to find regions of interest, followed by SIFT descriptors to represent them.

The learning process is iterative:

  1. The algorithm initializes with a simple background model.
  2. It proposes new feature triplets from a vocabulary learned via K-means clustering.
  3. An Expectation-Maximization (EM) approach evaluates if adding a specific structure improves the model's ability to explain the training data. Structures that significantly increase the score are retained.

Once the grammar is learned, the model employs dynamic programming—similar to the Viterbi algorithm—to rapidly parse new images.

Experiments and Results

The authors evaluated their approach on the classic Caltech 101 benchmark, testing on 13 specific categories including Chairs, Cougars, Pianos, Pandas, and Roosters.

Panda detection result showing 90.0% accuracy

Additionally, they designed a custom Hybrid Dataset mixing Faces, Motorbikes, and Airplanes. This tested the model's ability to learn a "super-category" where the top-level OR node must first decide which object class it is observing before parsing its specific parts.

Piano example from the Caltech 101 dataset

The model demonstrated several key strengths:

  • High Accuracy: The system achieved scores over 90% for most Caltech 101 objects, including 98% for Faces and 92.6% for Motorbikes. It performed competitively with the then-state-of-the-art Constellation Model.
  • Efficiency: Inference (detecting and parsing the object) takes less than one second for a standard 320x240 image.
  • Robustness: Objects were successfully detected even when rotated a full 360 degrees or scaled between 60% and 150% of their original size.
  • Unsupervised Part Discovery: The model successfully discovered spatial arrangements of features purely through statistical recurrences, rather than just drawing bounding boxes.

Limitations and Future Work

While highly effective, the authors note a few limitations. The current implementation uses a restricted grammar depth, primarily relying on a single OR-node at the top; deeper grammars could represent objects in greater detail. Furthermore, the model relies on a specific set of SIFT-like features. Incorporating a richer feature vocabulary could improve handling of complex textures. Finally, while the model excels at 2D in-plane rotation, it is not explicitly designed to handle 3D out-of-plane rotations (e.g., viewing a car from the front versus the side) without treating them as entirely separate OR branches.

Summary updated

Abstract

We describe an unsupervised method for learning a probabilistic grammar of an object from a set of training examples. Our approach is invariant to the scale and rotation of the objects. We illustrate our approach using thirteen objects from the Caltech 101 database. In addition, we learn the model of a hybrid object class where we do not know the specific object or its position, scale or pose. This is illustrated by learning a hybrid class consisting of faces, motorbikes, and airplanes. The individual objects can be recovered as different aspects of the grammar for the object class. In all cases, we validate our results by learning the probability grammars from training datasets and evaluating them on the test datasets. We compare our method to alternative approaches. The advantages of our approach is the speed of inference (under one second), the parsing of the object, and increased accuracy of performance. Moreover, our approach is very general and can be applied to a large range of objects and structures.
BibTeX
@inproceedings{zhu2007unsupervised,
  author = {Long Zhu and Yuanhao Chen and Alan L. Yuille},
  title = {{Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing}},
  booktitle = {The MIT Press eBooks},
  year = {2007},
  doi = {10.7551/mitpress/7503.003.0207},
}
Figure