大規模行動裝置影像搜尋：透過多個雜湊表的索引鍵挑選以近似加權漢明距離

Large Scale Mobile Visual Search: Using Index-bit Selection for Multiple Hash Tables to Approximate Weighted Hamming Distance

蔡江漁(Chiang-Yu Tsai)

指導教授 ： 徐宏民

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2014年)

https://doi.org/10.6342/NTU.2014.10791

摘要

在多媒體資訊搜尋系統中最重要的部分就是相似資料搜尋，在近年發表的論文中，雜湊表是個相當常見的方法之一。在使用雜湊表的相似資料搜尋系統中，有兩個技巧可以增進搜尋結果，第一個技巧是使用多個雜湊表，第二個技巧是使用加權漢明距離來評估資料的相似度。在第一個技巧中，多個雜湊表就表示需要有多個索引鍵，要如何決定多個適合的索引鍵就成了使用這個技巧的問題之一。在第二個技巧中，計算加權漢明距離和計算漢明距離比較起來，會多花相當多的時間，這也是一個很大的問題。

在本篇論文中，我們提出了一個機率選擇方法，使用這個選擇方法可以選出多個合適的索引鍵，另外我們可以透過這個選擇方法，計算出一個近似於加權漢明距離的結果，雖然我們的方法只是一個估計值，但是在實驗結果中顯示它確實可以逼近加權漢明距離，並且省下相當多的時間。

關鍵字

雜湊表 ； 加權漢明距離 ； 影像搜尋

並列摘要

The main process in multimedia retrieval systems is nearest neighbours search. To deal with this problem, searching in hash table is widely used in recent works. There are two skills to improve retrieval results. First, using multiple hash tables to improve recall. Second, using weighted hamming distance to measure the similarity between two binary signatures. In the first skill, we need to decide the suitable index keys for hash tables. In the second skill, calculating weighted hamming distance is slow due to floating point operations. In this paper, we propose using a probability selection model to decide the index keys for multiple hash tables based on the weights of bits and calculating an approximation version instead of traditional weighted hamming distance. By using our method, it can significantly save computation time but still keep high accuracy on retrieval results.

並列關鍵字

Hash Tables ； Weighted Hamming Distance ； Image Retrieval

參考文獻

[1] Flickr,http://www.flickr.com/cameras/

[2] Instagram,http://instagram.com/press/

[3] He, J., Feng, J., Liu, X., Cheng, T., Lin, T. H., Chung, H., and Chang, S. F. (2012, June). Mobile product search with bag of hash bits and boundary reranking. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on (pp. 3005- 3012). IEEE.

[4] Cai,J.,Liu,Q.,Chen,F.,Joshi,D.,andTian,Q.(2014,April).ScalableImageSearch with Multiple Index Tables. In Proceedings of International Conference on Multimedia Retrieval (p. 407). ACM.

[5] Kuo, Y. H., Chen, K. T., Chiang, C. H., and Hsu, W. H. (2009, October). Query expansion for hash-based image object retrieval. In Proceedings of the 17th ACM international conference on Multimedia (pp. 65-74). ACM.