基于鄰域相似度的行人重識別重排序算法

呂翔　陳念年　蔣勇

摘要：在行人重識別模型中引入鄰域數據關系，提出了一種基于圖像鄰域相似度的重排序方法。首先擴充圖像的鄰域數據，然后計算圖像對不同鄰域數據的相似度權重，利用該權重得到代表鄰域相似度的分布距離，再用分布距離與原始距離計算得出最終距離作為重排序評判標準。使用CCL，Transreid，Torchreid等行人重識別模型在Market-1501，DukeMTMC-reID數據集上進行實驗，結果表明本文方法對基準模型的精度提升均超過該領域的主流算法，證實了本文方法的有效性和泛化性。該重排序方法不需要任何人工交互和額外數據，適用于大規模數據集，可以有效應用于圖像檢索、目標跟蹤等需要考慮相似度關系的任務中。

關鍵詞：行人重識別 重排序 鄰域相似度

中圖分類號：TP391.41文獻標志碼：A文章編號：1671-8755（2023）04-0096-08

Re-ranking Algorithm of Person Re-identification with Neighborhood Similarity

LV Xiang， CHEN Niannian， JIANG Yong

Abstract：? The neighborhood data relationship was introduced into person re-identification model， and a re-ranking method based on image neighborhood similarity was proposed. Firstly， the neighborhood data of the image was expanded， and then the similarity weights of the image to different neighborhood data were calculated， and the distribution distance representing the neighborhood similarity was obtained by using the weight. Finally， the final distance which was calculated by using the distribution distance and the original distance was taken as the re-ranking criterion. CCL， Transreid， Torchreid and other person re-identification models were used to conduct experiments on Market-1501 and DukeMTMC-reID datasets. The results show that the accuracy improvement of the baseline model by the proposed method exceeds that of the mainstream algorithms in the field， which proves the effectiveness and generalization of the proposed method. The re-ranking method does not require any human interaction and additional data. It is suitable for large-scale datasets and can be effectively applied to tasks that need to consider the similarity relationship such as image retrieval and object tracking.

Keywords：? Person re-identification; Re-ranking; Neighborhood similarity

行人重識別［1-4］是計算機視覺中備受關注的領域之一，旨在從多個跨域攝像機所捕獲的人群中檢索出目標對象，廣泛應用于公共安全、刑事偵查等領域［5-6］。給定一張查詢圖像和一組從多個相機中獲取的圖像庫，根據查詢圖像與圖像庫中所有圖像的相似度，可以獲得一個有序的初始列表（圖1），位于初始列表頂部的圖像被認為與查詢圖像最為相似。通常使用余弦相似度計算圖像之間的相似性以獲得初始列表［7-9］，但該方法只考慮少量樣本信息且度量條件單一，無法應對實際應用中光照變化、相機分辨率改變、遮擋等復雜情況［10-11］。因此，僅靠一次粗排序得到的結果并不理想，解決方法通常是在評估階段后加入重排序步驟來解決這類問題。重排序是圖像檢索中的一種后處理手段，它不直接修改模型的參數，而是作用于模型的末端，進一步解析初始列表，發現圖像之間的內在關系，并對其進行重新排序，以獲得更好的檢索結果［12］。

現有的重排序工作主要考慮如何擴展更多的相似數據以及選擇更合理有效的度量方式來提升檢索效果［13-15］。Ye 等［16］將全局和局部特征的鄰域數據作為新的檢索基準，并通過聚合全局和局部特征使初始排序列表更加魯棒。Chum 等［17］提出了 AQE（Average query expansion）方法，得到的排序列表由返回的前 k 個數據中的平均排序結果獲得，將該方法運用于行人重識別中可顯著提升檢索效果。Ye 等［18］利用K-近鄰集合來計算不同基準方法的相似性和不相似性，然后將其聚合來優化初始排序列表。Bai 等［19］提出統一集合擴散算法，將數據特征進行擴散操作，并結合融合步驟實現互補性，進一步提升圖像重排序效果。Chen 等［20］利用圖卷積網絡的聚合操作和通道注意力機制來進一步提升重排序階段圖像檢索效果。Zhou 等［21］通過其近鄰圖像的線性組合對圖像信息進行擴展和增強，并結合注意力機制來預測圖像之間的相關性，降低排序的錯誤率。Wu 等［22］認為圖像外觀特征和排名上下文信息可以被聯合優化，以學習更多的鑒別性表征，實現更高的匹配精度。Zhong 等［10］研究了K-相互鄰近方法在人的重新識別中的重要性，設計了一個簡單而有效的重排序方法，其效果顯著且使用便捷。但對于鄰近樣本稀疏的困難樣本圖像，以上方法均存在可能使負樣本被排在更靠前位置的問題，其主要原因是重新度量相似度時，圖像之間的鄰域數據關系并沒有充分引入，從而導致誤排序。針對該問題，本文提出了一種利用鄰域相似性來度量圖像相似度的重排序方法。

1 算法總體設計

筆者認為圖像的鄰域數據中包含豐富的特征信息，由此提出了一種度量鄰域相似度的方法，利用該方法計算得到的鄰域分布距離可以發現更深層的鄰域關系，展現更為魯棒的相似性信息，能有效地過濾負樣本數據，提高重排序結果的準確性。本文方法重新計算相似度流程如圖2所示。

（1）擴展鄰域數據：對鄰域數據進行擴展以得到更加豐富的鄰域信息，緩解因為圖像數據稀疏而造成的誤排序問題。

（2）計算鄰域分布距離：每張圖像與各鄰域圖像集之間可以計算得到不同的相似度權重，利用相似度權重計算得到鄰域分布距離，該距離將作為度量鄰域相似度的標準。

（3）計算重排序距離，重排序：聯合鄰域相似度和余弦相似度，使用鄰域分布距離和原始距離進行加權求和得到重排序距離，根據重排序距離從小到大重新排序。

2 擴展鄰域數據

2.1問題定義

給定查詢圖像 q 和圖像庫G={gi｜i=1，2…N}，q和 gi之間的原始距離d=（q，gi）通過余弦距離計算，公式如下：

式中xq和xgi分別表示查詢圖像q和圖像gi的L2范數歸一化后的數據特征，該特征通過模型直接輸出獲得。根據原始距離d（q，gi）可以得到升序排列的初始列表L（q，G）={g0，g1…gN} 。初始列表是直接決定模型性能的關鍵。因此本文最終目標是將更多正樣本盡可能排在L（q，G）列表的前端，從而提高行人重識別的性能。

2.2 鄰域數據擴展

給定圖像庫G，定義N（q，k）為查詢圖像q與G中最相似的k個樣本，試圖從N（q，k）中發現魯棒的鄰域數據。受K-相互臨近［10］啟發，將N（q，k）分別劃分為硬臨近Nh（q，k）和軟臨近Ns（q，k）關系，表示如下：

由于Nh（q，k）與q具有對稱的鄰居關系以及較高的相似度，所以將其作為擴展q鄰居樣本的基準，相反地，屬于Ns（q，k）的圖像gi與q屬于非對稱的鄰居關系，僅使用其作為q的鄰居樣本。與K-相互臨近的擴展方式類似，如果Nh（q，k）與Nh（g，12k）集合交集大于后者集合總數的 23，那么就將Nh（g，12k）集合并入集合Nh（q，k）形成N*h（q，k）。完成上述步驟后，N*h（q，k）與Ns（q，k）合并形成N*（q，k）［10］，表示如下：

式中｜·｜表示集合中元素的數量。

2.3 原始距離轉化為相似度權重

通過余弦距離公式可以得到N*（q）中所有圖像與查詢圖像q之間的原始距離，但僅通過此操作得到距離并不能直接運用，它存在以下問題：（1）由于量綱影響，部分數值之間差距過大，計算復雜度較高且不利于后續操作；（2）原始距離只反映了圖像之間的相距情況，并不能體現其鄰域分布表現，沒有考慮鄰域元素的影響。

為解決第一個問題，本文對距離數據進行了0-1 歸一化：

通過公式（6）將所有數值轉化到 0-1 之間，可以緩解數值之間的量綱問題，并且也降低后續計算量，d*（q，gi）表示進行0-1歸一化后的距離數據。

針對第二個問題，對所有鄰域數據再進行求和歸一化操作，使各個鄰域數據之間建立關系：

式中Wq，gi表示進行求和歸一化操作后的相似度權重數據。經過公式（7）后，圖像q與鄰域數據的距離權重反映了查詢圖像q的所有鄰域元素與q相似度比例且所有距離權重和為 1，鄰域元素之間由此相互制衡并產生聯系。

2.4 鄰域數據聚合

通過以上操作，得到了更多正樣本的鄰域數據N*（q），且包含更為魯棒的鄰域信息，但也由于數據偏差而引入了負樣本數據。

為解決引入負樣本的問題，本文使用平均查詢擴展方法（AQE）［20］來生成更魯棒的鄰域相似度權重W*q，gi，公式如下：

式中：R（q，k）表示圖像q鄰域中前k個權重系數最大的圖像集合；W*q，gi表示查詢圖像q的鄰域數據的相似度權重占比。公式（9）可以將圖像q對gi的相似度權重替換為鄰域數據對gi圖像的平均相似度權重，如果圖像q和其鄰域數據均與圖像gi具有較高的相似度，那么q會對gi賦予一個較大的相似度權重，反之則會得到較低的相似度權重。通過這種方法可以聚集共性信息，排斥、疏遠異性信息，以達到降低負樣本權重系數和提升正樣本權重系數的目的。值得注意的是，這里的k與先前公式中的k是不同的，本文使用k2作為本公式中k值，k1作為先前公式中的k值。

3 計算鄰域分布距離

杰卡德距離常用于計算集合之間的相似性［10］，公式如下：

杰卡德距離主要思想是計算集合Q1和Q2的交集與并集的比值，將比值作為判斷集合相似性的依據。在行人重識別重排序階段，杰卡德距離也用于判斷兩鄰域集合的相似程度［10］，但其只考慮了兩個集合是否包含相同元素情況，而沒有涉及這些元素在集合中的分布位置問題，并不能挖掘鄰域關系。從關注對象看，杰卡德距離著重關注集合本身，而行人重識別更加關注的是查詢對象，即集合中的元素，所以杰卡德距離的宏觀思想與行人重識別的微觀目的并不相符。

為解決該問題，本文利用各圖像對不同鄰域數據的相似度權重來計算它們之間的鄰域相似度。圖像與其鄰域數據的距離權值總和為1，如果圖像 p與圖像q相似，那么它們與對方的鄰域數據的距離權重總和也應該接近1，由此提出了鄰域相似度計算公式——鄰域分布距離公式：

式中gq和gp分別是N*（q，k）和N*（p，k）鄰域集合中的元素。通過計算兩個圖像分別關于對方鄰域數據的距離權重占比，對稱性地分析圖像之間的臨近關系，計算得到的相似度距離更具準確性。鄰域分布距離計算流程如圖 3 所示。首先分別獲得圖像與不同鄰域數據之間相似度權重，然后計算這些圖像對同一鄰域數據的相似度權重差異，最后將所有的相似度權重差異的平均值作為鄰域分布距離，用于評判兩圖像之間的鄰域相似度。

由于現有的重排序方法大多忽略了原始距離在重新排序中的重要性，本文通過聯合歸一化后的原始距離和鄰域分布距離來調整初始排序列表，得到最終距離：

式中λ∈［0，1］，表示原始距離的懲罰系數。當λ=0時，只考慮鄰域分布距離，相反，當λ=1時，只考慮原始距離。最后，通過對最終距離的升序排序，可以得到調整后的排序列表L*（q，G）。

4 實驗驗證

4.1 實驗環境與評價指標

（1）數據集。在 Market-1501［23］和DukeMTMC-ReID［24］行人重識別圖像數據集上進行了實驗。數據集均從多個攝像頭獲取且由訓練集、測試集兩部分組成。

Market-1501 公開于 2015 年，來源于清華大學的一家超市門前的 6 個攝像頭，包含 32 668 張圖像，共有 1 501 個不同身份的行人。其中，訓練集由751 個行人的 12 936 張圖像組成，測試集中的查詢圖像和圖像庫均來自 750 個行人，分別包含 3 368 張和 19 732 張圖像，所有圖像通過 DPM 檢測器［8］和人工標注獲得。

DukeMTMC-ReID 發布于 2017 年，采集于杜克大學校園中的 8 個攝像頭，包含 36 411 張圖像，共有 1 812 個不同身份的行人。其中，訓練集由702個行人的16 552張圖像組成，測試集由 702 個行人的 19 889 張圖像組成，查詢圖像有 2 228 張，圖像庫有 17 661 張圖像。除了包含702 個行人外，測試集中還添加了 408 個用于干擾測試的行人數據，所有圖像均由人工標注獲得。

（2）基準模型。重排序手段通常用于后處理階段，所以為驗證所提出方法的有效性以及泛化性，分別使用 3 個基準模型進行實驗測試。CCL［25］使用 CNN 作為骨干網絡，結合對比學習的方法來應對行人重識別在無監督方向上所面臨的挑戰。Torchreid［26］方法提出一種基于 CNN 的輕量級全尺度網絡來學習行人特征，在同域和跨域數據上均取得較好的表現。Transreid［27］是首個基于 Vision Transformer 的行人重識別方法，通過引入注意力機制和去除降采樣、卷積等方式彌補基于 CNN 方法存在的限制。使用 CCL，Torchreid 以及Transreid作為實驗的基準模型是為了體現本文方法在無監督和有監督以及 CNN 和 Transformer 上的泛化性。

（3）評價指標。使用兩個評價指標來均衡評判各種重排序方法在數據集上的性能。第一個評價指標是平均精度（Mean average precision，mAP），用于計算每個查詢精度-召回曲線下的面積 AP，mAP 為所有查詢圖像的 AP 的平均值，它同時考慮了精度和召回率。另一個評價指標是累積匹配特性（Cumulative match characteristic，CMC），考慮到行人重識別是一個排序問題，如果第一個匹配的圖像出現在第k個圖像，那Rrank-k 的值將會置為 1，表示順序排序的第k位候選圖像為正確匹配結果。本文中使用了 mAP 和 Rank-1 的累積匹配精度作為實驗的評價指標。

4.2 實驗結果

4.2.1 參數尋優

主要針對數據擴展階段的k1、數據聚集階段的k2以及最終距離公式中所使用的λ參數進行分析。使用CCL作為基準模型，分別評估了以上參數變化在Market-1501 和DukeMTMC-reID 數據集上對mAP的影響。

圖4顯示了k1大小對mAP的影響（k2設為10，λ設為0.5，選用CCL作為基準模型）。mAP首先隨著k1的增長而增加，然后在k1超過一個閾值后開始緩慢下降。同樣地，隨著k1的增長，Rank-1 的準確率首先在波動中上升，在到達k1=20 左右的最佳點后，mAP 開始下降。如果k1的值過大，就會有更多的錯誤匹配包含在鄰域集合中，從而導致性能下降。

圖5顯示了k2對mAP 的影響（將k1設為20，λ設為0.5，選用CCL作為基準模型），當k2等于 1 時，參與聚集的鄰域數據為圖像本身，可以認為沒有進行鄰域聚集操作。很明顯，隨著k2在合理范圍內增加，性能也會增長。但如果給k2分配一個太大的值，會降低性能，因為它可能會引入更多分類錯誤的鄰近數據，導致在鄰域聚集結果中的錯誤匹配呈現遞增趨勢。實驗結果表明，當k2設定為7時，鄰域聚集階段對整體性能提升最佳。

參數λ的影響如圖 6 所示（將k1設為 20，k2設為 7，選用 CCL 作為基準模型）。當λ設置為 0 時，不考慮原始距離，直接將鄰域分布距離作為最終距離；當λ=1時，直接使用原始距離作為最終距離。由圖 6 可以觀察到，當鄰域分布距離被納入最終距離的計算范疇時，實驗結果均優于只考慮原始距離的情況，這表明提出的鄰域分布距離對重排序結果有積極影響。此外，當同時考慮原始距離和鄰域分布距離時，λ值在 0.8 左右時，性能得到進一步提高，說明原始距離對重排序結果也很重要。

4.2.2 性能比較

基于先前提到的 3 個基準模型，在重排序階段分別選用AQE，K-相互臨近以及本文方法進行實驗，設定參數k1=20，k2=7，λ=0.8， 表1和表2分別展示了在 Market-1501和 DukeMTMC-reID 數據集上的實驗對比結果，本文方法在各個基準模型上均超越先前方法的性能，表明了該方法的有效性以及泛化性。

5 結論

盡管鄰域數據關系為重排序提供了豐富的深層信息，但未被充分利用或受到限制。本文提出了一種基于圖像鄰域相似度的重排序方法，該方法巧妙地利用鄰域數據關系來提高行人重識別中重排序方法的性能。首先對原始數據信息進行預處理，在查詢圖像的鄰域中擴展并聚集更多的正樣本數據；然后根據不同圖像對同一鄰域數據的相似度差異性，提出了度量鄰域相似性的分布距離；最后使用原始距離和分布距離計算得到的最終距離進行重排序。在 Market-1501，DukeMTMC-reid 數據集上驗證表明本文方法的行人重識別性能明顯提高，精度均超過目前最流行的方法。本文方法是完全無監督的方法，無需預訓練額外模型和人工標注，可以很容易地在各種檢索模型上實現，在圖像檢索、目標跟蹤等需要考慮相似度關系的任務中可以有效應用。

參考文獻

［1］ YE M， SHEN J B， LIN G J， et al. Deep learning for person re-identification： A survey and outlook［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（6）： 2872-2893.

［2］ 羅浩， 姜偉， 范星， 等. 基于深度學習的行人重識別研究進展［J］. 自動化學報， 2019， 45（11）： 2032-2049.

［3］ LIAO S C， HU Y， ZHU X Y， et al. Person re-identification by Local Maximal Occurrence representation and metric learning［C］∥2015 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE， 2015： 2197-2206.

［4］ MARTINEL N， FORESTI G L， MICHELONI C. Person re-identification in a distributed camera network framework［J］. IEEE Transactions on Cybernetics， 2017， 47（11）： 3530-3541.

［5］ ZHENG L， YANG Y， HAUPTMANN A G. Person re-identification： past， present and future［EB/OL］. （2016-12-10） 2016： arXiv： 1610.02984. https：//arxiv.org/abs/1610.02984.

［6］ 馮霞， 杜佳浩， 段儀濃， 等. 基于深度學習的行人重識別研究綜述［J］. 計算機應用研究， 2020， 37（11）： 3220-3226， 3240.

［7］ JEGOU H， HARZALLAH H， SCHMID C. A contextual dissimilarity measure for accurate and efficient image search［C］∥2007 IEEE Conference on Computer Vision and Pattern Recognition. IEEE， 2007： 1-8.

［8］ SHEN X H， LIN Z， BRANDT J， et al. Object retrieval and localization with spatially-constrained similarity measure and k-NN re-ranking［C］∥2012 IEEE Conference on Computer Vision and Pattern Recognition. IEEE， 2012： 3013-3020.

［9］ YE M， LIANG C， WANG Z， et al. Ranking optimization for person re-identification via similarity and dissimilarity［C］∥Proceedings of the 23rd ACM International Conference on Multimedia. 2015： 1239-1242.

［10］CHEN P X， LIU W F， DAI P Y， et al. Occlude them all： occlusion-aware attention network for occluded person re-ID［C］∥2021 IEEE/CVF International Conference on Computer Vision （ICCV）. IEEE， 2022： 11813-11822.

［11］PHAN H， NGUYEN A. DeepFace-EMD： re-ranking using patch-wise earth movers distance improves out-of-distribution face identification［C］∥2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE， 2022： 20227-20237.

［12］LIU W W， XI Y J， QIN J R， et al. Neural re-ranking in multi-stage recommender systems： a review［EB/OL］. （2022-04-16） 2022： arXiv： 2202.06602. https：∥arxiv.org/abs/2202.06602.

［13］GARCIA J， MARTINEL N， GARDEL A， et al. Discriminant context information analysis for post-ranking person re-identification［J］. IEEE Transactions on Image Processing， 2017， 26（4）： 1650-1665.

［14］MA A J， LI P. Query based adaptive re-ranking for person re-identification［C］∥Computer Vision-ACCV 2014. Cham： Springer International Publishing， 2015： 397-412.

［15］ZHENG L， WANG S J， TIAN L， et al. Query-adaptive late fusion for image search and person re-identification［C］∥2015 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE， 2015： 1741-1750.

［16］YE M， CHEN J， LENG Q M， et al. Coupled-view based ranking optimization for person re-identification［C］∥International Conference on Multimedia Modeling. Cham： Springer， 2015： 105-117.

［17］CHUM O， PHILBIN J， SIVIC J， et al. Total recall： automatic query expansion with a generative feature model for object retrieval［C］∥2007 IEEE 11th International Conference on Computer Vision. IEEE， 2007： 1-8.

［18］YE M， LIANG C， YU Y， et al. Person reidentification via ranking aggregation of similarity pulling and dissimilarity pushing［J］. IEEE Transactions on Multimedia， 2016， 18（12）： 2553-2566.

［19］BAI S， TANG P， TORR P H S， et al. Re-ranking via metric fusion for object retrieval and person re-identification［C］∥2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE， 2020： 740-749.

［20］CHEN X Q， ZHENG L， ZHAO C， et al. RRGCCAN： re-ranking via graph convolution channel attention network for person re-identification［J］. IEEE Access， 2020， 8： 131352-131360.

［21］ZHOU Y H. Moving towards centers： re-ranking with attention and memory for re-identification［D］. Nanyang Technological University， 2021. DOI： 10.32657/10356/152805.

［22］WU G L， ZHU X T， GONG S G. Learning hybrid ranking representation for person re-identification［J］. Pattern Recognition， 2022， 121： 108239.

［23］ZHENG L， SHEN L Y， TIAN L， et al. Scalable person re-identification： a benchmark［C］∥2015 IEEE International Conference on Computer Vision （ICCV）. IEEE， 2016： 1116-1124.

［24］RISTANI E， SOLERA F， ZOU R， et al. Performance measures and a data set for multi-target， multi-camera tracking［C］∥European Conference on Computer Vision. Cham： Springer， 2016： 17-35.

［25］DAI Z Z， WANG G Y， YUAN W H， et al. Cluster contrast for unsupervised person re-identification［C］∥Asian Conference on Computer Vision. Cham： Springer， 2023： 319-337.

［26］ZHOU K， YANG Y， CAVALLARO A， et al. Learning generalisable omni-scale representations for person re-identification［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2021， 44（9）： 5056-5069.

［27］ZHOU K Y， YANG Y X， CAVALLARO A， et al. Learning generalisable omni-scale representations for person re-identification［EB/OL］. （2021-04-29） 2019： arXiv： 1910.06827. https：∥arxiv.org/abs/1910.06827.

［28］HE S T， LUO H， WANG P C， et al. TransReID： transformer-based object re-identification［C］∥2021 IEEE/CVF International Conference on Computer Vision（ICCV）. IEEE， 2022： 14993-15002.

收稿日期：2022-12-02；修回日期：2023-03-03

基金項目：四川省科技廳重點研發項目（2021YFG0031）；四川省省級科研院所科技成果轉化項目（22YSZH0021）

作者簡介：第一作者，呂翔（1997— ），男，碩士研究生，E-mail： 178717515@qq.com； 通信作者，陳念年（1977— ），男，碩士，副教授，研究方向為圖像分割與識別、視覺測量，E-mail： chenniannian@swust.edu.cn