本发明公开了一种大规模图像词汇树检索方法，属于计算机视觉领域。本发明算法针对GPU平台的结构特点，采用了一种新颖的词汇树数据结构，并将传统的SIFT特征点进行模块化组织，使得其能充分利用GPU大规模并行计算的能力，大大提高大规模图像SIFT特征点映射的效率。在将批量的SIFT特征点映射成直方图之后，再采用快速的紧凑化方法对原始的倒排索引方案进行增强改进，使得其后的视觉词汇独特性表达、直方图归一化与查询图像的评分都得到了一定的提速。本发明还实现了基于GPU加速的大规模图像词汇树检索系统，不仅对图像检索本身有重大的加速意义，也对大规模场景的三维重建算法的效率提高有着巨大的影响。
1.一种基于GPU加速的大规模图像词汇树检索方法，其特征在于，该方法包括以下步骤：(1)输入待查询图像；
(2)利用图像中每个SIFT特征点在词汇树中最相似视觉词汇构建每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
(3)利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数，具体采用以下公式更新：qi＝niωi，
其中，qi表示一幅图像中第i个视觉词汇的新频数；ni代表一幅图像中第i个视觉词汇的原频数，ωi为相应视觉词汇的权重；最后采用L1范数对图像索引列表进行计算，得到每幅图像的描述符长度，并以此长度对每幅图像直方图进行归一化；
(4)利用待查询图像直方图和预先准备的数据库图像直方图，采用直方图交叉核计算所有数据库图像和待查询图像的相似性，对所有数据库图像的相似性进行排序，得到和待查询图像相似性最高的数据库图像；所述采用直方图交叉核计算所有数据库图像和待查询图像的相似性具体为采用以下公式：其中，h1和h2分别表示待查询图像和数据库图像的描述直方图，I(h1,h2)表示相似性，h1(i)和h2(i)分别表示待查询图像直方图和数据库图像直方图第i个视觉词汇的最终频数；
所述词汇树的结构为地址连续的数组结构，采用广度优先搜索结合堆栈的方法将视觉词汇的树结构转换为地址连续的数组结构，用数组的一个元素表示词汇树的一个节点；所述数组结构的一个元素包括SIFT特征描述符、节点ID、该节点的子节点数和其第一个子节点的地址偏移量属性。
2.根据权利要求1所述的一种大规模图像词汇树检索方法，其特征在于，所述步骤(4)中预先准备的数据库图像直方图具体采用以下步骤获得：(21)批量输入数据库图像；
(22)利用图像中SIFT特征点在词汇树中找出最相似视觉词汇构建每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
(23)根据视觉词汇索引列表的数据，采用以下公式计算每个视觉词汇在图像数据库中的权重：其中，N代表图像数据库中所有图像总数目，Ni代表第i个视觉词汇下对应有多少幅数据库图像与其相关，ωi为第i个视觉词汇的权重，当Ni为0时，记ωi为0；
(24)利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数；最后采用L1范数对图像索引列表进行计算，得到每幅数据库图像的描述符长度，并以此长度对每幅数据库图像直方图进行归一化。
3.根据权利要求1或2所述的一种大规模图像词汇树检索方法，其特征在于，所述视觉词汇索引列表以视觉词汇为关键字，索引包含该视觉词汇的图像ID和该视觉词汇在该图像中出现的频数；图像索引列表以图像ID为关键字，索引该图像包含的视觉词汇ID和该视觉词汇在该图像中出现的频数。
4.根据权利要求1或2所述的一种大规模图像词汇树检索方法，其特征在于，所述利用图像中SIFT特征点在词汇树中找出最相似视觉词汇构建描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表具体包括以下步骤：(31)提取每幅图像的SIFT特征点，并剔除其中尺度小于设定阈值的SIFT特征点；
(32)将图像的SIFT特征点用新的存储结构表示，存储结构包括SIFT特征描述符、所属图像ID和所属视觉词汇ID属性；
(33)按深度优先搜索的形式在GPU每个线程中对每幅图像的每个SIFT特征点进行查找，查找每个SIFT特征点在词汇树中和其最相近的视觉词汇，由每幅图像的所有SIFT特征点对应的所有视觉词汇组成描述每幅图像的图像直方图；
(34)建立一个视觉词汇索引列表和图像索引列表，当一个视觉词汇在一个图像中的频数为零的时候则删除该索引。
5.一种基于GPU加速的大规模图像词汇树检索系统，其特征在于，该系统包括以下模块：查询图像输入模块，用于输入待查询图像；
图像直方图构建模块，用于利用GPU多线程并行计算出图像中每个SIFT特征点在词汇树中最相似视觉词汇，由每幅图像的所有SIFT特征点对应的视觉词汇组成描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
图像直方图归一化模块，用于利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数，具体采用以下公式更新：qi＝niωi，
其中，qi表示一幅图像中第i个视觉词汇的新频数；ni代表一幅图像中第i个视觉词汇的原频数，ωi为相应视觉词汇的权重；最后采用L1范数对图像索引列表进行计算，得到每幅图像的描述符长度，并以此长度对每幅图像直方图进行归一化；
图像检索模块，用于利用待查询图像直方图和预先准备的数据库图像直方图，采用直方图交叉核计算所有数据库图像和待查询图像的相似性，对所有数据库图像的相似性进行排序，得到和待查询图像相似性最高的数据库图像；所述采用直方图交叉核计算所有数据库图像和待查询图像的相似性具体为采用以下公式：其中，h1和h2分别表示待查询图像和数据库图像的描述直方图，I(h1,h2)表示相似性，h1(i)和h2(i)分别表示待查询图像直方图和数据库图像直方图第i个视觉词汇的最终频数；
所述词汇树的结构为地址连续的数组结构，采用广度优先搜索结合堆栈的方法将视觉词汇的树结构转换为地址连续的数组结构，用数组的一个元素表示词汇树的一个节点；所述数组结构的一个元素包括SIFT特征描述符、节点ID、该节点的子节点数和其第一个子节点的地址偏移量属性。
6.根据权利要求5所述的一种基于GPU加速的大规模图像词汇树检索系统，其特征在于，所述数据库图像直方图具体包含以下模块：数据库图像输入模块，用于批量输入数据库图像；
图像直方图构建模块，用于利用GPU多线程并行计算出图像中每个SIFT特征点在词汇树中最相似视觉词汇，由每幅图像的所有SIFT特征点对应的视觉词汇组成描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
视觉词汇权重计算模块，用于根据视觉词汇索引列表的数据，采用以下公式计算每个视觉词汇在图像数据库中的权重：其中，N代表图像数据库中所有图像总数目，Ni代表第i个视觉词汇下对应有多少幅数据库图像与其相关，ωi为第i个视觉词汇的权重，当Ni为0时，记ωi为0；
数据库图像直方图归一化模块，用于利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数；最后采用L1范数对图像索引列表进行计算，得到每幅数据库图像的描述符长度，并以此长度对每幅数据库图像直方图进行归一化。
7.根据权利要求5或6所述的一种基于GPU加速的大规模图像词汇树检索系统，其特征在于，所述视觉词汇索引列表以视觉词汇为关键字，索引包含该视觉词汇的图像ID和该视觉词汇在该图像中出现的频数；图像索引列表以图像ID为关键字，索引该图像包含的视觉词汇ID和该视觉词汇在该图像中出现的频数。
8.根据权利要求5或6所述的一种基于GPU加速的大规模图像词汇树检索系统，其特征在于，所述图像直方图构建模块具体包括以下单元：特征点提取单元，用于提取每幅图像的SIFT特征点，并剔除其中尺度小于设定阈值的SIFT特征点；
特征点转换单元，用于将图像的SIFT特征点用新的存储结构表示，存储结构包括SIFT特征描述符、所属图像ID和所属视觉词汇ID属性；
图像直方图构建单元，用于按深度优先搜索的形式在GPU每个线程中对每幅图像的每个SIFT特征点进行查找，查找每个SIFT特征点在词汇树中和其最相近的视觉词汇，由每幅图像的所有SIFT特征点对应的所有视觉词汇组成描述每幅图像的图像直方图；
索引列表建立单元，用于建立一个视觉词汇索引列表和图像索引列表，当一个视觉词汇在一个图像中的频数为零的时候则删除该索引。
一种基于GPU加速的大规模图像词汇树检索方法及系统
技术领域
[0001] 本发明属于计算机视觉领域，更具体地，涉及一种基于GPU加速的大规模图像词汇树检索方法及系统。
背景技术
[0002] David Nistér等人提出的词汇树算法由于其使用树的结构来对视觉词汇进行量化，并将视觉词汇的量化和索引集成为一体，再结合文本搜索技术来加快图像描述符的相似性判断，使其具有较高的准确率和效率，在目标识别、场景识别和三维重建等场合有着十分广泛的应用。
[0003] 原始的词汇树算法主要包含视觉词汇的学习、词汇树构建及词汇树查询三个阶段。
[0004] 在视觉词汇学习阶段，采用层次性k-means聚类来生成结构化的视觉词汇。首先需要提取数据库图像中每幅图像的尺度不变特征变换(Scale-Invariant Feature Transform，SIFT)特征点来对图像进行描述表达。由于所提取的数据库图像的特征点集合有着非常大的信息冗余，每个SIFT特征点对于描述一幅图像有着不同的重要性，因此需要采用聚类算法来提取有用的信息，也就是图像的视觉词汇。不同于一般的聚类算法，词汇树算法采用层次性的k-means聚类算法。也就是，首先对所有的SIFT特征点采用k-means算法生成k个簇中心，将这些SIFT特征点分成k个簇，然后再对每一份SIFT特征点集使用k-means聚类生成k个簇中心，又将之前得到的每一份SIFT特征点集再分成更小的k个簇，如此循环不断将SIFT特征点层层细化直到L层。这样，就得到一个SIFT特征点的词汇树结构，其中，非叶子结点代表着簇中心，而叶子结点则代表着视觉词汇。由于采用层次性的SIFT特征点表达形式，可以设计近邻搜索来有效地查找到视觉词汇。
[0005] 在词汇树构建阶段，需要将每幅图像的SIFT特征点映射到词汇树的视觉词汇上以得到描述直方图，并采用文本搜索技术对得到的直方图进行视觉词汇独特性加权和归一化处理。由于在视觉词汇的学习阶段将视觉词汇组织成树结构，因此对每个SIFT特征点对应的视觉词汇进行查询时只需要在每一层进行k次比较，大大减少了映射时间。在将数据库图像集合的所有特征点映射到相应的视觉词汇之后，便得到了每一个图像的直方图描述形式。结合文本搜索技术，每个视觉词汇所代表的显著区分性是不同的，同时为了加快查询图像对数据库图像的相似性判别，采用倒排文档技术，结合词频-逆向文件频率(Term Frequncy-Inverse Document Frequency，TF-IDF)加权技术，对每一个视觉词汇更新其独特性表达，生成新的描述直方图。最后，再对每幅图像的描述直方图进行归一化处理，去除每幅图像由于特征点数不同所造成的影响。
[0006] 如图所示在词汇树查询阶段，同样需要先提取查询图像的SIFT特征点，然后将其与词汇树的视觉词汇进行映射处理，得到查询图像的描述直方图，再进行归一化处理。最后，将查询图像的描述直方图与所有数据库图像的描述直方图进行直方图交叉核计算，得到查询图像与每幅数据库图像的相似性评分。这样，根据评分结果就可以得到想要的相似性图像。
[0007] 由于在词汇树的构建阶段需要将所有数据库图像的SIFT特征点映射到相应的视觉词汇上，尽管原始的词汇树算法采用了层次性的树结构进行比较查询在效率上有了一定的提高，但是在面对目前普遍的大规模图像检索时，该阶段将仍然占用整个算法巨大的计算开销。
发明内容
[0008] 针对现有技术的以上缺陷或改进需求，本发明提供了一种基于GPU加速的大规模图像词汇树检索方法及系统，其目的在于针对GPU平台的结构特点，首先将原始视觉词汇的指针链表形式转化为线性链表结构，并将传统的SIFT特征点进行模块化组织，使得GPU能一次处理大批量数据，大大提高SIFT特征点映射的效率。并根据在GPU上得到的中间结果，在后续阶段利用GPU采取相应的视觉词汇独特性加权和归一化处理等得到最终的查询图像相似性评分，由此解决现有技术在面对大规模图像检索时，算法占用巨大的计算开销的技术问题。
[0009] 为实现上述目的，按照本发明的一个方面，提供了一种大规模图像词汇树检索方法，该方法包括以下步骤：
[0010] (1)输入待查询图像；
[0011] (2)利用图像中每个SIFT特征点在词汇树中最相似视觉词汇构建每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
[0012] (3)利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数，具体采用以下公式更新：
[0013] qi＝niωi，
[0014] 其中，qi表示一幅图像中第i个视觉词汇的新频数；ni代表一幅图像中第i个视觉词汇的原频数，ωi为相应视觉词汇的权重；最后采用L1范数对图像索引列表进行计算，得到每幅图像的描述符长度，并以此长度对每幅图像直方图进行归一化；
[0015] (4)利用待查询图像直方图和预先准备的数据库图像直方图，采用直方图交叉核计算所有数据库图像和待查询图像的相似性，对所有数据库图像的相似性进行排序，得到和待查询图像相似性最高的数据库图像；所述采用直方图交叉核计算所有数据库图像和待查询图像的相似性具体为采用以下公式：
[0016]
[0017] 其中，h1和h2分别表示待查询图像和数据库图像的描述直方图，I(h1,h2)表示相似性，h1(i)和h2(i)分别表示待查询图像直方图和数据库图像直方图第i个视觉词汇的最终频数。
[0018] 进一步地，所述步骤(4)中预先准备的数据库图像直方图具体采用以下步骤获得：
[0019] (21)批量输入数据库图像；
[0020] (22)利用图像中SIFT特征点在词汇树中找出最相似视觉词汇构建描述每幅图像的图像直方图，并对由GPU操作引起的稀疏图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
[0021] (23)在图像的特征描述点中，每一个视觉词汇所代表的权重是不同的，需要根据文本搜索技术中的TF-IDF技术对视觉词汇进行加权处理，根据视觉词汇索引列表的数据，采用以下公式计算每个视觉词汇在图像数据库中的权重：
[0022]
[0023] 其中，N代表所有图像数据库中图像总数目，Ni代表第i个视觉词汇下对应有多少幅数据库图像与其相关，ωi为第i个视觉词汇的权重，当Ni为0时，记ωi为0；
[0024] (24)为了去除每幅图像由于特征点数不同所造成的影响，利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数；采用L1范数对图像索引列表进行计算，得到每幅数据库图像的描述符长度，并以此长度对每幅数据库图像直方图进行归一化。
[0025] 进一步地，为符合GPU大规模并行计算的特点，所述词汇树的结构为地址连续的数组结构，采用广度优先搜索结合堆栈的方法将视觉词汇的树结构转换为地址连续的数组结构，用数组的一个元素表示词汇树的一个节点，以便可以在CPU和GPU之间进行视觉词汇的传输和后面GPU对其便捷地访问。
[0026] 进一步地，所述数组的元素包括SIFT特征描述符、结点ID、该节点的子节点数和其第一个子节点的地址偏移量属性。
[0027] 进一步地，所述视觉词汇索引列表以视觉词汇为关键字，索引包含该视觉词汇的图像ID和该视觉词汇在该图像中出现的频数；图像索引列表以图像ID为关键字，索引该图像包含的视觉词汇ID和该视觉词汇在该图像中出现的频数；
[0028] 进一步地，所述利用图像中SIFT特征点在词汇树中找出最相似视觉词汇构建描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表具体包括以下步骤：
[0029] (31)提取每幅图像的SIFT特征点，并剔除其中尺度小于设定阈值的SIFT特征点，此阈值优选1.4；
[0030] (32)传统的CPU词汇树算法一次性只能处理一个SIFT特征点的视觉词汇映射，如果将一幅图像的所有SIFT特征点同时在GPU上进行映射也往往不能充分利用GPU的大规模并行计算能力。因此，将图像的SIFT特征点用新的存储结构表示，存储结构包括SIFT特征描述符、所属图像ID和所属视觉词汇ID属性，自适应计算判断GPU所能处理的图像张数；
[0031] (33)按深度优先搜索的形式在GPU每个线程中对每幅图像的每个SIFT特征点进行查找，查找每个SIFT特征点在词汇树中和其最相似的视觉词汇，由每幅图像所有SIFT特征点对应的所有视觉词汇组成描述每幅图像的图像直方图；当查询SIFT特征到达第0层时，将查询SIFT特征的128位描述符根据其第一个子节点的偏移量同其下属的子结点的特征描述符依次比较，判断其属于第几个子节点，然后将查询特征转移到那个子节点上，继续比较判断其属于第几个子节点，直到最后一层得到描述每幅图像的图像直方图；
[0032] (34)利用CPU建立一个视觉词汇索引列表和图像索引列表，当一个视觉词汇在一个图像中的频数为零的时候则删除该索引；由上一步得到的图像直方图在实际中是非常稀疏的，因此需要在建立一个视觉词汇索引列表和图像索引列表的同时对图像直方图进行压缩，去除直方图中为零的bin。
[0033] 按照本发明的另一个方面，提供了一种基于GPU加速的大规模图像词汇树检索系统，该方法包括以下模块：
[0034] 查询图像输入模块，用于输入待查询图像；
[0035] 图像直方图构建模块，用于利用GPU多线程并行计算出图像中每个SIFT特征点在词汇树中最相似视觉词汇，由每幅图像的所有SIFT特征点对应的视觉词汇组成描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
[0036] 图像直方图归一化模块，用于利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数，具体采用以下公式更新：
[0037] qi＝niωi，
[0038] 其中，qi表示一幅图像中第i个视觉词汇的新频数；ni代表一幅图像中第i个视觉词汇的原频数，ωi为相应视觉词汇的权重；最后采用L1范数对图像索引列表进行计算，得到每幅图像的描述符长度，并以此长度对每幅图像直方图进行归一化；
[0039] 图像检索模块，用于利用待查询图像直方图和预先准备的数据库图像直方图，采用直方图交叉核计算所有数据库图像和待查询图像的相似性，对所有数据库图像的相似性进行排序，得到和待查询图像相似性最高的数据库图像；所述采用直方图交叉核计算所有数据库图像和待查询图像的相似性具体为采用以下公式：
[0040]
[0041] 其中，h1和h2分别表示待查询图像和数据库图像的描述直方图，I(h1,h2)表示相似性，h1(i)和h2(i)分别表示待查询图像直方图和数据库图像直方图第i个视觉词汇的最终频数。
[0042] 进一步地，所述数据库图像直方图具体包含以下模块：
[0043] 数据库图像输入模块，用于批量输入数据库图像；
[0044] 图像直方图构建模块，用于利用GPU多线程并行计算出图像中每个SIFT特征点在词汇树中最相似视觉词汇，由每幅图像的所有SIFT特征点对应的视觉词汇组成描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
[0045] 视觉词汇权重计算模块，用于根据视觉词汇索引列表的数据，采用以下公式计算每个视觉词汇在图像数据库中的权重：
[0046]
[0047] 其中，N代表图像数据库中所有图像总数目，Ni代表第i个视觉词汇下对应有多少幅数据库图像与其相关，ωi为第i个视觉词汇的权重，当Ni为0时，记ωi为0；
[0048] 数据库图像直方图归一化模块，用于利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数；最后采用L1范数对图像索引列表进行计算，得到每幅数据库图像的描述符长度，并以此长度对每幅数据库图像直方图进行归一化。
[0049] 进一步地，所述词汇树的结构为地址连续的数组结构，采用广度优先搜索结合堆栈的方法将视觉词汇的树结构转换为地址连续的数组结构，用数组的一个元素表示词汇树的一个节点；所述数组结构的一个元素包括SIFT特征描述符、结点ID、该节点的子节点数和其第一个子节点的地址偏移量属性。
[0050] 进一步地，所述视觉词汇索引列表以视觉词汇为关键字，索引包含该视觉词汇的图像ID和该视觉词汇在该图像中出现的频数；图像索引列表以图像ID为关键字，索引该图像包含的视觉词汇ID和该视觉词汇在该图像中出现的频数。
[0051] 进一步地，所述图像直方图构建模块具体包括以下单元：
[0052] 特征点提取单元，用于提取每幅图像的SIFT特征点，并剔除其中尺度小于设定阈值的SIFT特征点；
[0053] 特征点转换单元，用于将图像的SIFT特征点用新的存储结构表示，存储结构包括SIFT特征描述符、所属图像ID和所属视觉词汇ID属性；
[0054] 图像直方图构建单元，用于按深度优先搜索的形式在GPU每个线程中对每幅图像的每个SIFT特征点进行查找，查找每个SIFT特征点在词汇树中和其最相近的视觉词汇，由每幅图像的所有SIFT特征点对应的所有视觉词汇组成描述每幅图像的图像直方图；
[0055] 索引列表建立单元，用于建立一个视觉词汇索引列表和图像索引列表，当一个视觉词汇在一个图像中的频数为零的时候则删除该索引。
[0056] 总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下技术特征及有益效果：
[0057] (1)采用广度优先搜索结合堆栈的方法将视觉词汇的树结构转换为地址连续的数组结构，用数组的一个元素表示词汇树的一个节点，克服了传统的GPU与CPU不能进行非连续地址指针形式的数据结构传输的缺陷，以此能在GPU上实现利用线性连续偏移树结构进行快速查找映射的技术优势；
[0058] (2)将图像的SIFT特征点用新的存储结构表示，存储结构包括SIFT特征描述符、所属图像ID和所属视觉词汇ID属性，得到可以在GPU上一次性处理数十万个特征点进行大规模并发查找映射以此加速的技术优势；
[0059] (3)由直方图紧凑化处理与查找映射的并发执行技术方案，得到可以将直方图的紧凑化处理与交叉索引建立的时间隐藏在GPU上实现特征点查找映射的步骤之下以此提高总体加速性能的技术优势。
附图说明
[0060] 图1是现有技术中待查询的SIFT特征映射过程；
[0061] 图2是本发明技术方案的图像检测流程示意图；
[0062] 图3是本发明技术方案的对数据库图像的GPU操作流程示意图；
[0063] 图4是本发明技术方案的以视觉词汇属性为关键词的列表结构；
[0064] 图5是本发明技术方案的以图像汇属性为关键词的列表结构。
具体实施方式
[0065] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
[0066] 图2是本发明技术方案的图像检测流程示意图，如图2所示本发明技术实施例包含以下步骤：
[0067] (1)输入待查询图像；
[0068] (2)利用图像中SIFT特征点在词汇树中找出最相似视觉词汇构建描述每幅图像的图像直方图，并对图像直方图进行紧凑化处理，同时建立图像索引列表和视觉词汇索引列表；
[0069] (3)利用视觉词汇在图像数据库中的权重更新视觉词汇索引列表和图像索引列表中视觉词汇出现的频数；最后采用L1范数对图像索引列表进行计算，得到每幅图像的描述符长度，并以此长度对每幅图像直方图进行归一化；
[0070] (4)利用待查询图像直方图和预先准备的数据库图像直方图，与传统的计算矢量相似性不同，这里采用直方图交叉核来评判两幅图像描述直方图的相似性，直方图交叉核的定义如下：
[0071]
[0072] 其中，h1和h2分别表示待查询图像和数据库图像的描述直方图，I(h1,h2)表示相似性，h1(i)和h2(i)分别表示待查询图像直方图和数据库图像直方图第i个视觉词汇的最终频数；
[0073] 对数据库所有图像得到的相似性进行排序，得到和待查询图像相似性最高的数据库图像。
[0074] 其中，为符合GPU大规模并行计算的特点，对原始词汇树算法得到的视觉词汇的树结构采用广度优先搜索结合堆栈的方式将其转换为地址连续的新的结构体数组形式。该数组结构的定义为：SIFT特征描述符、结点ID、该节点的孩子数和其第一个孩子结点的地址偏移量。因此在做广度优先搜索时对每个结点都要记录以上信息。这样，再将原先视觉词汇的指针形式转换为线性连续的地址偏移结构，可以方便地将视觉词汇信息传送到GPU设备上，也利于后面GPU对其进行便捷访问。在本发明的一个实施实例中，将原先深度为6，分支因子为10的具有106个视觉词汇的树的1,111,111个节点信息统一组织成具有一定连接关系的数组形式。
[0075] 如图3所示，预先准备数据库图像直方图包括以下步骤：
[0076] (21)输入数据库图像；
[0077] (22)对数据库中每幅图像提取SIFT特征点，原始的每个SIFT特征点包含位置信息、方向信息与尺度信息，由于在构建视觉词汇时需要的是具有显著代表性的视觉词汇，因此将尺度小于一定阈值的SIFT特征点剔除得到每一幅图像的临时表征，这里优选阈值K＝1.4；
[0078] 传统的CPU词汇树算法一次性只能处理一个SIFT特征点的视觉词汇映射，如果将一幅图像的所有特征点同时在GPU上进行映射也往往不能充分利用GPU的大规模并行计算能力。因此，本发明根据GPU显存自适应地读取若干幅图像的SIFT特征点，以使GPU的利用率尽可能达到最大，并设计一种新的SIFT特征点存储结构使其具有SIFT特征描述符、所属图像ID和所属视觉词汇ID等属性。这样就能一次性将数十万个SFIT特征点同时送到GPU设备上进行后续计算处理又不至于使每个SIFT特征点的私有属性产生混淆；
[0079] 这里在GPU上开辟一个永久的直方图临时存储区，便于每次对40幅图像的SIFT特征点进行查找映射时记录每幅图像中每个视觉词汇出现的频数。由于在词汇树中记录了每个结点的孩子数和第一个孩子结点在线性表中的地址偏移，因此可以有效地在GPU上按深度优先搜索的形式在每个线程中对待查询SIFT特征点进行查找映射。而且得益于词汇树的结点表达方式，同时也保持了原来视觉词汇树的深度和分支因子信息，所以每个待查询的SIFT特征点只要进行60次的比较就可以搜索到相应的视觉词汇。这样便得到相应的每幅图像的描述直方图；
[0080] 这一步中得到的图像直方图在实际中是非常稀疏的，也就是说在代表106个视觉词汇的直方图中仅有几千个bin会有相应的频数值，这无论是对后续的处理效率还是CPU与GPU的存储空间而言都是相当不利的，因此将数据返回CPU对每幅图像的直方图进行高效的压缩处理。在紧凑化的过程中同时对图像与视觉词汇建立交叉索引，这里将同时创建以视觉词汇属性为关键字和以图像属性为关键字的两个公共记录列表视觉词汇索引列表与图像索引列表，在每次判别出图像直方图的一个bin的频数值不为0时，在视觉词汇索引列表与图像索引列表分别作出记录。视觉词汇索引列表与图像索引列表的列表结构如图4和图5所示；
[0081] (23)在图像的特征描述点中，每一个视觉词汇所代表的权重是不同的，根据文本搜索技术对视觉词汇进行加权处理，即根据上一步骤中所得的视觉词汇索引列表结果，采用下式计算每个视觉词汇的相应权重：
[0082]
[0083] 其中，N代表所有数据库图像总的图像数目，Ni代表第i个视觉词汇下对应有多少幅数据库图像与其相关，当Ni为0时，记ωi为0；
[0084] (24)在得到每个视觉词汇相应的独特性权重后，对视觉词汇索引列表与图像索引列表中的对应频数进行相应的更新，更新公式为：
[0085] qi＝niωi
[0086] 其中，qi表示一幅图像中第i个视觉词汇的新频数；ni代表一幅图像中第i个视觉词汇的原频数，ωi为相应视觉词汇的权重；
[0087] 同时为了去除每幅图像由于特征点个数的不同所造成的影响，需要对每幅图像的直方图进行归一化修正，采用L1范数对图像索引列表计算每幅图像的描述符长度以此对每幅图像的频数进行归一化。由于视觉词汇索引列表与图像索引列表保存了视觉词汇和图像的完备信息，因此同样可以将每幅图像的频数更新和归一化放到GPU上进行计算，来得到一定提速。至此，利用大规模的数据库图像完成对视觉词汇树的GPU加速构建阶段。
[0088] 这里应用本发明算法在大规模三维场景的重建上进行测试。大规模三维场景重建由于原始的输入图像有成千上万张，然而并不是两两图像之间都有相应的匹配对应关系，因此往往先采用词汇树算法来粗略快速地挑选出含有潜在匹配关系的图像对。传统的词汇树算法尽管对整个大规模三维重建的效率有一定的提升，但是其本身的词汇树构建阶段的查找映射时间瓶颈也是显然的，采用本发明算法可以使词汇树算法的查找映射阶段提速达到30倍左右，整体效果(由GPU加速导致的整体时间效应)也达到了20倍左右，提升了整个大规模场景重建的时间效率。表1与表2分别展示了三维重建两个数据集应用传统的词汇树算法与GPU加速的词汇树算法的时间性能对比。其中，所有的CPU时间都是采用单核C++执行得到的，GPU时间是在NVIDIA GTX TITAN X上采用CUDA C执行得到的。
[0089] 表1 CPU与GPU程序时间性能比较(2360幅图像)
[0090]
[0091] 表2 CPU与GPU时间性能比较(6280幅图像)
[0092]
[0093] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。
