[發明專利]用于圖像特征庫的HNSW節點刪除方法、系統、設備和介質

有效

• 申請號: 202010925664.4
• 申請日: 2020-09-07
• 公開（公告）號: CN111813988B
• 公開（公告）日: 2021-03-12
• 發明（設計）人: 周曦;姚志強;陳輝
• 申請（專利權）人: 上海云從企業發展有限公司
• 主分類號: G06F16/583
• 分類號: G06F16/583;G06F16/23;G06K9/00
• 代理公司: 上海光華專利事務所(普通合伙) 31219
• 代理人: 代玲

本發明提出用于圖像特征庫的HNSW節點刪除方法、系統、設備和介質，包括：獲取來自圖像特征庫的HNSW圖中待刪除節點及其所處層級；根據所述HNSW圖中各節點對應的層級關系，找出與所述待刪除節點相關聯的節點；建立所述相關聯的節點之間的連接關系；刪除所述待刪除節點以及與所述待刪除節點相關的連接關系，生成新的所述HNSW圖，以更新所述圖像特征庫；本發明不影響圖的整體結構，多次刪除也不會降低圖的查找速度和準確度，刪除節點接口簡單，靈活，能夠做到實時更新，提高用戶體驗。

技術領域

本發明涉及圖像處理領域，尤其涉及用于圖像特征庫的HNSW節點刪除方法、系統、設備和介質。

背景技術

在人臉識別領域中，最近鄰查找算法應用十分廣泛，且隨著技術的不斷發展和市場環境的不斷變化，產品對于查找算法的速度和準確度要求也越來越高。

目前，行業公認的在最近鄰查找算法中，效果最好的是基于圖的查找算法。而在人臉特征比對這種對于準確度要求較高、千萬級別數據量的向量對比領域，表現最好的是HNSW（Hierarchical Navigable Small World，分層可導航小世界）這種基于圖的近鄰查找法。

HNSW算法在千萬級別的向量查找中具有得天獨厚的優勢，不僅準確率處于頂尖水平，同時時間復雜度也僅為對數復雜度。所以在人臉特征比對領域運用廣泛。

眾所周知，在人臉識別實際運用中，識別的底庫需要經常更新，但是由于HNSW的論文中沒有給出刪除節點的方法，導致每次只能通過重新建庫的方式來更新信息，這就導致了極大的時間和算力的浪費，無法實現節點實時更新?，F有技術中，刪除HNSW節點通常有兩種方式，其一，建立黑名單，將刪除節點信息記入黑名單中，這種方式并沒有實際刪除節點，當黑名單數量超過一定閾值時，會嚴重影響查找效率，只能重建新圖；其二，將要刪除的節點，復制一個和它最相似的節點替代它。此方法也不影響圖的完整性，但是如果未來需要刪除剛剛復制的那個節點，就會很復雜，因為已經不知道這個節點有多少份，分布在圖的哪些地方，重復刪除會有問題，如果復制的時候，將那個節點進行很小的偏移也會出現新的問題，這將導致未來圖有可能輸出這個已經偏移的節點，而這個節點信息其實不在我們的底庫中，這可能會導致接口使用者不知所措。

發明內容

鑒于以上現有技術存在的問題，本發明提出一種，主要解決傳統HNSW節點刪除操作復雜且難以進行實時更新的問題。

為了實現上述目的及其他目的，本發明采用的技術方案如下。

用于圖像特征庫的HNSW節點刪除方法，包括：

獲取來自圖像特征庫的HNSW圖中待刪除節點及其所處層級；

根據所述HNSW圖中各節點對應的層級關系，找出與所述待刪除節點相關聯的節點；

建立所述相關聯的節點之間的連接關系；

刪除所述待刪除節點以及與所述待刪除節點相關的連接關系，生成新的所述HNSW圖，以更新所述圖像特征庫。

可選地，所述相關聯的節點包括：與所述待刪除節點最相似的節點、在所述HNSW圖中與所述待刪除節點連接的節點。

可選地，還包括：若與所述待刪除節點及所述最相似節點連接的節點數之和大于預設數量，則刪除多余的節點，使剩下的節點數量與所述預設數量保持相同。

可選地，建立所述相關聯的節點之間的連接關系包括：所述最相似的節點與所述剩下的節點之間的雙向連接關系。

可選地，根據距所述最相似的節點遠近的規則選取所述剩下的節點。

可選地，設置時間閾值，當節點未被訪問的時間間隔超出所述時間閾值時，將對應的節點作為所述待刪除節點；和/或，設置頻率閾值，當節點被訪問頻率低于所述頻率閾值時，將對應的節點作為所述待刪除節點。