Joe Verbout
opencv on mbed
Embed:
(wiki syntax)
Show/hide line numbers
autotuned_index.h
00001 /*********************************************************************** 00002 * Software License Agreement (BSD License) 00003 * 00004 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. 00005 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved. 00006 * 00007 * THE BSD LICENSE 00008 * 00009 * Redistribution and use in source and binary forms, with or without 00010 * modification, are permitted provided that the following conditions 00011 * are met: 00012 * 00013 * 1. Redistributions of source code must retain the above copyright 00014 * notice, this list of conditions and the following disclaimer. 00015 * 2. Redistributions in binary form must reproduce the above copyright 00016 * notice, this list of conditions and the following disclaimer in the 00017 * documentation and/or other materials provided with the distribution. 00018 * 00019 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 *************************************************************************/ 00030 #ifndef OPENCV_FLANN_AUTOTUNED_INDEX_H_ 00031 #define OPENCV_FLANN_AUTOTUNED_INDEX_H_ 00032 00033 #include "general.h" 00034 #include "nn_index.h" 00035 #include "ground_truth.h" 00036 #include "index_testing.h" 00037 #include "sampling.h" 00038 #include "kdtree_index.h" 00039 #include "kdtree_single_index.h" 00040 #include "kmeans_index.h" 00041 #include "composite_index.h" 00042 #include "linear_index.h" 00043 #include "logger.h" 00044 00045 namespace cvflann 00046 { 00047 00048 template<typename Distance> 00049 NNIndex<Distance>* create_index_by_type(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance); 00050 00051 00052 struct AutotunedIndexParams : public IndexParams 00053 { 00054 AutotunedIndexParams(float target_precision = 0.8, float build_weight = 0.01, float memory_weight = 0, float sample_fraction = 0.1) 00055 { 00056 (*this)["algorithm"] = FLANN_INDEX_AUTOTUNED; 00057 // precision desired (used for autotuning, -1 otherwise) 00058 (*this)["target_precision"] = target_precision; 00059 // build tree time weighting factor 00060 (*this)["build_weight"] = build_weight; 00061 // index memory weighting factor 00062 (*this)["memory_weight"] = memory_weight; 00063 // what fraction of the dataset to use for autotuning 00064 (*this)["sample_fraction"] = sample_fraction; 00065 } 00066 }; 00067 00068 00069 template <typename Distance> 00070 class AutotunedIndex : public NNIndex<Distance> 00071 { 00072 public: 00073 typedef typename Distance::ElementType ElementType; 00074 typedef typename Distance::ResultType DistanceType; 00075 00076 AutotunedIndex(const Matrix<ElementType>& inputData, const IndexParams& params = AutotunedIndexParams(), Distance d = Distance()) : 00077 dataset_(inputData), distance_(d) 00078 { 00079 target_precision_ = get_param(params, "target_precision",0.8f); 00080 build_weight_ = get_param(params,"build_weight", 0.01f); 00081 memory_weight_ = get_param(params, "memory_weight", 0.0f); 00082 sample_fraction_ = get_param(params,"sample_fraction", 0.1f); 00083 bestIndex_ = NULL; 00084 } 00085 00086 AutotunedIndex(const AutotunedIndex&); 00087 AutotunedIndex& operator=(const AutotunedIndex&); 00088 00089 virtual ~AutotunedIndex() 00090 { 00091 if (bestIndex_ != NULL) { 00092 delete bestIndex_; 00093 bestIndex_ = NULL; 00094 } 00095 } 00096 00097 /** 00098 * Method responsible with building the index. 00099 */ 00100 virtual void buildIndex() 00101 { 00102 std::ostringstream stream; 00103 bestParams_ = estimateBuildParams(); 00104 print_params(bestParams_, stream); 00105 Logger::info("----------------------------------------------------\n"); 00106 Logger::info("Autotuned parameters:\n"); 00107 Logger::info("%s", stream.str().c_str()); 00108 Logger::info("----------------------------------------------------\n"); 00109 00110 bestIndex_ = create_index_by_type(dataset_, bestParams_, distance_); 00111 bestIndex_->buildIndex(); 00112 speedup_ = estimateSearchParams(bestSearchParams_); 00113 stream.str(std::string()); 00114 print_params(bestSearchParams_, stream); 00115 Logger::info("----------------------------------------------------\n"); 00116 Logger::info("Search parameters:\n"); 00117 Logger::info("%s", stream.str().c_str()); 00118 Logger::info("----------------------------------------------------\n"); 00119 } 00120 00121 /** 00122 * Saves the index to a stream 00123 */ 00124 virtual void saveIndex(FILE* stream) 00125 { 00126 save_value(stream, (int)bestIndex_->getType()); 00127 bestIndex_->saveIndex(stream); 00128 save_value(stream, get_param<int>(bestSearchParams_, "checks")); 00129 } 00130 00131 /** 00132 * Loads the index from a stream 00133 */ 00134 virtual void loadIndex(FILE* stream) 00135 { 00136 int index_type; 00137 00138 load_value(stream, index_type); 00139 IndexParams params; 00140 params["algorithm"] = (flann_algorithm_t)index_type; 00141 bestIndex_ = create_index_by_type<Distance>(dataset_, params, distance_); 00142 bestIndex_->loadIndex(stream); 00143 int checks; 00144 load_value(stream, checks); 00145 bestSearchParams_["checks"] = checks; 00146 } 00147 00148 /** 00149 * Method that searches for nearest-neighbors 00150 */ 00151 virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) 00152 { 00153 int checks = get_param<int>(searchParams,"checks",FLANN_CHECKS_AUTOTUNED); 00154 if (checks == FLANN_CHECKS_AUTOTUNED) { 00155 bestIndex_->findNeighbors(result, vec, bestSearchParams_); 00156 } 00157 else { 00158 bestIndex_->findNeighbors(result, vec, searchParams); 00159 } 00160 } 00161 00162 00163 IndexParams getParameters() const 00164 { 00165 return bestIndex_->getParameters(); 00166 } 00167 00168 SearchParams getSearchParameters() const 00169 { 00170 return bestSearchParams_; 00171 } 00172 00173 float getSpeedup() const 00174 { 00175 return speedup_; 00176 } 00177 00178 00179 /** 00180 * Number of features in this index. 00181 */ 00182 virtual size_t size() const 00183 { 00184 return bestIndex_->size(); 00185 } 00186 00187 /** 00188 * The length of each vector in this index. 00189 */ 00190 virtual size_t veclen() const 00191 { 00192 return bestIndex_->veclen(); 00193 } 00194 00195 /** 00196 * The amount of memory (in bytes) this index uses. 00197 */ 00198 virtual int usedMemory() const 00199 { 00200 return bestIndex_->usedMemory(); 00201 } 00202 00203 /** 00204 * Algorithm name 00205 */ 00206 virtual flann_algorithm_t getType() const 00207 { 00208 return FLANN_INDEX_AUTOTUNED; 00209 } 00210 00211 private: 00212 00213 struct CostData 00214 { 00215 float searchTimeCost; 00216 float buildTimeCost; 00217 float memoryCost; 00218 float totalCost; 00219 IndexParams params; 00220 }; 00221 00222 void evaluate_kmeans(CostData& cost) 00223 { 00224 StartStopTimer t; 00225 int checks; 00226 const int nn = 1; 00227 00228 Logger::info("KMeansTree using params: max_iterations=%d, branching=%d\n", 00229 get_param<int>(cost.params,"iterations"), 00230 get_param<int>(cost.params,"branching")); 00231 KMeansIndex<Distance> kmeans(sampledDataset_, cost.params, distance_); 00232 // measure index build time 00233 t.start(); 00234 kmeans.buildIndex(); 00235 t.stop(); 00236 float buildTime = (float)t.value; 00237 00238 // measure search time 00239 float searchTime = test_index_precision(kmeans, sampledDataset_, testDataset_, gt_matches_, target_precision_, checks, distance_, nn); 00240 00241 float datasetMemory = float(sampledDataset_.rows * sampledDataset_.cols * sizeof(float)); 00242 cost.memoryCost = (kmeans.usedMemory() + datasetMemory) / datasetMemory; 00243 cost.searchTimeCost = searchTime; 00244 cost.buildTimeCost = buildTime; 00245 Logger::info("KMeansTree buildTime=%g, searchTime=%g, build_weight=%g\n", buildTime, searchTime, build_weight_); 00246 } 00247 00248 00249 void evaluate_kdtree(CostData& cost) 00250 { 00251 StartStopTimer t; 00252 int checks; 00253 const int nn = 1; 00254 00255 Logger::info("KDTree using params: trees=%d\n", get_param<int>(cost.params,"trees")); 00256 KDTreeIndex<Distance> kdtree(sampledDataset_, cost.params, distance_); 00257 00258 t.start(); 00259 kdtree.buildIndex(); 00260 t.stop(); 00261 float buildTime = (float)t.value; 00262 00263 //measure search time 00264 float searchTime = test_index_precision(kdtree, sampledDataset_, testDataset_, gt_matches_, target_precision_, checks, distance_, nn); 00265 00266 float datasetMemory = float(sampledDataset_.rows * sampledDataset_.cols * sizeof(float)); 00267 cost.memoryCost = (kdtree.usedMemory() + datasetMemory) / datasetMemory; 00268 cost.searchTimeCost = searchTime; 00269 cost.buildTimeCost = buildTime; 00270 Logger::info("KDTree buildTime=%g, searchTime=%g\n", buildTime, searchTime); 00271 } 00272 00273 00274 // struct KMeansSimpleDownhillFunctor { 00275 // 00276 // Autotune& autotuner; 00277 // KMeansSimpleDownhillFunctor(Autotune& autotuner_) : autotuner(autotuner_) {} 00278 // 00279 // float operator()(int* params) { 00280 // 00281 // float maxFloat = numeric_limits<float>::max(); 00282 // 00283 // if (params[0]<2) return maxFloat; 00284 // if (params[1]<0) return maxFloat; 00285 // 00286 // CostData c; 00287 // c.params["algorithm"] = KMEANS; 00288 // c.params["centers-init"] = CENTERS_RANDOM; 00289 // c.params["branching"] = params[0]; 00290 // c.params["max-iterations"] = params[1]; 00291 // 00292 // autotuner.evaluate_kmeans(c); 00293 // 00294 // return c.timeCost; 00295 // 00296 // } 00297 // }; 00298 // 00299 // struct KDTreeSimpleDownhillFunctor { 00300 // 00301 // Autotune& autotuner; 00302 // KDTreeSimpleDownhillFunctor(Autotune& autotuner_) : autotuner(autotuner_) {} 00303 // 00304 // float operator()(int* params) { 00305 // float maxFloat = numeric_limits<float>::max(); 00306 // 00307 // if (params[0]<1) return maxFloat; 00308 // 00309 // CostData c; 00310 // c.params["algorithm"] = KDTREE; 00311 // c.params["trees"] = params[0]; 00312 // 00313 // autotuner.evaluate_kdtree(c); 00314 // 00315 // return c.timeCost; 00316 // 00317 // } 00318 // }; 00319 00320 00321 00322 void optimizeKMeans(std::vector<CostData>& costs) 00323 { 00324 Logger::info("KMEANS, Step 1: Exploring parameter space\n"); 00325 00326 // explore kmeans parameters space using combinations of the parameters below 00327 int maxIterations[] = { 1, 5, 10, 15 }; 00328 int branchingFactors[] = { 16, 32, 64, 128, 256 }; 00329 00330 int kmeansParamSpaceSize = FLANN_ARRAY_LEN(maxIterations) * FLANN_ARRAY_LEN(branchingFactors); 00331 costs.reserve(costs.size() + kmeansParamSpaceSize); 00332 00333 // evaluate kmeans for all parameter combinations 00334 for (size_t i = 0; i < FLANN_ARRAY_LEN(maxIterations); ++i) { 00335 for (size_t j = 0; j < FLANN_ARRAY_LEN(branchingFactors); ++j) { 00336 CostData cost; 00337 cost.params["algorithm"] = FLANN_INDEX_KMEANS; 00338 cost.params["centers_init"] = FLANN_CENTERS_RANDOM; 00339 cost.params["iterations"] = maxIterations[i]; 00340 cost.params["branching"] = branchingFactors[j]; 00341 00342 evaluate_kmeans(cost); 00343 costs.push_back(cost); 00344 } 00345 } 00346 00347 // Logger::info("KMEANS, Step 2: simplex-downhill optimization\n"); 00348 // 00349 // const int n = 2; 00350 // // choose initial simplex points as the best parameters so far 00351 // int kmeansNMPoints[n*(n+1)]; 00352 // float kmeansVals[n+1]; 00353 // for (int i=0;i<n+1;++i) { 00354 // kmeansNMPoints[i*n] = (int)kmeansCosts[i].params["branching"]; 00355 // kmeansNMPoints[i*n+1] = (int)kmeansCosts[i].params["max-iterations"]; 00356 // kmeansVals[i] = kmeansCosts[i].timeCost; 00357 // } 00358 // KMeansSimpleDownhillFunctor kmeans_cost_func(*this); 00359 // // run optimization 00360 // optimizeSimplexDownhill(kmeansNMPoints,n,kmeans_cost_func,kmeansVals); 00361 // // store results 00362 // for (int i=0;i<n+1;++i) { 00363 // kmeansCosts[i].params["branching"] = kmeansNMPoints[i*2]; 00364 // kmeansCosts[i].params["max-iterations"] = kmeansNMPoints[i*2+1]; 00365 // kmeansCosts[i].timeCost = kmeansVals[i]; 00366 // } 00367 } 00368 00369 00370 void optimizeKDTree(std::vector<CostData>& costs) 00371 { 00372 Logger::info("KD-TREE, Step 1: Exploring parameter space\n"); 00373 00374 // explore kd-tree parameters space using the parameters below 00375 int testTrees[] = { 1, 4, 8, 16, 32 }; 00376 00377 // evaluate kdtree for all parameter combinations 00378 for (size_t i = 0; i < FLANN_ARRAY_LEN(testTrees); ++i) { 00379 CostData cost; 00380 cost.params["algorithm"] = FLANN_INDEX_KDTREE; 00381 cost.params["trees"] = testTrees[i]; 00382 00383 evaluate_kdtree(cost); 00384 costs.push_back(cost); 00385 } 00386 00387 // Logger::info("KD-TREE, Step 2: simplex-downhill optimization\n"); 00388 // 00389 // const int n = 1; 00390 // // choose initial simplex points as the best parameters so far 00391 // int kdtreeNMPoints[n*(n+1)]; 00392 // float kdtreeVals[n+1]; 00393 // for (int i=0;i<n+1;++i) { 00394 // kdtreeNMPoints[i] = (int)kdtreeCosts[i].params["trees"]; 00395 // kdtreeVals[i] = kdtreeCosts[i].timeCost; 00396 // } 00397 // KDTreeSimpleDownhillFunctor kdtree_cost_func(*this); 00398 // // run optimization 00399 // optimizeSimplexDownhill(kdtreeNMPoints,n,kdtree_cost_func,kdtreeVals); 00400 // // store results 00401 // for (int i=0;i<n+1;++i) { 00402 // kdtreeCosts[i].params["trees"] = kdtreeNMPoints[i]; 00403 // kdtreeCosts[i].timeCost = kdtreeVals[i]; 00404 // } 00405 } 00406 00407 /** 00408 * Chooses the best nearest-neighbor algorithm and estimates the optimal 00409 * parameters to use when building the index (for a given precision). 00410 * Returns a dictionary with the optimal parameters. 00411 */ 00412 IndexParams estimateBuildParams() 00413 { 00414 std::vector<CostData> costs; 00415 00416 int sampleSize = int(sample_fraction_ * dataset_.rows); 00417 int testSampleSize = std::min(sampleSize / 10, 1000); 00418 00419 Logger::info("Entering autotuning, dataset size: %d, sampleSize: %d, testSampleSize: %d, target precision: %g\n", dataset_.rows, sampleSize, testSampleSize, target_precision_); 00420 00421 // For a very small dataset, it makes no sense to build any fancy index, just 00422 // use linear search 00423 if (testSampleSize < 10) { 00424 Logger::info("Choosing linear, dataset too small\n"); 00425 return LinearIndexParams(); 00426 } 00427 00428 // We use a fraction of the original dataset to speedup the autotune algorithm 00429 sampledDataset_ = random_sample(dataset_, sampleSize); 00430 // We use a cross-validation approach, first we sample a testset from the dataset 00431 testDataset_ = random_sample(sampledDataset_, testSampleSize, true); 00432 00433 // We compute the ground truth using linear search 00434 Logger::info("Computing ground truth... \n"); 00435 gt_matches_ = Matrix<int>(new int[testDataset_.rows], testDataset_.rows, 1); 00436 StartStopTimer t; 00437 t.start(); 00438 compute_ground_truth<Distance>(sampledDataset_, testDataset_, gt_matches_, 0, distance_); 00439 t.stop(); 00440 00441 CostData linear_cost; 00442 linear_cost.searchTimeCost = (float)t.value; 00443 linear_cost.buildTimeCost = 0; 00444 linear_cost.memoryCost = 0; 00445 linear_cost.params["algorithm"] = FLANN_INDEX_LINEAR; 00446 00447 costs.push_back(linear_cost); 00448 00449 // Start parameter autotune process 00450 Logger::info("Autotuning parameters...\n"); 00451 00452 optimizeKMeans(costs); 00453 optimizeKDTree(costs); 00454 00455 float bestTimeCost = costs[0].searchTimeCost; 00456 for (size_t i = 0; i < costs.size(); ++i) { 00457 float timeCost = costs[i].buildTimeCost * build_weight_ + costs[i].searchTimeCost; 00458 if (timeCost < bestTimeCost) { 00459 bestTimeCost = timeCost; 00460 } 00461 } 00462 00463 float bestCost = costs[0].searchTimeCost / bestTimeCost; 00464 IndexParams bestParams = costs[0].params; 00465 if (bestTimeCost > 0) { 00466 for (size_t i = 0; i < costs.size(); ++i) { 00467 float crtCost = (costs[i].buildTimeCost * build_weight_ + costs[i].searchTimeCost) / bestTimeCost + 00468 memory_weight_ * costs[i].memoryCost; 00469 if (crtCost < bestCost) { 00470 bestCost = crtCost; 00471 bestParams = costs[i].params; 00472 } 00473 } 00474 } 00475 00476 delete[] gt_matches_.data; 00477 delete[] testDataset_.data; 00478 delete[] sampledDataset_.data; 00479 00480 return bestParams; 00481 } 00482 00483 00484 00485 /** 00486 * Estimates the search time parameters needed to get the desired precision. 00487 * Precondition: the index is built 00488 * Postcondition: the searchParams will have the optimum params set, also the speedup obtained over linear search. 00489 */ 00490 float estimateSearchParams(SearchParams& searchParams) 00491 { 00492 const int nn = 1; 00493 const size_t SAMPLE_COUNT = 1000; 00494 00495 assert(bestIndex_ != NULL); // must have a valid index 00496 00497 float speedup = 0; 00498 00499 int samples = (int)std::min(dataset_.rows / 10, SAMPLE_COUNT); 00500 if (samples > 0) { 00501 Matrix<ElementType> testDataset = random_sample(dataset_, samples); 00502 00503 Logger::info("Computing ground truth\n"); 00504 00505 // we need to compute the ground truth first 00506 Matrix<int> gt_matches(new int[testDataset.rows], testDataset.rows, 1); 00507 StartStopTimer t; 00508 t.start(); 00509 compute_ground_truth<Distance>(dataset_, testDataset, gt_matches, 1, distance_); 00510 t.stop(); 00511 float linear = (float)t.value; 00512 00513 int checks; 00514 Logger::info("Estimating number of checks\n"); 00515 00516 float searchTime; 00517 float cb_index; 00518 if (bestIndex_->getType() == FLANN_INDEX_KMEANS) { 00519 Logger::info("KMeans algorithm, estimating cluster border factor\n"); 00520 KMeansIndex<Distance>* kmeans = (KMeansIndex<Distance>*)bestIndex_; 00521 float bestSearchTime = -1; 00522 float best_cb_index = -1; 00523 int best_checks = -1; 00524 for (cb_index = 0; cb_index < 1.1f; cb_index += 0.2f) { 00525 kmeans->set_cb_index(cb_index); 00526 searchTime = test_index_precision(*kmeans, dataset_, testDataset, gt_matches, target_precision_, checks, distance_, nn, 1); 00527 if ((searchTime < bestSearchTime) || (bestSearchTime == -1)) { 00528 bestSearchTime = searchTime; 00529 best_cb_index = cb_index; 00530 best_checks = checks; 00531 } 00532 } 00533 searchTime = bestSearchTime; 00534 cb_index = best_cb_index; 00535 checks = best_checks; 00536 00537 kmeans->set_cb_index(best_cb_index); 00538 Logger::info("Optimum cb_index: %g\n", cb_index); 00539 bestParams_["cb_index"] = cb_index; 00540 } 00541 else { 00542 searchTime = test_index_precision(*bestIndex_, dataset_, testDataset, gt_matches, target_precision_, checks, distance_, nn, 1); 00543 } 00544 00545 Logger::info("Required number of checks: %d \n", checks); 00546 searchParams["checks"] = checks; 00547 00548 speedup = linear / searchTime; 00549 00550 delete[] gt_matches.data; 00551 delete[] testDataset.data; 00552 } 00553 00554 return speedup; 00555 } 00556 00557 private: 00558 NNIndex<Distance>* bestIndex_; 00559 00560 IndexParams bestParams_; 00561 SearchParams bestSearchParams_; 00562 00563 Matrix<ElementType> sampledDataset_; 00564 Matrix<ElementType> testDataset_; 00565 Matrix<int> gt_matches_; 00566 00567 float speedup_; 00568 00569 /** 00570 * The dataset used by this index 00571 */ 00572 const Matrix<ElementType> dataset_; 00573 00574 /** 00575 * Index parameters 00576 */ 00577 float target_precision_; 00578 float build_weight_; 00579 float memory_weight_; 00580 float sample_fraction_; 00581 00582 Distance distance_; 00583 00584 00585 }; 00586 } 00587 00588 #endif /* OPENCV_FLANN_AUTOTUNED_INDEX_H_ */ 00589
Generated on Tue Jul 12 2022 16:42:37 by
1.7.2