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.
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.
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