Introduction

problem:

• relie on appearance alone
• inter-camera variations: lighting orientation object pose

Existing work:

• feature sets as template -> matching using template(direct distance measure)
  • Feature sets: color/texture/structure layout
  • Distance measure: histogram based Bhattacharyya distance/ K-nearest Neighbour/ L1-Norm/dis measure of relative proportions of col
  • Problem: overlap
    • Adaboost => sift features | overlaps => feature across indivisual space

Overview:

• ranking: Boosting / SVM
  • Boosting (similar drawbacks as Adaboost)
  • RankSVM learning in a higher dimensional feature space
    • scalability problem => slow
• primal-based RankSVM (PRSVM)
  • samples grows -> negative samples grows non-linearly -> memory consumption unmanageable
  • Propose Ensemble RankSVM => boosting on PRSVM

Ranking People for Re-Idef

relevance rank: \(\lambda = {r_1,r_2,...,r_\rho}\), where \(r_\rho \succ r_{\rho-1} \succ ... \succ r_1\)

dataset: \(X = \{ (x_i,y_i) \}^m_{i=1}\), relavant feature vector \(d^+_i\), irrelevant \(d^-_i\), \(m^- = m - m^+ -1\) , \(m^+ << m^-\)

Goal: ranking function \(\delta\) => \(\delta(x_i,x^+_{i,j})>\delta(x_i,x^-_{i,j})\)

Support Vector machine

Score: \(\delta(x_i,x_{i,j}) = w^T |x_i-x_{i,j}|\)

Absolute difference vector: \(|x_i-x_{i,j}|\)

Pairwise relevant difference vector: \(P = {\hat{x}^+_s,\hat{x}^-_s}\)

objective function(min): \(\frac{1}{2}||w||^2 + C \sum^{|P|}_{s=1}\xi_s\) , s.t. \(w^T(\hat{x}^+_s-\hat{x}^-_s) \geq 1 - \xi_s, \xi_s >0\)

Chappelle and KeerthiL=: \(w= arg\min_{w}\frac{1}{2}||w||^2 + C \sum_{s=1}^{|P|}\ell(0,1 - w^T(x^+_s - x^-_s))^2\)

• Newton Optimisation
• Sparse matrix

Ensemble RankSVM

Strong ranker \(w_{opt}\) <= weak ranker \(w_{opt} = \sum^N_i \alpha_i \cdotp w_i\)

Weak rankers learning:

• divide into non overlapping group \(Z_i\)(contains equal number)
• add duplicate(not completely separate) to avoid too weak => \(\tilde{Z_i} = Z_i \bigcup O_i\), \(O_i\) is picked randonly from \(Z-Z_i\), and \(|Z_i|=|O_i|\)
• Train using PRSVM
• Learning \(\alpha_i\)
  • select best weak ranker: \(k_t=arg\min_{i} \sum^{|P|}_{s=1}D^s_t \cdotp I_{w^T_i(\hat{x}^+_s-\hat{x}^-_s)} \geq 0\)
  • \(D\) => weight of pairwise difference vectors at t step \(\sum D = 1\), \(I\) => boolean function
  • \(D^s_{t+1}=F^{-1}D^s_t \cdotp \exp^{\alpha_t \cdotp (w^T_{k_t}(\hat{x}^-_s - \hat{x}^+_s))}\)
  • \(F\) normalizer => \(\sum D = 1\), initial \(D^s_1=\frac{1}{|P|}\)
  • \(\alpha_t = 0.5 \cdotp log \frac{1+r}{1-r}\), \(r=\sum^{|P|}_{s=1}D^s_t(w^T_{k_t}(\hat{x}^+_s - \hat{x}^-_s))\)
  • normalize \(w_i\) => \(w^T_i(\hat{x}^+_s-\hat{x}^-_s) \in [-1,+1]\)