流形表面上基于测地距离的K-means聚类多样化检索方法

摘要

本发明公开了一种流形表面上基于测地距离的K-means聚类多样化检索方法，具体包括以下步骤，提取特征，训练并生成多个不同参数的SVM，选出最佳SVM；提取输入图像特征并用最佳SVM执行检索，产生结果排序；利用DB指标选择缓冲池大小值及k近邻的k值；训练集的类空间划分，改进的K-means聚类法；利用测地距离得出最靠近各聚类中心的图像，然后导出最终排序。本发明用基于内容的图像检索技术，自动实现对图像识别和检索，很好的选取最优参数，并在保证相关性的前提下，实现检索结果的多样性，为用户隐藏雷同或近似雷同的检索结果，提取了具有代表性的结果，在尽可能短的时间为用户提供更多样化的信息。

说明书

技术领域

本发明涉及图像的多样化检索系统，特别涉及一种流形表面上基于测 地距离的K-means聚类多样化检索方法。

背景技术

图像的多样化检索研究的对象是：如何在图像检索中令新颖的、独特 的、非重复冗余的图像在检索结果中排序靠前。多样化图像检索系统 的应用领域主要包括：图像电子设备应用、互联网图像搜索、医学图 像检索、商业信息检索、遥感信息侦查等等。近年来，随着诸如扫描 仪、数码相机、数码摄像机等数字化设备的快速发展和普及使用，以 及多媒体技术的提高和Internet的迅速普及，使得图像数据呈现几何 级数的增长，于是出现了大容量的图像及海量的视频数据库，面对日 益庞大的信息海洋,如何有效地组织、管理和检索大规模的图像数据成 为迫切需要解决的问题，如果能够在检索的过程中自动筛选有用信息 ，尽量可能避免向用户提交雷同或者近似雷同的检索结果，无疑会提 高信息检索和浏览的效率，节约大量的时间。因此，多样化图像检索 技术的研究有着重大的现实意义，一旦研究成功并投入应用，将产生 巨大的社会和经济效益。

一般的图像检索技术都着重于提高检索结果的“概念”相关性，并不 注重结果的“新颖性”，致使检索的结果产生大量的冗余信息，一个 好的搜索引擎应该能自动去除这些冗余信息，理想情况下，用户所“ 关注”的检索结果中排名靠前的图像列表应该是对“概念”的全面覆 盖，也就是说，能够尽可能覆盖检索“概念”的所有“子概念”，这 样，当不同应用背景的用户输入相同的检索信息或者输入的检索信息 比较模糊时，多样化的检索结果就更能满足他们的潜在需求。如何迅 速而准确地从浩瀚的图像数据库中检索到用户所需要的图像也成了近 二十年来多媒体领域的研究热点。同时，在传统的聚类方法中，计算 点到中心的距离通常用欧氏距离，在具有潜在流形的结构中并不合适 ，并且，如今对于评价聚类的好坏并没有合适的指标，本发明将针对 上述问题提出解决方案，进而解决在保证概念相关性的前提下增加多 样性的问题。

发明内容

本发明的目的是提出一种流形表面上基于测地距离的K-means聚类多样 化检索方法，该方法结合了基于内容的图像搜索技术和基于测地距离 的K-means聚类算法，并创造性的提出了将测地距离引入DB指标，并用 于实验中的参数选择，能够有效地提供一种针对保证图像检索相关性 的前提下的增加搜索结果多样性的检索方法。

本发明的技术方案是：

流形表面上基于测地距离的K-means聚类多样化检索方法，其特征在于 ，具体包括以下步骤：

（1）首先对训练数据集进行特征提取，利用有不同的参数的SVM分类 器对提取的特征进行训练学习；

（2）用认证集数据对SVM分类器的参数进行筛选，选出最优参数作为 最佳SVM分类器；

（3）对输入的测试图像进行特征提取，并作为最佳SVM分类器的输入 数据，从而获得数据库中图像与输入图像之间的相关度大小排序；

（4）利用DB指标对缓冲池大小参数进行筛选；

选择缓冲池大小时，要用到两个评价指标：前n幅图像的检索精度Pn， 以及前n幅图像覆盖的子概念数CRn；通过SVM分类器检索之后，设置候 选缓冲池大小为多组数值，并对缓冲池中图像数据分别进行聚类，计 算DB值，比较结果，得出最优缓冲池大小r；

传统的DB指标计算使用的是欧式距离，本发明中使用测地距离替代欧 式距离，并应用于p值的选取以及缓冲池大小的选择，算法如下：

令C_j为向量的聚类，X_j是分配给C_i的一个n维特征向量；

$S_i=\sqrt[q]{\frac{1}{T_i}\underset{j=1}{\overset{T_i}{\Sigma }}{\left|d_G(X_j,A_i)\right|}^q}$

其中A_i是C_i的聚类中心，T_i是类i的大小，S_i是一种聚类内部的分散度 量, d_G(X_j,A_i)为两点间的测地距离；

$M_{i,j}=\left|\right|A_i-A_j|{|}_p=\sqrt[p]{\underset{m=1}{\overset{n}{\Sigma }}{\left|d_G\left(a_{m,i}{a}_{m,j}\right)\right|}^p}$

其中M_i,j为C_i与C_j间的距离大小；a_m,i是A_i中的第m个元素，并且A中有n个 这样的元素，这里的m表明数据的特征，并且M_i,j本质上是当p=2时，类 i和j的中心之间的测地距离；

根据定义，M_i,j表示第i个聚类和第j个聚类的距离，理想情况下，是使 各类间的散度最大， S_i表示类i的类内散度，应使其尽可能小；

（5）对相关度大小按降序排列，选取缓冲池中的图像，利用DB指标对 改进的K-means聚类的p参数进行选择，从而获得此部分图像的各聚类 中心；

①k-means聚类方法的目标是将流形上的一组样本点（X1，X2，...  XN）（其中每个样本点是一个d维的实向量）分割为k个类集（k<=n） ，类集为S={S1，S2，…Sk}，计算数据点到该数据点所在类中心的流 形表面距离，使所有点距聚类中心的测地距离值最小：

$\underset{s}{\arg \min }\underset{i=1}{\overset{K}{\Sigma }}\underset{X_j\in S_i}{\Sigma }{\left|\right|d_G(X_j,{\mu }_i)\left|\right|}^2$

其中，μ_i 是类集，S_i的平均值，d_G(X_j,A_i)为两点间的测地距离；

算法流程描述如下：

首先输入：t, data[n]；

1） 选择t个初始中心点，例如c[0]=data[0],…c[k-1]=data[t-1]；

2） 对于data[0]….data[n], 分别与c[0]…c[t-1]比较，若与c[i ]沿流形表面的距离最小，就标记为i；

3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j] 之和}/标记为i的个数；

4） 重复2)、3),直到所有c[i]值的变化小于给定阈值；

② p值的选取：

根据前面所得，固定缓冲池大小为r，为了找到每个主题的最优参数p ，我们采用不同的p值系统的计算了图像集之中的不同主题类别的DB指 标，我们设置p值为不同数值，得到不同p值下不同主题所对应的DB值 ，从而选择出参数p；

（6）利用测地距离得出流形上距每个聚类中心最近的图像；

（7）得到最终排序。

SVM是支持向量机Support Vector Machine；DB评价指标Davies B ouldin index，也称为分类适确性指标；K-means算法是硬聚类算法 ，是典型的局域原型的目标函数聚类方法的代表，它是数据点到原型 的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运 算的调整规则。

关于测地距离,对于在一个非线性流形上的数据点，两点之间的距离应 该是流形上的测地距离，即沿着流形表面的距离而不是直接的欧氏距 离。这种方法的重点在于找出潜在的几何流形，从而得出每两点之间 的测地流形距离。我们把测地距离定义如下：对于相邻数据点，以欧 氏距离作为测地距离；对于较远的点，我们用相邻点的线段连线作为 测地距离，实际中，我们也可以有效地找到相邻点间的最短距离，从 而近似计算出测地距离。

本发明的有益效果是：

本发明用基于内容的图像检索技术，自动实现对图像识别和检索，很 好的选取最优参数，并在保证相关性的前提下，实现检索结果的多样 性，为用户隐藏雷同或近似雷同的检索结果，提取了具有代表性的结 果，在尽可能短的时间为用户提供更多样化的信息。

附图说明：

图1是本发明的方法流程图。

图2是ImageCLEF2008图像检索中的一个图像样例。

图3为本发明实验结果对比图。

具体实施方式：

如图1所示，流形表面上基于测地距离的K-means聚类多样化检索方法 ，具体包括以下步骤：

（1）首先对训练数据集进行特征提取，利用有不同的参数的SVM分类 器对提取的特征进行训练学习；

（2）用认证集数据对SVM分类器的参数进行筛选，选出最优参数作为 最佳SVM分类器；

（3）对输入的测试图像进行特征提取，并作为最佳SVM分类器的输入 数据，从而获得数据库中图像与输入图像之间的相关度大小排序；

（4）利用DB指标对缓冲池大小参数进行筛选；

选择缓冲池大小时，要用到两个评价指标：前n幅图像的检索精度Pn， 以及前n幅图像覆盖的子概念数CRn；通过SVM分类器检索之后，设置候 选缓冲池大小为多组数值，并对缓冲池中图像数据分别进行聚类，计 算DB值，比较结果，得出最优缓冲池大小r。

传统的DB指标计算使用的是欧式距离，本发明中使用测地距离替代欧 式距离，并应用于p值的选取以及缓冲池大小的选择，算法如下：

令C_j为向量的聚类，X_j是分配给C_i的一个n维特征向量；

$S_i=\sqrt[q]{\frac{1}{T_i}\underset{j=1}{\overset{T_i}{\Sigma }}{|d_G(X_j,A_i)}^q}$

其中A_i是C_i的聚类中心，T_i是类i的大小，S_i是一种聚类内部的分散度 量,d_G(X_j,A_i)为两点间的测地距离；

$M_{i,j}=\left|\right|A_i-A_j|{|}_p=\sqrt[p]{\underset{m=1}{\overset{n}{\Sigma }}{|d_G(a_{m,i},a_{m,j})p}^{}}$

其中M_i,j为C_i与C_j间的距离大小；a_m,i是A_i中的第m个元素，并且A中有n个 这样的元素，这里的m表明数据的特征，并且M_i,j本质上是当p=2时，类 i和j的中心之间的测地距离；

根据定义，M_i,j表示第i个聚类和第j个聚类的距离，理想情况下，是使 各类间的散度最大，S_i表示类i的类内散度，应使其尽可能小；

（5）对相关度大小按降序排列，选取缓冲池中的图像，利用DB指标对 改进的K-means聚类的p参数进行选择，从而获得此部分图像的各聚类 中心；

①k-means聚类方法的目标是将流形上的一组样本点（X1，X2，...  XN）（其中每个样本点是一个d维的实向量）分割为k个类集（k<=n） ，类集为S={S1，S2，…Sk}，计算数据点到该数据点所在类中心的流 形表面距离，使所有点距聚类中心的测地距离值最小：

$\underset{s}{\arg \min }\underset{i=1}{\overset{K}{\Sigma }}\underset{X_j\in S_i}{\Sigma }{\left|\right|d_G(X_j,{\mu }_i)\left|\right|}^2$

其中，μ_i 是类集，S_i的平均值，d_G(X_j,A_i)为两点间的测地距离；

算法流程描述如下：

首先输入：t, data[n]；

1） 选择t个初始中心点，例如c[0]=data[0],…c[k-1]=data[t-1]；

2） 对于data[0]….data[n], 分别与c[0]…c[t-1]比较，若与c[i ]沿流形表面的距离最小，就标记为i；

3） 对于所有标记为i点，重新计算c[i]={ 所有标记为i的data[j] 之和}/标记为i的个数；

4） 重复2)、3),直到所有c[i]值的变化小于给定阈值；

② p值的选取： 

根据前面所得，固定缓冲池大小为r，为了找到每个主题的最优参数p ，我们 采用不同的p值系统的计算了图像集之中的不同主题类别的DB指标，我 们设置p值为不同数值，得到不同p值下不同主题所对应的DB值，从而 选择出参数p；

（6）利用测地距离得出流形上距每个聚类中心最近的图像；

（7）得到最终排序。

图2是本发明实验时样例。图2中为测试集图像中的一张图片。每个主 题都由3张图片构成了一个图像检索的训练集。在本例中，对于检索我 们只考虑视觉部分，而不考虑文件描述。

图3是本发明的实例结果前后对比图。用本发明方法的聚类算法进行多 样化学习前（左）后（右）的结果比较。检索概念为“体育场”，左 图为SVM分类器的检索结果前20幅图像，其中子概念“足球场”重复了 2次，“室外网球场”重复了3次，“室内网球场”重复了6次；右图为 经过流形表面上的改进的k-means聚类算法进行多样化学习后的结果前 20幅图像，不仅消除了大部分的重复冗余图像，而且增加了一些新的 子概念结果，如第9幅为“室外体育馆”总体外观图，第11、16幅为“ 公路自行车赛道”，第13幅为“室外马球馆”，第18幅为“赛马体育 馆”。