A Fast Sub-Volume Search Method for Human Action Detection

Ping Guo, Zhenjiang Miao, Xiao–Ping Zhang, Zhe WangIEICE 2012 · DOI

Abstract

This paper discusses the task of human action detection, which requires not only classifying the type of action but also finding its spatial-temporal location in a video. The authors introduce two significant novelties: a new graph-based representation for the search space in a video and a novel sub-volume search method using Minimum Cycle detection. The proposed method maintains high detection accuracy while significantly reducing computational complexity. Evaluated on challenging datasets with cluttered backgrounds, the approach outperforms state-of-the-art methods in both Precision-Recall values and processing speeds.

Introduction

Human action detection is a two-fold challenge: identifying what action is occurring (classification) and determining where and when it happens (spatial-temporal localization). While classification is a relatively mature field, localization remains difficult in uncontrolled environments characterized by cluttered backgrounds, moving cameras, or occlusions.

Traditional approaches typically rely on human tracking or sliding window searches. Tracking is fast but often fails in messy environments. Sliding windows are robust but computationally expensive; searching for a 3D sub-volume (a cuboid in space-time) across a video has a complexity of $O(W^2H^2T^2)$. This paper aims to bridge this gap by searching the entire sub-volume space without the exhaustive cost of traditional methods.

Methodology

Graph-Based Video Representation

The core innovation is representing the video search space as a weighted directed graph (digraph). The authors map a sub-volume (a cuboid) to a cycle within this graph. A cuboid is defined by its edges and vertices; in the proposed digraph, nodes represent candidate locations for the edges, and arrows (edges) represent the vertices where these edges intersect.

Mapping a space-time cuboid to a cycle in a directed graph.

Weighting and Optimization

To identify the optimal sub-volume, the graph is weighted based on the similarity between the optical flow of the test video and a query template. The detection task is then transformed into a Minimum Cycle detection problem. The authors utilize an iterative approach based on the Bellman-Ford algorithm to efficiently find the cycle with the lowest weight, which corresponds to the most likely action location.

Computational Efficiency

By shifting the problem to graph theory, the search complexity drops from the quadratic $O(W^2H^2T^2)$ to approximately $O(uWHT)$, where $u$ is a small linear factor. This reduction makes the process significantly faster than traditional sliding windows or branch-and-bound techniques.

Key Results

The method was evaluated on the CMU Dataset (five actions in crowded backgrounds) and the MSR Action Dataset II (realistic, noisy scenarios). The proposed approach consistently outperformed existing techniques.

Comparison of Precision-Recall values and computational complexity on the CMU dataset.
  • Speed: On the CMU dataset, the search took approximately 25 seconds on a 2.83 GHz processor. On the MSR II dataset, total testing time was about 8 hours, nearly three times faster than competing branch-and-bound methods.
  • Accuracy: On the CMU dataset, the method achieved a precision of 0.9 at a recall of 0.2 and maintained a precision of 0.5 at a recall of 0.8, significantly higher than the 0.15 precision achieved by previous sliding window methods at the same recall level.

Conclusion

By framing spatial-temporal detection as a topological graph problem, the authors achieve a significant breakthrough in efficiency. The Minimum Cycle detection approach ensures that detected boundaries are consistent and closed while maintaining high accuracy. While the method currently relies on clean query templates and rigid cuboid geometry, it provides a robust foundation for future work in more flexible action detection models.

Summary updated

Abstract

This paper discusses the task of human action detection. It requires not only classifying what type the action of interest is, but also finding actions' spatial-temporal locations in a video. The novelty of this paper lies on two significant aspects. One is to introduce a new graph based representation for the search space in a video. The other is to propose a novel sub-volume search method by Minimum Cycle detection. The proposed method has a low computation complexity while maintaining a high action detection accuracy. It is evaluated on two challenging datasets which are captured in cluttered backgrounds. The proposed approach outperforms other state-of-the-art methods in most situations in terms of both Precision-Recall values and running speeds.
BibTeX
@inproceedings{guo2012fast,
  author = {Ping Guo and Zhenjiang Miao and Xiao–Ping Zhang and Zhe Wang},
  title = {{A Fast Sub-Volume Search Method for Human Action Detection}},
  booktitle = {IEICE},
  year = {2012},
  doi = {10.1587/transinf.e95.d.285},
}
Figure