= vocabulary_tree/Reviews =
== Package proposal ==
This will be a cleaned-up, generic implementation of Nister vocabulary trees intended to replace the one in [[place_recognition]]. Problems with the existing version:
 * Only supports dense uint8 Calonder descriptors. 
  * The new version will allow any feature such that it can compute a distance between two instances.
  * Calonder-specific feature quantization code will be moved out of the `VocabularyTree` class, into a Calonder-specific training program.
 * Assumes L2 distance between features.
  * The new version will allow other metrics (L1, EMD, ...).
 * Complicated implementation.
  * New version will separate tasks across multiple classes instead of putting everything in a monolithic `VocabularyTree` class.
  * Existing version supports hierarchical scoring (every tree node is considered a word and receives a weight). This considerably complicates the implementation for little or no benefit; Nister got the best recognition performance using only the leaves as words. The new version will not bother with hierarchical scoring. (Neither does [[http://www.cvg.ethz.ch/people/postgraduates/fraundof/vocsearch|Fraundorfer's implementation]])

=== Vocabulary Tree ===
Unlike the current all-in-one class, the new `VocabularyTree` is responsible for exactly one task: quantizing features into "words."

{{{
#!cplusplus block=vocab_tree
typedef uint32_t Word;

template<class Feature, class Distance = L2>
class VocabularyTree
{
  VocabularyTree(Distance d = Distance());

  Word quantize(const Feature& f) const;

  void save(const std::string& file) const;
  void load(const std::string& file);
};
}}}

=== Database ===
The `Database` stores "documents" (images represented as words). It can find the set of documents best matching a query. Internally, it keeps an inverted file for each word mapping that word to the documents containing it.
{{{
#!cplusplus block=database
typedef uint32_t DocId;
typedef std::vector<Word> Document;

class Database
{
  // Insert a new document. The returned DocId identifies it.
  DocId insert(const Document& words);

  struct Match
  {
    DocId id;
    float score;
  };
  typedef std::vector<Match> Matches;

  // Find the top N matches in the database for the query document.
  void find(const Document& words, size_t N, Matches& matches) const;

  // Find the top N matches AND insert the query document. insert and find
  // are essentially the same operation, so this is twice as fast as doing
  // them sequentially.
  DocId findAndInsert(const Document& words, size_t N, Matches& matches);

  // Compute the TF-IDF weights of all the words. To be called after inserting
  // a corpus of training examples into the database.
  void computeWeights();

  void saveWeights(const std::string& file) const;
  void loadWeights(const std::string& file);
};
}}}

=== K-means ===
[[place_recognition]] already contains a rather fast implementation of K-means. It uses [[http://cseweb.ucsd.edu/users/elkan/kmeansicml03.pdf|Elkan's algorithm]], which greatly reduces the number of distance computations while producing the same results as standard K-means at each iteration. It can use the [[http://www.google.com/url?sa=t&source=web&ct=res&cd=3&ved=0CBgQFjAC&url=http%3A%2F%2Fwww.ima.umn.edu%2F~iwen%2FREU%2FBATS-Means.pdf&ei=LhdhS6CJCov-tAPzx7DGCw&usg=AFQjCNFr6xZ5n9yRmAKhP8idrkxf_kkY3w|k-means++]] seeding algorithm, which tends to reduce the number of iterations required for convergence. It is already templated to work with `float` or `double` features.

Needed changes:
 * Support user-specified features and distance (currently assume dense features with L2).
 * Tweak as needed to work with integer features.

{{{
#!cplusplus block=kmeans
template<class Feature, class Distance>
class Kmeans
{
  Kmeans(Distance d = Distance());

  // random, use given, kmeans++, ...
  void setInitMethod(...);

  // Stop after convergence or some number of iterations.
  void setMaxIterations(size_t iters);

  // Number of times to run the algorithm, if seeding is non-deterministic.
  void setStarts(size_t starts);

  // Cluster a set of features into k centers, with each input feature
  // assigned membership to some center. Returns the error.
  distance_type cluster(const std::vector<Feature>& features,
                        size_t k,
                        std::vector<Feature>& centers,
                        std::vector<size_t>& membership) const;
};
}}}

A reusable `HierarchicalKmeans` class would be nice to have also, but requires a more complicated interface. That can wait I think.

=== Feature concept ===
Features must have a value type (e.g. `float`, `uint8_t`) and dimension (e.g. 176 for Calonder) known at compile time. This information can be accessed through type traits. Normally a feature class will simply be a wrapper for a stack-allocated array, such as fixed-size `Eigen` vectors or `boost::array`.

=== Distance concept ===
{{{
#!cplusplus block=distance
concept Distance
{
  typedef ... value_type;  // the coordinate type of the feature
  typedef ... result_type; // capable of accumulating value_type

  // Returns the (squared) distance between a and b.
  result_type operator() (const Feature& a, const Feature& b) const;
};
}}}

== Package review meeting notes ==
<<FullSearch(title:"vocabulary_tree/Reviews/" PackageReviewCategory)>>

== Create new package review ==
Enter the date in the appropriate box to generate a template for an API or code review meeting.  Check the [[QAProcess]] page for more information.

<<NewPage(PackageAPIReviewTemplate, API Review, "vocabulary_tree/Reviews", %s_API_Review)>>
<<NewPage(PackageDocReviewTemplate, Doc Review, "vocabulary_tree/Reviews", %s_Doc_Review)>>
<<NewPage(PackageCodeReviewTemplate, Code Review, "vocabulary_tree/Reviews", %s_Code_Review)>>

## PackageReviewCategory