#include <vocab_tree.hpp>

Inheritance diagram for VocabTree:

Collaboration diagram for VocabTree:

Data Structures
struct	MatchResults
	Subclass of match results base which also returns scores. More...

struct	SearchParams
	Subclass of train params base which specifies Vocab Tree training parameters. More...

struct	TrainParams
	Subclass of train params base which specifies vocab tree training parameters. More...

struct	TreeNode

Public Member Functions
	VocabTree ()

bool	train (Dataset &dataset, const std::shared_ptr< const TrainParamsBase > &params, const std::vector< std::shared_ptr< const Image > > &examples)
	Given a set of training parameters, list of images, trains. More...

bool	load (const std::string &file_path)
	Loads a trained search structure from the input filepath. More...

bool	save (const std::string &file_path) const
	Saves a trained search structure to the input filepath. More...

std::shared_ptr< MatchResultsBase >	search (Dataset &dataset, const std::shared_ptr< const SearchParamsBase > &params, const std::shared_ptr< const Image > &example)
	Given a set of search parameters, a query image, searches for matching images and returns the match. More...

uint32_t	tree_splits () const
	returns the split size of each node More...

uint32_t	tree_depth () const
	returns the depth size of tree More...

Public Member Functions inherited from SearchBase
	SearchBase ()

	SearchBase (const std::string &file_path)

virtual	~SearchBase ()

std::vector< std::shared_ptr < MatchResultsBase > >	search (Dataset &dataset, const std::shared_ptr< SearchParamsBase > &params, const std::vector< std::shared_ptr< const Image > > &examples)
	Given a set of search parameters, list of query images, searches for matching images and returns the result matches. More...

Protected Member Functions
void	buildTreeRecursive (uint32_t t, const cv::Mat &descriptors, cv::TermCriteria &tc, int attempts, int flags, int currLevel)
	Recursively builds a tree, starting with 0 and ending with currLevel = maxLevel-1. More...

std::vector< float >	generateVector (const cv::Mat &descriptors, bool shouldWeight, int64_t id=-1)
	helper function, inserts a dummy possibleMatches More...

std::vector< float >	generateVector (const cv::Mat &descriptors, bool shouldWeight, std::unordered_set< uint32_t > &possibleMatches, int64_t id=-1)
	To call with an id call without possibleMatches and it will go to the helper function Takes descriptors for an image and for each descriptor finds the path down the tree generating a vector (describing the path) Adds up all vectors (one from each descriptor) to return the vector of counts for each node If shouldWeight is true will weight each by the weight of the node, should be true for general query and false for construction If id is set then will insert that id into the invertedFile of each leaf visited, if negative or not set then won't do anything When id is not set will use insert images into possibleMatches, possibleMatches will not be used if id is set. More...

void	generateVectorHelper (uint32_t nodeIndex, const cv::Mat &descriptor, std::vector< float > &counts, std::unordered_set< uint32_t > &possibleMatches, int64_t id=-1)
	Recursive function that recursively goes down the tree from t to find where the single descriptor belongs (stopping at leaf) On each node increments cound in the counts vector If id is set (>=0) then adds the image with that id to the leaf Picks the child to traverse down based on the max dot product. More...

Protected Attributes
uint32_t	split
	stores the amount of splits used to generate tree More...

uint32_t	maxLevel
	Stores the max level of the tree. More...

uint32_t	numberOfNodes
	number of nodes the tree will have, saved in variable so don't have to recompute More...

std::vector< float >	weights

std::vector< TreeNode >	tree

std::vector < std::unordered_map< uint64_t, uint32_t > >	invertedFiles

std::unordered_map< uint64_t, std::vector< float > >	databaseVectors
	Stores the database vectors for all images in the database - d_i in the paper Indexes by the image id. More...

Detailed Description

Definition at line 7 of file vocab_tree.hpp.

Constructor & Destructor Documentation

VocabTree::VocabTree ( )

Definition at line 17 of file vocab_tree.cxx.

                      : SearchBase() {
 
 }

Member Function Documentation

void VocabTree::buildTreeRecursive	(	uint32_t	t,
		const cv::Mat &	descriptors,
		cv::TermCriteria &	tc,
		int	attempts,
		int	flags,
		int	currLevel
	)

protected

Recursively builds a tree, starting with 0 and ending with currLevel = maxLevel-1.

Definition at line 270 of file vocab_tree.cxx.

References maxLevel, split, and tree.

Referenced by train().

                                           {
 
   tree[t].invertedFileLength = descriptors.rows;
   tree[t].level = currLevel;
 
   // handles the leaves
   if (currLevel == maxLevel - 1) {
     tree[t].firstChildIndex = 0;
     return;
   }
 
   cv::Mat labels;
   cv::Mat centers;
 
   std::vector<cv::Mat> groups(split);
   for (uint32_t i = 0; i < split; i++)
     groups[i] = cv::Mat();
 
   // printf("t: %d  rows: %d, counts: ", t, descriptors.rows);
 
   bool enoughToFill = true;
   if (descriptors.rows >= split) {
     cv::kmeans(descriptors, split, labels, tc, attempts, flags, centers);
 
     for (int i = 0; i < labels.rows; i++) {
       int index = labels.at<int>(i);
       groups[index].push_back(descriptors.row(i));
     }
   }
   else {
     // *** THIS SHOULDN'T BE THE CASE, why is kmeans splitting poorly? ****
     enoughToFill = false;
     for (int i = 0; i < descriptors.rows; i++)
       groups[i].push_back(descriptors.row(i));
   }
 
   // for (uint32_t i = 0; i < split; i++)
   //   printf("%d, ", groups[i].rows);
   // printf("\n");
 
   uint32_t totalChildren = pow(split, currLevel);
   
 #if ENABLE_MULTITHREADING && ENABLE_OPENMP && totalChildren<maxThreads
   uint32_t maxThreads = omp_get_num_threads();
 #pragma omp parallel for schedule(dynamic)
 #endif
   for (uint32_t i = 0; i < split; i++) {
     uint32_t childLevelIndex = tree[t].levelIndex*split + i;
     uint32_t childIndex = (uint32_t)((pow(split, tree[t].level+1)-1) / (split - 1)) + childLevelIndex;
     if (enoughToFill)
       tree[childIndex].mean = centers.row(i);
     tree[childIndex].levelIndex = childLevelIndex;
     tree[childIndex].index = childIndex;
     if (i == 0)
       tree[t].firstChildIndex = childIndex;
 
     buildTreeRecursive(childIndex, groups[i], tc, attempts, flags, currLevel + 1);
   }
 }

std::vector< float > VocabTree::generateVector	(	const cv::Mat &	descriptors,
		bool	shouldWeight,
		int64_t	id = `-1`
	)

protected

helper function, inserts a dummy possibleMatches

Definition at line 331 of file vocab_tree.cxx.

Referenced by search(), and train().

                                                                                                   {
   std::unordered_set<uint32_t> dummy;
   return generateVector(descriptors, shouldWeight, dummy, id);
 }

std::vector< float > VocabTree::generateVector	(	const cv::Mat &	descriptors,
		bool	shouldWeight,
		std::unordered_set< uint32_t > &	possibleMatches,
		int64_t	id = `-1`
	)

protected

To call with an id call without possibleMatches and it will go to the helper function Takes descriptors for an image and for each descriptor finds the path down the tree generating a vector (describing the path) Adds up all vectors (one from each descriptor) to return the vector of counts for each node If shouldWeight is true will weight each by the weight of the node, should be true for general query and false for construction If id is set then will insert that id into the invertedFile of each leaf visited, if negative or not set then won't do anything When id is not set will use insert images into possibleMatches, possibleMatches will not be used if id is set.

Definition at line 336 of file vocab_tree.cxx.

References generateVectorHelper(), numberOfNodes, and weights.

                                                             {
 
   std::vector<float> vec(numberOfNodes);
   for (uint32_t i = 0; i < numberOfNodes; i++)
     vec[i] = 0;
 
   for (int r = 0; r < descriptors.rows; r++) {
     generateVectorHelper(0, descriptors.row(r), vec, possibleMatches, id);
   }
 
   // if shouldWeight is true then weight all values in the vector and normalize
   if (shouldWeight) {
     float length = 0; // for normalizing
     for (uint32_t i = 0; i < numberOfNodes; i++) {
       vec[i] *= weights[i];
       length += vec[i] * vec[i];
     }
     length = sqrt(length);
     for (uint32_t i = 0; i < numberOfNodes; i++) {
     if(length == 0)
       vec[i] = 0;
     else
       vec[i] /= length;
     }
 
   }
 
   return vec;
 }

void VocabTree::generateVectorHelper	(	uint32_t	nodeIndex,
		const cv::Mat &	descriptor,
		std::vector< float > &	counts,
		std::unordered_set< uint32_t > &	possibleMatches,
		int64_t	id = `-1`
	)

protected

Recursive function that recursively goes down the tree from t to find where the single descriptor belongs (stopping at leaf) On each node increments cound in the counts vector If id is set (>=0) then adds the image with that id to the leaf Picks the child to traverse down based on the max dot product.

Definition at line 367 of file vocab_tree.cxx.

References invertedFiles, split, and tree.

Referenced by generateVector().

                                                             {
 
   counts[nodeIndex]++;
   // if leaf
   if (tree[nodeIndex].firstChildIndex <= 0) {
     std::unordered_map<uint64_t, uint32_t> & invFile = invertedFiles[tree[nodeIndex].levelIndex];
     //printf("|%d|=%d, ", tree[nodeIndex].levelIndex, invFile.size());
     // inserting image id into the inverted file
     if (id >= 0) {
       //printf("Leaf %d\n", nodeIndex);
 #pragma omp critical
       {
       if (invFile.find(id) == invFile.end())
         invFile[id] = 1;
       else
         invFile[id]++;
       }
     }
     // accumulating image id's into possibleMatches
     else {
       // i don't like doing this serial, should find a better method
       //typedef std::unordered_map<uint64_t, uint32_t>::iterator it_type;
       //for (it_type iterator = invFile.begin(); iterator != invFile.end(); iterator++)
       possibleMatches.insert(tree[nodeIndex].levelIndex); //iterator->first);
     }
   }
   // if inner node
   else {
     uint32_t maxChild = tree[nodeIndex].firstChildIndex;
     double max = descriptor.dot(tree[maxChild].mean);
     
     for (uint32_t i = 1; i < split; i++) {
       if (tree[nodeIndex].invertedFileLength == 0)
         continue;
       uint32_t childIndex = tree[nodeIndex].firstChildIndex + i;
       double dot = descriptor.dot(tree[childIndex].mean);
 
       if (dot>max) {
         max = dot;
         maxChild = childIndex;
       }
     }
     generateVectorHelper(maxChild, descriptor, counts, possibleMatches, id);
   }
 }

bool VocabTree::load ( const std::string & file_path )

virtual

Loads a trained search structure from the input filepath.

Implements SearchBase.

Definition at line 29 of file vocab_tree.cxx.

References cvmat_header::cols, databaseVectors, cvmat_header::elem_size, cvmat_header::elem_type, invertedFiles, maxLevel, numberOfNodes, cvmat_header::rows, split, tree, and weights.

                                                 {
   std::cout << "Reading vocab tree from " << file_path << "..." << std::endl;
 
   std::ifstream ifs(file_path, std::ios::binary);
   ifs.read((char *)&split, sizeof(uint32_t));
   ifs.read((char *)&maxLevel, sizeof(uint32_t));
   ifs.read((char *)&numberOfNodes, sizeof(uint32_t));
 
   weights.resize(numberOfNodes);
   ifs.read((char *)&weights[0], sizeof(float)*numberOfNodes);
 
   // load image data
   uint32_t imageCount;
   ifs.read((char *)&imageCount, sizeof(uint32_t));
   for (uint32_t i = 0; i < imageCount; i++) {
     uint64_t imageId;
     std::vector<float> vec(numberOfNodes);
     ifs.read((char *)&imageId, sizeof(uint64_t));
     ifs.read((char *)&vec[0], sizeof(float)*numberOfNodes);
     databaseVectors[imageId] = vec;
   }
 
   // load inveted files
   uint32_t invertedFileCount;
   ifs.read((char *)&invertedFileCount, sizeof(uint32_t));
   invertedFiles.resize(invertedFileCount);
 
   for (uint32_t i = 0; i < invertedFileCount; i++) {
     uint32_t size;
     ifs.read((char *)&size, sizeof(uint32_t));
     for (uint32_t j = 0; j < size; j++) {
       uint64_t imageId;
       uint32_t imageCount;
       ifs.read((char *)&imageId, sizeof(uint64_t));
       ifs.read((char *)&imageCount, sizeof(uint32_t));
       invertedFiles[i][imageId] = imageCount;
     }
   }
 
   // read in tree
   tree.resize(numberOfNodes);
   for (uint32_t i = 0; i < numberOfNodes; i++) {
     ifs.read((char *)&tree[i].firstChildIndex, sizeof(uint32_t));
     ifs.read((char *)&tree[i].index, sizeof(uint32_t));
     ifs.read((char *)&tree[i].invertedFileLength, sizeof(uint32_t));
     ifs.read((char *)&tree[i].level, sizeof(uint32_t));
     ifs.read((char *)&tree[i].levelIndex, sizeof(uint32_t));
 
     // read cv::mat, copied from filesystem.cxx
     cvmat_header h;
     ifs.read((char *)&h, sizeof(cvmat_header));
     tree[i].mean.create(h.rows, h.cols, h.elem_type);
     if (h.rows == 0 || h.cols == 0) continue;
     ifs.read((char *)tree[i].mean.ptr(), h.rows * h.cols * h.elem_size);
   }
 
   std::cout << "Done reading vocab tree." << std::endl;
   
   return (ifs.rdstate() & std::ifstream::failbit) == 0;
 }

bool VocabTree::save ( const std::string & file_path ) const

virtual

Saves a trained search structure to the input filepath.

Implements SearchBase.

Definition at line 90 of file vocab_tree.cxx.

References cvmat_header::cols, databaseVectors, cvmat_header::elem_size, cvmat_header::elem_type, VocabTree::TreeNode::firstChildIndex, VocabTree::TreeNode::index, VocabTree::TreeNode::invertedFileLength, invertedFiles, VocabTree::TreeNode::level, VocabTree::TreeNode::levelIndex, maxLevel, VocabTree::TreeNode::mean, numberOfNodes, cvmat_header::rows, split, tree, and weights.

Referenced by train_tree().

                                                       {
   std::cout << "Writing vocab tree to " << file_path << "..." << std::endl;
 
   std::ofstream ofs(file_path, std::ios::binary | std::ios::trunc);
 
   //uint32_t num_clusters = inverted_index.size();
   ofs.write((const char *)&split, sizeof(uint32_t));
   ofs.write((const char *)&maxLevel, sizeof(uint32_t));
   ofs.write((const char *)&numberOfNodes, sizeof(uint32_t));
   ofs.write((const char *)&weights[0], sizeof(float)*numberOfNodes); // weights
 
   // write out databaseVectors
   uint32_t imageCount = databaseVectors.size();
   ofs.write((const char *)&imageCount, sizeof(uint32_t));
   for (auto& pair : databaseVectors) {
     ofs.write((const char *)&pair.first, sizeof(uint64_t));
     ofs.write((const char *)&(pair.second)[0], sizeof(float)*numberOfNodes); 
   }
 
   // write out inverted files
   uint32_t numInvertedFiles = invertedFiles.size();
   ofs.write((const char *)&numInvertedFiles, sizeof(uint32_t));
   for (std::unordered_map<uint64_t, uint32_t> invFile : invertedFiles) {
     uint32_t size = invFile.size();
     ofs.write((const char *)&size, sizeof(uint32_t));
     for (std::pair<uint64_t, uint32_t> pair : invFile) {
       ofs.write((const char *)&pair.first, sizeof(uint64_t));
       ofs.write((const char *)&pair.second, sizeof(uint32_t));
     }
   }
 
   // write out tree
   for (uint32_t i = 0; i < numberOfNodes; i++) {
     TreeNode t = tree[i];
     ofs.write((const char *)&t.firstChildIndex, sizeof(uint32_t));
     ofs.write((const char *)&t.index, sizeof(uint32_t));
     ofs.write((const char *)&t.invertedFileLength, sizeof(uint32_t));
     ofs.write((const char *)&t.level, sizeof(uint32_t));
     ofs.write((const char *)&t.levelIndex, sizeof(uint32_t));
 
     // write cv::mat, copied from filesystem.cxx
     cvmat_header h;
     h.elem_size = t.mean.elemSize();
     h.elem_type = t.mean.type();
     h.rows = t.mean.rows;
     h.cols = t.mean.cols;
     ofs.write((char *)&h, sizeof(cvmat_header));
     ofs.write((char *)t.mean.ptr(), h.rows * h.cols * h.elem_size);
   }
 
   std::cout << "Done writing vocab tree." << std::endl;
 
   return (ofs.rdstate() & std::ofstream::failbit) == 0;;
 }

std::shared_ptr< MatchResultsBase > VocabTree::search	(	Dataset &	dataset,
		const std::shared_ptr< const SearchParamsBase > &	params,
		const std::shared_ptr< const Image > &	example
	)

virtual

Given a set of search parameters, a query image, searches for matching images and returns the match.

Implements SearchBase.

Definition at line 415 of file vocab_tree.cxx.

References databaseVectors, filesystem::file_exists(), generateVector(), invertedFiles, filesystem::load_cvmat(), Dataset::location(), and numberOfNodes.

Referenced by main().

                                               {
 
   std::cout << "Searching for matching images..." << std::endl;
   const std::shared_ptr<const SearchParams> &ii_params = std::static_pointer_cast<const SearchParams>(params);
 
   std::shared_ptr<MatchResults> match_result = std::make_shared<MatchResults>();
 
   // get descriptors for example
   if (example == nullptr) return nullptr;
   const std::string &descriptors_location = dataset.location(example->feature_path("descriptors"));
   if (!filesystem::file_exists(descriptors_location)) return nullptr;
 
   cv::Mat descriptors, descriptorsf;
   if (!filesystem::load_cvmat(descriptors_location, descriptors)) return nullptr;
 
   std::unordered_set<uint32_t> possibleMatches;
   descriptors.convertTo(descriptorsf, CV_32FC1);
   std::vector<float> vec = generateVector(descriptorsf, true, possibleMatches);
 
   typedef std::pair<uint64_t, float> matchPair;
   struct myComparer {
     bool operator() (matchPair a, matchPair b) { return a.second < b.second; };
   } comparer;
 
   std::unordered_set<uint64_t> possibleImages;
   for (uint32_t elem : possibleMatches) {
     std::unordered_map<uint64_t, uint32_t> & invFile = invertedFiles[elem];
 
     typedef std::unordered_map<uint64_t, uint32_t>::iterator it_type;
     for (it_type iterator = invFile.begin(); iterator != invFile.end(); iterator++)
     if (possibleImages.count(iterator->first) == 0)
       possibleImages.insert(iterator->first);
   }
 
   //std::set<matchPair, myComparer> values;
   std::vector<matchPair> values;
   for (uint64_t elem : possibleImages) {
     // compute L1 norm (based on paper eq 5)
     //float l1norm = 0;
     float score = 0;
     for (uint32_t i = 0; i < numberOfNodes; i++) {
       float t = vec[i] - (databaseVectors[elem])[i];
       score += t*t;
       // std::cout << vec[i] << std::endl;
       //l1norm += abs(vec[i] * (databaseVectors[elem])[i]);
     }
     //values[elem] = l1norm;
     //values.insert(elem, l1norm));
 
     values.push_back(matchPair(elem, sqrt(score)));
   }
 
 
   std::sort(values.begin(), values.end(), comparer);
 
   // printf("%d matches\n", values.size());
   // add all images in order or match
   for (matchPair m : values){
     match_result->matches.push_back(m.first);
     match_result->tfidf_scores.push_back(m.second);
     // std::cout << m.second << std::endl;
   }
 
   // add in matches, just do 2 for now
   //possibleMatches.size() / 10.0
   /*for (int i = 0; i < 1; i++) {
     std::set<matchPair>::iterator top = values.begin();
     match_result->matches.push_back(top->first);
     match_result->tfidf_scores.push_back(top->second);
   }*/
   //match_result->matches.push_back(0);
 
   return (std::shared_ptr<MatchResultsBase>)match_result;
 }

bool VocabTree::train	(	Dataset &	dataset,
		const std::shared_ptr< const TrainParamsBase > &	params,
		const std::vector< std::shared_ptr< const Image > > &	examples
	)

virtual

Given a set of training parameters, list of images, trains.

Returns true if successful, false if not successful.

Implements SearchBase.

Definition at line 145 of file vocab_tree.cxx.

References buildTreeRecursive(), databaseVectors, filesystem::file_exists(), generateVector(), Dataset::image(), invertedFiles, filesystem::load_cvmat(), Dataset::location(), maxLevel, vision::merge_descriptors(), numberOfNodes, split, tree, and weights.

Referenced by main(), and train_tree().

                                                             {
 
   const std::shared_ptr<const TrainParams> &vt_params = std::static_pointer_cast<const TrainParams>(params);
   split = vt_params->split;
   //uint32_t depth = vt_params->depth;
   maxLevel = vt_params->depth;
   numberOfNodes = (uint32_t)(pow(split, maxLevel) - 1) / (split - 1);
   weights.resize(numberOfNodes);
   tree.resize(numberOfNodes);
   invertedFiles.resize((uint32_t)pow(split, maxLevel-1));
 
   // took the following from bag_of_words
   std::vector<uint64_t> all_ids(examples.size());
   for (uint32_t i = 0; i < examples.size(); i++) {
     all_ids[i] = examples[i]->id;
   }
   std::random_shuffle(all_ids.begin(), all_ids.end());
 
   std::vector<cv::Mat> all_descriptors;
   uint64_t num_features = 0;
   for (size_t i = 0; i < all_ids.size(); i++) {
     std::shared_ptr<Image> image = std::static_pointer_cast<Image>(dataset.image(all_ids[i]));
     if (image == nullptr) continue;
 
     const std::string &descriptors_location = dataset.location(image->feature_path("descriptors"));
     if (!filesystem::file_exists(descriptors_location)) continue;
 
     cv::Mat descriptors, descriptorsf;
     if (filesystem::load_cvmat(descriptors_location, descriptors)) {
       descriptors.convertTo(descriptorsf, CV_32FC1);
       num_features += descriptors.rows;
 
       all_descriptors.push_back(descriptorsf);
     }
   }
 
   const cv::Mat merged_descriptor = vision::merge_descriptors(all_descriptors, true);
   cv::Mat labels;
   uint32_t attempts = 1;
   cv::TermCriteria tc(cv::TermCriteria::COUNT | cv::TermCriteria::EPS, 18, 0.000001);
   // end of stuff from bag of words
 
   tree[0].levelIndex = 0;
   tree[0].index = 0;
   buildTreeRecursive(0, merged_descriptor, tc, attempts, cv::KMEANS_PP_CENTERS, 0);
 
   databaseVectors.reserve(all_ids.size());
 
   // now generate data on the reference images - descriptors go down tree, add images to inverted lists at leaves, 
   //   and generate di vector for image
   // Also stores counts for how many images pass through each node to calculate weights
   std::vector<uint32_t> counts(numberOfNodes);
   for (size_t i = 0; i < numberOfNodes; i++)
     counts[i] = 0;
 
 #if ENABLE_MULTITHREADING && ENABLE_OPENMP
 #pragma omp parallel for schedule(dynamic)
 #endif
   for (size_t i = 0; i < all_ids.size(); i++) {
     std::shared_ptr<Image> image = std::static_pointer_cast<Image>(dataset.image(all_ids[i]));
     if (image == nullptr) continue;
 
     const std::string &descriptors_location = dataset.location(image->feature_path("descriptors"));
     if (!filesystem::file_exists(descriptors_location)) continue;
 
     cv::Mat descriptors, descriptorsf;
     if (filesystem::load_cvmat(descriptors_location, descriptors)) {
       descriptors.convertTo(descriptorsf, CV_32FC1);
       std::vector<float> result = generateVector(descriptorsf, false, all_ids[i]);
       // accumulate counts
       for (size_t j = 0; j < numberOfNodes; j++)
         if (result[j] > 0)
           counts[j]++;
 
       //databaseVectors.insert(std::make_pair<uint64_t, std::vector<float>>(all_ids[i], result));
 #pragma omp critical
       {
         databaseVectors[all_ids[i]] = result;
       }
     }
   }
 
   // create weights according to equation 4: w_i = ln(N / N_i)
   for (size_t i = 0; i < numberOfNodes; i++) {
     if (counts[i] == 0)
       weights[i] = 0;
     else
       weights[i] = log(((float)all_ids.size()) / ((float)counts[i]));
     // printf("Node %d, count %d, total %d, size %d, weight %f \n", i, counts[i], all_ids.size(), tree[i].invertedFileLength, weights[i]);
   }
 
   // now that we have the weights we iterate over all images and adjust the vector by weights, 
   //  then normalizes the vector
   typedef std::unordered_map<uint64_t, std::vector<float>>::iterator it_type;
   for (it_type iterator = databaseVectors.begin(); iterator != databaseVectors.end(); iterator++) {
     float length = 0; // hopefully shouldn't overflow from adding doubles
     for (size_t i = 0; i < numberOfNodes; i++) {
       (iterator->second)[i] *= weights[i];
       length += (float)pow((iterator->second)[i], 2.0);
     }
     // normalizing
     length = sqrt(length);
     for (size_t i = 0; i < numberOfNodes; i++) 
       (iterator->second)[i] /= length;
   }
 
   for (uint32_t i = 0; i < (uint32_t)pow(split, maxLevel - 1); i++) {
     // printf("Size of inv file %d: %d\n", i, invertedFiles[i].size());
   }
   // printf("\n\n");
   uint32_t l = 0, inL = 0;
   for (uint32_t i = 0; i < numberOfNodes; i++) {
     // printf("Node %d, num %d, weight %f || ", i, tree[i].invertedFileLength, weights[i]);
     inL++;
     if (inL >= (uint32_t)pow(split, l)) {
       l++;
       inL = 0;
       // printf("\n");
     }
   }
 
   return true;
 }

uint32_t VocabTree::tree_depth ( ) const

returns the depth size of tree

Definition at line 495 of file vocab_tree.cxx.

References maxLevel.

                                      {
         return maxLevel;
 }

uint32_t VocabTree::tree_splits ( ) const

returns the split size of each node

Definition at line 491 of file vocab_tree.cxx.

References split.

                                       {
         return split;
 }

Field Documentation

std::unordered_map<uint64_t, std::vector<float> > VocabTree::databaseVectors

protected

Stores the database vectors for all images in the database - d_i in the paper Indexes by the image id.

Definition at line 83 of file vocab_tree.hpp.

Referenced by load(), save(), search(), and train().

std::vector<std::unordered_map<uint64_t, uint32_t> > VocabTree::invertedFiles

protected

Definition at line 79 of file vocab_tree.hpp.

Referenced by generateVectorHelper(), load(), save(), search(), and train().

uint32_t VocabTree::maxLevel

protected

Stores the max level of the tree.

Definition at line 72 of file vocab_tree.hpp.

Referenced by buildTreeRecursive(), load(), save(), train(), and tree_depth().

uint32_t VocabTree::numberOfNodes

protected

number of nodes the tree will have, saved in variable so don't have to recompute

Definition at line 74 of file vocab_tree.hpp.

Referenced by generateVector(), load(), save(), search(), and train().

uint32_t VocabTree::split

protected

stores the amount of splits used to generate tree

Definition at line 70 of file vocab_tree.hpp.

Referenced by buildTreeRecursive(), generateVectorHelper(), load(), main(), save(), train(), train_tree(), and tree_splits().

std::vector<TreeNode> VocabTree::tree

protected

Definition at line 78 of file vocab_tree.hpp.

Referenced by buildTreeRecursive(), generateVectorHelper(), load(), save(), and train().

std::vector<float> VocabTree::weights

protected

Definition at line 76 of file vocab_tree.hpp.

Referenced by generateVector(), load(), save(), and train().

The documentation for this class was generated from the following files:

/home/psastras/vocabtree/modules/search/vocab_tree/vocab_tree.hpp
/home/psastras/vocabtree/modules/search/vocab_tree/vocab_tree.cxx

Data Structures

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation