Abstract
Person re-identification (re-ID) is a critical task in multi-camera surveillance, yet most existing systems rely on individual algorithms that may struggle with specific environmental variations. This paper presents SHaPE (Shortest Hamiltonian Path Estimation), a novel unsupervised framework that treats re-ID as a graph-theoretic consensus problem. By mapping similarity scores from multiple algorithms into a "Score Distance Graph," the ranking process is modeled as finding the Shortest Hamiltonian Path. Through a two-step optimization process involving Greedy Nearest Node Search (GNNS) and Ant Colony Optimization (ACO), SHaPE effectively aggregates disparate model outputs. Experimental results on benchmark datasets demonstrate that SHaPE consistently outperforms individual state-of-the-art models and existing fusion techniques.
Introduction
The task of person re-identification involves identifying the same individual across non-overlapping camera views. While numerous feature descriptors and distance metrics have been proposed, the challenge of robustly combining multiple algorithms remains. Simple score averaging often fails due to the diverse distributions and ranges of different models. SHaPE addresses this by seeking a mathematically sound consensus ranking through graph theory.
Methods
The SHaPE framework operates in two primary stages: graph mapping and path optimization.
- Score Distance Graph Construction: Each gallery image is represented as a vertex in a fully connected graph. For a set of re-ID algorithms, each vertex is assigned an attribute vector of similarity scores. Edge weights between vertices are calculated using the Mahalanobis distance, which accounts for variances and correlations between different algorithms' score distributions, effectively normalizing the "opinions" of each model.
- Ranking as a Pathfinding Problem: The optimal ranking is conceptualized as a trajectory through similarity space. Specifically, it is modeled as the Shortest Hamiltonian Path—a path starting at the most likely match and visiting every other image exactly once in order of decreasing similarity.
- Two-Step Optimization: To find this path, the system first employs a Greedy Nearest Node Search (GNNS) to establish an initial rough ranking. This is followed by Ant Colony Optimization (ACO), where virtual "ants" traverse the graph to refine the path globally, overcoming the sub-optimality of local greedy decisions.
Experimental Results
The performance of SHaPE was evaluated on three standard benchmark datasets: VIPeR, CUHK01, and CUHK03. These datasets present various challenges, including viewpoint changes, illumination variations, and realistic errors from automated pedestrian detectors.
As shown in the CMC curves, SHaPE consistently achieves higher re-identification rates across all ranks compared to individual base algorithms (e.g., SDC_ocsvm, SDALF) and other fusion methods (e.g., l-UPPSF). On the VIPeR dataset, SHaPE achieved a Rank-1 accuracy of 34.26%, a significant improvement over the best individual algorithm's 23.78% and the best previous fusion method's 30.35%.
Discussion and Conclusion
The success of SHaPE highlights that ranking in re-ID can be effectively treated as a spatial trajectory problem. Its unsupervised nature allows it to find consensus without requiring labeled training data for fusion weights. While the ACO refinement step adds computational complexity, it is essential for achieving global optimality; the authors demonstrated that the initial GNNS estimate was significantly less accurate than the final refined path. Future work may explore the application of this graph-theoretic consensus approach to other multi-metric decision-making problems beyond person re-identification.
Summary updated