Re-ranking Person Re-identification with k-reciprocal Encoding 重排序算法解析

論文：

Re-ranking Person Re-identification with k-reciprocal Encoding

代碼：

https://github.com/layumi/Person_reID_baseline_pytorch/blob/master/re_ranking.py

3.提出的方法

3.1 問題定義

給定probe person 

和gallery set

,可以度量它們的馬氏距離：

這裡

和

是特征向量，M是半正定矩陣。我們可以根據這個距離對p和G排序，距離從小到大排列：

我們的目标是對這個初始排序清單重新排序，使得更多的正樣本出現在清單的前段。

3.2 K-reciprocal Nearest Neighbors

首先，定義k-nearest neighbors（k-nn），即排序清單的前k個樣本：

接着，定義k-reciprocal nearest neighbors（k-rnn），簡單地說就是滿足“

和

都在對方的k-nn清單裡”這一條件的

的集合：

然而，由于光照、姿态、視角等一系列變化，正樣本可能會被排除到k-nn清單外，是以我們定義了一個更魯棒的k-rnn集合：

上式的意思是，對于原本的集合R(p,k)中的每一個樣本q，找到它們的k-rnn集合R(q,k/2)，對于重合樣本數達到一定條件的，則将其并入R(p,k).通過這種方式，将原本不在R(p,k)集合中的正樣本重新帶回來。文中給了一個例子來說明這一過程，如下圖所示：

3.3 Jaccard距離

作者認為，假如兩張圖檔相似，那麼它們的k-rnn集合會重疊，即會有重複的樣本。重複的樣本越多，這兩張圖檔就越相似。那麼很自然地就想到用Jaccard Distance度量它們k-rnn集合的相似度：

然而，上面的距離度量有三個缺點：

1.取交集和并集的操作非常耗時間，尤其是在需要計算所有圖像對的情況下。一個可選方式是将近鄰集編碼為一個等價的但是更簡單的向量，以減少計算複雜度。

2.這種距離計算方法将所有的近鄰樣本都認為是同等重要的，而實際上，距離更接近于probe的更可能是正樣本。是以，根據原始的距離将大的權值配置設定給較近的樣本這一做法是合理的。

3.單純考慮上下文資訊會在試圖測量兩個人之間的相似性時造成相當大的障礙。因為，不可避免的變化會使得區分上下文資訊變得困難。是以，為了得到魯棒的距離度量，結合原始距離和Jaccard距離是有必要的。

為了克服上述缺點，我們開始改造Jaccard距離。首先，将k-rnn集合編碼為N維的二值向量

=

，其中每個元素由以下訓示函數定義：

接着，為了給每一個元素根據原始距離來重新配置設定權值，我們采用了高斯核。于是将向量改寫為：

于是，計算Jaccard距離時用到的交集和并集的基數就改寫為：

最後，我們終于得到了改造過的Jaccard距離：

這個改造過程，實際上是将集合比較問題轉化為純粹的向量計算，實踐起來更簡單。

3.4 Local Query Expansion

基于來自同一類的圖像可能共享相似特征的想法，我們使用probe的k-nn集合來實作local query expansion，

特别要說明的是，這個query expansion被同時用到了probe 

和galleries

上。（這裡我的了解是對每個向量定義為其k-nn集合向量的平均，通過這種方法來提升性能。根據我的測試，去掉這一步仍然有不錯的效果，但mAP會有少許的下降。）因為k-nn集合可能會混有噪聲，是以我們将k值設定得比較小。為了與前面的k做區分，我們定義前面用到的為

，而這裡用到的為

，k1>k2.

3.5 最終距離

在這裡有參數

，最終計算距離如下：

3.6 複雜度分析

參考原文内容。

整個重排序的流程圖如下所示：