[發明專利]一種動態k近鄰圖的構建方法及基于動態k近鄰圖的快速圖像檢索方法

在審

• 申請號: 202011271641.2
• 申請日: 2020-11-13
• 公開（公告）號: CN112507149A
• 公開（公告）日: 2021-03-16
• 發明（設計）人: 趙萬磊;王輝;雷蘊奇
• 申請（專利權）人: 廈門大學
• 主分類號: G06F16/51
• 分類號: G06F16/51;G06F16/583
• 代理公司: 廈門市新華專利商標代理有限公司 35203
• 代理人: 羅恒蘭

1.一種動態k近鄰圖的構建方法，其特征在于：包括以下步驟：

步驟1、當圖像數據集中新加入圖像時，對新加入的圖像進行特征提取，得到特征向量q，將該特征向量q加入到圖像特征集S中；該圖像特征集S是在d維空間的一個向量集合，其中的向量由圖像數據集中的圖像以特征提取方法得到；

步驟2、當圖像特征集S中的特征向量數小于M時，采用窮舉比較的方式計算特征向量q和圖像特征集S中的所有向量之間的距離，以計算的距離更新k近鄰圖G；

步驟3、當圖像特征集S中的特征向量數不小于M時，按照如下方式對k近鄰圖G進行更新：

步驟3.1、 在k近鄰圖G中隨機選取多個頂點作為起點，將這些頂點加入優先隊列C中，優先隊列C中距離特征向量q越近的頂點優先級越高；

步驟3.2、取出優先隊列C的隊首元素c，遍歷該頂點c在k近鄰圖G中的鄰居頂點，將這些鄰居頂點中之前未被訪問過的頂點加入C中，并更新q的k近鄰表；

步驟3.3、重復步驟3.2，直到C為空或者q的k近鄰表不能再被更新；

步驟3.4、利用步驟3.2和3.3中訪問到的所有頂點與q的距離信息更新k近鄰圖G；

步驟4、輸出k近鄰圖。

2.根據權利要求1所述的一種動態k近鄰圖的構建方法，其特征在于：所述步驟3.4為：采用受限遞歸近鄰傳播策略優化k近鄰圖，即對步驟3.3中訪問到的所有頂點向外進行寬度優先搜索，搜索只擴展給定層數內的頂點，并要求這些頂點在q的k近鄰范圍內，利用搜索過程中計算的距離信息更新k近鄰圖G。

3.一種基于動態k近鄰圖的快速圖像檢索方法，其特征在于：包括以下步驟：

步驟1、輸入待查詢的圖像特征向量q，構建特征向量q的k近鄰圖作為圖像檢索的索引；

步驟1.1、當圖像特征集S中的特征向量數小于M時，采用窮舉比較的方式計算特征向量q和圖像特征集S中的所有向量之間的距離，以計算的距離更新k近鄰圖G；

步驟1.2、當圖像特征集S中的特征向量數不小于M時，按照如下方式對k近鄰圖G進行更新：

步驟1.21、在k近鄰圖G中隨機選取多個頂點作為起點，將這些頂點加入優先隊列C中，優先隊列C中距離特征向量q越近的頂點優先級越高，然后更新特征向量q的k近鄰表，即距離q最近的k個頂點；

步驟1.22、取出優先隊列C的隊首元素c，遍歷該頂點c在k近鄰圖G中的鄰居頂點，將這些鄰居頂點中之前未被訪問過的頂點加入C中，并更新q的k近鄰表；

步驟1.23、重復步驟1.22，直到C為空或者q的k近鄰表不能再被更新；

步驟1.24、利用步驟1.23中訪問到的所有頂點與q的距離信息更新k近鄰圖G；

步驟2、采用延遲圖散化策略提升基于k近鄰圖G的向量檢索性能，即利用步驟1中計算的距離信息更新k近鄰表中頂點的遮擋值，并將這些頂點中遮擋值超過其所在k近鄰表平均遮擋值的頂點標記為不可訪問的，并更新k近鄰圖G；其中，對于頂點r的k近鄰頂點a和b，若r到b的距離大于r到a的距離，且a到b的距離小于r到b的距離，則稱在r的近鄰中b被a遮擋，b在r的k近鄰表中的遮擋值加一；

步驟3、根據步驟2更新的k近鄰圖進行檢索；

步驟3.1、在k近鄰圖G中隨機選取多個頂點作為起點，將這些頂點加入優先隊列C中，優先隊列C中距離q越近的頂點優先級越高；

步驟3.2、取出優先隊列C隊首元素c，遍歷其在近似k近鄰圖G中的鄰居頂點，忽略被標記為“不可訪問”的頂點，將其余未訪問過的鄰居頂點加入隊列C中，并更新q的k近鄰表；

步驟3.3、重復步驟3.2，直到隊列C為空或者q的k近鄰表不能再被更新；

步驟3.4、返回q的k近鄰表，即返回檢索到的與q最相似的k個圖像特征向量的編號，其對應的圖像即為所需檢索的結果。

4.根據權利要求3所述的一種基于動態k近鄰圖的快速圖像檢索方法，其特征在于：所述步驟1.24為：采用受限遞歸近鄰傳播策略優化k近鄰圖，即對步驟1.23中訪問到的所有頂點向外進行寬度優先搜索，搜索只擴展給定層數內的頂點，并要求這些頂點在q的k近鄰范圍內，利用搜索過程中計算的距離信息更新K近鄰圖G。