Implements a Bag of Words based (BoW) image search using an inverted index. More...

#include <inverted_index.hpp>

Inheritance diagram for InvertedIndex:

Collaboration diagram for InvertedIndex:

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

struct	SearchParams
	Subclass of train params base which specifies inverted index training parameters. More...

struct	TrainParams
	Subclass of train params base which specifies inverted index training parameters. More...

Public Member Functions
	InvertedIndex ()

	InvertedIndex (const std::string &file_name)

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...

uint32_t	num_clusters () const
	Returns the number of clusters used in the inverted index descriptors. 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...

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 Attributes
std::vector< std::vector < uint64_t > >	inverted_index

std::vector< float >	idf_weights
	Stores the inverted index, dimension one is the cluster index, dimension two holds a list of ids containing that word. More...

Detailed Description

Implements a Bag of Words based (BoW) image search using an inverted index.

The inverted index keeps track of a list of images associated with each visual word. The images are represented as an unsigned long long which must then be translated back to an actual image using the appropriate Dataset class implementation.

Definition at line 10 of file inverted_index.hpp.

Constructor & Destructor Documentation

InvertedIndex::InvertedIndex ( )

Definition at line 11 of file inverted_index.cxx.

                              : SearchBase() {
 
 }

InvertedIndex::InvertedIndex ( const std::string & file_name )

Definition at line 15 of file inverted_index.cxx.

References filesystem::file_exists(), and load().

                                                        : SearchBase(file_name) {
         if(!filesystem::file_exists(file_name)) {
                 std::cerr << "Error reading index from " << file_name << std::endl;
                 return;
         }
         if(!this->load(file_name)) {
                 std::cerr << "Error reading index from " << file_name << std::endl;
         }
 }

Member Function Documentation

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

virtual

Loads a trained search structure from the input filepath.

Implements SearchBase.

Definition at line 25 of file inverted_index.cxx.

References idf_weights, inverted_index, and num_clusters().

Referenced by InvertedIndex().

                                                     {
         std::cout << "Reading inverted index from " << file_path << "..." << std::endl;
 
         std::ifstream ifs(file_path, std::ios::binary);
         uint32_t num_clusters;
         ifs.read((char *)&num_clusters, sizeof(uint32_t));
         inverted_index.resize(num_clusters);
         idf_weights.resize(num_clusters);
         ifs.read((char *)&idf_weights[0], sizeof(float) * num_clusters);
         for(uint32_t i=0; i<num_clusters; i++) {
                 uint64_t num_entries;
                 ifs.read((char *)&num_entries, sizeof(uint64_t));
                 inverted_index[i].resize(num_entries);
                 ifs.read((char *)&inverted_index[i][0], sizeof(uint64_t) * num_entries);
         }
 
         std::cout << "Done reading inverted index." << std::endl;
         
         return (ifs.rdstate() & std::ifstream::failbit) == 0;
 }

uint32_t InvertedIndex::num_clusters ( ) const

Returns the number of clusters used in the inverted index descriptors.

Definition at line 158 of file inverted_index.cxx.

References idf_weights.

Referenced by load(), and save().

                                            {
         return idf_weights.size();
 }

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

virtual

Saves a trained search structure to the input filepath.

Implements SearchBase.

Definition at line 47 of file inverted_index.cxx.

References idf_weights, inverted_index, and num_clusters().

                                                           {
         std::cout << "Writing inverted index 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 *)&num_clusters, sizeof(uint32_t));
         ofs.write((const char *)&idf_weights[0], sizeof(float) * num_clusters);
         for(uint32_t i=0; i<num_clusters; i++) {
                 uint64_t num_entries = inverted_index[i].size();
                 ofs.write((const char *)&num_entries, sizeof(uint64_t));
                 ofs.write((const char *)&inverted_index[i][0], sizeof(uint64_t) * num_entries);
         }
 
         std::cout << "Done writing inverted index." << std::endl;
 
         return (ofs.rdstate() & std::ofstream::failbit) == 0;
 }

std::shared_ptr< MatchResultsBase > InvertedIndex::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.

If the match is nullptr, then the search failed (it will fail if the example image has missing features).

Implements SearchBase.

Definition at line 99 of file inverted_index.cxx.

References filesystem::file_exists(), idf_weights, Dataset::image(), inverted_index, filesystem::load_sparse_vector(), Dataset::location(), numerics::min_hist(), and Dataset::num_images().

                                                                                                                                                                        {
 
         // 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>();
 
         const std::string &example_bow_descriptors_location = dataset.location(example->feature_path("bow_descriptors"));
         if(!filesystem::file_exists(example_bow_descriptors_location)) {
                 std::cerr << "No file at load " << example_bow_descriptors_location << std::endl;
                 return nullptr;
         }
         numerics::sparse_vector_t example_bow_descriptors;
         if(!filesystem::load_sparse_vector(example_bow_descriptors_location, example_bow_descriptors))  {
                 std::cerr << "Failed to load " << example_bow_descriptors_location << std::endl;
                 return nullptr;
         }
 
         std::vector<uint64_t> candidates(dataset.num_images(), 0);
         uint64_t num_candidates = 0;
         for(size_t i=0; i<example_bow_descriptors.size(); i++) {
                 uint32_t cluster = example_bow_descriptors[i].first;
                 for(size_t j=0; j<inverted_index[cluster].size(); j++) {
                         if(!candidates[inverted_index[cluster][j]])
                                 candidates[inverted_index[cluster][j]] = ++num_candidates;
                 }
         }
 
         std::vector< std::pair<float, uint64_t> > candidate_scores(num_candidates);
 
 #if ENABLE_MULTITHREADING && ENABLE_OPENMP
 #pragma omp parallel for schedule(dynamic)
 #endif
         for(int64_t i=0; i<(int64_t)candidates.size(); i++) {
                 if(!candidates[i]) continue;
 
                 const std::string &bow_descriptors_location = dataset.location(dataset.image(i)->feature_path("bow_descriptors"));
                 if (!filesystem::file_exists(bow_descriptors_location)) continue;
                 numerics::sparse_vector_t bow_descriptors;
                 if(!filesystem::load_sparse_vector(bow_descriptors_location, bow_descriptors)) continue;
 
                 float sim = numerics::min_hist(example_bow_descriptors, bow_descriptors, idf_weights);
                 candidate_scores[candidates[i]-1] = std::pair<float, uint64_t>(sim, i);
         }
 
         std::sort(candidate_scores.begin(), candidate_scores.end(), 
           boost::bind(&std::pair<float, uint64_t>::first, _1) >
           boost::bind(&std::pair<float, uint64_t>::first, _2));
 
         match_result->tfidf_scores.resize(candidate_scores.size());
         match_result->matches.resize(candidate_scores.size());
         
         for(int64_t i=0; i<(int64_t)candidate_scores.size(); i++) {
                 match_result->tfidf_scores[i] = candidate_scores[i].first;
                 match_result->matches[i] = candidate_scores[i].second;
         }
 
         return std::static_pointer_cast<MatchResultsBase>(match_result);
 }

bool InvertedIndex::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 66 of file inverted_index.cxx.

References InvertedIndex::TrainParams::bag_of_words, filesystem::file_exists(), idf_weights, inverted_index, filesystem::load_sparse_vector(), and Dataset::location().

Referenced by main(), and train_index().

                                                                                                                                                         {
         const std::shared_ptr<const TrainParams> &ii_params = std::static_pointer_cast<const TrainParams>(params);
         
         const std::shared_ptr<BagOfWords> &bag_of_words = ii_params->bag_of_words;
         
         if(bag_of_words == nullptr) return false;
 
         inverted_index.resize(bag_of_words->num_clusters());
         idf_weights.resize(bag_of_words->num_clusters(), 0.f);
 
         for (size_t i = 0; i < examples.size(); i++) {
                 const std::shared_ptr<const Image> &image = examples[i];
                 const std::string &bow_descriptors_location = dataset.location(image->feature_path("bow_descriptors"));
 
                 if (!filesystem::file_exists(bow_descriptors_location)) continue;
 
                 numerics::sparse_vector_t bow_descriptors;
                 if(!filesystem::load_sparse_vector(bow_descriptors_location, bow_descriptors)) continue;
 
                 for(size_t j=0; j<bow_descriptors.size(); j++) {
                         inverted_index[bow_descriptors[j].first].push_back(image->id);
                 }
         }
 
         for(size_t i=0; i<idf_weights.size(); i++) {
                 idf_weights[i] = logf(
                                 (float)examples.size() /
                                 (float)inverted_index[i].size());
         }
 
         return true;
 }

Field Documentation

std::vector<float> InvertedIndex::idf_weights

protected

Stores the inverted index, dimension one is the cluster index, dimension two holds a list of ids containing that word.

Definition at line 52 of file inverted_index.hpp.

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

std::vector< std::vector<uint64_t> > InvertedIndex::inverted_index

protected

Definition at line 51 of file inverted_index.hpp.

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

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

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

Data Structures

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation