XEP33SAM -- Understan​ding State of the Art Methods, Algorithms​, and Implementa​tions

Meeting time: Wednesdays 16:30 Location: G102A

Kick-off meeting 27 Feb 2019

Location: Karlovo namesti G3 (ground floor) at 16:30

First meeting 20 Mar 2019

Paper

Marius Muja and David G. Lowe: “Scalable Nearest Neighbor Algorithms for High Dimensional Data”. Pattern Analysis and Machine Intelligence (PAMI), Vol. 36, 2014. PDF software page

• 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 thumbnails, descriptors (128 D vectors, single precision, stored one by one), and corresponing image 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');
fclose(fid);

SIFT dataset: 2M SIFT descriptors are available here. The descriptors are 128D unsigned byte precision, the following Matlab lines will read the descriptors:

fid = fopen('SIFT.dat', 'r');
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 ??/4 2019

Paper

Herve Jegou, Matthijs Douze, Cordelia Schmid: “Product quantization for nearest neighbor search”, PAMI 2011. PDF software page

(Do not get confused by the text on the page. The mex version is in the package.)