面向購物圖像搜索的哈希索引結構算法研究.pdf

1、隨著電子商務的不斷發(fā)展，網(wǎng)絡購物因其快捷、方便等優(yōu)點而被越來越多的人所選擇，但隨之而來的是網(wǎng)絡圖像呈幾何增長。如何在這浩瀚的購物圖像數(shù)據(jù)集中快速有效地返回用戶需要的圖像商品，即圖像的相似性搜索問題，已成為學術界和工業(yè)界的最新研究熱點。目前，已有部分購物搜索系統(tǒng)出現(xiàn)，例如:淘淘搜、安圖搜等。而在這些系統(tǒng)中，當用戶上傳一張圖像時，系統(tǒng)返回的時間都相對較長，很難達到用戶的需求。為了提高查詢速度，需要對系統(tǒng)中的數(shù)據(jù)集進行索引結構的建立，一個好的

2、索引結構可以大幅度提高系統(tǒng)檢索速度。
　　 針對這個特點，最初人們提出了通過構建樹形索引結構等一系列方法來解決圖像的相似性搜索問題，但這些方法通常只適用于特征向量維度較低的情況。當特征向量維度較高時，這些方法的性能逐漸下降。為了解決該問題，一種基于近似最近鄰搜索算法—LSH（LocalitySensitiveHashing）被提出。該方法適用于高維數(shù)據(jù)且具有快速高效的搜索效果，因此被作為目前用于相似性搜索最為流行的一種方法。

3、r>　　 本文仍從哈希角度出發(fā)，提出了兩種快速有效的局部敏感哈希算法，其旨在保證系統(tǒng)能在一定搜索精確度的情況下減少查詢時間。本文的主要工作和貢獻總結如下:
　　 第一，提出了一種基于隨機的局部敏感哈希算法。該算法仍遵循LSH思想和框架，但針對現(xiàn)有LSH算法普遍存在的缺陷進行改進。在建立索引時，對于結構中的每個哈希桶，其內部特征向量按照與所屬哈希桶的桶中心距離進行升序排列存儲。查詢時，利用三角不等式原理對候選桶向量進行剪枝過濾，

4、減少距離計算次數(shù)，提高查詢速度。
　　 第二，提出了一種基于非隨機的局部敏感哈希算法。該算法針對隨機局部敏感哈希存在的性能不穩(wěn)定性提出改進。在原始數(shù)據(jù)集上根據(jù)分析維度信息量來建立哈希函數(shù)，由于一個固定的數(shù)據(jù)集維度信息量始終不變，因此哈希函數(shù)的選取不具有隨機性，從而保證了算法性能的穩(wěn)定。查詢時，利用多探測檢測思想，除了將與查詢點對應哈希桶作為候選桶外，還將臨近桶也作為候選桶，同時，利用三角不等式進行剪枝過濾，提高查詢速度。