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

有效

• 申請(qǐng)?zhí)枺?/td>: 201310410588.3
• 申請(qǐng)日: 2013-09-10
• 公開（公告）號(hào): CN103473307A
• 公開（公告）日: 2013-12-25
• 發(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)靡，網(wǎng)絡(luò)上的多媒體數(shù)據(jù)的數(shù)量正在以驚人的速度增長。多媒體數(shù)據(jù)具有復(fù)雜的語義，難以直接進(jìn)行度量，一般的做法是對(duì)其進(jìn)行特征抽取得到相應(yīng)的特征。通常這些特征都是高維的，因此，多媒體數(shù)據(jù)的檢索問題就轉(zhuǎn)變?yōu)榱烁呔S數(shù)據(jù)的檢索問題。傳統(tǒng)的暴力的線性比較的策略在面對(duì)大規(guī)模高維數(shù)據(jù)的時(shí)候的時(shí)間復(fù)雜度顯然不能滿足用戶的在線搜索需求。此時(shí)，人們需要一種有效的索引機(jī)制以實(shí)現(xiàn)高維數(shù)據(jù)地高效檢索。哈希方法是近些年來的高維索引的熱點(diǎn)研究方向。它的核心的思想就是用近似最近鄰代替?zhèn)鹘y(tǒng)的最近鄰的來實(shí)現(xiàn)海量高維數(shù)據(jù)的檢索。相對(duì)于檢索的準(zhǔn)確性，用戶更注重搜索的速度，在大多數(shù)情況下，完全精確的查找并不是必須的，近似解已經(jīng)足以滿足用戶絕大多數(shù)的要求。給定一個(gè)高維數(shù)據(jù)的搜索，通過哈希函數(shù)將其映射為簡短的哈希編碼，在數(shù)據(jù)集(查找和它具有相同或相近編碼的數(shù)據(jù)作為搜索結(jié)果。由于哈希編碼的相似性計(jì)算是非常高效的，因此在面對(duì)海量數(shù)據(jù)的時(shí)候哈希方法也能取得很好的查詢性能。

多媒體數(shù)據(jù)的另一個(gè)特性就是多模態(tài)的數(shù)據(jù)存在共生關(guān)系。舉例來說，一張網(wǎng)絡(luò)圖像除了有圖片本身，還有一些描述信息如標(biāo)題、用戶的標(biāo)注信息、評(píng)論信息等；一則新聞報(bào)道除了有文字的描述通常還有與之相關(guān)的新聞圖片。跨媒體檢索的目標(biāo)就是合理地利用同一模態(tài)內(nèi)數(shù)據(jù)的相似性以及不同模態(tài)的數(shù)據(jù)已知的關(guān)聯(lián)關(guān)系，在不同媒體之間建立“橋梁”，使得不同模態(tài)的數(shù)據(jù)可以在統(tǒng)一的度量空間進(jìn)行相似性比較。為了能對(duì)海量的多模態(tài)的多媒體數(shù)據(jù)實(shí)現(xiàn)高效的跨媒體檢索，相應(yīng)的跨媒體哈希索引算法被相繼提出。

已有的跨媒體哈希算法大多還是基于流形學(xué)習(xí)的框架，學(xué)習(xí)的哈希函數(shù)試圖在保留每個(gè)模態(tài)的數(shù)據(jù)的流形的同時(shí)，將不同模態(tài)映射到同一個(gè)子空間內(nèi)并將不同模態(tài)的流形對(duì)齊。近年來，人們發(fā)現(xiàn)字典學(xué)習(xí)的方法也可以很好地用學(xué)習(xí)得到的字典對(duì)數(shù)據(jù)進(jìn)行有效地表達(dá)。本發(fā)明提出的方法就是基于字典學(xué)習(xí)的框架來來進(jìn)行多模態(tài)字典學(xué)習(xí)，并把學(xué)習(xí)得到的字典作為哈希函數(shù)建立跨媒體哈希索引。

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

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

跨媒體稀疏哈希索引方法包括如下步驟：

1)對(duì)多個(gè)模態(tài)數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系利用超圖進(jìn)行統(tǒng)一建模；模態(tài)內(nèi)的相似性使用數(shù)據(jù)的底層特征的歐氏距離，模態(tài)間的關(guān)聯(lián)利用不同模態(tài)數(shù)據(jù)已知的關(guān)聯(lián)關(guān)系；

2)將統(tǒng)一超圖約束引入多模態(tài)字典學(xué)習(xí)的框架內(nèi)，使得學(xué)習(xí)得到的多模態(tài)字典能保留模態(tài)內(nèi)的相似性以及模態(tài)間的關(guān)聯(lián)關(guān)系；

3)將學(xué)習(xí)得到的字典作為哈希函數(shù)，對(duì)新的數(shù)據(jù)利用對(duì)應(yīng)模態(tài)的字典進(jìn)行稀疏編碼；

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

所述的步驟2)包括：

給出如下基于最小重建誤差的目標(biāo)函數(shù)，以實(shí)現(xiàn)多模態(tài)字典學(xué)習(xí)：