Renesas / opencv-lib

openCV library for Renesas RZ/A

Dependents:   RZ_A2M_Mbed_samples

include/opencv2/flann/lsh_table.h@0:0e0631af0305, 2021-01-29 (annotated)

Committer:
RyoheiHagimoto
Date:
Fri Jan 29 04:53:38 2021 +0000
Revision:
0:0e0631af0305
copied from https://github.com/d-kato/opencv-lib.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
RyoheiHagimoto 0:0e0631af0305 1 /***********************************************************************
RyoheiHagimoto 0:0e0631af0305 2 * Software License Agreement (BSD License)
RyoheiHagimoto 0:0e0631af0305 3 *
RyoheiHagimoto 0:0e0631af0305 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
RyoheiHagimoto 0:0e0631af0305 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
RyoheiHagimoto 0:0e0631af0305 6 *
RyoheiHagimoto 0:0e0631af0305 7 * THE BSD LICENSE
RyoheiHagimoto 0:0e0631af0305 8 *
RyoheiHagimoto 0:0e0631af0305 9 * Redistribution and use in source and binary forms, with or without
RyoheiHagimoto 0:0e0631af0305 10 * modification, are permitted provided that the following conditions
RyoheiHagimoto 0:0e0631af0305 11 * are met:
RyoheiHagimoto 0:0e0631af0305 12 *
RyoheiHagimoto 0:0e0631af0305 13 * 1. Redistributions of source code must retain the above copyright
RyoheiHagimoto 0:0e0631af0305 14 * notice, this list of conditions and the following disclaimer.
RyoheiHagimoto 0:0e0631af0305 15 * 2. Redistributions in binary form must reproduce the above copyright
RyoheiHagimoto 0:0e0631af0305 16 * notice, this list of conditions and the following disclaimer in the
RyoheiHagimoto 0:0e0631af0305 17 * documentation and/or other materials provided with the distribution.
RyoheiHagimoto 0:0e0631af0305 18 *
RyoheiHagimoto 0:0e0631af0305 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
RyoheiHagimoto 0:0e0631af0305 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
RyoheiHagimoto 0:0e0631af0305 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
RyoheiHagimoto 0:0e0631af0305 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
RyoheiHagimoto 0:0e0631af0305 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
RyoheiHagimoto 0:0e0631af0305 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
RyoheiHagimoto 0:0e0631af0305 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
RyoheiHagimoto 0:0e0631af0305 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
RyoheiHagimoto 0:0e0631af0305 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
RyoheiHagimoto 0:0e0631af0305 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
RyoheiHagimoto 0:0e0631af0305 29 *************************************************************************/
RyoheiHagimoto 0:0e0631af0305 30
RyoheiHagimoto 0:0e0631af0305 31 /***********************************************************************
RyoheiHagimoto 0:0e0631af0305 32 * Author: Vincent Rabaud
RyoheiHagimoto 0:0e0631af0305 33 *************************************************************************/
RyoheiHagimoto 0:0e0631af0305 34
RyoheiHagimoto 0:0e0631af0305 35 #ifndef OPENCV_FLANN_LSH_TABLE_H_
RyoheiHagimoto 0:0e0631af0305 36 #define OPENCV_FLANN_LSH_TABLE_H_
RyoheiHagimoto 0:0e0631af0305 37
RyoheiHagimoto 0:0e0631af0305 38 #include <algorithm>
RyoheiHagimoto 0:0e0631af0305 39 #include <iostream>
RyoheiHagimoto 0:0e0631af0305 40 #include <iomanip>
RyoheiHagimoto 0:0e0631af0305 41 #include <limits.h>
RyoheiHagimoto 0:0e0631af0305 42 // TODO as soon as we use C++0x, use the code in USE_UNORDERED_MAP
RyoheiHagimoto 0:0e0631af0305 43 #ifdef __GXX_EXPERIMENTAL_CXX0X__
RyoheiHagimoto 0:0e0631af0305 44 # define USE_UNORDERED_MAP 1
RyoheiHagimoto 0:0e0631af0305 45 #else
RyoheiHagimoto 0:0e0631af0305 46 # define USE_UNORDERED_MAP 0
RyoheiHagimoto 0:0e0631af0305 47 #endif
RyoheiHagimoto 0:0e0631af0305 48 #if USE_UNORDERED_MAP
RyoheiHagimoto 0:0e0631af0305 49 #include <unordered_map>
RyoheiHagimoto 0:0e0631af0305 50 #else
RyoheiHagimoto 0:0e0631af0305 51 #include <map>
RyoheiHagimoto 0:0e0631af0305 52 #endif
RyoheiHagimoto 0:0e0631af0305 53 #include <math.h>
RyoheiHagimoto 0:0e0631af0305 54 #include <stddef.h>
RyoheiHagimoto 0:0e0631af0305 55
RyoheiHagimoto 0:0e0631af0305 56 #include "dynamic_bitset.h"
RyoheiHagimoto 0:0e0631af0305 57 #include "matrix.h"
RyoheiHagimoto 0:0e0631af0305 58
RyoheiHagimoto 0:0e0631af0305 59 namespace cvflann
RyoheiHagimoto 0:0e0631af0305 60 {
RyoheiHagimoto 0:0e0631af0305 61
RyoheiHagimoto 0:0e0631af0305 62 namespace lsh
RyoheiHagimoto 0:0e0631af0305 63 {
RyoheiHagimoto 0:0e0631af0305 64
RyoheiHagimoto 0:0e0631af0305 65 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
RyoheiHagimoto 0:0e0631af0305 66
RyoheiHagimoto 0:0e0631af0305 67 /** What is stored in an LSH bucket
RyoheiHagimoto 0:0e0631af0305 68 */
RyoheiHagimoto 0:0e0631af0305 69 typedef uint32_t FeatureIndex;
RyoheiHagimoto 0:0e0631af0305 70 /** The id from which we can get a bucket back in an LSH table
RyoheiHagimoto 0:0e0631af0305 71 */
RyoheiHagimoto 0:0e0631af0305 72 typedef unsigned int BucketKey;
RyoheiHagimoto 0:0e0631af0305 73
RyoheiHagimoto 0:0e0631af0305 74 /** A bucket in an LSH table
RyoheiHagimoto 0:0e0631af0305 75 */
RyoheiHagimoto 0:0e0631af0305 76 typedef std::vector<FeatureIndex> Bucket;
RyoheiHagimoto 0:0e0631af0305 77
RyoheiHagimoto 0:0e0631af0305 78 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
RyoheiHagimoto 0:0e0631af0305 79
RyoheiHagimoto 0:0e0631af0305 80 /** POD for stats about an LSH table
RyoheiHagimoto 0:0e0631af0305 81 */
RyoheiHagimoto 0:0e0631af0305 82 struct LshStats
RyoheiHagimoto 0:0e0631af0305 83 {
RyoheiHagimoto 0:0e0631af0305 84 std::vector<unsigned int> bucket_sizes_;
RyoheiHagimoto 0:0e0631af0305 85 size_t n_buckets_;
RyoheiHagimoto 0:0e0631af0305 86 size_t bucket_size_mean_;
RyoheiHagimoto 0:0e0631af0305 87 size_t bucket_size_median_;
RyoheiHagimoto 0:0e0631af0305 88 size_t bucket_size_min_;
RyoheiHagimoto 0:0e0631af0305 89 size_t bucket_size_max_;
RyoheiHagimoto 0:0e0631af0305 90 size_t bucket_size_std_dev;
RyoheiHagimoto 0:0e0631af0305 91 /** Each contained vector contains three value: beginning/end for interval, number of elements in the bin
RyoheiHagimoto 0:0e0631af0305 92 */
RyoheiHagimoto 0:0e0631af0305 93 std::vector<std::vector<unsigned int> > size_histogram_;
RyoheiHagimoto 0:0e0631af0305 94 };
RyoheiHagimoto 0:0e0631af0305 95
RyoheiHagimoto 0:0e0631af0305 96 /** Overload the << operator for LshStats
RyoheiHagimoto 0:0e0631af0305 97 * @param out the streams
RyoheiHagimoto 0:0e0631af0305 98 * @param stats the stats to display
RyoheiHagimoto 0:0e0631af0305 99 * @return the streams
RyoheiHagimoto 0:0e0631af0305 100 */
RyoheiHagimoto 0:0e0631af0305 101 inline std::ostream& operator <<(std::ostream& out, const LshStats& stats)
RyoheiHagimoto 0:0e0631af0305 102 {
RyoheiHagimoto 0:0e0631af0305 103 int w = 20;
RyoheiHagimoto 0:0e0631af0305 104 out << "Lsh Table Stats:\n" << std::setw(w) << std::setiosflags(std::ios::right) << "N buckets : "
RyoheiHagimoto 0:0e0631af0305 105 << stats.n_buckets_ << "\n" << std::setw(w) << std::setiosflags(std::ios::right) << "mean size : "
RyoheiHagimoto 0:0e0631af0305 106 << std::setiosflags(std::ios::left) << stats.bucket_size_mean_ << "\n" << std::setw(w)
RyoheiHagimoto 0:0e0631af0305 107 << std::setiosflags(std::ios::right) << "median size : " << stats.bucket_size_median_ << "\n" << std::setw(w)
RyoheiHagimoto 0:0e0631af0305 108 << std::setiosflags(std::ios::right) << "min size : " << std::setiosflags(std::ios::left)
RyoheiHagimoto 0:0e0631af0305 109 << stats.bucket_size_min_ << "\n" << std::setw(w) << std::setiosflags(std::ios::right) << "max size : "
RyoheiHagimoto 0:0e0631af0305 110 << std::setiosflags(std::ios::left) << stats.bucket_size_max_;
RyoheiHagimoto 0:0e0631af0305 111
RyoheiHagimoto 0:0e0631af0305 112 // Display the histogram
RyoheiHagimoto 0:0e0631af0305 113 out << std::endl << std::setw(w) << std::setiosflags(std::ios::right) << "histogram : "
RyoheiHagimoto 0:0e0631af0305 114 << std::setiosflags(std::ios::left);
RyoheiHagimoto 0:0e0631af0305 115 for (std::vector<std::vector<unsigned int> >::const_iterator iterator = stats.size_histogram_.begin(), end =
RyoheiHagimoto 0:0e0631af0305 116 stats.size_histogram_.end(); iterator != end; ++iterator) out << (*iterator)[0] << "-" << (*iterator)[1] << ": " << (*iterator)[2] << ", ";
RyoheiHagimoto 0:0e0631af0305 117
RyoheiHagimoto 0:0e0631af0305 118 return out;
RyoheiHagimoto 0:0e0631af0305 119 }
RyoheiHagimoto 0:0e0631af0305 120
RyoheiHagimoto 0:0e0631af0305 121
RyoheiHagimoto 0:0e0631af0305 122 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
RyoheiHagimoto 0:0e0631af0305 123
RyoheiHagimoto 0:0e0631af0305 124 /** Lsh hash table. As its key is a sub-feature, and as usually
RyoheiHagimoto 0:0e0631af0305 125 * the size of it is pretty small, we keep it as a continuous memory array.
RyoheiHagimoto 0:0e0631af0305 126 * The value is an index in the corpus of features (we keep it as an unsigned
RyoheiHagimoto 0:0e0631af0305 127 * int for pure memory reasons, it could be a size_t)
RyoheiHagimoto 0:0e0631af0305 128 */
RyoheiHagimoto 0:0e0631af0305 129 template<typename ElementType>
RyoheiHagimoto 0:0e0631af0305 130 class LshTable
RyoheiHagimoto 0:0e0631af0305 131 {
RyoheiHagimoto 0:0e0631af0305 132 public:
RyoheiHagimoto 0:0e0631af0305 133 /** A container of all the feature indices. Optimized for space
RyoheiHagimoto 0:0e0631af0305 134 */
RyoheiHagimoto 0:0e0631af0305 135 #if USE_UNORDERED_MAP
RyoheiHagimoto 0:0e0631af0305 136 typedef std::unordered_map<BucketKey, Bucket> BucketsSpace;
RyoheiHagimoto 0:0e0631af0305 137 #else
RyoheiHagimoto 0:0e0631af0305 138 typedef std::map<BucketKey, Bucket> BucketsSpace;
RyoheiHagimoto 0:0e0631af0305 139 #endif
RyoheiHagimoto 0:0e0631af0305 140
RyoheiHagimoto 0:0e0631af0305 141 /** A container of all the feature indices. Optimized for speed
RyoheiHagimoto 0:0e0631af0305 142 */
RyoheiHagimoto 0:0e0631af0305 143 typedef std::vector<Bucket> BucketsSpeed;
RyoheiHagimoto 0:0e0631af0305 144
RyoheiHagimoto 0:0e0631af0305 145 /** Default constructor
RyoheiHagimoto 0:0e0631af0305 146 */
RyoheiHagimoto 0:0e0631af0305 147 LshTable()
RyoheiHagimoto 0:0e0631af0305 148 {
RyoheiHagimoto 0:0e0631af0305 149 }
RyoheiHagimoto 0:0e0631af0305 150
RyoheiHagimoto 0:0e0631af0305 151 /** Default constructor
RyoheiHagimoto 0:0e0631af0305 152 * Create the mask and allocate the memory
RyoheiHagimoto 0:0e0631af0305 153 * @param feature_size is the size of the feature (considered as a ElementType[])
RyoheiHagimoto 0:0e0631af0305 154 * @param key_size is the number of bits that are turned on in the feature
RyoheiHagimoto 0:0e0631af0305 155 */
RyoheiHagimoto 0:0e0631af0305 156 LshTable(unsigned int feature_size, unsigned int key_size)
RyoheiHagimoto 0:0e0631af0305 157 {
RyoheiHagimoto 0:0e0631af0305 158 (void)feature_size;
RyoheiHagimoto 0:0e0631af0305 159 (void)key_size;
RyoheiHagimoto 0:0e0631af0305 160 std::cerr << "LSH is not implemented for that type" << std::endl;
RyoheiHagimoto 0:0e0631af0305 161 assert(0);
RyoheiHagimoto 0:0e0631af0305 162 }
RyoheiHagimoto 0:0e0631af0305 163
RyoheiHagimoto 0:0e0631af0305 164 /** Add a feature to the table
RyoheiHagimoto 0:0e0631af0305 165 * @param value the value to store for that feature
RyoheiHagimoto 0:0e0631af0305 166 * @param feature the feature itself
RyoheiHagimoto 0:0e0631af0305 167 */
RyoheiHagimoto 0:0e0631af0305 168 void add(unsigned int value, const ElementType* feature)
RyoheiHagimoto 0:0e0631af0305 169 {
RyoheiHagimoto 0:0e0631af0305 170 // Add the value to the corresponding bucket
RyoheiHagimoto 0:0e0631af0305 171 BucketKey key = (lsh::BucketKey)getKey(feature);
RyoheiHagimoto 0:0e0631af0305 172
RyoheiHagimoto 0:0e0631af0305 173 switch (speed_level_) {
RyoheiHagimoto 0:0e0631af0305 174 case kArray:
RyoheiHagimoto 0:0e0631af0305 175 // That means we get the buckets from an array
RyoheiHagimoto 0:0e0631af0305 176 buckets_speed_[key].push_back(value);
RyoheiHagimoto 0:0e0631af0305 177 break;
RyoheiHagimoto 0:0e0631af0305 178 case kBitsetHash:
RyoheiHagimoto 0:0e0631af0305 179 // That means we can check the bitset for the presence of a key
RyoheiHagimoto 0:0e0631af0305 180 key_bitset_.set(key);
RyoheiHagimoto 0:0e0631af0305 181 buckets_space_[key].push_back(value);
RyoheiHagimoto 0:0e0631af0305 182 break;
RyoheiHagimoto 0:0e0631af0305 183 case kHash:
RyoheiHagimoto 0:0e0631af0305 184 {
RyoheiHagimoto 0:0e0631af0305 185 // That means we have to check for the hash table for the presence of a key
RyoheiHagimoto 0:0e0631af0305 186 buckets_space_[key].push_back(value);
RyoheiHagimoto 0:0e0631af0305 187 break;
RyoheiHagimoto 0:0e0631af0305 188 }
RyoheiHagimoto 0:0e0631af0305 189 }
RyoheiHagimoto 0:0e0631af0305 190 }
RyoheiHagimoto 0:0e0631af0305 191
RyoheiHagimoto 0:0e0631af0305 192 /** Add a set of features to the table
RyoheiHagimoto 0:0e0631af0305 193 * @param dataset the values to store
RyoheiHagimoto 0:0e0631af0305 194 */
RyoheiHagimoto 0:0e0631af0305 195 void add(Matrix<ElementType> dataset)
RyoheiHagimoto 0:0e0631af0305 196 {
RyoheiHagimoto 0:0e0631af0305 197 #if USE_UNORDERED_MAP
RyoheiHagimoto 0:0e0631af0305 198 buckets_space_.rehash((buckets_space_.size() + dataset.rows) * 1.2);
RyoheiHagimoto 0:0e0631af0305 199 #endif
RyoheiHagimoto 0:0e0631af0305 200 // Add the features to the table
RyoheiHagimoto 0:0e0631af0305 201 for (unsigned int i = 0; i < dataset.rows; ++i) add(i, dataset[i]);
RyoheiHagimoto 0:0e0631af0305 202 // Now that the table is full, optimize it for speed/space
RyoheiHagimoto 0:0e0631af0305 203 optimize();
RyoheiHagimoto 0:0e0631af0305 204 }
RyoheiHagimoto 0:0e0631af0305 205
RyoheiHagimoto 0:0e0631af0305 206 /** Get a bucket given the key
RyoheiHagimoto 0:0e0631af0305 207 * @param key
RyoheiHagimoto 0:0e0631af0305 208 * @return
RyoheiHagimoto 0:0e0631af0305 209 */
RyoheiHagimoto 0:0e0631af0305 210 inline const Bucket* getBucketFromKey(BucketKey key) const
RyoheiHagimoto 0:0e0631af0305 211 {
RyoheiHagimoto 0:0e0631af0305 212 // Generate other buckets
RyoheiHagimoto 0:0e0631af0305 213 switch (speed_level_) {
RyoheiHagimoto 0:0e0631af0305 214 case kArray:
RyoheiHagimoto 0:0e0631af0305 215 // That means we get the buckets from an array
RyoheiHagimoto 0:0e0631af0305 216 return &buckets_speed_[key];
RyoheiHagimoto 0:0e0631af0305 217 break;
RyoheiHagimoto 0:0e0631af0305 218 case kBitsetHash:
RyoheiHagimoto 0:0e0631af0305 219 // That means we can check the bitset for the presence of a key
RyoheiHagimoto 0:0e0631af0305 220 if (key_bitset_.test(key)) return &buckets_space_.find(key)->second;
RyoheiHagimoto 0:0e0631af0305 221 else return 0;
RyoheiHagimoto 0:0e0631af0305 222 break;
RyoheiHagimoto 0:0e0631af0305 223 case kHash:
RyoheiHagimoto 0:0e0631af0305 224 {
RyoheiHagimoto 0:0e0631af0305 225 // That means we have to check for the hash table for the presence of a key
RyoheiHagimoto 0:0e0631af0305 226 BucketsSpace::const_iterator bucket_it, bucket_end = buckets_space_.end();
RyoheiHagimoto 0:0e0631af0305 227 bucket_it = buckets_space_.find(key);
RyoheiHagimoto 0:0e0631af0305 228 // Stop here if that bucket does not exist
RyoheiHagimoto 0:0e0631af0305 229 if (bucket_it == bucket_end) return 0;
RyoheiHagimoto 0:0e0631af0305 230 else return &bucket_it->second;
RyoheiHagimoto 0:0e0631af0305 231 break;
RyoheiHagimoto 0:0e0631af0305 232 }
RyoheiHagimoto 0:0e0631af0305 233 }
RyoheiHagimoto 0:0e0631af0305 234 return 0;
RyoheiHagimoto 0:0e0631af0305 235 }
RyoheiHagimoto 0:0e0631af0305 236
RyoheiHagimoto 0:0e0631af0305 237 /** Compute the sub-signature of a feature
RyoheiHagimoto 0:0e0631af0305 238 */
RyoheiHagimoto 0:0e0631af0305 239 size_t getKey(const ElementType* /*feature*/) const
RyoheiHagimoto 0:0e0631af0305 240 {
RyoheiHagimoto 0:0e0631af0305 241 std::cerr << "LSH is not implemented for that type" << std::endl;
RyoheiHagimoto 0:0e0631af0305 242 assert(0);
RyoheiHagimoto 0:0e0631af0305 243 return 1;
RyoheiHagimoto 0:0e0631af0305 244 }
RyoheiHagimoto 0:0e0631af0305 245
RyoheiHagimoto 0:0e0631af0305 246 /** Get statistics about the table
RyoheiHagimoto 0:0e0631af0305 247 * @return
RyoheiHagimoto 0:0e0631af0305 248 */
RyoheiHagimoto 0:0e0631af0305 249 LshStats getStats() const;
RyoheiHagimoto 0:0e0631af0305 250
RyoheiHagimoto 0:0e0631af0305 251 private:
RyoheiHagimoto 0:0e0631af0305 252 /** defines the speed fo the implementation
RyoheiHagimoto 0:0e0631af0305 253 * kArray uses a vector for storing data
RyoheiHagimoto 0:0e0631af0305 254 * kBitsetHash uses a hash map but checks for the validity of a key with a bitset
RyoheiHagimoto 0:0e0631af0305 255 * kHash uses a hash map only
RyoheiHagimoto 0:0e0631af0305 256 */
RyoheiHagimoto 0:0e0631af0305 257 enum SpeedLevel
RyoheiHagimoto 0:0e0631af0305 258 {
RyoheiHagimoto 0:0e0631af0305 259 kArray, kBitsetHash, kHash
RyoheiHagimoto 0:0e0631af0305 260 };
RyoheiHagimoto 0:0e0631af0305 261
RyoheiHagimoto 0:0e0631af0305 262 /** Initialize some variables
RyoheiHagimoto 0:0e0631af0305 263 */
RyoheiHagimoto 0:0e0631af0305 264 void initialize(size_t key_size)
RyoheiHagimoto 0:0e0631af0305 265 {
RyoheiHagimoto 0:0e0631af0305 266 const size_t key_size_lower_bound = 1;
RyoheiHagimoto 0:0e0631af0305 267 //a value (size_t(1) << key_size) must fit the size_t type so key_size has to be strictly less than size of size_t
RyoheiHagimoto 0:0e0631af0305 268 const size_t key_size_upper_bound = (std::min)(sizeof(BucketKey) * CHAR_BIT + 1, sizeof(size_t) * CHAR_BIT);
RyoheiHagimoto 0:0e0631af0305 269 if (key_size < key_size_lower_bound || key_size >= key_size_upper_bound)
RyoheiHagimoto 0:0e0631af0305 270 {
RyoheiHagimoto 0:0e0631af0305 271 CV_Error(cv::Error::StsBadArg, cv::format("Invalid key_size (=%d). Valid values for your system are %d <= key_size < %d.", (int)key_size, (int)key_size_lower_bound, (int)key_size_upper_bound));
RyoheiHagimoto 0:0e0631af0305 272 }
RyoheiHagimoto 0:0e0631af0305 273
RyoheiHagimoto 0:0e0631af0305 274 speed_level_ = kHash;
RyoheiHagimoto 0:0e0631af0305 275 key_size_ = (unsigned)key_size;
RyoheiHagimoto 0:0e0631af0305 276 }
RyoheiHagimoto 0:0e0631af0305 277
RyoheiHagimoto 0:0e0631af0305 278 /** Optimize the table for speed/space
RyoheiHagimoto 0:0e0631af0305 279 */
RyoheiHagimoto 0:0e0631af0305 280 void optimize()
RyoheiHagimoto 0:0e0631af0305 281 {
RyoheiHagimoto 0:0e0631af0305 282 // If we are already using the fast storage, no need to do anything
RyoheiHagimoto 0:0e0631af0305 283 if (speed_level_ == kArray) return;
RyoheiHagimoto 0:0e0631af0305 284
RyoheiHagimoto 0:0e0631af0305 285 // Use an array if it will be more than half full
RyoheiHagimoto 0:0e0631af0305 286 if (buckets_space_.size() > ((size_t(1) << key_size_) / 2)) {
RyoheiHagimoto 0:0e0631af0305 287 speed_level_ = kArray;
RyoheiHagimoto 0:0e0631af0305 288 // Fill the array version of it
RyoheiHagimoto 0:0e0631af0305 289 buckets_speed_.resize(size_t(1) << key_size_);
RyoheiHagimoto 0:0e0631af0305 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;
RyoheiHagimoto 0:0e0631af0305 291
RyoheiHagimoto 0:0e0631af0305 292 // Empty the hash table
RyoheiHagimoto 0:0e0631af0305 293 buckets_space_.clear();
RyoheiHagimoto 0:0e0631af0305 294 return;
RyoheiHagimoto 0:0e0631af0305 295 }
RyoheiHagimoto 0:0e0631af0305 296
RyoheiHagimoto 0:0e0631af0305 297 // If the bitset is going to use less than 10% of the RAM of the hash map (at least 1 size_t for the key and two
RyoheiHagimoto 0:0e0631af0305 298 // for the vector) or less than 512MB (key_size_ <= 30)
RyoheiHagimoto 0:0e0631af0305 299 if (((std::max(buckets_space_.size(), buckets_speed_.size()) * CHAR_BIT * 3 * sizeof(BucketKey)) / 10
RyoheiHagimoto 0:0e0631af0305 300 >= (size_t(1) << key_size_)) || (key_size_ <= 32)) {
RyoheiHagimoto 0:0e0631af0305 301 speed_level_ = kBitsetHash;
RyoheiHagimoto 0:0e0631af0305 302 key_bitset_.resize(size_t(1) << key_size_);
RyoheiHagimoto 0:0e0631af0305 303 key_bitset_.reset();
RyoheiHagimoto 0:0e0631af0305 304 // Try with the BucketsSpace
RyoheiHagimoto 0:0e0631af0305 305 for (BucketsSpace::const_iterator key_bucket = buckets_space_.begin(); key_bucket != buckets_space_.end(); ++key_bucket) key_bitset_.set(key_bucket->first);
RyoheiHagimoto 0:0e0631af0305 306 }
RyoheiHagimoto 0:0e0631af0305 307 else {
RyoheiHagimoto 0:0e0631af0305 308 speed_level_ = kHash;
RyoheiHagimoto 0:0e0631af0305 309 key_bitset_.clear();
RyoheiHagimoto 0:0e0631af0305 310 }
RyoheiHagimoto 0:0e0631af0305 311 }
RyoheiHagimoto 0:0e0631af0305 312
RyoheiHagimoto 0:0e0631af0305 313 /** The vector of all the buckets if they are held for speed
RyoheiHagimoto 0:0e0631af0305 314 */
RyoheiHagimoto 0:0e0631af0305 315 BucketsSpeed buckets_speed_;
RyoheiHagimoto 0:0e0631af0305 316
RyoheiHagimoto 0:0e0631af0305 317 /** The hash table of all the buckets in case we cannot use the speed version
RyoheiHagimoto 0:0e0631af0305 318 */
RyoheiHagimoto 0:0e0631af0305 319 BucketsSpace buckets_space_;
RyoheiHagimoto 0:0e0631af0305 320
RyoheiHagimoto 0:0e0631af0305 321 /** What is used to store the data */
RyoheiHagimoto 0:0e0631af0305 322 SpeedLevel speed_level_;
RyoheiHagimoto 0:0e0631af0305 323
RyoheiHagimoto 0:0e0631af0305 324 /** If the subkey is small enough, it will keep track of which subkeys are set through that bitset
RyoheiHagimoto 0:0e0631af0305 325 * That is just a speedup so that we don't look in the hash table (which can be mush slower that checking a bitset)
RyoheiHagimoto 0:0e0631af0305 326 */
RyoheiHagimoto 0:0e0631af0305 327 DynamicBitset key_bitset_;
RyoheiHagimoto 0:0e0631af0305 328
RyoheiHagimoto 0:0e0631af0305 329 /** The size of the sub-signature in bits
RyoheiHagimoto 0:0e0631af0305 330 */
RyoheiHagimoto 0:0e0631af0305 331 unsigned int key_size_;
RyoheiHagimoto 0:0e0631af0305 332
RyoheiHagimoto 0:0e0631af0305 333 // Members only used for the unsigned char specialization
RyoheiHagimoto 0:0e0631af0305 334 /** The mask to apply to a feature to get the hash key
RyoheiHagimoto 0:0e0631af0305 335 * Only used in the unsigned char case
RyoheiHagimoto 0:0e0631af0305 336 */
RyoheiHagimoto 0:0e0631af0305 337 std::vector<size_t> mask_;
RyoheiHagimoto 0:0e0631af0305 338 };
RyoheiHagimoto 0:0e0631af0305 339
RyoheiHagimoto 0:0e0631af0305 340 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
RyoheiHagimoto 0:0e0631af0305 341 // Specialization for unsigned char
RyoheiHagimoto 0:0e0631af0305 342
RyoheiHagimoto 0:0e0631af0305 343 template<>
RyoheiHagimoto 0:0e0631af0305 344 inline LshTable<unsigned char>::LshTable(unsigned int feature_size, unsigned int subsignature_size)
RyoheiHagimoto 0:0e0631af0305 345 {
RyoheiHagimoto 0:0e0631af0305 346 initialize(subsignature_size);
RyoheiHagimoto 0:0e0631af0305 347 // Allocate the mask
RyoheiHagimoto 0:0e0631af0305 348 mask_ = std::vector<size_t>((size_t)ceil((float)(feature_size * sizeof(char)) / (float)sizeof(size_t)), 0);
RyoheiHagimoto 0:0e0631af0305 349
RyoheiHagimoto 0:0e0631af0305 350 // A bit brutal but fast to code
RyoheiHagimoto 0:0e0631af0305 351 std::vector<size_t> indices(feature_size * CHAR_BIT);
RyoheiHagimoto 0:0e0631af0305 352 for (size_t i = 0; i < feature_size * CHAR_BIT; ++i) indices[i] = i;
RyoheiHagimoto 0:0e0631af0305 353 std::random_shuffle(indices.begin(), indices.end());
RyoheiHagimoto 0:0e0631af0305 354
RyoheiHagimoto 0:0e0631af0305 355 // Generate a random set of order of subsignature_size_ bits
RyoheiHagimoto 0:0e0631af0305 356 for (unsigned int i = 0; i < key_size_; ++i) {
RyoheiHagimoto 0:0e0631af0305 357 size_t index = indices[i];
RyoheiHagimoto 0:0e0631af0305 358
RyoheiHagimoto 0:0e0631af0305 359 // Set that bit in the mask
RyoheiHagimoto 0:0e0631af0305 360 size_t divisor = CHAR_BIT * sizeof(size_t);
RyoheiHagimoto 0:0e0631af0305 361 size_t idx = index / divisor; //pick the right size_t index
RyoheiHagimoto 0:0e0631af0305 362 mask_[idx] |= size_t(1) << (index % divisor); //use modulo to find the bit offset
RyoheiHagimoto 0:0e0631af0305 363 }
RyoheiHagimoto 0:0e0631af0305 364
RyoheiHagimoto 0:0e0631af0305 365 // Set to 1 if you want to display the mask for debug
RyoheiHagimoto 0:0e0631af0305 366 #if 0
RyoheiHagimoto 0:0e0631af0305 367 {
RyoheiHagimoto 0:0e0631af0305 368 size_t bcount = 0;
RyoheiHagimoto 0:0e0631af0305 369 BOOST_FOREACH(size_t mask_block, mask_){
RyoheiHagimoto 0:0e0631af0305 370 out << std::setw(sizeof(size_t) * CHAR_BIT / 4) << std::setfill('0') << std::hex << mask_block
RyoheiHagimoto 0:0e0631af0305 371 << std::endl;
RyoheiHagimoto 0:0e0631af0305 372 bcount += __builtin_popcountll(mask_block);
RyoheiHagimoto 0:0e0631af0305 373 }
RyoheiHagimoto 0:0e0631af0305 374 out << "bit count : " << std::dec << bcount << std::endl;
RyoheiHagimoto 0:0e0631af0305 375 out << "mask size : " << mask_.size() << std::endl;
RyoheiHagimoto 0:0e0631af0305 376 return out;
RyoheiHagimoto 0:0e0631af0305 377 }
RyoheiHagimoto 0:0e0631af0305 378 #endif
RyoheiHagimoto 0:0e0631af0305 379 }
RyoheiHagimoto 0:0e0631af0305 380
RyoheiHagimoto 0:0e0631af0305 381 /** Return the Subsignature of a feature
RyoheiHagimoto 0:0e0631af0305 382 * @param feature the feature to analyze
RyoheiHagimoto 0:0e0631af0305 383 */
RyoheiHagimoto 0:0e0631af0305 384 template<>
RyoheiHagimoto 0:0e0631af0305 385 inline size_t LshTable<unsigned char>::getKey(const unsigned char* feature) const
RyoheiHagimoto 0:0e0631af0305 386 {
RyoheiHagimoto 0:0e0631af0305 387 // no need to check if T is dividable by sizeof(size_t) like in the Hamming
RyoheiHagimoto 0:0e0631af0305 388 // distance computation as we have a mask
RyoheiHagimoto 0:0e0631af0305 389 const size_t* feature_block_ptr = reinterpret_cast<const size_t*> ((const void*)feature);
RyoheiHagimoto 0:0e0631af0305 390
RyoheiHagimoto 0:0e0631af0305 391 // Figure out the subsignature of the feature
RyoheiHagimoto 0:0e0631af0305 392 // Given the feature ABCDEF, and the mask 001011, the output will be
RyoheiHagimoto 0:0e0631af0305 393 // 000CEF
RyoheiHagimoto 0:0e0631af0305 394 size_t subsignature = 0;
RyoheiHagimoto 0:0e0631af0305 395 size_t bit_index = 1;
RyoheiHagimoto 0:0e0631af0305 396
RyoheiHagimoto 0:0e0631af0305 397 for (std::vector<size_t>::const_iterator pmask_block = mask_.begin(); pmask_block != mask_.end(); ++pmask_block) {
RyoheiHagimoto 0:0e0631af0305 398 // get the mask and signature blocks
RyoheiHagimoto 0:0e0631af0305 399 size_t feature_block = *feature_block_ptr;
RyoheiHagimoto 0:0e0631af0305 400 size_t mask_block = *pmask_block;
RyoheiHagimoto 0:0e0631af0305 401 while (mask_block) {
RyoheiHagimoto 0:0e0631af0305 402 // Get the lowest set bit in the mask block
RyoheiHagimoto 0:0e0631af0305 403 size_t lowest_bit = mask_block & (-(ptrdiff_t)mask_block);
RyoheiHagimoto 0:0e0631af0305 404 // Add it to the current subsignature if necessary
RyoheiHagimoto 0:0e0631af0305 405 subsignature += (feature_block & lowest_bit) ? bit_index : 0;
RyoheiHagimoto 0:0e0631af0305 406 // Reset the bit in the mask block
RyoheiHagimoto 0:0e0631af0305 407 mask_block ^= lowest_bit;
RyoheiHagimoto 0:0e0631af0305 408 // increment the bit index for the subsignature
RyoheiHagimoto 0:0e0631af0305 409 bit_index <<= 1;
RyoheiHagimoto 0:0e0631af0305 410 }
RyoheiHagimoto 0:0e0631af0305 411 // Check the next feature block
RyoheiHagimoto 0:0e0631af0305 412 ++feature_block_ptr;
RyoheiHagimoto 0:0e0631af0305 413 }
RyoheiHagimoto 0:0e0631af0305 414 return subsignature;
RyoheiHagimoto 0:0e0631af0305 415 }
RyoheiHagimoto 0:0e0631af0305 416
RyoheiHagimoto 0:0e0631af0305 417 template<>
RyoheiHagimoto 0:0e0631af0305 418 inline LshStats LshTable<unsigned char>::getStats() const
RyoheiHagimoto 0:0e0631af0305 419 {
RyoheiHagimoto 0:0e0631af0305 420 LshStats stats;
RyoheiHagimoto 0:0e0631af0305 421 stats.bucket_size_mean_ = 0;
RyoheiHagimoto 0:0e0631af0305 422 if ((buckets_speed_.empty()) && (buckets_space_.empty())) {
RyoheiHagimoto 0:0e0631af0305 423 stats.n_buckets_ = 0;
RyoheiHagimoto 0:0e0631af0305 424 stats.bucket_size_median_ = 0;
RyoheiHagimoto 0:0e0631af0305 425 stats.bucket_size_min_ = 0;
RyoheiHagimoto 0:0e0631af0305 426 stats.bucket_size_max_ = 0;
RyoheiHagimoto 0:0e0631af0305 427 return stats;
RyoheiHagimoto 0:0e0631af0305 428 }
RyoheiHagimoto 0:0e0631af0305 429
RyoheiHagimoto 0:0e0631af0305 430 if (!buckets_speed_.empty()) {
RyoheiHagimoto 0:0e0631af0305 431 for (BucketsSpeed::const_iterator pbucket = buckets_speed_.begin(); pbucket != buckets_speed_.end(); ++pbucket) {
RyoheiHagimoto 0:0e0631af0305 432 stats.bucket_sizes_.push_back((lsh::FeatureIndex)pbucket->size());
RyoheiHagimoto 0:0e0631af0305 433 stats.bucket_size_mean_ += pbucket->size();
RyoheiHagimoto 0:0e0631af0305 434 }
RyoheiHagimoto 0:0e0631af0305 435 stats.bucket_size_mean_ /= buckets_speed_.size();
RyoheiHagimoto 0:0e0631af0305 436 stats.n_buckets_ = buckets_speed_.size();
RyoheiHagimoto 0:0e0631af0305 437 }
RyoheiHagimoto 0:0e0631af0305 438 else {
RyoheiHagimoto 0:0e0631af0305 439 for (BucketsSpace::const_iterator x = buckets_space_.begin(); x != buckets_space_.end(); ++x) {
RyoheiHagimoto 0:0e0631af0305 440 stats.bucket_sizes_.push_back((lsh::FeatureIndex)x->second.size());
RyoheiHagimoto 0:0e0631af0305 441 stats.bucket_size_mean_ += x->second.size();
RyoheiHagimoto 0:0e0631af0305 442 }
RyoheiHagimoto 0:0e0631af0305 443 stats.bucket_size_mean_ /= buckets_space_.size();
RyoheiHagimoto 0:0e0631af0305 444 stats.n_buckets_ = buckets_space_.size();
RyoheiHagimoto 0:0e0631af0305 445 }
RyoheiHagimoto 0:0e0631af0305 446
RyoheiHagimoto 0:0e0631af0305 447 std::sort(stats.bucket_sizes_.begin(), stats.bucket_sizes_.end());
RyoheiHagimoto 0:0e0631af0305 448
RyoheiHagimoto 0:0e0631af0305 449 // BOOST_FOREACH(int size, stats.bucket_sizes_)
RyoheiHagimoto 0:0e0631af0305 450 // std::cout << size << " ";
RyoheiHagimoto 0:0e0631af0305 451 // std::cout << std::endl;
RyoheiHagimoto 0:0e0631af0305 452 stats.bucket_size_median_ = stats.bucket_sizes_[stats.bucket_sizes_.size() / 2];
RyoheiHagimoto 0:0e0631af0305 453 stats.bucket_size_min_ = stats.bucket_sizes_.front();
RyoheiHagimoto 0:0e0631af0305 454 stats.bucket_size_max_ = stats.bucket_sizes_.back();
RyoheiHagimoto 0:0e0631af0305 455
RyoheiHagimoto 0:0e0631af0305 456 // TODO compute mean and std
RyoheiHagimoto 0:0e0631af0305 457 /*float mean, stddev;
RyoheiHagimoto 0:0e0631af0305 458 stats.bucket_size_mean_ = mean;
RyoheiHagimoto 0:0e0631af0305 459 stats.bucket_size_std_dev = stddev;*/
RyoheiHagimoto 0:0e0631af0305 460
RyoheiHagimoto 0:0e0631af0305 461 // Include a histogram of the buckets
RyoheiHagimoto 0:0e0631af0305 462 unsigned int bin_start = 0;
RyoheiHagimoto 0:0e0631af0305 463 unsigned int bin_end = 20;
RyoheiHagimoto 0:0e0631af0305 464 bool is_new_bin = true;
RyoheiHagimoto 0:0e0631af0305 465 for (std::vector<unsigned int>::iterator iterator = stats.bucket_sizes_.begin(), end = stats.bucket_sizes_.end(); iterator
RyoheiHagimoto 0:0e0631af0305 466 != end; )
RyoheiHagimoto 0:0e0631af0305 467 if (*iterator < bin_end) {
RyoheiHagimoto 0:0e0631af0305 468 if (is_new_bin) {
RyoheiHagimoto 0:0e0631af0305 469 stats.size_histogram_.push_back(std::vector<unsigned int>(3, 0));
RyoheiHagimoto 0:0e0631af0305 470 stats.size_histogram_.back()[0] = bin_start;
RyoheiHagimoto 0:0e0631af0305 471 stats.size_histogram_.back()[1] = bin_end - 1;
RyoheiHagimoto 0:0e0631af0305 472 is_new_bin = false;
RyoheiHagimoto 0:0e0631af0305 473 }
RyoheiHagimoto 0:0e0631af0305 474 ++stats.size_histogram_.back()[2];
RyoheiHagimoto 0:0e0631af0305 475 ++iterator;
RyoheiHagimoto 0:0e0631af0305 476 }
RyoheiHagimoto 0:0e0631af0305 477 else {
RyoheiHagimoto 0:0e0631af0305 478 bin_start += 20;
RyoheiHagimoto 0:0e0631af0305 479 bin_end += 20;
RyoheiHagimoto 0:0e0631af0305 480 is_new_bin = true;
RyoheiHagimoto 0:0e0631af0305 481 }
RyoheiHagimoto 0:0e0631af0305 482
RyoheiHagimoto 0:0e0631af0305 483 return stats;
RyoheiHagimoto 0:0e0631af0305 484 }
RyoheiHagimoto 0:0e0631af0305 485
RyoheiHagimoto 0:0e0631af0305 486 // End the two namespaces
RyoheiHagimoto 0:0e0631af0305 487 }
RyoheiHagimoto 0:0e0631af0305 488 }
RyoheiHagimoto 0:0e0631af0305 489
RyoheiHagimoto 0:0e0631af0305 490 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
RyoheiHagimoto 0:0e0631af0305 491
RyoheiHagimoto 0:0e0631af0305 492 #endif /* OPENCV_FLANN_LSH_TABLE_H_ */