侯建华，周 浪，项 俊

(中南民族大学 电子信息工程学院，武汉 430074)

基于边缘概率和m-Best求解的行人再识别

侯建华，周 浪，项 俊

(中南民族大学 电子信息工程学院，武汉 430074)

指出了行人再识别应用之一是在同一场景、不同摄像头视角下，对查询集与候选集中的所有目标做出最优关联，其本质是二分图匹配问题.针对传统方法只在联合概率分布基础上寻找一个最优解，没有利用其它候选解中的有用信息，不能保证最优解的正确性的问题，提出了利用边缘分布特点，综合其它候选匹配点的信息，在联合匹配空间上使每一对匹配点的边缘分布最大化，从而提高求解质量；且对联合匹配空间的边缘分布计算不可行，采用二叉树分割算法求m个最优解，以实现边缘概率的估计.实验表明：将上述方法应用于行人再识别问题能有效改善再识别算法的精度.

行人再识别；图匹配；联合匹配空间；边缘概率分布

过去五年，行人再识别(re-id)问题[1]已成为机器视觉领域的研究热点；其基本任务是给定一张行人测试图片，从候选图像集中寻找与之拥有一致身份的行人图像[2].受光照、视角、姿态的变化，以及背景干扰和不同摄像机方位等因素影响，行人外观易产生较大的差异，行人再识别研究面临很大的挑战.如图1所示，同一行人在不同场景下外观发生了很大变化.

现有的行人再识别方法主要分为两大类：基于特征表达的方法[3,4]、基于距离度量学习的方法[5-7].前者致力于寻找对光照、视角变化具有良好鲁棒性的特征表达方式，例如Liao等[3]提出了一种局部最大发生概率(LOMO)的特征表达方法；M.Farenzena 等[4]首先对行人轮廓分割，再提取局部加权颜色直方图、最大稳定颜色区域、以及高频结构块特征作为特征描述子.基于度量学习的方法则着重设计判别性的距离度量模型，例如KISSME距离度量学习方法[5]、概率相对距离比较模型(PRDC)[7]等.

图1 VIPeR数据库图片：同一列为同一行人，但外观具有较大差异Fig.1 VIPeR Database:the images of the same column belong to the same identify, but are different in person′s appearance

需要指出的是，上述re-id问题考虑的是一个测试目标与候选集所有目标间的匹配.但行人再识别还有一种应用需求，即在同一场景、不同摄像头视角下的行人身份关联[8,9]，本文称为关联再识别，其本质是二分图匹配问题，即查询集中所有目标与候选集中所有目标之间的最优关联求解.一般的说，关联再识别首先构建两个集合目标间的联合匹配概率(或者代价函数)，再依据最大后验概率(MAP)准则、或者匈牙利算法求最优解[10].文献[9]指出，在这种基于联合概率分布(JPD)的方法中，为了方便求解，每一对点之间的匹配与其它各对点匹配视为相互独立，没有考虑其它点对当前两点匹配的影响，因此不能保证最优解一定是正确的解(见图3说明).

本文对基于边缘分布的二分图匹配问题进行了研究.其思路是在联合匹配空间上，使每一对匹配点的边缘分布最大化，从而综合考虑了其它候选匹配点的信息，求解质量无疑优于JPD方法.但计算联合匹配空间的边缘分布数据量巨大、在实际应用中不可行；为此借鉴文献[9]提出的m-best求解方法，即利用二叉树分割[11]算法将联合空间划分为不同子集，搜索其中的m个最优解，用联合匹配空间小部分数据(即m个解)对边缘分布做出较精确的估计.实验证明了这种基于边缘概率和m-Best求解的行人再识别算法有效性.

1 图匹配问题描述

图匹配理论[12]已广泛应用于机器视觉领域.一对一匹配，就是将候选集每一个目标与查询集的一个目标进行匹配，通过联合匹配概率最大化(或者目标代价最小化)得到最优匹配方案.

(1)

(2)

所有解的集合构成联合匹配空间χ：

(3)

约束(a)

约束(b)

其中约束(a)表示候选集[B]中每个目标最多分配一个查询集[A]中的目标，约束(b)表示查询集[A]中的每个目标必须与[B]0中的唯一目标相匹配(可以是空点).

在联合匹配空间上，利用最大后验概率准则(MAP)使联合概率最大化，得到最优解(即分配结果)：

(4)

一对一匹配问题可以用二分图表示.图2给出了一个示例，图中浅色线条指示的结果是通过MAP准则求出的最优解，即(Q1→G2，Q2→G3)，然而正确匹配结果如深色线条指示，应该是(Q1→G3，Q2→G2).匹配错误原因在于：由于Q2与G3相似性很大，即使Q1与G2相似性较小，最终也导致(Q1→G2，Q2→G3)的联合概率大于(Q1→G3，Q2→G2).

图2 行人匹配框架Fig.2 The framework of matching person

由于优化过程中约束条件过于简单，仅依赖合适的优化函数(联合概率)实现全局最优，并不能保证匹配的正确性.为此，本文利用联合匹配空间的边缘分布，综合其它候选匹配点的相关信息，通过求匹配点的最大边缘分布，提高匹配的准确性.

2 基于边缘分布最大化求解

2.1 基本思想

在实际应用中匹配空间行人外观可能产生剧烈变化，导致不同行人可能具有较高的相似性，解空间中通常存在许多解向量、其对应的联合概率p(X)接近全局最优解p(X*)；换言之，虽然存在许多有竞争力的候选解，但最后仅通过MAP准则获得唯一解.这种偏“武断”的处理方式没有考虑其它相似解中所包含的有效信息进而做出集体决策，增加了错误匹配的可能性.

(5)

图3 基于边缘分布方法与基于联合概率分布方法的比较Fig.3 The application of the marginals

上述求解方法优势如下：1)在计算每一对匹配点的边缘分布时，需要将包含此匹配的所有解考虑进去，实质上是一种集体决策；相比较而言，最大后验概率估计则仅考虑了一种解.2)边缘分布是通过对联合匹配空间求和得到的，因此具有平滑噪声的特性.文献[9]指出，基于边缘分布的求解在理论上要优于最大后验概率估计方法.

然而，求解边缘分布涉及到联合匹配空间中所有相关的解，当查询集、候选集中目标个数比较多时，计算每一对匹配点的边缘分布计算量巨大，几乎难以在实际中应用.针对此问题，以下介绍一种计算边缘分布的近似方法：m-Best求解.

2.2 基于二叉树分割的m-Best近似求解

(6)

本文采用二叉树分割算法(BTP)[11]计算m个最优解.设根据MAP准则能够寻找到最优解X*，在此前提下，BTP算法通过迭代将解空间不断分割为两个子集，计算出余下的m-1个最优解；由于BTP算法利用解向量元素的二值性、减少冗余的约束条件，是一种高效便捷的求解方法.二叉树分割算法简要描述如下.

设第m个最优解所在的解空间为χm，则：

χ1=χ

χ2={χ|<‖‖1}

χ3={χ|<‖‖1},

<‖‖1}

⋮

χm={χ|∀k∈{1,2,…,m-1},

<‖‖1}

(7)

(8)

(9)

然后在分裂的两个集合上分别求解，通过比较解向量得到第三个最优解：

(10)

3 实验结果

3.1 数据库和性能评价

实验采用行人再识别研究中的4种通用公共数据库.(1)VIPeR数据库[2]包含632对行人图像，是在室外环境下、通过两个不同视角的摄像机采集得到，每个行人在每个视角下仅有一张图像，图像大小统一为128×48像素；该数据库涵盖了视角、姿态和光照的变化，对行人再识别来说是最具挑战的数据库之一；(2)CUHK01数据库[14]包含971个行人个体，每个个体在每个摄像机视角下拥有两张图片；(3)WARD数据库[15]包含70个不同行人的4786张图像，其困难在于除了分辨率、姿势变化外，还包括光照的剧烈变化；(4)RAiD数据库[8]包含43个行人的6920张图像，其中只有41个行人在所有摄像机中出现过.

性能评价指标采用累积匹配特性曲线(CMC)，CMC曲线描述在候选集中搜索待查询行人，前k个匹配结果中找到待查询人的比率，用Rank-k表示.其中Rank-1表示再识别算法的真正识别率.为了获得稳定可靠的再识别率，每次实验重复10次，再将平均结果作为最终的再识别率.

3.2 结果

图4 在RAiD数据库上的实验Fig.4 The experiment on the RAiD Datebase

图6和图7给出了在VIPeR和CUHK01数据库上的实验结果.根据文献[6]，视觉特征为SIFT/LAB、LBP/RGB、区域协方差和CNN描述子的加权组合，以此计算行人图像匹配相似度分数作为匹配概率.

可以看出，本文方法(浅色曲线)的Rank-1比文献[6]方法(黑色曲线)有一个较显著的提升.

图5 在数据库WARD上的实验Fig.5 The experiment on the WARD Database

图6 在VIPeR数据库上的实验对比Fig.6 The comparison of methods on VIPeR Database

图7 在CUHK01数据库上的实验对比Fig.7 The comparison of methods on CUHK01 Database

表1给出了在不同数据库下利用原始匹配概率和利用m-Best方法求解边缘概率得到的再识别率.表1中数据表明，利用m-best方法可以获得Rank-1的明显提升，随着k值的增加，再识别率趋于平缓.

图8为本文算法与已有的一些行人再识别算法在VIPeR数据库上的的CMC曲线对比图；表2是与图8对应中的再识别率.可以看出本文算法有效提高了行人再识别算法的识别精度，具有良好的再识别特性.

图8 本文算法与已有算法在VIPeR数据库上的实验对比Fig.8 The comparison of the proposed method and existing methods on the VIPeR Database

4 结语

本文提出了基于边缘分布最大化的行人再识别算法,该方法采用二叉树分割算法求m个最优解，以此近似联合匹配空间、计算边缘分布，求解质量优于基于联合概率分布最大方法.实验表明：该方法有效提高了行人再识别算法的识别精度，具有良好的再识别特性.今后可以将深度神经网络的特征学习能力、不同损失函数特性与之结合开展进一步的研究.

表1 不同方法的再识别率

表2 行人再识别算法比较

[1] Wang X, Zhao R. Person Re-identification: System Design and Evaluation Overview [M]. London : Springer ,2014:351-370.

[2] Gray D, Brennan S, Tao H. Evaluating appearance models for recognition, reacquisition, and tracking [C]// IEEE.Proceedings of IEEE International Workshop on Performance Evaluation for Tracking and Surveillance (PETS). New Jersey:IEEE,2007:3-5.

[3] Liao S, Hu Y, Zhu X, et al. Person re-identification by local maximal occurrence representation and metric learning [C]// CVPR. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. New Jersey : IEEE,2015: 2197-2206.

[4] Farenzena M, Bazzani L, Perina A, et al. Person re-identification by symmetry-driven accumulation of local features [C]// CVPR. Proceedings of Computer Vision and Pattern Recognition. San Francisco CA : CVPR, 2010:2360-2367.

[5] Köstinger M, Hirzer M, Wohlhart P, et al. Large scale metric learning from equivalence constraints [C]// CVPR. Proceedings of Computer Vision and Pattern Recognition. Washington D C : CVPR, 2012:2288-2295.

[6] Paisitkriangkrai S, Shen C, Hengel A V D. Learning to rank in person re-identification with metric ensembles [C]// CVPR. Proceedings of Computer Vision and Pattern Recognition. Boston MA : CVPR, 2015:1846-1855.

[7] Zheng W S, Gong S, Xiang T. Reidentification by relative distance comparison [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(3): 653-668.

[8] Das A, Chakraborty A, Roy-Chowdhury A K. Consistent Re-identification in a Camera Network [C]// ECCV. Proceedings of European Conference on Computer Vision. Zurich : ECCV, 2014:330-345.

[9] Hamid Rezatofighi S, Milan A, Zhang Z, et al. Joint probabilistic data association revisited [C]// ICCV. Proceedings of IEEE International Conference on Computer Vision. Santiago : ICCV, 2015: 3047-3055.

[10] Kuhn H W. The Hungarian method for the assignment problem [J]. Naval Research Logistics, 2005, 52(1):7-21.

[11] Fromer M, Globerson A. An LP View of the M-best MAP problem [C]// NIPS. Proceedings of Neural Information Processing Systems 2009. Vancouver BC : NIPS , 2009:567-575.

[12] Yan J, Cho M, Zha H, et al. Multi-graph matching via affinity optimization with graduated consistency regularization [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(6): 1228-1242.

[13] Zhang L, Li Y, Nevatia R. Global data association for multi-object tracking using network flows [C]// CVPR. Proceedings of Computer Vision and Pattern Recognition. Anchorage AL : CVPR, 2008: 1-8.

[14] Li W, Zhao R, Xiao T, et al. DeepReID: Deep Filter Pairing Neural Network for Person Re-identification [C]// IEEE.Proceedings of Computer Vision and Pattern Recognition. New Jersey : IEEE , 2014:152-159.

[15] Martinel N, Micheloni C. Re-identify people in wide area camera network [C]// CVPRW. Proceedings of Computer Vision and Pattern Recognition Workshops.New Jersey : IEEE, 2012: 31-36.

[16] Javed O, Shafique K, Rasheed Z, et al. Modeling inter-camera space-time and appearance relationships for tracking across non-overlapping views[J]. Computer Vision and Image Understanding, 2008, 109(2): 146-162.

[17] Wang J, Sang N, Wang Z, et al. Similarity Learning with Top-heavy Ranking Loss for Person Re-identification [J]. IEEE Signal Processing Letters, 2016, 23(1): 84-88.

Person Re-Identification Based on Marginal Probability andm-Best Solutions

HouJianhua,ZhouLang,XiangJun

(College of Electronic Information Engineering, South-Central University for Nationalities, Wuhan 430074)

One application of the person re-identification is optimal matching of all objects among prob set and gallery set which are under different camera views and at the same scene, and it is a binary graph matching problem in essence. The traditional method is to find a global optimum based on joint probability distribution that exploits no information of other candidates, thus can′t guarantee the correctness even the obtained solution is optimal. To tackle this issue, an approach is proposed to maximize the marginal distribution for matching each pair points over joint matching space, and the matching solution is improved by taking into account all possible matching combinations for all other candidates. As exact marginalization of the joint matching space is intractable, binary partition algorithm is used to approximate the marginal distributions by exploiting the m-best solutions of the original problem. Experimental results demonstrate that the proposed method has improved the algorithm′s accuracy when applied in the context of person re-identification.

person re-identification; graph matching; joint matching space; marginal probability distribution

2017-03-17

侯建华(1964-)，男，教授，博士，研究方向: 计算机视觉、模式识别，E-mail: hou8781@126.com

国家自然科学基金资助项目( 61671484); 中南民族大学中央高校基本科研业务费专项资金( CZQ17001)

TP391.41

A

1672-4321(2017)02-0073-06