35 #ifndef OPENCV_FLANN_LSH_TABLE_H_
36 #define OPENCV_FLANN_LSH_TABLE_H_
43 #ifdef __GXX_EXPERIMENTAL_CXX0X__
44 # define USE_UNORDERED_MAP 1
46 # define USE_UNORDERED_MAP 0
49 #include <unordered_map>
76 typedef std::vector<FeatureIndex>
Bucket;
104 out <<
"Lsh Table Stats:\n" << std::setw(w) << std::setiosflags(
std::ios::right) <<
"N buckets : "
106 << std::setiosflags(std::ios::left) << stats.
bucket_size_mean_ <<
"\n" << std::setw(w)
108 << std::setiosflags(
std::ios::right) <<
"min size : " << std::setiosflags(std::ios::left)
113 out << std::endl << std::setw(w) << std::setiosflags(
std::ios::right) <<
"histogram : "
114 << std::setiosflags(std::ios::left);
115 for (std::vector<std::vector<unsigned int> >::const_iterator iterator = stats.
size_histogram_.begin(),
end =
116 stats.
size_histogram_.end(); iterator !=
end; ++iterator) out << (*iterator)[0] <<
"-" << (*iterator)[1] <<
": " << (*iterator)[2] <<
", ";
129 template<
typename ElementType>
135 #if USE_UNORDERED_MAP
158 std::cerr <<
"LSH is not implemented for that type" << std::endl;
166 void add(
unsigned int value,
const ElementType* feature)
171 switch (speed_level_) {
174 buckets_speed_[
key].push_back(value);
178 key_bitset_.
set(key);
179 buckets_space_[
key].push_back(value);
184 buckets_space_[
key].push_back(value);
195 #if USE_UNORDERED_MAP
196 buckets_space_.rehash((buckets_space_.size() + dataset.
rows) * 1.2);
199 for (
unsigned int i = 0; i < dataset.
rows; ++i)
add(i, dataset[i]);
211 switch (speed_level_) {
214 return &buckets_speed_[
key];
218 if (key_bitset_.
test(key))
return &buckets_space_.find(key)->second;
224 BucketsSpace::const_iterator bucket_it, bucket_end = buckets_space_.end();
225 bucket_it = buckets_space_.find(key);
227 if (bucket_it == bucket_end)
return 0;
228 else return &bucket_it->second;
239 std::cerr <<
"LSH is not implemented for that type" << std::endl;
257 kArray, kBitsetHash, kHash
262 void initialize(
size_t key_size)
264 const size_t key_size_lower_bound = 1;
266 const size_t key_size_upper_bound =
std::min(
sizeof(
BucketKey) * CHAR_BIT + 1,
sizeof(
size_t) * CHAR_BIT);
267 if (key_size < key_size_lower_bound || key_size >= key_size_upper_bound)
269 std::stringstream errorMessage;
270 errorMessage <<
"Invalid key_size (=" << key_size <<
"). Valid values for your system are " << key_size_lower_bound <<
" <= key_size < " << key_size_upper_bound <<
".";
274 speed_level_ = kHash;
275 key_size_ = (unsigned)key_size;
283 if (speed_level_ == kArray)
return;
286 if (buckets_space_.size() > ((size_t(1) << key_size_) / 2)) {
287 speed_level_ = kArray;
289 buckets_speed_.resize(
size_t(1) << key_size_);
290 for (BucketsSpace::const_iterator key_bucket = buckets_space_.begin(); key_bucket != buckets_space_.end(); ++key_bucket) buckets_speed_[key_bucket->first] = key_bucket->second;
293 buckets_space_.clear();
299 if (((std::max(buckets_space_.size(), buckets_speed_.size()) * CHAR_BIT * 3 *
sizeof(
BucketKey)) / 10
300 >= (
size_t(1) << key_size_)) || (key_size_ <= 32)) {
301 speed_level_ = kBitsetHash;
302 key_bitset_.
resize(
size_t(1) << key_size_);
305 for (BucketsSpace::const_iterator key_bucket = buckets_space_.begin(); key_bucket != buckets_space_.end(); ++key_bucket) key_bitset_.
set(key_bucket->first);
308 speed_level_ = kHash;
322 SpeedLevel speed_level_;
331 unsigned int key_size_;
337 std::vector<size_t> mask_;
346 initialize(subsignature_size);
348 mask_ = std::vector<size_t>((size_t)ceil((
float)(feature_size *
sizeof(
char)) / (
float)
sizeof(
size_t)), 0);
351 std::vector<size_t>
indices(feature_size * CHAR_BIT);
352 for (
size_t i = 0; i < feature_size * CHAR_BIT; ++i) indices[i] = i;
353 std::random_shuffle(indices.begin(), indices.end());
356 for (
unsigned int i = 0; i < key_size_; ++i) {
357 size_t index = indices[i];
360 size_t divisor = CHAR_BIT *
sizeof(size_t);
361 size_t idx = index / divisor;
362 mask_[
idx] |= size_t(1) << (index % divisor);
369 BOOST_FOREACH(
size_t mask_block, mask_){
370 out << std::setw(
sizeof(
size_t) * CHAR_BIT / 4) << std::setfill(
'0') << std::hex << mask_block
372 bcount += __builtin_popcountll(mask_block);
374 out <<
"bit count : " << std::dec << bcount << std::endl;
375 out <<
"mask size : " << mask_.size() << std::endl;
389 const size_t* feature_block_ptr =
reinterpret_cast<const size_t*
> ((
const void*)feature);
394 size_t subsignature = 0;
395 size_t bit_index = 1;
397 for (std::vector<size_t>::const_iterator pmask_block = mask_.begin(); pmask_block != mask_.end(); ++pmask_block) {
399 size_t feature_block = *feature_block_ptr;
400 size_t mask_block = *pmask_block;
403 size_t lowest_bit = mask_block & (-(ptrdiff_t)mask_block);
405 subsignature += (feature_block & lowest_bit) ? bit_index : 0;
407 mask_block ^= lowest_bit;
422 if ((buckets_speed_.empty()) && (buckets_space_.empty())) {
430 if (!buckets_speed_.empty()) {
431 for (BucketsSpeed::const_iterator pbucket = buckets_speed_.begin(); pbucket != buckets_speed_.end(); ++pbucket) {
439 for (BucketsSpace::const_iterator
x = buckets_space_.begin();
x != buckets_space_.end(); ++
x) {
462 unsigned int bin_start = 0;
463 unsigned int bin_end = 20;
464 bool is_new_bin =
true;
467 if (*iterator < bin_end) {
unsigned __int32 uint32_t
Definition: dist.h:38
short float uchar uchar uchar uchar uchar ushort int uchar ushort int float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float float int int int float int int int float int CV_CUDEV_IMPLEMENT_VEC_BINARY_OP char CV_CUDEV_IMPLEMENT_VEC_BINARY_OP ushort CV_CUDEV_IMPLEMENT_VEC_BINARY_OP short CV_CUDEV_IMPLEMENT_VEC_BINARY_OP int CV_CUDEV_IMPLEMENT_VEC_BINARY_OP uint CV_CUDEV_IMPLEMENT_VEC_BINARY_OP float CV_CUDEV_IMPLEMENT_VEC_BINARY_OP double char
Definition: vec_math.hpp:426
std::ostream & operator<<(std::ostream &out, const LshStats &stats)
Definition: lsh_table.h:101
CV_EXPORTS_W void sort(InputArray src, OutputArray dst, int flags)
sorts independently each matrix row or each matrix column
CvFileNode const CvStringHashNode * key
Definition: core_c.h:1584
const int * idx
Definition: core_c.h:323
GLuint index
Definition: core_c.h:986
std::map< BucketKey, Bucket > BucketsSpace
Definition: lsh_table.h:138
LshStats getStats() const
LshTable(unsigned int, unsigned int)
Definition: lsh_table.h:156
size_t bucket_size_std_dev
Definition: lsh_table.h:90
Definition: lsh_table.h:130
size_t bucket_size_mean_
Definition: lsh_table.h:86
size_t getKey(const ElementType *) const
Definition: lsh_table.h:237
std::unordered_map< BucketKey, Bucket > BucketsSpace
Definition: lsh_table.h:136
const Bucket * getBucketFromKey(BucketKey key) const
Definition: lsh_table.h:208
unsigned int BucketKey
Definition: lsh_table.h:72
std::vector< std::vector< unsigned int > > size_histogram_
Definition: lsh_table.h:93
void set(size_t index)
Definition: dynamic_bitset.h:128
boost::dynamic_bitset DynamicBitset
Definition: dynamic_bitset.h:44
void clear()
Definition: dynamic_bitset.h:77
std::vector< FeatureIndex > Bucket
Definition: lsh_table.h:76
CV_EXPORTS_W void min(InputArray src1, InputArray src2, OutputArray dst)
computes per-element minimum of two arrays (dst = min(src1, src2))
void add(Matrix< ElementType > dataset)
Definition: lsh_table.h:193
GLenum GLint x
Definition: core_c.h:632
Definition: lsh_table.h:82
uint32_t FeatureIndex
Definition: lsh_table.h:69
size_t n_buckets_
Definition: lsh_table.h:85
void resize(size_t sz)
Definition: dynamic_bitset.h:119
size_t bucket_size_median_
Definition: lsh_table.h:87
const CvMat CvMat * indices
Definition: legacy.hpp:3052
size_t bucket_size_max_
Definition: lsh_table.h:89
GLsizei const GLfloat * value
Definition: core_c.h:341
std::vector< Bucket > BucketsSpeed
Definition: lsh_table.h:143
void add(unsigned int value, const ElementType *feature)
Definition: lsh_table.h:166
size_t rows
Definition: matrix.h:51
std::vector< unsigned int > bucket_sizes_
Definition: lsh_table.h:84
bool test(size_t index) const
Definition: dynamic_bitset.h:144
::max::max::max float
Definition: functional.hpp:326
GLubyte GLubyte GLubyte GLubyte w
int x
Definition: highgui_c.h:186
double double end
Definition: core_c.h:774
size_t bucket_size_min_
Definition: lsh_table.h:88
const CvArr * right
Definition: calib3d.hpp:353
void reset()
Definition: dynamic_bitset.h:92
LshTable()
Definition: lsh_table.h:147
Definition: types_c.h:222