[image retrivial][searching]inverted file and min-hash

searching
未分类

http://www.cs.utexas.edu/~grauman/courses/fall2009/slides/lecture16_bow.pdf
good intro for descriptors and searching in image retrieval

Video Google: A Text Retrieval Approach to Object Matching in Videos (mension inverted file systems and document
rankings are used) c3996
http://www.robots.ox.ac.uk/~vgg/publications/papers/sivic03.pdf

Scalable Recognition with a Vocabulary Tree - EECS ...C2590
http://www-inst.eecs.berkeley.edu/~cs294-6/fa06/papers/nister_stewenius_cvpr2006.pdf

inverted file indexing

• application: from text retrieval(find all pages on which a word occurs through index) to image search(find all images in which a feature occurs through index)
• for image searching: first generate the local descriptors in high-dimension(128 for example), map the descriptors in to words by quantizing the feature space(tech: clustering)

Min Hash

lecture notes from utah
http://www.cs.utah.edu/~jeffp/teaching/cs5955/L5-Minhash.pdf
Jaccard similarity -> Matrix Representation -> Hash Clustering; Min Hashing

http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf

• [pre]Jaccard similarity
  
  • for two sets A = {0, 1, 2, 5, 6} and B = {0, 2, 3, 5, 7, 9} $JS(A,B)=\frac{|A\cap B|}{|A\cup B|}$
• [pre]Matrix Representation

- Min Hash
- application: for high dimension data which is sparse (eg, BOW Weighted by TF-IDF[to remove 'stop word' like 'the']); LSH can be based on MinHash
- $\pi$ FUNCTION: Minhash(π) of a set is the number of the row(element) with first non-zero in the permuted order π.
- avoid large permutation -> random hash function
- LSH Based on MinHash:http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf