====== 2016 XEP33SAM -- Understanding State of the Art Methods, Algorithms, and Implementations =====
Meeting time: Wednesdays 16:15
Location: G102A
===== First meeting 30 Mar 2016 =====
=== Paper ===
Marius Muja and David G. Lowe: "Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration", in International Conference on Computer Vision Theory and Applications (VISAPP'09), 2009 [[http://people.cs.ubc.ca/~mariusm/uploads/FLANN/flann_visapp09.pdf|PDF]]
[[http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN|software page]]
== Task ==
* Implement approximate k-means algorithm, use approximate NN instead of exact NN
* Construct k-NN graph: a directed graph, vertex is a feature vector, from each vertex there are k edges to k nearest data vectors
Oxford 5k dataset: image [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/images.zip|thumbnails]], [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/imagedesc.dat|descriptors]] (128 D vectors, single precision, stored one by one), and corresponing image [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/imagenames.txt|names]] (one name per line, i-th name corresponds to i-th descriptors).
The following lines will read the descriptors and the image names in MATLAB:
fid = fopen('imagedesc.dat', 'r');\\
X = fread(fid, [128,inf], 'single=>single');\\
fclose(fid);\\
Names = textread('imagenames.txt', '%s');
SIFT dataset: 2M SIFT descriptors are available [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/sift.zip|here]]. The descriptors are 128D unsigned byte precision, the following Matlab lines will read the descriptors:
fid = fopen('SIFT.dat', 'r');\\
X = fread(fid, [128,inf], 'uint8=>uint8');\\
fclose(fid);\\
Use the SIFT dataset for the approximate k-means. Use 32k cluster centers. Compare three different assignments to the nearest cluster (kd-forest, k-means tree, exact assignmet). For all three cases, start from identical inicialization. Compare the final results (up to say 30 iterations) in terms of sum of squared distances, that is Σ (X - f(X))^2, where f(X) is the assigned cluster center.
Looking forward to results on your own data too.
===== Second meeting 20/4 2016 =====
=== Paper ===
Herve Jegou, Matthijs Douze, Cordelia Schmid: "Product quantization for nearest neighbor search", PAMI 2011.
[[http://hal.inria.fr/docs/00/82/50/85/PDF/jegou_pq_postprint.pdf|PDF]] [[http://www.irisa.fr/texmex/people/jegou/ann.php|software page]]
(Do not get confused by the text on the page. The mex version is in the package.)
== Task ==
Oxford 105k dataset: image [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/oxc-complete.zip|thumbnails]], [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/imgdesc105k.dat|descriptors]] (128 D vectors, single precision, stored one by one), and corresponing image [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/imagenames105k.txt|names]] (one name per line, i-th name corresponds to i-th descriptors, Oxford 5k image names are given without a directory, remaining filenames contain a directory corresponding to the distributed directory structure).
Additional descriptors for Oxford105k are available [[http://cmp.felk.cvut.cz/~chum/XEP33SAM/CNNdesc105k.dat|here]]. These descriptors are based on deep convolutional neural networks and should in general give better visual similarity for nearest neighbours than the previous ones, please compare.
* For each image (use all 105k images) find k-NN, visually verify the quality - script that for a selected image shows the k neighbours, etc.
* Compare the quality and running time of product quantization and FLANN. Select 1000 images at random and find exact k-NN, for each of the algorithms compute an estimate of its precision.
===== Third meeting 16/5 2016 (MONDAY change of day) =====
=== Paper ===
Ahmet Iscen, Teddy Furon, Vincent Gripon, Michael Rabbat, Hervé Jégou: "Memory vectors for similarity search in high-dimensional spaces", 2014.
[[http://arxiv.org/abs/1412.3328|Arxiv]] [[http://people.rennes.inria.fr/Ahmet.Iscen/memoryvectors.html|software page]]
== Task ==
Apply memory vectors on Oxford 105k dataset. Report precision and time efficiency, compare with previous approaches.
===== Fourth meeting *MONDAY* 20/6/2016 =====
=== Paper ===
Wei Dong, Moses Charikar, Kai Li : "Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures." In Proceedings of the 20th international conference on World Wide Web (WWW). New York, NY. 2011.
[[http://www.cs.princeton.edu/cass/papers/www11.pdf|PDF]] [[http://code.google.com/p/nndes/|software page]]
Use the new [[http://www.kgraph.org/| KGraph]] implementation.
=== Task ===
Create a k-NN graph on the Oxford 105k dataset (CNN descriptors) and compare the precision and the run-time with the previous methods. Perform also a visual inspection of the results (are the nearest images similar?).