Reranking论文笔记

最近做了一个ReID的项目，算是开始入门学习，中间学习、掌握的一些东西开始用博客记下来，也算是自己再梳理一遍。
论文：Re-ranking Person Re-identification with k-reciprocal Encoding

第一章 Abstract

第二章 Related Work

第三章 Proposed Aproach

一、Problem Definition

二、K-reciprocal Nearest Neighbors

一个Probe person：p，和一个gallery set: G
K-nearest neighbors: 在gallery set G中对p按距离顺序排列，取前k个。论文中用的是Mahalanobis distance（马哈拉诺比斯距离，协方差距离）
$N(p,k) = \{g_1^0,g_2^0,...,g_k^0\},|N(p,k)|=k.$N(p,k)={g10​,g20​,...,gk0​},∣N(p,k)∣=k.
K-reciprocal: 两者相互均在k-nearest neighbors中
$R(p,k) = \{ g_i | (g_i \in N(p,k) \land(p \in N(g_i,k)) \}$R(p,k)={gi​∣(gi​∈N(p,k)∧(p∈N(gi​,k))}

for gi in  N_p_k:
	if p in N_gi_k:
		k-reciprocal.append(gi) 

由于照明、姿势、视角、遮挡的变化，会导致一些positive image从k-nearest neighbors中踢出没有进入k-reciprocal nearest neighbors。
$R^*(p,k)\leftarrow R(p,k)\cup R(q, \frac 12k) \\[2ex] s.t. |R(p,k) \cap R(q, \frac 12k)| \ge \frac 23 |R(q, \frac 12k)|,\\[2ex] \forall q \in R(p, k)$R∗(p,k)←R(p,k)∪R(q,21​k)s.t.∣R(p,k)∩R(q,21​k)∣≥32​∣R(q,21​k)∣,∀q∈R(p,k)
对k-reciprocal nearest neighbors 计算每个元素的1/2k的k-reciprocal nearest neighbors 然后加入构成k-expansion-reciprocal nearest neighbors。
这个结果并不是用于当做top rank images, 而是作为计算p和gallery之间距离的一个基础。

Jaccard Distance

得到这两个集合的交集和并集是非常time-consuming的，而且当每对图片的 jaccard distance都要计算时，这个挑战更大。另一种可替代的方法是将 neighbor set编码成更加简单但是等价的向量。
$V_p = [V_{p,g1},V_{p,g2},...,V_{p,gN}]$Vp​=[Vp,g1​,Vp,g2​,...,Vp,gN​]
$V_{p,gi} = \begin{cases} 1, & \text{ if $g^i \in R^* (p,k)$} \\ 0, & \text{otherwise} \end{cases}$Vp,gi​={1,0,​ if gi∈R∗(p,k)otherwise​
因此：
$|R^*(p,k) \cap R^*(g_i,k)| = ||min(v_p,v_gi)||_1 \\[2ex] |R^*(p,k) \cup R^*(g_i,k)| = ||max(v_p,v_gi)||_1$∣R∗(p,k)∩R∗(gi​,k)∣=∣∣min(vp​,vg​i)∣∣1​∣R∗(p,k)∪R∗(gi​,k)∣=∣∣max(vp​,vg​i)∣∣1​
$d_J(p,g_i) = 1 - \frac{\sum_{j=1}^Nmin(\nu_{p,g_i},\nu_{g_i,g_j})} {\sum_{j=1}^N max(\nu_{p,g_i},\nu_{g_i,g_j})}$dJ​(p,gi​)=1−∑j=1N​max(νp,gi​​,νgi​,gj​​)∑j=1N​min(νp,gi​​,νgi​,gj​​)​

Local Query Expansion

考虑到，相同class的图片有相似的feature。
$\nu_p = \frac { 1 } {N(p,k)} \sum_{g_i \in N(p, k)}\nu_{g_i}$νp​=N(p,k)1​gi​∈N(p,k)∑​νgi​​

Final Distance

$d^*(p,g_i) = (1 - \lambda)d_J(p,g_i) + \lambda d(p,gi)$d∗(p,gi​)=(1−λ)dJ​(p,gi​)+λd(p,gi)

Complexity Analysis

计算prop和gallery成对距离复杂度为，最终排序复杂度