Person Re-Identification by Common-Near-Neighbor Analysis

Wei Li, Masayuki Mukunoki, Yinghui Kuang, Yang Wu, Michihiko MinohIEICE Trans. Information and Systems 2014 · DOI

Abstract

Re-identifying individuals across disparate camera views is a critical challenge in visual surveillance. Traditional methods often struggle with the high intra-class variation and low inter-class differences inherent in real-world human imagery. We propose Common-Near-Neighbor Analysis (CNNA), a novel dissimilarity measure that leverages neighborhood-wise relative information. By utilizing the distribution of well-behaved samples to assist in identifying poorly-distributed outliers, CNNA ensures that intra-class dissimilarities remain smaller than inter-class dissimilarities within a learned discriminative space.

Introduction: The Re-ID Challenge

Person re-identification (Re-ID) is often described as a "needle in a haystack" problem. It involves identifying the same individual across non-overlapping camera views, a task complicated by two primary factors:

  1. Large Intra-class Variation: A single person's appearance can change drastically due to lighting, pose, or occlusions.
  2. Small Inter-class Variation: Different individuals often wear similar clothing, making them nearly indistinguishable to standard algorithms.

Traditional "point-wise" distance metrics—which calculate the direct mathematical distance between feature vectors—often fail when a sample is an outlier due to environmental factors. CNNA addresses this by shifting the focus from isolated points to the "neighborhood" of similar samples.

Methodology: Common-Near-Neighbor Modeling

The core of our approach is Common-Near-Neighbor Modeling (CNNM). Instead of a simple distance calculation between Image A and Image B, the system evaluates the rank of Image B within the top $n$ neighbors of Image A.

Figure 1: Illustration of rank-order lists and the fixed-number n concept used in neighborhood analysis.

Key Components

  • Symmetric Dissimilarity: This measure sums the rank orders of the top $n$ neighbors of one sample within the rank-order list of the other. This "borrows" the distribution strength of well-behaved samples to stabilize the identification of outliers.
  • Asymmetric Dissimilarity: Tailored for "single-shot" scenarios, this handles cases where the neighbor relationship is not reciprocal (e.g., Image A ranks Image B highly, but Image B does not rank Image A highly).
  • Metric Learning (OMRR): We utilize Optimizing Mean Reciprocal Ranking (OMRR) as a pre-processing step to "clean" the feature space, ensuring that initial distances are discriminative before neighborhood analysis is applied.
  • Feature Fusion: Robust signatures are created by combining color information (Weighted HSV Histograms) with texture and spatial data (Dense Sampled Color Histograms).

Experimental Evaluation

We evaluated CNNA on three benchmark datasets representing real-world challenges: VIPeR (viewpoint/lighting variations), ETHZ (crowded moving camera sequences), and i-LIDS (heavy occlusions in an airport).

Results and Insights

CNNA consistently outperformed state-of-the-art methods. On the VIPeR dataset, it achieved significantly higher recognition rates than traditional metric learning methods like KISSME or LMNN. The method proved exceptionally robust against occlusions in the i-LIDS dataset, where other algorithms often failed.

Figure 5: Qualitative comparison of various distance measures on synthetic data, showing how CNNA (CNNM) better preserves cluster structures.

A key insight is the importance of the "Fixed-number" $n$. We found that setting $n$ to roughly half the average number of images per person in the dataset yields optimal results. Qualitatively, as seen in Figure 5, the symmetric dissimilarity effectively "pushes" incorrect matches further away while "pulling" true matches to the top of the ranking, even when initial Euclidean distances are misleading.

Conclusion

CNNA provides a robust framework for person re-identification by utilizing neighborhood structures as anchors. While it introduces some computational complexity due to ranking requirements, its stability across diverse environmental challenges makes it a powerful tool for real-world surveillance. Future work will explore extending this neighborhood-wise perspective to multi-target human tracking in dense crowds.

Summary updated

BibTeX
@article{li2014person,
  author = {Wei Li and Masayuki Mukunoki and Yinghui Kuang and Yang Wu and Michihiko Minoh},
  title = {{Person Re-Identification by Common-Near-Neighbor Analysis}},
  journal = {IEICE Trans. Information and Systems},
  year = {2014},
  doi = {10.1587/transinf.2014edp7102},
}
Figure