网络图像搜索中的图像摘要技术研究(5)
2.2 图像相似度的计算方法
根据2.1节的介绍，我们得到了5种低层的图像特征向量，为了弥补各特征的局限性，以便更全面的描述图像的特征，我们将这五种图像特征进行融合，本文采取的方法是将五种图像特征拼接成高文向量，用高文向量做图像的新特征，进而用来计算相似度。
关于特征相似关系的理论研究通常使用的是几何模型，将图像的特征看作是特征空间中的点，两个点的接近程度通常用它们之间的距离来表示，即它们的相似距离[13]。所以我们就用5种图像特征融合后的高文向量的距离，来作为图像的相似度。距离函数有多种形式，如Mahalanobis距离、欧氏距离等。本文用欧氏距离算法来计算图像的相似度。
欧氏距离(Euclidean distance)也称欧几里得度量、欧几里得度量，是一个人们通常采用的距离计算公式，它是在m文空间中两个点之间的真实距离。在二文中的欧式距离的就是两点之间的距离，如下所示：
（9）
推广到N文空间，欧氏距离公式如下所示： （10）
其中，N表示文数； 表示第一个图像中点的第i文坐标， 表示第二个图像中点的第i文坐标。欧氏距离是简单的距离公式，也是在图像检索系统中应用较广的距离公式。
2.3 AP聚类算法
聚类(clustering)是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。聚类分析的算法可以分为：划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。经典的K-means和K-centers都是划分法。本文使用的是一种新的聚类算法：AP聚类算法。
Affinity Propagation(AP)聚类[2]是2007年在Science杂志上提出的一种新的聚类算法。它根据N个数据点之间的相似度进行聚类,这些相似度可以是对称的,即两个数据点互相之间的相似度一样(如欧氏距离);也可以是不对称的,即两个数据点互相之间的相似度不等。这些相似度组成N×N的相似度矩阵S(其中N为N个数据点)，这个相似度矩阵就是AP聚类算法的输入，经过AP算法最终找到最优的聚类中心点，即每个类中所有点到该类的聚类中心的相似度之和最大。
AP聚类算法中传递着两种类型的消息,代表度(responsibility)和适合度(availability)，r(i,k)表示从点i发送到候选聚类中心k的消息,反映点k作为点i的聚类中心的代表程度（如图2.3-1）。a(i,k)则从候选聚类中心点k发送到点i的消息,反映点i选择点k作为其聚类中心的适合程度（如图2.3-2）。r(i,k)与a(i,k)的计算公式为：
对于k点来说，r(i,k)与a(i,k)越强,则k点作为聚类中心的可能性就越大,并且i点隶属于以k点为聚类中心的聚类的可能性也越大。AP算法通过迭代过程不断更新每一个点的代表度和适合度,直到产生m个高质量的聚类中心点,同时将其余的数据点分配到相应的聚类中。
AP聚类算法不需要事先设定聚类个数，其聚类个数不仅与数据点的消息传递有关，还与输入的参考度（preference）有关。如果参考度事先设定成为一个共享值，则所有数据点成为聚类中心的机会是一样的。参考度越大，则聚类数目越少，我们可以通过调整参考度的大小来调整聚类的数目，参考度可以设为相似度的平均值（结果为中等规模的聚集）或者最小值（结果为小等规模的聚集）。
图2.3-3 当参考度p=10*平均相似度时，关键字“house”的图像摘要结果
下一篇：基于图的聚类算法研究+文献综述