From: <hug...@li...> - 2011-01-15 16:09:36
|
branch: details: http://hugin.hg.sourceforge.net/hgweb/hugin/hugin/hgrepo/h/hu/hugin/hugin/rev/0e4c4f8d21e9 changeset: 4829:0e4c4f8d21e9 user: Pablo d'Angelo <pab...@we...> date: Sat Jan 08 23:03:06 2011 +0100 description: merged in flann branch diffstat: src/foreign/CMakeLists.txt | 1 + src/foreign/flann/CMakeLists.txt | 36 + src/foreign/flann/README | 13 + src/foreign/flann/algorithms/all_indices.h | 80 + src/foreign/flann/algorithms/autotuned_index.h | 648 +++++++++++ src/foreign/flann/algorithms/composite_index.h | 190 +++ src/foreign/flann/algorithms/dist.h | 569 +++++++++ src/foreign/flann/algorithms/kdtree_index.h | 640 +++++++++++ src/foreign/flann/algorithms/kdtree_single_index.h | 549 +++++++++ src/foreign/flann/algorithms/kmeans_index.h | 1152 ++++++++++++++++++++ src/foreign/flann/algorithms/linear_index.h | 135 ++ src/foreign/flann/algorithms/nn_index.h | 108 + src/foreign/flann/flann.cpp | 768 +++++++++++++ src/foreign/flann/flann.h | 446 +++++++ src/foreign/flann/flann.hpp | 268 ++++ src/foreign/flann/flann_cpp.cpp | 89 + src/foreign/flann/flann_mpi.hpp | 262 ++++ src/foreign/flann/general.h | 173 +++ src/foreign/flann/io/hdf5.h | 201 +++ src/foreign/flann/nn/ground_truth.h | 97 + src/foreign/flann/nn/index_testing.cpp | 59 + src/foreign/flann/nn/index_testing.h | 307 +++++ src/foreign/flann/nn/simplex_downhill.h | 186 +++ src/foreign/flann/util/allocator.h | 188 +++ src/foreign/flann/util/heap.h | 210 +++ src/foreign/flann/util/logger.cpp | 84 + src/foreign/flann/util/logger.h | 89 + src/foreign/flann/util/matrix.h | 118 ++ src/foreign/flann/util/object_factory.h | 93 + src/foreign/flann/util/pair_iterator.hpp | 138 ++ src/foreign/flann/util/random.cpp | 53 + src/foreign/flann/util/random.h | 133 ++ src/foreign/flann/util/result_set.h | 198 +++ src/foreign/flann/util/sampling.h | 93 + src/foreign/flann/util/saving.cpp | 63 + src/foreign/flann/util/saving.h | 118 ++ src/foreign/flann/util/timer.h | 90 + src/hugin_base/panodata/Mask.h | 2 +- src/hugin_base/panodata/PanoramaOptions.h | 5 +- src/hugin_cpfind/cpfind/CMakeLists.txt | 4 +- src/hugin_cpfind/cpfind/PanoDetector.cpp | 10 +- src/hugin_cpfind/cpfind/PanoDetector.h | 11 +- src/hugin_cpfind/cpfind/PanoDetectorLogic.cpp | 59 +- 43 files changed, 8696 insertions(+), 40 deletions(-) Unterschiede (Ausschnitt von 9034 bis 500 Zeilen): diff -r b0337849acda -r 0e4c4f8d21e9 src/foreign/CMakeLists.txt --- a/src/foreign/CMakeLists.txt Sat Jan 08 23:02:01 2011 +0100 +++ b/src/foreign/CMakeLists.txt Sat Jan 08 23:03:06 2011 +0100 @@ -3,6 +3,7 @@ add_subdirectory(vigra) add_subdirectory(levmar) add_subdirectory(lensdb) +add_subdirectory(flann) add_subdirectory(zthread/src) IF (WIN32 AND NOT MINGW) diff -r b0337849acda -r 0e4c4f8d21e9 src/foreign/flann/CMakeLists.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/foreign/flann/CMakeLists.txt Sat Jan 08 23:03:06 2011 +0100 @@ -0,0 +1,36 @@ + +add_definitions(-D_FLANN_VERSION=1.6.6) + +file(GLOB_RECURSE C_SOURCES *.cpp) +file(GLOB_RECURSE CPP_SOURCES *.cpp) + +file(GLOB_RECURSE C_FLANN flann.cpp) +file(GLOB_RECURSE CPP_FLANN flann_cpp.cpp) + +list(REMOVE_ITEM CPP_SOURCES ${C_FLANN}) +list(REMOVE_ITEM C_SOURCES ${CPP_FLANN}) + +add_library(flann_cpp_s STATIC ${CPP_SOURCES}) +set_target_properties(flann_cpp_s PROPERTIES COMPILE_FLAGS -fPIC) + +if(CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_COMPILER_IS_GNUCC) + add_library(flann_cpp SHARED "") + target_link_libraries(flann_cpp -Wl,-whole-archive flann_cpp_s -Wl,-no-whole-archive) +else() + add_library(flann_cpp SHARED ${CPP_SOURCES}) +endif() + +set_target_properties(flann_cpp PROPERTIES + VERSION ${FLANN_VERSION} + SOVERSION ${FLANN_SOVERSION} +) + +IF(WIN32) + install(TARGETS flann_cpp flann_cpp_s RUNTIME DESTINATION ${BINDIR} ARCHIVE DESTINATION ${BINDIR} ) +ELSEIF(${HUGIN_LIBS_PRIVATE_DIR}) + install(TARGETS flann_cpp flann_cpp_s LIBRARY DESTINATION ${LIBDIR}/hugin NAMELINK_SKIP ARCHIVE DESTINATION ${LIBDIR}/hugin ) +ELSE(WIN32) + install(TARGETS flann_cpp flann_cpp_s LIBRARY DESTINATION ${LIBDIR} NAMELINK_SKIP ARCHIVE DESTINATION ${LIBDIR} ) +ENDIF(WIN32) + + diff -r b0337849acda -r 0e4c4f8d21e9 src/foreign/flann/README --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/foreign/flann/README Sat Jan 08 23:03:06 2011 +0100 @@ -0,0 +1,13 @@ +FLANN - Fast Library for Approximate Nearest neighbors +====================================================== + +This is a library for fast approximate nearest neighbor matching. +See the doc/manual.pdf file for information on how to use the library. + +This is a subset of flann 1.6.6, (src folder and slightly modified +CMakeLists.txt), as downloaded from +http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN + +Conditions of use +================= +FLANN is distributed under the terms of the BSD License. diff -r b0337849acda -r 0e4c4f8d21e9 src/foreign/flann/algorithms/all_indices.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/foreign/flann/algorithms/all_indices.h Sat Jan 08 23:03:06 2011 +0100 @@ -0,0 +1,80 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (ma...@cs...). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lo...@cs...). All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + *************************************************************************/ + + +#ifndef ALL_INDICES_H_ +#define ALL_INDICES_H_ + +#include "flann/general.h" + +#include "flann/algorithms/nn_index.h" +#include "flann/algorithms/kdtree_index.h" +#include "flann/algorithms/kdtree_single_index.h" +#include "flann/algorithms/kmeans_index.h" +#include "flann/algorithms/composite_index.h" +#include "flann/algorithms/linear_index.h" +#include "flann/algorithms/autotuned_index.h" + + +namespace flann { + +template<typename Distance> +NNIndex<Distance>* create_index_by_type(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance) +{ + flann_algorithm_t index_type = params.getIndexType(); + + NNIndex<Distance>* nnIndex; + switch (index_type) { + case LINEAR: + nnIndex = new LinearIndex<Distance>(dataset, (const LinearIndexParams&)params, distance); + break; + case KDTREE_SINGLE: + nnIndex = new KDTreeSingleIndex<Distance>(dataset, (const KDTreeSingleIndexParams&)params, distance); + break; + case KDTREE: + nnIndex = new KDTreeIndex<Distance>(dataset, (const KDTreeIndexParams&)params, distance); + break; + case KMEANS: + nnIndex = new KMeansIndex<Distance>(dataset, (const KMeansIndexParams&)params, distance); + break; + case COMPOSITE: + nnIndex = new CompositeIndex<Distance>(dataset, (const CompositeIndexParams&) params, distance); + break; + case AUTOTUNED: + nnIndex = new AutotunedIndex<Distance>(dataset, (const AutotunedIndexParams&) params, distance); + break; + default: + throw FLANNException("Unknown index type"); + } + + return nnIndex; +} + +} + +#endif /* ALL_INDICES_H_ */ diff -r b0337849acda -r 0e4c4f8d21e9 src/foreign/flann/algorithms/autotuned_index.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/foreign/flann/algorithms/autotuned_index.h Sat Jan 08 23:03:06 2011 +0100 @@ -0,0 +1,648 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (ma...@cs...). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lo...@cs...). All rights reserved. + * + * THE BSD LICENSE + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + *************************************************************************/ +#ifndef AUTOTUNEDINDEX_H_ +#define AUTOTUNEDINDEX_H_ + +#include "flann/general.h" +#include "flann/algorithms/nn_index.h" +#include "flann/nn/ground_truth.h" +#include "flann/nn/index_testing.h" +#include "flann/util/sampling.h" +#include "flann/algorithms/kdtree_index.h" +#include "flann/algorithms/kdtree_single_index.h" +#include "flann/algorithms/kmeans_index.h" +#include "flann/algorithms/composite_index.h" +#include "flann/algorithms/linear_index.h" + +namespace flann +{ + + +template<typename Distance> + NNIndex<Distance>* index_by_type(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance) + { + flann_algorithm_t index_type = params.getIndexType(); + + NNIndex<Distance>* nnIndex; + switch (index_type) { + case LINEAR: + nnIndex = new LinearIndex<Distance>(dataset, (const LinearIndexParams&)params, distance); + break; + case KDTREE_SINGLE: + nnIndex = new KDTreeSingleIndex<Distance>(dataset, (const KDTreeSingleIndexParams&)params, distance); + break; + case KDTREE: + nnIndex = new KDTreeIndex<Distance>(dataset, (const KDTreeIndexParams&)params, distance); + break; + case KMEANS: + nnIndex = new KMeansIndex<Distance>(dataset, (const KMeansIndexParams&)params, distance); + break; + case COMPOSITE: + nnIndex = new CompositeIndex<Distance>(dataset, (const CompositeIndexParams&) params, distance); + break; + default: + printf("Index type: %d\n", (int)index_type); + throw FLANNException("Unknown index type"); + } + + return nnIndex; + } + + +struct AutotunedIndexParams : public IndexParams { + AutotunedIndexParams( float target_precision_ = 0.8, float build_weight_ = 0.01, + float memory_weight_ = 0, float sample_fraction_ = 0.1) : + IndexParams(AUTOTUNED), + target_precision(target_precision_), + build_weight(build_weight_), + memory_weight(memory_weight_), + sample_fraction(sample_fraction_) {}; + + float target_precision; // precision desired (used for autotuning, -1 otherwise) + float build_weight; // build tree time weighting factor + float memory_weight; // index memory weighting factor + float sample_fraction; // what fraction of the dataset to use for autotuning + + void fromParameters(const FLANNParameters& p) + { + assert(p.algorithm==algorithm); + target_precision = p.target_precision; + build_weight = p.build_weight; + memory_weight = p.memory_weight; + sample_fraction = p.sample_fraction; + } + + void toParameters(FLANNParameters& p) const + { + p.algorithm = algorithm; + p.target_precision = target_precision; + p.build_weight = build_weight; + p.memory_weight = memory_weight; + p.sample_fraction = sample_fraction; + } + + void print() const + { + logger.info("Index type: %d\n",(int)algorithm); + logger.info("Target precision: %g\n", target_precision); + logger.info("Build weight: %g\n", build_weight); + logger.info("Memory weight: %g\n", memory_weight); + logger.info("Sample fraction: %g\n", sample_fraction); + } +}; + + +template <typename Distance> +class AutotunedIndex : public NNIndex<Distance> +{ + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + NNIndex<Distance>* bestIndex; + + IndexParams* bestParams; + SearchParams bestSearchParams; + + Matrix<ElementType> sampledDataset; + Matrix<ElementType> testDataset; + Matrix<int> gt_matches; + + float speedup; + + /** + * The dataset used by this index + */ + const Matrix<ElementType> dataset; + + /** + * Index parameters + */ + const AutotunedIndexParams& index_params; + + Distance distance; +public: + + AutotunedIndex(const Matrix<ElementType>& inputData, const AutotunedIndexParams& params = AutotunedIndexParams(), + Distance d = Distance()) : + dataset(inputData), index_params(params), distance(d) + { + bestIndex = NULL; + bestParams = NULL; + } + + virtual ~AutotunedIndex() + { + if (bestIndex!=NULL) { + delete bestIndex; + } + if (bestParams!=NULL) { + delete bestParams; + } + }; + + /** + Method responsible with building the index. + */ + virtual void buildIndex() + { + bestParams = estimateBuildParams(); + logger.info("----------------------------------------------------\n"); + logger.info("Autotuned parameters:\n"); + bestParams->print(); + logger.info("----------------------------------------------------\n"); + flann_algorithm_t index_type = bestParams->getIndexType(); + switch (index_type) { + case LINEAR: + bestIndex = new LinearIndex<Distance>(dataset, (const LinearIndexParams&)*bestParams, distance); + break; + case KDTREE: + bestIndex = new KDTreeIndex<Distance>(dataset, (const KDTreeIndexParams&)*bestParams, distance); + break; + case KMEANS: + bestIndex = new KMeansIndex<Distance>(dataset, (const KMeansIndexParams&)*bestParams, distance); + break; + default: + throw FLANNException("Unknown algorithm chosen by the autotuning, most likely a bug."); + } + bestIndex->buildIndex(); + speedup = estimateSearchParams(bestSearchParams); + } + + /** + Saves the index to a stream + */ + virtual void saveIndex(FILE* stream) + { + save_value(stream, (int)bestIndex->getType()); + bestIndex->saveIndex(stream); + save_value(stream, bestSearchParams); + } + + /** + Loads the index from a stream + */ + virtual void loadIndex(FILE* stream) + { + int index_type; + load_value(stream,index_type); + IndexParams* params = ParamsFactory::instance().create((flann_algorithm_t)index_type); + bestIndex = index_by_type<Distance>(dataset, *params, distance); + bestIndex->loadIndex(stream); + load_value(stream, bestSearchParams); + } + + /** + Method that searches for nearest-neighbors + */ + virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + if (searchParams.checks==CHECKS_AUTOTUNED) { + bestIndex->findNeighbors(result, vec, bestSearchParams); + } + else { + bestIndex->findNeighbors(result, vec, searchParams); + } + } + + + const IndexParams* getParameters() const + { + return bestIndex->getParameters(); + } + + const SearchParams* getSearchParameters() const + { + return &bestSearchParams; + } + + float getSpeedup() const + { + return speedup; + } + + + /** + Number of features in this index. + */ + virtual size_t size() const + { + return bestIndex->size(); + } + + /** + The length of each vector in this index. + */ + virtual size_t veclen() const + { + return bestIndex->veclen(); + } + + /** + The amount of memory (in bytes) this index uses. + */ + virtual int usedMemory() const + { + return bestIndex->usedMemory(); + } + + /** + * Algorithm name + */ + virtual flann_algorithm_t getType() const + { + return AUTOTUNED; + } + +private: + + struct CostData { + float searchTimeCost; + float buildTimeCost; + float memoryCost; + float totalCost; + IndexParams* params; + }; + + typedef std::pair<CostData, KDTreeIndexParams> KDTreeCostData; + typedef std::pair<CostData, KMeansIndexParams> KMeansCostData; + + + void evaluate_kmeans(CostData& cost) + { + StartStopTimer t; + int checks; + const int nn = 1; + + KMeansIndexParams* kmeans_params = (KMeansIndexParams*)cost.params; + + logger.info("KMeansTree using params: max_iterations=%d, branching=%d\n", kmeans_params->iterations, kmeans_params->branching); + KMeansIndex<Distance> kmeans(sampledDataset, *kmeans_params, distance); + // measure index build time + t.start(); + kmeans.buildIndex(); + t.stop(); + float buildTime = t.value; + + // measure search time + float searchTime = test_index_precision(kmeans, sampledDataset, testDataset, gt_matches, index_params.target_precision, checks, distance, nn); + + float datasetMemory = sampledDataset.rows*sampledDataset.cols*sizeof(float); + cost.memoryCost = (kmeans.usedMemory()+datasetMemory)/datasetMemory; + cost.searchTimeCost = searchTime; + cost.buildTimeCost = buildTime; + logger.info("KMeansTree buildTime=%g, searchTime=%g, buildTimeFactor=%g\n",buildTime, searchTime, index_params.build_weight); + } + + + void evaluate_kdtree(CostData& cost) + { + StartStopTimer t; + int checks; + const int nn = 1; + + KDTreeIndexParams* kdtree_params = (KDTreeIndexParams*)cost.params; + + logger.info("KDTree using params: trees=%d\n",kdtree_params->trees); + KDTreeIndex<Distance> kdtree(sampledDataset, *kdtree_params, distance); + + t.start(); + kdtree.buildIndex(); + t.stop(); + float buildTime = t.value; + + //measure search time + float searchTime = test_index_precision(kdtree, sampledDataset, testDataset, gt_matches, index_params.target_precision, checks, distance, nn); + + float datasetMemory = sampledDataset.rows*sampledDataset.cols*sizeof(float); + cost.memoryCost = (kdtree.usedMemory()+datasetMemory)/datasetMemory; |