3.1.2  DVWs和DVPs的生成
DVWs是用来捕捉某些物体或场景，从而他们需要一些独特的特征：1）如果一个对象或场景出现在一些图片中，描述它的DVWs应更频繁地出现在这些图像之中。此外，他们应该较少的出现在不包含这种对象或场景的图像里面。2）他们应经常位于对象或场景之中，即使场景或物体被杂乱的背景所包围。
DVPs被定义为描述并通常共同出现的在一个约束在一定的空间距离物体或场景类别中的视觉图像词对。为了找出这种视觉词对，并计算其共同出现的频率，需要利用旋转不变的空间直方图如图3所示为DVP产生候选。空间直方图通常用于相似点之间的空间关系计算。图3，每个共同出现的视觉词对在直方图里被视作为DVP候选。
 
图3
3.2  取样数据集建立的方法
首先使用WordNet V.2.1提取得到117097个非抽象的图像词例关于对象和场景的全面列表。然后用从谷歌图片搜索和下载提取的列表图像类别中的图像。每次查询保存最顶端返回的250个图像。在收集的原始数据库中小于的100图像类别已经滤除。然后，通过查看在每个类别的缩略图，我们从剩余图像精心挑选了1506类视觉一致的单个物体或场景。最后，我们建立了一个376500个图像组成的数据集。
由于收集的数据集是大型并且具有代表性，因此，在此基础上提取和选择DVWs和DVPs将具有静态意义。根据收集到的数据集，包含32357词汇树产生的视觉字。根据收集到的数据集，包含32357词典树产生的视觉字。不会生成储量庞大的视觉字，是出于以下三个方面的考虑：
1）大量的视觉词语，将可能导致出现大量视觉词对，使每个DVP候选的重复性降低。
2）无论如何优良的比例，单一的视觉字显示的描述能力有限。
3）训练图像均匀地从代表数据库选择，以获得尽可能对功能空间更好的描述。基于生成的视觉字，整个图像数据集（376500）用于候选的生成和最终DVW和DVP选择。
3.3  建立和使用词典树
词典树是用分层k-means聚类定义的一个分层量化。一个大的样本描述向量集合被用于非监督测试的词汇树中。
与将k定义为集合或量化单元的最终数值不同，K定义的是词典树的分支因子（子节点的数值）。首先，初始KMEANS进程在测试数据中运行，定义为ķ聚类中心。然后将测试数据分成K组，每个组包括最接近一个特定分类中心的描述载体。
将递归应用到每个描述符向量的分组中，与通过拆分每个量化单元形成k新的部分来进行递归定义量化单元，是同样的步骤。
词典树是逐级逐级确定的，直到确定至最大级别数L，并且每个分为k部分的分支只能由属于父量化单元的描述载体的分布来定义。这个过程如图4所示
 
图4 一个词典树在建立过程中的说明
分层量化定义在以k为中心（在这种情况下K = 3）的
每个级别和他们的泰森多边形（Voronoi）区域。
在网上阶段，每个描述符向量通过在每一层比较描述向量和k的候选聚类中心（由k在词典树中的子节点表示），并选择最接近的点，简单地沿着词典树向下传播。非常容易的就可以在每一层生成k个点，总共得到kL个点，如果k不是特别庞大的话，这样的方式是非常有效的。词典树向下的路径可以由一个单一的整数来进行编码，并可以用于记录。
值得关注的是，词典树以一种综合的方式定义了图像词和一个有效的搜索程序。与定义一个非层次结构的图像词不同，我们需要制定一个近似近邻搜索，以便找到有效的视觉字。如果保证了一致性和确定性，后者的做法也能在原来的空间定义量化单元，尽管这样，采用无缝选择仍然更具有吸引力。采用分层的方式也使随后的记录过程更加灵活。 部分重复图像匹配中局部特征词典建立研究(4):http://www.751com.cn/tongxin/lunwen_2484.html