Abstract
Robust object tracking is required by many vision applications, and it will be useful for the motion analysis of moving object if we can not only track the object, but also make clear the corresponding relation of each part between consecutive frames. For this purpose, we propose a new method for moving object extraction and tracking based on the exclusive block matching. We build a cost matrix consisting of the similarities between the current frame's and the previous frame's blocks and obtain the corresponding relation by solving one-to-one matching as linear assignment problem. In addition, we can track the trajectory of occluded blocks by dealing with multi-frames simultaneously.
Introduction
Tracking moving objects in video sequences is a fundamental task in computer vision. While identifying a moving object is common, understanding the precise movement of its constituent parts remains challenging. Traditional methods often encounter specific limitations:
- Background subtraction identifies motion but lacks part-to-part correspondence.
- Mean-Shift and Particle Filters focus on global object states, ignoring internal dynamics.
- Optical Flow provides dense detail but is sensitive to low-texture regions and rapid motion.
- Feature-based methods (e.g., SIFT) often fail to provide enough keypoints for comprehensive object tracking.
This paper introduces "Exclusive Block Matching," a technique designed to maintain precise part-level correspondences by treating tracking as a global optimization problem.
Methodology
The core innovation lies in shifting from local searches to a global Linear Assignment Problem (LAP). Instead of allowing multiple blocks to compete for the same destination, the algorithm ensures a one-to-one (exclusive) mapping using the Hungarian method to minimize total cost.
Matrix and Multi-Frame Expansion
To accommodate real-world scenarios where objects appear, disappear, or are occluded, the cost matrix is expanded with "dummy" rows and columns representing Background, Creation, and Vanishment. Furthermore, to handle temporary occlusions, the system considers multiple previous frames ($T$).
Efficiency through State Transitions
A significant challenge in global optimization is computational cost. The authors implement Restriction of State Transition (RST), defining seven block states (e.g., MovingObject, StaticObject, Occlusion). By applying spatial constraints—limiting how far a block can move between frames—the dense cost matrix becomes sparse, drastically reducing processing time.
Evaluation and Results
The method was tested on both computer-generated (CG) sequences and real-world office footage.
- Accuracy: In controlled CG tests involving rotation and scaling, the proposed method achieved an Accuracy Rate (AR) of 81-85%, significantly outperforming standard block matching (50-60%).
- Performance: RST proved essential for real-time viability. Processing time per frame dropped from ~45 seconds to under 1 second (0.12 - 0.85s).
- Robustness: The system maintained trajectories during complex maneuvers where feature-based methods typically fail due to insufficient keypoints.
Spatio-Temporal Tracking Analysis
The multi-frame approach effectively treats tracking as a 3D problem in spatio-temporal space. This allows the system to maintain object identity even when parts are temporarily hidden or change size.
Conclusion
Exclusive Block Matching provides a robust framework for tracking object parts by enforcing global one-to-one correspondences. While highly effective, the method currently faces challenges with the "aperture problem" in uniform-colored regions. Future work will explore incorporating shape similarity and connectivity constraints to improve performance in low-contrast environments.
Summary updated