5.8.2 改进的近邻传播聚类算法
采用AP聚类算法对提取到的潜在异物目标进行分类，根据分类结果的轨迹形状来进一步区分真实异物目标和残差噪声。但是，如果将标准的AP聚类算法不加改进直接用于异物分类的话，分类结果并不尽人意。在标准的AP中，数据点之间的相似度量采用的是负的欧氏距离，即sij=-‖xi-xj‖2。但是这种度量方法并不能够很好地反映数据集内部的拓扑关系。实际上，本节要进行分类的数据有一些特性可以加以利用得到理想的分类结果，这就是噪声与异物的轨迹差别。假设数据点i被认定为异物目标，那么可以推断在数据点i附近一定有与其形状大小都很相近的数据点存在，并与数据点i一起形成一条线性的轨迹。假设数据点i被认定为残差噪声，那么可以推断数据点i在其附近形成一个孤立点或者与其他一些形状大小相异的数据点形成一个分散的类。
图5.55 轨迹累积图
如图5.55所示的轨迹累积图，在图中有6条线性的轨迹，也就是有6个真实的异物目标存在(图中每个数据点的瞬时标签由灰度深浅表示，相同深色的数据点来自同一帧图像)。显然，每一条线性轨迹应该由来自不同图像帧中的数据组成，从而形成异物目标运动轨迹。另外，除了真实异物目标形成的运动轨迹，图中还存在一些噪声数据点，如图中标记的数据点a 到数据点h。观察A 区域中的数据点a，其形状大小与附近两条轨迹中的数据点差异较大并距离较远，所以只能成为一个孤立点。同理，在B 区域中，数据点b虽然与其附近的轨迹距离较近，但是形状大小差异过大，所以不应该被划分为同一类中。另外，数据点c，d 和e可能被划分为一类，但其结构并非线性的轨迹结构，所以也不可能是真实的异物目标。(https://www.daowen.com)
图5.56 标准AP聚类算法分类结果
图5.56给出了标准AP聚类算法对图5.55中的数据进行分类的结果，颜色相同的数据点属于同一类。在图中，原本属于同一轨迹的数据点被分割成两类，这是因为标准AP聚类算法的目标是最小化平方误差，当以数据点之间的欧式距离作为相似性度量方法时，AP聚类更适合处理那些呈团簇结构的数据集。
经过以上讨论分析，本节准备从两个方面对标准的AP聚类算法进行改进：相似性度量方法和约束方程。
