[發明專利]一種基于耦合鑒別性字典的跨媒體哈希索引方法

有效

• 申請號: 201410532084.3
• 申請日: 2014-10-10
• 公開（公告）號: CN104317838A
• 公開（公告）日: 2015-01-28
• 發明（設計）人: 湯斯亮;邵健;余宙;吳飛;莊越挺
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 張法高

技術領域

本發明涉及跨媒體檢索，尤其涉及一種基于海量數據的跨媒體高效索引方法。

背景技術

隨著互聯網技術的高速發展和社交網絡的風靡，互聯網上的多媒體數據的數量正在以驚人的速度增長。多媒體數據具有如下幾個特性1)由于多媒體數據具有復雜的語義，因此難以直接進行度量。為了實現多媒體數據的度量，一般是先對其媒體數據所具有的特征進行提取，然后將特征之間的相似度作為媒體數據之間的相似度。一般的，這些所提取的特征往往是高維的，因此，多媒體數據的檢索問題就轉變為了高維數據的檢索問題。2)多媒體數據量十分龐大，傳統的暴力線性搜索策略在處理大規模數據時候會產生極高時間復雜度，無法滿足用戶在線搜索需求。為了克服這一困難，現在主流海量高維數據檢索方法一般采用哈希索引策略，也就是說，其用近似最近鄰檢索來代替傳統精確最近鄰檢索。在哈希索引中，給定海量高維媒體數據，可通過哈希函數將每個媒體數據映射為簡短哈希編碼，于是可在哈希編碼空間實現高維數據近似搜索。由于哈希編碼的相似性計算非常高效，因此哈希索引在實現海量數據近似查詢時能取得很高查詢性能。3)多媒體數據中廣泛存在多種媒體數據共生關系。舉例來說，一張網絡圖像除了有圖片本身外，還有一些描述信息(如標題、用戶的標注信息、評論信息等)；一則新聞報道除了有文字的描述，通常還有與之相關的新聞圖片。如何合理地利用同一模態內數據的相似性以及不同模態間數據的已知關聯關系，在不同類型媒體數據之間建立“橋梁”，使得不同模態的數據可以在統一的度量空間進行相似性比較是一個非常重要的問題。

結合以上幾個特性，為了達到海量多模態的多媒體數據高效跨媒體檢索這一目的，一些跨媒體哈希索引算法被相繼提出。已有的跨媒體哈希算法大多基于流形學習框架。這些方法在學習哈希函數中會保留每個模態數據流形結構，同時將不同模態數據映射到同一個子空間內，并將不同模態數據進行流形對齊。近年來，人們發現字典學習的方法可以很好地用學習得到的字典對數據進行有效地表達，并在這種有效表達基礎上來實現跨媒體哈希索引。本發明提出的方法在其基礎上更進一步，提出了鑒別性耦合字典這一概念，其將不同模態數據映射到一個語義明確的字典空間內，并在耦合字典的基礎上學習哈希函數，建立跨媒體數據的哈希索引。

發明內容

本發明的目的是克服現有技術的不足，提供一種跨媒體稀疏哈希索引的方法。

基于耦合鑒別性字典的跨媒體哈希索引方法包括如下步驟：

1)基于圖結構對多個模態數據之間的關聯關系進行建模；通過數據底層特征之間的歐氏距離確定同一模態內部的相似性，利用不同模態數據已知關聯關系確定模態間的關聯，利用數據所具有類別標簽信息增強圖結構上數據的鑒別性；

2)在步驟1)中得到的圖結構上數據的關聯關系學習鑒別性的耦合字典；

3)利用步驟2)中學習得到的耦合字典對不同模態的數據進行稀疏編碼，并映射到統一的字典空間內；

4)學習從字典空間到二值海明空間的哈希映射函數。

步驟2)包括：

將步驟1)得到的圖結構形式化表達為G(V，E，w，C)；其中v為圖結構中的頂點集合，代表不同模態所對應的數據對象，E是圖結構中邊的集合，代表了每個頂點之間的關聯關系，w為邊的權重集合，C為每個頂點對應的標簽信息的集合；

得到圖結構G(V，E，w，C)后，基于圖分割方法，給出了鑒別性耦合字典學習問題的解決方法：從邊的集合E中選擇合適的子集A，將圖G分割成K個子圖，將每個子圖中所包含數據對象的質心選擇出來，形成一組耦合字典，假設總共有M個模態數據，就得到了M個耦合字典D¹，D²，...，D^M，每個字典中所包含的字典項個數都為K；

為了得到合適的子集A，設計了具有亞模性質的三個函數，這三個亞模函數分別具有如下壓縮性、鑒別性和平衡性；

壓縮函數：基于隨機游走模型中的“熵率”，設計了壓縮函數，該函數使得每個子圖中的媒體對象之間距離盡可能近，從而使得每個子圖都具有“緊湊”特性，即

H(A)＝-Σ_iμ_iΣ_jP_i，j(A)logP_i，j(A)????(7)其中μ_i為頂點i穩態分布的概率，P_i，j(A)為頂點i到j的傳遞概率函數，定義如下：