原文链接：Multiple People Tracking by Lifted Multicut and Person Re-identification
MOT16 dataset测评：
预备知识：
multicut问题：指在一个图中上删除最少个数的顶点，使得预先给定的一组顶点对均不连通，是NP难（non-deterministic polynomial hard）问题。
softmax：根据概率选择输出，值越大概率越大。
ReLU：f(x)=max(0,x)
摘要：单摄像头中拥挤场景的多目标跟踪一直是一个棘手难题，即使某一个目标丢失视野，我们人类也可以在他重新出现时根据外观很好地捕捉到这个目标。但是我们也需要关注远距离的目标重现，而不是单单凭着外观来重新识别，因为这有可能不是同一个人。在本文中，作者提出一种基于图的新理论，可以串联、聚类不同时间出现的相同目标，通过解决最小损耗lifted multicut问题。作者的模型在不改变原来的可行解集的同时，将一个图的多个相距较远但是又相似的顶点连接起来，如此泛化了前人的工作，使得我们可以奖励那些以不引入不可行解的方式对同一目标进行相似性外观检测的轨迹。为了高效匹配较远距离的假设，作者还为目标重识别提出了新的深度结构，该结构将从深度网络提取出的全局表示和用state-of-the-art姿态估计模型得到的身体姿态层连接起来。
1、介绍及相关工作：（略）
2、模型：
MP(minimum cost multicut problem)：图中所有边表示的都是它们所连接的两结点来自同一目标的概率。
LMP(lminimum cost lifted multicut problem)：在MP基础上多加了lifted边，不定义直接相连结点的可能性。(do not define possibilities of directly joining nodes)
2.1、参数：
a）有限集V表示在一幅图像中的一个目标检测，即跟踪框。对于每个目标检测v∈V，它的高度是hv，中心位置是xv,yv，帧数是tv。
b）对于每对v,w∈V，条件概率pvw∈(0,1)表示v,w分属于不同目标的概率。
c）在图G=(V,E)中，每个边都是regular边，表示在相同帧中连接v,w，或者在不同帧但是帧数相近中连接v,w，并且这个差距存在上界δt≥|tv-tw|
d）在图G'=(V,E')中，E⊆E'，lifted边{v,w}∈E'\E，表示在不同帧中连接相似的v,w，并且满足|tv-t2|>δt和pvw≤p0，其中p0∈(0.1/2)
2.2、可行解集：
LMP的任一可行解都是01向量x∈{0,1}E'，其中xvw=1表示结点v和w属于不同分量。为了使x能定义G的分量，扩展补充定义：在XGG'∈{0,1}E'中的量x∈{0,1}E'，存在以下约束：
约束（1）表示，对于任意邻居结点v和w，如果在G中存在一条路径，这个路径的所有边都标记为0，那么vw的边也只能标记为0。
约束（2）（3）表示，当且仅当v和w再一个更小的图中相连，并且路径的边都标记为0，对于所有的可行解和所有的lifted边vw∈E'\E，xvw都标记为0。（意味着v和w属于同一个目标）
通过给lifted边vw∈E'\E分配cost cvw，我们可以不用将v和w直接相连再求概率，而是可以给可行解中分属于不同目标的v,w分配cost。
2.3、目标函数：
式（4）表示选择那些能最大化相同目标和不同目标概率的分量对。
θγ是在训练集上通过logistic回归估计得到的，γ表示目标检测对之间间隔长度。f(e)在这里表示目标检测间的相似度。
2.4、优化：
使用[1]的启发式方法，其中子图的双划分由一组变换序列更新。
3、跟踪中的目标重识别
主要比较多个CNN结构对重识别问题的作用，本文的基础CNN结构是VGG-16 Net。然后将MOT15 benchmark、MOT16 benchmark中的5个序列作为训练集；将CUHK03、Market-1501用于人物识别例子；将MOT16中的序列MOT16-02和序列MOT16-11作为测试集。总共2511个identities用作训练，123个identities用作测试。
3.1、结构
a）ID-Net：首先使用VGG net φ 从收集好的数据集中学习N=2511个identities，即N分类问题，然后将图像划分成112*224*3，每个图像xi与ground truth identity标记yi∈{1,...,N}相连接，VGG就将每个图像属于每个标记的概率pi=φ(xi)作为前向传播函数，而损失函数则选择softmax。
在测试时，给定一个没有identities标记的图像，最后的softmax层将被移除，然后全连接层φf7将的输出将用作identity的特征。给定一对图像，两identity特征的欧几里得距离将被用作判断是否这对图像是否具有相同的identity。在实验中作者认为这个identity特征已经有较好准确度，然而使用SiameseNet和StackNet的效果将会更上一层楼。
b）SiameseNet：一个Siamese结构指的是含有共享参数的两个对称CNNs的网络。为了对相似性建模，作者在两个CNNs顶部使用一个全连接层，通过这层就可以由一组图像得到特征FC6(xi)和FC6(xj)，然后再通过后面两个全连接层FC7和FC8连接并转换。其中紧接着FC7的是非线性的ReLU，而FC8则使用softmax函数产生概率估计来判断它们是含有相同的identity还是不同的identities。
c）StackNet：首先将一对图像根据RGB通道存到栈中，这样的话网络的输入大小就变成112*224*6，第一个卷积层大小也从3*3*3变成3*3*6，剩下的网络则使用VGG的结构。最后的全连接层和SiameseNet的FC8一样，将输出这对图像是否含有相同identity或不同identities。
在测试时，给定一对图像，SiameseNet和StackNet将输出得到是否含有相同或不同identities的概率作为前向传播。
StackNet允许一对图像在网络早期阶段进行比较，但是仍然受限于与目标身体部分回馈的配合。
3.2、融合身体部分信息
目前网络需要改进的是如何提取身体部分信息，并将此作为一个感兴趣的局部区域，然后基于这个局部区域和整个图像再计算图像对之间的相似性。作者将融合身体部分的检测加入到CNN中，并且为图像对的14个不同身体部分计算score maps（由于对称最终得到7个scores maps），每一个都和输入图像具有相同大小。然后将这些图也存到栈中，这样就有112*224*20的输入大小，第一个卷积层大小也变成了3*3*20，剩下的和StackNet后面的结构一样。
其余关于调参、实验结果、结论等内容感兴趣的读者可以自己去浏览，这里目前只关注作者创新内容~
参考文献：
[1]：M. Keuper, E. Levinkov, N. Bonneel, G. Lavoue, T. Brox, and B. Andres. Efficient decomposition of image and mesh graphs by lifted multicuts. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2015.