Re-Ranking

Table of Contents

1. $N(p,k)$
2. $R$
3. ${\mathcal{R}}^{\ast }$
4. Jaccard距离
5. ${\mathcal{V}}_{p,g_j}$
6. 局部查询扩展

$N(p,k)$

1. N ( p , k ) = { g 1 0 , g 2 0 , . . . , g k 0 } , ∣ N ( p , k ) ∣ = k 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
2. $N(p,k)$ 是查询图像 $p$ 的 $k$ 最近邻图片集合。

$R$

1. R ( p , k ) = { ( g i ∈ N ( p , k ) ) ∩ ( p ∈ N ( g i , k ) ) } \mathcal{R}(p, k) = \{(g_i \in N(p, k)) \cap (p \in N(g_i, k))\} R(p,k)={(gi​∈N(p,k))∩(p∈N(gi​,k))}
   $p$ 和 $g_i$ 互为 $k$ 最近邻
2. $\mathcal{R}(p,k)$ 是以 $p$ 作为查询图像，与 $p$ 互为 $k$ 最近邻的图片集合。

${\mathcal{R}}^{\ast }$

1. 由于照明、姿态、视图、和遮挡的变化，正样本可能不在 $N(p,k)$ 中，进而不在 $\mathcal{R}(p,k)$ 中。

正样本图像可能被从 $k$ -最近邻中排除，并且随后不被包括在 $k$ -相互最近邻中。为了解决这个问题，我们根据以下条件将 $\mathcal{R}(p,k)$ 中每个候选项的 $\frac{1}{2}k$ -相互最近邻增量地添加到更鲁棒的集合 ${\mathcal{R}}^{\ast }(p,k)$ 中：

1. ${\mathcal{R}}^{\ast }\leftarrow \mathcal{R}(p,k)\cup \mathcal{R}(q,\frac{1}{2}k)$
2. $s.t.|\mathcal{R}(p,k)\cap \mathcal{R}(q,\frac{1}{2}k)|\ge \frac{2}{3}|\mathcal{R}(q,\frac{1}{2}k)|$
3. $\forall q\in \mathcal{R}(p,k)$

Jaccard距离

1. $p$ 和 $g_i$ 的相似性度量取决于 $p$ 和 $g_i$ 各自的邻居。
2. $$d_J(p,g_i)=1-\frac{|{\mathcal{R}}^{\ast }(p,k)\cap {\mathcal{R}}^{\ast }(g_i,k)|}{|{\mathcal{R}}^{\ast }(p,k)\cup {\mathcal{R}}^{\ast }(g_i,k)|}(5)$$

${\mathcal{V}}_{p,g_j}$

1. $${\mathcal{V}}_p=[{\mathcal{V}}_{p,g_1},{\mathcal{V}}_{p,g_2},...,{\mathcal{V}}_{p,g_N}]$$

2. V p , g i = { 1 i f   g i ∈ R ∗ ( p , k ) 0 o t h e r w i s e .   ( 6 ) \mathcal{V}_{p, g_i} = \left\{

   1if gi∈R∗(p,k)0otherwise." role="presentation">10if gi∈R∗(p,k)otherwise.$$\begin{array}{ll}1& if{g}_i\in {\mathcal{R}}^{\ast }(p,k)\\ 0& otherwise.\end{array}$$
   \right. \ (6) Vp,gi​​={10​if gi​∈R∗(p,k)otherwise.​ (6)
   V p , g i = { e − d ( p , g i ) i f   g i ∈ R ∗ ( p , k ) 0 o t h e r w i s e .   ( 7 ) \mathcal{V}_{p, g_i} = \left\{
   e−d(p,gi)if gi∈R∗(p,k)0otherwise." role="presentation">e−d(p,gi)0if gi∈R∗(p,k)otherwise.$$\begin{array}{ll}{e}^{-d(p,g_i)}& if{g}_i\in {\mathcal{R}}^{\ast }(p,k)\\ 0& otherwise.\end{array}$$
   \right. \ (7) Vp,gi​​={e−d(p,gi​)0​if gi​∈R∗(p,k)otherwise.​ (7)
   1. 如果 ${\mathcal{V}}_{p,g_i}$ 按照公式6中的定义，公式5和公式10是等价的。
   2. 如果 ${\mathcal{V}}_{p,g_i}$ 按照公式7中的定义，公式5和公式10是近似等价的。

3. $g_i$ 是图集中的图片， $p$ 是查询图像。

4. $$|{\mathcal{R}}^{\ast }(p,k)\cap {\mathcal{R}}^{\ast }(g_i,k)|=\Vert \min ({\mathcal{V}}_p,{\mathcal{V}}_{g_i}){\Vert }_1(8)$$

5. $$|{\mathcal{R}}^{\ast }(p,k)\cup {\mathcal{R}}^{\ast }(g_i,k)|=\Vert \max ({\mathcal{V}}_p,{\mathcal{V}}_{g_i}){\Vert }_1(9)$$
   L1范数是指向量中各个元素绝对值之和

6. $$d_J(p_{,}{g}_i)=1-\frac{{\sum }_{j=1}^N\min ({\mathcal{V}}_{p,g_j},{\mathcal{V}}_{g_i,g_j})}{{\sum }_{j=1}^N\max ({\mathcal{V}}_{p,g_j},{\mathcal{V}}_{g_i,g_j})}(10)$$

   如果图像 $g_j$ 既是 $p$ 的 $k$ 相互最近邻，又是 $g_i$ 的 $k$ 相互最近邻，
   则 $\min ({\mathcal{V}}_{p,g_j},{\mathcal{V}}_{g_i,g_j})=1,\max ({\mathcal{V}}_{p,g_j},{\mathcal{V}}_{g_i,g_j})=1$ 。

局部查询扩展

1. ${\mathcal{V}}_p=\frac{1}{|N(p,k)|}{\sum }_{g_i\in N(p,k)}{\mathcal{V}}_{g_i}(11)$
2. $p$ 和其它节点的距离取决于 $p$ 的邻居和其它节点的距离。

#!/usr/bin/env python2/python3
# -*- coding: utf-8 -*-
"""
Source: https://github.com/zhunzhong07/person-re-ranking
Created on Mon Jun 26 14:46:56 2017
@author: luohao
Modified by Houjing Huang, 2017-12-22.
- This version accepts distance matrix instead of raw features.
- The difference of `/` division between python 2 and 3 is handled.
- numpy.float16 is replaced by numpy.float32 for numerical precision.
CVPR2017 paper:Zhong Z, Zheng L, Cao D, et al. Re-ranking Person Re-identification with k-reciprocal Encoding[J]. 2017.
url:http://openaccess.thecvf.com/content_cvpr_2017/papers/Zhong_Re-Ranking_Person_Re-Identification_CVPR_2017_paper.pdf
Matlab version: https://github.com/zhunzhong07/person-re-ranking
API
q_g_dist: query-gallery distance matrix, numpy array, shape [num_query, num_gallery]
q_q_dist: query-query distance matrix, numpy array, shape [num_query, num_query]
g_g_dist: gallery-gallery distance matrix, numpy array, shape [num_gallery, num_gallery]
k1, k2, lambda_value: parameters, the original paper is (k1=20, k2=6, lambda_value=0.3)
Returns:
  final_dist: re-ranked distance, numpy array, shape [num_query, num_gallery]
"""
from __future__ import absolute_import
from __future__ import print_function
from __future__ import division

__all__ = ['re_ranking']

import numpy as np
import pudb
from pudb import set_trace


def re_ranking(q_g_dist, q_q_dist, g_g_dist, k1=20, k2=6, lambda_value=0.3):
    original_dist = np.concatenate(
      [np.concatenate([q_q_dist, q_g_dist], axis=1),
       np.concatenate([q_g_dist.T, g_g_dist], axis=1)], axis=0)
    original_dist = np.power(original_dist, 2).astype(np.float32)
    original_dist = np.transpose(1. * original_dist/np.max(original_dist, axis =0))
    v = np.zeros_like(original_dist).astype(np.float32)
    initial_rank = np.argsort(original_dist).astype(np.int32)

    query_num = q_g_dist.shape[0]
    all_num = q_g_dist.shape[0] + q_g_dist.shape[1]

    for i in range(all_num):
        # k-reciprocal neighbors
        # i的前k+1个邻居的索引
        forward_k_neigh_index = initial_rank[i,:k1+1]
        # i的前k+1个邻居的索引的前k+1个邻居的索引
        backward_k_neigh_index = initial_rank[forward_k_neigh_index,:k1+1]
        fi = np.where(backward_k_neigh_index==i)[0]
        k_reciprocal_index = forward_k_neigh_index[fi]
        k_reciprocal_expansion_index = k_reciprocal_index
        for j in range(len(k_reciprocal_index)):
            candidate = k_reciprocal_index[j]
            candidate_forward_k_neigh_index = initial_rank[candidate,:int(np.around(k1/2.))+1]
            candidate_backward_k_neigh_index = initial_rank[candidate_forward_k_neigh_index,:int(np.around(k1/2.))+1]
            fi_candidate = np.where(candidate_backward_k_neigh_index == candidate)[0]
            candidate_k_reciprocal_index = candidate_forward_k_neigh_index[fi_candidate]
            # 对应公式4
            if len(np.intersect1d(candidate_k_reciprocal_index,k_reciprocal_index))> 2./3*len(candidate_k_reciprocal_index):
                k_reciprocal_expansion_index = np.append(k_reciprocal_expansion_index,candidate_k_reciprocal_index)

        # 去除重复的元素
        k_reciprocal_expansion_index = np.unique(k_reciprocal_expansion_index)
        # 对应公式7
        weight = np.exp(-original_dist[i,k_reciprocal_expansion_index])
        # 归一化
        v[i,k_reciprocal_expansion_index] = 1.*weight/np.sum(weight)
        # v[i, j]: 如果i和j是k相互近邻，则v[i, j] = 1, 否则v[i, j] = 0
    original_dist = original_dist[:query_num,]

    if k2 != 1:
        v_q = np.zeros_like(v,dtype=np.float32)
        for i in range(all_num):
            # 对应公式11 多行平均
            v_q[i,:] = np.mean(v[initial_rank[i,:k2],:],axis=0)
            # i和其他节点的距离取决于i的邻居和其它节点的距离
        v = v_q
        del v_q
    del initial_rank

    inv_index = []
    for i in range(all_num):
        # v矩阵中每一列不为0的行索引
        inv_index.append(np.where(v[:,i] != 0)[0])

    jaccard_dist = np.zeros_like(original_dist, dtype=np.float32)

    for i in range(query_num):
        min_dist = np.zeros(shape=[1, all_num], dtype=np.float32)
        # i的前k个相互最近邻
        ind_non_zero = np.where(v[i,:] != 0)[0]
        ind_images = []
        # i的相互最近邻的相互最近邻的行索引
        ind_images = [inv_index[ind] for ind in ind_non_zero]
        for j in range(len(ind_non_zero)):
            # j是i的第j个邻居
            # 计算q_i和g_j的距离
            min_dist[0,ind_images[j]] += np.minimum(
                # 0: 第0维
                v[i, ind_non_zero[j]],
                v[ind_images[j], ind_non_zero[j]])
            # 这里的实现和论文中描述的公式不一致
            # 这里计算的含义是i和3的距离等于j1和3的距离加上j2和3的距离
        # 公式10中计算的是p和g_i的距离，这里计算的是p和前k个相互最近邻的距离
        jaccard_dist[i] = 1-min_dist/(2.-min_dist)

    final_dist = lambda_value* original_dist + (1-lambda_value) * jaccard_dist
    del original_dist
    del v
    del jaccard_dist
    final_dist = final_dist[:query_num,query_num:]
    return final_dist

# 1. 计算的出发点是构建query和gallery的距离。
# v中d(i, j)不等于d(j, i)

# 2. 对v要极其的熟悉
# v[i, j]标志i和j是否是k相互最近邻

# 1. 对np.where()要极其熟悉
# np.where返回的是元组
# np.where(matrix==1)[0] 返回的是矩阵中元素1的行号
# np.where(vector==1)[0] 返回的是向量中元素1的索引


def re_ranking2(q_g_dist, q_q_dist, g_g_dist, k1=20, k2=6, lambda_value=0.3):
    original_dist = np.concatenate(
      [np.concatenate([q_q_dist, q_g_dist], axis=1),
       np.concatenate([q_g_dist.T, g_g_dist], axis=1)], axis=0)
    original_dist = np.power(original_dist, 2).astype(np.float32)
    original_dist = np.transpose(1. * original_dist/np.max(original_dist, axis =0))
    v = np.zeros_like(original_dist).astype(np.float32)
    initial_rank = np.argsort(original_dist).astype(np.int32)

    query_num = q_g_dist.shape[0]
    all_num = q_g_dist.shape[0] + q_g_dist.shape[1]

    for i in range(all_num):
        # k-reciprocal neighbors
        # i的前k+1个邻居的索引
        forward_k_neigh_index = initial_rank[i,:k1+1]
        # i的前k+1个邻居的索引的前k+1个邻居的索引
        backward_k_neigh_index = initial_rank[forward_k_neigh_index,:k1+1]
        fi = np.where(backward_k_neigh_index==i)[0]
        k_reciprocal_index = forward_k_neigh_index[fi]
        k_reciprocal_expansion_index = k_reciprocal_index
        for j in range(len(k_reciprocal_index)):
            candidate = k_reciprocal_index[j]
            candidate_forward_k_neigh_index = initial_rank[candidate,:int(np.around(k1/2.))+1]
            candidate_backward_k_neigh_index = initial_rank[candidate_forward_k_neigh_index,:int(np.around(k1/2.))+1]
            fi_candidate = np.where(candidate_backward_k_neigh_index == candidate)[0]
            candidate_k_reciprocal_index = candidate_forward_k_neigh_index[fi_candidate]
            # 对应公式4
            if len(np.intersect1d(candidate_k_reciprocal_index,k_reciprocal_index))> 2./3*len(candidate_k_reciprocal_index):
                k_reciprocal_expansion_index = np.append(k_reciprocal_expansion_index,candidate_k_reciprocal_index)

        # 去除重复的元素
        k_reciprocal_expansion_index = np.unique(k_reciprocal_expansion_index)
        # 对应公式7
        weight = np.exp(-original_dist[i,k_reciprocal_expansion_index])
        # 归一化
        v[i,k_reciprocal_expansion_index] = 1.*weight/np.sum(weight)
        # v[i, j]: 如果i和j是k相互近邻，则v[i, j] = 1, 否则v[i, j] = 0
    original_dist = original_dist[:query_num,]

    if k2 != 1:
        v_q = np.zeros_like(v,dtype=np.float32)
        for i in range(all_num):
            # 对应公式11 
            v_q[i,:] = np.mean(v[initial_rank[i,:k2],:],axis=0)
            # 多行平均：i和其他节点的距离取决于i的邻居和其它节点的距离
        v = v_q
        del v_q
    del initial_rank

    jaccard_dist = np.zeros_like(original_dist, dtype=np.float32)

    for i in range(query_num):
        min_dist = np.zeros(shape=[1, all_num], dtype=np.float32)
        ind_non_zero = np.where(v[i,:] != 0)[0]
        for j in range(len(ind_non_zero)):
            # 对应公式10
            min_dist[0,j] = np.sum(np.minimum(v[i, :], v[j, :]))
        jaccard_dist[i] = 1-min_dist/(2.-min_dist)

    final_dist = lambda_value* original_dist + (1-lambda_value) * jaccard_dist
    del original_dist
    del v
    del jaccard_dist
    final_dist = final_dist[:query_num,query_num:]
    return final_dist


if __name__ == "__main__":
    q_g_dist = np.random.rand(5, 10)
    q_q_dist = np.random.rand(5, 5)
    g_g_dist = np.random.rand(10, 10)
    f1 = re_ranking(q_g_dist, q_q_dist, g_g_dist, k1=5, k2=3, lambda_value=0.3)
    f2 = re_ranking2(q_g_dist, q_q_dist, g_g_dist, k1=5, k2=3, lambda_value=0.3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202