使用随机量化词汇树的检索方法及基于其的图像检索方法

技术领域

本发明图像检索技术领域，特别涉及使用随机量化词汇树的检索方法及基于其的图像检索方法。

背景技术

近年来，随着数字技术特别是网络技术的发展与普及、物联网和计算机信息采集软硬件技术的发展，越来越多的数据被采集和存储，数量采集的速度已经远远超过了传统方法能够处理它们的速度，而且这个趋势越来越明显。Facebook是世界排名领先的照片分享站点，截止到2013年11月每天上传约3.5亿张照片，而仅在Facebook 上的照片容量已经达到了250PB；在数字视频方面，YouTube在2013 年的统计数据显示，每分钟上传72小时以上的视频内容，每天有40 亿个网站视频播放请求，且这些数据仍在大幅增加。对于如此巨大的数据资源和同样海量的访问需求，如何有效地组织、管理和检索大规模数据库，成为迫切需要解决的问题。

传统的基于文本的图像检索方法，采用关键字对图像进行注释，将图像检索变成对关键字的查找。其明显的缺点是：计算机视觉与人工智能技术都无法对图像自动进行文本标注，需要依赖人工标注。由于数据规模不断膨胀，人工标注的速度远远赶不上图像数据的膨胀速度，而且由于人工标注的主观性和不精确性，不同人对图像的理解不同，导致对图像的注释没有一个统一的标准。为了克服基于文本的图像检索方法的局限性，20世纪90年代出现了基于内容的图像检索 (Content Based-Image Retrieval，CBIR)。它区别于传统的检索手段，融合图像理解技术，提供一种从大容量的图像数据库中，根据人们提出的要求进行有效检索的方法。

基于内容的图像检索系统的基本思想是对图像的视觉特征进行分析并联系上下文进行检索。它的实现方法是采用图像数据库存储并管理图像数据，然后将基于内容的图像检索技术作为数据库的引擎嵌入图像数据库中，提供基于内容的图像检索功能。在现有的基于内容的图像检索系统中普遍采用低层的图像信息，包括图像的颜色、纹理、形状以及它们之间的空间关系等内容，计算查询图像和目标图像之间的相似度，然后按照相似度的大小，即图像特征之间的匹配程度进行检索。因此，首先采用特征提取把图像库中的每一幅图像都转化为图像特征空间中的一个点，即对应的特征向量，然后，根据特征向量进行图像的检索，从而将基于内容的图像检索转化为对图像特征空间中特征点的检索。

在图像数据库规模较小的情况下，最常用的图像特征检索方法是顺序扫描方法。但是，随着人们获取信息的手段不断发展和信息需求的不断增长，图像数据库的规模越来越大，传统的顺序扫描方法已经无法满足用户对于检索时间的要求。因此，通过对数据进行有效的组织以快速缩小检索范围，提高检索速度，从而建立一个高效的索引机制，是基于内容检索的关键所在。

在以往的相关研究中，研究者们针对特定的应用领域，提出了许多数据索引方法。然而，这些数据索引方法在处理高维数据时，都受到高维空间“维度灾难”的影响，当数据维度增大时，其检索性能退化到顺序扫描，甚至比顺序扫描性能还差。由于在CBIR研究中，从原始图像中提取的特征向量通常都是高维的，对于图像特征数据的索引不可避免的受到“维度灾难”的影响。Nister和Stewenius提出了基于词汇树的检索方法在高维空间表现出很好的检索效果，但是，其对高维空间的建树时间很长，难以满足现代数据库对检索时效性的要求。因此，针对图像特征数据的高维特性，建立高效的高维数据索引机制，是当前图像检索研究所面临的一个重要挑战。

发明内容

本发明提供了一种使用随机量化词汇树的检索方法及基于其的图像检索方法，旨在解决现有技术中存在的上述缺陷。

为达到上述技术目的，本发明采用如下技术方案：

使用随机量化词汇树的检索方法，包括以下步骤：

(1)产生一个最近邻搜索树，将整个数据库的所有特征向量作为第一节的根节点，向下分节；

(2)第二级中，从整个数据库中随机选取k个点作为簇的中心，然后根据所选择的相似性度量方法，将每个特征向量分配到离其最近的簇中心，将整个数据库分为k个子集，继续向下分节；

(3)第三级中，对于每一个从第二级获得的k个簇中，从它们的特征向量池中随机选取k个特征点作为其下一级的聚类中心，然后利用相似性度量方法将每个特征向量分配到离其最近的簇中心，从而在第三级上形成k²个簇；

(4)重复步骤(2)、(3)，直至所有叶节点包含的特征向量都属于同一类对象或叶节点包含的特征向量的数量低于一定的限制；其中每个特征向量都有一个与它相关的类标签。

在步骤(2)中，特征向量到两个或者两个以上的簇中心距离相等，则随机选择一个簇。

在步骤(3)中，从特征向量池中选出的新的特征向量，将其分配到离其最近的簇中心，当到达分配的簇中心的叶节点时，如果该叶节点中所有特征向量点具有相同的类标号，则分配相关联的类标签给新的特征向量，然后停止运算；否则，重新在分配簇中进行搜索，选择簇中与新的特征向量距离最短的特征向量，并且将该特征向量相关联的类标签分配给新的特征向量，随后停止运算。

一种基于随机量化词汇树的检索方法的图像检索方法，包括以下步骤：

(1)首先通过重叠分块方法，将图像分成若干相互重叠的子区域；

(2)将图像的特征信息块与其语义特征相结合；由于每一个提取的特征向量，对应于特征空间的一个点，通过对特征空间中的特征点进行无指导学习(即数据挖掘中的聚类)，将特征向量库中的所有特征向量划分成多个模式，使得在同一个类中的模式之间具有更多的相似性，在不同类中的模式之间具有较大的相异性；通过类标号对特征点进行标记，每一个类标号具有特定的语义信息，将图像特征信息块与语义特征相结合，对图像的不同区域进行解释，以建立图像知识库；

(3)产生一个最近邻搜索树，将图像知识库中的所有图像特征向量作为第一节的根节点，向下分节；

(4)第二级中，从图像知识库中随机选取k个点作为簇的中心，然后根据所选择的相似性度量方法，将每个图像特征向量分配到离其最近的簇中心，将整个数据库分为k个子集，继续向下分节；

(5)第三级中，对于每一个从第二级获得的k个簇中，从它们的特征向量池中随机选取k个特征点作为其下一级的聚类中心，然后利用相似性度量方法将每个图像特征向量分配到离其最近的簇中心，从而在第三级上形成k²个簇；

(6)重复步骤(2)、(3)，直至所有叶节点包含的图像特征向量都属于同一类对象或叶节点包含的图像特征向量的数量低于一定的限制；其中每个图像特征向量都有一个与它相关的类标签。

在步骤(1)中，重叠分块方法将大小为height×weight的图像用N×N 的窗口进行划分，行和列方向按Nhop个像素移位，划分成若干相互重叠的子区域，为了使图像中包含的足够小的对象可以被检测出来，缩小方块窗口尺寸，增加补丁数量；通过相互重叠子区间，将颜色直方图与颜色的空间分布相结合。

在步骤(2)中，建立图像知识库过程中，使用Chameleon聚类算法和基于MST的聚类算法，对图像的彩色直方图特征向量库进行聚类，对聚类结果设置类标号，建立基于彩色直方图特征的知识库。

采用以上技术方案，具有如下有益效果：

(1)本发明的图像检索方法克服了现有技术中词汇树建立需要大量的时间的问题，可以在很短的时间内建立词汇树，满足实时性要求；

(2)本发明通过使用重叠分块方法，将图像细化成多个块提取图像的彩色直方图作为特征向量库，有效的将图像的彩色直方图与颜色空间信息相结合，克服了现有技术中图像特征提取时忽略颜色的空间特性这一问题；

(3)本发明可以更加快速的提取图片特征，满足实时性要求，同时对特征数据库进行无指导学习，通过区域标记对场景图像的不同区域进行标记，形成知识库。

附图说明

图1是本发明的示意图；

图2是本发明重叠分块法的示意图；

图3是21-14的10648维RGB直方图的聚类结果；

图4是24-16的5000维HSV直方图的聚类结果；

图5是24-16的5832维Opponent直方图的聚类结果；

图6是21-14的10648维Transformed直方图的聚类结果；

图7是21-14组RGB直方图准确率对比图；

图8是24-16组RGB直方图准确率对比图；

图9是27-18组RGB直方图准确率对比图。

具体实施例

下面结合附图、实施例，对本方案进行进一步说明。

如图1所示，使用随机量化词汇树的检索方法，包括以下步骤：

(1)产生一个最近邻搜索树，将整个数据库的所有特征向量作为第一节的根节点，向下分节；

(2)第二级中，从整个数据库中随机选取k个点作为簇的中心，然后根据所选择的相似性度量方法，将每个特征向量分配到离其最近的簇中心，将整个数据库分为k个子集，继续向下分节；

(3)第三级中，对于每一个从第二级获得的k个簇中，从它们的特征向量池中随机选取k个特征点作为其下一级的聚类中心，然后利用相似性度量方法将每个特征向量分配到离其最近的簇中心，从而在第三级上形成k²个簇；

(4)重复步骤(2)、(3)，直至所有叶节点包含的特征向量都属于同一类对象或叶节点包含的特征向量的数量低于一定的限制；其中每个特征向量都有一个与它相关的类标签。

在步骤(2)中，特征向量到两个或者两个以上的簇中心距离相等，则随机选择一个簇。

在步骤(3)中，从特征向量池中选出的新的特征向量，将其分配到离其最近的簇中心，当到达分配的簇中心的叶节点时，如果该叶节点中所有特征向量点具有相同的类标号，则分配相关联的类标签给新的特征向量，然后停止运算；否则，重新在分配簇中进行搜索，选择簇中与新的特征向量距离最短的特征向量，并且将该特征向量相关联的类标签分配给新的特征向量，随后停止运算。

对于大型数据库，随机量化树的检索方法选择遵循词汇树的思想，但在其基础上做了一个重要的改进，产生一个最近邻搜索树。如图1 所示，给定数据库，在第一级中只有一个节点，包含所有的特征向量，成为根节点。第二级，从整个数据库中随机选取K个点作为簇的中心，然后根据所选择的相似性度量方法，将每个特征向量分配到离其最接近的簇中心，将整个数据库分为K个子集。在第三级，对于每一个从第二级获得的K个簇中，从它们的特征向量池中随机选取K个特征点作为其下一级的聚类中心，然后利用相似性度量方法将每个特征向量分配到离其最近的簇中心，从而在第三级上形成K个簇。继续这个过程，直到所有叶节点包含的特征向量都属于同一类对象(即，该节点是纯净的)或叶节点包含的特征向量的数量低于一定的限制(例如， 50)。每个特征向量都有一个与它相关的类标签。

在对树进行分支时，通过一个最近邻搜索树，每个数据到其他数据项的距离可以被更新到一个更小的值。这种策略保证了空间中最接近的数据点更可能被分配到同一分区中。然而，因为分区中的任意一个数据点，相比于其他分区的中心，都最接近它自己的簇中心(并不是最近邻)，如果数据点到两个或更多个簇的中心的距离相等，数据点则随机选择一个簇。

通过随机量化树搜索给定的新的特征向量。新的特征向量沿着随机量化树的某一特定路径，在每一层上计算该特征向量到K个簇中心的距离，结果是这个新的特征向量到K个簇中心点距离最近的一个簇中心点。当到达叶节点时，如果该叶节点是纯净的(即，叶节点中所有特征向量点具有相同的类标号)，分配相关联的类标签给新的特征向量，然后停止运算。否则，在相关簇的向量中做一个最近邻搜索，搜索的结果是根据所选择的相似性度量方法得到的最短距离的特征向量，并将该特征向量相关联的类标签分配给新的特征向量，然后停止运算。

一种基于随机量化词汇树的检索方法的图像检索方法，包括以下步骤：

(1)首先通过重叠分块方法，将图像分成若干相互重叠的子区域；

(2)将图像的特征信息块与其语义特征相结合；由于每一个提取的特征向量，对应于特征空间的一个点，通过对特征空间中的特征点进行无指导学习(即数据挖掘中的聚类)，将特征向量库中的所有特征向量划分成多个模式，使得在同一个类中的模式之间具有更多的相似性，在不同类中的模式之间具有较大的相异性；通过类标号对特征点进行标记，每一个类标号具有特定的语义信息，将图像特征信息块与语义特征相结合，对图像的不同区域进行解释，以建立图像知识库；

(3)产生一个最近邻搜索树，将图像知识库中的所有图像特征向量作为第一节的根节点，向下分节；

(4)第二级中，从图像知识库中随机选取k个点作为簇的中心，然后根据所选择的相似性度量方法，将每个图像特征向量分配到离其最近的簇中心，将整个数据库分为k个子集，继续向下分节；

(5)第三级中，对于每一个从第二级获得的k个簇中，从它们的特征向量池中随机选取k个特征点作为其下一级的聚类中心，然后利用相似性度量方法将每个图像特征向量分配到离其最近的簇中心，从而在第三级上形成k²个簇；

(6)重复步骤(2)、(3)，直至所有叶节点包含的图像特征向量都属于同一类对象或叶节点包含的图像特征向量的数量低于一定的限制；其中每个图像特征向量都有一个与它相关的类标签。

如图2所示，在步骤(1)中，重叠分块方法将大小为height×weight 的图像用N×N的窗口进行划分，行和列方向按Nhop个像素移位，划分成若干相互重叠的子区域，为了使图像中包含的足够小的对象可以被检测出来，缩小方块窗口尺寸，增加补丁数量；通过相互重叠子区间，将颜色直方图与颜色的空间分布相结合。用重叠子区间将大小的图像划分为多个方块：

行数：blockrows＝(height-N)/Nhop+1

列数：blockcols＝(weidth-N)/Nhop+1

方块补丁数：numofSamples＝blockrows×blockcols

图像大小为height×weight个像素，产生的处理后的图像的尺寸大小由补丁窗口的大小决定。通过图片的补丁窗口大小变化，产生的方块补丁的数量也会发生变化。当补丁窗口缩小时，处理图像产生的方块补丁数量会增加，反之亦然。此时，处理后的图像中，每一个像素用一个方块补丁的颜色直方图表示。方块窗口的大小直接影响了处理后的图像的分辨率。因此，这限制了补丁方块窗口的尺寸不能过大，使得需要用较多数量的补丁来表示完整的图像信息。即意味着每幅图像的补丁数增多。

单纯的对图像进行分块提取其颜色直方图，只是将图像单独地划分成没有任何语义信息的块。将图像的特征信息块与其语义特征相结合是建立图像知识库的目的。由于每一个提取的特征向量，对应于特征空间的一个点，通过对特征空间中的特征点进行无指导学习(即数据挖掘中的聚类)，将特征向量库中的所有特征向量划分成多个模式，使得在同一个类中的模式之间具有更多的相似性，在不同类中的模式之间具有较大的相异性。通过类标号对特征点进行标记，每一个类标号具有特定的语义信息，将图像特征信息块与语义特征相结合，对图像的不同区域进行解释。

在步骤(2)中，建立图像知识库过程中，使用Chameleon聚类算法和基于MST的聚类算法，对图像的彩色直方图特征向量库进行聚类，对聚类结果设置类标号，建立基于彩色直方图特征的知识库。

下面通过实验的方式，来进一步表明本发明的优越性。

图像特征数据的聚类

对特征向量数据库分别采用chameleon聚类算法和基于MST 的聚类算法进行聚类，将图像中的物体划分成多个簇，并对簇进行标记，形成知识库。并采用彩色图像表现聚类后的数据库。通过将原始图像集、基于MST的聚类结果图像、Chameleon聚类结果图像三者进行对比，验证本文对图像特征的提取方法的可行性。

实验中，由于图像数据集中图像比较多，我们仅对数据库中的部分图像聚类结果进行展示，同时由于特征数据库具有多组，我们分别对RGB空间，HSV空间，Opponent空间及Transformed空间的一组聚类结果进行展示。

表1基于RGB颜色直方图RGB知识库中主要场景及其语义关系

如图3所示，图中为21-14的10648维RGB直方图的聚类结果。

表2基于HSV颜色直方图HSV知识库主要场景及其语义关系

如图4所示，图中为24-16的5000维HSV直方图的聚类结果。

表3基于Opponent颜色直方图Opponent知识库主要场景及其语义关系

如图5所示，图中为24-16的5832维Opponent直方图的聚类结果。

表4基于Transformed颜色直方图Transformed知识库中主要场景及其语义关系

如图6所示，图为21-14的10648维Transformed直方图的聚类结果。

提取特征速度

选用图像大小为720×1280个像素，采用21×21补丁窗口大小，移动像素值设置为14(表示为21-14)，则处理后的图像的尺寸大小为 50×90像素；当采用24×24补丁窗口大小时，移动像素值设置为16(表示为24-16)，则处理后的图像大小为；当采用27×27补丁窗口大小时，移动像素值设置为18(表示为27-18)，则处理后的图像大小为 39×70。

通过更加细化的重叠分块方法，将图像划分成4500个块、3476 个块、2730个块，并提取每个块的彩色直方图。以往的图像分块，主要提取图像的灰度颜色直方图，或者HSV颜色直方图，本文中，提取图像的RGB颜色直方图、HSV颜色直方图、Opponent颜色直方图及Transformed颜色直方图，建立图像特征向量库。

实验中，对720×1280大小的35幅图像，分别采用21-14，24-16，27-18三种重叠分块方法提取图像的RGB颜色直方图10000维、HSV 颜色直方图10648维、Opponent颜色直方图10000维、Transformed 颜色直方图10000维、Gabor纹理特征，以及提取相同图像的SIFT 特征点。

本实验分别统计35幅图片不同特征的提取时间，每幅图像特征提取的平均值如下表所示。

表5

表5显示：采用相同的图像分块方法，即使提取图像的高维颜色直方图，其提取速度明显优于Gabor纹理特征的提取方法速度；同时，提取整幅图像的SIFT特征点花费的时间也比分块后提取其颜色直方图的时间缓慢很多。因此，本文采用的特征提取方式可以快速的提取图像特征。

准确率

由于最近邻检索是检索对象与其最近邻属于同一类，其检索准确度最高。我们以最近邻作为标准检索结果集。通过将词汇树的检索结果，随机量化树检索的结果与最近邻检索结果进行比较，分析两种树的检索准确率。

RGB直方图准确率对比

首先，我们针对RGB颜色空间中不同组(21-14，24-16，27-18) 的多个维度(64维，125维，216维，512维，1000维，2744维，5832 维，10648维)，共24组训练集进行检索，对比结果表2，表3，表4 所示，其中KQtree为随机量化词汇树，VTree为传统的词汇树。

RGB直方图准确率对比结果：从图7、图8、图9显示出，随机量化树的准确率明显高于词汇树的准确率。

在图8，随机量化树的准确率在1000维最高，达到83.03％，并且显示出高维的检索结果比低维检索结果好。在图9中，随机量化树在维数为5832时准确率最高，达到86.73％，也显示出高维的检索结果比低维好。在图9中，随机量化树在512维准确率最高，达到85.49％，高维数据检索效果比低维数据检索效果好，但是不明显，中间维度的检索效果最好。

图7、图8、图9一起对比，我们发现RGB颜色直方图总体上在高维数据空间的检索效果比低维数据空间的检索效果好，同时，针对于不同的方块窗口大小，窗口越小，方块补丁数越多，图像信息越丰富，但并不是方块补丁越多，图像的检索准确率越高，不同维度具有不同的表现，没有统一规律。

建立词汇树时间

随机量化树和词汇树在RGB直方图中不同组(21-14，24-16， 27-18)的多个维度(64维，125维，216维，512维，1000维，2744 维，5832维，10648维)的运行时间，如表6、表7、表8所示，单 位为秒，其中KQtree为随机量化词汇树，VTree为传统的词汇树。

表6窗口21×21，移位14，随机量化词汇树和词汇树在RGB直方图不同维度运行时间

表7窗口24×24，移位16，随机量化词汇树和词汇树在RGB直方图不同维度运行时间

表8窗口27×27，移位18，随机量化词汇树和词汇树在RGB直方图不同维度运行时间

在RGB直方图中，随机量化树的运行速度明显比词汇树的运行速度快。随着RGB直方图维数的增加，词汇树运行时间比随机量化树运行时间成几何倍数增加。

随机量化词汇树和词汇树在Opponent直方图中不同组(21-14， 24-16，27-18)的多个维度(64维，125维，216维，512维，1000 维，2744维，5832维，10648维)的运行时间，如表9，10，11所 示，单位为秒。

表9窗口21×21，移位14，随机量化词汇树和词汇树在Opponent直方图不同维度运行时间

表10窗口24×24，移位16，随机量化词汇树和词汇树在Opponent直方图不同维度运行时间

表11窗口27×27，移位18，随机量化词汇树和词汇树在Opponent直方图不同维度运行时间

在Opponent直方图中，随机量化树的运行速度明显比词汇树的运行速度快。随着Opponent直方图维数的增加，词汇树运行时间比随机量化树运行时间成几何倍数增加。

综上可以看出，随机量化词汇树的检索方法在时间效率上，明显优于词汇树。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员，在不脱离本发明原理的前提下，还可以做出若干改进和补充，这些改进和补充也应视为本发明的保护范围。