海量图片快速去重技术千里马论文.docx

海量图片快速去重技术　　针对海量图片中的去除重复图片效率低的问题，提出一种基于图片特征的并行化海量图片快速去重技术。首先，对图片提取图片颜色、纹理、形状等特征，用来全面描述图片;其次，使用度量标准对图片之间的特征距离进行度量计算;最后，利用如果两个点到任意一点距离相等则这两点有可能是同一个点的思想实现根据特征距离对重复图片的快速定位，达到重复图片检测与去重的目的。结合实验计算机网络数据分析验证该技术不仅能够准确地去重图片，且采用i5四核处理器的单机计算方式仅10min左右即可处理500万级图片量，与一般的两两计算相比，提高了海量图片去重的时效性，使得计算时间大幅度缩短。　0引言　随着数据的指数级增长，企业面临的快速备份和恢复的时间点越来越多，管理保存数据的成本及数据中心空间和能耗也变得越来越严重。研究发现，应用系统所保存的数据中高达60%是冗余的，缩减数据占用空间，降低成本，重复数据删除技术此句不太通顺，请作相应调整。已成为一个热门的研究课题。所以，重复数据删除技术就成为了缩减数据占用空间及降低成本的重要手段之一。目前重复数据删除技术主要包含相同数据检测及相似数据检测两大类，其中相同数据检测[1-3]的方法主要有完全文件检测技术、固定分块检测等，这些检测方法主要通过hash技术进行数据挖掘;相似数据检测利用数据自身的相似性特点，通过shingle技术[4]、bloom filter技术[5]及模式匹配技术[6-7]等挖掘出重复数据。这些技术使得共享数据块的文件之间产生了依赖性，降低了系统的可靠性;同时因为数据检测对比等过程导致大量的计算开销，对系统的性能影响也很大。因此，为了提高检测速度，降低对系统的性能影响，很多学者提出了并行化处理方式[8-10]。　由于图片文件的数据量大且不易修改的特性由于图片文件的数据量大其不易修改的特性，若采用文件级去重则计算开销大，效率较低，而块级则容易导致图片读取不完整、删除错误、恢复图片困难等问题，在海量图片的情况下这些问题将更加突出。针对上述问题，文献[11]提出一种针对海量图片文件存储去重技术的方法，利用MD5(MessageDigest Algorithm 5)特性在图片文件上传存储过程中实现去重取得了较好的效果。本文则针对已存储的海量图片，提出一种并行化快速去重算法：主要提取图片本身具有的数据特征，根据特征进行重复检测，实现海量图片去重处理，其时间复杂度为Ο(n2)。进一步，为了降低算法时间复杂度，本文针对该算法进行改进，将时间复杂度降低为Ο(n log n)，实现了海量图片的快速去重。　1.1颜色特征提取方法　颜色是图像最直观的特征，也是图像视觉重要的感知特征之一。HSV(Hue， Saturation， Value)颜色模型由色度H、饱和度S、亮度V三个分量组成，和人的视觉特性比较接近，所以选择在HSV空间提取颜色特征.为减少高维数特征对计算带来的不便，进行如下量化[12]：　再按式L=7H+3S+1V转化成一维特征量。传统颜色直方图只是每种颜色的量的统计，忽略了图像中每种颜色的分布方式。文献[12]提出一种环形区域划分的思想，将图片空间划分成M个同心圆环及外围区域，以(C，D)为图片几何中心，中心圆半径为R=[min(A，B)]/(2M)，其中(A，B)为图片边长，其他圆形半径为MR，其中取M=2。本文同样选择M=2，将图片区域被划分为中心圆、圆环和外部3个区域。这样既能够不增加特征向量的维数和计算成本，同时与传统颜色直方图相比颜色空间分布信息得到充分利用。所以提取累加直方图作为颜色特征，每个区域提取58个，共提取174个颜色特征。 　1.2纹理特征及形状特征提取方法　小波分析往往具有多尺度以及多方向性的特点，已经被广泛应用到图像纹理特征提取及形状特征提取方面的应用[13-14]。本文首先采用Mallat小波分解，得到分解层上的高频子带图像能量和低频子带上灰度共生矩阵统计量作为纹理特征特征向量;同时得到分解层上的高频子带图像均值、标准差和低频子带图像Hu不变矩的10个相对矩作为形状特征向量。Mallat在多分辨率分析中采用了离散框架小波变换。多次小波分解的分解系数是一组有关离散高通滤波U(n)和低通滤波G(n)的递推关系式，其计算方式如式(4)和(5)所示：　特征提取过程如下：　1)根据Mallat分解方法，对图片进行4个子带的分解。　2)继续对低频子图像进行小波变换，得到更多级别的分解子图像。第i级别j子带的能量表示为：　ENij=1n∑nk=1Cij(k)2(7)　其中：Cij(k)为该子带上的小波系数;n是j子带的小波的系数个数，将能量作为特征矩阵的元素构造特征向量。　3)继续对低频子图像进行小波变换，对每层低频子图像计算Hu不变矩的10个相对矩[14]：　4)在低频子带上依