University of Paris 6 at TRECVID 2006: Forest of Fuzzy Decision Trees for High-Level Feature Extraction

Marcin Detyniecki, Ph.D., Christophe Marsala, Marcin DetynieckiTrecvid 2006

Abstract

In the TRECVID 2006 evaluation, researchers from the University of Paris 6 proposed a robust framework for high-level video feature extraction using a Forest of Fuzzy Decision Trees (FFDT). This approach addresses the inherent challenges of semantic concept recognition in large-scale video archives, specifically data imbalance and the "fuzzy" nature of numerical visual descriptors. By combining spatial segmentation with an ensemble of fuzzy classifiers trained on balanced datasets, the method achieves improved ranking performance. This paper details the pipeline, from regional descriptor extraction to the aggregation of forest votes, and analyzes the impact of forest size on retrieval accuracy.

Introduction

High-level feature extraction—the automated identification of semantic concepts like "Military," "Desert," or "Sports" in video—remains a significant challenge in computer vision. Two primary obstacles hinder progress: the extreme imbalance between positive and negative examples in large datasets, and the brittleness of hard-threshold decision trees when dealing with noisy, numerical visual data. To overcome these, the University of Paris 6 team deployed a Forest of Fuzzy Decision Trees (FFDT), demonstrating that ensemble methods can effectively model skewed data spaces.

Methodology

The proposed system utilizes a multi-stage pipeline centered on fuzzy induction using the Salammbô software.

Spatial Segmentation and Descriptors

Rather than treating the entire frame as a single entity, the system divides each keyframe into five distinct regions: Top, Bottom, Left, Right, and Middle. This allows the model to capture the compositional importance of different areas. For instance, the "Middle" and "Bottom" regions often contain the primary subject or ground context and are thus assigned higher-resolution HSV color histograms compared to the peripheral regions.

Figure 1: Spatial segmentation of keyframes into five regions (Top, Bottom, Left, Right, Middle) to capture regional semantic importance.

The Forest of Fuzzy Decision Trees (FFDT)

The core of the approach is the FFDT. Unlike traditional decision trees, fuzzy trees use soft partitions, which are more resilient to numerical noise in descriptors. To handle data imbalance, the "forest" consists of multiple trees, each trained on a balanced subset containing an equal number of positive and negative examples.

To classify a new frame, the degrees of certainty from all trees in the forest are aggregated using a Łukasiewicz t-norm. For the final shot ranking, a "Max" aggregation strategy—assigning a shot the score of its highest-rated keyframe—was found to be most effective, providing a nuanced ranking that single-tree models lack.

Results and Discussion

The system was evaluated on the TRECVID 2006 dataset across 39 high-level features. A key finding was the direct correlation between forest size and performance.

Figure 2: Performance metrics across 39 features, comparing the submitted run with forests of size N=5, 11, and 20. Increasing the number of trees consistently improves Inferred Average Precision and hit rates at various depths.

As shown in Figure 2, increasing the number of trees from the initial competition submission to larger ensembles (up to 20 trees) led to consistent improvements in Inferred Average Precision and hit rates at depths of 100, 1000, and 2000. The ensemble approach provides a "collegiate" decision that is far more effective for ranking borderline cases. The system performed particularly well on features with strong visual signatures, such as "Military," "Desert," and "Waterscape," though it struggled with more abstract or dynamic concepts like "Weather" or "Meeting."

Conclusion

The University of Paris 6's participation in TRECVID 2006 demonstrated that Forests of Fuzzy Decision Trees are a powerful tool for managing the complexities of video retrieval. While simple HSV histograms served as a baseline, the ensemble architecture proved vital for handling skewed data distributions. Future work will focus on integrating more sophisticated visual descriptors and refining fuzzy partitioning to better capture dynamic semantic content.

Summary updated

BibTeX
@inproceedings{phd2006university,
  author = {Marcin Detyniecki, Ph.D. and Christophe Marsala and Marcin Detyniecki},
  title = {{University of Paris 6 at TRECVID 2006: Forest of Fuzzy Decision Trees for High-Level Feature Extraction}},
  booktitle = {Trecvid},
  year = {2006},
}
Figure