空间密度聚类在数字图书馆图像检索中的应用

王华秋王重阳聂 珍

（1．重庆理工大学计算机科学与工程学院，重庆400054；2．重庆理工大学图书馆，重庆400054）

空间密度聚类在数字图书馆图像检索中的应用

王华秋1王重阳1聂 珍2

（1．重庆理工大学计算机科学与工程学院，重庆400054；2．重庆理工大学图书馆，重庆400054）

图像聚类为数字图书馆图像管理提供了新的技术支持，能够在大量图像数据中发掘使用户感兴趣的信息。传统应用于图像聚类的特征提取算法往往忽略图像颜色的空间分布信息，且适应性较差。通过等面积矩形环对图像进行划分并计算各空间区域的相关性，并根据空间区域相关性计算各区域的重要性，将空间信息与颜色信息进行融合。同时对快速搜索密度峰值聚类算法的截断距离进行了合理改进，在保证聚类精度的同时提高收敛速度。最后将该密度聚类算法应用于数字图书馆图像检索之中。通过实验验证，本文提出的方法是可行的、有效的。

密度聚类；截断距离；空间相关性；数字图书馆；图像检索

随着数字图书馆图像采集技术以及存储技术的不断发展，图像数据正在以惊人的速度增长，越来越多的图像数据使之成为了传递信息的重要媒介。对于如此庞大的数据，如何有效地管理和检索，并从中获取潜在的信息及价值已成为研究者们研究热点。图像聚类通常应用于图像检索与图像管理之中，通过图像聚类可以有效地缩小检索范围，提高图像检索的效率，同时可以帮助数字图书馆图像管理者发掘感兴趣的信息。

合理有效的低层特征提取是提高图像聚类准确度的关键。颜色特征作为一种重要的视觉特征，被广泛的应用于机器视觉、图像检索等领域。与其它特征相比，颜色特征对于图像本身的大小、方向、角度等依赖性较小，鲁棒性较高。直方图法［1］是较为常用的颜色特征提取方法，但它并没有反映图像颜色的空间位置分布信息。进而有学者提出分块直方图法，将空间信息与颜色信息相融合，但分块直方图破坏了颜色特征本身所具备的旋转、缩放、平移不变性。就此，张鑫［2］等提出了一种矩形环结构的颜色分块方案，在考虑空间位置的同时保留了图像特征的旋转、缩放以及平移不变性。但其在为各区域块分配权重时简单假设图像的主体部分位于中心区域，各区域权重从中心至四周递减且固定不变，没有考虑到图像各区域间的相关性。因此，本文将图像区域间的相关性与颜色特征相结合，形成一种融入区域相关性的颜色特征提取方法。该方法利用等面积矩形环对图像进行划分并提取各区域特征，之后计算各区域之间相似度，根据区域间相似度计算各区域的权重。在计算图像间相似度时，将图像的区域相关性融入相似度计算之中，提高聚类准确度。

由于本文提出的特征提取方法得到的各区域权值是基于图像内容自动设定的，在进行聚类时，无法简单的通过计算各图像特征的质心来确定图像的聚类中心，因此本文选取基于图像间相似度的快速搜索密度峰值聚类（DP）算法实现图像聚类。DP算法是由Alex Rodriguez和Alessandro Laio等人于2014年提出的一种新型无监督聚类算法［3］，该算法无需预先指定聚类数目，在迭代过程中不断搜索合适的聚类中心，避免了聚类结果受初始类代表点影响的缺点。同时该算法在处理多类数据时运算速度较快，性能更优。基于以上原因，本文采用DP聚类算法对图像进行聚类，该算法根据相似度矩阵对各数据点进行划分。由于该聚类算法采用固定的截断距离，该系数过小会导致同一个簇中被拆分成多个，过大会导致聚类区分度不高［4］。因此本文自适应调整截断距离，使算法能够减少聚类的极端情况。

1 融入区域相关性的图像特征提取

1.1 颜色特征提取及其量化方法

常用的颜色空间有RGB颜色空间、HSV颜色空间等，但RGB颜色模型是基于硬件角度提出的，不能很好的与人眼感知相匹配，人眼的色彩感知主要包括色调、饱和度和亮度3个要素，因此，本文选取HSV颜色空间作为颜色空间模型。

为了减少颜色维度过高为计算带来的不便，本文对HSV颜色空间的h、s、v 3个分量按照人类对颜色的感知进行量化，将h分为7份依次代表红、橙、黄、绿、青、蓝、紫，s和v各分为3份。对处理后的h、s、v值进行非等间距量化，得到一系列离散值，从而便于对颜色特征进行统计和计算。具体量化方式如下：

式（1）中的H、S、V分别表示量化后的离散值，h、s、v为通过RGB值计算得到的HSV颜色空间连续值。根据量化后的H、S、V值对各分量进行线性组合，得到一维矢量L：

式（2）中Qs、Qv分别为饱和度（S）和亮度（V）的量化基数，本文中Qs＝4，Qv＝2，以减小亮度和饱和度对聚类结果的影响。量化后的特征值范围为［0，1，2，…，54］，即一副图像的每个像素点通过以上方法映射到55种颜色中。

1.2 区域相关性计算方法

传统的颜色直方图法仅仅对图像中各像素的颜色值进行统计和整理，并不考虑颜色的空间分布情况，为了使颜色特征更具代表性，并将空间信息与颜色特征进行融合，可以在统计颜色特征时对图像进行区域划分。均匀分块法［5］为一种常用的图像划分方法，但融入该方法的图像特征失去了本身所具备的旋转和缩放不变性，因此有学者提出矩形环法，该方法在保留了旋转和缩放不变性的同时能够反映颜色的空间分布情况，突出图像不同区域的重要性，但传统的矩形环划分法对不同区域的重要性采用固定值来表示，适应性较差，因此本文提出一种基于图像内容的区域相关性计算方法，并根据区域相关性自动调整各区域的重要性权值。具体方法描述如下：

首先按照等面积划分的方式用矩形环将图像划分为面积相同的不同区域，假设图像的长为l，宽为w，将图像划分为M个不同的区域，则矩形环的边长公式如下：

公式（3）中k表示从内到外划分图像的矩形环标号，划分方式如图1所示：

图1 等面积矩形环划分法

划分后对各区域分别赋予不同的权值，即wk，就一般情况来说，图像中的主体区域一般位于中心，而边缘部分为背景区域，因此wk一般呈中心高，边缘低的分布，但由于不同图像的主体区域所占面积不同，或图像各区域所反映的事物大致相同，所以采用固定的权值不具有普适性，因此本文根据图像各区域的相似性判断图像主体区域的显著程度及所在区域，并以此作为设定wk的标准。

由于累积直方图较传统直方图具有更好的鲁棒性［6］，本文统计图像I各区域的HSV颜色累积直方图作为图像特征，假设共将图像分为D个区域，区域k共有Nk个像素，颜色值为［0，1，…，54］，则区域k的颜色累积直方图Gk的计算方法如下：

其中ni为HSV颜色量化值为i的像素点的个数。区域m与n的相似度Sm，n计算公式如下：

公式（5）中L为HSV颜色空间的量化级数，本文为55。通过计算各区域之间的相似度，可以有效的描述图像的区域相关性。下面以将图像划分为3个区域为例说明通过图像的区域相关性计算各区域重要因子的详细过程。

如图1所示，假设从内至外分别表示区域1、区域2和区域3，一般情况下，主体区域分布于图像中心，而且主体区域之间相似度较高，背景区域之间相似度同样较高，主体区域与背景区域往往存在较大的差距。

通过分析可知，若区域1重要性权值较高，则说明主体部分集中于区域1，区域2与区域3为背景部分，即区域2与区域3相似度较高，而区域1与区域3，区域1与区域2相似度较低，因此w1正相关于S2，3，负相关于S1，2、S1，3。基于上述分析，本文定义区域1的重要性权值如下：

按照同样的分析方法，定义区域2与区域3的重要性权值如下：

为了体现图像的区域重要性一般从中心至四周递减，本文定义区域k的基础重要性影响因子，其中λ为中心重要性参数，λ越大则中心区域的重要性越高，反之重要性越低，本文中λ＝0.1。

计算出各区域权值之后，需要进行归一化处理，归一化方法如下：

将各权值收集至W便得到图像I的重要性向量：

表1给出了6张图片所对应的重要性向量：

表1 代表图像权值向量对比表

通过表1可以看出，本文提出的方法可以通过图像各区域的相似性计算出各区域的重要程度，从而反映出主体区域所在区域及所占面积。对于图像1、3、4，明显主体区域大部分位于区域1内，因此区域1权值较高，而区域2区域3的权值较低。对于图像5、6主体区域不够明显，由于基础重要性影响因子的存在，重要性权值仍然从中心至四周递减。

通过上述运算过程可以看出，本方法即保留了中心区域的重要性，又根据图像内容中各区域的相关性对各区域的重要性进行自动调整，提高了特征提取算法的鲁棒性及适应性。

2 图像聚类算法

2.1 快速搜索密度峰值聚类（DP）

以n个数据点两两之间的相似度组成的相似度矩阵sn×n作为算法的输入。给定用于确定截断距离dc的参数，计算每一个数据点i的局部密度ρi，原文中局部密度计算采用了cut－off函数，公式如下：

其中函数χ（x）定义如下：

得到ρi之后，需要对每一个数据点i计算i到任何比i密度大的点的距离的最小值δi，计算公式如下：

对于局部密度ρi最大的点，要对其δi进行处理，采取如下公式：

至此，对于每一个数据点i，得到两个值ρi和δi，如果该点同时具有较大的ρi和δi，那么该点很可能为聚类中心。在判断聚类中心时，将每一个点的ρi和δi按如下公式进行计算得到每个数据点i的密度峰值：

最终在得到每个数据点i的密度峰值γi之后，以ρi为横轴、δi为纵轴绘制决策图，用户自行选择γi值较高的点作为聚类中心，剩余的数据点则被归属到各自的有更高密度的最近邻点所属的类簇，类簇分布仅需这一步即可完成。

一个簇中的数据点可分为簇中心和离群两部分，前者局部密度较大，对应簇的核心部分，而后者的局部密度较小，对应簇的边缘部分，我们常说的离群点就分布在halo中，这里，如果hi＝1，则表示xi属于离群点，如果hi＝0，则表示xi属于簇中心。

2.2 DP算法的优化

DP聚类算法截断距离dc固定不变，参数dc的选取，从某种意义上决定着聚类算法的成效，取得太大或太小都不行：如果dc太大将使得每个数据点i的局部密度都非常大导致难以区分；如果dc太小则有很大可能会导致同一个类簇被拆分成多个。因此，找到一个合适的截断距离dc对DP算法有较明显的影响。

本文提出一种截断距离动态调整方案，在DP算法中动态调整截断距离，使之在保证收敛精度的同时具有较快的收敛速度。因此，我们加入了最后一步，就是剔除离群点，再转到公式（11）重新迭代DP算法。

假设共有n个数据点，两两之间的相似度组成相似度矩阵Sn×n，同时由于DP算法中往往以对角线上的数值S（k，k）作为数据点k是否成为聚类中心的标准，因此本文根据迭代过程中Sn×n对角线上数值之和的变化速度来确定截断距离的大小，具体方法如下：

式中dc0为初始截断距离，本文中dc0＝0.02，α和β为范围系数，用于调整截断距离的变化范围和变化速度，α越大，截断距离受迭代变化的影响越大，反之影响越小。β主要用于配合α，使得截断距离的变化范围在合理范围内，本文中α＝0.4，β＝0.5。

2.3 相似度矩阵的计算方法

相似度矩阵的计算是保证聚类精度的关键，为提高相似度计算的鲁棒性，本文提出一种融合区域相关性的相似度矩阵计算方法。该方法在计算图像间相同区域的相似度时，通过图像各区域的重要性权值调整各区域相似度对整体相似度的影响。

首先设图像k区域i的HSV颜色累积直方图为Gk（i），重要性权值向量为Wk，D为区域划分的总块数，则图像p和q在计算相似度时各区域的重要性权重Wp，q的计算方法如下：

则图像p和图像q的距离S′（p，q）的计算公式如下：

式中dis（Gp（i），Gq（i））表示图像p与图像q区域i累积直方图的欧式距离。最后需要对S′（p，q）进行归一化处理并取反，得到图像p与图像q的相似度S（p，q）：

其中S（p，q）＝S（q，p），且S（k，k）＝0，k＝1，2，…，N。

由式（19）可知，相似度计算时各区域的重要性权值与进行对比的两幅图片的重要性向量有关，通过式（18）和式（19）可以有效的减小主体区域分布不同的图像间的相似度，增加主体分布相似图像间的相似度，提高相似度计算的鲁棒性。

为了将图像聚类应用于图像检索之中，本文假设用户提供的图像为I，首先对图像I根据不同的特征提取方法进行特征提取，之后根据图像I与各个聚类中心的距离来判断图像I与哪个聚类中心最为接近。但由于DP聚类算法的聚类中心数是算法根据相似度矩阵自行得到的，其数量往往会多于实际类别数，因此只在与图像I相似度最高类中查找相似图像会将图像聚类产生的错误累积至图像检索，在这里本文找出与图像I相似度最高的3个聚类中心，分别为C1、C2、C3，则图像I与由C1、C2、C3所属的类中的所有图片进行相似度对比，按照相似度大小返回检索结果，整体流程如图2所示。

图2 采用聚类的图像检索流程图

3 实验与结果分析

3.1 实验环境

实验在Windows7 64位操作系统下进行，测试软件为matlab 2010b，实验的硬件环境为CPU：Intel（R）Core（TM）2 Duo，内存：4G。

3.2 聚类算法在图像检索中的应用

为验证本文提出的图像聚类算法在检索中的有效性，实验选用Corel库［7］作为测试图像库，其中包括Bus、Flower、Dinosaurs、Horse、Mountain、Sunset 6类图像，每类图像100张共600张图像作为图像库，其中每类抽取50张做180°旋转，每类中随机抽取10张作为查询图像。通过计算各类图像的查准率－查全率［8］来评价特征提取及相似度计算方法的性能。

实验对比全局HSV颜色直方图法（GH）、均匀分块HSV颜色直方图法（BH）、矩形环分块法（BCH）及本文提出的融入区域相关性的颜色特征提取方法（RBCH）所对应的检索精度。各直方图均采取累积直方图的方式。为了更加直观的比较各种方法，图3～图6给出了各种方法在查全率为给定值时所对应的查准率。

图3 查全率＝50%时查准率统计图

图4 查全率＝60%时各查准率统计图

图5 查全率＝70%时查准率统计图

图6 查全率＝80%时查准率统计图

根据图3～图6可以看出，RBCH法根据图像内容自动调整各区域的重要性权值，具有更高的适应性，更具体的描述了颜色的空间分布特性，在一定程度上提高了检索精度。GH法仅仅对全局颜色特征进行了统计，没有描述颜色的空间分布情况，检索精度较低。BH法能够更具体的描述颜色的空间分布情况，但由于实验中加入了旋转的干扰，检索精度有所降低。

为了对比聚类与未聚类对检索精度的影响，本研究以RBCH为特征提取方法，对聚类后的检索精度与未聚类的检索精度进行了比较，对比结果如表2所示：

表2 聚类与未聚类检索结果对比统计表

从表2可以看出，在查全率较低时，应用聚类算法的图像检索具有较高的查准率；而在查全率较高时，未应用聚类算法的图像检索具有较高的查准率，原因在于聚类算法能够将相似度较高的聚集在一起，在进行图像检索时只在与查询图像较为相似的类中查询，排除了大量图像的干扰，因此在查全率较低时查准率较高，然而由于聚类精度有限，有部分原本与查询图像相似的图像并不在查询库内，因此在查全率较高时，检索精度略低，但在检索时间上，应用聚类算法的图像检索效率要高于原始方法。

4 结 论

本文在传统颜色空间分布特征提取的基础上，提出了一种融入区域相关性的颜色特征提取方法，根据图像自身内容调整图像各区域的重要性权值，提高了特征提取算法的适应性，其重点在于区域相关性的提取以及与区域特征的融合方法，并没有引入复杂的特征提取方法。另外，考虑DP算法中截断距离dc对聚类的影响，提出了一种自适应调整方法，该方法使DP算法在保证收敛稳定性及准确性的同时，减少迭代次数，提高收敛速度。实验结果证明，本文提出的彩色图像聚类算法是可行的、有效的。接下来的研究将考虑引入更加高效的特征提取方法，同时将在大型图像数据库中进行实验，并根据数据量改进DP聚类算法使之适应数字图书馆图像数据库。

［1］Pin Liao，Yongjun Wang，Mingyan Wang，Siru Ding，Huimin Ma． An Effective Preprocessing Scheme for Face Recognition Based on Local Gabor Binary Pattern Histogram Sequence［J］．IEEE International Conference on Computer Science and Automation Engineering，Zhangjiajie，2012：581－585．

［2］张鑫，温显斌，孟庆霞．基于颜色特征的图像检索方法研究［J］．计算机科学，2012，39（11）：243－260．

［3］Alex Rodriguez，Alessandro Laio．Clustering by fast search and find of density peaks［J］．Science，2014，344（6191）：1492－1496．

［4］Xu R，Wunsch D．Survey of clustering algorithms［J］．IEEE Trans Neural Networks，2005，16（3）：645－678．

［5］Lincy Rachel Mathews，Arathy C．Haran V．Histogram Shifting Based Reversible Data Hiding Using Block Division and Pixel Differences［C］．2014 International Conference on Control，Instrumentation，Communication and Computational Technologies，Kanyakumari，2014：937－940．

［6］Li Xiao，Wang Weilan，Yang Wei．Improved local accumulate histogram－based Thangka Image Retrieval［C］．Image Analysis and Signal Processing，2010，（6）：318－321．

［7］James Z.Wang，Jia Li，Gio Wiederhold，SIMPL Icity：Semanticssensitive Integrated Matching for Picture LIbraries，IEEE Trans．on Pattern Analysis and Machine Intelligence，2001，23（9）：947－963．

［8］黄承慧，印鉴，候 ．一种结合词项语义信息的TF－IDF方法的文本相似度量方法［J］．计算机学报，2011，34（5）：856－864．

（本文责任编辑：孙国雷）

Application of Spatial Density Clustering in Image Retrieval of Digital Library

Wang Huaqiu1Wang Chongyang1Nie Zhen2
（1．College of Computer Science and Engineering，Chongqing University of Technology，Chongqing 400054，China；2．Library，Chongqing University of Technology，Chongqing 400054，China）

Image clustering of digital library can discover user interested information from large image database so as to provide a new technical support for image management．Traditional feature extraction algorithms which are applied to image clustering often ignore the space distribution information of image color，and have the poor adaptability．Images are divided by equal regional rectangle ring and regional spatial correlations are calculated，which is used to calculate regional importance to integrate spatial information with color information．At the same time，to ensure clustering accuracy and improve convergence speed，the cutoff distance parameter of the fast search density peaks clustering（DP）is improved reasonably．Finally the proposed clustering algorithm is used in image retrieval of digital library．Experimental results show that the proposed method is feasible and effective．

density clustering；cutoff distance；spatial area correlation；digital library；image retrieval

10．3969/j．issn．1008－0821．2016．02．025

TP391.41

A

1008－0821（2016）02－0129－06

2015－08－03

国家社会科学基金一般项目“数字图书馆智能图像检索系统研制”（项目编号：14BTQ053），重庆市研究生教育教学改革研究项目“研究生《大数据挖掘》课程案例与演示系统研制”（项目编号：yjg143090）。

王华秋（1975－），男，教授，博士，研究方向：图像检索、数据挖掘，发表论文6篇。