5.8.3 基于测地距离的相似性度量
为了更好地反映数据集内部的结构信息，本节采用测地距离[75][76]来作为改进AP算法的相似性度量方法。图5.57中给出了数据点i和数据点j的欧式距离dE(pi，pj)和测地距离dG(pi，pj)，其中，测地距离(折线)不仅连接了数据点i和数据点j，而且中途还经过了4个数据点。如果将图中的6个数据点看成一个拓扑结构，那么数据点i和数据点j的测地距离dG(pi，pj)实际上就是i和j的最短路径。显然，和欧氏距离dE(pi，pj)相比，测地距离dG(pi，pj)更能反映数据集内部的线性结构信息。
图5.57 欧氏距离与测地距离对比
(1)测地距离生成
另外，除了考虑数据点之间的距离信息，将数据点之间的大小差异和时间差异考虑在内也非常有必要。接下来，将介绍如何利用测地距离对本节中的待分类数据集进行相似性度量。首先，将5.6.3 节提取到的数据集
构成一个加权连通图G=(V，E)。其中，顶点集合(即下标序列号集合)为V={1，…，NL}，边集合为
。在加权连通图G 中，顶点i与j所成的边为eij(eij与eji等价，为无向图)，其大小也就是加权值。一般情况下，eij的大小是顶点i与j之间的欧氏距离。但是在本节中，不仅仅要考虑欧氏距离，还要考虑数据点其他特征信息的差异，如公式(5.62)、公式(5.63)和公式(5.64)所示。
其中，(xi，yi)是数据点i的中心坐标，ai是数据点i的面积大小，li是数据点i的瞬时标签(所在图像帧序列号)。数据i与数据j所成的边eij的大小最终由dE(pi，pj)、dA(pi，pj)与dT(pi，pj)共同决定。
接下来，根据生成的连通图G 得到最小生成树(minimum spanning tree，MST)。所谓最小生成树其实就是最小权重生成树的简称。如图5.58所示，任意一个无向加权连通图都可以有多个生成树，但是其最小生成树只有一个，就是所有权重之和最小的生成树。生成最小生成树的方法很多，本节选择比较经典的Prim 算法，其具体做法如下：
步骤1：初始化描述最小生成树的顶点集合Vnew={r}和边集合Enew=Φ。其中，r为原始顶点集合V 中的任一顶点(最小生成树的起始点)；
步骤2：在原始边集合E 中选取权值最小的边euv，其中u 为集合Vnew中的元素，而v为原始顶点集合V 中的元素，但不是Vnew中的元素；
步骤3：将v加入到集合Vnew中，将euv加入到集合Enew中；
步骤4：重复步骤2和步骤3，直到Vnew=V。那么使用集合Vnew和Enew就可以描述所得到的最小生成树了。
图5.58 无向加权连通图与其最小生成树
图5.59给出了连续10帧药液图像累积图的最小生成树。图中任意两个目标距离是其最小生成树中该两点之间的最短路径，和欧氏距离相比，最小生成树中的最短路径能够更好地反映数据点之间的结构信息，最大化了数据点之间的差异。
根据得到的最小生成树来计算任意两个顶点之间的最短路径(各边上权值之和最小的一条路径)。同样，解决最短路径的问题也有多种方法，如Dijkstra算法、Bellman-Ford算法、Floyd算法和SPFA 算法等。其中，本节采用Floyd算法来计算数据点i和数据点j的最短距离dmin(pi，pj)，具体做法如下：(https://www.daowen.com)
步骤1：初始化所有之间相连的顶点之间的最短路径dG(pi，pj)为他们的边长权重eij，即dG(pi，pj)=eij，其中eij∈Enew；
步骤2：对于eij∉Enew，遍历所有中间节点k，使其满足：
图5.59 异物目标最小生成树
重复步骤2直至求得所有数据之间的最短路径。
(2)测地距离修正
根据异物目标的运动特性，同一异物目标在相邻图像帧中的运动距离是有限的。因此，如果生成的测地距离中，有两个数据点的距离相对较大(如图5.60所示的纵向线段)，那么很可能这两个数据点属于两个不同的异物目标。另外，在异物目标的最小生成树中，正常情况下每个节点最多与两个节点相连构成一条没有分叉的路径。当路径发生分叉的时候，必然有某个节点与不少于两个节点相连(如图5.60所示横向线段相连的节点)。可以很容易判断，这种发生分叉的情况一般都是当由两个异物目标组成的轨迹相近相连的时候。因此，希望能够尽量避免这种情况，从而最大化不同类之间的差异，避免聚类的时候产生误差干扰。
对于图5.60中的蓝色路径，本节采用设定阈值的方法来判断是否要进行修正。首先计算所有测地距离的均值ωavg，然后设定阈值T=δ×ωavg。其中，权值a 要根据反复实验来选取。当dG(pi，pj)＞T 时，则dG(pi，pj)=+∞。
图5.60 干扰路径示意图
对于图5.60中的纵向路径，本节根据异物目标的运动惯性来对多余的纵向路径进行修正。如图5.61所示，来自第k 帧的节点pj分别与来自第k-1帧的节点pi、第k+1帧的节点ps和pt相连，从而产生了分岔路径。因此，需要根据从pi到pj的运动矢量vi，j来估计与pj最合适的连接节点。首先将pi到pj的运动矢量vi，j平移，与pj到ps的运动矢量vj，s和pj到pt的运动矢量vj，t进行比较，分别计算它们的方向夹角θi，j，s和θi，j，t[θi，j，s=∠(vj，s，vi，j)，θi，j，t=∠(vj，t，vi，j)]并进行比较。与pj方向夹角小的节点应该被保留下来，剩下的节点与pj的测地距离被置为+∞。
图5.61 异物目标的运动惯性
经过两次修正，得到了最终的测地距离。接下来就可以建立相似性矩阵[si，j]NL×NL，其中[si，j]表示为：
