没有合适的资源?快使用搜索试试~ 我知道了~
可扩展二值化模式搜索方法的视觉模式发现
1可扩展视觉模式发现的二值化模式搜索张伟1,曹晓春1,2刘伟,王瑞1,郭元芳1,陈志能31:中国科学2:中国科学院大学网络安全学院3:中科院自动化研究所{wzhang,caoxiaochun,wangrui,guoyuanfang}@ iie.ac.cn,zhineng. ia.ac.cn摘要101101000010111010001110101000101100110111bMS10101101001010本文研究了在大规模图像集合中通过二值化模式搜索进行视觉模式发现的方法。目标集合00110110101010001111110101011011100011001000111011101000... ......这是什么?1010110100101000101010101000... ......这是什么?频繁模式测试存储和计算。 我们解决这个问题,从10110100001011cbMS101011011010二进制空间模式搜索的观点。首先,提出了一种二元均值漂移(bMS)来发现频率,通过直接在二进制空间中进行模式搜索来测试模式。介绍了基于二项式的核函数和二元约束对比集1010001110101000101100110111001101101010100011111101010100111011101000... ......这是什么?0010101010100000101011101000... ......这是什么?信息模式二进制分析。其次,我们进一步扩展bMS到一个更一般的形式,即对比二进制均值漂移(cbMS),它最大化二进制空间中的对比密度,用于发现对数据集既频繁又有区别的信息模式。 使用二进制化的算法和优化,我们的方法证明了显着的计算(50倍)和存储(32倍)的改进相比,标准技术在欧几里德s-空间操作,而性能并没有很大程度上退化。此外,cbMS发现了更多信息模式通过抑制低鉴别模式。我们评估了我们的方法在注释ILSVRC(1M图像)和未注释的盲Flickr(10M图像)数据集与百万规模的图像,这表明了我们的算法的可扩展性和有效性,发现频繁和信息丰富的模式在大规模的集合。1. 介绍模式发现是计算机视觉和模式分析中最基本的问题之一。给定大规模无序图像集合(例如,从匿名网站抓取的图像),第一个问题是问“数据集中有什么样的图像?与其他“常见”数据集有什么不同?“视觉模式发现的目的是在未监督的环境中自动发现主导项目。很多研究者都在研究这个问题--*通讯作者。(a)大型图像集(b)二进制代码(c)模式(d)模式图1.给定大量图像(a),我们的目标是通过在二进制空间(b)中寻找模式(c)来发现模式(d)我们的bMS寻求频繁的模式,从目标集,而cbMS发现更多的信息模式,通过引用一个额外的对比集。lem由于其在各种视觉任务中的广泛应用,如分类[7],检索[27],摘要[32]。在大数据的背景下,视觉模式发现变得更加重要,因为它提供了一种有效的方式来表征大型图像集合。特别是,这个问题甚至是重要的数据爆炸的照片共享网站,如Instagram,Flickr,Imgur。在模式发现技术中,聚类分析是其核心部分.通过将数据投影到特征空间,模式与高密度区域密切相关。以前的技术主要是基于聚类- ing直接在欧几里德空间。然而,仍然有两个基本问题很少得到解决。一个问题是可扩展性问题。在欧几里得空间中对大型数据集进行聚类是非常不有效的。首先,距离估计涉及大量的实值运算,这使得它不可能分析大数据集。其次,对于大型数据集,将所有数据保存在内存中也很困难。例如,保存一百万个实值向量,比如AlexNet的R4,096-FC 7 activation- s [11],需要30 GB内存,更不用说38643865挖掘算法所需的额外内存。这对大多数计算机来说是不可能的。因此,随着数据的增长,从计算和存储成本的角度分析数据的当前方法变得不可行。另一个问题在于所发现的模式的信息量。通过信息,我们表明,模式需要是频繁的和歧视性的。换句话说,只有当模式在目标数据集中很常见,而在其他对比数据集中很少见时,它才被认为是信息性的。在大规模数据集中,直接挖掘频繁项仅给出到处出现的模式(例如,树木和天空),并不总是提供信息。请注意,数据集中的大多数图像实际上并不那么有趣,要么是因为它们太罕见而无法表征数据集,要么是因为它们在几乎所有数据集中都太常见。值得注意的是,我们的信息量类似于信息检索中使用的TF-IDF1概念,其中一个词的权重由频率和区分度决定。本文提出了两个版本的二进制模- e寻求算法的可扩展的视觉模式发现(图1)。一方面,二值化数据表示和二值化算法共同解决了计算和存储问题。另一方面,我们通过对比二进制模式搜索来抑制信息量较少的模式。概率分布的模式是概率密度函数(PDF)取其(局部)最大值的值。首先,我们提出了一个二值化的均值漂移算法,通过直接在二进制空间中操作来应对可扩展性的挑战。频繁模式可以被有效地发现为二进制空间中的模式,其中距离可以用“XOR”和“PopCnt”操作有效地评估。虽然散列技术已经被广泛研究[29,28,22]用于生成二进制代码,但对二进制化数据分析的研究仍然非常有限。在本文中,我们提出在二进制空间中分析数据。具体来说二进制均值偏移通过强制执行二进制均值偏移来产生,ry约束和探索合适的核。 其次,我们提出了通过挖掘对比密度来抑制信息量较少的模式。对于自然图像数据集,主导模式通常对应于非常常见的项目(例如,脸,天空,树),这些都不是信息。 我们进一步扩展了二进制均值漂移以在对比密度上操作,即,目标数据集(作为正或前景分布)与另一对比数据集(作为负或背景分布)之间的密度比。通过迭代地最大化密度比,可以发现最佳区分目标集和对比集的模式。为了进行评估,我们在带注释的ILSVRC数据集[21]上测试了我们的方法,包括一百万张图像,以及另一个未标记的Flickr数据集,包括超过1000万张图像。TF-IDF:词频倒置文档频率从Flickr网站抓取的狮子图片。与传统方法相比,该方法通过在二进制空间和对比密度下进行运算,以更快的速度和更小的内存开销找到频繁模式和信息模式。据我们所知,这是研究二值化模式挖掘技术的试点工作。我们的主要贡献总结如下:• 提出了一种二进制模式搜索算法(bMS),该算法在二进制空间中采用基于二进制的核和二进制约束。• 我们进一步扩展到对比版本(cbMS),以发现更多的信息模式,并表明,bMS可以通过利用非均匀背景密度进行优化而被推广到对比密度。• 实验结果表明,我们的算法运行速度快得多(50倍)与较少的内存成本(32倍),并没有退化太多的性能。2. 相关工作我们的工作是密切相关的两个视觉模式distraction和二进制空间数据分析。在本节中,我们回顾了基于这种分类的相关文献。视觉模式发现。视觉模式发现是多媒体和计算机视觉领域的一个研究对公共模式发现的早期研究[13,25,30]将其建模为优化问题。这些方法在计算上是昂贵的,因此只能在小的规模数据集(多达数百张图像)。频繁项集挖掘[31,18]主要工作在小规模数据集(约10k图像)上,尽管有一些工作[14,20]优化了大型数据集的可扩展性。 这些方法在模式发现,但在支持计数步骤中缓慢。用于大规模视觉模式发现的方法可以大致分为两个流。第一个流基于集群。最流行的技术k-means有两个固有的局限性:集群被约束为球对称的,并且它们的数量必须是先验已知的[8]。Sivic [24]直接对局部特征周围提取的小块进行聚类,以便将频繁模式分组在一起。Philbin [17]提出通过谱聚类[15]在匹配图上发现模式,该匹配图是通过针对整个数据集依次搜索每个图像来构建的。因此,稠密子图被认为是模式。至于速度,聚类一个37k的数据集大约需要两个小时。Chum [3]通过使用Min-Hash算法对图像进行聚类来挖掘视觉相似的照片,其中哈希密钥冲突被提取为模式。它需要大量的哈希表来获得合适的冲突概率。3866F第二个流是基于模式搜索,它不需要事先知道的集群的数量,或限制集群的形状。一个典型的方法是[7],其通过在欧几里得空间中的判别式模式搜索来挖掘中级视觉元素。二进制数据分析。 虽然已经有许多用于数据二进制化的散列技术,但只有少数作品直接分析二进制空间中的数据,以充分探索二进制表示的有效性。二进制空间中的快速精确最近邻搜索[16]通过在二进制代码子串上构建多个哈希表来提高检索效率。最近关于BK means的工作[10]通过将K-Means适应于双-表示是二进制哈希键。为了执行均值漂移,可以从紧凑的哈希键到实值向量构建哈希表,如[ 10 ]中所做。在优化过程中,实值向量可以在O(1)内有效地检索以进行数值计算。在这种情况下,该方法与标准均值漂移具有相同的结果和相似的运行速度。3.2. 二进制均值漂移:bMS给定一组实值向量X ={x1,x2,.,xn},在Rd中表现出潜在的概率密度函数p(x),密度可以通过以下公式估计:nary空间虽然非常有效,但它仍然需要在生成任何模式之前处理所有数据。值得注意的是,基于聚类的方法需要在生成任何模式之前处理所有数据,而模式搜索具有p(x)Σni=1K(K)x−xhi(2)在有限的时间预算中部分生成图案的优点。基于深度学习的技术已经在各种任务上显示出有希望的结果。通常,它需要considerable计算资源的良好性能。有趣的是,二值化深度架构[12,6,5]的最新进展利用了深度神经网络中的二进制运算和连接,这证明了数据二值化在视觉识别任务中的效率和有效性最近的一项探索“XNOR”操作的工作[19]58倍加速和32倍内存节省。这些有希望的结果显示了二元化肛门的巨大潜力多媒体内容分析。作为比较,我们的方法通过在二进制空间中的模式搜索有效地发现了模式,即,二进制模式搜索技术,针对大型数据集。3. 二值化可视模式发现3.1. 数据二值化其中hi是与xi的n相关联的自适应带宽最近邻[8],并且K(x)是核函数(例如,高斯)。均值漂移通过最大化p(x)来定位模式。然而,由于时间效率,标准均值漂移不适用于在欧几里得空间中操作的大型数据集。我们提出了一个非常有效的二进制均值漂移算法,直接定位模式在二进制空间。设B={b1,b2,.,bn}是嵌入在k维二进制空间中的X对应二进制{-1,1}k,其中bi使用ITQ生成。在二进制空间中,通常采用的连续核(例如,高斯核)不适用。首先,为连续空间设计的核不太适合离散二进制空间。其次,二进制代码之间的距离有一个明确的解释,即,不一致的位数,这也需要一个适合这种解释的内核。在没有任何先验知识的情况下,假设二进制码在{-1,1}k中均匀分布。在此假设下,两个随机散列码之间的汉明距离遵循二项分布Bin(k,1/2)。我们提出了一个核Kb加权二进制码与不同的- ent汉明距离:从理论上讲,任何散列技术都可以在我们的算法中采用。我们的目标是用二进制代码最好地近似数据,这样下面的过程可以从二进制化中受益,精度损失最小因此.1Kb(d)=−log22k Σdi=0时.ΣΣK我/z,(3)我们采用迭代量化(ITQ)[9],因为它通过用R旋转数据来最小化在将实值向量V量化为二进制码B时的精度损失:Q(B,R)=<$B−V R<$2,(1)其可以通过交替地更新B和R来优化。关于这种二值化技术的细节可以在[9]中找到。在实值向量上执行均值漂移是微不足道的。然而,在实践中,我们可能无法在内存中保留大量的实值向量唯一负担得起的3867其中z是确保Kb是有效k-内核的归一化因子,并且括号中的部分相当于Bin(k,1/2)的累积分布函数CDF(d)。这样,核Kb(d)就有了一个清晰的解释:两个随机二进制码的汉明距离小于或等于d的概率。因为Kb只有k+ 1个有限值,所以在我们的例子中,它被实现为一个查找表。此外,我们的方法在运行速度上比标准均值漂移有明显的优势。考虑到这个基于二项式的内核以及双-3868我我p (b)─0.030.0250.020.030.0250.02只要我们计算出Kb就很简单了。因此,执行具有二进制约束的均值偏移是通过以下方式更新估计值fib0.0150.015.nbiG(0.010.01b=sgni=12h2bΣ2hi、(五)n1G(b−bi2)0.0050.005i=12h2b2hi0−500−400−300−200−1000100200300400 5000−500−400−300−200−1000100200300400 500其中sgn(·)是用于二值化的正负号函数。图2.基于二项式的核Kb(左)和相应的核Gb(右)。请注意,所有内核都是离散的,我们将离散点排成一行只是为了更好地可视化。这张照片最好用彩色看。算法1- bMS:二进制均值漂移输入:B:数据集的二进制代码;b:初始位置;h:带宽; r:半径搜索阈值; T:最大迭代次数;输出:模式:b模式1:在B上建立多索引哈希表M;2:对于iter= 1. 没做3:N(b)=M.r-search(b,r);4:使用等式更新BQb。(6);有两个观察结果可以进一步加快计算速度。首先,虽然Eq。(5)对整个点集求和,这是非常不必要的,因为大多数点对求和没有贡献。在我们的实现中,我们只考虑b的邻域中的点,即,点,其汉明距离小于或等于阈值r。为了在汉明球中进行有效的r -半径搜索,我们采用多索引哈希[16]来索引和搜索二进制s-步伐。 从图2中可以看出,k/4≤k/3是一个合理的范围,R. 这种策略大大提高了跑步速度。其次,注意到核Kb以及Gb是严格正的,分母可以被忽略,因为它是严格正的。 因此,可以进一步简化5:如果不收敛,6:b←b;7:其他8:断裂;9:如果结束如:⎛ Σb=sgnbi∈N(b)⎞biG(b-bi2),(6)2h2b2hi10:结束11:b=b;nary约束,我们将问题公式化为:其中N(b)表示b的邻域。结果我们的这种方法在计算方面是非常有效的。这算法(bMS)总结在算法1中。3.3. 对比二进制均值漂移:cbMSbmax= argmaxBΣni=1Kb(b−b2hi(一)(四)随着数据的增长,特征空间中的模式通常对应于常见模式(例如,天空,人)出现在每一个地方。对于具有大量类别的数据集,S.T. b,bi∈{−1,+1}k,其中n·n表示l2-范数。在b的二元约束下,我们只在Hamming超立方体的顶点之间移动估计。为了优化,我们迭代地更新估计均值漂移。 如文[2]所指出的,Gb=−K′等价于密度的梯度上升它们可能会互相重叠,因为图案不是那么信息丰富,例如,图1中的天空和人脸模式(右上角)。我们进一步扩展了二进制均值漂移,通过对比另一组定义的背景分布来发现判别模式。我们将目标数据集作为正集,并引入-引入另一个背景数据集作为用于对比的负集。 正负集密度比b′用其阴影核Kb估计,其中Kb表示Kb的导数。图2显示了不同位数k的Kb(左)和Gb(右)的几个示例内核配置文件。请注意,为二进制s-空间导出的内核与广泛采用的欧几里得空间的高斯内核有很大不同。Gb的形状是类二项式的.大部分能量位于汉明距离较小的区域,峰值比高斯峰更有意义,因为它抑制了所有的模式,存在于背景中。形式上,在二进制空间中,一些点被视为前景(正集P),而其他点被视为背景(负集N)。受[7]的启发,我们可以将关于对比密度比的问题表示为p∈(b)=p+(b):K(功能在我们的例子中,G也被实现为查找b=argmaxp(b)=bi∈Pb2hI,bcbK(<$b-bj<$2) +λ(七)表,以方便快速计算。 虽然不同的-bj∈Nb2hik=256k=512k=256k=512我3869分析上是复杂的,数值计算S.T. b,bi,bj∈{−1,+1}k3870C其中,模式是用p+和p-之间的对比密度估计的,并且λ是对avoiddivision-by-zero的偏移因此,一个模式必须在正集合中频繁出现,同时在负集合中罕见。类似地,通过最大化pω(b),可以通过下式估计n-w模式算法2- cbMS:对比二进制均值漂移输入:P:目标数据集的二进制代码;N:对比数据集的二进制代码;b:初始化;h:带宽;T:最大迭代次数;λ:smoothing ter- m;b=sgn .ΣfNb,Gb·l Pb,Kb−f Pb,Gb·l Nb,Kb−λf Pb,Gb,输出:模式:b模式1:为{P_N}构建多索引哈希表M;C哪里lPb,Kb· lNb,Gb— lNb,Kb· lPb,Gb— λlPb,Gb(八)2:对于iter= 1. 没做3:[Pb,Nb] =M. r-search(b,r);4:使用等式更新b_c(8);fS,H=Σbi2h2H( b−bi2小时(2)5:如果不收敛,6:b←b<$c;lS,H=bi∈SΣbi∈S我H(H)b−b2hi我i=2),(九)7:其他8:断裂;9:如果结束10:结束11:b=b;和S ∈ {Pb,Nb},H∈ {Kb,Gb},其中Pb,Nb表示b在集合P,N中的邻域。讨论值得注意的是,Eq。(8)可以看作是Eq.bMS实际上是cb M S的一个特例。假设p−(x)是一个uniforr-m分布,很容易证明方程。(8)退化到(5)用下列等式成立:ΣKb(bi)=1/|N|、C4. 实验基准模式搜索算法相当困难。由于缺乏大规模的注释数据集,量化评估我们的算法变得非常困难。在本节中,我们首先评估bMS和cbMS,bi∈NΣΣbiGb(bi)=Gb(bi)=0,(十)纯度覆盖。然后,我们分析了一个大规模的真实世界的Flickr数据集的结果。bi∈Nb i∈N哪里|N|是集合N的基数,且bi∈N是均匀分布的。值得注意的是,cbMS和[7]之间的根本区别在于,我们的方法是针对大数据集设计的二值化分析,并且优化是完全不同的。[7]在连续空间上运行,目标是相对较小的数据。优化细节。在实践中,优化Eq. 当p−(b)收缩到zero时,(7)与(8)趋于不稳定。在这些位置附近的反射率是峰值,并且Eq. (7)变得困难和不稳定。请注意,偏移参数λ在通过在背景密度上添加恒定偏移来平滑估计中也起着重要作用,使得经由sgn(·)将不会剧烈地漂移b/c太远。在极端如果λ变得非常大,则问题cbMS ( 公 式 ( 7 ) ) 退 化 为 bMS ( 方 程 ( 7 ) ) 。(四))。在Eq.(8)涉及核和它的影子,仍然可以用Kb和Gb的两个单独的循环表有效地计算它。注意,正集合和负集合的二元码在一个多索引哈希表中被联合索引,但是在等式(1)中不同的邻域被联合索引。8人单独评价。该算法(cbMS)总结在算法2中。4.1. 数据集我们采用ILSVRC是因为它是公开可用的最大的完全注释的数据集,因此可以进行定量评估。另一方面,采用Flickr10M在真实世界的大规模无序数据集上测试了我们的算法。ILSVRC[21]. 从 互 联 网 上 抓 取 的 大 量 图 像 都 是 用WordNet高层次结构手动组织的。该数据集包含1,000个对象类别,1.28总共有100万张图片。为了进行详细的评估,我们从1000个类别中随机挑选200、500和1000个对象类别,分 别 命 名 为 ILSVRC-200 、 ILSVRC-500 和 ILSVRC-1000,对三个子集进行采样。请注意,ILSVRC-1000对应于ILSVRC的全套。Flickr10M。这个数据集包含从Flickr抓取的1000万张图像。虽然是随机构建的,但由于大数据的影响,Flick-r10 M仍然包含大量的视觉模式,例如,不同用户共享的热门对象/地标,在同一地理位置上传的一致图像。请注意,我们不可能对这个数据集进行注释,这个数据集作为一个38710.80.60.40.2ILSVRC−2000.80.60.40.2ILSVRC−5000.80.60.40.2ILSVRC−100000.2 0.40.6覆盖00.2 0.4 0.60.8覆盖00.2 0.4 0.6 0.8覆盖图3.用纯度-覆盖图比较不同方法左:包含200个类别的子集中:包含500个类别的子集。右:全套1,000个类别。4.2. 实验装置我们使用VGGNet-19 [23] fc 7活动的深层特征作为图像特征。迭代量化[9]应用于将特征转换为二进制代码,二进制代码是所有方法的输入(除了在欧氏空间中操作的均值偏移)。我们遵循[7]的评价方案,纯度-覆盖率图。高质量模式对应于特征空间中的密集区域,其中位于其邻域内的支持图像共享相同的类别标签。对于一个发现的模式(或等效的模式在特征空间),我们池不同的支持图像集通过改变(汉明)距离的模式。纯度被定义为集合中真实图像的百分比,覆盖率是集合中包含的真实图像的分数。作为精确度-召回率曲线的类似物,在纯度和覆盖率之间也存在权衡。据我们所知,本文是关于使用二进制分析的模式搜索/模式发现的先驱工作,其中数据很难适应内存。因此,大多数在欧几里得空间中操作的方法都不能直接比较。我们包括标准的Mean Shift对全精度数据进行操作,以评估我们二进制化算法中的精度损失。在本文中,包括以下方法以供比较:• Mean Shift(MS)是在欧几里得空间中操作的标准方法[4]。• 二进制均值漂移(bMS)对应于算法1中的方法(具有基于二进制的内核Kb)。• 具有高斯核的二进制均值漂移(bMS-Kg)对应于算法1中的方法。与bMS不同的是,bMS-Kg采用了基于高斯的核函数.• 对比二进制均值漂移(cbMS)是算法-m2中描述的bMS在对比密度上的扩展.4.3. 性能比较为了公平比较,我们用相同的初始位置集初始化所有方法,初始位置集包含200/500/ILSVRC-200 / 500 / 1000的1,000个随机位置。在收敛过程中,模式被提取为模式,并通过检索邻域得到支持图像。图3在纯度-覆盖率图方面比较了ILSVRC的每个子集的不同方法。如图所示,在只有200个类别的小子集中找到模式稍微容易一些。随着更多的图像被嵌入到特征空间中,模式可以容易地被来自其他类别的噪声图像扰动。图4. bMS在ILSVRC中发现的示例模式。带有红色虚线边界的图像是来自其他类别而不是主导模式的错误结果正如预期的那样,MS通过在原始欧几里德空间中操作而工作得最好,因为其他方法在数据二进制化期间遭受精度损失以及二进制约束。总的来说,我们的方法bMS工作得相当好,表现出比MS稍差的性能。然而,正如我们将在后面的4.5节中展示的那样,bMS比MS运行得快得多。bMS的示例模式见图4。通过在二进制空间中操作,bMS不会表现出太多的性能退化。首先,通过ITQ的数据二值化通过最小化量化误差近似地保留密度,尽管邻域不一定保持。其次,在模式搜索步骤中,二项式核Kb对二进制空间的核建模是有效的,这可以通过比较bMS和bMS-Kg来证实。然而,高斯核并不适合二进制代码。对于cbMS,我们依次取一个类别作为正集,其他类别作为负集。我们的cbMS在高纯度区域显示出明显的优势(见各图的上半部分的纯度MSBMSbMS−KG信任措施纯度纯度3872cbMS倾向于将模式定位在负密度较低的区域。信息模式发现实际上,对于真实用户来说,频率和可辨别性都是“好”模式。我们更感兴趣的是区分事物的模式。图5显示了bMS和cbMS从ILSVRC数据集中发现的示例模式。对于bMS,我们为每个类别描述了细化模式。对于cbMS,我们将一个类别作为正集合,其余的作为负集合。根据我们的观察,更容易发现模式-s来自具有一致视觉外观的类别。在实践中,有些类别具有多种模式,不同类别的模式可能会相互重叠。例如,在第一行中,“空格键”具有类似于“打字机键盘”的模式,以及具有闭合视图空格键的其他模式。使用bMS模式,仍然很难区分一个类别和另一个类别,因为“空格键”的模式与“打字机键盘”的模式非常相似。而cbMS通过对比密度的方法解决了这个问题。如最后一列所示,cbMS发现的模式对描述类别更有意义。另一个典型的例子是最后一行。左边的图案是鱼和一个人在里面。然而,在整个数据集中,人是相当“常见”的模式(中间)。因此,左侧bMS的模式被抑制,cbMS发现了更具鉴别力的模式(右侧)。4.4. Flickr10M数据集我们进一步在未注释的Flickr10M数据集上进行实验,以发现“盲”集中的模式,即,没有数据集的先验知识。图6显示了bMS(左)和cbMS(右)在该数据集上发现的几种模式。如左图所示,现实世界数据集中最流行的模式并不那么有趣,类似于信息检索中的停止词(例如,is,are,of)。真实世界的数据大多是嘈杂和有偏见的。正如预期的那样,我们的方法bMS用这样的模式来表征Flickr10M,例如,默认占位符图像(第一行),天空(第二行),单色照片(第三行)和人(最后几行)。如果我们仔细观察,大多数模式的存在是由于某些原因。例如,占位符模式是由于死链接。我们进一步将bMS中的顶部模式作为负集N,并再次在数据集上运行cbMS这一次,产生的模式通过显示更多信息模式来表征Flickr10M数据集,例如,宠物,飞机,地标,这些都是Flickr用户之间普遍分享的。4.5. 讨论实验在PC上进行,具有3. 30GHz CPU和8GB内存,除了全精度意味着表1. 在ILSVRC 数据集中找到一种模式的平均运行时间(秒)(具有一百万张图像)。方法MSBMSbMS-Kg信任措施时间9.780.170.170.21Shift(MS)位于内存为64GB的服务器上。我们的方法的空间复杂度是O(n),其中n是图像的总数。在实践中,保持相同的特征维数,将实值数据转换为二进制代码会得到64×(双精度位)或32×(单精度位精度到位)存储器节省。算法的时间复杂度为O(Tn2),其中T为迭代次数.表1总结了从一百万张图像中挖掘模式的平均运行时间。直接在二进制空间中运行的算法运行得更快,即,10秒对0.2秒,受益于有效的“XOR”和“PopCnt”操作。在我们的实验中,bMS和bMS-Kg显示出相似的运行时间,因为它们都受益于用查找表实现的离散核。相反,MS需要在线评估连续空间中的核。我们的cbMS比bMS稍慢,因为在优化中引入了额外的计算(等式2)。(8))。理论上,对于现代CPU,可以在单个CPU时钟中执行64个二元运算,因此加速比约为64倍[19]。实际上,我们观察周围50倍加速比(表1)。值得注意的是,在速度效率方面,基于模式搜索的方法在运行时间上更灵活。即使在有限的时间预算(例如一秒)下,它仍然可以从大型数据集中返回一些有趣的模式,因为它不需要遍历所有数据来找到一个单一的模式。随着更多的时间预算,它可以根据需要逐渐找到更多的模式。相反,基于聚类的方法需要遍历所有数据才能生成任何模式,这使得它不太适合实际应用。收敛性分析虽然bMS和cbMS的收敛性证明是困难的2,我们提供了一些关于收敛性的实证分析根据实验-目前,我们的方法通常需要5~ 15次迭代来收敛。 特别地,bMS总是在10次迭代中收敛,并且cbMS在实践中通常需要更多的迭代。偏移项(等式7中的λ)对收敛速度有很大帮助。由于离散优化(特别是sgn(·)运算)的存在,很难保证收敛性。凯莉在我们的例子中,通过Eq. 6、8将估计更新到具有更高密度的点。2请注意,在连续空间中标准Mean-Shift的严格收敛性证明仍然缺失[1]3873bMS发现的模式负集样本cbMS发现的模式空格键打字机键盘空格键巴拉库塔山鲟鱼巴拉库塔山图5.ILSVRC中bMS(左)和cbMS(右)发现的模式比较中间:其他类别中与左列视觉相似的示例图像按bMS列出的最佳模式按cbMS列出的最图6. bMS(左)和cbMS(右)在无序Flickr10M数据集中发现的前5个模式。每一行都列出了一个已发现模式的支持图像,并根据模式密度进行排名(从上到下)。bMS倾向于发现许多图像共享的共同模式,而cbMS发现更多表征数据集的信息模式。5. 结论我们提出了一种通过二进制空间中的模式搜索来解决大规模视觉模式发现的技术,通过探索二进制约束和二项核。我们的方法在计算和存储方面比标准技术更具可扩展性。通过进一步扩展对比密度算法,我们能够从数据集中发现更多信息的模式。目前,我们的实验只在完整的图像上进行,的发现未来的方向是扩展对象级挖掘,即,找到物体的代表性部分。6. 确认本 课 题 得 到 了 国 家 重 点 研 究 发 展 计 划( No.2016YFB0800603 ) 、 国 家 自 然 科 学 基 金( No.2016YFB0800603 ) 、 国 家 自 然 科 学 基 金( No.2016YFB0800603 ) 和 国 家 自 然 科 学 基 金(No.2016YFB0800603)的资助。61602463号61422213号61602344)、北京自然科学基金(4172068)、中国科学院重点项目(No. QYZDB-SSW-JSC003)。3874引用[1] Y. Aliyari Ghassabeh高斯核均值漂移算法收敛的一个充分条件多元分析杂志,135:17[2] Y.程均值漂移、模式搜索和聚类。IEEE Trans. 模式分析马赫内特尔第790-799页4[3] O. Chum和J. Matas。空间相关图像的大规模发现。IEEE传输模式分析马赫内特尔,32:371-377,2010. 2[4] D. Comaniciu和P.米尔Mean Shift:A Robust ApproachToward Feature Space Analysis(Mean Shift:一种稳健的特征空间分析方法)IEEE传输模式分析马赫内特尔,24(5):6036[5] M. Courbariaux和Y.本吉奥。Binarynet:训练深度神经网络,权重和激活被限制为+1或-1。CoRR,abs/1602.02830,2016。3[6] M. Courbariaux,Y. Bengio和J.大卫Binaryconnect:在传播过程中使用二进制权重训练深度神经网络。NIPS,2015年。3[7] C.多尔施A. Gupta和A. A.埃夫罗斯中级视觉元素发现作为判别模式搜索。 在procNIPS,第494一、三、四、五、六[8] B. 格奥尔杰斯库岛Shimshoni ,和P.米尔Mean Shiftbasedclusteringinhighdimensions : Atextureclassification example.载于ICCV,第456IEEE计算机学会,2003年。二、三[9] Y. Gong和S. Lazebnik迭代量化:一种学习二进制代码的亲克鲁斯特方法。 在proc CVPR,第817-824页,2011年。三、六[10] Y. Gong , M. Pawlowski ,F. 扬 湖, 澳- 地 布兰 迪湖Bourdev和R.费格斯。在一台机器上进行Web规模的照片哈希聚类。在Proc.CVPR,2015中。3[11] A.克里热夫斯基岛Sutskever和G. E.辛顿使用深度卷积神经网络进行Imagenet分类。在Proc. NIPS,第1097-1105页,2012中。1[12] Z. 林,M。库尔巴里奥河Memisevic和Y.本吉奥。神经网络与几个乘法。ICLR,2016. 3[13] H. Liu和S.燕.通过空间相干对应的共同视觉模式发现。在Proc. CVPR,第1609-1616页,2010中。2[14] S. Moens,E. Aksehirli和B. Goethals大数据的频繁项集挖 掘 InInternational Conference on Big Data , pages1112[15] A. Y. Ng,M。I. Jordan和Y.韦斯关于谱聚类:分析和算法。在Proc. NIPS,第849麻省理工学院出版社,2001年。2[16] M. Norouzi、A. Punjani和D. J·弗利特利用多索引散列法在汉明空间中进行快速精确搜索。IEEE Trans.模式分析马赫内特尔第1107-1119页,2014年三、四[17] J. Philbin和A.齐瑟曼。在非常大的图像集合上使用匹配图的对象挖掘InProc. ICVGIP,2008. 2[18] T. Quack、V.Ferrari和L. V.Gool频繁项集配置的视频挖掘。 在proc CIVR,第360- 369页,2006年。2[19] M. 拉斯泰加里河谷Ordonez,J.Redmon和A.法哈迪。Xnor- net:使用二进制卷积神经网络的Imagenet分类CoRR,abs/1603.05279v1,2016。三、七3875[20] Z. Rong和J.D.你好直接内存外分布式并行频繁模式挖掘。在大数据、流和异构源挖掘国际研讨会:Al出租、系统、编程模型和应用,第55-62页,2013年 2[21] O.鲁萨科夫斯基Deng, H.苏,J.克劳斯,S. 萨蒂希S.妈Z。Huang,黄背天蛾A.卡帕西A.科斯拉,M。伯恩斯坦A. C. Berg和L.飞飞ImageNet大规模视觉识别挑战。International Journal of Computer Vision,第1-42页,2015年4月。二、五[22] F. 申角沈,W。Liu和H.陶申。监督离散散列。在CVPR,2015年6月。2[23] K. Simonyan和A.齐瑟曼。用于大规模图像识别的深度卷积网络ICLR,2015年。6[24] J. Sivic和A.齐瑟曼。使用视点不变区域配置的视频数据挖掘 在proc CVPR,2004年。2[25] H.- K. Tan和C.- W. Ngo.局部匹配使用推土机图像视觉计算,27(10),2009年。2[26] B. Thomee,D.A. Shamma,G.弗里德兰湾Elizalde,K.倪D. 波兰,D。Borth和L.李YFCC100M:多媒体研究的新数据Commun. ACM,59(2):64 -73,2016.[27] W. Vor a vuthikunchai,B. Cr e′ milleux和F. 朱丽基 于频繁模式统计的图像重排序。在2014年国际多媒体检索会议第129页中1[28] J. Wang,W.Liu,中国粘蝇A.X. Sun和Y.-G. 蒋使用列表监督学习InProc. ICCV,2013. 2[29] Y. Weiss,A. Torralba和R.费格斯。光谱散列。神经信息处理系统的进展,第1753-1760页,2008年2[30] J.Yuan和Y.吴空间随机分割用于共同视觉模式发现。载于《国际刑事法院判例汇编》,2007年。2[31] M. J. 扎 基 关 联 挖 掘 的 可 扩 展 算 法 IEEE Trans. onKDE,第372-390页,2000年。2[32] W. Zhang,H.Li,C.-,中国地质大学学报(自然科学版),2003 - 11W. Ngo和S.-F. 昌可扩展的可视化实例挖掘与线程的功能。在ACM Multimedia,第297-306页1
下载后可阅读完整内容,剩余1页未读,立即下载
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)