大規(guī)模圖像檢索中高維索引技術(shù)研究.pdf

1、大規(guī)模圖像檢索(Large-scale Image Retrieval)旨在從大規(guī)模圖像庫中快速、準(zhǔn)確地查找與查詢圖像內(nèi)容相似的圖像，已在多媒體檢索、版權(quán)保護(hù)和網(wǎng)絡(luò)信息監(jiān)控等領(lǐng)域得到廣泛的應(yīng)用和飛速的發(fā)展。
　　大規(guī)模圖像檢索系統(tǒng)一般采用特征提取技術(shù)將圖像的視覺內(nèi)容描述為高維特征數(shù)據(jù)，從而將圖像檢索問題轉(zhuǎn)化為高維數(shù)據(jù)的相似性度量問題。在網(wǎng)絡(luò)大規(guī)模圖像檢索背景下，特征數(shù)據(jù)動輒上百維且特征規(guī)模在千萬級以上，因此高維索引技術(shù)是影響大規(guī)模

2、圖像檢索性能的關(guān)鍵。“維數(shù)災(zāi)難”問題導(dǎo)致傳統(tǒng)的樹型索引性能急劇下降，且大規(guī)模數(shù)據(jù)環(huán)境下內(nèi)存資源也成為影響系統(tǒng)性能的瓶頸。如何對大規(guī)模高維特征數(shù)據(jù)建立有效的索引，以滿足檢索性能和內(nèi)存資源的要求，是一個極具挑戰(zhàn)的研究熱點(diǎn)與難點(diǎn)問題。
　　為實(shí)現(xiàn)大規(guī)模數(shù)據(jù)環(huán)境下高效率、高精度和低內(nèi)存消耗的高維索引，本文圍繞分布式局部敏感哈希索引、數(shù)據(jù)依賴的多索引哈希算法和二進(jìn)制層次索引技術(shù)等關(guān)鍵問題進(jìn)行了較為深入的研究，取得了如下成果:
　　(1

3、)分布式局部敏感哈希索引
　　局部敏感哈希索引是目前比較通用的近似最近鄰查詢算法。由于該算法在建立哈希表時對數(shù)據(jù)空間進(jìn)行均勻劃分，而真實(shí)數(shù)據(jù)并不呈均勻分布，因此其不能有效處理數(shù)據(jù)非均勻分布問題，進(jìn)而影響其查詢性能。本文首先提出數(shù)據(jù)依賴的局部敏感哈希索引算法，該算法具有兩層結(jié)構(gòu)。在第一層，通過訓(xùn)練數(shù)據(jù)集得到一系列聚類中心，然后根據(jù)聚類中心把待索引的數(shù)據(jù)集劃分成一個個類，從而使得每類中的數(shù)據(jù)呈近似均勻分布。在第二層，對每一類中的數(shù)據(jù)建

4、立哈希表。對于查詢數(shù)據(jù)，首先把它映射到相似的類中心，然后在每一類的哈希表中進(jìn)行近似最近鄰查詢。為了進(jìn)一步提升索引的性能，提出優(yōu)化的分布式局部敏感哈希算法。在國際基準(zhǔn)測試數(shù)據(jù)集上的實(shí)驗結(jié)果表明，與通用的E2LSH算法相比，數(shù)據(jù)依賴的局部敏感哈希索引算法在保持高查詢精度的同時可以使查詢速度提升48倍，并且分布式實(shí)現(xiàn)可以使查詢速度得到進(jìn)一步提升。
　　(2)數(shù)據(jù)依賴的多索引哈希算法
　　多索引哈希是目前使用廣泛的針對二進(jìn)制碼的精確

5、查詢索引算法。由于多索引哈?；跀?shù)據(jù)集中的二進(jìn)制碼呈均勻分布這一假設(shè)，不能有效處理非均勻分布的數(shù)據(jù)集;且在計算海明距離時為二進(jìn)制碼的每一位賦予相同的權(quán)重導(dǎo)致距離度量模糊。針對這一問題，本文提出數(shù)據(jù)依賴的多索引哈希算法。首先把二進(jìn)制碼劃分為多個連續(xù)不重合的子串，并通過協(xié)方差矩陣計算二進(jìn)制碼每位之間的相關(guān)性，為每一個子串學(xué)習(xí)得到自適應(yīng)投影向量。在為每個子串建立哈希表時，使用投影向量對子串進(jìn)行投影從而得到哈希表中的下標(biāo)。采用自適應(yīng)投影的方法可

6、以使得哈希表中的元素接近于均勻分布，進(jìn)而提升查詢速度。本文進(jìn)一步利用協(xié)方差矩陣提出查詢結(jié)果重排序算法，通過為二進(jìn)制碼的每一位賦予不同的權(quán)重對查詢結(jié)果進(jìn)行重排序。在大規(guī)模數(shù)據(jù)集上的實(shí)驗表明，與多索引哈希算法相比數(shù)據(jù)依賴的多索引哈希算法可以使查詢速度提升36.9％-87.4％，查詢精度提升22.2％。
　　(3)二進(jìn)制層次索引技術(shù)
　　為了進(jìn)一步提高索引的查詢速度，研究者提出二進(jìn)制碼近似查詢算法，其中層次聚類樹得到廣泛應(yīng)用。但是

7、該算法隨機(jī)選取類中心并且使用整個二進(jìn)制碼建立索引，影響查詢性能。針對這一問題，本文提出二進(jìn)制層次索引技術(shù)。首先提出一種新的聚類方法，通過二進(jìn)制碼的相對距離選取類中心實(shí)現(xiàn)對數(shù)據(jù)集的均勻劃分。然后提出二進(jìn)制碼壓縮技術(shù)，利用均方差的特性衡量二進(jìn)制碼每位的區(qū)分性，生成短小且區(qū)分性高的二進(jìn)制碼，并根據(jù)壓縮二進(jìn)制碼建立層次聚類樹。最后采用粗篩選與精確過濾相結(jié)合的方式，進(jìn)行索引查詢。在十億級數(shù)據(jù)集上的實(shí)驗表明，本文算法在保證精度的前提下明顯提高了查詢