Video Event Classification Using Bag of Words and String Kernels

Lamberto Ballan, Marco Bertini, Alberto Del Bimbo, Giuseppe Serra

Introduction

The "Bag-of-Words" (BoW) model is a cornerstone of computer vision, particularly for object and scene recognition. By treating an image as an unordered collection of local features, it achieves robustness to spatial variations. However, when applied to video events—such as a soccer goal or a person exiting a vehicle—the standard BoW model's "temporally orderless" nature becomes a significant drawback. In video, the sequence of visual primitives is essential for distinguishing between similar actions. For instance, a "goal kick" and a "shot on goal" may share visual elements but follow distinct temporal trajectories.

This paper addresses the challenge of incorporating temporal progression into the BoW framework without resorting to computationally expensive 3D spatio-temporal features or rigid fixed-length sampling. The authors propose a method that treats a video clip as a "phrase" composed of "characters" (frame-level histograms), enabling the use of sequence alignment techniques for classification.

Proposed Methodology

The authors introduce a hierarchical representation that bridges the gap between simple BoW models and complex temporal modeling.

1. Frame and Action Representation

Each video frame is treated as a discrete "character." SIFT features are extracted from every frame and quantized into a visual vocabulary using k-means. A frame is then represented as a histogram of these visual words. Consequently, an entire video clip is viewed as a sequence (or "string") of these histograms.

Representation of a video clip as a sequence of frame-level Bag-of-Words histograms.

2. Sequence Alignment and String Kernels

To compare videos of varying lengths, the authors adapt the Needleman-Wunsch algorithm, a global alignment technique originally used in bioinformatics. The algorithm calculates an "edit distance" based on the cost of insertions, deletions, and substitutions required to transform one video string into another. Because the "alphabet" of histograms is continuous, the Chi-square distance is used to determine the similarity between individual frame-histograms.

This distance is then integrated into a Support Vector Machine (SVM) via a custom string kernel: $$k(x, x') = \exp(-d(x, x'))$$ where $d$ represents the Needleman-Wunsch distance. This formulation allows the SVM to operate on variable-length sequences while strictly respecting their temporal order.

Experimental Evaluation

The proposed method was evaluated on two datasets: a specialized soccer dataset and a subset of the TRECVID 2005 corpus.

Soccer Dataset Performance

The soccer dataset consists of 100 clips featuring four actions: shot-on-goal, placed-kick, throw-in, and goal-kick. This dataset is particularly difficult due to variations in lighting, stadium backgrounds, and action speed. The SVM with a string kernel achieved a mean accuracy of 0.73, significantly outperforming the baseline kNN classifier's 0.52.

Confusion matrices comparing the baseline kNN classifier (a) with the proposed SVM string classifier (b) on the soccer dataset.

As shown in the confusion matrices, the string kernel approach is notably more effective at distinguishing between classes that are visually similar but temporally distinct, such as "shot-on-goal" and "throw-in."

TRECVID 2005 Results

On a broader subset of TRECVID 2005 (covering concepts like Exiting Car and Running), the approach achieved a Mean Average Precision (MAP) of 0.35, compared to 0.28 for the traditional orderless BoW model. The most substantial gains were observed in dynamic classes like "Exiting Car" and "Airplane Flying," where temporal sequence is a primary defining characteristic.

Key Insights and Conclusion

A surprising finding was that a small visual vocabulary (30 words) outperformed larger ones in the soccer domain. The authors suggest that in specialized environments like a soccer pitch, a complex vocabulary introduces noise rather than discriminative detail. Furthermore, the use of global alignment (Needleman-Wunsch) proved crucial for capturing the complete "narrative" of an event from start to finish.

While the approach shows great promise, the $O(mn)$ computational complexity of the alignment algorithm remains a potential bottleneck for large-scale datasets. Future work will focus on optimizing these string kernels and expanding the methodology to a wider variety of event categories. By successfully marrying the simplicity of Bag-of-Words with the structural power of string kernels, this research provides a robust path forward for temporal video analysis.

Summary updated

Abstract

The recognition of events in videos is a relevant and challenging task of automatic semantic video analysis. At present one of the most successful frameworks, used for object recognition tasks, is the bag-of-words (BoW) approach. However this approach does not model the temporal information of the video stream. In this paper we present a method to introduce temporal information within the BoW approach. Events are modeled as a sequence composed of histograms of visual features, computed from each frame using the traditional BoW model. The sequences are treated as strings where each histogram is considered as a character. Event classification of these sequences of variable size, depending on the length of the video clip, are performed using SVM classifiers with a string kernel that uses the Needlemann-Wunsch edit distance. Experimental results, performed on two datasets, soccer video and TRECVID 2005, demonstrate the validity of the proposed approach.
BibTeX
@inproceedings{ballan2009video,
  author = {Lamberto Ballan and Marco Bertini and Alberto Del Bimbo and Giuseppe Serra},
  title = {{Video Event Classification Using Bag of Words and String Kernels}},
  booktitle = {ICIAP},
  year = {2009},
  doi = {10.1007/978-3-642-04146-4\_20},
}
Figure