Abstract
This paper presents a novel approach to moving object extraction and tracking by framing it as a global optimization problem. By utilizing "Exclusive Block Matching" formulated as a linear assignment problem (LAP), the method effectively addresses the aperture problem and maintains tracking continuity through temporary occlusions. The inclusion of multi-frame lookback and virtual states for background and object creation allows for robust performance in dynamic real-world environments.
Introduction
Traditional object tracking methods often struggle with a fundamental trade-off. High-level approaches like Mean-Shift or Particle Filters track object centroids effectively but lose internal structural details. Conversely, low-level methods like Optical Flow provide fine-grained pixel data but are highly susceptible to the aperture problem. This occurs when blocks of pixels move across uniform regions, leading to ambiguous matches and erratic motion vectors. Furthermore, standard two-frame comparisons fail during temporary occlusions or when the background is revealed.
Methodology: Exclusive Block Matching
The core innovation of this work is the shift from local "best-match" searches to a global "optimal-set" matching strategy.
Linear Assignment and Exclusivity
Instead of allowing multiple source blocks to map to the same destination—a common cause of "clumping" in traditional methods—the authors enforce a one-to-one (exclusive) mapping. This is modeled as a Linear Assignment Problem (LAP) and solved using the Munkres (Hungarian) algorithm to minimize the total global cost of movement across the entire frame.
Matrix Expansion for Real-World Dynamics
To account for objects entering or leaving the scene, the cost matrix is expanded with "virtual" rows and columns representing Background, Creation, and Vanishment. This allows the algorithm to "assign" a block to the background if no suitable moving match is found, or to recognize a new object appearing without forcing it to match a previous block.
Multi-frame Lookback and Occlusion Handling
To handle occlusions, the system does not limit its search to the immediate previous frame ($t-1$). The cost matrix is expanded to include blocks from up to four previous frames ($t-2, t-3, t-4$).
As shown in Figure 1, this temporal depth allows the system to "re-connect" a trajectory even if an object disappears for several frames. If a block is occluded at $t=3$, it can be matched directly from $t=2$ to its reappearance at $t=4$ or $t=5$.
Figure 4 illustrates the technical implementation of this lookback. The current frame Curr(t) is matched against a composite set of previous states, background, and creation possibilities, ensuring the most globally consistent path is chosen even across time gaps.
Key Insights
- Exclusivity as a Regularizer: Forcing unique matches preserves the spatial structure of objects, preventing the "warping" often seen in Lucas-Kanade or Horn-Schunck methods.
- Contextual Histograms: To improve matching accuracy for small blocks, the authors use "neighborhood signatures" by incorporating HSV histogram data from the eight surrounding blocks.
Results
The method was evaluated on both synthetic CG data and real-world video sequences.
- Qualitative Performance: The proposed method produced significantly cleaner, parallel motion vectors compared to standard optical flow, avoiding unnatural flows caused by background interference.
- Occlusion Recovery: The system successfully maintained object identity through full occlusions.
- Efficiency: Processing averaged approximately 1 second per frame on a 3.0 GHz PC. While not yet real-time, the authors suggest that sparse-matrix optimizations and hardware acceleration could bridge this gap.
Conclusion
Exclusive Block Matching provides a robust framework for tracking by treating motion as a global assignment problem. By integrating multi-frame temporal data and virtual state transitions, the method overcomes the limitations of local search strategies, particularly in the presence of occlusions and the aperture problem. Future work will focus on incorporating shape similarity constraints and optimizing computational speed for real-time applications.
Summary updated