[發明專利]跨媒體稀疏哈希索引方法

有效

• 申請號: 201310410588.3
• 申請日: 2013-09-10
• 公開（公告）號: CN103473307A
• 公開（公告）日: 2013-12-25
• 發明（設計）人: 吳飛;張寅;余宙;邵健;莊越挺
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 張法高

1.一種跨媒體稀疏哈希索引方法，其特征在于包括如下步驟：

1)對多個模態數據之間的關聯關系利用超圖進行統一建模；模態內的相似性使用數據的底層特征的歐氏距離，模態間的關聯利用不同模態數據已知的關聯關系；

2)將統一超圖約束引入多模態字典學習的框架內，使得學習得到的多模態字典能保留模態內的相似性以及模態間的關聯關系；

3)將學習得到的字典作為哈希函數，對新的數據利用對應模態的字典進行稀疏編碼；

4)將稀疏編碼通過哈希策略轉化為稀疏編碼集，并使用類jaccard距離來計算集合之間的相似度。

2.根據權利要求1所述的一種跨媒體稀疏哈希索引方法，其特征在于所述的步驟2)包括：

給出如下基于最小重建誤差的目標函數，以實現多模態字典學習：

minA,Dx,Dy||X-DxAx||F2+||Y-DyAy||F2+Ω(A)s.t.||dkx||F2≤1,||dky||F2≤1,∀k=1,2,...K---(1)]]>

其中X=[x1,x2,...,xNx]∈Rpx×Nx,Y=[y1,y2,...,yNy]∈Rpy×Ny]]>是兩個模態的數據，p_x，p_y為相應模態的數據的維度，N_x，N_y為數據的個數；Dx=[d1x,d1x,...dKx]∈Rpx×K,Dy=[d1y,d1y,...dky]∈Rpy×K]]>是數據集X和Y對應的字典；為；K為組成字典的元素的個數，組成D^x和D^y的元素個數相同使得不同模態的數據被映射到統一的字典空間里；是數據集X和Y中每個數據用對應的字典重建的稀疏系數；

此外，是來自不同模態數據對應的重建系數集合，并在目標函數中添加了額外的正則約束項Ω(A)，來實現兩個目標：1)重建系數盡可能稀疏，以防止目標函數的“過擬合”，也能起到數據壓縮的作用，2)重建系數保持了在超圖中的不同模態數據之間關聯關系，使得學到的字典具有好的魯棒性；綜合如上兩個目標，給出如下的正則項Ω(A)：

Ω(A)=λ||A||1+α2Σe∈EΣ{vi,vj}⊆eω(e)δ(e)||ai-aj||2=λ||A||1+αTr(ALhAT)---(2)]]>

Ω(A)由兩項組成，分別對應了之前定義的兩個目標：稀疏和超圖關聯關系保持。

其中L_h為超圖拉普拉斯矩陣，具體的定義如下：

Lh=I-Dv-1/2HWDe-1HTDv-1/2---(3).]]>

其中I是單位矩陣，H是關聯矩陣，D_v，D_e為超圖的頂點和超邊的度的構建的對角矩陣，W為超邊的權重構建的對角矩陣。

3.根據權利要求1所述的一種跨媒體稀疏哈希索引方法，其特征在于所述的步驟4)包括：

假設數據x的用其模態學習得到的字典D^x進行稀疏編碼后得到再將稀疏編碼通過哈希方法生成稀疏編碼集：

SC+(ax)={i|∀i∈1,2,...,K,ifaix>σ}SC-(ax)={i|∀i∈1,2,...,K,ifaix<-σ}---(4)]]>

其中σ為設定的閾值，SC₊(·)和SC_{_}(·)對應兩個量化函數，生成稀疏編碼a^x的系數為正值和負值對應的下標集合；

此外，針對多個稀疏編碼集，采用類似于jaccard相似度的度量機制來衡量它們之間的相似性，具體的相似度計算公式如下：

Sim(ax,ay)=12(|SC+(ax)∩SC+(ay)||SC+(ax)∪SC+(ay)|+|SC-(ax)∩SC-(ay)||SC-(ax)∪SC-(ay)|)---(5)]]>

在實現高效地基于稀疏編碼集的檢索時，有兩種可選的方法：

●當K不大時，使用K維的二值向量來表達稀疏編碼集，將稀疏編碼集合的“交”和“并”的操作就轉變為硬件實現的高效AND和OR位運算；

當K較大時，所有稀疏編碼集對應K維的二值向量可能無法一次性加載到內存中來進行計算，使用另一種方法：使用min-Hash作為稀疏編碼集的哈希函數，然后建立LSH索引，從而支持高效的檢索。