Title :
Weighted Component Hashing of Binary Aggregated Descriptors for Fast Visual Search
Author :
Ling-Yu Duan ; Jie Lin ; Zhe Wang ; Tiejun Huang ; Wen Gao
Author_Institution :
Sch. of Electron. Eng. & Comput. Sci., Peking Univ., Beijing, China
Abstract :
Towards low bit rate mobile visual search, recent works have proposed to aggregate the local features and compress the aggregated descriptor (such as Fisher vector, the vector of locally aggregated descriptors) for low latency query delivery as well as moderate search complexity. Even though Hamming distance can be computed very fast, the computational cost of exhaustive linear search over the binary descriptors grows linearly with either the length of a binary descriptor or the number of database images. In this paper, we propose a novel weighted component hashing (WeCoHash) algorithm for long binary aggregated descriptors to significantly improve search efficiency over a large scale image database. Accordingly, the proposed WeCoHash has attempted to address two essential issues in Hashing algorithms: “what to hash” and “how to search.” “What to hash” is tackled by a hybrid approach, which utilizes both image-specific component (i.e., visual word) redundancy and bit dependency within each component of a binary aggregated descriptor to produce discriminative hash values for bucketing. “How to search” is tackled by an adaptive relevance weighting based on the statistics of hash values. Extensive comparison results have shown that WeCoHash is at least 20 times faster than linear search and 10 times faster than local sensitive hash (LSH) when maintaining comparable search accuracy. In particular , the WeCoHash solution has been adopted by the emerging MPEG compact descriptor for visual search (CDVS) standard to significantly speed up the exhaustive search of the binary aggregated descriptors.
Keywords :
file organisation; image retrieval; redundancy; visual databases; Hamming distance; MPEG CDVS standard; MPEG compact descriptor; WeCoHash algorithm; adaptive relevance weighting; binary aggregated descriptor; bit dependency; compact descriptor for visual search; hybrid approach; image database; image specific component redundancy; local sensitive hash; mobile visual search; moderate search complexity; query delivery; search efficiency; weighted component hashing; Accuracy; Artificial neural networks; Databases; Hamming distance; Search problems; Visualization; Vocabulary; Aggregating local features; hamming space; hashing; visual search;
Journal_Title :
Multimedia, IEEE Transactions on
DOI :
10.1109/TMM.2015.2419973