海量图片快速去重技术

来源:用户上传      作者: 韩逢庆宋志坚余锐

　　摘要：针对海量图片中的去除重复图片效率低的问题，提出一种基于图片特征的并行化海量图片快速去重技术。首先，对图片提取图片颜色、纹理、形状等特征，用来全面描述图片；其次，使用度量标准对图片之间的特征距离进行度量计算；最后，利用如果两个点到任意一点距离相等则这两点有可能是同一个点的思想实现根据特征距离对重复图片的快速定位，达到重复图片检测与去重的目的。结合实验数据分析验证该技术不仅能够准确地去重图片，且采用i5四核处理器的单机计算方式仅10min左右即可处理500万级图片量，与一般的两两计算相比，提高了海量图片去重的时效性，使得计算时间大幅度缩短。
　　关键词：
　　海量图片；快速去重；并行化；单机计算；图片特征
　　中图分类号： TP301.6 文献标志码：A
　　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）在低频子带上依次按照0°、45°、90°和135°方向构造灰度共生矩阵[13]，然后分别计算熵Entropyj、二阶矩ASMj、逆差矩DMj、对比度conj、相关系数corj作为特征参数，其中j=1，2，3，4，再结合之前计算出的各层子带的能量ENj成为纹理特征向量如下：
　　Wi=[ENi.j.k，Entropyi.j.k，ASMi.j.k，DMi.j.k，coni.j.k，cori.j.k]
　　其中k表示分解层数。
　　1.3度量方法
　　1.3.1颜色特征的距离度量
　　本文颜色特征的距离度量采用欧氏距离法，公式如式（9）所示：
　　其中：xi，xj（i≠j）为图片集中任意两幅图像；Eyk 、Ehk 、Ewk 分别为图片区域的圆心、圆环和外部区域所提取的特征；k是特征分量；N为特征数目；ay，ah，aw为各区域的权重，对于一般图片而言，图片的中心区域信息量多，而圆环部分和外部区域的信息量较少，所以本文分别取0.5，0.3，0.2代表各区域的重要程度。 　　1.3.2纹理特征和形状特征的距离度量
　　2并行化图片去重算法
　　2.1并行化图片去重算法
　　1）本文主要使用图片固有特征实现达到图片去重的目的，所以首先对图片集{xi}提取上述特征值，设图片集{xi}大小为n，将其分配给T个计算单元进行处理，则时间缩短至n/T，本文中实验取T=4。
　　2）对任意图片xi，xj（i≠j）计算距离D（xi，xj），由于重复图片所在位置具有任意性，若要找出所有重复图片则需要遍历整个图片集，计算量n2，采用并行计算则计算量为n2/T。
　　3）遍历相似度距离D（xi，xj），查找其中距离为0。若为0，则说明其为相同图片，标记并且删除后一张图片，仅保留前一张。
　　2.2实验结果
　　由于如果图片为重复图片则提取特征值相等，则距离必然为0，故本文主要使用运行时间作为衡量该算法的重要指标，使用Matlab软件编程实现对上述算法进行评价（注：以下时间均不包含图片特征的采集时间）。
　　本次实验选取1000及5000张图片进行处理，运行时间如表1所示。
　　按照上述算法进行5000张图片去重时，处理时间就达到22min。如果按照上述算法对万级、十万级甚至百万级图片处理时程序运行时间不可估量，本文对上述算法进行改进。
　　3改进算法及实验结果
　　3.1算法改进
　　针对上述算法主要影响运行时间的是在去重过程要遍历整个图片集，计算量为n2，即便采用并行处理方式，对最终结果的影响终究有限。针对此问题，本文对第2章中的算法进行改进，从图片集中任取一张图片x0，如果存在图片{xi，xj}（i≠j）使得D（x0，xi）=D（x0，xj），则{xi，xj}（i≠j）有可能为重复图片，需要进一步判断D（xi，xj）是否为0；若不为0，则{xi，xj}（i≠j）不是重复图片。利用这样处理方式，在距离计算过程中计算量为n；同时在计算过程中采用并行处理，最终计算量减小为n/T，相比n2的计算量大大减小。
　　改进算法具体步骤如下：
　　1）对图片集提取特征值，设图片集大小为n，将其分配给T个计算单元进行处理，则时间缩短至n/T，本文中实验取T=4。
　　2）从图片集中任取一张图片x0，分别与其图片集中其他图片进行距离计算，在计算过程中采用并行处理，计算量缩短为n/T。
　　3）对2）中计算得到的距离D（x0，xi）进行由小到大排序，得到排序后的距离D*i（i=1，2，…，n）。本文采用快速排序法。
　　4）遍历距离D*（x0，xi），查找其中相同的距离。由于在3）中已经对距离进行由小到大的排序，故每次只需要判断D*i+1是否与D*i相同，若D*i+1与D*i相同则进行第5）步，比较完毕后继续遍历剩下的距离，若遍历完成且没有相同距离则停止。
　　5）设{xi，xj}（i≠j）使得D（x0，xi）=D（x0，xj），则计算D（xi，xj）之间的距离，若为0，则说明其为相同图片，标记并且删除xj，保留xi；若大于0，则说明{xi，xj}对x0在特征上的相似程度一致，但并非相同图片，两张同时保留。
　　3.2查找重复图片的改进算法与第2章原算法运行时间的对比
　　如果图片量太大，第2章中对重复图片查找算法的计算量会急剧上升，导致运行时间过长，故本次选用300，600及900张图片分别用改进方法和第2章中方法进行重复图片的查找，对查找时间进行对比，如表2所示。
　　由表2中数据可知，采用遍历图片集查找重复图片的方式运算时间高于改进运算的10倍以上。同时改进运算在图片数量增加时运算时间增长并不明显，增长幅度仅在百分位，说明改进算法在海量图片去重上是有效的。
　　3.3改进算法在不同数量级与不同重复率时间对比
　　分别使用万级（1万）、十万级（10万）、百万级（100万和500万）级图片量进行测试；同时每种量级的重复图片分别占总数的30%、60%及90%，结果如表3所示。
　　由表3中数据可知：1）由万级到10万级运行时间增长在两倍左右，而10万级到100万级甚至500万级时按照本文图片量呈现线性关系，运行时间增长分别在10倍及50倍左右，这是由于处理数据大量增长，而实验用机在运行速度和处理能力上有限，导致在100万张及500万张图片的距离、比较等运算时处理能力不足，所以运行时间会呈现出与图片量增长倍数相同的情况，故适当提高硬件处理能力可以减少运行时间；2）由每种数量级不同重复率下的运行时间来看，随着重复率的升高运行时间略有下降，此情况出现是由于排序算法导致，重复图片越多，相同距离也就越多，故排序时间也就越短，所以在大数据量时选用合适的排序算法也是影响运行时间的重要因素。
　　综上所述，本文在改进算法中，从图片集中任取一张图片x0，分别与其图片集中其他图片进行距离的计算的方式相比遍历图片集计算距离的方式在运行时间效率此处是否应该是“运行效率”，时间上应该是减少，而不是提高吧？请明确。上提高10倍以上；同时针对不同重复率下不同数量级进行了测试，发现查询500万数量级中重复图片时运算时间也仅需10min左右，去重效率大幅度提高。故本文提出的算法为大数据量的图片快速去重工作提供了有效支撑。
　　4结语
　　面对目前数据的指数级增长，海量数据重复删除技术的研究在解决数据存储空间消耗大、数据备份及恢复成本高等方面具有重要的意义。本文利用图片固有属性特征，提出了一种海量图片快速并行化去重算法，使用该算法能够快速准确地对图片进行去重。实验结果表明，10min左右即可处理完500万图片集的去重工作，这为海量图片的去重处理提供了新的思路。同时，实验发现在大数据量时，对距离进行排序的时间对整个去重过程有一定的影响，排序时间越短，整个去重的时间也就越短，所以如何缩短排序时间作为本文将是该快速去重技术进一步的研究方向。 　　参考文献：
　　[1]
　　敖莉，舒继武，李明强.重复数据删除技术[J].软件学报，2010，21（5）：916-929.（AO L， SHU J W， LI M Q. Data deduplication techniques [J]. Journal of Software， 2010， 21（5）： 916-929.）
　　[2]
　　CLEMENTS A T， AHMAD I， VILAYANNUR M， et al. Decentralized deduplication in SAN cluster file systems [C]// Proceedings of the 2009 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2009： 101-114.
　　[3]
　　ESHGHI K， LILLIBRIDGE M， WILCOCK L， et al. Jumbo Store： providing efficient incremental upload and versioning for a utility rendering service [C]// Proceedings of the 5th USENIX Conference on File and Storage Technologies. Berkeley， CA： USENIX Association， 2007： 123-138.
　　[4]
　　HAN B， KELEHER P. Implementation and performance evaluation of fuzzy file block matching [C]// Proceedings of the 2007 USENIX Annual Technical Conference. Berkeley， CA： USENIX Association， 2007： 199-204.
　　[5]
　　张星煜，张建，辛明军.相似性―局部性方法相关参数分析[J].计算机技术与发展，2014，24（11）：47-50.（ZHANG X Y， ZHANG J， XIN M J. Analysis of related parameters based on similaritylocality approach [J]. Computer Technology and Development， 2014， 24（11）： 47-50.）
　　[6]
　　陈芬.改进量子粒子群算法优化神经网络的数据库重复记录检测[J].计算机应用与软件，2014，31（3）：22-23.（CHEN F. Database duplicate records detection using neural network optimised by IQPSO. [J]. Computer Applications and Software， 2014， 31（3）： 22-23.）
　　[7]
　　梁雪，任剑锋，景丽.基于QPSOLSSVM的数据库相似重复记录检测算法[J].计算机科学，2012，39（11）：157-159.（LIANG X， REN J F， JING L. Approximate duplicate record detection algorithm based on PSO and LSSVM [J]. Computer Science， 2012， 39（11）： 157-159.）
　　[8]
　　江程，朱锐，张芳，等.一种低开销的并行重复数据删除算法[J].软件导刊，2015，14（8）：96-99.（JIANG C， ZHU R， ZHANG F， et al. A parallel deduplication method with low overhead [J]. Software Guide， 2015，14（8）： 96-99.）
　　[9]
　　刘厚贵，邢晶，霍志刚，等.一种支持海量数据备份的可扩展分布式重复数据删除系统[J].计算机研究与发展，2013，50（z2）：64-70.（LIU H G， XING J， HUO Z G， et al. A scalable distributed data deduplication system to backup massive storage [J]. Journal of Computer Research and Development， 2013， 50（z2）： 64-70.）
　　[10]
　　曹英忠.基于Hadoop的重复数据删除技术的研究与应用[D].桂林：桂林理工大学，2012：46-66.（CAO Y Z. Research on the technology of data deduplication by Hadoop [D]. Guilin： Guilin University of Technology， 2012： 46-66.）
　　[11]
　　孙有军，张大兴.海量图片文件存储去重技术研究[J].计算机应用与软件，2014，31（4）：56-58.（SUN Y J， ZHANG D X. Research on deduplication technology for massive image file storage [J]. Computer Applications and Software， 2014， 31（4）： 56-58.）
　　[12]
　　常哲，侯榆青，李明俐，等.综合颜色和纹理特征的图像检索[J].小型微型计算机系统，2011，32（1）：161-164.（CHANG Z， HOU Y Q， LI M L， et al. Image retrieval based on combined color with texture feature [J]. Journal of Chinese Computer Systems， 2011， 32（1）： 161-164）
　　[13]
　　费园园，孙劲光，陶志勇.基于小波分解和灰度共生矩阵的纹理图像检索[J].现代计算机，2007（10）： 58-59.（FEI Y Y， SUN J G， TAO Z Y. Texture image retrieval based on wavelet decomposition and gray level cooccurrence matrix [J]. Modern Computer， 2007（10）： 58-59.）
　　[14]
　　夏定元，刘书学，周曼丽，等.基于小波和相对矩的形状特征提取与检索方法[J].计算机工程，2004，30（10）：146-147.（XIA D Y， LIU S X， ZHOU M L， et al. Method for shape feature extraction and image retrieval based on wavelet and relative moments [J]. Computer Engineering， 2004， 30（10）： 146-147.）
转载注明来源:https://www.xzbu.com/8/view-7438065.htm