采用非分层的方式增加词典的规模会使计算成本会非常高，然而采用分层的方法计算成本会是叶节点数目的对数。在叶节点 的数量上内存的使用情况是线性的。描述载体的总数有必要表示为 。对于D文的描述来说用char表示大概是 字节。就我们目前的实验来说，一个参数为D = 128, L =6以及k = 10的词典树来说，产生1M的叶节点需要占用148MB的内存。
4    空间检查以及检索
 
图 5
    如图5所示，一个倒置的文件索引结构用于大规模的索引和检索。每个视觉字在包含该视觉字出现的图像列表的索引中拥有一个项。我们并不需要了解本地的SIFT特征的准确位置。相反，我们只需要记录的相对空间位置的局部特征。因此，它足以存储每个特征的x坐标和y坐标的排序顺序，这将在查询时用于生成空间编码映射。因此，对于每个被索引的特征，我们保存了它的图像识别码，SIFT的方向向量值以及其相应的x和y坐标排列顺序。
我们制定的图像检索非常类似于投票表决问题。每个视觉字的图像查询取决于它的匹配图像。直观地说，TF-IDF的权重[2]可以用来区分不同的匹配功能。然而，从实验中，我们发现单纯地对匹配功能计数能够得到更近似的或更好结果。此外，为了区别与相同数量的图像正样例匹配但不同于误报匹配或不同特征的数量的情况，定义了一个空间检查的长期任务。
TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜寻引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，因特网上的搜寻引擎还会使用基于连结分析的评级方法，以确定文件在搜寻结果中出现的顺序。
5    实验
基于本文中的算法，我用C++实现了一个图像检索系统，利用了openCV库并使用MFC做了界面。主界面见图6
从互联网上用爬取了10万多张图片作为该系统的图片库，由于目前还没有公开的用于部分内容复制图像检索的评价数据库，我从Google和Tineye上收集了29组总计815张图片用于测试，每组图像都互为其部分内容重复图像，其中一些典型的例子展示在图N到图M。
 
图6图像检索系统的主界面
从每组测试图片中挑选3张进行检索，也就是总计87张图片进行检索，采用mAp（Mean average precision）[6]作为检索精准度的度量。本实验在3.3GHz CPU,4GB内存的计算机上进行。
由于图片库的这10万多张图片，有可能其中一些是测试图片集的部分内容重复图像，所以先对每一张测试图像进行检索，人工发现这些图片，并将其加入到测试图片集中。从每组测试图片中挑选3张进行检索，也就是总计87张图片进行检索，采用mAp（Mean average precision）作为检索精准度的度量。关于检索大致的流程图见图7
 
图 7图像检索的流程图
局部特征词典的大小描述的是特征空间分割的程度，由于本文提到的空间信息检查方法可以有效的的发现并移除错误的匹配，所以可以使用更小的局部特征词典，从而使匹配变得更加鲁棒。在10万张的图片库上，测试了4种不同大小的特征词典。从图8（a）可以看出，当特征词典的大小从12K增大到500K，mAP逐渐减小,图8（b）中，当使用很小的特征词典时，平均每次检索的时间开销很高，但随着词典变大迅速减小，而后在130K处趋于平稳。 部分重复图像匹配中局部特征词典建立研究(5):http://www.751com.cn/tongxin/lunwen_2484.html