一种多媒体对象的相似检索方法及装置

本发明公开了一种多媒体对象的相似检索方法及装置，通过对多媒体对象进行特征提取，获取多媒体对象的d维特征向量,对d维特征向量进行降维处理,提取待检索多媒体对象的d维特征向量，并通过iDistance算法，将待检索多媒体对象的d维特征向量映射为一维键值及数据空间中的查询点q,根据查询点q、查询空间及距离度量，修剪掉不需查询的Partition分区及不需查询的数据点,在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值及查询点与对所述查询空间内的数据点进行查询，以查询待检索多媒体对象的d维特征向量。本发明减少无效的I/O查询，并以三角剪枝的方式降低计算开销，进而提高查询效率。

技术领域
本发明涉及相似性检索领域，尤其涉及一种多媒体对象的相似检索方法及装置。
背景技术
现如今许多数据处理应用需要处理结构更为松散甚至无结构的数据。很多实际应用更是需要处理基于样本的检索，例如基于内容的图像检索等。而这些应用都可以归结到相似性检索的范畴，尤其在多媒体应用中，基于多媒体数据的内容进行相似搜索的技术，也变得越来越重要。为了提升多媒体相似性检索的处理效率，通常针对多媒体对象的高维特征建立高维索引。多年来，研究者们已经设计和开发了很多高维索引技术用于组织视频、图像、音频等多媒体数据的特征向量，以提升检索性能。由于“维度灾难”的存在，当数据量很大，维度很高时，提升多媒体检索任务的性能仍然是一项艰巨的工作，现有技术中的高维索引技术，当数据规模较大，维度较高时，I/O开销及计算开销均会变大，降低了索引查询的性能。
发明内容
本发明提供一种多媒体对象的相似检索方法及装置，解决现有技术中高维索引技术当数据规模较大，维度较高时，I/O开销及计算开销均会变大，降低了索引查询的性能的技术问题。本发明的目的是通过以下技术方案实现的：一种多媒体对象的相似检索方法，包括：通过对多媒体对象进行特征提取，获取多媒体对象的d维特征向量；将d维特征向量的数据空间划分为M个区域，通过iDistance算法，将d维特征向量映射为一维键值，并通过一维索引结构存储所述一维键值及所述d维特征向量，以获得查询数据库，其中，所述数据空间中包括d维特征向量对应的数据点；提取待检索多媒体对象的d维特征向量，并通过iDistance算法，将待检索多媒体对象的d维特征向量映射为一维键值及数据空间中的查询点q；根据查询点q、查询空间及距离度量，修剪掉不需查询的Partition分区及不需查询的数据点；在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值，对所述查询空间内的数据点进行查询，以查询待检索多媒体对象的d维特征向量。前述的多媒体对象的相似检索方法，所述特征提取包括SIFT特征提取、HARRIS特征提取和SUSAN特征提取。前述的多媒体对象的相似检索方法，所述将d维特征向量划分为M个区域，通过iDistance算法，将d维特征向量映射为一维键值，并通过一维索引结构存储所述一维键值及所述d维特征向量，以获得查询数据库，包括：将多个d维特征向量的数据空间划分为m个分区P0、P1、…、Pm-1；为每个分区选定参照点Q0、Q1、…、Qm-1；根据d维特征向量对应的数据点p到参照点Qi的距离，将d维特征向量映射为一维键值，其中，一维键值y＝i×c+dist(p，Qi)，0≤i≤m-1，c为弹性系数，dist(p，Qi)为d维特征向量对应的数据点p到参照点Qi的距离；采用映射后的一维键值y建立B+-tree的索引结构,以存储所述一维键值y及所述d维特征向量。前述的多媒体对象的相似检索方法，所述根据查询点q、查询空间及距离度量，修剪掉不需查询的Partition分区及不需查询的数据点的步骤，包括：将所述查询点q与查询半径r所形成的超球扩展成超立方体；判断每个Partition是否与所述超立方体相交；当所述Partition与所述超立方体不相交时，修剪掉不需查询的所述Partition，并扩大查询半径r，重新进行修剪判断，直至KNN检索结束；当KNN检索结束后，对未修剪的Partition中的数据点p增加数据点到数据空间中心的距离dist(p，center)，判断所述查询点q到数据空间中心的距离dist(q，center)及查询半径r，是否满足dist(p，center)≤r+dist(q，center)，当不满足时，修剪掉数据点p。前述的多媒体对象的相似检索方法，在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值，对所述查询空间内的数据点进行查询，以查询待检索多媒体对象的d维特征向量的步骤，包括：当第一种情况时，根据查询范围，向B+-Tree树的叶子节点两边进行遍历，查询待检索多媒体对象的d维特征向量对应的数据点p，其中，所述第一种情况为当前Partition包含查询点q；当第二种情况时，根据查询范围及Partition的半径，向B+-Tree树的叶子节点内部进行遍历，其中，所述第二种情况为查询点q在当前Partition外，且所述查询点q与查询半径r所形成的超球与Partition相交。一种多媒体对象的相似检索装置，包括：特征向量提取模块，用于通过对多媒体对象进行特征提取，获取多媒体对象的d维特征向量；降维模块，用于将d维特征向量的数据空间划分为M个区域，通过iDistance算法，将d维特征向量映射为一维键值，并通过一维索引结构存储所述一维键值及所述d维特征向量，以获得查询数据库，其中，所述数据空间中包括d维特征向量对应的数据点；映射模块，用于提取待检索多媒体对象的d维特征向量，并通过iDistance算法，将待检索多媒体对象的d维特征向量映射为一维键值及数据空间中的查询点q；剪枝模块，用于根据查询点q、查询空间及距离度量，修剪掉不需查询的Partition分区及不需查询的数据点；查询模块，用于在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值，对所述查询空间内的数据点进行查询，以查询待检索多媒体对象的d维特征向量。前述的多媒体对象的相似检索装置，所述降维模块包括：分区单元，用于将多个d维特征向量的数据空间划分为m个分区P0、P1、…、Pm-1；映射单元，用于为每个分区选定参照点Q0、Q1、…、Qm-1，根据d维特征向量对应的数据点p到参照点Qi的距离，将d维特征向量映射为一维键值，其中，一维键值y＝i×c+dist(p，Qi)，0≤i≤m-1，c为弹性系数，dist(p，Qi)为d维特征向量对应的数据点p到参照点Qi的距离；索引单元，用于采用映射后的一维键值y建立B+-tree的索引结构,以存储所述一维键值y及所述d维特征向量。前述的多媒体对象的相似检索装置，所述剪枝模块包括：变换单元，用于将所述查询点q与查询半径r所形成的超球扩展成超立方体；判断单元，用于判断每个Partition是否与所述超立方体相交；第一修剪单元，用于当所述Partition与所述超立方体不相交时，修剪掉不需查询的所述Partition，并扩大查询半径r，重新进行修剪判断，直至KNN检索结束；第二修剪单元，用于当KNN检索结束后，对未修剪的Partition中的数据点p增加数据点到数据空间中心的距离dist(p，center)，判断所述查询点q到数据空间中心的距离dist(q，center)及查询半径r，是否满足dist(p，center)≤r+dist(q，center)，当不满足时，修剪掉数据点p。前述的多媒体对象的相似检索装置，所述查询模块包括：查询执行单元，用于在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值及查询点q与当前partition的情况，对所述查询空间内的数据点进行查询，其中，查询点q与当前partition的情况包括第一种情况和第二种情况；第一遍历单元，用于当第一种情况时，根据查询范围，向B+-Tree树的叶子节点两边进行遍历，查询待检索多媒体对象的d维特征向量对应的数据点p，其中，所述第一种情况为当前Partition包含查询点q；第二遍历单元，用于当第二种情况时，根据查询范围及Partition的半径，向B+-Tree树的叶子节点内部进行遍历，其中，所述第二种情况为查询点q在当前Partition外，且所述查询点q与查询半径r所形成的超球与Partition相交。本发明的技术效果为：通过优化I/O开销的分区剪枝PP算法，剪掉无效的分区，减少无效的I/O查询，提高查询效率；通过优化计算开销的基于三角不等式的剪枝LP算法，筛除一部分数据点，以三角剪枝的方式降低计算开销，进而提高查询效率。
附图说明
图1为本发明实施例提供的一种多媒体对象的相似检索方法的流程图；图2为本发明实施例提供的kNN检索遍历策略三种情况的示意图；图3为本发明实施例中基于PP算法的剪枝示意图；图4为本发明实施例提供的一种多媒体对象的相似检索装置的结构示意图。
具体实施方式
为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。如图1所示，为本发明实施例中的一种多媒体对象的相似检索方法，包括：步骤101、通过对多媒体对象进行特征提取，获取多媒体对象的d维特征向量；其中，特征提取是相似性检索的基础之一。其通过特定的算法，提取重要的特征，并结合特征提取函数F，将其映射到d维空间，目的在于将多媒体对象转化为特征向量，所述特征提取包括SIFT特征提取、HARRIS特征提取和SUSAN特征提取。步骤102、对d维特征向量进行降维处理；其中，将d维特征向量的数据空间划分为M个区域，通过iDistance算法，将d维特征向量映射为一维键值，并通过一维索引结构存储所述一维键值及所述d维特征向量，以获得查询数据库，其中，所述数据空间中包括d维特征向量对应的数据点；其中，步骤102还可以包括：步骤102-1、将多个d维特征向量的数据空间划分为m个分区P0、P1、…、Pm-1；步骤102-2、为每个分区选定参照点Q0、Q1、…、Qm-1；步骤102-3、根据d维特征向量对应的数据点p到参照点Qi的距离，将d维特征向量映射为一维键值，其中，一维键值y＝i×c+dist(p，Qi)，0≤i≤m-1，c为弹性系数，dist(p，Qi)为d维特征向量对应的数据点p到参照点Qi的距离；其中，c不小于d＝dist(p，Qi)。步骤102-4、采用映射后的一维键值y建立B+-tree的索引结构,以存储所述一维键值y及所述d维特征向量。步骤103、提取待检索多媒体对象的d维特征向量，并通过iDistance算法，将待检索多媒体对象的d维特征向量映射为一维键值及数据空间中的查询点q；其中，步骤103的具体映射方式与步骤102相同。步骤104、根据查询点q、查询空间及距离度量，修剪掉不需查询的Partition分区及不需查询的数据点；其中，步骤104还可以包括：步骤104-1、将所述查询点q与查询半径r所形成的超球扩展成超立方体；步骤104-2、判断每个Partition是否与所述超立方体相交；步骤104-3、当所述Partition与所述超立方体不相交时，修剪掉不需查询的所述Partition，并扩大查询半径r，重新进行修剪判断，直至KNN检索结束；其中，基于iDistance的kNN检索与传统的kNN检索策略一致，首先选定初始查询半径进行查询，再逐渐扩大半径，直到k个查询对象都被找到，其查询停止的标记为：k个对象内最远对象离查询点的距离不大于查询半径。因每个区域内点的键值在每个页上是顺序存储的，对于查询点q，映射到B+-Tree后，根据查询范围与查询约束，向叶子结点的两边遍历。这种技术的优势是，当查询半径逐渐增大时，同个区域内可以通过这种方式递归查询。对于每个区域如何选择kNN检索遍历策略，包括如下情况：三种情况：第一种情况(Situation1)：当前区域包含查询点q，双向遍历(Outward andInward)；第二种情况(Situation2)：查询点q在当前区域外，但是所形成的超球与区域相交，向内遍历(Inward)；第三种情况(Situation3)：查询点q在当前区域外，其所形成的超球与区域不相交，该区域不需遍历。如图2为kNN检索遍历策略三种情况的示意图，其中，给定三个分区划分P1、P2、P3，对于查询点q，P1需要双向遍历、P2需要内向遍历，P3不需要遍历。如图3所示，查询点q与查询半径r所形成的圆扩展成正方形，不难看出正方形与P2不存在交叉，即满足PP算法中的剪枝情况，不必对原本需要查询的page进行查询，减少了一部分I/O的开销。步骤104-4、当KNN检索结束后，对未修剪的Partition中的数据点p增加数据点到数据空间中心的距离dist(p，center)，判断所述查询点q到数据空间中心的距离dist(q，center)及查询半径r，是否满足dist(p，center)≤r+dist(q，center)，当不满足时，修剪掉数据点p。其中，为每个叶子节点增加了一个属性，该属性记录该点到数据空间中心的距离。剪枝算法通过该点到与中心点的距离、该点到参考点的距离、查询半径作为参数，以三角剪枝的达到降低计算开销的目的，进而提高查询效率为数据空间内的全部数据点增加一个属性字段(包括查询点q)，记录该点到DS中心center的距离。例如采用欧氏距离作为度量标准，p为DS内某个与查询区域相交的page中的的数据点，则存在以下三角不等式规则，可作为剪枝依据：dist(p，q)-dist(q，center)≤dist(p，center)≤dist(p，q)+dist(q，center)；当规定查询点q的查询半径r时，对于q查询半径内的所有候选点p，必须满足：dist(p，center)≤r+dist(q，center)，否则，page内的点将被筛除，以减少I/O开销。步骤105、在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值及查询点与对所述查询空间内的数据点进行查询，以查询待检索多媒体对象的d维特征向量。其中，步骤105还可以包括：步骤105-1、在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值及查询点q与当前partition的情况，对所述查询空间内的数据点进行查询，其中，查询点q与当前partition的情况包括第一种情况和第二种情况；步骤105-2、当第一种情况时，根据查询范围，向B+-Tree树的叶子节点两边进行遍历，查询待检索多媒体对象的d维特征向量对应的数据点p，其中，所述第一种情况为当前Partition包含查询点q；步骤105-3、当第二种情况时，根据查询范围及Partition的半径，向B+-Tree树的叶子节点内部进行遍历，其中，所述第二种情况为查询点q在当前Partition外，且所述查询点q与查询半径r所形成的超球与Partition相交。本发明实施例提出的一种多媒体对象的相似检索方法，通过同时优化I/O开销和计算的高维索引技术AP-iDistance(Advanced pruning iDistance)开销。在判断是否遍历当前partition之前，先判断该查询范围所扩展而成的超立方体是否与当前partition相交，以减少无效的I/O查询，提高查询效率；并在遍历每个page中数据点之前，通过三角剪枝的方法筛除一部分数据点。该方案为每个叶子结点增加了一个属性，该属性记录该点到数据空间中心的距离。剪枝算法通过该点到与中心点的距离、该点到参考点的距离、查询半径作为参数，以三角剪枝的达到降低计算开销的目的，进而提高查询效率。本发明实施例还提供一种多媒体对象的相似检索装置，如图4，包括：特征向量提取模块410，用于通过对多媒体对象进行特征提取，获取多媒体对象的d维特征向量；降维模块420，用于将d维特征向量的数据空间划分为M个区域，通过iDistance算法，将d维特征向量映射为一维键值，并通过一维索引结构存储所述一维键值及所述d维特征向量，以获得查询数据库，其中，所述数据空间中包括d维特征向量对应的数据点；映射模块430，用于提取待检索多媒体对象的d维特征向量，并通过iDistance算法，将待检索多媒体对象的d维特征向量映射为一维键值及数据空间中的查询点q；剪枝模块440，用于根据查询点q、查询空间及距离度量，修剪掉不需查询的Partition分区及不需查询的数据点；查询模块450，用于在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值，对所述查询空间内的数据点进行查询，以查询待检索多媒体对象的d维特征向量。其中，所述降维模块420包括：分区单元421，用于将多个d维特征向量的数据空间划分为m个分区P0、P1、…、Pm-1；映射单元422，用于为每个分区选定参照点Q0、Q1、…、Qm-1，根据d维特征向量对应的数据点p到参照点Qi的距离，将d维特征向量映射为一维键值，其中，一维键值y＝i×c+dist(p，Qi)，0≤i≤m-1，c为弹性系数，dist(p，Qi)为d维特征向量对应的数据点p到参照点Qi的距离；索引单元423，用于采用映射后的一维键值y建立B+-tree的索引结构,以存储所述一维键值y及所述d维特征向量。所述剪枝模块440包括：变换单元441，用于将所述查询点q与查询半径r所形成的超球扩展成超立方体；判断单元442，用于判断每个Partition是否与所述超立方体相交；第一修剪单元443，用于当所述Partition与所述超立方体不相交时，修剪掉不需查询的所述Partition，并扩大查询半径r，重新进行修剪判断，直至KNN检索结束；第二修剪单元444，用于当KNN检索结束后，对未修剪的Partition中的数据点p增加数据点到数据空间中心的距离dist(p，center)，判断所述查询点q到数据空间中心的距离dist(q，center)及查询半径r，是否满足dist(p，center)≤r+dist(q，center)，当不满足时，修剪掉数据点p。所述查询模块450包括：查询执行单元451，用于在经过修剪后的数据点中，确定包含于所述查询空间内的数据点，根据所述一维键值及查询点q与当前partition的情况，对所述查询空间内的数据点进行查询，其中，查询点q与当前partition的情况包括第一种情况和第二种情况；第一遍历单元452，用于当第一种情况时，根据查询范围，向B+-Tree树的叶子节点两边进行遍历，查询待检索多媒体对象的d维特征向量对应的数据点p，其中，所述第一种情况为当前Partition包含查询点q；第二遍历单元453，用于当第二种情况时，根据查询范围及Partition的半径，向B+-Tree树的叶子节点内部进行遍历，其中，所述第二种情况为查询点q在当前Partition外，且所述查询点q与查询半径r所形成的超球与Partition相交。通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的硬件平台的方式来实现，当然也可以全部通过硬件来实施，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案对背景技术做出贡献的全部或者部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。以上对本发明进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。