一种基于分层聚类的均衡图像聚类方法

摘要

本发明公开了一种基于分层聚类的均衡图像聚类方法，本发明针对服饰类商品图像高维特征数据，采用基于层次聚类的方法，获得大小均衡的聚类簇，且单个聚类簇包含的数据量不超过限定的阈值。检索时，将被检索数据与所有聚类中心进行距离计算后，选取最近的多个聚类簇，在多个聚类簇内部进行数据遍历，获得最后的查询结果。相对于通用的基于聚类的索引方法，该方法避免了当被检索数据处于大聚类簇时遍历数据量过大的问题，保证了查询的性能。同时，通过遍历多聚类簇的方式，查询结果与SSA的查询结果有更高的重合度，提高了查询效果。

说明书

技术领域

本发明涉及图像搜索技术领域，尤其涉及一种基于分层聚类的图像高维向 量快速近似k-近邻检索方法。

背景技术

在基于内容的图像搜索技术（Content-Based Image Retrieval,CBIR）中， 当用户上传一幅商品图像并期望搜寻与该图相同或相近的商品时，搜索引擎对 用户上传的商品图像进行特征提取，并从索引图像特征矢量数据库中选取与其 在高维空间中距离最近的k个图像作为结果返回。在大量索引特征数据库中查 询最近的k个图像特征，最基本的方法是SSA方法。SSA方法通过计算被检索 图像与每一个已入库图像的距离，然后对这些距离进行排序的方式获得最近的k 个图像。这是一种精确的k近邻检索（k-Nearest Neighbor，kNN）。但是， 当图像特征维度以及库内图像数量较大时，该方法的查询耗时较大，无法满足 工程需要。

聚类的方法被引入CBIR中。采用聚类的方法，将数据按照其在高维空间的 分布，聚集成为聚类簇；检索时，首先计算被检索图像与所有簇的中心的距离， 确定被检索图像所属的聚类簇，然后对簇内的数据进行遍历，获得最近的k个 图像。由于需要遍历的数据量的减少，该方法相对于正向遍历的方式检索效率 有所提高，但是存在以下问题：

1、查询时间效率依赖于被查询图像所属的簇的大小，如果聚类产生的簇的 大小不均衡，会导致查询时间产生不均衡性。当被查询图像属于包含图像个数 较大的簇时，需要遍历的图像量及查询耗时增大。由于包含数据量大的簇代表 更“常见”的图像特征，被查询图像落在其中的概率大于包含数据量少的聚类簇。 因此，如果某个聚类簇包含的数据量远高于平均值，将会严重影响商品图像搜 索引擎的平均响应时间。

2、数据遍历被限定在簇内，如果有k-近邻数据处于其他簇中，则在检索结 果中被丢失，导致查询效果降低。

发明内容

本发明的目的在于针对现有技术的不足，提供一种优化的图像聚类方法。

本发明的目的是通过以下技术方案来实现的：一种基于分层聚类的均衡图 像聚类方法，包含如下步骤：

（1）在建立索引时，首先对图像特征数据进行初始聚类；

（2）对步骤（1）得到的每个聚类簇进行聚类切分操作。具体步骤为：检查该 聚类所包含的图像个数。如果该聚类中心包含的图像个数小于设置的上限N_top， 则在聚类内部进行二分聚类。如果二分聚类的结果包含的数据量仍超过N_top，则 对二分聚类的结果迭代此过程。将数据量不超过N_top的聚类簇中心记录到聚类中 心文件中。之后将该类目所有图像特征数据按照获得的聚类中心进行组织。 （3）在检索时，对查询图像的特征数据，计算其到所属类目的所有聚类中心的 距离，并且对这些距离进行升序排序，获取距离最小的前c个聚类簇标识，c值 由系统参数指定。之后在c个聚类簇的内部进行数据遍历，得到最后的查询结 果。

本发明的有益效果是，本专利针对服饰类商品图像高维特征数据，采用基 于层次聚类的方法，获得大小均衡的聚类簇，且单个聚类簇包含的数据量不超 过限定的阈值。检索时，将被检索数据与所有聚类中心进行距离计算后，选取 最近的多个聚类簇，在多个聚类簇内部进行数据遍历，获得最后的查询结果。 相对于通用的基于聚类的索引方法，该方法避免了当被检索数据处于大聚类簇 时遍历数据量过大的问题，保证了查询的性能。同时，通过遍历多聚类簇的方 式，查询结果与SSA的查询结果有更高的重合度，提高了查询效果。

附图说明

图1是商品图像特征数据索引建立流程；

图2是商品图像特征数据聚类切分流程图；

图3是商品图像特征数据入库流程图；

图4是检索流程图；

图5是二维情况下“边缘效应”示意图。

具体实施方式

下面以服饰类商品图像的聚类，索引建立、检索及维护为例，结合附图详 细描述本发明，本发明的目的和效果将变得更加明显。

如图1所示，本发明基于分层聚类的均衡图像聚类方法的索引建立包括如 下步骤：

步骤1：对商品图像进行图像特征提取，将图像数据转换成特征矢量数据。

特征提取的目的是获得图像的低级结构描述。通过d维矢量来代表各特征。

本发明采用的是图像的全局特征，即每一副图像对应一个高维特征矢量。 特征矢量的每一维数值都用来表征图像在某一个方面的特征，例如形状、颜色、 纹理、结构等信息。图像特征提取方法很多，MPEG-7视觉特征提取工具是一 种比较流行的方法。该方法包括颜色布局描述（Color Layout Descriptor,CLD）、 边缘直方图描述符（Edge Histogram Descriptor,EHD）等。其中，CLD使用8*8 DCT的12个系数，适合于很紧凑并且分辨率不变的颜色表示。EHD使用80个 直方图窗来描述来自16个子图像的内容。

为了便于数据存储和计算，我们将每一维特征值量化为[0,255]范围内的整 数。量化后的特征向量，每一个维度可以存储为一个字节。

步骤2：对步骤1得到的原始特征数据进行初始聚类，聚类中心个数设置为 一个较小的整数。对数据进行初始聚类的目的是为了大概体现出数据的分布状 态。聚类所使用的算法是k-均值（K-Means）。

K-Means算法将输入的n个数据对象划分为k个聚类以便使得所获得的聚 类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。

K-Means算法的主要参数包括：聚类个数k和距离公式d(x,y)。

由于只是对数据进行初始聚类，这里设置比较小的k值。我们希望在进行 初始聚类之后，每个聚类簇包含的平均数据量为一个固定的值N_s。初始聚类的k 值可以通过索引建立时的数据总量N_total和N_s算出：

$k=\frac{N_{\mathrm{total}}}{N_s};$

对于距离公式，通用的距离包括曼哈顿距离（L1距离）、欧氏距离（L2距 离）、马氏距离（Mahalanobis distance）等。距离公式不要求计算所有的特征维 度，可以选取特征向量中区分度较大的维度进行距离计算。对于同一类目，该 距离公式需要的后续的步骤中保持一致。对于不同的类目可以采用不同的距离 计算公式。

步骤3：对步骤2得到的数据进行聚类切分，如图2。即对步骤2获得的每 个聚类簇，进行如下操作：

步骤3.1：检查该聚类所包含的图像个数。如果该聚类中心包含的图像个数 小于设置的阈值N_top则跳转到步骤3.3，否则跳转到步骤3.2。

N_top的设定取决于服务器的计算及IO性能。由于高维空间距离计算的复杂 性，我们在计算的时候忽略距离排序及归并的计算量，而着眼于使单次查询距 离计算次数最小。设单次查询遍历的聚类簇个数为c。我们引入聚类簇平均饱和 度α，定义为平均每个聚类簇包含的数据量N_mean与N_top的比值：

$\alpha =\frac{N_{\mathrm{mean}}}{N_{\mathrm{top}}};$

因此，总的聚类簇的个数N_c：

在检索时，我们需要的距离计算包括两个部分：选取最近的c个聚类中心， 以及在c个聚类中心内部进行遍历。为了获得最近的c个聚类中心，需要的距离 计算次数等于聚类簇的个数N_c。在c个聚类中心内部进行遍历需要的距离计算 次数为c×N_mean。总的距离计算次数为：$C_{\mathrm{dis}}=N_c+c\times N_{\mathrm{mean}}=\frac{N_{\mathrm{total}}}{\alpha \times N_{\mathrm{top}}}+c\times \alpha \times N_{\mathrm{top}}.$当时，上式取得最小值。此时：

$\min \left(N_{\mathrm{top}}\right)=2\times \sqrt{N_{\mathrm{total}}\times c}.$

举例说明：对于某一类目包含5,000,000图像，单次查询遍历最近的8个聚 类中心，那么$N_{\mathrm{top}}=2\times \sqrt{5000000\times 8}\approx 1300.$

步骤3.2：在该聚类簇进行2聚类中心聚类。由于我们的目标是保证每一个 聚类簇包含的数据量不超过N_top。因此，对于包含数据量超过N_top的聚类簇，我 们在该聚类簇内部进行2个聚类中心的k-Means聚类。聚类的过程与步骤2相 似，区别在于这里的k值被强行设为2。聚类得到2个新的聚类簇，并且这两个 新的聚类簇包含的数据量仍可能超过N_top。对于数据量超过N_top的新聚类簇，重 复执行步骤3.2的操作，直到没有聚类簇包含的数据量超过N_top；

步骤3.3：对于包含数据量小于等于N_top的聚类簇，将该聚类簇的中心坐标 写入到聚类中心文件中。聚类中心的维数与特征文件的维数相等。为了保证精 度，我们将聚类中心的每一维数据保存为一个浮点数。一个聚类中心文件可能 包含多个类目的聚类中心数据，而一个类目包含多个聚类中心点的坐标。

步骤4：如图3所示，得到类目的聚类中心之后，我们需要对原始特征数据 按照获得的聚类中心进行重新组织，以便于检索时读取。具体的方法为，对于 原始特征文件中的每一个图像特征数据，计算其到该类目所有聚类中心的距离， 选取其中最小的距离，并且将该图像特征数据归属到最小距离对应的聚类簇特 征文件中。

步骤5：保存每一个聚类簇数据到硬盘文件。图像特征文件在硬盘上的存放 需保证同一个聚类簇的数据保存为连续的硬盘数据块。

如图4所示，本发明一种改进的图像聚类方法的检索包括如下步骤：

步骤6：加载聚类中心数据到内存；

对于每一次查询，商品所属类目的聚类中心数据都会被用来进行距离计算， 对于聚类中心数据的访问是非常频繁的。因此，聚类中心数据需要常驻在内存 中。

从步骤3.3的分析可知，平均每个聚类簇包含的图像个数为：N_top×α，对应 一个聚类中心。每个聚类中心坐标为d个浮点数，占用d*4个字节的内存。因 此，总共的内存占用为：

V_center=N_total/(α×N_top)×d×4；

例如，对于某一个类目的特征数据，N_total=5000000，N_top=2000，d=600， α＝0.6。那么存储该类目聚类中心所需要的内存空间约为10M字节。

步骤7：对被查询图像进行图像特征提取；该操作于步骤1完全相同，这里 不再赘述。

步骤8：对步骤7得到的图像特征数据，计算其到所属类目的所有聚类中心 的距离，排序后获取距离最小的前c个CID；

K-近邻检索的结果，在高维空间中，构成了一个以被查询矢量为球心的超 球。

传统的基于聚类的索引及查询方式，每次查询仅遍历与被查询图像最近的 聚类簇中的数据。如果被查询图像特征数据与其所属的聚类簇的中心较近，则 超球完全包含在该聚类簇的包络中。那么，即使只遍历最近的1个聚类中心， 也可以获得与全库正向遍历完全相同的查询结果。图5中的q₀展示了二维空间 中的这种情况。C0、C1、C2、C3、C4是5个聚类中心，q₀是被查询图像特征 矢量。在二维情况下，超球退化成一个以q₀为中心的圆。在图5中，以q₀为圆心 的圆完全处于C0聚类簇包络中。

如果被查询图像特征数据与其所属的聚类簇的中心较远，那么传统的聚类 查询方式会导致数据丢失。如图5中q₁所示，被查询图像特征矢量处于C1聚类 簇的边缘位置，查询结果超球同时与C1、C2、C3、C4四个聚类簇相交。如果 只遍历C1聚类簇，那么超球与C2、C3、C4相交区域的数据被丢失。这种丢失 效应可以称为“边缘效应”。

在高维度情况下，“边缘效应”被放大。设想一个空间包络为超球的聚类簇， 半径为r，那么该超球的体积为：

V(r)=a×r^d，

其中，α为常数因子。

我们定义到聚类簇中心的距离为r/2以内为离中心“较近”，那么这个“较近” 的区域体积为：

V(r/s)=a×(r/2)^d；

“较近”区域体积占整个超球体积的比例为：

$\frac{V(r/2)}{V\left(r\right)}=r\times 2^{-d};$

由于该比例随着维数d的增加呈指数降低，因此，在高维空间中，被查询 数据落在聚类簇边缘为常态，“边缘效应”无法被忽略。为了找回被“边缘效应” 丢失的数据，采用多聚类中心遍历的方式，可以显著的降低丢失的数据量。例 如在图5的例子中，同时遍历C1和C2聚类簇，查全率明显要高于仅遍历C1 聚类簇。而同时遍历C1、C2、C3和C4则可以获得与全库遍历相同的查询结果。

同时遍历多个近邻聚类簇会带来更大距离计算和数据IO开销，这个问题可 以通过控制N_top的方式，降低每个聚类簇所包含的数据量的方式来克服。

遍历近邻聚类簇个数c可以做为搜索引擎系统的可控参数。当硬件性能提 高或者系统负荷较低时，可以通过增大c获得更好的查询效果。当硬件性能下 降或者系统负荷较高时，可以通过减小c，牺牲部分查询效果以获得更好的查询 效率。

步骤9：对步骤8得到的每一个CID，从磁盘读取其相应的特征数据，计算 步骤7得到的图像特征数据与该聚类簇内部每一个数据的距离，将这些距离进 行升序排列，获得距离最小的k个图像的图像标识（Image ID，IID）及对应的 距离值；

本步骤包含大量的距离计算及数据读取。在步骤3.1中我们对距离计算量进 行了详细的讨论。这里我们更多考虑数据读取引起的硬盘IO开销。

设平均每个聚类簇包含的数据量为D（Byte）。硬盘的平均寻道时间为t_f， 数据读取速度为s_read。每个聚类簇的数据在硬盘上都是连续分布的。那么单次查 询的平均数据IO时间为：

$t=c\times (t_f+\frac{D}{s_{\mathrm{read}}})=c\times t_f+\frac{c\times D}{s_{\mathrm{read}}}$

对于一个应用实例，c＝8，D＝1MB。我们计算不同硬件条件下的数据读取 耗时。

如果数据存放于普通SAS（Serial Attached SCSI）硬盘，t_f的典型值为3ms， s_read的典型值为150MB/s。那么单次查询的数据读取耗时为：3*8+8/150*1000= 75ms。而对于固态硬盘（Solid State Disk,SSD）来说，t_f的典型值为0.1ms，s_read的典型值为500MB/s，单次查询的数据读取耗时为8*0.1+8/500*1000=17ms。

对于本发明所使用的结构来说，由于采用多聚类簇检索，会增加硬盘寻道 次数，此时SSD的低寻道时间特性会大大降低数据IO时间。由此可见，使用 SSD代替SAS硬盘，可以有效的节约数据IO时间，降低引擎的平均响应时间。

步骤10：归并步骤9中得到的c个IID序列，获取其中最小的k个IID及 对应的距离值，作为结果返回。

本发明优化的图像聚类方法查询结果与全库遍历的结果重合度更高；查询 耗时更短，更均衡；可以用简单的方式对查询效果和性能进行权衡。