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

有效

• 申請(qǐng)?zhí)枺?/td>: 201410532084.3
• 申請(qǐng)日: 2014-10-10
• 公開（公告）號(hào): CN104317838A
• 公開（公告）日: 2015-01-28
• 發(fā)明（設(shè)計(jì)）人: 湯斯亮;邵健;余宙;吳飛;莊越挺
• 申請(qǐng)（專利權(quán)）人: 浙江大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 張法高

技術(shù)領(lǐng)域

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

背景技術(shù)

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

結(jié)合以上幾個(gè)特性，為了達(dá)到海量多模態(tài)的多媒體數(shù)據(jù)高效跨媒體檢索這一目的，一些跨媒體哈希索引算法被相繼提出。已有的跨媒體哈希算法大多基于流形學(xué)習(xí)框架。這些方法在學(xué)習(xí)哈希函數(shù)中會(huì)保留每個(gè)模態(tài)數(shù)據(jù)流形結(jié)構(gòu)，同時(shí)將不同模態(tài)數(shù)據(jù)映射到同一個(gè)子空間內(nèi)，并將不同模態(tài)數(shù)據(jù)進(jìn)行流形對(duì)齊。近年來(lái)，人們發(fā)現(xiàn)字典學(xué)習(xí)的方法可以很好地用學(xué)習(xí)得到的字典對(duì)數(shù)據(jù)進(jìn)行有效地表達(dá)，并在這種有效表達(dá)基礎(chǔ)上來(lái)實(shí)現(xiàn)跨媒體哈希索引。本發(fā)明提出的方法在其基礎(chǔ)上更進(jìn)一步，提出了鑒別性耦合字典這一概念，其將不同模態(tài)數(shù)據(jù)映射到一個(gè)語(yǔ)義明確的字典空間內(nèi)，并在耦合字典的基礎(chǔ)上學(xué)習(xí)哈希函數(shù)，建立跨媒體數(shù)據(jù)的哈希索引。

發(fā)明內(nèi)容

本發(fā)明的目的是克服現(xiàn)有技術(shù)的不足，提供一種跨媒體稀疏哈希索引的方法。

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

1)基于圖結(jié)構(gòu)對(duì)多個(gè)模態(tài)數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系進(jìn)行建模；通過(guò)數(shù)據(jù)底層特征之間的歐氏距離確定同一模態(tài)內(nèi)部的相似性，利用不同模態(tài)數(shù)據(jù)已知關(guān)聯(lián)關(guān)系確定模態(tài)間的關(guān)聯(lián)，利用數(shù)據(jù)所具有類別標(biāo)簽信息增強(qiáng)圖結(jié)構(gòu)上數(shù)據(jù)的鑒別性；

2)在步驟1)中得到的圖結(jié)構(gòu)上數(shù)據(jù)的關(guān)聯(lián)關(guān)系學(xué)習(xí)鑒別性的耦合字典；

3)利用步驟2)中學(xué)習(xí)得到的耦合字典對(duì)不同模態(tài)的數(shù)據(jù)進(jìn)行稀疏編碼，并映射到統(tǒng)一的字典空間內(nèi)；

4)學(xué)習(xí)從字典空間到二值海明空間的哈希映射函數(shù)。

步驟2)包括：

將步驟1)得到的圖結(jié)構(gòu)形式化表達(dá)為G(V，E，w，C)；其中v為圖結(jié)構(gòu)中的頂點(diǎn)集合，代表不同模態(tài)所對(duì)應(yīng)的數(shù)據(jù)對(duì)象，E是圖結(jié)構(gòu)中邊的集合，代表了每個(gè)頂點(diǎn)之間的關(guān)聯(lián)關(guān)系，w為邊的權(quán)重集合，C為每個(gè)頂點(diǎn)對(duì)應(yīng)的標(biāo)簽信息的集合；

得到圖結(jié)構(gòu)G(V，E，w，C)后，基于圖分割方法，給出了鑒別性耦合字典學(xué)習(xí)問(wèn)題的解決方法：從邊的集合E中選擇合適的子集A，將圖G分割成K個(gè)子圖，將每個(gè)子圖中所包含數(shù)據(jù)對(duì)象的質(zhì)心選擇出來(lái)，形成一組耦合字典，假設(shè)總共有M個(gè)模態(tài)數(shù)據(jù)，就得到了M個(gè)耦合字典D¹，D²，...，D^M，每個(gè)字典中所包含的字典項(xiàng)個(gè)數(shù)都為K；

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

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

H(A)＝-Σ_iμ_iΣ_jP_i，j(A)logP_i，j(A)????(7)其中μ_i為頂點(diǎn)i穩(wěn)態(tài)分布的概率，P_i，j(A)為頂點(diǎn)i到j(luò)的傳遞概率函數(shù)，定義如下：