Abstract
We introduce a Probabilistic Grammar-Markov Model (PGMM) which couples probabilistic context-free grammars and Markov Random Fields. These PGMMs are generative models defined over attributed features and are used to detect and classify objects in natural images. PGMMs are designed so that they can perform rapid inference, parameter learning, and the more difficult task of structure induction. PGMMs can deal with unknown 2D pose (position, orientation, and scale) in both inference and learning, as well as different appearances or aspects of the model. The PGMMs can be learnt in an unsupervised manner where the image can contain one of an unknown number of objects of different categories or even be pure background. We demonstrate results on a subset of the Caltech dataset, showing performance comparable to the state of the art with inference performed in less than five seconds.
Introduction
In the mid-2000s, computer vision research faced a significant hurdle: structure induction. While researchers could train models to recognize objects given "weak supervision" (e.g., labels indicating an object's presence), it was far more challenging to build a system that could analyze unlabeled, cluttered images and autonomously discover the underlying structure of the objects within them.
Traditional models like Markov Random Fields (MRFs) excel at modeling spatial relationships but typically require a fixed graph structure. Conversely, Probabilistic Context-Free Grammars (PCFGs)—concepts adapted from linguistics—can handle variable structures, such as an object viewed from different angles, but often struggle to capture the rigid spatial geometry of visual parts. The authors of this paper bridge this gap by creating a hybrid model capable of learning both the constituent "parts" of an object and the "rules" governing their assembly without human intervention.
The Probabilistic Grammar-Markov Model (PGMM)
The proposed PGMM architecture is built upon a hybrid framework that leverages the strengths of both grammars and spatial graphs.
The Hybrid Architecture
The model utilizes an AND-OR graph structure. "AND" nodes represent the composition of parts (e.g., a face is composed of eyes AND a nose), while "OR" nodes represent different "aspects" or appearances (e.g., a car viewed from the side OR the front). Horizontal connections between nodes act as the "Markov" component, enforcing necessary spatial constraints between parts. This allows the model to handle "topological" changes—such as parts disappearing due to occlusion—while maintaining geometric consistency.
Oriented Triplets as Building Blocks
Instead of operating on individual pixels or isolated points, the model uses triplets of features as its fundamental building blocks. The critical insight is that the internal angles of a triangle are invariant to 2D scale and rotation. This geometric property allows the model to recognize a motorbike regardless of whether it is zoomed in, zoomed out, or tilted, providing a local coordinate system that simplifies the learning of unknown poses.
Structure Pursuit and Unsupervised Learning
The model begins as a simple "background" model. It then iteratively "pursues" structure by identifying "suspicious coincidences"—clusters of features that appear together more frequently than chance would suggest. It proposes new triplets to add to the grammar and employs model selection (scoring) to determine if the new structure provides a better explanation of the data. This process allows for the unsupervised discovery of object "aspects," assigning distinct looks to different branches of an "OR" node.
Experimental Evaluation
The authors evaluated the PGMM on several standard benchmarks to test its classification and localization capabilities.
Datasets and Results
- Caltech 4: Includes faces, motorbikes, airplanes, and background images.
- Caltech 101: A diverse set of 101 categories. Testing focused on subsets of 13 and 26 categories with at least 80 images each.
- Modified Caltech 101: To demonstrate 2D pose invariance, the authors created a custom dataset by artificially rotating (360 degrees) and scaling (60% to 150%) images from the original set.
The PGMM achieved classification rates comparable to the contemporary state-of-the-art. Notable performance metrics include 97.7% on Faces, 92.9% on Motorbikes, and 91.8% on Airplanes. Beyond accuracy, the model demonstrated significant advantages in speed—performing inference in less than 5 seconds—and maintained 96.3% accuracy in rotation and scale tests.
Discussion and Future Work
While the PGMM handles 2D transformations effectively, it currently treats 3D viewpoint changes as different "aspects" (OR nodes) rather than modeling 3D geometry directly. Furthermore, the system is dependent on the initial quality of feature detectors; if these fail to identify "interesting" points, the grammar lacks the necessary data to build a model. Future research directions include extending the model to incorporate a richer set of image features beyond point-based descriptors to capture more subtle object textures and boundaries.
Summary updated