1.4　基于图理论的算法

1.4.1　基于图方法的基本概念

在视觉目标跟踪中，因为目标和背景的动态变化，要获取充足且准确的反映目标（或背景）信息的标记样本是比较困难的。但由于目标与背景具有一定差别，因此可以借助大量既包含目标又包含背景的未标记样本的内在结构特征来提高在标记样本有限条件下的分类准确率，从而提高跟踪的精度。目前大部分判别式跟踪方法仅仅利用了有限的标记样本进行监督学习，而忽视了大量作为未标记样本的候选区域所提供的信息，影响了跟踪的鲁棒性和精确性。

基于图的方法是一种非常重要的半监督学习方法。该类方法利用有标记和未标记数据构建图结构，并且根据图上的邻接关系将标记从有标记样本向未标记样本传播。根据标记传播方式的不同，可将基于图的半监督学习方法分为两大类：一类是通过定义满足某种性质的标记传播方式来实现显式标记传播，例如，基于高斯随机场与谐函数的标记传播、基于全局和局部一致性的标记传播等；另一类则是通过定义在图上的正则化项实现隐式标记传播，如通过定义流形正则化项，迫使类别预测函数对图相互靠近的样本输出相似的类别信息，从而将标记从有标记样本隐式地传播至未标记样本。

基于图的方法的核心是构建一个图模型，用有标记和未标记的样本点代表图中的顶点，边代表样本点间的相似度。这种学习方法一般假定模型满足两个条件：局部和全局一致性假设。局部一致性表示图中距离较近的样本点间具有相同的标识，全局一致性假设表示图中同一个流行结构内的样本具有相同的标识。基于图的方法可被视为在图中估计一个标识函数，该函数应同时满足两个条件：对于已知的标识样本，由此函数估计出的标识应与给定的一致；在全图中，此函数必须是平滑的，即应有连续的一阶和二阶偏导数。目前，一些较成熟的基于图的方法的不同之处主要在损失函数和规划项的选取上。例如，Blum和Chawla等人提出的最小图切割法（Graph Mincut），Ghahramani等人提出的离散马尔可夫场方法，Zhu等人提出的高斯随机场及调和函数，Zhou等人提出的正规化拉普拉斯算法，Belkin等人提出的拉普拉斯流行规划方法。此类方法也存在一些需要改进的地方，如选取什么样的图模型、图中的参数如何确定等。

1.4.2　图的构造方法

我们首先对图要有一个初步的认识，怎样构建图模型？什么样的图模型可以称为好的图模型呢？一个好的图模型应该能反映出该图模型所用领域的先验知识。大部分基于图的方法可以视为在图模型基础上估计函数，我们希望此函数能满足两个条件：对于已知的标识样本，用它估计出的标识必须与给定的非常接近；它在图中必须是光滑的，即必须有连续的一阶和二阶偏导数。如果从图规划角度来看待这个条件，这两个条件分别相当于依据图模型构建适当的损失函数和规划函数。目前，各种基于图的半监督学习算法主要区别在于，它们选取何种损失函数和规划函数。当前图模型的设计问题是一个值得考究的方面，图模型设计好后，需要实践者即时反馈实验情况，如此理论与实际不断促进，来为得到更好的基于图模型的半监督学习算法服务。查阅资料发现，常用的图模型如下［45］。

（1）全连接图。顾名思义，就是将所有结点都两两相连，图中的边必须是带有权重的，如此相似的样本点才能具有大的边权重。全连接图的优势在于权重学习（具有不同的权重计算函数），使用它可以很容易得到超参数衍生图来更好地解决实际问题。不足之处在于，其计算复杂度较大（虽然我们可以使用一些快速计算方法）。大量实验已经表明，先验的全连接图的实验效果劣于稀疏图模型。

（2）稀疏图。我们可以使用k近邻图或者ε近邻图等方法来对相似度矩阵进行稀疏化处理，让有相似性的节点间对应的矩阵元素有数值，没有相似性的节点间的矩阵元素为0，以更好地反映样本内部的聚类信息。在稀疏图中，每个节点只与其他部分节点相连接，即有边权重，这样不仅减少了不同类别样本间的干扰性，而且在运算时能降低计算复杂度。此方法的不足之处在于，对于权重学习不好处理，如改变算法中的参数，样本的近邻点选取将发生变化，导致后续的优化难题。

（3）k近邻图。如果节点j是节点i的k个近邻点中的一个，那么i和j之间有边相连。k是控制图密度分布的参数，k近邻图具有良好的自适应尺度特性，因其近邻半径自动根据样本区域的密度大小进行适度调整。k选取过小会导致图中没有连接成分，就没有意义了。

（4）ε近邻图。如果节点j和节点i的欧几里得距离d（i，j）≤ε，那么它们之间则有边相连。参数ε控制近邻半径大小，虽然参数ε在实际中应该是随着样本密度连续变化的，但是我们搜索ε时是以离散值来不断寻优的，此过程的计算复杂度最大为O（n2）。

（5）tanh权重图。权重Wij=（tanh（α1（d（i，j）-α2））+1）/2。此双曲正切函数相当于近邻图中的近似，当d（i，j）＞＞α2，Wij≈0；d（i，j）＜＜α2，Wij≈1时，参数α1和α2分别代表伸缩范围和切割值。此图模型的意图是在α2切割范围内，对图进行一个软切割，来达到使图中距离近的节点相连，不同类的节点不相连。区别于ε近邻图，双曲正切图中的参数α1和α2是连续变化的，适合用梯度下降法来求最优值，方便实现。

（6）exp权重图。Wij=exp（-d（i，j）2/α2），此函数也是连续的，但是它在Y轴上的切割值不如tanh权重图那么明显，参数α为衰变因子，控制函数值下降的程度。如果d（i，j）为欧几里得距离，那么可以给样本的每个特征维都定义一个α。

以上是一些常见的构建图模型用来表征样本内部结构信息的方法，每种方法都有其对应的权重函数，都引入了自身的参数，这些方法的选取要视具体情况而定。从大量实验中已经发现，选用k近邻图方法时，k值选取偏小一些在各项综合指标中都获得了不错的效果。总而言之，构建图模型就是用一个n×n的权重矩阵W来描述图结构，如果图中节点i和节点j间没有边相连，则Wij=0。值得一提的是，权重矩阵W无须满足半正定条件。由于W中的元素都是非负且对称的，可以考虑将图拉普拉斯矩阵引入图模型中加以利用。

具体构建方法为：

给定一个数据集，其中，前l个是标记样本，其余的n-l个是未标记样本是标签向量，c表示类别数量，yij=1表示样本xi属于第j类；反之，则yij=0。定义一个无向图为G=（V，E），其中，是图中n个节点的集合，每个节点vi∈V一一对应于一个样本点xi∈X，是边的集合，eij是连接第t个节点和第Dii=∑jwij个节点的边，每条边eij都与一个权值wij相连接。是权值矩阵。

常见的图构造方法有k近邻图和ε近邻图。通常，图的构建有两个步骤：一是建立图的邻接结构；二是确定图的权值。

定义一个距离函数ψ：Rd×Rd→R，距离矩阵｛ψ|ψij=ψ（xi，xj）｝∈RN×N。

k近邻图构建如下。

（1）对任意一个样本xi选取与其距离最近的k个样本。

（2）计算样本xi到k个样本的相似度，并构建如下相似矩阵。

式中，N（xi）表示与样本xi距离最近的k个样本的集合。有时k近邻图不是对称的，有三种方法对其进行对称化：①互k近邻图，其权值矩阵为=min（W，WT）；②对称k近邻图，其权值矩阵为=max（W，WT）；③favored对称k近邻图（Symmetric-favored k Nearest Neighbor Graph），其权值矩阵为=W+WT。

ε近邻图构建如下，对于任意一个样本xi，计算其到各个样本的距离，并构建相似矩阵：

ε是一个任意选取的参数。在一般情况下，ε近邻图在实际情况中较少使用，因为不恰当的ε可能生成许多不连接的子图。

图权值的确定有多种方法，如高斯核函数法、Hein＆Maier相似函数法、局部线性嵌入法等。

高斯核函数法采用高斯核函数来计算样本之间的相似度：

式中，δ为核函数窗宽。

Hein＆Maier相似函数定义为：

式中，h（xi）是xi的k近邻距离。

局部线性嵌入法通过求解以下最优问题得到权值矩阵：

式中，‖·‖2表示·的2范式。

1.4.3　基于图方法在视频跟踪中的应用

图方法具有直观性和可解释性，且分类能力较一般方法强，同时基于图的方法是一种重要的半监督学习方法，能有效利用标记和未标记样本的综合信息，图方法已经在维数约简、音素识别、人脸识别、图像分类、一般分类问题中得到广泛应用。

目标跟踪是计算机视觉领域一项基础而重要的课题。虽然经过数十年的研究发展，但目标和背景动态变化，例如，光照变化、遮挡、形状变化、相似物体的出现等，目前目标跟踪仍然是一项非常艰巨的任务。在线学习是处理目标和背景动态变化的一种有效方法。根据学习对象的差别，在线学习目标跟踪方法可以分为产生式方法和判别式方法。产生式方法重在对目标进行准确建模，而忽视目标所处背景的信息。判别式方法则将目标跟踪问题看作目标或背景的两分类问题，着重关注如何建立合适的分类器，以区分候选区域是目标还是背景。然而在缺乏足够数量的训练样本时，传统有监督分类器的性能受影响较大，从而影响跟踪精度，半监督分类方法正是针对这一问题提出的。半监督分类方法不仅利用有限的标记样本，而且综合考虑包括标记样本和未标记样本在内的样本集的内在结构特征，从而提高在标记样本有限情况下的分类准确率。

在视觉目标跟踪中，因为目标和背景的动态变化，要获取准确和充足的反映目标信息的标记样本是比较困难的。但目标和背景之间具有一定差别，因此大量既包含目标又包含背景的未标记样本可以借助样本集合的内在结构特征，提高在标记样本有限条件下的分类准确率，从而提高跟踪的精度。目前，大部分判别式跟踪方法仅利用了有限的标记样本进行监督学习，而忽视了大量作为未标记样本的候选区域所提供的信息，影响了跟踪的鲁棒性和精确性。