Superpixel-based Tracking-by-Segmentation using Markov Chains

论文链接：Superpixel-based Tracking-by-Segmentation using Markov Chains

思想：将Tracking问题转化为已知前一帧超像素块的bg，fg状态的前提下求下一帧超像素块的bg，fg状态判定的问题，而后通过一些判断，确定最合理的fg超像素块的组合。这一系列操作都是基于超像素的，而状态的判定用了吸收状态的马尔科夫链。

优点：

1、应用了超像素来做区域回归，将少了数据量的同时，保留了图像分割的有效信息，且一般不破坏图像中的边界信息

2、将每个超像素块都当做马尔科夫链的一个状态，并且将空间上，时间上相邻的点都连线，生成的马尔科夫链将包含相邻帧的超像素块时空特性，切合Tracking问题的特性

3、用图论来做概率推算，CNN做的是一个SVR的特征提取器，训练的方式类似one-shot，先用semantic segmentation预训练模型，然后用自己的数据微调。可以看出，作者对于Tracking问题，更加关注的是时空关系，CNN用来做一种特征描述

4、在后续的Tracking中，会对前一帧的分割效果进行纠正，依赖于将bg设置为吸收态

核心： AMC的构建，超像素分割

具体作法：
以两帧为位

1、对于第一帧，我们将会得到它的ground-truth（或者预测的truth），然后为之在图上划分一个足够大的块ROI，作为超像素分割的输入（用SLIC进行超像素分割）

2、对于得到的超像素块，将之根据和ground-truth的overlap大小，分为bg和fg，对于bg设置为absorbing state

4、除了第一帧是视频的第一帧，对于每一个帧，我们都将two hops的超像素块相邻（即存在马尔科夫链中的状态装换），同时，根据运行信息，即光流向量，将两个帧之间有关联的超像素块连接起来，这样我们的马尔科夫链构建完成，进行下一步，进行边的权重确定

5、对于马尔科夫链中的每一条边，我们都是通过判断两端的超像素块经过SVR（support vector regression）的得分的差异程度来给权值。所以SVR的训练需要将同一label（只有bg或fg，简化标注的问题）的超像素块给以较小的得分差异，不同label给较多的得分差异。这里介绍CNN的做法，具体是，先用全连接回归分割中的CNN（ Fully convolutional networks for semantic segmentation）做pre-train model，然后将视频第一帧和后面predict得到的结果的bg扔进去训练，得到一个比较好的特征提取器，计算得分
（SVR的后面补充）
特别的，对于视频第一帧，采用

6、现在，我们得到一个完备的吸收态的马尔科夫链，计算概率q和r，则可以得到N矩阵，即非吸收态到非吸收态的平均频数，后对每一列求和，得到每个非态的吸收时间，然后通过阈值判断（平均现在帧所有fg的吸收时间）得到属于fg或bg的label
q和r的计算
π的值会影响分割效果

7、得到每个超像素块的label后，要进行判断，确定那些是能构成一个target，采用two-hops 的形式，将超像素块连接，则得到若干个组合体

8、对于若干个组合体，要判断哪个是原先的的target的，需要用遗传模型判断，先计算每个的归一化颜色直方图，然后判断那个和ht的巴氏距离（用于离散概率分布），小的为所求，更新ht

补充：

1、我们在计算下一帧的fg，bg时，得到的结果同样可以对上一帧进行更新，会修整的更好，这是因为这种方法对上一帧的不可见的判断错的bg有很好的处理

2、SVR实现：