35 #ifndef RTABMAP_FLANN_LSH_TABLE_H_
36 #define RTABMAP_FLANN_LSH_TABLE_H_
43 #if RTFLANN_USE_UNORDERED_MAP
44 #include <unordered_map>
72 typedef std::vector<FeatureIndex>
Bucket;
97 inline std::ostream&
operator <<(std::ostream& out,
const LshStats& stats)
100 out <<
"Lsh Table Stats:\n" << std::setw(w) << std::setiosflags(std::ios::right) <<
"N buckets : "
101 <<
stats.n_buckets_ <<
"\n" << std::setw(w) << std::setiosflags(std::ios::right) <<
"mean size : "
102 << std::setiosflags(std::ios::left) <<
stats.bucket_size_mean_ <<
"\n" << std::setw(w)
103 << std::setiosflags(std::ios::right) <<
"median size : " <<
stats.bucket_size_median_ <<
"\n" << std::setw(w)
104 << std::setiosflags(std::ios::right) <<
"min size : " << std::setiosflags(std::ios::left)
105 <<
stats.bucket_size_min_ <<
"\n" << std::setw(w) << std::setiosflags(std::ios::right) <<
"max size : "
106 << std::setiosflags(std::ios::left) <<
stats.bucket_size_max_;
109 out << std::endl << std::setw(w) << std::setiosflags(std::ios::right) <<
"histogram : "
110 << std::setiosflags(std::ios::left);
111 for (std::vector<std::vector<unsigned int> >::const_iterator
iterator =
stats.size_histogram_.begin(), end =
112 stats.size_histogram_.end();
iterator != end; ++
iterator)
out << (*iterator)[0] <<
"-" << (*iterator)[1] <<
": " << (*iterator)[2] <<
", ";
125 template<
typename ElementType>
131 #if RTFLANN_USE_UNORDERED_MAP
152 LshTable(
unsigned int ,
unsigned int )
154 std::cerr <<
"LSH is not implemented for that type" << std::endl;
162 void add(
unsigned int value,
const ElementType* feature)
189 void add(
const std::vector< std::pair<size_t, ElementType*> >& features)
191 #if RTFLANN_USE_UNORDERED_MAP
195 for (
size_t i = 0;
i < features.size(); ++
i) {
225 if (bucket_it == bucket_end)
return 0;
226 else return &bucket_it->second;
235 size_t getKey(
const ElementType* )
const
237 std::cerr <<
"LSH is not implemented for that type" << std::endl;
301 template<
typename Archive>
305 if (Archive::is_saving::value) {
309 if (Archive::is_loading::value) {
326 friend struct serialization::access;
352 std::vector<size_t>
mask_;
363 mask_ = std::vector<size_t>((
size_t)
ceil((
float)(feature_size *
sizeof(
char)) / (
float)
sizeof(
size_t)), 0);
366 std::vector<size_t>
indices(feature_size * CHAR_BIT);
367 for (
size_t i = 0;
i < feature_size * CHAR_BIT; ++
i) indices[i] = i;
368 std::random_device rd;
369 std::mt19937
g(rd());
373 for (
unsigned int i = 0;
i < key_size_; ++
i) {
377 size_t divisor = CHAR_BIT *
sizeof(
size_t);
378 size_t idx = index / divisor;
379 mask_[idx] |=
size_t(1) << (index % divisor);
386 BOOST_FOREACH(
size_t mask_block, mask_){
387 out << std::setw(
sizeof(
size_t) * CHAR_BIT / 4) << std::setfill(
'0') << std::hex << mask_block
389 bcount += __builtin_popcountll(mask_block);
391 out <<
"bit count : " << std::dec << bcount << std::endl;
392 out <<
"mask size : " << mask_.size() << std::endl;
406 const size_t* feature_block_ptr =
reinterpret_cast<const size_t*
> (feature);
411 size_t subsignature = 0;
412 size_t bit_index = 1;
414 for (std::vector<size_t>::const_iterator pmask_block = mask_.begin(); pmask_block != mask_.end(); ++pmask_block) {
416 size_t feature_block = *feature_block_ptr;
417 size_t mask_block = *pmask_block;
420 size_t lowest_bit = mask_block & (-(ptrdiff_t)mask_block);
422 subsignature += (feature_block & lowest_bit) ? bit_index : 0;
424 mask_block ^= lowest_bit;
438 stats.bucket_size_mean_ = 0;
439 if ((buckets_speed_.empty()) && (buckets_space_.empty())) {
440 stats.n_buckets_ = 0;
441 stats.bucket_size_median_ = 0;
442 stats.bucket_size_min_ = 0;
443 stats.bucket_size_max_ = 0;
447 if (!buckets_speed_.empty()) {
448 for (BucketsSpeed::const_iterator pbucket = buckets_speed_.begin(); pbucket != buckets_speed_.end(); ++pbucket) {
449 stats.bucket_sizes_.push_back(pbucket->size());
450 stats.bucket_size_mean_ += pbucket->size();
452 stats.bucket_size_mean_ /= buckets_speed_.size();
453 stats.n_buckets_ = buckets_speed_.size();
456 for (BucketsSpace::const_iterator x = buckets_space_.begin(); x != buckets_space_.end(); ++x) {
457 stats.bucket_sizes_.push_back(
x->second.size());
458 stats.bucket_size_mean_ +=
x->second.size();
460 stats.bucket_size_mean_ /= buckets_space_.size();
461 stats.n_buckets_ = buckets_space_.size();
464 std::sort(
stats.bucket_sizes_.begin(),
stats.bucket_sizes_.end());
469 stats.bucket_size_median_ =
stats.bucket_sizes_[
stats.bucket_sizes_.size() / 2];
470 stats.bucket_size_min_ =
stats.bucket_sizes_.front();
471 stats.bucket_size_max_ =
stats.bucket_sizes_.back();
479 unsigned int bin_start = 0;
480 unsigned int bin_end = 20;
481 bool is_new_bin =
true;
486 stats.size_histogram_.push_back(std::vector<unsigned int>(3, 0));
487 stats.size_histogram_.back()[0] = bin_start;
488 stats.size_histogram_.back()[1] = bin_end - 1;
491 ++
stats.size_histogram_.back()[2];