[發明專利]一種基于GPU加速的大規模圖像詞匯樹檢索方法及系統

有效

• 申請號: 201710068307.9
• 申請日: 2017-02-08
• 公開（公告）號: CN106919658B
• 公開（公告）日: 2019-09-27
• 發明（設計）人: 陶文兵;徐青山;孫琨;李杰
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F16/583
• 分類號: G06F16/583;G06K9/46
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 李智

本發明公開了一種大規模圖像詞匯樹檢索方法，屬于計算機視覺領域。本發明算法針對GPU平臺的結構特點，采用了一種新穎的詞匯樹數據結構，并將傳統的SIFT特征點進行模塊化組織，使得其能充分利用GPU大規模并行計算的能力，大大提高大規模圖像SIFT特征點映射的效率。在將批量的SIFT特征點映射成直方圖之后，再采用快速的緊湊化方法對原始的倒排索引方案進行增強改進，使得其后的視覺詞匯獨特性表達、直方圖歸一化與查詢圖像的評分都得到了一定的提速。本發明還實現了基于GPU加速的大規模圖像詞匯樹檢索系統，不僅對圖像檢索本身有重大的加速意義，也對大規模場景的三維重建算法的效率提高有著巨大的影響。

技術領域

本發明屬于計算機視覺領域，更具體地，涉及一種基于GPU加速的大規模圖像詞匯樹檢索方法及系統。

背景技術

David Nistér等人提出的詞匯樹算法由于其使用樹的結構來對視覺詞匯進行量化，并將視覺詞匯的量化和索引集成為一體，再結合文本搜索技術來加快圖像描述符的相似性判斷，使其具有較高的準確率和效率，在目標識別、場景識別和三維重建等場合有著十分廣泛的應用。

原始的詞匯樹算法主要包含視覺詞匯的學習、詞匯樹構建及詞匯樹查詢三個階段。

在視覺詞匯學習階段，采用層次性k-means聚類來生成結構化的視覺詞匯。首先需要提取數據庫圖像中每幅圖像的尺度不變特征變換(Scale-Invariant FeatureTransform，SIFT)特征點來對圖像進行描述表達。由于所提取的數據庫圖像的特征點集合有著非常大的信息冗余，每個SIFT特征點對于描述一幅圖像有著不同的重要性，因此需要采用聚類算法來提取有用的信息，也就是圖像的視覺詞匯。不同于一般的聚類算法，詞匯樹算法采用層次性的k-means聚類算法。也就是，首先對所有的SIFT特征點采用k-means算法生成k個簇中心，將這些SIFT特征點分成k個簇，然后再對每一份SIFT特征點集使用k-means聚類生成k個簇中心，又將之前得到的每一份SIFT特征點集再分成更小的k個簇，如此循環不斷將SIFT特征點層層細化直到L層。這樣，就得到一個SIFT特征點的詞匯樹結構，其中，非葉子結點代表著簇中心，而葉子結點則代表著視覺詞匯。由于采用層次性的SIFT特征點表達形式，可以設計近鄰搜索來有效地查找到視覺詞匯。

在詞匯樹構建階段，需要將每幅圖像的SIFT特征點映射到詞匯樹的視覺詞匯上以得到描述直方圖，并采用文本搜索技術對得到的直方圖進行視覺詞匯獨特性加權和歸一化處理。由于在視覺詞匯的學習階段將視覺詞匯組織成樹結構，因此對每個SIFT特征點對應的視覺詞匯進行查詢時只需要在每一層進行k次比較，大大減少了映射時間。在將數據庫圖像集合的所有特征點映射到相應的視覺詞匯之后，便得到了每一個圖像的直方圖描述形式。結合文本搜索技術，每個視覺詞匯所代表的顯著區分性是不同的，同時為了加快查詢圖像對數據庫圖像的相似性判別，采用倒排文檔技術，結合詞頻-逆向文件頻率(TermFrequncy-Inverse Document Frequency，TF-IDF)加權技術，對每一個視覺詞匯更新其獨特性表達，生成新的描述直方圖。最后，再對每幅圖像的描述直方圖進行歸一化處理，去除每幅圖像由于特征點數不同所造成的影響。

如圖所示在詞匯樹查詢階段，同樣需要先提取查詢圖像的SIFT特征點，然后將其與詞匯樹的視覺詞匯進行映射處理，得到查詢圖像的描述直方圖，再進行歸一化處理。最后，將查詢圖像的描述直方圖與所有數據庫圖像的描述直方圖進行直方圖交叉核計算，得到查詢圖像與每幅數據庫圖像的相似性評分。這樣，根據評分結果就可以得到想要的相似性圖像。

由于在詞匯樹的構建階段需要將所有數據庫圖像的SIFT特征點映射到相應的視覺詞匯上，盡管原始的詞匯樹算法采用了層次性的樹結構進行比較查詢在效率上有了一定的提高，但是在面對目前普遍的大規模圖像檢索時，該階段將仍然占用整個算法巨大的計算開銷。

發明內容