Pattern Recognition from One Example by Chopping

François Fleuret, Gilles BlanchardNeurIPS 2005 · OpenReview

Standard machine learning models are notoriously "data hungry," often requiring hundreds or thousands of labeled examples to recognize a specific class of objects. In stark contrast, biological visual systems are remarkably efficient. If you see a specific, uniquely shaped teapot just once, you can usually recognize it again from a different angle or under different lighting conditions.

This paper introduces Chopping, a novel framework for "one-sample learning"—the ability to recognize a new object after seeing it only once. By training hundreds of random binary classifiers on a reference set of different objects, the system learns universal visual invariances (like lighting and pose) that it can then apply to identify similarities between images of entirely new, unseen objects.

The Challenge of Interclass Transfer

The authors address the challenge of interclass transfer: how can we use knowledge gained from known objects (e.g., chairs and cars) to help us recognize a completely new object (e.g., a specific statue) from a single example?

The goal is to move away from learning specific object shapes and toward learning a general "similarity measure" that is robust to noise, rotation, and illumination. Instead of asking "What is this object?", the system is trained to ask "Are these two things the same?"

The "Chopping" Algorithm

Instead of trying to model complex geometric deformations explicitly, the authors use a brute-force statistical approach called Chopping. The method breaks down into four key steps:

  1. Random Splits (The "Chopping"): The algorithm takes a reference database of labeled objects and creates hundreds of random "splits." For each split, half of the object classes are randomly assigned to "Class 0" and the other half to "Class 1."
  2. Training Predictors: For every random split, a binary classifier (a linear perceptron) is trained using features selected via Conditional Mutual Information Maximization. Because a single split contains many different objects in each category, the classifier is forced to ignore specific object identities. Instead, it must find broader visual commonalities and invariances to succeed.
  3. Bayesian Combination: To compare two new images, they are passed through all the trained split-predictors. If the two images show the same object, the predictors should consistently return the same labels. These responses are combined using a Bayesian log-odds ratio to calculate the final probability that the two images represent the same object.
  4. Smart Chopping: The authors also propose an optimized version where "problematic" objects—those frequently misclassified in a specific split—are removed to sharpen the predictor's accuracy.

Datasets and Evaluation

The authors evaluated their method on two distinct datasets to test different types of visual invariance:

1. COIL-100 Dataset A standard computer vision dataset containing 7,200 images of 100 different objects filmed from 72 different angles. This tests the model's ability to handle 3D pose and illumination variations.

COIL-100 Dataset Examples

2. Degraded LaTeX Symbols A custom dataset of 150 different LaTeX symbols (like $\Phi$ or $\cap$). To make it challenging, the authors generated 1,000 versions of each symbol with random rotations, scaling, and "noise" in the form of random grayscale lines.

Degraded LaTeX Symbols

Key Results and Insights

The results demonstrate that Chopping is significantly more efficient than traditional training paradigms:

  • One vs. Many: On both the COIL-100 and LaTeX datasets, the Chopping method using only one example achieved an error rate comparable to a standard classifier trained on 32 examples.
  • Error Rates: The system achieved an optimal error rate of 7.41% on the complex LaTeX symbols and 11.42% on the COIL-100 dataset.
  • Superiority over Direct Learning: Chopping outperformed "Learnt Similarity" (training a single classifier directly on pairs of images). This suggests that decomposing the problem into many independent, randomized splits is a more effective way to capture visual invariance.
  • The Power of Ensembles: A single random split is a weak predictor, but the combination of hundreds of "chops" creates a highly robust similarity metric without needing explicit 3D geometry or mathematical rotation models.

Limitations and Future Work

While highly effective, the Chopping framework has a few limitations. The "Smart Chopping" variant, while improving accuracy, doubles the computational cost because each predictor must be built twice. Additionally, the method relies heavily on edge-based boolean features; while effective for these specific 32x32 and 38x38 pixel datasets, it remains unclear how well these features scale to high-resolution, cluttered real-world scenes. Finally, the Bayesian combination relies on a "Naive Bayes" assumption (that split responses are independent). The authors acknowledge this simplification and suggest that more sophisticated probabilistic modeling could yield even better results in the future.

Summary updated

Abstract

We investigate the learning of the appearance of an object from a single image of it. Instead of using a large number of pictures of the object to recognize, we use a labeled reference database of pictures of other ob- jects to learn invariance to noise and variations in pose and illumination. This acquired knowledge is then used to predict if two pictures of new objects, which do not appear on the training pictures, actually display the same object. We propose a generic scheme called chopping to address this task. It relies on hundreds of random binary splits of the training set chosen to keep together the images of any given object. Those splits are extended to the complete image space with a simple learning algorithm. Given two images, the responses of the split predictors are combined with a Bayesian rule into a posterior probability of similarity. Experiments with the COIL-100 database and with a database of 150 de- graded LATEX symbols compare our method to a classical learning with several examples of the positive class and to a direct learning of the sim- ilarity.
BibTeX
@inproceedings{fleuret2005pattern,
  author = {François Fleuret and Gilles Blanchard},
  title = {{Pattern Recognition from One Example by Chopping}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
  url = {https://openreview.net/forum?id=SkbRhd-_bB},
}

Loading related content...

Figure