35 #ifndef OPENCV_FLANN_LSH_INDEX_H_
36 #define OPENCV_FLANN_LSH_INDEX_H_
59 LshIndexParams(
unsigned int table_number = 12,
unsigned int key_size = 20,
unsigned int multi_probe_level = 2)
63 (*this)[
"table_number"] = table_number;
65 (*this)[
"key_size"] = key_size;
67 (*this)[
"multi_probe_level"] = multi_probe_level;
77 template<
typename Distance>
90 Distance
d = Distance()) :
91 dataset_(input_data), index_params_(
params), distance_(
d)
95 table_number_ = (
unsigned int)get_param<int>(index_params_,
"table_number",12);
96 key_size_ = (
unsigned int)get_param<int>(index_params_,
"key_size",20);
97 multi_probe_level_ = (
unsigned int)get_param<int>(index_params_,
"multi_probe_level",2);
99 feature_size_ = (unsigned)dataset_.
cols;
100 fill_xor_mask(0, key_size_, multi_probe_level_, xor_masks_);
112 tables_.resize(table_number_);
113 for (
unsigned int i = 0; i < table_number_; ++i) {
145 index_params_[
"algorithm"] =
getType();
146 index_params_[
"table_number"] = table_number_;
147 index_params_[
"key_size"] = key_size_;
148 index_params_[
"multi_probe_level"] = multi_probe_level_;
156 return dataset_.
rows;
164 return feature_size_;
173 return (
int)(dataset_.
rows *
sizeof(
int));
179 return index_params_;
193 assert(indices.
rows >= queries.
rows);
195 assert(
int(indices.
cols) >= knn);
196 assert(
int(dists.
cols) >= knn);
200 for (
size_t i = 0; i < queries.
rows; i++) {
202 std::fill_n(indices[i], knn, -1);
203 std::fill_n(dists[i], knn, std::numeric_limits<DistanceType>::max());
206 else resultSet.
copy(indices[i], dists[i], knn);
222 getNeighbors(vec, result);
228 typedef std::pair<float, unsigned int> ScoreIndexPair;
229 struct SortScoreIndexPairOnSecond
231 bool operator()(
const ScoreIndexPair&
left,
const ScoreIndexPair&
right)
const
233 return left.second < right.second;
244 std::vector<lsh::BucketKey>& xor_masks)
246 xor_masks.push_back(key);
247 if (level == 0)
return;
251 fill_xor_mask(new_key,
index, level - 1, xor_masks);
263 void getNeighbors(
const ElementType* vec,
bool ,
float radius,
bool do_k,
unsigned int k_nn,
266 static std::vector<ScoreIndexPair> score_index_heap;
269 unsigned int worst_score = std::numeric_limits<unsigned int>::max();
270 typename std::vector<lsh::LshTable<ElementType> >::const_iterator
table = tables_.begin();
271 typename std::vector<lsh::LshTable<ElementType> >::const_iterator table_end = tables_.end();
272 for (; table != table_end; ++table) {
273 size_t key = table->getKey(vec);
274 std::vector<lsh::BucketKey>::const_iterator xor_mask = xor_masks_.begin();
275 std::vector<lsh::BucketKey>::const_iterator xor_mask_end = xor_masks_.end();
276 for (; xor_mask != xor_mask_end; ++xor_mask) {
277 size_t sub_key = key ^ (*xor_mask);
278 const lsh::Bucket* bucket = table->getBucketFromKey(sub_key);
279 if (bucket == 0)
continue;
282 std::vector<lsh::FeatureIndex>::const_iterator training_index = bucket->begin();
283 std::vector<lsh::FeatureIndex>::const_iterator last_training_index = bucket->end();
287 for (; training_index < last_training_index; ++training_index) {
288 hamming_distance = distance_(vec, dataset_[*training_index], dataset_.
cols);
290 if (hamming_distance < worst_score) {
292 score_index_heap.push_back(ScoreIndexPair(hamming_distance, training_index));
293 std::push_heap(score_index_heap.begin(), score_index_heap.end());
295 if (score_index_heap.size() > (
unsigned int)k_nn) {
297 std::pop_heap(score_index_heap.begin(), score_index_heap.end());
298 score_index_heap.pop_back();
300 worst_score = score_index_heap.front().first;
308 typename std::vector<lsh::LshTable<ElementType> >::const_iterator table = tables_.begin();
309 typename std::vector<lsh::LshTable<ElementType> >::const_iterator table_end = tables_.end();
310 for (; table != table_end; ++table) {
311 size_t key = table->getKey(vec);
312 std::vector<lsh::BucketKey>::const_iterator xor_mask = xor_masks_.begin();
313 std::vector<lsh::BucketKey>::const_iterator xor_mask_end = xor_masks_.end();
314 for (; xor_mask != xor_mask_end; ++xor_mask) {
315 size_t sub_key = key ^ (*xor_mask);
316 const lsh::Bucket* bucket = table->getBucketFromKey(sub_key);
317 if (bucket == 0)
continue;
320 std::vector<lsh::FeatureIndex>::const_iterator training_index = bucket->begin();
321 std::vector<lsh::FeatureIndex>::const_iterator last_training_index = bucket->end();
325 for (; training_index < last_training_index; ++training_index) {
327 hamming_distance = distance_(vec, dataset_[*training_index], dataset_.
cols);
328 if (hamming_distance < radius) score_index_heap.push_back(ScoreIndexPair(hamming_distance, training_index));
341 typename std::vector<lsh::LshTable<ElementType> >::const_iterator table = tables_.begin();
342 typename std::vector<lsh::LshTable<ElementType> >::const_iterator table_end = tables_.end();
343 for (; table != table_end; ++table) {
344 size_t key = table->getKey(vec);
345 std::vector<lsh::BucketKey>::const_iterator xor_mask = xor_masks_.begin();
346 std::vector<lsh::BucketKey>::const_iterator xor_mask_end = xor_masks_.end();
347 for (; xor_mask != xor_mask_end; ++xor_mask) {
348 size_t sub_key = key ^ (*xor_mask);
350 if (bucket == 0)
continue;
353 std::vector<lsh::FeatureIndex>::const_iterator training_index = bucket->begin();
354 std::vector<lsh::FeatureIndex>::const_iterator last_training_index = bucket->end();
358 for (; training_index < last_training_index; ++training_index) {
360 hamming_distance = distance_(vec, dataset_[*training_index], (
int)dataset_.
cols);
361 result.addPoint(hamming_distance, *training_index);
368 std::vector<lsh::LshTable<ElementType> > tables_;
371 Matrix<ElementType> dataset_;
374 unsigned int feature_size_;
379 unsigned int table_number_;
381 unsigned int key_size_;
383 unsigned int multi_probe_level_;
386 std::vector<lsh::BucketKey> xor_masks_;
392 #endif //OPENCV_FLANN_LSH_INDEX_H_
void findNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &)
Definition: lsh_index.h:220
flann_algorithm_t
Definition: defines.h:81
T get_param(const IndexParams ¶ms, std::string name, const T &default_value)
Definition: params.h:59
GLint level
Definition: tracking.hpp:88
LshIndex(const Matrix< ElementType > &input_data, const IndexParams ¶ms=LshIndexParams(), Distance d=Distance())
Definition: lsh_index.h:89
size_t cols
Definition: matrix.h:52
Definition: lsh_index.h:78
int usedMemory() const
Definition: lsh_index.h:171
CvFileNode const CvStringHashNode * key
Definition: core_c.h:1584
size_t veclen() const
Definition: lsh_index.h:162
GLuint index
Definition: core_c.h:986
int d
Definition: legacy.hpp:3064
IndexParams getParameters() const
Definition: lsh_index.h:177
flann_algorithm_t getType() const
Definition: lsh_index.h:122
Distance::ElementType ElementType
Definition: lsh_index.h:81
Definition: lsh_table.h:130
virtual void knnSearch(const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, int knn, const SearchParams ¶ms)
Perform k-nearest neighbor search.
Definition: lsh_index.h:190
const CvArr const CvArr CvArr * result
Definition: core_c.h:805
unsigned int BucketKey
Definition: lsh_table.h:72
GLenum GLsizei GLenum GLenum const GLvoid * table
size_t size() const
Definition: lsh_index.h:154
LshIndex & operator=(const LshIndex &)
virtual void sortAndCopy(int *indices, DistanceType *dist, int n_neighbors=-1) const
Definition: result_set.h:351
GLuint GLuint GLsizei GLenum const GLvoid * indices
Definition: legacy.hpp:3084
Distance::ResultType DistanceType
Definition: lsh_index.h:82
std::vector< FeatureIndex > Bucket
Definition: lsh_table.h:76
int index
Definition: core_c.h:309
LshIndexParams(unsigned int table_number=12, unsigned int key_size=20, unsigned int multi_probe_level=2)
Definition: lsh_index.h:59
void load_value(FILE *stream, T &value, size_t count=1)
Definition: saving.h:147
void clear()
Definition: result_set.h:425
Definition: result_set.h:389
void buildIndex()
Definition: lsh_index.h:110
virtual void copy(int *indices, DistanceType *dist, int n_neighbors=-1) const
Definition: result_set.h:327
Definition: result_set.h:66
std::map< std::string, any > IndexParams
Definition: params.h:42
GLenum const GLfloat * params
Definition: compat.hpp:688
void add(unsigned int value, const ElementType *feature)
Definition: lsh_table.h:166
Definition: nn_index.h:48
size_t rows
Definition: matrix.h:51
::max::max int
Definition: functional.hpp:324
void saveIndex(FILE *stream)
Saves the index to a stream.
Definition: lsh_index.h:128
void save_value(FILE *stream, const T &value, size_t count=1)
Definition: saving.h:126
CvPoint int radius
Definition: core_c.h:1290
Definition: lsh_index.h:57
void loadIndex(FILE *stream)
Loads the index from a stream.
Definition: lsh_index.h:136