1 计算某张图像的K-reciprocal Nearest Neighbor

K-reciprocal重排序是ReID任务中用来提高检索效果的一种常用手段。一般的行人检索通常是根据行人特征，选取query图像(记为\(p\))的KNN作为topK，记为\(g = [g_1, g_2, ..., g_k]\)。虽然g集合中的图像都是p的K近邻，但对g中的某些图像，p可能不在它们的K近邻。如果某张图像和p互为K近邻，显然它更有可能和p代表同一个行人。因此，p的K-reciprocal nearest neighbor(\(\mathcal{R}(p, k)=\left\{g_{i} \mid\left(g_{i} \in N(p, k)\right) \wedge\left(p \in N\left(g_{i}, k\right)\right)\right\}\))比p的K nearest neighbor(\(N(p, k)=\left\{g_{1}^{0}, g_{2}^{0}, \ldots, g_{k}^{0}\right\},|N(p, k)|=k\))是更好的检索结果。

但是我们应该注意到，由于光照、姿态的影响，有些p的positive samples没在p的KNN中，如何在\(\mathcal{R}(p, k)\)的基础上召回这些positive samples呢？论文中给出的一种扩张方法为：

\[\begin{aligned} &\mathcal{R}^{*}(p, k) \leftarrow \mathcal{R}(p, k) \cup \mathcal{R}\left(q, \frac{1}{2} k\right) \\ &\text { s.t. }\left|\mathcal{R}(p, k) \cap \mathcal{R}\left(q, \frac{1}{2} k\right)\right| \geqslant \frac{2}{3}\left|\mathcal{R}\left(q, \frac{1}{2} k\right)\right| \\ &\forall q \in \mathcal{R}(p, k) \end{aligned}\]

像上面的1/2和2/3都是超参。对p的K-reciprocal NN中的每张图像，我们都去找它的1/2K-reciprocal NN(记为\(\mathcal{R}(q, 1/2k)\))，如果该集合和\(\mathcal{R}(p, k)\)交集的元素超过\(\mathcal{R}(p, k)\)中元素的2/3，那么将集合\(\mathcal{R}(q, 1/2k)\)中新的元素加入进来。

注意：经过这样处理，\(\mathcal{R}^{*}(p, k)\)中的元素个数是不确定的

2 计算两张图像的Jaccard距离

经过第一部分，我们可以得到\(\mathcal{R}^{*}(p, k)、\mathcal{R}^{*}(g_1, k)、\mathcal{R}^{*}(g_2, k)...\mathcal{R}^{*}(g_N, k)\)。之前只是利用\(p\)和\(g_i\)的行人特征的余弦距离来排序，现在我们增加一个新的距离：

\[d_{J}\left(p, g_{i}\right)=1-\frac{\left|\mathcal{R}^{*}(p, k) \cap \mathcal{R}^{*}\left(g_{i}, k\right)\right|}{\left|\mathcal{R}^{*}(p, k) \cup \mathcal{R}^{*}\left(g_{i}, k\right)\right|} \]

但是直接求集合的交、并会比较耗时。一种更高效的方式是将\(\mathcal{R}^{*}(p, k)\)编码成一个N维向量，我们去看p的KNN中有哪些元素在\(\mathcal{R}^{*}(p, k)\)里。

\[\mathcal{V}_{p, g_{i}}= \begin{cases}\mathrm{e}^{-d\left(p, g_{i}\right)} & \text { if } g_{i} \in \mathcal{R}^{*}(p, k) \\ 0 & \text { otherwise }\end{cases} \]

最终的Jaccard距离计算公式为：

\[d_{J}\left(p, g_{i}\right)=1-\frac{\sum_{j=1}^{N} \min \left(\mathcal{V}_{p, g_{j}}, \mathcal{V}_{g_{i}, g_{j}}\right)}{\sum_{j=1}^{N} \max \left(\mathcal{V}_{p, g_{j}}, \mathcal{V}_{g_{i}, g_{j}}\right)} \]

最后，我们将两张图像的Jaccard距离和余弦距离的加权和作为最终的排序指标，进行重排。

相关代码实现

https://github.com/michuanhaohao/reid-strong-baseline/blob/3da7e6f03164a92e696cb6da059b1cd771b0346d/utils/re_ranking.py