diff options
Diffstat (limited to 'thirdparty/linux/include/opencv2/flann')
36 files changed, 10225 insertions, 0 deletions
diff --git a/thirdparty/linux/include/opencv2/flann/all_indices.h b/thirdparty/linux/include/opencv2/flann/all_indices.h new file mode 100644 index 0000000..ff53fd8 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/all_indices.h @@ -0,0 +1,155 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_ALL_INDICES_H_ +#define OPENCV_FLANN_ALL_INDICES_H_ + +#include "general.h" + +#include "nn_index.h" +#include "kdtree_index.h" +#include "kdtree_single_index.h" +#include "kmeans_index.h" +#include "composite_index.h" +#include "linear_index.h" +#include "hierarchical_clustering_index.h" +#include "lsh_index.h" +#include "autotuned_index.h" + + +namespace cvflann +{ + +template<typename KDTreeCapability, typename VectorSpace, typename Distance> +struct index_creator +{ + static NNIndex<Distance>* create(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance) + { + flann_algorithm_t index_type = get_param<flann_algorithm_t>(params, "algorithm"); + + NNIndex<Distance>* nnIndex; + switch (index_type) { + case FLANN_INDEX_LINEAR: + nnIndex = new LinearIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_KDTREE_SINGLE: + nnIndex = new KDTreeSingleIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_KDTREE: + nnIndex = new KDTreeIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_KMEANS: + nnIndex = new KMeansIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_COMPOSITE: + nnIndex = new CompositeIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_AUTOTUNED: + nnIndex = new AutotunedIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_HIERARCHICAL: + nnIndex = new HierarchicalClusteringIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_LSH: + nnIndex = new LshIndex<Distance>(dataset, params, distance); + break; + default: + throw FLANNException("Unknown index type"); + } + + return nnIndex; + } +}; + +template<typename VectorSpace, typename Distance> +struct index_creator<False,VectorSpace,Distance> +{ + static NNIndex<Distance>* create(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance) + { + flann_algorithm_t index_type = get_param<flann_algorithm_t>(params, "algorithm"); + + NNIndex<Distance>* nnIndex; + switch (index_type) { + case FLANN_INDEX_LINEAR: + nnIndex = new LinearIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_KMEANS: + nnIndex = new KMeansIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_HIERARCHICAL: + nnIndex = new HierarchicalClusteringIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_LSH: + nnIndex = new LshIndex<Distance>(dataset, params, distance); + break; + default: + throw FLANNException("Unknown index type"); + } + + return nnIndex; + } +}; + +template<typename Distance> +struct index_creator<False,False,Distance> +{ + static NNIndex<Distance>* create(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance) + { + flann_algorithm_t index_type = get_param<flann_algorithm_t>(params, "algorithm"); + + NNIndex<Distance>* nnIndex; + switch (index_type) { + case FLANN_INDEX_LINEAR: + nnIndex = new LinearIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_HIERARCHICAL: + nnIndex = new HierarchicalClusteringIndex<Distance>(dataset, params, distance); + break; + case FLANN_INDEX_LSH: + nnIndex = new LshIndex<Distance>(dataset, params, distance); + break; + default: + throw FLANNException("Unknown index type"); + } + + return nnIndex; + } +}; + +template<typename Distance> +NNIndex<Distance>* create_index_by_type(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance) +{ + return index_creator<typename Distance::is_kdtree_distance, + typename Distance::is_vector_space_distance, + Distance>::create(dataset, params,distance); +} + +} + +#endif /* OPENCV_FLANN_ALL_INDICES_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/allocator.h b/thirdparty/linux/include/opencv2/flann/allocator.h new file mode 100644 index 0000000..26091d0 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/allocator.h @@ -0,0 +1,188 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_ALLOCATOR_H_ +#define OPENCV_FLANN_ALLOCATOR_H_ + +#include <stdlib.h> +#include <stdio.h> + + +namespace cvflann +{ + +/** + * Allocates (using C's malloc) a generic type T. + * + * Params: + * count = number of instances to allocate. + * Returns: pointer (of type T*) to memory buffer + */ +template <typename T> +T* allocate(size_t count = 1) +{ + T* mem = (T*) ::malloc(sizeof(T)*count); + return mem; +} + + +/** + * Pooled storage allocator + * + * The following routines allow for the efficient allocation of storage in + * small chunks from a specified pool. Rather than allowing each structure + * to be freed individually, an entire pool of storage is freed at once. + * This method has two advantages over just using malloc() and free(). First, + * it is far more efficient for allocating small objects, as there is + * no overhead for remembering all the information needed to free each + * object or consolidating fragmented memory. Second, the decision about + * how long to keep an object is made at the time of allocation, and there + * is no need to track down all the objects to free them. + * + */ + +const size_t WORDSIZE=16; +const size_t BLOCKSIZE=8192; + +class PooledAllocator +{ + /* We maintain memory alignment to word boundaries by requiring that all + allocations be in multiples of the machine wordsize. */ + /* Size of machine word in bytes. Must be power of 2. */ + /* Minimum number of bytes requested at a time from the system. Must be multiple of WORDSIZE. */ + + + int remaining; /* Number of bytes left in current block of storage. */ + void* base; /* Pointer to base of current block of storage. */ + void* loc; /* Current location in block to next allocate memory. */ + int blocksize; + + +public: + int usedMemory; + int wastedMemory; + + /** + Default constructor. Initializes a new pool. + */ + PooledAllocator(int blockSize = BLOCKSIZE) + { + blocksize = blockSize; + remaining = 0; + base = NULL; + + usedMemory = 0; + wastedMemory = 0; + } + + /** + * Destructor. Frees all the memory allocated in this pool. + */ + ~PooledAllocator() + { + void* prev; + + while (base != NULL) { + prev = *((void**) base); /* Get pointer to prev block. */ + ::free(base); + base = prev; + } + } + + /** + * Returns a pointer to a piece of new memory of the given size in bytes + * allocated from the pool. + */ + void* allocateMemory(int size) + { + int blockSize; + + /* Round size up to a multiple of wordsize. The following expression + only works for WORDSIZE that is a power of 2, by masking last bits of + incremented size to zero. + */ + size = (size + (WORDSIZE - 1)) & ~(WORDSIZE - 1); + + /* Check whether a new block must be allocated. Note that the first word + of a block is reserved for a pointer to the previous block. + */ + if (size > remaining) { + + wastedMemory += remaining; + + /* Allocate new storage. */ + blockSize = (size + sizeof(void*) + (WORDSIZE-1) > BLOCKSIZE) ? + size + sizeof(void*) + (WORDSIZE-1) : BLOCKSIZE; + + // use the standard C malloc to allocate memory + void* m = ::malloc(blockSize); + if (!m) { + fprintf(stderr,"Failed to allocate memory.\n"); + return NULL; + } + + /* Fill first word of new block with pointer to previous block. */ + ((void**) m)[0] = base; + base = m; + + int shift = 0; + //int shift = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1); + + remaining = blockSize - sizeof(void*) - shift; + loc = ((char*)m + sizeof(void*) + shift); + } + void* rloc = loc; + loc = (char*)loc + size; + remaining -= size; + + usedMemory += size; + + return rloc; + } + + /** + * Allocates (using this pool) a generic type T. + * + * Params: + * count = number of instances to allocate. + * Returns: pointer (of type T*) to memory buffer + */ + template <typename T> + T* allocate(size_t count = 1) + { + T* mem = (T*) this->allocateMemory((int)(sizeof(T)*count)); + return mem; + } + +}; + +} + +#endif //OPENCV_FLANN_ALLOCATOR_H_ diff --git a/thirdparty/linux/include/opencv2/flann/any.h b/thirdparty/linux/include/opencv2/flann/any.h new file mode 100644 index 0000000..bfe06c8 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/any.h @@ -0,0 +1,324 @@ +#ifndef OPENCV_FLANN_ANY_H_ +#define OPENCV_FLANN_ANY_H_ +/* + * (C) Copyright Christopher Diggins 2005-2011 + * (C) Copyright Pablo Aguilar 2005 + * (C) Copyright Kevlin Henney 2001 + * + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt + * + * Adapted for FLANN by Marius Muja + */ + +#include "defines.h" +#include <stdexcept> +#include <ostream> +#include <typeinfo> + +namespace cvflann +{ + +namespace anyimpl +{ + +struct bad_any_cast +{ +}; + +struct empty_any +{ +}; + +inline std::ostream& operator <<(std::ostream& out, const empty_any&) +{ + out << "[empty_any]"; + return out; +} + +struct base_any_policy +{ + virtual void static_delete(void** x) = 0; + virtual void copy_from_value(void const* src, void** dest) = 0; + virtual void clone(void* const* src, void** dest) = 0; + virtual void move(void* const* src, void** dest) = 0; + virtual void* get_value(void** src) = 0; + virtual const void* get_value(void* const * src) = 0; + virtual ::size_t get_size() = 0; + virtual const std::type_info& type() = 0; + virtual void print(std::ostream& out, void* const* src) = 0; + virtual ~base_any_policy() {} +}; + +template<typename T> +struct typed_base_any_policy : base_any_policy +{ + virtual ::size_t get_size() { return sizeof(T); } + virtual const std::type_info& type() { return typeid(T); } + +}; + +template<typename T> +struct small_any_policy : typed_base_any_policy<T> +{ + virtual void static_delete(void**) { } + virtual void copy_from_value(void const* src, void** dest) + { + new (dest) T(* reinterpret_cast<T const*>(src)); + } + virtual void clone(void* const* src, void** dest) { *dest = *src; } + virtual void move(void* const* src, void** dest) { *dest = *src; } + virtual void* get_value(void** src) { return reinterpret_cast<void*>(src); } + virtual const void* get_value(void* const * src) { return reinterpret_cast<const void*>(src); } + virtual void print(std::ostream& out, void* const* src) { out << *reinterpret_cast<T const*>(src); } +}; + +template<typename T> +struct big_any_policy : typed_base_any_policy<T> +{ + virtual void static_delete(void** x) + { + if (* x) delete (* reinterpret_cast<T**>(x)); + *x = NULL; + } + virtual void copy_from_value(void const* src, void** dest) + { + *dest = new T(*reinterpret_cast<T const*>(src)); + } + virtual void clone(void* const* src, void** dest) + { + *dest = new T(**reinterpret_cast<T* const*>(src)); + } + virtual void move(void* const* src, void** dest) + { + (*reinterpret_cast<T**>(dest))->~T(); + **reinterpret_cast<T**>(dest) = **reinterpret_cast<T* const*>(src); + } + virtual void* get_value(void** src) { return *src; } + virtual const void* get_value(void* const * src) { return *src; } + virtual void print(std::ostream& out, void* const* src) { out << *reinterpret_cast<T const*>(*src); } +}; + +template<> inline void big_any_policy<flann_centers_init_t>::print(std::ostream& out, void* const* src) +{ + out << int(*reinterpret_cast<flann_centers_init_t const*>(*src)); +} + +template<> inline void big_any_policy<flann_algorithm_t>::print(std::ostream& out, void* const* src) +{ + out << int(*reinterpret_cast<flann_algorithm_t const*>(*src)); +} + +template<> inline void big_any_policy<cv::String>::print(std::ostream& out, void* const* src) +{ + out << (*reinterpret_cast<cv::String const*>(*src)).c_str(); +} + +template<typename T> +struct choose_policy +{ + typedef big_any_policy<T> type; +}; + +template<typename T> +struct choose_policy<T*> +{ + typedef small_any_policy<T*> type; +}; + +struct any; + +/// Choosing the policy for an any type is illegal, but should never happen. +/// This is designed to throw a compiler error. +template<> +struct choose_policy<any> +{ + typedef void type; +}; + +/// Specializations for small types. +#define SMALL_POLICY(TYPE) \ + template<> \ + struct choose_policy<TYPE> { typedef small_any_policy<TYPE> type; \ + } + +SMALL_POLICY(signed char); +SMALL_POLICY(unsigned char); +SMALL_POLICY(signed short); +SMALL_POLICY(unsigned short); +SMALL_POLICY(signed int); +SMALL_POLICY(unsigned int); +SMALL_POLICY(signed long); +SMALL_POLICY(unsigned long); +SMALL_POLICY(float); +SMALL_POLICY(bool); + +#undef SMALL_POLICY + +template <typename T> +class SinglePolicy +{ + SinglePolicy(); + SinglePolicy(const SinglePolicy& other); + SinglePolicy& operator=(const SinglePolicy& other); + +public: + static base_any_policy* get_policy(); + +private: + static typename choose_policy<T>::type policy; +}; + +template <typename T> +typename choose_policy<T>::type SinglePolicy<T>::policy; + +/// This function will return a different policy for each type. +template <typename T> +inline base_any_policy* SinglePolicy<T>::get_policy() { return &policy; } + +} // namespace anyimpl + +struct any +{ +private: + // fields + anyimpl::base_any_policy* policy; + void* object; + +public: + /// Initializing constructor. + template <typename T> + any(const T& x) + : policy(anyimpl::SinglePolicy<anyimpl::empty_any>::get_policy()), object(NULL) + { + assign(x); + } + + /// Empty constructor. + any() + : policy(anyimpl::SinglePolicy<anyimpl::empty_any>::get_policy()), object(NULL) + { } + + /// Special initializing constructor for string literals. + any(const char* x) + : policy(anyimpl::SinglePolicy<anyimpl::empty_any>::get_policy()), object(NULL) + { + assign(x); + } + + /// Copy constructor. + any(const any& x) + : policy(anyimpl::SinglePolicy<anyimpl::empty_any>::get_policy()), object(NULL) + { + assign(x); + } + + /// Destructor. + ~any() + { + policy->static_delete(&object); + } + + /// Assignment function from another any. + any& assign(const any& x) + { + reset(); + policy = x.policy; + policy->clone(&x.object, &object); + return *this; + } + + /// Assignment function. + template <typename T> + any& assign(const T& x) + { + reset(); + policy = anyimpl::SinglePolicy<T>::get_policy(); + policy->copy_from_value(&x, &object); + return *this; + } + + /// Assignment operator. + template<typename T> + any& operator=(const T& x) + { + return assign(x); + } + + /// Assignment operator, specialed for literal strings. + /// They have types like const char [6] which don't work as expected. + any& operator=(const char* x) + { + return assign(x); + } + + /// Utility functions + any& swap(any& x) + { + std::swap(policy, x.policy); + std::swap(object, x.object); + return *this; + } + + /// Cast operator. You can only cast to the original type. + template<typename T> + T& cast() + { + if (policy->type() != typeid(T)) throw anyimpl::bad_any_cast(); + T* r = reinterpret_cast<T*>(policy->get_value(&object)); + return *r; + } + + /// Cast operator. You can only cast to the original type. + template<typename T> + const T& cast() const + { + if (policy->type() != typeid(T)) throw anyimpl::bad_any_cast(); + const T* r = reinterpret_cast<const T*>(policy->get_value(&object)); + return *r; + } + + /// Returns true if the any contains no value. + bool empty() const + { + return policy->type() == typeid(anyimpl::empty_any); + } + + /// Frees any allocated memory, and sets the value to NULL. + void reset() + { + policy->static_delete(&object); + policy = anyimpl::SinglePolicy<anyimpl::empty_any>::get_policy(); + } + + /// Returns true if the two types are the same. + bool compatible(const any& x) const + { + return policy->type() == x.policy->type(); + } + + /// Returns if the type is compatible with the policy + template<typename T> + bool has_type() + { + return policy->type() == typeid(T); + } + + const std::type_info& type() const + { + return policy->type(); + } + + friend std::ostream& operator <<(std::ostream& out, const any& any_val); +}; + +inline std::ostream& operator <<(std::ostream& out, const any& any_val) +{ + any_val.policy->print(out,&any_val.object); + return out; +} + +} + +#endif // OPENCV_FLANN_ANY_H_ diff --git a/thirdparty/linux/include/opencv2/flann/autotuned_index.h b/thirdparty/linux/include/opencv2/flann/autotuned_index.h new file mode 100644 index 0000000..6ffb929 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/autotuned_index.h @@ -0,0 +1,588 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_AUTOTUNED_INDEX_H_ +#define OPENCV_FLANN_AUTOTUNED_INDEX_H_ + +#include "general.h" +#include "nn_index.h" +#include "ground_truth.h" +#include "index_testing.h" +#include "sampling.h" +#include "kdtree_index.h" +#include "kdtree_single_index.h" +#include "kmeans_index.h" +#include "composite_index.h" +#include "linear_index.h" +#include "logger.h" + +namespace cvflann +{ + +template<typename Distance> +NNIndex<Distance>* create_index_by_type(const Matrix<typename Distance::ElementType>& dataset, const IndexParams& params, const Distance& distance); + + +struct AutotunedIndexParams : public IndexParams +{ + AutotunedIndexParams(float target_precision = 0.8, float build_weight = 0.01, float memory_weight = 0, float sample_fraction = 0.1) + { + (*this)["algorithm"] = FLANN_INDEX_AUTOTUNED; + // precision desired (used for autotuning, -1 otherwise) + (*this)["target_precision"] = target_precision; + // build tree time weighting factor + (*this)["build_weight"] = build_weight; + // index memory weighting factor + (*this)["memory_weight"] = memory_weight; + // what fraction of the dataset to use for autotuning + (*this)["sample_fraction"] = sample_fraction; + } +}; + + +template <typename Distance> +class AutotunedIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + AutotunedIndex(const Matrix<ElementType>& inputData, const IndexParams& params = AutotunedIndexParams(), Distance d = Distance()) : + dataset_(inputData), distance_(d) + { + target_precision_ = get_param(params, "target_precision",0.8f); + build_weight_ = get_param(params,"build_weight", 0.01f); + memory_weight_ = get_param(params, "memory_weight", 0.0f); + sample_fraction_ = get_param(params,"sample_fraction", 0.1f); + bestIndex_ = NULL; + } + + AutotunedIndex(const AutotunedIndex&); + AutotunedIndex& operator=(const AutotunedIndex&); + + virtual ~AutotunedIndex() + { + if (bestIndex_ != NULL) { + delete bestIndex_; + bestIndex_ = NULL; + } + } + + /** + * Method responsible with building the index. + */ + virtual void buildIndex() + { + std::ostringstream stream; + bestParams_ = estimateBuildParams(); + print_params(bestParams_, stream); + Logger::info("----------------------------------------------------\n"); + Logger::info("Autotuned parameters:\n"); + Logger::info("%s", stream.str().c_str()); + Logger::info("----------------------------------------------------\n"); + + bestIndex_ = create_index_by_type(dataset_, bestParams_, distance_); + bestIndex_->buildIndex(); + speedup_ = estimateSearchParams(bestSearchParams_); + stream.str(std::string()); + print_params(bestSearchParams_, stream); + Logger::info("----------------------------------------------------\n"); + Logger::info("Search parameters:\n"); + Logger::info("%s", stream.str().c_str()); + Logger::info("----------------------------------------------------\n"); + } + + /** + * Saves the index to a stream + */ + virtual void saveIndex(FILE* stream) + { + save_value(stream, (int)bestIndex_->getType()); + bestIndex_->saveIndex(stream); + save_value(stream, get_param<int>(bestSearchParams_, "checks")); + } + + /** + * Loads the index from a stream + */ + virtual void loadIndex(FILE* stream) + { + int index_type; + + load_value(stream, index_type); + IndexParams params; + params["algorithm"] = (flann_algorithm_t)index_type; + bestIndex_ = create_index_by_type<Distance>(dataset_, params, distance_); + bestIndex_->loadIndex(stream); + int checks; + load_value(stream, checks); + bestSearchParams_["checks"] = checks; + } + + /** + * Method that searches for nearest-neighbors + */ + virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + int checks = get_param<int>(searchParams,"checks",FLANN_CHECKS_AUTOTUNED); + if (checks == FLANN_CHECKS_AUTOTUNED) { + bestIndex_->findNeighbors(result, vec, bestSearchParams_); + } + else { + bestIndex_->findNeighbors(result, vec, searchParams); + } + } + + + IndexParams getParameters() const + { + return bestIndex_->getParameters(); + } + + 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 FLANN_INDEX_AUTOTUNED; + } + +private: + + struct CostData + { + float searchTimeCost; + float buildTimeCost; + float memoryCost; + float totalCost; + IndexParams params; + }; + + void evaluate_kmeans(CostData& cost) + { + StartStopTimer t; + int checks; + const int nn = 1; + + Logger::info("KMeansTree using params: max_iterations=%d, branching=%d\n", + get_param<int>(cost.params,"iterations"), + get_param<int>(cost.params,"branching")); + KMeansIndex<Distance> kmeans(sampledDataset_, cost.params, distance_); + // measure index build time + t.start(); + kmeans.buildIndex(); + t.stop(); + float buildTime = (float)t.value; + + // measure search time + float searchTime = test_index_precision(kmeans, sampledDataset_, testDataset_, gt_matches_, target_precision_, checks, distance_, nn); + + float datasetMemory = float(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, build_weight=%g\n", buildTime, searchTime, build_weight_); + } + + + void evaluate_kdtree(CostData& cost) + { + StartStopTimer t; + int checks; + const int nn = 1; + + Logger::info("KDTree using params: trees=%d\n", get_param<int>(cost.params,"trees")); + KDTreeIndex<Distance> kdtree(sampledDataset_, cost.params, distance_); + + t.start(); + kdtree.buildIndex(); + t.stop(); + float buildTime = (float)t.value; + + //measure search time + float searchTime = test_index_precision(kdtree, sampledDataset_, testDataset_, gt_matches_, target_precision_, checks, distance_, nn); + + float datasetMemory = float(sampledDataset_.rows * sampledDataset_.cols * sizeof(float)); + cost.memoryCost = (kdtree.usedMemory() + datasetMemory) / datasetMemory; + cost.searchTimeCost = searchTime; + cost.buildTimeCost = buildTime; + Logger::info("KDTree buildTime=%g, searchTime=%g\n", buildTime, searchTime); + } + + + // struct KMeansSimpleDownhillFunctor { + // + // Autotune& autotuner; + // KMeansSimpleDownhillFunctor(Autotune& autotuner_) : autotuner(autotuner_) {} + // + // float operator()(int* params) { + // + // float maxFloat = numeric_limits<float>::max(); + // + // if (params[0]<2) return maxFloat; + // if (params[1]<0) return maxFloat; + // + // CostData c; + // c.params["algorithm"] = KMEANS; + // c.params["centers-init"] = CENTERS_RANDOM; + // c.params["branching"] = params[0]; + // c.params["max-iterations"] = params[1]; + // + // autotuner.evaluate_kmeans(c); + // + // return c.timeCost; + // + // } + // }; + // + // struct KDTreeSimpleDownhillFunctor { + // + // Autotune& autotuner; + // KDTreeSimpleDownhillFunctor(Autotune& autotuner_) : autotuner(autotuner_) {} + // + // float operator()(int* params) { + // float maxFloat = numeric_limits<float>::max(); + // + // if (params[0]<1) return maxFloat; + // + // CostData c; + // c.params["algorithm"] = KDTREE; + // c.params["trees"] = params[0]; + // + // autotuner.evaluate_kdtree(c); + // + // return c.timeCost; + // + // } + // }; + + + + void optimizeKMeans(std::vector<CostData>& costs) + { + Logger::info("KMEANS, Step 1: Exploring parameter space\n"); + + // explore kmeans parameters space using combinations of the parameters below + int maxIterations[] = { 1, 5, 10, 15 }; + int branchingFactors[] = { 16, 32, 64, 128, 256 }; + + int kmeansParamSpaceSize = FLANN_ARRAY_LEN(maxIterations) * FLANN_ARRAY_LEN(branchingFactors); + costs.reserve(costs.size() + kmeansParamSpaceSize); + + // evaluate kmeans for all parameter combinations + for (size_t i = 0; i < FLANN_ARRAY_LEN(maxIterations); ++i) { + for (size_t j = 0; j < FLANN_ARRAY_LEN(branchingFactors); ++j) { + CostData cost; + cost.params["algorithm"] = FLANN_INDEX_KMEANS; + cost.params["centers_init"] = FLANN_CENTERS_RANDOM; + cost.params["iterations"] = maxIterations[i]; + cost.params["branching"] = branchingFactors[j]; + + evaluate_kmeans(cost); + costs.push_back(cost); + } + } + + // Logger::info("KMEANS, Step 2: simplex-downhill optimization\n"); + // + // const int n = 2; + // // choose initial simplex points as the best parameters so far + // int kmeansNMPoints[n*(n+1)]; + // float kmeansVals[n+1]; + // for (int i=0;i<n+1;++i) { + // kmeansNMPoints[i*n] = (int)kmeansCosts[i].params["branching"]; + // kmeansNMPoints[i*n+1] = (int)kmeansCosts[i].params["max-iterations"]; + // kmeansVals[i] = kmeansCosts[i].timeCost; + // } + // KMeansSimpleDownhillFunctor kmeans_cost_func(*this); + // // run optimization + // optimizeSimplexDownhill(kmeansNMPoints,n,kmeans_cost_func,kmeansVals); + // // store results + // for (int i=0;i<n+1;++i) { + // kmeansCosts[i].params["branching"] = kmeansNMPoints[i*2]; + // kmeansCosts[i].params["max-iterations"] = kmeansNMPoints[i*2+1]; + // kmeansCosts[i].timeCost = kmeansVals[i]; + // } + } + + + void optimizeKDTree(std::vector<CostData>& costs) + { + Logger::info("KD-TREE, Step 1: Exploring parameter space\n"); + + // explore kd-tree parameters space using the parameters below + int testTrees[] = { 1, 4, 8, 16, 32 }; + + // evaluate kdtree for all parameter combinations + for (size_t i = 0; i < FLANN_ARRAY_LEN(testTrees); ++i) { + CostData cost; + cost.params["algorithm"] = FLANN_INDEX_KDTREE; + cost.params["trees"] = testTrees[i]; + + evaluate_kdtree(cost); + costs.push_back(cost); + } + + // Logger::info("KD-TREE, Step 2: simplex-downhill optimization\n"); + // + // const int n = 1; + // // choose initial simplex points as the best parameters so far + // int kdtreeNMPoints[n*(n+1)]; + // float kdtreeVals[n+1]; + // for (int i=0;i<n+1;++i) { + // kdtreeNMPoints[i] = (int)kdtreeCosts[i].params["trees"]; + // kdtreeVals[i] = kdtreeCosts[i].timeCost; + // } + // KDTreeSimpleDownhillFunctor kdtree_cost_func(*this); + // // run optimization + // optimizeSimplexDownhill(kdtreeNMPoints,n,kdtree_cost_func,kdtreeVals); + // // store results + // for (int i=0;i<n+1;++i) { + // kdtreeCosts[i].params["trees"] = kdtreeNMPoints[i]; + // kdtreeCosts[i].timeCost = kdtreeVals[i]; + // } + } + + /** + * Chooses the best nearest-neighbor algorithm and estimates the optimal + * parameters to use when building the index (for a given precision). + * Returns a dictionary with the optimal parameters. + */ + IndexParams estimateBuildParams() + { + std::vector<CostData> costs; + + int sampleSize = int(sample_fraction_ * dataset_.rows); + int testSampleSize = std::min(sampleSize / 10, 1000); + + Logger::info("Entering autotuning, dataset size: %d, sampleSize: %d, testSampleSize: %d, target precision: %g\n", dataset_.rows, sampleSize, testSampleSize, target_precision_); + + // For a very small dataset, it makes no sense to build any fancy index, just + // use linear search + if (testSampleSize < 10) { + Logger::info("Choosing linear, dataset too small\n"); + return LinearIndexParams(); + } + + // We use a fraction of the original dataset to speedup the autotune algorithm + sampledDataset_ = random_sample(dataset_, sampleSize); + // We use a cross-validation approach, first we sample a testset from the dataset + testDataset_ = random_sample(sampledDataset_, testSampleSize, true); + + // We compute the ground truth using linear search + Logger::info("Computing ground truth... \n"); + gt_matches_ = Matrix<int>(new int[testDataset_.rows], testDataset_.rows, 1); + StartStopTimer t; + t.start(); + compute_ground_truth<Distance>(sampledDataset_, testDataset_, gt_matches_, 0, distance_); + t.stop(); + + CostData linear_cost; + linear_cost.searchTimeCost = (float)t.value; + linear_cost.buildTimeCost = 0; + linear_cost.memoryCost = 0; + linear_cost.params["algorithm"] = FLANN_INDEX_LINEAR; + + costs.push_back(linear_cost); + + // Start parameter autotune process + Logger::info("Autotuning parameters...\n"); + + optimizeKMeans(costs); + optimizeKDTree(costs); + + float bestTimeCost = costs[0].searchTimeCost; + for (size_t i = 0; i < costs.size(); ++i) { + float timeCost = costs[i].buildTimeCost * build_weight_ + costs[i].searchTimeCost; + if (timeCost < bestTimeCost) { + bestTimeCost = timeCost; + } + } + + float bestCost = costs[0].searchTimeCost / bestTimeCost; + IndexParams bestParams = costs[0].params; + if (bestTimeCost > 0) { + for (size_t i = 0; i < costs.size(); ++i) { + float crtCost = (costs[i].buildTimeCost * build_weight_ + costs[i].searchTimeCost) / bestTimeCost + + memory_weight_ * costs[i].memoryCost; + if (crtCost < bestCost) { + bestCost = crtCost; + bestParams = costs[i].params; + } + } + } + + delete[] gt_matches_.data; + delete[] testDataset_.data; + delete[] sampledDataset_.data; + + return bestParams; + } + + + + /** + * Estimates the search time parameters needed to get the desired precision. + * Precondition: the index is built + * Postcondition: the searchParams will have the optimum params set, also the speedup obtained over linear search. + */ + float estimateSearchParams(SearchParams& searchParams) + { + const int nn = 1; + const size_t SAMPLE_COUNT = 1000; + + assert(bestIndex_ != NULL); // must have a valid index + + float speedup = 0; + + int samples = (int)std::min(dataset_.rows / 10, SAMPLE_COUNT); + if (samples > 0) { + Matrix<ElementType> testDataset = random_sample(dataset_, samples); + + Logger::info("Computing ground truth\n"); + + // we need to compute the ground truth first + Matrix<int> gt_matches(new int[testDataset.rows], testDataset.rows, 1); + StartStopTimer t; + t.start(); + compute_ground_truth<Distance>(dataset_, testDataset, gt_matches, 1, distance_); + t.stop(); + float linear = (float)t.value; + + int checks; + Logger::info("Estimating number of checks\n"); + + float searchTime; + float cb_index; + if (bestIndex_->getType() == FLANN_INDEX_KMEANS) { + Logger::info("KMeans algorithm, estimating cluster border factor\n"); + KMeansIndex<Distance>* kmeans = (KMeansIndex<Distance>*)bestIndex_; + float bestSearchTime = -1; + float best_cb_index = -1; + int best_checks = -1; + for (cb_index = 0; cb_index < 1.1f; cb_index += 0.2f) { + kmeans->set_cb_index(cb_index); + searchTime = test_index_precision(*kmeans, dataset_, testDataset, gt_matches, target_precision_, checks, distance_, nn, 1); + if ((searchTime < bestSearchTime) || (bestSearchTime == -1)) { + bestSearchTime = searchTime; + best_cb_index = cb_index; + best_checks = checks; + } + } + searchTime = bestSearchTime; + cb_index = best_cb_index; + checks = best_checks; + + kmeans->set_cb_index(best_cb_index); + Logger::info("Optimum cb_index: %g\n", cb_index); + bestParams_["cb_index"] = cb_index; + } + else { + searchTime = test_index_precision(*bestIndex_, dataset_, testDataset, gt_matches, target_precision_, checks, distance_, nn, 1); + } + + Logger::info("Required number of checks: %d \n", checks); + searchParams["checks"] = checks; + + speedup = linear / searchTime; + + delete[] gt_matches.data; + delete[] testDataset.data; + } + + return speedup; + } + +private: + 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 + */ + float target_precision_; + float build_weight_; + float memory_weight_; + float sample_fraction_; + + Distance distance_; + + +}; +} + +#endif /* OPENCV_FLANN_AUTOTUNED_INDEX_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/composite_index.h b/thirdparty/linux/include/opencv2/flann/composite_index.h new file mode 100644 index 0000000..527ca1a --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/composite_index.h @@ -0,0 +1,194 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_COMPOSITE_INDEX_H_ +#define OPENCV_FLANN_COMPOSITE_INDEX_H_ + +#include "general.h" +#include "nn_index.h" +#include "kdtree_index.h" +#include "kmeans_index.h" + +namespace cvflann +{ + +/** + * Index parameters for the CompositeIndex. + */ +struct CompositeIndexParams : public IndexParams +{ + CompositeIndexParams(int trees = 4, int branching = 32, int iterations = 11, + flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM, float cb_index = 0.2 ) + { + (*this)["algorithm"] = FLANN_INDEX_KMEANS; + // number of randomized trees to use (for kdtree) + (*this)["trees"] = trees; + // branching factor + (*this)["branching"] = branching; + // max iterations to perform in one kmeans clustering (kmeans tree) + (*this)["iterations"] = iterations; + // algorithm used for picking the initial cluster centers for kmeans tree + (*this)["centers_init"] = centers_init; + // cluster boundary index. Used when searching the kmeans tree + (*this)["cb_index"] = cb_index; + } +}; + + +/** + * This index builds a kd-tree index and a k-means index and performs nearest + * neighbour search both indexes. This gives a slight boost in search performance + * as some of the neighbours that are missed by one index are found by the other. + */ +template <typename Distance> +class CompositeIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + /** + * Index constructor + * @param inputData dataset containing the points to index + * @param params Index parameters + * @param d Distance functor + * @return + */ + CompositeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = CompositeIndexParams(), + Distance d = Distance()) : index_params_(params) + { + kdtree_index_ = new KDTreeIndex<Distance>(inputData, params, d); + kmeans_index_ = new KMeansIndex<Distance>(inputData, params, d); + + } + + CompositeIndex(const CompositeIndex&); + CompositeIndex& operator=(const CompositeIndex&); + + virtual ~CompositeIndex() + { + delete kdtree_index_; + delete kmeans_index_; + } + + /** + * @return The index type + */ + flann_algorithm_t getType() const + { + return FLANN_INDEX_COMPOSITE; + } + + /** + * @return Size of the index + */ + size_t size() const + { + return kdtree_index_->size(); + } + + /** + * \returns The dimensionality of the features in this index. + */ + size_t veclen() const + { + return kdtree_index_->veclen(); + } + + /** + * \returns The amount of memory (in bytes) used by the index. + */ + int usedMemory() const + { + return kmeans_index_->usedMemory() + kdtree_index_->usedMemory(); + } + + /** + * \brief Builds the index + */ + void buildIndex() + { + Logger::info("Building kmeans tree...\n"); + kmeans_index_->buildIndex(); + Logger::info("Building kdtree tree...\n"); + kdtree_index_->buildIndex(); + } + + /** + * \brief Saves the index to a stream + * \param stream The stream to save the index to + */ + void saveIndex(FILE* stream) + { + kmeans_index_->saveIndex(stream); + kdtree_index_->saveIndex(stream); + } + + /** + * \brief Loads the index from a stream + * \param stream The stream from which the index is loaded + */ + void loadIndex(FILE* stream) + { + kmeans_index_->loadIndex(stream); + kdtree_index_->loadIndex(stream); + } + + /** + * \returns The index parameters + */ + IndexParams getParameters() const + { + return index_params_; + } + + /** + * \brief Method that searches for nearest-neighbours + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + kmeans_index_->findNeighbors(result, vec, searchParams); + kdtree_index_->findNeighbors(result, vec, searchParams); + } + +private: + /** The k-means index */ + KMeansIndex<Distance>* kmeans_index_; + + /** The kd-tree index */ + KDTreeIndex<Distance>* kdtree_index_; + + /** The index parameters */ + const IndexParams index_params_; +}; + +} + +#endif //OPENCV_FLANN_COMPOSITE_INDEX_H_ diff --git a/thirdparty/linux/include/opencv2/flann/config.h b/thirdparty/linux/include/opencv2/flann/config.h new file mode 100644 index 0000000..56832fd --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/config.h @@ -0,0 +1,38 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2011 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2011 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_CONFIG_H_ +#define OPENCV_FLANN_CONFIG_H_ + +#ifdef FLANN_VERSION_ +#undef FLANN_VERSION_ +#endif +#define FLANN_VERSION_ "1.6.10" + +#endif /* OPENCV_FLANN_CONFIG_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/defines.h b/thirdparty/linux/include/opencv2/flann/defines.h new file mode 100644 index 0000000..f0264f7 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/defines.h @@ -0,0 +1,177 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2011 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2011 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_DEFINES_H_ +#define OPENCV_FLANN_DEFINES_H_ + +#include "config.h" + +#ifdef FLANN_EXPORT +#undef FLANN_EXPORT +#endif +#ifdef WIN32 +/* win32 dll export/import directives */ + #ifdef FLANN_EXPORTS + #define FLANN_EXPORT __declspec(dllexport) + #elif defined(FLANN_STATIC) + #define FLANN_EXPORT + #else + #define FLANN_EXPORT __declspec(dllimport) + #endif +#else +/* unix needs nothing */ + #define FLANN_EXPORT +#endif + + +#ifdef FLANN_DEPRECATED +#undef FLANN_DEPRECATED +#endif +#ifdef __GNUC__ +#define FLANN_DEPRECATED __attribute__ ((deprecated)) +#elif defined(_MSC_VER) +#define FLANN_DEPRECATED __declspec(deprecated) +#else +#pragma message("WARNING: You need to implement FLANN_DEPRECATED for this compiler") +#define FLANN_DEPRECATED +#endif + + +#undef FLANN_PLATFORM_32_BIT +#undef FLANN_PLATFORM_64_BIT +#if defined __amd64__ || defined __x86_64__ || defined _WIN64 || defined _M_X64 +#define FLANN_PLATFORM_64_BIT +#else +#define FLANN_PLATFORM_32_BIT +#endif + + +#undef FLANN_ARRAY_LEN +#define FLANN_ARRAY_LEN(a) (sizeof(a)/sizeof(a[0])) + +namespace cvflann { + +/* Nearest neighbour index algorithms */ +enum flann_algorithm_t +{ + FLANN_INDEX_LINEAR = 0, + FLANN_INDEX_KDTREE = 1, + FLANN_INDEX_KMEANS = 2, + FLANN_INDEX_COMPOSITE = 3, + FLANN_INDEX_KDTREE_SINGLE = 4, + FLANN_INDEX_HIERARCHICAL = 5, + FLANN_INDEX_LSH = 6, + FLANN_INDEX_SAVED = 254, + FLANN_INDEX_AUTOTUNED = 255, + + // deprecated constants, should use the FLANN_INDEX_* ones instead + LINEAR = 0, + KDTREE = 1, + KMEANS = 2, + COMPOSITE = 3, + KDTREE_SINGLE = 4, + SAVED = 254, + AUTOTUNED = 255 +}; + + + +enum flann_centers_init_t +{ + FLANN_CENTERS_RANDOM = 0, + FLANN_CENTERS_GONZALES = 1, + FLANN_CENTERS_KMEANSPP = 2, + FLANN_CENTERS_GROUPWISE = 3, + + // deprecated constants, should use the FLANN_CENTERS_* ones instead + CENTERS_RANDOM = 0, + CENTERS_GONZALES = 1, + CENTERS_KMEANSPP = 2 +}; + +enum flann_log_level_t +{ + FLANN_LOG_NONE = 0, + FLANN_LOG_FATAL = 1, + FLANN_LOG_ERROR = 2, + FLANN_LOG_WARN = 3, + FLANN_LOG_INFO = 4 +}; + +enum flann_distance_t +{ + FLANN_DIST_EUCLIDEAN = 1, + FLANN_DIST_L2 = 1, + FLANN_DIST_MANHATTAN = 2, + FLANN_DIST_L1 = 2, + FLANN_DIST_MINKOWSKI = 3, + FLANN_DIST_MAX = 4, + FLANN_DIST_HIST_INTERSECT = 5, + FLANN_DIST_HELLINGER = 6, + FLANN_DIST_CHI_SQUARE = 7, + FLANN_DIST_CS = 7, + FLANN_DIST_KULLBACK_LEIBLER = 8, + FLANN_DIST_KL = 8, + FLANN_DIST_HAMMING = 9, + + // deprecated constants, should use the FLANN_DIST_* ones instead + EUCLIDEAN = 1, + MANHATTAN = 2, + MINKOWSKI = 3, + MAX_DIST = 4, + HIST_INTERSECT = 5, + HELLINGER = 6, + CS = 7, + KL = 8, + KULLBACK_LEIBLER = 8 +}; + +enum flann_datatype_t +{ + FLANN_INT8 = 0, + FLANN_INT16 = 1, + FLANN_INT32 = 2, + FLANN_INT64 = 3, + FLANN_UINT8 = 4, + FLANN_UINT16 = 5, + FLANN_UINT32 = 6, + FLANN_UINT64 = 7, + FLANN_FLOAT32 = 8, + FLANN_FLOAT64 = 9 +}; + +enum +{ + FLANN_CHECKS_UNLIMITED = -1, + FLANN_CHECKS_AUTOTUNED = -2 +}; + +} + +#endif /* OPENCV_FLANN_DEFINES_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/dist.h b/thirdparty/linux/include/opencv2/flann/dist.h new file mode 100644 index 0000000..9dbe527 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/dist.h @@ -0,0 +1,905 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_DIST_H_ +#define OPENCV_FLANN_DIST_H_ + +#include <cmath> +#include <cstdlib> +#include <string.h> +#ifdef _MSC_VER +typedef unsigned __int32 uint32_t; +typedef unsigned __int64 uint64_t; +#else +#include <stdint.h> +#endif + +#include "defines.h" + +#if (defined WIN32 || defined _WIN32) && defined(_M_ARM) +# include <Intrin.h> +#endif + +#ifdef __ARM_NEON__ +# include "arm_neon.h" +#endif + +namespace cvflann +{ + +template<typename T> +inline T abs(T x) { return (x<0) ? -x : x; } + +template<> +inline int abs<int>(int x) { return ::abs(x); } + +template<> +inline float abs<float>(float x) { return fabsf(x); } + +template<> +inline double abs<double>(double x) { return fabs(x); } + +template<typename T> +struct Accumulator { typedef T Type; }; +template<> +struct Accumulator<unsigned char> { typedef float Type; }; +template<> +struct Accumulator<unsigned short> { typedef float Type; }; +template<> +struct Accumulator<unsigned int> { typedef float Type; }; +template<> +struct Accumulator<char> { typedef float Type; }; +template<> +struct Accumulator<short> { typedef float Type; }; +template<> +struct Accumulator<int> { typedef float Type; }; + +#undef True +#undef False + +class True +{ +}; + +class False +{ +}; + + +/** + * Squared Euclidean distance functor. + * + * This is the simpler, unrolled version. This is preferable for + * very low dimensionality data (eg 3D points) + */ +template<class T> +struct L2_Simple +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const + { + ResultType result = ResultType(); + ResultType diff; + for(size_t i = 0; i < size; ++i ) { + diff = *a++ - *b++; + result += diff*diff; + } + return result; + } + + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + return (a-b)*(a-b); + } +}; + + + +/** + * Squared Euclidean distance functor, optimized version + */ +template<class T> +struct L2 +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the squared Euclidean distance between two vectors. + * + * This is highly optimised, with loop unrolling, as it is one + * of the most expensive inner loops. + * + * The computation of squared root at the end is omitted for + * efficiency. + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + ResultType diff0, diff1, diff2, diff3; + Iterator1 last = a + size; + Iterator1 lastgroup = last - 3; + + /* Process 4 items with each loop for efficiency. */ + while (a < lastgroup) { + diff0 = (ResultType)(a[0] - b[0]); + diff1 = (ResultType)(a[1] - b[1]); + diff2 = (ResultType)(a[2] - b[2]); + diff3 = (ResultType)(a[3] - b[3]); + result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3; + a += 4; + b += 4; + + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + /* Process last 0-3 pixels. Not needed for standard vector lengths. */ + while (a < last) { + diff0 = (ResultType)(*a++ - *b++); + result += diff0 * diff0; + } + return result; + } + + /** + * Partial euclidean distance, using just one dimension. This is used by the + * kd-tree when computing partial distances while traversing the tree. + * + * Squared root is omitted for efficiency. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + return (a-b)*(a-b); + } +}; + + +/* + * Manhattan distance functor, optimized version + */ +template<class T> +struct L1 +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the Manhattan (L_1) distance between two vectors. + * + * This is highly optimised, with loop unrolling, as it is one + * of the most expensive inner loops. + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + ResultType diff0, diff1, diff2, diff3; + Iterator1 last = a + size; + Iterator1 lastgroup = last - 3; + + /* Process 4 items with each loop for efficiency. */ + while (a < lastgroup) { + diff0 = (ResultType)abs(a[0] - b[0]); + diff1 = (ResultType)abs(a[1] - b[1]); + diff2 = (ResultType)abs(a[2] - b[2]); + diff3 = (ResultType)abs(a[3] - b[3]); + result += diff0 + diff1 + diff2 + diff3; + a += 4; + b += 4; + + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + /* Process last 0-3 pixels. Not needed for standard vector lengths. */ + while (a < last) { + diff0 = (ResultType)abs(*a++ - *b++); + result += diff0; + } + return result; + } + + /** + * Partial distance, used by the kd-tree. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + return abs(a-b); + } +}; + + + +template<class T> +struct MinkowskiDistance +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + int order; + + MinkowskiDistance(int order_) : order(order_) {} + + /** + * Compute the Minkowsky (L_p) distance between two vectors. + * + * This is highly optimised, with loop unrolling, as it is one + * of the most expensive inner loops. + * + * The computation of squared root at the end is omitted for + * efficiency. + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + ResultType diff0, diff1, diff2, diff3; + Iterator1 last = a + size; + Iterator1 lastgroup = last - 3; + + /* Process 4 items with each loop for efficiency. */ + while (a < lastgroup) { + diff0 = (ResultType)abs(a[0] - b[0]); + diff1 = (ResultType)abs(a[1] - b[1]); + diff2 = (ResultType)abs(a[2] - b[2]); + diff3 = (ResultType)abs(a[3] - b[3]); + result += pow(diff0,order) + pow(diff1,order) + pow(diff2,order) + pow(diff3,order); + a += 4; + b += 4; + + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + /* Process last 0-3 pixels. Not needed for standard vector lengths. */ + while (a < last) { + diff0 = (ResultType)abs(*a++ - *b++); + result += pow(diff0,order); + } + return result; + } + + /** + * Partial distance, used by the kd-tree. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + return pow(static_cast<ResultType>(abs(a-b)),order); + } +}; + + + +template<class T> +struct MaxDistance +{ + typedef False is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the max distance (L_infinity) between two vectors. + * + * This distance is not a valid kdtree distance, it's not dimensionwise additive. + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + ResultType diff0, diff1, diff2, diff3; + Iterator1 last = a + size; + Iterator1 lastgroup = last - 3; + + /* Process 4 items with each loop for efficiency. */ + while (a < lastgroup) { + diff0 = abs(a[0] - b[0]); + diff1 = abs(a[1] - b[1]); + diff2 = abs(a[2] - b[2]); + diff3 = abs(a[3] - b[3]); + if (diff0>result) {result = diff0; } + if (diff1>result) {result = diff1; } + if (diff2>result) {result = diff2; } + if (diff3>result) {result = diff3; } + a += 4; + b += 4; + + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + /* Process last 0-3 pixels. Not needed for standard vector lengths. */ + while (a < last) { + diff0 = abs(*a++ - *b++); + result = (diff0>result) ? diff0 : result; + } + return result; + } + + /* This distance functor is not dimension-wise additive, which + * makes it an invalid kd-tree distance, not implementing the accum_dist method */ + +}; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** + * Hamming distance functor - counts the bit differences between two strings - useful for the Brief descriptor + * bit count of A exclusive XOR'ed with B + */ +struct HammingLUT +{ + typedef False is_kdtree_distance; + typedef False is_vector_space_distance; + + typedef unsigned char ElementType; + typedef int ResultType; + + /** this will count the bits in a ^ b + */ + ResultType operator()(const unsigned char* a, const unsigned char* b, size_t size) const + { + static const uchar popCountTable[] = + { + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 + }; + ResultType result = 0; + for (size_t i = 0; i < size; i++) { + result += popCountTable[a[i] ^ b[i]]; + } + return result; + } +}; + +/** + * Hamming distance functor (pop count between two binary vectors, i.e. xor them and count the number of bits set) + * That code was taken from brief.cpp in OpenCV + */ +template<class T> +struct Hamming +{ + typedef False is_kdtree_distance; + typedef False is_vector_space_distance; + + + typedef T ElementType; + typedef int ResultType; + + template<typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const + { + ResultType result = 0; +#ifdef __ARM_NEON__ + { + uint32x4_t bits = vmovq_n_u32(0); + for (size_t i = 0; i < size; i += 16) { + uint8x16_t A_vec = vld1q_u8 (a + i); + uint8x16_t B_vec = vld1q_u8 (b + i); + uint8x16_t AxorB = veorq_u8 (A_vec, B_vec); + uint8x16_t bitsSet = vcntq_u8 (AxorB); + uint16x8_t bitSet8 = vpaddlq_u8 (bitsSet); + uint32x4_t bitSet4 = vpaddlq_u16 (bitSet8); + bits = vaddq_u32(bits, bitSet4); + } + uint64x2_t bitSet2 = vpaddlq_u32 (bits); + result = vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),0); + result += vgetq_lane_s32 (vreinterpretq_s32_u64(bitSet2),2); + } +#elif __GNUC__ + { + //for portability just use unsigned long -- and use the __builtin_popcountll (see docs for __builtin_popcountll) + typedef unsigned long long pop_t; + const size_t modulo = size % sizeof(pop_t); + const pop_t* a2 = reinterpret_cast<const pop_t*> (a); + const pop_t* b2 = reinterpret_cast<const pop_t*> (b); + const pop_t* a2_end = a2 + (size / sizeof(pop_t)); + + for (; a2 != a2_end; ++a2, ++b2) result += __builtin_popcountll((*a2) ^ (*b2)); + + if (modulo) { + //in the case where size is not dividable by sizeof(size_t) + //need to mask off the bits at the end + pop_t a_final = 0, b_final = 0; + memcpy(&a_final, a2, modulo); + memcpy(&b_final, b2, modulo); + result += __builtin_popcountll(a_final ^ b_final); + } + } +#else // NO NEON and NOT GNUC + typedef unsigned long long pop_t; + HammingLUT lut; + result = lut(reinterpret_cast<const unsigned char*> (a), + reinterpret_cast<const unsigned char*> (b), size * sizeof(pop_t)); +#endif + return result; + } +}; + +template<typename T> +struct Hamming2 +{ + typedef False is_kdtree_distance; + typedef False is_vector_space_distance; + + typedef T ElementType; + typedef int ResultType; + + /** This is popcount_3() from: + * http://en.wikipedia.org/wiki/Hamming_weight */ + unsigned int popcnt32(uint32_t n) const + { + n -= ((n >> 1) & 0x55555555); + n = (n & 0x33333333) + ((n >> 2) & 0x33333333); + return (((n + (n >> 4))& 0xF0F0F0F)* 0x1010101) >> 24; + } + +#ifdef FLANN_PLATFORM_64_BIT + unsigned int popcnt64(uint64_t n) const + { + n -= ((n >> 1) & 0x5555555555555555); + n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333); + return (((n + (n >> 4))& 0x0f0f0f0f0f0f0f0f)* 0x0101010101010101) >> 56; + } +#endif + + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const + { +#ifdef FLANN_PLATFORM_64_BIT + const uint64_t* pa = reinterpret_cast<const uint64_t*>(a); + const uint64_t* pb = reinterpret_cast<const uint64_t*>(b); + ResultType result = 0; + size /= (sizeof(uint64_t)/sizeof(unsigned char)); + for(size_t i = 0; i < size; ++i ) { + result += popcnt64(*pa ^ *pb); + ++pa; + ++pb; + } +#else + const uint32_t* pa = reinterpret_cast<const uint32_t*>(a); + const uint32_t* pb = reinterpret_cast<const uint32_t*>(b); + ResultType result = 0; + size /= (sizeof(uint32_t)/sizeof(unsigned char)); + for(size_t i = 0; i < size; ++i ) { + result += popcnt32(*pa ^ *pb); + ++pa; + ++pb; + } +#endif + return result; + } +}; + + + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +template<class T> +struct HistIntersectionDistance +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the histogram intersection distance + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + ResultType min0, min1, min2, min3; + Iterator1 last = a + size; + Iterator1 lastgroup = last - 3; + + /* Process 4 items with each loop for efficiency. */ + while (a < lastgroup) { + min0 = (ResultType)(a[0] < b[0] ? a[0] : b[0]); + min1 = (ResultType)(a[1] < b[1] ? a[1] : b[1]); + min2 = (ResultType)(a[2] < b[2] ? a[2] : b[2]); + min3 = (ResultType)(a[3] < b[3] ? a[3] : b[3]); + result += min0 + min1 + min2 + min3; + a += 4; + b += 4; + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + /* Process last 0-3 pixels. Not needed for standard vector lengths. */ + while (a < last) { + min0 = (ResultType)(*a < *b ? *a : *b); + result += min0; + ++a; + ++b; + } + return result; + } + + /** + * Partial distance, used by the kd-tree. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + return a<b ? a : b; + } +}; + + + +template<class T> +struct HellingerDistance +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the Hellinger distance + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType /*worst_dist*/ = -1) const + { + ResultType result = ResultType(); + ResultType diff0, diff1, diff2, diff3; + Iterator1 last = a + size; + Iterator1 lastgroup = last - 3; + + /* Process 4 items with each loop for efficiency. */ + while (a < lastgroup) { + diff0 = sqrt(static_cast<ResultType>(a[0])) - sqrt(static_cast<ResultType>(b[0])); + diff1 = sqrt(static_cast<ResultType>(a[1])) - sqrt(static_cast<ResultType>(b[1])); + diff2 = sqrt(static_cast<ResultType>(a[2])) - sqrt(static_cast<ResultType>(b[2])); + diff3 = sqrt(static_cast<ResultType>(a[3])) - sqrt(static_cast<ResultType>(b[3])); + result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3; + a += 4; + b += 4; + } + while (a < last) { + diff0 = sqrt(static_cast<ResultType>(*a++)) - sqrt(static_cast<ResultType>(*b++)); + result += diff0 * diff0; + } + return result; + } + + /** + * Partial distance, used by the kd-tree. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + ResultType diff = sqrt(static_cast<ResultType>(a)) - sqrt(static_cast<ResultType>(b)); + return diff * diff; + } +}; + + +template<class T> +struct ChiSquareDistance +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the chi-square distance + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + ResultType sum, diff; + Iterator1 last = a + size; + + while (a < last) { + sum = (ResultType)(*a + *b); + if (sum>0) { + diff = (ResultType)(*a - *b); + result += diff*diff/sum; + } + ++a; + ++b; + + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + return result; + } + + /** + * Partial distance, used by the kd-tree. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + ResultType result = ResultType(); + ResultType sum, diff; + + sum = (ResultType)(a+b); + if (sum>0) { + diff = (ResultType)(a-b); + result = diff*diff/sum; + } + return result; + } +}; + + +template<class T> +struct KL_Divergence +{ + typedef True is_kdtree_distance; + typedef True is_vector_space_distance; + + typedef T ElementType; + typedef typename Accumulator<T>::Type ResultType; + + /** + * Compute the Kullback–Leibler divergence + */ + template <typename Iterator1, typename Iterator2> + ResultType operator()(Iterator1 a, Iterator2 b, size_t size, ResultType worst_dist = -1) const + { + ResultType result = ResultType(); + Iterator1 last = a + size; + + while (a < last) { + if (* b != 0) { + ResultType ratio = (ResultType)(*a / *b); + if (ratio>0) { + result += *a * log(ratio); + } + } + ++a; + ++b; + + if ((worst_dist>0)&&(result>worst_dist)) { + return result; + } + } + return result; + } + + /** + * Partial distance, used by the kd-tree. + */ + template <typename U, typename V> + inline ResultType accum_dist(const U& a, const V& b, int) const + { + ResultType result = ResultType(); + if( *b != 0 ) { + ResultType ratio = (ResultType)(a / b); + if (ratio>0) { + result = a * log(ratio); + } + } + return result; + } +}; + + + +/* + * This is a "zero iterator". It basically behaves like a zero filled + * array to all algorithms that use arrays as iterators (STL style). + * It's useful when there's a need to compute the distance between feature + * and origin it and allows for better compiler optimisation than using a + * zero-filled array. + */ +template <typename T> +struct ZeroIterator +{ + + T operator*() + { + return 0; + } + + T operator[](int) + { + return 0; + } + + const ZeroIterator<T>& operator ++() + { + return *this; + } + + ZeroIterator<T> operator ++(int) + { + return *this; + } + + ZeroIterator<T>& operator+=(int) + { + return *this; + } + +}; + + +/* + * Depending on processed distances, some of them are already squared (e.g. L2) + * and some are not (e.g.Hamming). In KMeans++ for instance we want to be sure + * we are working on ^2 distances, thus following templates to ensure that. + */ +template <typename Distance, typename ElementType> +struct squareDistance +{ + typedef typename Distance::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist*dist; } +}; + + +template <typename ElementType> +struct squareDistance<L2_Simple<ElementType>, ElementType> +{ + typedef typename L2_Simple<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist; } +}; + +template <typename ElementType> +struct squareDistance<L2<ElementType>, ElementType> +{ + typedef typename L2<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist; } +}; + + +template <typename ElementType> +struct squareDistance<MinkowskiDistance<ElementType>, ElementType> +{ + typedef typename MinkowskiDistance<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist; } +}; + +template <typename ElementType> +struct squareDistance<HellingerDistance<ElementType>, ElementType> +{ + typedef typename HellingerDistance<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist; } +}; + +template <typename ElementType> +struct squareDistance<ChiSquareDistance<ElementType>, ElementType> +{ + typedef typename ChiSquareDistance<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist; } +}; + + +template <typename Distance> +typename Distance::ResultType ensureSquareDistance( typename Distance::ResultType dist ) +{ + typedef typename Distance::ElementType ElementType; + + squareDistance<Distance, ElementType> dummy; + return dummy( dist ); +} + + +/* + * ...and a template to ensure the user that he will process the normal distance, + * and not squared distance, without loosing processing time calling sqrt(ensureSquareDistance) + * that will result in doing actually sqrt(dist*dist) for L1 distance for instance. + */ +template <typename Distance, typename ElementType> +struct simpleDistance +{ + typedef typename Distance::ResultType ResultType; + ResultType operator()( ResultType dist ) { return dist; } +}; + + +template <typename ElementType> +struct simpleDistance<L2_Simple<ElementType>, ElementType> +{ + typedef typename L2_Simple<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return sqrt(dist); } +}; + +template <typename ElementType> +struct simpleDistance<L2<ElementType>, ElementType> +{ + typedef typename L2<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return sqrt(dist); } +}; + + +template <typename ElementType> +struct simpleDistance<MinkowskiDistance<ElementType>, ElementType> +{ + typedef typename MinkowskiDistance<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return sqrt(dist); } +}; + +template <typename ElementType> +struct simpleDistance<HellingerDistance<ElementType>, ElementType> +{ + typedef typename HellingerDistance<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return sqrt(dist); } +}; + +template <typename ElementType> +struct simpleDistance<ChiSquareDistance<ElementType>, ElementType> +{ + typedef typename ChiSquareDistance<ElementType>::ResultType ResultType; + ResultType operator()( ResultType dist ) { return sqrt(dist); } +}; + + +template <typename Distance> +typename Distance::ResultType ensureSimpleDistance( typename Distance::ResultType dist ) +{ + typedef typename Distance::ElementType ElementType; + + simpleDistance<Distance, ElementType> dummy; + return dummy( dist ); +} + +} + +#endif //OPENCV_FLANN_DIST_H_ diff --git a/thirdparty/linux/include/opencv2/flann/dummy.h b/thirdparty/linux/include/opencv2/flann/dummy.h new file mode 100644 index 0000000..26bd3fa --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/dummy.h @@ -0,0 +1,16 @@ + +#ifndef OPENCV_FLANN_DUMMY_H_ +#define OPENCV_FLANN_DUMMY_H_ + +namespace cvflann +{ + +#if (defined WIN32 || defined _WIN32 || defined WINCE) && defined CVAPI_EXPORTS +__declspec(dllexport) +#endif +void dummyfunc(); + +} + + +#endif /* OPENCV_FLANN_DUMMY_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/dynamic_bitset.h b/thirdparty/linux/include/opencv2/flann/dynamic_bitset.h new file mode 100644 index 0000000..d795b5d --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/dynamic_bitset.h @@ -0,0 +1,159 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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. + *************************************************************************/ + +/*********************************************************************** + * Author: Vincent Rabaud + *************************************************************************/ + +#ifndef OPENCV_FLANN_DYNAMIC_BITSET_H_ +#define OPENCV_FLANN_DYNAMIC_BITSET_H_ + +#ifndef FLANN_USE_BOOST +# define FLANN_USE_BOOST 0 +#endif +//#define FLANN_USE_BOOST 1 +#if FLANN_USE_BOOST +#include <boost/dynamic_bitset.hpp> +typedef boost::dynamic_bitset<> DynamicBitset; +#else + +#include <limits.h> + +#include "dist.h" + +namespace cvflann { + +/** Class re-implementing the boost version of it + * This helps not depending on boost, it also does not do the bound checks + * and has a way to reset a block for speed + */ +class DynamicBitset +{ +public: + /** default constructor + */ + DynamicBitset() + { + } + + /** only constructor we use in our code + * @param sz the size of the bitset (in bits) + */ + DynamicBitset(size_t sz) + { + resize(sz); + reset(); + } + + /** Sets all the bits to 0 + */ + void clear() + { + std::fill(bitset_.begin(), bitset_.end(), 0); + } + + /** @brief checks if the bitset is empty + * @return true if the bitset is empty + */ + bool empty() const + { + return bitset_.empty(); + } + + /** set all the bits to 0 + */ + void reset() + { + std::fill(bitset_.begin(), bitset_.end(), 0); + } + + /** @brief set one bit to 0 + * @param index + */ + void reset(size_t index) + { + bitset_[index / cell_bit_size_] &= ~(size_t(1) << (index % cell_bit_size_)); + } + + /** @brief sets a specific bit to 0, and more bits too + * This function is useful when resetting a given set of bits so that the + * whole bitset ends up being 0: if that's the case, we don't care about setting + * other bits to 0 + * @param index + */ + void reset_block(size_t index) + { + bitset_[index / cell_bit_size_] = 0; + } + + /** resize the bitset so that it contains at least sz bits + * @param sz + */ + void resize(size_t sz) + { + size_ = sz; + bitset_.resize(sz / cell_bit_size_ + 1); + } + + /** set a bit to true + * @param index the index of the bit to set to 1 + */ + void set(size_t index) + { + bitset_[index / cell_bit_size_] |= size_t(1) << (index % cell_bit_size_); + } + + /** gives the number of contained bits + */ + size_t size() const + { + return size_; + } + + /** check if a bit is set + * @param index the index of the bit to check + * @return true if the bit is set + */ + bool test(size_t index) const + { + return (bitset_[index / cell_bit_size_] & (size_t(1) << (index % cell_bit_size_))) != 0; + } + +private: + std::vector<size_t> bitset_; + size_t size_; + static const unsigned int cell_bit_size_ = CHAR_BIT * sizeof(size_t); +}; + +} // namespace cvflann + +#endif + +#endif // OPENCV_FLANN_DYNAMIC_BITSET_H_ diff --git a/thirdparty/linux/include/opencv2/flann/flann.hpp b/thirdparty/linux/include/opencv2/flann/flann.hpp new file mode 100644 index 0000000..227683f --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/flann.hpp @@ -0,0 +1,48 @@ +/*M/////////////////////////////////////////////////////////////////////////////////////// +// +// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. +// +// By downloading, copying, installing or using the software you agree to this license. +// If you do not agree to this license, do not download, install, +// copy or use the software. +// +// +// License Agreement +// For Open Source Computer Vision Library +// +// Copyright (C) 2000-2008, Intel Corporation, all rights reserved. +// Copyright (C) 2009, Willow Garage Inc., all rights reserved. +// Copyright (C) 2013, OpenCV Foundation, all rights reserved. +// Third party copyrights are property of their respective owners. +// +// Redistribution and use in source and binary forms, with or without modification, +// are permitted provided that the following conditions are met: +// +// * Redistribution's of source code must retain the above copyright notice, +// this list of conditions and the following disclaimer. +// +// * Redistribution's 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. +// +// * The name of the copyright holders may not be used to endorse or promote products +// derived from this software without specific prior written permission. +// +// This software is provided by the copyright holders and contributors "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 Intel Corporation or contributors 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. +// +//M*/ + +#ifdef __OPENCV_BUILD +#error this is a compatibility header which should not be used inside the OpenCV library +#endif + +#include "opencv2/flann.hpp" diff --git a/thirdparty/linux/include/opencv2/flann/flann_base.hpp b/thirdparty/linux/include/opencv2/flann/flann_base.hpp new file mode 100644 index 0000000..98c33cf --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/flann_base.hpp @@ -0,0 +1,290 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_BASE_HPP_ +#define OPENCV_FLANN_BASE_HPP_ + +#include <vector> +#include <cassert> +#include <cstdio> + +#include "general.h" +#include "matrix.h" +#include "params.h" +#include "saving.h" + +#include "all_indices.h" + +namespace cvflann +{ + +/** + * Sets the log level used for all flann functions + * @param level Verbosity level + */ +inline void log_verbosity(int level) +{ + if (level >= 0) { + Logger::setLevel(level); + } +} + +/** + * (Deprecated) Index parameters for creating a saved index. + */ +struct SavedIndexParams : public IndexParams +{ + SavedIndexParams(cv::String filename) + { + (* this)["algorithm"] = FLANN_INDEX_SAVED; + (*this)["filename"] = filename; + } +}; + + +template<typename Distance> +NNIndex<Distance>* load_saved_index(const Matrix<typename Distance::ElementType>& dataset, const cv::String& filename, Distance distance) +{ + typedef typename Distance::ElementType ElementType; + + FILE* fin = fopen(filename.c_str(), "rb"); + if (fin == NULL) { + return NULL; + } + IndexHeader header = load_header(fin); + if (header.data_type != Datatype<ElementType>::type()) { + throw FLANNException("Datatype of saved index is different than of the one to be created."); + } + if ((size_t(header.rows) != dataset.rows)||(size_t(header.cols) != dataset.cols)) { + throw FLANNException("The index saved belongs to a different dataset"); + } + + IndexParams params; + params["algorithm"] = header.index_type; + NNIndex<Distance>* nnIndex = create_index_by_type<Distance>(dataset, params, distance); + nnIndex->loadIndex(fin); + fclose(fin); + + return nnIndex; +} + + +template<typename Distance> +class Index : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + Index(const Matrix<ElementType>& features, const IndexParams& params, Distance distance = Distance() ) + : index_params_(params) + { + flann_algorithm_t index_type = get_param<flann_algorithm_t>(params,"algorithm"); + loaded_ = false; + + if (index_type == FLANN_INDEX_SAVED) { + nnIndex_ = load_saved_index<Distance>(features, get_param<cv::String>(params,"filename"), distance); + loaded_ = true; + } + else { + nnIndex_ = create_index_by_type<Distance>(features, params, distance); + } + } + + ~Index() + { + delete nnIndex_; + } + + /** + * Builds the index. + */ + void buildIndex() + { + if (!loaded_) { + nnIndex_->buildIndex(); + } + } + + void save(cv::String filename) + { + FILE* fout = fopen(filename.c_str(), "wb"); + if (fout == NULL) { + throw FLANNException("Cannot open file"); + } + save_header(fout, *nnIndex_); + saveIndex(fout); + fclose(fout); + } + + /** + * \brief Saves the index to a stream + * \param stream The stream to save the index to + */ + virtual void saveIndex(FILE* stream) + { + nnIndex_->saveIndex(stream); + } + + /** + * \brief Loads the index from a stream + * \param stream The stream from which the index is loaded + */ + virtual void loadIndex(FILE* stream) + { + nnIndex_->loadIndex(stream); + } + + /** + * \returns number of features in this index. + */ + size_t veclen() const + { + return nnIndex_->veclen(); + } + + /** + * \returns The dimensionality of the features in this index. + */ + size_t size() const + { + return nnIndex_->size(); + } + + /** + * \returns The index type (kdtree, kmeans,...) + */ + flann_algorithm_t getType() const + { + return nnIndex_->getType(); + } + + /** + * \returns The amount of memory (in bytes) used by the index. + */ + virtual int usedMemory() const + { + return nnIndex_->usedMemory(); + } + + + /** + * \returns The index parameters + */ + IndexParams getParameters() const + { + return nnIndex_->getParameters(); + } + + /** + * \brief Perform k-nearest neighbor search + * \param[in] queries The query points for which to find the nearest neighbors + * \param[out] indices The indices of the nearest neighbors found + * \param[out] dists Distances to the nearest neighbors found + * \param[in] knn Number of nearest neighbors to return + * \param[in] params Search parameters + */ + void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params) + { + nnIndex_->knnSearch(queries, indices, dists, knn, params); + } + + /** + * \brief Perform radius search + * \param[in] query The query point + * \param[out] indices The indinces of the neighbors found within the given radius + * \param[out] dists The distances to the nearest neighbors found + * \param[in] radius The radius used for search + * \param[in] params Search parameters + * \returns Number of neighbors found + */ + int radiusSearch(const Matrix<ElementType>& query, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params) + { + return nnIndex_->radiusSearch(query, indices, dists, radius, params); + } + + /** + * \brief Method that searches for nearest-neighbours + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + nnIndex_->findNeighbors(result, vec, searchParams); + } + + /** + * \brief Returns actual index + */ + FLANN_DEPRECATED NNIndex<Distance>* getIndex() + { + return nnIndex_; + } + + /** + * \brief Returns index parameters. + * \deprecated use getParameters() instead. + */ + FLANN_DEPRECATED const IndexParams* getIndexParameters() + { + return &index_params_; + } + +private: + /** Pointer to actual index class */ + NNIndex<Distance>* nnIndex_; + /** Indices if the index was loaded from a file */ + bool loaded_; + /** Parameters passed to the index */ + IndexParams index_params_; +}; + +/** + * Performs a hierarchical clustering of the points passed as argument and then takes a cut in the + * the clustering tree to return a flat clustering. + * @param[in] points Points to be clustered + * @param centers The computed cluster centres. Matrix should be preallocated and centers.rows is the + * number of clusters requested. + * @param params Clustering parameters (The same as for cvflann::KMeansIndex) + * @param d Distance to be used for clustering (eg: cvflann::L2) + * @return number of clusters computed (can be different than clusters.rows and is the highest number + * of the form (branching-1)*K+1 smaller than clusters.rows). + */ +template <typename Distance> +int hierarchicalClustering(const Matrix<typename Distance::ElementType>& points, Matrix<typename Distance::ResultType>& centers, + const KMeansIndexParams& params, Distance d = Distance()) +{ + KMeansIndex<Distance> kmeans(points, params, d); + kmeans.buildIndex(); + + int clusterNum = kmeans.getClusterCenters(centers); + return clusterNum; +} + +} +#endif /* OPENCV_FLANN_BASE_HPP_ */ diff --git a/thirdparty/linux/include/opencv2/flann/general.h b/thirdparty/linux/include/opencv2/flann/general.h new file mode 100644 index 0000000..9d5402a --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/general.h @@ -0,0 +1,50 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_GENERAL_H_ +#define OPENCV_FLANN_GENERAL_H_ + +#include "opencv2/core.hpp" + +namespace cvflann +{ + +class FLANNException : public cv::Exception +{ +public: + FLANNException(const char* message) : cv::Exception(0, message, "", __FILE__, __LINE__) { } + + FLANNException(const cv::String& message) : cv::Exception(0, message, "", __FILE__, __LINE__) { } +}; + +} + + +#endif /* OPENCV_FLANN_GENERAL_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/ground_truth.h b/thirdparty/linux/include/opencv2/flann/ground_truth.h new file mode 100644 index 0000000..fd8f3ae --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/ground_truth.h @@ -0,0 +1,94 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_GROUND_TRUTH_H_ +#define OPENCV_FLANN_GROUND_TRUTH_H_ + +#include "dist.h" +#include "matrix.h" + + +namespace cvflann +{ + +template <typename Distance> +void find_nearest(const Matrix<typename Distance::ElementType>& dataset, typename Distance::ElementType* query, int* matches, int nn, + int skip = 0, Distance distance = Distance()) +{ + typedef typename Distance::ResultType DistanceType; + int n = nn + skip; + + std::vector<int> match(n); + std::vector<DistanceType> dists(n); + + dists[0] = distance(dataset[0], query, dataset.cols); + match[0] = 0; + int dcnt = 1; + + for (size_t i=1; i<dataset.rows; ++i) { + DistanceType tmp = distance(dataset[i], query, dataset.cols); + + if (dcnt<n) { + match[dcnt] = (int)i; + dists[dcnt++] = tmp; + } + else if (tmp < dists[dcnt-1]) { + dists[dcnt-1] = tmp; + match[dcnt-1] = (int)i; + } + + int j = dcnt-1; + // bubble up + while (j>=1 && dists[j]<dists[j-1]) { + std::swap(dists[j],dists[j-1]); + std::swap(match[j],match[j-1]); + j--; + } + } + + for (int i=0; i<nn; ++i) { + matches[i] = match[i+skip]; + } +} + + +template <typename Distance> +void compute_ground_truth(const Matrix<typename Distance::ElementType>& dataset, const Matrix<typename Distance::ElementType>& testset, Matrix<int>& matches, + int skip=0, Distance d = Distance()) +{ + for (size_t i=0; i<testset.rows; ++i) { + find_nearest<Distance>(dataset, testset[i], matches[i], (int)matches.cols, skip, d); + } +} + + +} + +#endif //OPENCV_FLANN_GROUND_TRUTH_H_ diff --git a/thirdparty/linux/include/opencv2/flann/hdf5.h b/thirdparty/linux/include/opencv2/flann/hdf5.h new file mode 100644 index 0000000..80d23b9 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/hdf5.h @@ -0,0 +1,231 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_HDF5_H_ +#define OPENCV_FLANN_HDF5_H_ + +#include <hdf5.h> + +#include "matrix.h" + + +namespace cvflann +{ + +namespace +{ + +template<typename T> +hid_t get_hdf5_type() +{ + throw FLANNException("Unsupported type for IO operations"); +} + +template<> +hid_t get_hdf5_type<char>() { return H5T_NATIVE_CHAR; } +template<> +hid_t get_hdf5_type<unsigned char>() { return H5T_NATIVE_UCHAR; } +template<> +hid_t get_hdf5_type<short int>() { return H5T_NATIVE_SHORT; } +template<> +hid_t get_hdf5_type<unsigned short int>() { return H5T_NATIVE_USHORT; } +template<> +hid_t get_hdf5_type<int>() { return H5T_NATIVE_INT; } +template<> +hid_t get_hdf5_type<unsigned int>() { return H5T_NATIVE_UINT; } +template<> +hid_t get_hdf5_type<long>() { return H5T_NATIVE_LONG; } +template<> +hid_t get_hdf5_type<unsigned long>() { return H5T_NATIVE_ULONG; } +template<> +hid_t get_hdf5_type<float>() { return H5T_NATIVE_FLOAT; } +template<> +hid_t get_hdf5_type<double>() { return H5T_NATIVE_DOUBLE; } +} + + +#define CHECK_ERROR(x,y) if ((x)<0) throw FLANNException((y)); + +template<typename T> +void save_to_file(const cvflann::Matrix<T>& dataset, const String& filename, const String& name) +{ + +#if H5Eset_auto_vers == 2 + H5Eset_auto( H5E_DEFAULT, NULL, NULL ); +#else + H5Eset_auto( NULL, NULL ); +#endif + + herr_t status; + hid_t file_id; + file_id = H5Fopen(filename.c_str(), H5F_ACC_RDWR, H5P_DEFAULT); + if (file_id < 0) { + file_id = H5Fcreate(filename.c_str(), H5F_ACC_EXCL, H5P_DEFAULT, H5P_DEFAULT); + } + CHECK_ERROR(file_id,"Error creating hdf5 file."); + + hsize_t dimsf[2]; // dataset dimensions + dimsf[0] = dataset.rows; + dimsf[1] = dataset.cols; + + hid_t space_id = H5Screate_simple(2, dimsf, NULL); + hid_t memspace_id = H5Screate_simple(2, dimsf, NULL); + + hid_t dataset_id; +#if H5Dcreate_vers == 2 + dataset_id = H5Dcreate2(file_id, name.c_str(), get_hdf5_type<T>(), space_id, H5P_DEFAULT, H5P_DEFAULT, H5P_DEFAULT); +#else + dataset_id = H5Dcreate(file_id, name.c_str(), get_hdf5_type<T>(), space_id, H5P_DEFAULT); +#endif + + if (dataset_id<0) { +#if H5Dopen_vers == 2 + dataset_id = H5Dopen2(file_id, name.c_str(), H5P_DEFAULT); +#else + dataset_id = H5Dopen(file_id, name.c_str()); +#endif + } + CHECK_ERROR(dataset_id,"Error creating or opening dataset in file."); + + status = H5Dwrite(dataset_id, get_hdf5_type<T>(), memspace_id, space_id, H5P_DEFAULT, dataset.data ); + CHECK_ERROR(status, "Error writing to dataset"); + + H5Sclose(memspace_id); + H5Sclose(space_id); + H5Dclose(dataset_id); + H5Fclose(file_id); + +} + + +template<typename T> +void load_from_file(cvflann::Matrix<T>& dataset, const String& filename, const String& name) +{ + herr_t status; + hid_t file_id = H5Fopen(filename.c_str(), H5F_ACC_RDWR, H5P_DEFAULT); + CHECK_ERROR(file_id,"Error opening hdf5 file."); + + hid_t dataset_id; +#if H5Dopen_vers == 2 + dataset_id = H5Dopen2(file_id, name.c_str(), H5P_DEFAULT); +#else + dataset_id = H5Dopen(file_id, name.c_str()); +#endif + CHECK_ERROR(dataset_id,"Error opening dataset in file."); + + hid_t space_id = H5Dget_space(dataset_id); + + hsize_t dims_out[2]; + H5Sget_simple_extent_dims(space_id, dims_out, NULL); + + dataset = cvflann::Matrix<T>(new T[dims_out[0]*dims_out[1]], dims_out[0], dims_out[1]); + + status = H5Dread(dataset_id, get_hdf5_type<T>(), H5S_ALL, H5S_ALL, H5P_DEFAULT, dataset[0]); + CHECK_ERROR(status, "Error reading dataset"); + + H5Sclose(space_id); + H5Dclose(dataset_id); + H5Fclose(file_id); +} + + +#ifdef HAVE_MPI + +namespace mpi +{ +/** + * Loads a the hyperslice corresponding to this processor from a hdf5 file. + * @param flann_dataset Dataset where the data is loaded + * @param filename HDF5 file name + * @param name Name of dataset inside file + */ +template<typename T> +void load_from_file(cvflann::Matrix<T>& dataset, const String& filename, const String& name) +{ + MPI_Comm comm = MPI_COMM_WORLD; + MPI_Info info = MPI_INFO_NULL; + + int mpi_size, mpi_rank; + MPI_Comm_size(comm, &mpi_size); + MPI_Comm_rank(comm, &mpi_rank); + + herr_t status; + + hid_t plist_id = H5Pcreate(H5P_FILE_ACCESS); + H5Pset_fapl_mpio(plist_id, comm, info); + hid_t file_id = H5Fopen(filename.c_str(), H5F_ACC_RDWR, plist_id); + CHECK_ERROR(file_id,"Error opening hdf5 file."); + H5Pclose(plist_id); + hid_t dataset_id; +#if H5Dopen_vers == 2 + dataset_id = H5Dopen2(file_id, name.c_str(), H5P_DEFAULT); +#else + dataset_id = H5Dopen(file_id, name.c_str()); +#endif + CHECK_ERROR(dataset_id,"Error opening dataset in file."); + + hid_t space_id = H5Dget_space(dataset_id); + hsize_t dims[2]; + H5Sget_simple_extent_dims(space_id, dims, NULL); + + hsize_t count[2]; + hsize_t offset[2]; + + hsize_t item_cnt = dims[0]/mpi_size+(dims[0]%mpi_size==0 ? 0 : 1); + hsize_t cnt = (mpi_rank<mpi_size-1 ? item_cnt : dims[0]-item_cnt*(mpi_size-1)); + + count[0] = cnt; + count[1] = dims[1]; + offset[0] = mpi_rank*item_cnt; + offset[1] = 0; + + hid_t memspace_id = H5Screate_simple(2,count,NULL); + + H5Sselect_hyperslab(space_id, H5S_SELECT_SET, offset, NULL, count, NULL); + + dataset.rows = count[0]; + dataset.cols = count[1]; + dataset.data = new T[dataset.rows*dataset.cols]; + + plist_id = H5Pcreate(H5P_DATASET_XFER); + H5Pset_dxpl_mpio(plist_id, H5FD_MPIO_COLLECTIVE); + status = H5Dread(dataset_id, get_hdf5_type<T>(), memspace_id, space_id, plist_id, dataset.data); + CHECK_ERROR(status, "Error reading dataset"); + + H5Pclose(plist_id); + H5Sclose(space_id); + H5Sclose(memspace_id); + H5Dclose(dataset_id); + H5Fclose(file_id); +} +} +#endif // HAVE_MPI +} // namespace cvflann::mpi + +#endif /* OPENCV_FLANN_HDF5_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/heap.h b/thirdparty/linux/include/opencv2/flann/heap.h new file mode 100644 index 0000000..92a6ea6 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/heap.h @@ -0,0 +1,165 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_HEAP_H_ +#define OPENCV_FLANN_HEAP_H_ + +#include <algorithm> +#include <vector> + +namespace cvflann +{ + +/** + * Priority Queue Implementation + * + * The priority queue is implemented with a heap. A heap is a complete + * (full) binary tree in which each parent is less than both of its + * children, but the order of the children is unspecified. + */ +template <typename T> +class Heap +{ + + /** + * Storage array for the heap. + * Type T must be comparable. + */ + std::vector<T> heap; + int length; + + /** + * Number of element in the heap + */ + int count; + + + +public: + /** + * Constructor. + * + * Params: + * sz = heap size + */ + + Heap(int sz) + { + length = sz; + heap.reserve(length); + count = 0; + } + + /** + * + * Returns: heap size + */ + int size() + { + return count; + } + + /** + * Tests if the heap is empty + * + * Returns: true is heap empty, false otherwise + */ + bool empty() + { + return size()==0; + } + + /** + * Clears the heap. + */ + void clear() + { + heap.clear(); + count = 0; + } + + struct CompareT + { + bool operator()(const T& t_1, const T& t_2) const + { + return t_2 < t_1; + } + }; + + /** + * Insert a new element in the heap. + * + * We select the next empty leaf node, and then keep moving any larger + * parents down until the right location is found to store this element. + * + * Params: + * value = the new element to be inserted in the heap + */ + void insert(T value) + { + /* If heap is full, then return without adding this element. */ + if (count == length) { + return; + } + + heap.push_back(value); + static CompareT compareT; + std::push_heap(heap.begin(), heap.end(), compareT); + ++count; + } + + + + /** + * Returns the node of minimum value from the heap (top of the heap). + * + * Params: + * value = out parameter used to return the min element + * Returns: false if heap empty + */ + bool popMin(T& value) + { + if (count == 0) { + return false; + } + + value = heap[0]; + static CompareT compareT; + std::pop_heap(heap.begin(), heap.end(), compareT); + heap.pop_back(); + --count; + + return true; /* Return old last node. */ + } +}; + +} + +#endif //OPENCV_FLANN_HEAP_H_ diff --git a/thirdparty/linux/include/opencv2/flann/hierarchical_clustering_index.h b/thirdparty/linux/include/opencv2/flann/hierarchical_clustering_index.h new file mode 100644 index 0000000..9d890d4 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/hierarchical_clustering_index.h @@ -0,0 +1,848 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2011 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2011 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_HIERARCHICAL_CLUSTERING_INDEX_H_ +#define OPENCV_FLANN_HIERARCHICAL_CLUSTERING_INDEX_H_ + +#include <algorithm> +#include <map> +#include <cassert> +#include <limits> +#include <cmath> + +#include "general.h" +#include "nn_index.h" +#include "dist.h" +#include "matrix.h" +#include "result_set.h" +#include "heap.h" +#include "allocator.h" +#include "random.h" +#include "saving.h" + + +namespace cvflann +{ + +struct HierarchicalClusteringIndexParams : public IndexParams +{ + HierarchicalClusteringIndexParams(int branching = 32, + flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM, + int trees = 4, int leaf_size = 100) + { + (*this)["algorithm"] = FLANN_INDEX_HIERARCHICAL; + // The branching factor used in the hierarchical clustering + (*this)["branching"] = branching; + // Algorithm used for picking the initial cluster centers + (*this)["centers_init"] = centers_init; + // number of parallel trees to build + (*this)["trees"] = trees; + // maximum leaf size + (*this)["leaf_size"] = leaf_size; + } +}; + + +/** + * Hierarchical index + * + * Contains a tree constructed through a hierarchical clustering + * and other information for indexing a set of points for nearest-neighbour matching. + */ +template <typename Distance> +class HierarchicalClusteringIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + +private: + + + typedef void (HierarchicalClusteringIndex::* centersAlgFunction)(int, int*, int, int*, int&); + + /** + * The function used for choosing the cluster centers. + */ + centersAlgFunction chooseCenters; + + + + /** + * Chooses the initial centers in the k-means clustering in a random manner. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * indices_length = length of indices vector + * + */ + void chooseCentersRandom(int k, int* dsindices, int indices_length, int* centers, int& centers_length) + { + UniqueRandom r(indices_length); + + int index; + for (index=0; index<k; ++index) { + bool duplicate = true; + int rnd; + while (duplicate) { + duplicate = false; + rnd = r.next(); + if (rnd<0) { + centers_length = index; + return; + } + + centers[index] = dsindices[rnd]; + + for (int j=0; j<index; ++j) { + DistanceType sq = distance(dataset[centers[index]], dataset[centers[j]], dataset.cols); + if (sq<1e-16) { + duplicate = true; + } + } + } + } + + centers_length = index; + } + + + /** + * Chooses the initial centers in the k-means using Gonzales' algorithm + * so that the centers are spaced apart from each other. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * Returns: + */ + void chooseCentersGonzales(int k, int* dsindices, int indices_length, int* centers, int& centers_length) + { + int n = indices_length; + + int rnd = rand_int(n); + assert(rnd >=0 && rnd < n); + + centers[0] = dsindices[rnd]; + + int index; + for (index=1; index<k; ++index) { + + int best_index = -1; + DistanceType best_val = 0; + for (int j=0; j<n; ++j) { + DistanceType dist = distance(dataset[centers[0]],dataset[dsindices[j]],dataset.cols); + for (int i=1; i<index; ++i) { + DistanceType tmp_dist = distance(dataset[centers[i]],dataset[dsindices[j]],dataset.cols); + if (tmp_dist<dist) { + dist = tmp_dist; + } + } + if (dist>best_val) { + best_val = dist; + best_index = j; + } + } + if (best_index!=-1) { + centers[index] = dsindices[best_index]; + } + else { + break; + } + } + centers_length = index; + } + + + /** + * Chooses the initial centers in the k-means using the algorithm + * proposed in the KMeans++ paper: + * Arthur, David; Vassilvitskii, Sergei - k-means++: The Advantages of Careful Seeding + * + * Implementation of this function was converted from the one provided in Arthur's code. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * Returns: + */ + void chooseCentersKMeanspp(int k, int* dsindices, int indices_length, int* centers, int& centers_length) + { + int n = indices_length; + + double currentPot = 0; + DistanceType* closestDistSq = new DistanceType[n]; + + // Choose one random center and set the closestDistSq values + int index = rand_int(n); + assert(index >=0 && index < n); + centers[0] = dsindices[index]; + + // Computing distance^2 will have the advantage of even higher probability further to pick new centers + // far from previous centers (and this complies to "k-means++: the advantages of careful seeding" article) + for (int i = 0; i < n; i++) { + closestDistSq[i] = distance(dataset[dsindices[i]], dataset[dsindices[index]], dataset.cols); + closestDistSq[i] = ensureSquareDistance<Distance>( closestDistSq[i] ); + currentPot += closestDistSq[i]; + } + + + const int numLocalTries = 1; + + // Choose each center + int centerCount; + for (centerCount = 1; centerCount < k; centerCount++) { + + // Repeat several trials + double bestNewPot = -1; + int bestNewIndex = 0; + for (int localTrial = 0; localTrial < numLocalTries; localTrial++) { + + // Choose our center - have to be slightly careful to return a valid answer even accounting + // for possible rounding errors + double randVal = rand_double(currentPot); + for (index = 0; index < n-1; index++) { + if (randVal <= closestDistSq[index]) break; + else randVal -= closestDistSq[index]; + } + + // Compute the new potential + double newPot = 0; + for (int i = 0; i < n; i++) { + DistanceType dist = distance(dataset[dsindices[i]], dataset[dsindices[index]], dataset.cols); + newPot += std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] ); + } + + // Store the best result + if ((bestNewPot < 0)||(newPot < bestNewPot)) { + bestNewPot = newPot; + bestNewIndex = index; + } + } + + // Add the appropriate center + centers[centerCount] = dsindices[bestNewIndex]; + currentPot = bestNewPot; + for (int i = 0; i < n; i++) { + DistanceType dist = distance(dataset[dsindices[i]], dataset[dsindices[bestNewIndex]], dataset.cols); + closestDistSq[i] = std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] ); + } + } + + centers_length = centerCount; + + delete[] closestDistSq; + } + + + /** + * Chooses the initial centers in a way inspired by Gonzales (by Pierre-Emmanuel Viel): + * select the first point of the list as a candidate, then parse the points list. If another + * point is further than current candidate from the other centers, test if it is a good center + * of a local aggregation. If it is, replace current candidate by this point. And so on... + * + * Used with KMeansIndex that computes centers coordinates by averaging positions of clusters points, + * this doesn't make a real difference with previous methods. But used with HierarchicalClusteringIndex + * class that pick centers among existing points instead of computing the barycenters, there is a real + * improvement. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * Returns: + */ + void GroupWiseCenterChooser(int k, int* dsindices, int indices_length, int* centers, int& centers_length) + { + const float kSpeedUpFactor = 1.3f; + + int n = indices_length; + + DistanceType* closestDistSq = new DistanceType[n]; + + // Choose one random center and set the closestDistSq values + int index = rand_int(n); + assert(index >=0 && index < n); + centers[0] = dsindices[index]; + + for (int i = 0; i < n; i++) { + closestDistSq[i] = distance(dataset[dsindices[i]], dataset[dsindices[index]], dataset.cols); + } + + + // Choose each center + int centerCount; + for (centerCount = 1; centerCount < k; centerCount++) { + + // Repeat several trials + double bestNewPot = -1; + int bestNewIndex = 0; + DistanceType furthest = 0; + for (index = 0; index < n; index++) { + + // We will test only the potential of the points further than current candidate + if( closestDistSq[index] > kSpeedUpFactor * (float)furthest ) { + + // Compute the new potential + double newPot = 0; + for (int i = 0; i < n; i++) { + newPot += std::min( distance(dataset[dsindices[i]], dataset[dsindices[index]], dataset.cols) + , closestDistSq[i] ); + } + + // Store the best result + if ((bestNewPot < 0)||(newPot <= bestNewPot)) { + bestNewPot = newPot; + bestNewIndex = index; + furthest = closestDistSq[index]; + } + } + } + + // Add the appropriate center + centers[centerCount] = dsindices[bestNewIndex]; + for (int i = 0; i < n; i++) { + closestDistSq[i] = std::min( distance(dataset[dsindices[i]], dataset[dsindices[bestNewIndex]], dataset.cols) + , closestDistSq[i] ); + } + } + + centers_length = centerCount; + + delete[] closestDistSq; + } + + +public: + + + /** + * Index constructor + * + * Params: + * inputData = dataset with the input features + * params = parameters passed to the hierarchical k-means algorithm + */ + HierarchicalClusteringIndex(const Matrix<ElementType>& inputData, const IndexParams& index_params = HierarchicalClusteringIndexParams(), + Distance d = Distance()) + : dataset(inputData), params(index_params), root(NULL), indices(NULL), distance(d) + { + memoryCounter = 0; + + size_ = dataset.rows; + veclen_ = dataset.cols; + + branching_ = get_param(params,"branching",32); + centers_init_ = get_param(params,"centers_init", FLANN_CENTERS_RANDOM); + trees_ = get_param(params,"trees",4); + leaf_size_ = get_param(params,"leaf_size",100); + + if (centers_init_==FLANN_CENTERS_RANDOM) { + chooseCenters = &HierarchicalClusteringIndex::chooseCentersRandom; + } + else if (centers_init_==FLANN_CENTERS_GONZALES) { + chooseCenters = &HierarchicalClusteringIndex::chooseCentersGonzales; + } + else if (centers_init_==FLANN_CENTERS_KMEANSPP) { + chooseCenters = &HierarchicalClusteringIndex::chooseCentersKMeanspp; + } + else if (centers_init_==FLANN_CENTERS_GROUPWISE) { + chooseCenters = &HierarchicalClusteringIndex::GroupWiseCenterChooser; + } + else { + throw FLANNException("Unknown algorithm for choosing initial centers."); + } + + trees_ = get_param(params,"trees",4); + root = new NodePtr[trees_]; + indices = new int*[trees_]; + + for (int i=0; i<trees_; ++i) { + root[i] = NULL; + indices[i] = NULL; + } + } + + HierarchicalClusteringIndex(const HierarchicalClusteringIndex&); + HierarchicalClusteringIndex& operator=(const HierarchicalClusteringIndex&); + + /** + * Index destructor. + * + * Release the memory used by the index. + */ + virtual ~HierarchicalClusteringIndex() + { + free_elements(); + + if (root!=NULL) { + delete[] root; + } + + if (indices!=NULL) { + delete[] indices; + } + } + + + /** + * Release the inner elements of indices[] + */ + void free_elements() + { + if (indices!=NULL) { + for(int i=0; i<trees_; ++i) { + if (indices[i]!=NULL) { + delete[] indices[i]; + indices[i] = NULL; + } + } + } + } + + + /** + * Returns size of index. + */ + size_t size() const + { + return size_; + } + + /** + * Returns the length of an index feature. + */ + size_t veclen() const + { + return veclen_; + } + + + /** + * Computes the inde memory usage + * Returns: memory used by the index + */ + int usedMemory() const + { + return pool.usedMemory+pool.wastedMemory+memoryCounter; + } + + /** + * Builds the index + */ + void buildIndex() + { + if (branching_<2) { + throw FLANNException("Branching factor must be at least 2"); + } + + free_elements(); + + for (int i=0; i<trees_; ++i) { + indices[i] = new int[size_]; + for (size_t j=0; j<size_; ++j) { + indices[i][j] = (int)j; + } + root[i] = pool.allocate<Node>(); + computeClustering(root[i], indices[i], (int)size_, branching_,0); + } + } + + + flann_algorithm_t getType() const + { + return FLANN_INDEX_HIERARCHICAL; + } + + + void saveIndex(FILE* stream) + { + save_value(stream, branching_); + save_value(stream, trees_); + save_value(stream, centers_init_); + save_value(stream, leaf_size_); + save_value(stream, memoryCounter); + for (int i=0; i<trees_; ++i) { + save_value(stream, *indices[i], size_); + save_tree(stream, root[i], i); + } + + } + + + void loadIndex(FILE* stream) + { + free_elements(); + + if (root!=NULL) { + delete[] root; + } + + if (indices!=NULL) { + delete[] indices; + } + + load_value(stream, branching_); + load_value(stream, trees_); + load_value(stream, centers_init_); + load_value(stream, leaf_size_); + load_value(stream, memoryCounter); + + indices = new int*[trees_]; + root = new NodePtr[trees_]; + for (int i=0; i<trees_; ++i) { + indices[i] = new int[size_]; + load_value(stream, *indices[i], size_); + load_tree(stream, root[i], i); + } + + params["algorithm"] = getType(); + params["branching"] = branching_; + params["trees"] = trees_; + params["centers_init"] = centers_init_; + params["leaf_size"] = leaf_size_; + } + + + /** + * Find set of nearest neighbors to vec. Their indices are stored inside + * the result object. + * + * Params: + * result = the result object in which the indices of the nearest-neighbors are stored + * vec = the vector for which to search the nearest neighbors + * searchParams = parameters that influence the search algorithm (checks) + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + + int maxChecks = get_param(searchParams,"checks",32); + + // Priority queue storing intermediate branches in the best-bin-first search + Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_); + + std::vector<bool> checked(size_,false); + int checks = 0; + for (int i=0; i<trees_; ++i) { + findNN(root[i], result, vec, checks, maxChecks, heap, checked); + } + + BranchSt branch; + while (heap->popMin(branch) && (checks<maxChecks || !result.full())) { + NodePtr node = branch.node; + findNN(node, result, vec, checks, maxChecks, heap, checked); + } + assert(result.full()); + + delete heap; + + } + + IndexParams getParameters() const + { + return params; + } + + +private: + + /** + * Struture representing a node in the hierarchical k-means tree. + */ + struct Node + { + /** + * The cluster center index + */ + int pivot; + /** + * The cluster size (number of points in the cluster) + */ + int size; + /** + * Child nodes (only for non-terminal nodes) + */ + Node** childs; + /** + * Node points (only for terminal nodes) + */ + int* indices; + /** + * Level + */ + int level; + }; + typedef Node* NodePtr; + + + + /** + * Alias definition for a nicer syntax. + */ + typedef BranchStruct<NodePtr, DistanceType> BranchSt; + + + + void save_tree(FILE* stream, NodePtr node, int num) + { + save_value(stream, *node); + if (node->childs==NULL) { + int indices_offset = (int)(node->indices - indices[num]); + save_value(stream, indices_offset); + } + else { + for(int i=0; i<branching_; ++i) { + save_tree(stream, node->childs[i], num); + } + } + } + + + void load_tree(FILE* stream, NodePtr& node, int num) + { + node = pool.allocate<Node>(); + load_value(stream, *node); + if (node->childs==NULL) { + int indices_offset; + load_value(stream, indices_offset); + node->indices = indices[num] + indices_offset; + } + else { + node->childs = pool.allocate<NodePtr>(branching_); + for(int i=0; i<branching_; ++i) { + load_tree(stream, node->childs[i], num); + } + } + } + + + + + void computeLabels(int* dsindices, int indices_length, int* centers, int centers_length, int* labels, DistanceType& cost) + { + cost = 0; + for (int i=0; i<indices_length; ++i) { + ElementType* point = dataset[dsindices[i]]; + DistanceType dist = distance(point, dataset[centers[0]], veclen_); + labels[i] = 0; + for (int j=1; j<centers_length; ++j) { + DistanceType new_dist = distance(point, dataset[centers[j]], veclen_); + if (dist>new_dist) { + labels[i] = j; + dist = new_dist; + } + } + cost += dist; + } + } + + /** + * The method responsible with actually doing the recursive hierarchical + * clustering + * + * Params: + * node = the node to cluster + * indices = indices of the points belonging to the current node + * branching = the branching factor to use in the clustering + * + * TODO: for 1-sized clusters don't store a cluster center (it's the same as the single cluster point) + */ + void computeClustering(NodePtr node, int* dsindices, int indices_length, int branching, int level) + { + node->size = indices_length; + node->level = level; + + if (indices_length < leaf_size_) { // leaf node + node->indices = dsindices; + std::sort(node->indices,node->indices+indices_length); + node->childs = NULL; + return; + } + + std::vector<int> centers(branching); + std::vector<int> labels(indices_length); + + int centers_length; + (this->*chooseCenters)(branching, dsindices, indices_length, ¢ers[0], centers_length); + + if (centers_length<branching) { + node->indices = dsindices; + std::sort(node->indices,node->indices+indices_length); + node->childs = NULL; + return; + } + + + // assign points to clusters + DistanceType cost; + computeLabels(dsindices, indices_length, ¢ers[0], centers_length, &labels[0], cost); + + node->childs = pool.allocate<NodePtr>(branching); + int start = 0; + int end = start; + for (int i=0; i<branching; ++i) { + for (int j=0; j<indices_length; ++j) { + if (labels[j]==i) { + std::swap(dsindices[j],dsindices[end]); + std::swap(labels[j],labels[end]); + end++; + } + } + + node->childs[i] = pool.allocate<Node>(); + node->childs[i]->pivot = centers[i]; + node->childs[i]->indices = NULL; + computeClustering(node->childs[i],dsindices+start, end-start, branching, level+1); + start=end; + } + } + + + + /** + * Performs one descent in the hierarchical k-means tree. The branches not + * visited are stored in a priority queue. + * + * Params: + * node = node to explore + * result = container for the k-nearest neighbors found + * vec = query points + * checks = how many points in the dataset have been checked so far + * maxChecks = maximum dataset points to checks + */ + + + void findNN(NodePtr node, ResultSet<DistanceType>& result, const ElementType* vec, int& checks, int maxChecks, + Heap<BranchSt>* heap, std::vector<bool>& checked) + { + if (node->childs==NULL) { + if (checks>=maxChecks) { + if (result.full()) return; + } + for (int i=0; i<node->size; ++i) { + int index = node->indices[i]; + if (!checked[index]) { + DistanceType dist = distance(dataset[index], vec, veclen_); + result.addPoint(dist, index); + checked[index] = true; + ++checks; + } + } + } + else { + DistanceType* domain_distances = new DistanceType[branching_]; + int best_index = 0; + domain_distances[best_index] = distance(vec, dataset[node->childs[best_index]->pivot], veclen_); + for (int i=1; i<branching_; ++i) { + domain_distances[i] = distance(vec, dataset[node->childs[i]->pivot], veclen_); + if (domain_distances[i]<domain_distances[best_index]) { + best_index = i; + } + } + for (int i=0; i<branching_; ++i) { + if (i!=best_index) { + heap->insert(BranchSt(node->childs[i],domain_distances[i])); + } + } + delete[] domain_distances; + findNN(node->childs[best_index],result,vec, checks, maxChecks, heap, checked); + } + } + +private: + + + /** + * The dataset used by this index + */ + const Matrix<ElementType> dataset; + + /** + * Parameters used by this index + */ + IndexParams params; + + + /** + * Number of features in the dataset. + */ + size_t size_; + + /** + * Length of each feature. + */ + size_t veclen_; + + /** + * The root node in the tree. + */ + NodePtr* root; + + /** + * Array of indices to vectors in the dataset. + */ + int** indices; + + + /** + * The distance + */ + Distance distance; + + /** + * Pooled memory allocator. + * + * Using a pooled memory allocator is more efficient + * than allocating memory directly when there is a large + * number small of memory allocations. + */ + PooledAllocator pool; + + /** + * Memory occupied by the index. + */ + int memoryCounter; + + /** index parameters */ + int branching_; + int trees_; + flann_centers_init_t centers_init_; + int leaf_size_; + + +}; + +} + +#endif /* OPENCV_FLANN_HIERARCHICAL_CLUSTERING_INDEX_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/index_testing.h b/thirdparty/linux/include/opencv2/flann/index_testing.h new file mode 100644 index 0000000..d764004 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/index_testing.h @@ -0,0 +1,318 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_INDEX_TESTING_H_ +#define OPENCV_FLANN_INDEX_TESTING_H_ + +#include <cstring> +#include <cassert> +#include <cmath> + +#include "matrix.h" +#include "nn_index.h" +#include "result_set.h" +#include "logger.h" +#include "timer.h" + + +namespace cvflann +{ + +inline int countCorrectMatches(int* neighbors, int* groundTruth, int n) +{ + int count = 0; + for (int i=0; i<n; ++i) { + for (int k=0; k<n; ++k) { + if (neighbors[i]==groundTruth[k]) { + count++; + break; + } + } + } + return count; +} + + +template <typename Distance> +typename Distance::ResultType computeDistanceRaport(const Matrix<typename Distance::ElementType>& inputData, typename Distance::ElementType* target, + int* neighbors, int* groundTruth, int veclen, int n, const Distance& distance) +{ + typedef typename Distance::ResultType DistanceType; + + DistanceType ret = 0; + for (int i=0; i<n; ++i) { + DistanceType den = distance(inputData[groundTruth[i]], target, veclen); + DistanceType num = distance(inputData[neighbors[i]], target, veclen); + + if ((den==0)&&(num==0)) { + ret += 1; + } + else { + ret += num/den; + } + } + + return ret; +} + +template <typename Distance> +float search_with_ground_truth(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData, + const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches, int nn, int checks, + float& time, typename Distance::ResultType& dist, const Distance& distance, int skipMatches) +{ + typedef typename Distance::ResultType DistanceType; + + if (matches.cols<size_t(nn)) { + Logger::info("matches.cols=%d, nn=%d\n",matches.cols,nn); + + throw FLANNException("Ground truth is not computed for as many neighbors as requested"); + } + + KNNResultSet<DistanceType> resultSet(nn+skipMatches); + SearchParams searchParams(checks); + + std::vector<int> indices(nn+skipMatches); + std::vector<DistanceType> dists(nn+skipMatches); + int* neighbors = &indices[skipMatches]; + + int correct = 0; + DistanceType distR = 0; + StartStopTimer t; + int repeats = 0; + while (t.value<0.2) { + repeats++; + t.start(); + correct = 0; + distR = 0; + for (size_t i = 0; i < testData.rows; i++) { + resultSet.init(&indices[0], &dists[0]); + index.findNeighbors(resultSet, testData[i], searchParams); + + correct += countCorrectMatches(neighbors,matches[i], nn); + distR += computeDistanceRaport<Distance>(inputData, testData[i], neighbors, matches[i], (int)testData.cols, nn, distance); + } + t.stop(); + } + time = float(t.value/repeats); + + float precicion = (float)correct/(nn*testData.rows); + + dist = distR/(testData.rows*nn); + + Logger::info("%8d %10.4g %10.5g %10.5g %10.5g\n", + checks, precicion, time, 1000.0 * time / testData.rows, dist); + + return precicion; +} + + +template <typename Distance> +float test_index_checks(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData, + const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches, + int checks, float& precision, const Distance& distance, int nn = 1, int skipMatches = 0) +{ + typedef typename Distance::ResultType DistanceType; + + Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n"); + Logger::info("---------------------------------------------------------\n"); + + float time = 0; + DistanceType dist = 0; + precision = search_with_ground_truth(index, inputData, testData, matches, nn, checks, time, dist, distance, skipMatches); + + return time; +} + +template <typename Distance> +float test_index_precision(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData, + const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches, + float precision, int& checks, const Distance& distance, int nn = 1, int skipMatches = 0) +{ + typedef typename Distance::ResultType DistanceType; + const float SEARCH_EPS = 0.001f; + + Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n"); + Logger::info("---------------------------------------------------------\n"); + + int c2 = 1; + float p2; + int c1 = 1; + //float p1; + float time; + DistanceType dist; + + p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches); + + if (p2>precision) { + Logger::info("Got as close as I can\n"); + checks = c2; + return time; + } + + while (p2<precision) { + c1 = c2; + //p1 = p2; + c2 *=2; + p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches); + } + + int cx; + float realPrecision; + if (fabs(p2-precision)>SEARCH_EPS) { + Logger::info("Start linear estimation\n"); + // after we got to values in the vecinity of the desired precision + // use linear approximation get a better estimation + + cx = (c1+c2)/2; + realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches); + while (fabs(realPrecision-precision)>SEARCH_EPS) { + + if (realPrecision<precision) { + c1 = cx; + } + else { + c2 = cx; + } + cx = (c1+c2)/2; + if (cx==c1) { + Logger::info("Got as close as I can\n"); + break; + } + realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches); + } + + c2 = cx; + p2 = realPrecision; + + } + else { + Logger::info("No need for linear estimation\n"); + cx = c2; + realPrecision = p2; + } + + checks = cx; + return time; +} + + +template <typename Distance> +void test_index_precisions(NNIndex<Distance>& index, const Matrix<typename Distance::ElementType>& inputData, + const Matrix<typename Distance::ElementType>& testData, const Matrix<int>& matches, + float* precisions, int precisions_length, const Distance& distance, int nn = 1, int skipMatches = 0, float maxTime = 0) +{ + typedef typename Distance::ResultType DistanceType; + + const float SEARCH_EPS = 0.001; + + // make sure precisions array is sorted + std::sort(precisions, precisions+precisions_length); + + int pindex = 0; + float precision = precisions[pindex]; + + Logger::info(" Nodes Precision(%) Time(s) Time/vec(ms) Mean dist\n"); + Logger::info("---------------------------------------------------------\n"); + + int c2 = 1; + float p2; + + int c1 = 1; + float p1; + + float time; + DistanceType dist; + + p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches); + + // if precision for 1 run down the tree is already + // better then some of the requested precisions, then + // skip those + while (precisions[pindex]<p2 && pindex<precisions_length) { + pindex++; + } + + if (pindex==precisions_length) { + Logger::info("Got as close as I can\n"); + return; + } + + for (int i=pindex; i<precisions_length; ++i) { + + precision = precisions[i]; + while (p2<precision) { + c1 = c2; + p1 = p2; + c2 *=2; + p2 = search_with_ground_truth(index, inputData, testData, matches, nn, c2, time, dist, distance, skipMatches); + if ((maxTime> 0)&&(time > maxTime)&&(p2<precision)) return; + } + + int cx; + float realPrecision; + if (fabs(p2-precision)>SEARCH_EPS) { + Logger::info("Start linear estimation\n"); + // after we got to values in the vecinity of the desired precision + // use linear approximation get a better estimation + + cx = (c1+c2)/2; + realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches); + while (fabs(realPrecision-precision)>SEARCH_EPS) { + + if (realPrecision<precision) { + c1 = cx; + } + else { + c2 = cx; + } + cx = (c1+c2)/2; + if (cx==c1) { + Logger::info("Got as close as I can\n"); + break; + } + realPrecision = search_with_ground_truth(index, inputData, testData, matches, nn, cx, time, dist, distance, skipMatches); + } + + c2 = cx; + p2 = realPrecision; + + } + else { + Logger::info("No need for linear estimation\n"); + cx = c2; + realPrecision = p2; + } + + } +} + +} + +#endif //OPENCV_FLANN_INDEX_TESTING_H_ diff --git a/thirdparty/linux/include/opencv2/flann/kdtree_index.h b/thirdparty/linux/include/opencv2/flann/kdtree_index.h new file mode 100644 index 0000000..dc0971c --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/kdtree_index.h @@ -0,0 +1,621 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_KDTREE_INDEX_H_ +#define OPENCV_FLANN_KDTREE_INDEX_H_ + +#include <algorithm> +#include <map> +#include <cassert> +#include <cstring> + +#include "general.h" +#include "nn_index.h" +#include "dynamic_bitset.h" +#include "matrix.h" +#include "result_set.h" +#include "heap.h" +#include "allocator.h" +#include "random.h" +#include "saving.h" + + +namespace cvflann +{ + +struct KDTreeIndexParams : public IndexParams +{ + KDTreeIndexParams(int trees = 4) + { + (*this)["algorithm"] = FLANN_INDEX_KDTREE; + (*this)["trees"] = trees; + } +}; + + +/** + * Randomized kd-tree index + * + * Contains the k-d trees and other information for indexing a set of points + * for nearest-neighbor matching. + */ +template <typename Distance> +class KDTreeIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + + /** + * KDTree constructor + * + * Params: + * inputData = dataset with the input features + * params = parameters passed to the kdtree algorithm + */ + KDTreeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KDTreeIndexParams(), + Distance d = Distance() ) : + dataset_(inputData), index_params_(params), distance_(d) + { + size_ = dataset_.rows; + veclen_ = dataset_.cols; + + trees_ = get_param(index_params_,"trees",4); + tree_roots_ = new NodePtr[trees_]; + + // Create a permutable array of indices to the input vectors. + vind_.resize(size_); + for (size_t i = 0; i < size_; ++i) { + vind_[i] = int(i); + } + + mean_ = new DistanceType[veclen_]; + var_ = new DistanceType[veclen_]; + } + + + KDTreeIndex(const KDTreeIndex&); + KDTreeIndex& operator=(const KDTreeIndex&); + + /** + * Standard destructor + */ + ~KDTreeIndex() + { + if (tree_roots_!=NULL) { + delete[] tree_roots_; + } + delete[] mean_; + delete[] var_; + } + + /** + * Builds the index + */ + void buildIndex() + { + /* Construct the randomized trees. */ + for (int i = 0; i < trees_; i++) { + /* Randomize the order of vectors to allow for unbiased sampling. */ + std::random_shuffle(vind_.begin(), vind_.end()); + tree_roots_[i] = divideTree(&vind_[0], int(size_) ); + } + } + + + flann_algorithm_t getType() const + { + return FLANN_INDEX_KDTREE; + } + + + void saveIndex(FILE* stream) + { + save_value(stream, trees_); + for (int i=0; i<trees_; ++i) { + save_tree(stream, tree_roots_[i]); + } + } + + + + void loadIndex(FILE* stream) + { + load_value(stream, trees_); + if (tree_roots_!=NULL) { + delete[] tree_roots_; + } + tree_roots_ = new NodePtr[trees_]; + for (int i=0; i<trees_; ++i) { + load_tree(stream,tree_roots_[i]); + } + + index_params_["algorithm"] = getType(); + index_params_["trees"] = tree_roots_; + } + + /** + * Returns size of index. + */ + size_t size() const + { + return size_; + } + + /** + * Returns the length of an index feature. + */ + size_t veclen() const + { + return veclen_; + } + + /** + * Computes the inde memory usage + * Returns: memory used by the index + */ + int usedMemory() const + { + return int(pool_.usedMemory+pool_.wastedMemory+dataset_.rows*sizeof(int)); // pool memory and vind array memory + } + + /** + * Find set of nearest neighbors to vec. Their indices are stored inside + * the result object. + * + * Params: + * result = the result object in which the indices of the nearest-neighbors are stored + * vec = the vector for which to search the nearest neighbors + * maxCheck = the maximum number of restarts (in a best-bin-first manner) + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + int maxChecks = get_param(searchParams,"checks", 32); + float epsError = 1+get_param(searchParams,"eps",0.0f); + + if (maxChecks==FLANN_CHECKS_UNLIMITED) { + getExactNeighbors(result, vec, epsError); + } + else { + getNeighbors(result, vec, maxChecks, epsError); + } + } + + IndexParams getParameters() const + { + return index_params_; + } + +private: + + + /*--------------------- Internal Data Structures --------------------------*/ + struct Node + { + /** + * Dimension used for subdivision. + */ + int divfeat; + /** + * The values used for subdivision. + */ + DistanceType divval; + /** + * The child nodes. + */ + Node* child1, * child2; + }; + typedef Node* NodePtr; + typedef BranchStruct<NodePtr, DistanceType> BranchSt; + typedef BranchSt* Branch; + + + + void save_tree(FILE* stream, NodePtr tree) + { + save_value(stream, *tree); + if (tree->child1!=NULL) { + save_tree(stream, tree->child1); + } + if (tree->child2!=NULL) { + save_tree(stream, tree->child2); + } + } + + + void load_tree(FILE* stream, NodePtr& tree) + { + tree = pool_.allocate<Node>(); + load_value(stream, *tree); + if (tree->child1!=NULL) { + load_tree(stream, tree->child1); + } + if (tree->child2!=NULL) { + load_tree(stream, tree->child2); + } + } + + + /** + * Create a tree node that subdivides the list of vecs from vind[first] + * to vind[last]. The routine is called recursively on each sublist. + * Place a pointer to this new tree node in the location pTree. + * + * Params: pTree = the new node to create + * first = index of the first vector + * last = index of the last vector + */ + NodePtr divideTree(int* ind, int count) + { + NodePtr node = pool_.allocate<Node>(); // allocate memory + + /* If too few exemplars remain, then make this a leaf node. */ + if ( count == 1) { + node->child1 = node->child2 = NULL; /* Mark as leaf node. */ + node->divfeat = *ind; /* Store index of this vec. */ + } + else { + int idx; + int cutfeat; + DistanceType cutval; + meanSplit(ind, count, idx, cutfeat, cutval); + + node->divfeat = cutfeat; + node->divval = cutval; + node->child1 = divideTree(ind, idx); + node->child2 = divideTree(ind+idx, count-idx); + } + + return node; + } + + + /** + * Choose which feature to use in order to subdivide this set of vectors. + * Make a random choice among those with the highest variance, and use + * its variance as the threshold value. + */ + void meanSplit(int* ind, int count, int& index, int& cutfeat, DistanceType& cutval) + { + memset(mean_,0,veclen_*sizeof(DistanceType)); + memset(var_,0,veclen_*sizeof(DistanceType)); + + /* Compute mean values. Only the first SAMPLE_MEAN values need to be + sampled to get a good estimate. + */ + int cnt = std::min((int)SAMPLE_MEAN+1, count); + for (int j = 0; j < cnt; ++j) { + ElementType* v = dataset_[ind[j]]; + for (size_t k=0; k<veclen_; ++k) { + mean_[k] += v[k]; + } + } + for (size_t k=0; k<veclen_; ++k) { + mean_[k] /= cnt; + } + + /* Compute variances (no need to divide by count). */ + for (int j = 0; j < cnt; ++j) { + ElementType* v = dataset_[ind[j]]; + for (size_t k=0; k<veclen_; ++k) { + DistanceType dist = v[k] - mean_[k]; + var_[k] += dist * dist; + } + } + /* Select one of the highest variance indices at random. */ + cutfeat = selectDivision(var_); + cutval = mean_[cutfeat]; + + int lim1, lim2; + planeSplit(ind, count, cutfeat, cutval, lim1, lim2); + + if (lim1>count/2) index = lim1; + else if (lim2<count/2) index = lim2; + else index = count/2; + + /* If either list is empty, it means that all remaining features + * are identical. Split in the middle to maintain a balanced tree. + */ + if ((lim1==count)||(lim2==0)) index = count/2; + } + + + /** + * Select the top RAND_DIM largest values from v and return the index of + * one of these selected at random. + */ + int selectDivision(DistanceType* v) + { + int num = 0; + size_t topind[RAND_DIM]; + + /* Create a list of the indices of the top RAND_DIM values. */ + for (size_t i = 0; i < veclen_; ++i) { + if ((num < RAND_DIM)||(v[i] > v[topind[num-1]])) { + /* Put this element at end of topind. */ + if (num < RAND_DIM) { + topind[num++] = i; /* Add to list. */ + } + else { + topind[num-1] = i; /* Replace last element. */ + } + /* Bubble end value down to right location by repeated swapping. */ + int j = num - 1; + while (j > 0 && v[topind[j]] > v[topind[j-1]]) { + std::swap(topind[j], topind[j-1]); + --j; + } + } + } + /* Select a random integer in range [0,num-1], and return that index. */ + int rnd = rand_int(num); + return (int)topind[rnd]; + } + + + /** + * Subdivide the list of points by a plane perpendicular on axe corresponding + * to the 'cutfeat' dimension at 'cutval' position. + * + * On return: + * dataset[ind[0..lim1-1]][cutfeat]<cutval + * dataset[ind[lim1..lim2-1]][cutfeat]==cutval + * dataset[ind[lim2..count]][cutfeat]>cutval + */ + void planeSplit(int* ind, int count, int cutfeat, DistanceType cutval, int& lim1, int& lim2) + { + /* Move vector indices for left subtree to front of list. */ + int left = 0; + int right = count-1; + for (;; ) { + while (left<=right && dataset_[ind[left]][cutfeat]<cutval) ++left; + while (left<=right && dataset_[ind[right]][cutfeat]>=cutval) --right; + if (left>right) break; + std::swap(ind[left], ind[right]); ++left; --right; + } + lim1 = left; + right = count-1; + for (;; ) { + while (left<=right && dataset_[ind[left]][cutfeat]<=cutval) ++left; + while (left<=right && dataset_[ind[right]][cutfeat]>cutval) --right; + if (left>right) break; + std::swap(ind[left], ind[right]); ++left; --right; + } + lim2 = left; + } + + /** + * Performs an exact nearest neighbor search. The exact search performs a full + * traversal of the tree. + */ + void getExactNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, float epsError) + { + // checkID -= 1; /* Set a different unique ID for each search. */ + + if (trees_ > 1) { + fprintf(stderr,"It doesn't make any sense to use more than one tree for exact search"); + } + if (trees_>0) { + searchLevelExact(result, vec, tree_roots_[0], 0.0, epsError); + } + assert(result.full()); + } + + /** + * Performs the approximate nearest-neighbor search. The search is approximate + * because the tree traversal is abandoned after a given number of descends in + * the tree. + */ + void getNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, int maxCheck, float epsError) + { + int i; + BranchSt branch; + + int checkCount = 0; + Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_); + DynamicBitset checked(size_); + + /* Search once through each tree down to root. */ + for (i = 0; i < trees_; ++i) { + searchLevel(result, vec, tree_roots_[i], 0, checkCount, maxCheck, epsError, heap, checked); + } + + /* Keep searching other branches from heap until finished. */ + while ( heap->popMin(branch) && (checkCount < maxCheck || !result.full() )) { + searchLevel(result, vec, branch.node, branch.mindist, checkCount, maxCheck, epsError, heap, checked); + } + + delete heap; + + assert(result.full()); + } + + + /** + * Search starting from a given node of the tree. Based on any mismatches at + * higher levels, all exemplars below this level must have a distance of + * at least "mindistsq". + */ + void searchLevel(ResultSet<DistanceType>& result_set, const ElementType* vec, NodePtr node, DistanceType mindist, int& checkCount, int maxCheck, + float epsError, Heap<BranchSt>* heap, DynamicBitset& checked) + { + if (result_set.worstDist()<mindist) { + // printf("Ignoring branch, too far\n"); + return; + } + + /* If this is a leaf node, then do check and return. */ + if ((node->child1 == NULL)&&(node->child2 == NULL)) { + /* Do not check same node more than once when searching multiple trees. + Once a vector is checked, we set its location in vind to the + current checkID. + */ + int index = node->divfeat; + if ( checked.test(index) || ((checkCount>=maxCheck)&& result_set.full()) ) return; + checked.set(index); + checkCount++; + + DistanceType dist = distance_(dataset_[index], vec, veclen_); + result_set.addPoint(dist,index); + + return; + } + + /* Which child branch should be taken first? */ + ElementType val = vec[node->divfeat]; + DistanceType diff = val - node->divval; + NodePtr bestChild = (diff < 0) ? node->child1 : node->child2; + NodePtr otherChild = (diff < 0) ? node->child2 : node->child1; + + /* Create a branch record for the branch not taken. Add distance + of this feature boundary (we don't attempt to correct for any + use of this feature in a parent node, which is unlikely to + happen and would have only a small effect). Don't bother + adding more branches to heap after halfway point, as cost of + adding exceeds their value. + */ + + DistanceType new_distsq = mindist + distance_.accum_dist(val, node->divval, node->divfeat); + // if (2 * checkCount < maxCheck || !result.full()) { + if ((new_distsq*epsError < result_set.worstDist())|| !result_set.full()) { + heap->insert( BranchSt(otherChild, new_distsq) ); + } + + /* Call recursively to search next level down. */ + searchLevel(result_set, vec, bestChild, mindist, checkCount, maxCheck, epsError, heap, checked); + } + + /** + * Performs an exact search in the tree starting from a node. + */ + void searchLevelExact(ResultSet<DistanceType>& result_set, const ElementType* vec, const NodePtr node, DistanceType mindist, const float epsError) + { + /* If this is a leaf node, then do check and return. */ + if ((node->child1 == NULL)&&(node->child2 == NULL)) { + int index = node->divfeat; + DistanceType dist = distance_(dataset_[index], vec, veclen_); + result_set.addPoint(dist,index); + return; + } + + /* Which child branch should be taken first? */ + ElementType val = vec[node->divfeat]; + DistanceType diff = val - node->divval; + NodePtr bestChild = (diff < 0) ? node->child1 : node->child2; + NodePtr otherChild = (diff < 0) ? node->child2 : node->child1; + + /* Create a branch record for the branch not taken. Add distance + of this feature boundary (we don't attempt to correct for any + use of this feature in a parent node, which is unlikely to + happen and would have only a small effect). Don't bother + adding more branches to heap after halfway point, as cost of + adding exceeds their value. + */ + + DistanceType new_distsq = mindist + distance_.accum_dist(val, node->divval, node->divfeat); + + /* Call recursively to search next level down. */ + searchLevelExact(result_set, vec, bestChild, mindist, epsError); + + if (new_distsq*epsError<=result_set.worstDist()) { + searchLevelExact(result_set, vec, otherChild, new_distsq, epsError); + } + } + + +private: + + enum + { + /** + * To improve efficiency, only SAMPLE_MEAN random values are used to + * compute the mean and variance at each level when building a tree. + * A value of 100 seems to perform as well as using all values. + */ + SAMPLE_MEAN = 100, + /** + * Top random dimensions to consider + * + * When creating random trees, the dimension on which to subdivide is + * selected at random from among the top RAND_DIM dimensions with the + * highest variance. A value of 5 works well. + */ + RAND_DIM=5 + }; + + + /** + * Number of randomized trees that are used + */ + int trees_; + + /** + * Array of indices to vectors in the dataset. + */ + std::vector<int> vind_; + + /** + * The dataset used by this index + */ + const Matrix<ElementType> dataset_; + + IndexParams index_params_; + + size_t size_; + size_t veclen_; + + + DistanceType* mean_; + DistanceType* var_; + + + /** + * Array of k-d trees used to find neighbours. + */ + NodePtr* tree_roots_; + + /** + * Pooled memory allocator. + * + * Using a pooled memory allocator is more efficient + * than allocating memory directly when there is a large + * number small of memory allocations. + */ + PooledAllocator pool_; + + Distance distance_; + + +}; // class KDTreeForest + +} + +#endif //OPENCV_FLANN_KDTREE_INDEX_H_ diff --git a/thirdparty/linux/include/opencv2/flann/kdtree_single_index.h b/thirdparty/linux/include/opencv2/flann/kdtree_single_index.h new file mode 100644 index 0000000..30488ad --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/kdtree_single_index.h @@ -0,0 +1,634 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_ +#define OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_ + +#include <algorithm> +#include <map> +#include <cassert> +#include <cstring> + +#include "general.h" +#include "nn_index.h" +#include "matrix.h" +#include "result_set.h" +#include "heap.h" +#include "allocator.h" +#include "random.h" +#include "saving.h" + +namespace cvflann +{ + +struct KDTreeSingleIndexParams : public IndexParams +{ + KDTreeSingleIndexParams(int leaf_max_size = 10, bool reorder = true, int dim = -1) + { + (*this)["algorithm"] = FLANN_INDEX_KDTREE_SINGLE; + (*this)["leaf_max_size"] = leaf_max_size; + (*this)["reorder"] = reorder; + (*this)["dim"] = dim; + } +}; + + +/** + * Randomized kd-tree index + * + * Contains the k-d trees and other information for indexing a set of points + * for nearest-neighbor matching. + */ +template <typename Distance> +class KDTreeSingleIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + + /** + * KDTree constructor + * + * Params: + * inputData = dataset with the input features + * params = parameters passed to the kdtree algorithm + */ + KDTreeSingleIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KDTreeSingleIndexParams(), + Distance d = Distance() ) : + dataset_(inputData), index_params_(params), distance_(d) + { + size_ = dataset_.rows; + dim_ = dataset_.cols; + int dim_param = get_param(params,"dim",-1); + if (dim_param>0) dim_ = dim_param; + leaf_max_size_ = get_param(params,"leaf_max_size",10); + reorder_ = get_param(params,"reorder",true); + + // Create a permutable array of indices to the input vectors. + vind_.resize(size_); + for (size_t i = 0; i < size_; i++) { + vind_[i] = (int)i; + } + } + + KDTreeSingleIndex(const KDTreeSingleIndex&); + KDTreeSingleIndex& operator=(const KDTreeSingleIndex&); + + /** + * Standard destructor + */ + ~KDTreeSingleIndex() + { + if (reorder_) delete[] data_.data; + } + + /** + * Builds the index + */ + void buildIndex() + { + computeBoundingBox(root_bbox_); + root_node_ = divideTree(0, (int)size_, root_bbox_ ); // construct the tree + + if (reorder_) { + delete[] data_.data; + data_ = cvflann::Matrix<ElementType>(new ElementType[size_*dim_], size_, dim_); + for (size_t i=0; i<size_; ++i) { + for (size_t j=0; j<dim_; ++j) { + data_[i][j] = dataset_[vind_[i]][j]; + } + } + } + else { + data_ = dataset_; + } + } + + flann_algorithm_t getType() const + { + return FLANN_INDEX_KDTREE_SINGLE; + } + + + void saveIndex(FILE* stream) + { + save_value(stream, size_); + save_value(stream, dim_); + save_value(stream, root_bbox_); + save_value(stream, reorder_); + save_value(stream, leaf_max_size_); + save_value(stream, vind_); + if (reorder_) { + save_value(stream, data_); + } + save_tree(stream, root_node_); + } + + + void loadIndex(FILE* stream) + { + load_value(stream, size_); + load_value(stream, dim_); + load_value(stream, root_bbox_); + load_value(stream, reorder_); + load_value(stream, leaf_max_size_); + load_value(stream, vind_); + if (reorder_) { + load_value(stream, data_); + } + else { + data_ = dataset_; + } + load_tree(stream, root_node_); + + + index_params_["algorithm"] = getType(); + index_params_["leaf_max_size"] = leaf_max_size_; + index_params_["reorder"] = reorder_; + } + + /** + * Returns size of index. + */ + size_t size() const + { + return size_; + } + + /** + * Returns the length of an index feature. + */ + size_t veclen() const + { + return dim_; + } + + /** + * Computes the inde memory usage + * Returns: memory used by the index + */ + int usedMemory() const + { + return (int)(pool_.usedMemory+pool_.wastedMemory+dataset_.rows*sizeof(int)); // pool memory and vind array memory + } + + + /** + * \brief Perform k-nearest neighbor search + * \param[in] queries The query points for which to find the nearest neighbors + * \param[out] indices The indices of the nearest neighbors found + * \param[out] dists Distances to the nearest neighbors found + * \param[in] knn Number of nearest neighbors to return + * \param[in] params Search parameters + */ + void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params) + { + assert(queries.cols == veclen()); + assert(indices.rows >= queries.rows); + assert(dists.rows >= queries.rows); + assert(int(indices.cols) >= knn); + assert(int(dists.cols) >= knn); + + KNNSimpleResultSet<DistanceType> resultSet(knn); + for (size_t i = 0; i < queries.rows; i++) { + resultSet.init(indices[i], dists[i]); + findNeighbors(resultSet, queries[i], params); + } + } + + IndexParams getParameters() const + { + return index_params_; + } + + /** + * Find set of nearest neighbors to vec. Their indices are stored inside + * the result object. + * + * Params: + * result = the result object in which the indices of the nearest-neighbors are stored + * vec = the vector for which to search the nearest neighbors + * maxCheck = the maximum number of restarts (in a best-bin-first manner) + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + float epsError = 1+get_param(searchParams,"eps",0.0f); + + std::vector<DistanceType> dists(dim_,0); + DistanceType distsq = computeInitialDistances(vec, dists); + searchLevel(result, vec, root_node_, distsq, dists, epsError); + } + +private: + + + /*--------------------- Internal Data Structures --------------------------*/ + struct Node + { + /** + * Indices of points in leaf node + */ + int left, right; + /** + * Dimension used for subdivision. + */ + int divfeat; + /** + * The values used for subdivision. + */ + DistanceType divlow, divhigh; + /** + * The child nodes. + */ + Node* child1, * child2; + }; + typedef Node* NodePtr; + + + struct Interval + { + DistanceType low, high; + }; + + typedef std::vector<Interval> BoundingBox; + + typedef BranchStruct<NodePtr, DistanceType> BranchSt; + typedef BranchSt* Branch; + + + + + void save_tree(FILE* stream, NodePtr tree) + { + save_value(stream, *tree); + if (tree->child1!=NULL) { + save_tree(stream, tree->child1); + } + if (tree->child2!=NULL) { + save_tree(stream, tree->child2); + } + } + + + void load_tree(FILE* stream, NodePtr& tree) + { + tree = pool_.allocate<Node>(); + load_value(stream, *tree); + if (tree->child1!=NULL) { + load_tree(stream, tree->child1); + } + if (tree->child2!=NULL) { + load_tree(stream, tree->child2); + } + } + + + void computeBoundingBox(BoundingBox& bbox) + { + bbox.resize(dim_); + for (size_t i=0; i<dim_; ++i) { + bbox[i].low = (DistanceType)dataset_[0][i]; + bbox[i].high = (DistanceType)dataset_[0][i]; + } + for (size_t k=1; k<dataset_.rows; ++k) { + for (size_t i=0; i<dim_; ++i) { + if (dataset_[k][i]<bbox[i].low) bbox[i].low = (DistanceType)dataset_[k][i]; + if (dataset_[k][i]>bbox[i].high) bbox[i].high = (DistanceType)dataset_[k][i]; + } + } + } + + + /** + * Create a tree node that subdivides the list of vecs from vind[first] + * to vind[last]. The routine is called recursively on each sublist. + * Place a pointer to this new tree node in the location pTree. + * + * Params: pTree = the new node to create + * first = index of the first vector + * last = index of the last vector + */ + NodePtr divideTree(int left, int right, BoundingBox& bbox) + { + NodePtr node = pool_.allocate<Node>(); // allocate memory + + /* If too few exemplars remain, then make this a leaf node. */ + if ( (right-left) <= leaf_max_size_) { + node->child1 = node->child2 = NULL; /* Mark as leaf node. */ + node->left = left; + node->right = right; + + // compute bounding-box of leaf points + for (size_t i=0; i<dim_; ++i) { + bbox[i].low = (DistanceType)dataset_[vind_[left]][i]; + bbox[i].high = (DistanceType)dataset_[vind_[left]][i]; + } + for (int k=left+1; k<right; ++k) { + for (size_t i=0; i<dim_; ++i) { + if (bbox[i].low>dataset_[vind_[k]][i]) bbox[i].low=(DistanceType)dataset_[vind_[k]][i]; + if (bbox[i].high<dataset_[vind_[k]][i]) bbox[i].high=(DistanceType)dataset_[vind_[k]][i]; + } + } + } + else { + int idx; + int cutfeat; + DistanceType cutval; + middleSplit_(&vind_[0]+left, right-left, idx, cutfeat, cutval, bbox); + + node->divfeat = cutfeat; + + BoundingBox left_bbox(bbox); + left_bbox[cutfeat].high = cutval; + node->child1 = divideTree(left, left+idx, left_bbox); + + BoundingBox right_bbox(bbox); + right_bbox[cutfeat].low = cutval; + node->child2 = divideTree(left+idx, right, right_bbox); + + node->divlow = left_bbox[cutfeat].high; + node->divhigh = right_bbox[cutfeat].low; + + for (size_t i=0; i<dim_; ++i) { + bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low); + bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high); + } + } + + return node; + } + + void computeMinMax(int* ind, int count, int dim, ElementType& min_elem, ElementType& max_elem) + { + min_elem = dataset_[ind[0]][dim]; + max_elem = dataset_[ind[0]][dim]; + for (int i=1; i<count; ++i) { + ElementType val = dataset_[ind[i]][dim]; + if (val<min_elem) min_elem = val; + if (val>max_elem) max_elem = val; + } + } + + void middleSplit(int* ind, int count, int& index, int& cutfeat, DistanceType& cutval, const BoundingBox& bbox) + { + // find the largest span from the approximate bounding box + ElementType max_span = bbox[0].high-bbox[0].low; + cutfeat = 0; + cutval = (bbox[0].high+bbox[0].low)/2; + for (size_t i=1; i<dim_; ++i) { + ElementType span = bbox[i].high-bbox[i].low; + if (span>max_span) { + max_span = span; + cutfeat = i; + cutval = (bbox[i].high+bbox[i].low)/2; + } + } + + // compute exact span on the found dimension + ElementType min_elem, max_elem; + computeMinMax(ind, count, cutfeat, min_elem, max_elem); + cutval = (min_elem+max_elem)/2; + max_span = max_elem - min_elem; + + // check if a dimension of a largest span exists + size_t k = cutfeat; + for (size_t i=0; i<dim_; ++i) { + if (i==k) continue; + ElementType span = bbox[i].high-bbox[i].low; + if (span>max_span) { + computeMinMax(ind, count, i, min_elem, max_elem); + span = max_elem - min_elem; + if (span>max_span) { + max_span = span; + cutfeat = i; + cutval = (min_elem+max_elem)/2; + } + } + } + int lim1, lim2; + planeSplit(ind, count, cutfeat, cutval, lim1, lim2); + + if (lim1>count/2) index = lim1; + else if (lim2<count/2) index = lim2; + else index = count/2; + } + + + void middleSplit_(int* ind, int count, int& index, int& cutfeat, DistanceType& cutval, const BoundingBox& bbox) + { + const float EPS=0.00001f; + DistanceType max_span = bbox[0].high-bbox[0].low; + for (size_t i=1; i<dim_; ++i) { + DistanceType span = bbox[i].high-bbox[i].low; + if (span>max_span) { + max_span = span; + } + } + DistanceType max_spread = -1; + cutfeat = 0; + for (size_t i=0; i<dim_; ++i) { + DistanceType span = bbox[i].high-bbox[i].low; + if (span>(DistanceType)((1-EPS)*max_span)) { + ElementType min_elem, max_elem; + computeMinMax(ind, count, cutfeat, min_elem, max_elem); + DistanceType spread = (DistanceType)(max_elem-min_elem); + if (spread>max_spread) { + cutfeat = (int)i; + max_spread = spread; + } + } + } + // split in the middle + DistanceType split_val = (bbox[cutfeat].low+bbox[cutfeat].high)/2; + ElementType min_elem, max_elem; + computeMinMax(ind, count, cutfeat, min_elem, max_elem); + + if (split_val<min_elem) cutval = (DistanceType)min_elem; + else if (split_val>max_elem) cutval = (DistanceType)max_elem; + else cutval = split_val; + + int lim1, lim2; + planeSplit(ind, count, cutfeat, cutval, lim1, lim2); + + if (lim1>count/2) index = lim1; + else if (lim2<count/2) index = lim2; + else index = count/2; + } + + + /** + * Subdivide the list of points by a plane perpendicular on axe corresponding + * to the 'cutfeat' dimension at 'cutval' position. + * + * On return: + * dataset[ind[0..lim1-1]][cutfeat]<cutval + * dataset[ind[lim1..lim2-1]][cutfeat]==cutval + * dataset[ind[lim2..count]][cutfeat]>cutval + */ + void planeSplit(int* ind, int count, int cutfeat, DistanceType cutval, int& lim1, int& lim2) + { + /* Move vector indices for left subtree to front of list. */ + int left = 0; + int right = count-1; + for (;; ) { + while (left<=right && dataset_[ind[left]][cutfeat]<cutval) ++left; + while (left<=right && dataset_[ind[right]][cutfeat]>=cutval) --right; + if (left>right) break; + std::swap(ind[left], ind[right]); ++left; --right; + } + /* If either list is empty, it means that all remaining features + * are identical. Split in the middle to maintain a balanced tree. + */ + lim1 = left; + right = count-1; + for (;; ) { + while (left<=right && dataset_[ind[left]][cutfeat]<=cutval) ++left; + while (left<=right && dataset_[ind[right]][cutfeat]>cutval) --right; + if (left>right) break; + std::swap(ind[left], ind[right]); ++left; --right; + } + lim2 = left; + } + + DistanceType computeInitialDistances(const ElementType* vec, std::vector<DistanceType>& dists) + { + DistanceType distsq = 0.0; + + for (size_t i = 0; i < dim_; ++i) { + if (vec[i] < root_bbox_[i].low) { + dists[i] = distance_.accum_dist(vec[i], root_bbox_[i].low, (int)i); + distsq += dists[i]; + } + if (vec[i] > root_bbox_[i].high) { + dists[i] = distance_.accum_dist(vec[i], root_bbox_[i].high, (int)i); + distsq += dists[i]; + } + } + + return distsq; + } + + /** + * Performs an exact search in the tree starting from a node. + */ + void searchLevel(ResultSet<DistanceType>& result_set, const ElementType* vec, const NodePtr node, DistanceType mindistsq, + std::vector<DistanceType>& dists, const float epsError) + { + /* If this is a leaf node, then do check and return. */ + if ((node->child1 == NULL)&&(node->child2 == NULL)) { + DistanceType worst_dist = result_set.worstDist(); + for (int i=node->left; i<node->right; ++i) { + int index = reorder_ ? i : vind_[i]; + DistanceType dist = distance_(vec, data_[index], dim_, worst_dist); + if (dist<worst_dist) { + result_set.addPoint(dist,vind_[i]); + } + } + return; + } + + /* Which child branch should be taken first? */ + int idx = node->divfeat; + ElementType val = vec[idx]; + DistanceType diff1 = val - node->divlow; + DistanceType diff2 = val - node->divhigh; + + NodePtr bestChild; + NodePtr otherChild; + DistanceType cut_dist; + if ((diff1+diff2)<0) { + bestChild = node->child1; + otherChild = node->child2; + cut_dist = distance_.accum_dist(val, node->divhigh, idx); + } + else { + bestChild = node->child2; + otherChild = node->child1; + cut_dist = distance_.accum_dist( val, node->divlow, idx); + } + + /* Call recursively to search next level down. */ + searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError); + + DistanceType dst = dists[idx]; + mindistsq = mindistsq + cut_dist - dst; + dists[idx] = cut_dist; + if (mindistsq*epsError<=result_set.worstDist()) { + searchLevel(result_set, vec, otherChild, mindistsq, dists, epsError); + } + dists[idx] = dst; + } + +private: + + /** + * The dataset used by this index + */ + const Matrix<ElementType> dataset_; + + IndexParams index_params_; + + int leaf_max_size_; + bool reorder_; + + + /** + * Array of indices to vectors in the dataset. + */ + std::vector<int> vind_; + + Matrix<ElementType> data_; + + size_t size_; + size_t dim_; + + /** + * Array of k-d trees used to find neighbours. + */ + NodePtr root_node_; + + BoundingBox root_bbox_; + + /** + * Pooled memory allocator. + * + * Using a pooled memory allocator is more efficient + * than allocating memory directly when there is a large + * number small of memory allocations. + */ + PooledAllocator pool_; + + Distance distance_; +}; // class KDTree + +} + +#endif //OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_ diff --git a/thirdparty/linux/include/opencv2/flann/kmeans_index.h b/thirdparty/linux/include/opencv2/flann/kmeans_index.h new file mode 100644 index 0000000..98ad0c8 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/kmeans_index.h @@ -0,0 +1,1171 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_KMEANS_INDEX_H_ +#define OPENCV_FLANN_KMEANS_INDEX_H_ + +#include <algorithm> +#include <map> +#include <cassert> +#include <limits> +#include <cmath> + +#include "general.h" +#include "nn_index.h" +#include "dist.h" +#include "matrix.h" +#include "result_set.h" +#include "heap.h" +#include "allocator.h" +#include "random.h" +#include "saving.h" +#include "logger.h" + + +namespace cvflann +{ + +struct KMeansIndexParams : public IndexParams +{ + KMeansIndexParams(int branching = 32, int iterations = 11, + flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM, float cb_index = 0.2 ) + { + (*this)["algorithm"] = FLANN_INDEX_KMEANS; + // branching factor + (*this)["branching"] = branching; + // max iterations to perform in one kmeans clustering (kmeans tree) + (*this)["iterations"] = iterations; + // algorithm used for picking the initial cluster centers for kmeans tree + (*this)["centers_init"] = centers_init; + // cluster boundary index. Used when searching the kmeans tree + (*this)["cb_index"] = cb_index; + } +}; + + +/** + * Hierarchical kmeans index + * + * Contains a tree constructed through a hierarchical kmeans clustering + * and other information for indexing a set of points for nearest-neighbour matching. + */ +template <typename Distance> +class KMeansIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + + + typedef void (KMeansIndex::* centersAlgFunction)(int, int*, int, int*, int&); + + /** + * The function used for choosing the cluster centers. + */ + centersAlgFunction chooseCenters; + + + + /** + * Chooses the initial centers in the k-means clustering in a random manner. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * indices_length = length of indices vector + * + */ + void chooseCentersRandom(int k, int* indices, int indices_length, int* centers, int& centers_length) + { + UniqueRandom r(indices_length); + + int index; + for (index=0; index<k; ++index) { + bool duplicate = true; + int rnd; + while (duplicate) { + duplicate = false; + rnd = r.next(); + if (rnd<0) { + centers_length = index; + return; + } + + centers[index] = indices[rnd]; + + for (int j=0; j<index; ++j) { + DistanceType sq = distance_(dataset_[centers[index]], dataset_[centers[j]], dataset_.cols); + if (sq<1e-16) { + duplicate = true; + } + } + } + } + + centers_length = index; + } + + + /** + * Chooses the initial centers in the k-means using Gonzales' algorithm + * so that the centers are spaced apart from each other. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * Returns: + */ + void chooseCentersGonzales(int k, int* indices, int indices_length, int* centers, int& centers_length) + { + int n = indices_length; + + int rnd = rand_int(n); + assert(rnd >=0 && rnd < n); + + centers[0] = indices[rnd]; + + int index; + for (index=1; index<k; ++index) { + + int best_index = -1; + DistanceType best_val = 0; + for (int j=0; j<n; ++j) { + DistanceType dist = distance_(dataset_[centers[0]],dataset_[indices[j]],dataset_.cols); + for (int i=1; i<index; ++i) { + DistanceType tmp_dist = distance_(dataset_[centers[i]],dataset_[indices[j]],dataset_.cols); + if (tmp_dist<dist) { + dist = tmp_dist; + } + } + if (dist>best_val) { + best_val = dist; + best_index = j; + } + } + if (best_index!=-1) { + centers[index] = indices[best_index]; + } + else { + break; + } + } + centers_length = index; + } + + + /** + * Chooses the initial centers in the k-means using the algorithm + * proposed in the KMeans++ paper: + * Arthur, David; Vassilvitskii, Sergei - k-means++: The Advantages of Careful Seeding + * + * Implementation of this function was converted from the one provided in Arthur's code. + * + * Params: + * k = number of centers + * vecs = the dataset of points + * indices = indices in the dataset + * Returns: + */ + void chooseCentersKMeanspp(int k, int* indices, int indices_length, int* centers, int& centers_length) + { + int n = indices_length; + + double currentPot = 0; + DistanceType* closestDistSq = new DistanceType[n]; + + // Choose one random center and set the closestDistSq values + int index = rand_int(n); + assert(index >=0 && index < n); + centers[0] = indices[index]; + + for (int i = 0; i < n; i++) { + closestDistSq[i] = distance_(dataset_[indices[i]], dataset_[indices[index]], dataset_.cols); + closestDistSq[i] = ensureSquareDistance<Distance>( closestDistSq[i] ); + currentPot += closestDistSq[i]; + } + + + const int numLocalTries = 1; + + // Choose each center + int centerCount; + for (centerCount = 1; centerCount < k; centerCount++) { + + // Repeat several trials + double bestNewPot = -1; + int bestNewIndex = -1; + for (int localTrial = 0; localTrial < numLocalTries; localTrial++) { + + // Choose our center - have to be slightly careful to return a valid answer even accounting + // for possible rounding errors + double randVal = rand_double(currentPot); + for (index = 0; index < n-1; index++) { + if (randVal <= closestDistSq[index]) break; + else randVal -= closestDistSq[index]; + } + + // Compute the new potential + double newPot = 0; + for (int i = 0; i < n; i++) { + DistanceType dist = distance_(dataset_[indices[i]], dataset_[indices[index]], dataset_.cols); + newPot += std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] ); + } + + // Store the best result + if ((bestNewPot < 0)||(newPot < bestNewPot)) { + bestNewPot = newPot; + bestNewIndex = index; + } + } + + // Add the appropriate center + centers[centerCount] = indices[bestNewIndex]; + currentPot = bestNewPot; + for (int i = 0; i < n; i++) { + DistanceType dist = distance_(dataset_[indices[i]], dataset_[indices[bestNewIndex]], dataset_.cols); + closestDistSq[i] = std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] ); + } + } + + centers_length = centerCount; + + delete[] closestDistSq; + } + + + +public: + + flann_algorithm_t getType() const + { + return FLANN_INDEX_KMEANS; + } + + class KMeansDistanceComputer : public cv::ParallelLoopBody + { + public: + KMeansDistanceComputer(Distance _distance, const Matrix<ElementType>& _dataset, + const int _branching, const int* _indices, const Matrix<double>& _dcenters, const size_t _veclen, + int* _count, int* _belongs_to, std::vector<DistanceType>& _radiuses, bool& _converged, cv::Mutex& _mtx) + : distance(_distance) + , dataset(_dataset) + , branching(_branching) + , indices(_indices) + , dcenters(_dcenters) + , veclen(_veclen) + , count(_count) + , belongs_to(_belongs_to) + , radiuses(_radiuses) + , converged(_converged) + , mtx(_mtx) + { + } + + void operator()(const cv::Range& range) const + { + const int begin = range.start; + const int end = range.end; + + for( int i = begin; i<end; ++i) + { + DistanceType sq_dist = distance(dataset[indices[i]], dcenters[0], veclen); + int new_centroid = 0; + for (int j=1; j<branching; ++j) { + DistanceType new_sq_dist = distance(dataset[indices[i]], dcenters[j], veclen); + if (sq_dist>new_sq_dist) { + new_centroid = j; + sq_dist = new_sq_dist; + } + } + if (sq_dist > radiuses[new_centroid]) { + radiuses[new_centroid] = sq_dist; + } + if (new_centroid != belongs_to[i]) { + count[belongs_to[i]]--; + count[new_centroid]++; + belongs_to[i] = new_centroid; + mtx.lock(); + converged = false; + mtx.unlock(); + } + } + } + + private: + Distance distance; + const Matrix<ElementType>& dataset; + const int branching; + const int* indices; + const Matrix<double>& dcenters; + const size_t veclen; + int* count; + int* belongs_to; + std::vector<DistanceType>& radiuses; + bool& converged; + cv::Mutex& mtx; + KMeansDistanceComputer& operator=( const KMeansDistanceComputer & ) { return *this; } + }; + + /** + * Index constructor + * + * Params: + * inputData = dataset with the input features + * params = parameters passed to the hierarchical k-means algorithm + */ + KMeansIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KMeansIndexParams(), + Distance d = Distance()) + : dataset_(inputData), index_params_(params), root_(NULL), indices_(NULL), distance_(d) + { + memoryCounter_ = 0; + + size_ = dataset_.rows; + veclen_ = dataset_.cols; + + branching_ = get_param(params,"branching",32); + iterations_ = get_param(params,"iterations",11); + if (iterations_<0) { + iterations_ = (std::numeric_limits<int>::max)(); + } + centers_init_ = get_param(params,"centers_init",FLANN_CENTERS_RANDOM); + + if (centers_init_==FLANN_CENTERS_RANDOM) { + chooseCenters = &KMeansIndex::chooseCentersRandom; + } + else if (centers_init_==FLANN_CENTERS_GONZALES) { + chooseCenters = &KMeansIndex::chooseCentersGonzales; + } + else if (centers_init_==FLANN_CENTERS_KMEANSPP) { + chooseCenters = &KMeansIndex::chooseCentersKMeanspp; + } + else { + throw FLANNException("Unknown algorithm for choosing initial centers."); + } + cb_index_ = 0.4f; + + } + + + KMeansIndex(const KMeansIndex&); + KMeansIndex& operator=(const KMeansIndex&); + + + /** + * Index destructor. + * + * Release the memory used by the index. + */ + virtual ~KMeansIndex() + { + if (root_ != NULL) { + free_centers(root_); + } + if (indices_!=NULL) { + delete[] indices_; + } + } + + /** + * Returns size of index. + */ + size_t size() const + { + return size_; + } + + /** + * Returns the length of an index feature. + */ + size_t veclen() const + { + return veclen_; + } + + + void set_cb_index( float index) + { + cb_index_ = index; + } + + /** + * Computes the inde memory usage + * Returns: memory used by the index + */ + int usedMemory() const + { + return pool_.usedMemory+pool_.wastedMemory+memoryCounter_; + } + + /** + * Builds the index + */ + void buildIndex() + { + if (branching_<2) { + throw FLANNException("Branching factor must be at least 2"); + } + + indices_ = new int[size_]; + for (size_t i=0; i<size_; ++i) { + indices_[i] = int(i); + } + + root_ = pool_.allocate<KMeansNode>(); + std::memset(root_, 0, sizeof(KMeansNode)); + + computeNodeStatistics(root_, indices_, (int)size_); + computeClustering(root_, indices_, (int)size_, branching_,0); + } + + + void saveIndex(FILE* stream) + { + save_value(stream, branching_); + save_value(stream, iterations_); + save_value(stream, memoryCounter_); + save_value(stream, cb_index_); + save_value(stream, *indices_, (int)size_); + + save_tree(stream, root_); + } + + + void loadIndex(FILE* stream) + { + load_value(stream, branching_); + load_value(stream, iterations_); + load_value(stream, memoryCounter_); + load_value(stream, cb_index_); + if (indices_!=NULL) { + delete[] indices_; + } + indices_ = new int[size_]; + load_value(stream, *indices_, size_); + + if (root_!=NULL) { + free_centers(root_); + } + load_tree(stream, root_); + + index_params_["algorithm"] = getType(); + index_params_["branching"] = branching_; + index_params_["iterations"] = iterations_; + index_params_["centers_init"] = centers_init_; + index_params_["cb_index"] = cb_index_; + + } + + + /** + * Find set of nearest neighbors to vec. Their indices are stored inside + * the result object. + * + * Params: + * result = the result object in which the indices of the nearest-neighbors are stored + * vec = the vector for which to search the nearest neighbors + * searchParams = parameters that influence the search algorithm (checks, cb_index) + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) + { + + int maxChecks = get_param(searchParams,"checks",32); + + if (maxChecks==FLANN_CHECKS_UNLIMITED) { + findExactNN(root_, result, vec); + } + else { + // Priority queue storing intermediate branches in the best-bin-first search + Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_); + + int checks = 0; + findNN(root_, result, vec, checks, maxChecks, heap); + + BranchSt branch; + while (heap->popMin(branch) && (checks<maxChecks || !result.full())) { + KMeansNodePtr node = branch.node; + findNN(node, result, vec, checks, maxChecks, heap); + } + assert(result.full()); + + delete heap; + } + + } + + /** + * Clustering function that takes a cut in the hierarchical k-means + * tree and return the clusters centers of that clustering. + * Params: + * numClusters = number of clusters to have in the clustering computed + * Returns: number of cluster centers + */ + int getClusterCenters(Matrix<DistanceType>& centers) + { + int numClusters = centers.rows; + if (numClusters<1) { + throw FLANNException("Number of clusters must be at least 1"); + } + + DistanceType variance; + KMeansNodePtr* clusters = new KMeansNodePtr[numClusters]; + + int clusterCount = getMinVarianceClusters(root_, clusters, numClusters, variance); + + Logger::info("Clusters requested: %d, returning %d\n",numClusters, clusterCount); + + for (int i=0; i<clusterCount; ++i) { + DistanceType* center = clusters[i]->pivot; + for (size_t j=0; j<veclen_; ++j) { + centers[i][j] = center[j]; + } + } + delete[] clusters; + + return clusterCount; + } + + IndexParams getParameters() const + { + return index_params_; + } + + +private: + /** + * Struture representing a node in the hierarchical k-means tree. + */ + struct KMeansNode + { + /** + * The cluster center. + */ + DistanceType* pivot; + /** + * The cluster radius. + */ + DistanceType radius; + /** + * The cluster mean radius. + */ + DistanceType mean_radius; + /** + * The cluster variance. + */ + DistanceType variance; + /** + * The cluster size (number of points in the cluster) + */ + int size; + /** + * Child nodes (only for non-terminal nodes) + */ + KMeansNode** childs; + /** + * Node points (only for terminal nodes) + */ + int* indices; + /** + * Level + */ + int level; + }; + typedef KMeansNode* KMeansNodePtr; + + /** + * Alias definition for a nicer syntax. + */ + typedef BranchStruct<KMeansNodePtr, DistanceType> BranchSt; + + + + + void save_tree(FILE* stream, KMeansNodePtr node) + { + save_value(stream, *node); + save_value(stream, *(node->pivot), (int)veclen_); + if (node->childs==NULL) { + int indices_offset = (int)(node->indices - indices_); + save_value(stream, indices_offset); + } + else { + for(int i=0; i<branching_; ++i) { + save_tree(stream, node->childs[i]); + } + } + } + + + void load_tree(FILE* stream, KMeansNodePtr& node) + { + node = pool_.allocate<KMeansNode>(); + load_value(stream, *node); + node->pivot = new DistanceType[veclen_]; + load_value(stream, *(node->pivot), (int)veclen_); + if (node->childs==NULL) { + int indices_offset; + load_value(stream, indices_offset); + node->indices = indices_ + indices_offset; + } + else { + node->childs = pool_.allocate<KMeansNodePtr>(branching_); + for(int i=0; i<branching_; ++i) { + load_tree(stream, node->childs[i]); + } + } + } + + + /** + * Helper function + */ + void free_centers(KMeansNodePtr node) + { + delete[] node->pivot; + if (node->childs!=NULL) { + for (int k=0; k<branching_; ++k) { + free_centers(node->childs[k]); + } + } + } + + /** + * Computes the statistics of a node (mean, radius, variance). + * + * Params: + * node = the node to use + * indices = the indices of the points belonging to the node + */ + void computeNodeStatistics(KMeansNodePtr node, int* indices, int indices_length) + { + + DistanceType radius = 0; + DistanceType variance = 0; + DistanceType* mean = new DistanceType[veclen_]; + memoryCounter_ += int(veclen_*sizeof(DistanceType)); + + memset(mean,0,veclen_*sizeof(DistanceType)); + + for (size_t i=0; i<size_; ++i) { + ElementType* vec = dataset_[indices[i]]; + for (size_t j=0; j<veclen_; ++j) { + mean[j] += vec[j]; + } + variance += distance_(vec, ZeroIterator<ElementType>(), veclen_); + } + for (size_t j=0; j<veclen_; ++j) { + mean[j] /= size_; + } + variance /= size_; + variance -= distance_(mean, ZeroIterator<ElementType>(), veclen_); + + DistanceType tmp = 0; + for (int i=0; i<indices_length; ++i) { + tmp = distance_(mean, dataset_[indices[i]], veclen_); + if (tmp>radius) { + radius = tmp; + } + } + + node->variance = variance; + node->radius = radius; + node->pivot = mean; + } + + + /** + * The method responsible with actually doing the recursive hierarchical + * clustering + * + * Params: + * node = the node to cluster + * indices = indices of the points belonging to the current node + * branching = the branching factor to use in the clustering + * + * TODO: for 1-sized clusters don't store a cluster center (it's the same as the single cluster point) + */ + void computeClustering(KMeansNodePtr node, int* indices, int indices_length, int branching, int level) + { + node->size = indices_length; + node->level = level; + + if (indices_length < branching) { + node->indices = indices; + std::sort(node->indices,node->indices+indices_length); + node->childs = NULL; + return; + } + + cv::AutoBuffer<int> centers_idx_buf(branching); + int* centers_idx = (int*)centers_idx_buf; + int centers_length; + (this->*chooseCenters)(branching, indices, indices_length, centers_idx, centers_length); + + if (centers_length<branching) { + node->indices = indices; + std::sort(node->indices,node->indices+indices_length); + node->childs = NULL; + return; + } + + + cv::AutoBuffer<double> dcenters_buf(branching*veclen_); + Matrix<double> dcenters((double*)dcenters_buf,branching,veclen_); + for (int i=0; i<centers_length; ++i) { + ElementType* vec = dataset_[centers_idx[i]]; + for (size_t k=0; k<veclen_; ++k) { + dcenters[i][k] = double(vec[k]); + } + } + + std::vector<DistanceType> radiuses(branching); + cv::AutoBuffer<int> count_buf(branching); + int* count = (int*)count_buf; + for (int i=0; i<branching; ++i) { + radiuses[i] = 0; + count[i] = 0; + } + + // assign points to clusters + cv::AutoBuffer<int> belongs_to_buf(indices_length); + int* belongs_to = (int*)belongs_to_buf; + for (int i=0; i<indices_length; ++i) { + + DistanceType sq_dist = distance_(dataset_[indices[i]], dcenters[0], veclen_); + belongs_to[i] = 0; + for (int j=1; j<branching; ++j) { + DistanceType new_sq_dist = distance_(dataset_[indices[i]], dcenters[j], veclen_); + if (sq_dist>new_sq_dist) { + belongs_to[i] = j; + sq_dist = new_sq_dist; + } + } + if (sq_dist>radiuses[belongs_to[i]]) { + radiuses[belongs_to[i]] = sq_dist; + } + count[belongs_to[i]]++; + } + + bool converged = false; + int iteration = 0; + while (!converged && iteration<iterations_) { + converged = true; + iteration++; + + // compute the new cluster centers + for (int i=0; i<branching; ++i) { + memset(dcenters[i],0,sizeof(double)*veclen_); + radiuses[i] = 0; + } + for (int i=0; i<indices_length; ++i) { + ElementType* vec = dataset_[indices[i]]; + double* center = dcenters[belongs_to[i]]; + for (size_t k=0; k<veclen_; ++k) { + center[k] += vec[k]; + } + } + for (int i=0; i<branching; ++i) { + int cnt = count[i]; + for (size_t k=0; k<veclen_; ++k) { + dcenters[i][k] /= cnt; + } + } + + // reassign points to clusters + cv::Mutex mtx; + KMeansDistanceComputer invoker(distance_, dataset_, branching, indices, dcenters, veclen_, count, belongs_to, radiuses, converged, mtx); + parallel_for_(cv::Range(0, (int)indices_length), invoker); + + for (int i=0; i<branching; ++i) { + // if one cluster converges to an empty cluster, + // move an element into that cluster + if (count[i]==0) { + int j = (i+1)%branching; + while (count[j]<=1) { + j = (j+1)%branching; + } + + for (int k=0; k<indices_length; ++k) { + if (belongs_to[k]==j) { + // for cluster j, we move the furthest element from the center to the empty cluster i + if ( distance_(dataset_[indices[k]], dcenters[j], veclen_) == radiuses[j] ) { + belongs_to[k] = i; + count[j]--; + count[i]++; + break; + } + } + } + converged = false; + } + } + + } + + DistanceType** centers = new DistanceType*[branching]; + + for (int i=0; i<branching; ++i) { + centers[i] = new DistanceType[veclen_]; + memoryCounter_ += (int)(veclen_*sizeof(DistanceType)); + for (size_t k=0; k<veclen_; ++k) { + centers[i][k] = (DistanceType)dcenters[i][k]; + } + } + + + // compute kmeans clustering for each of the resulting clusters + node->childs = pool_.allocate<KMeansNodePtr>(branching); + int start = 0; + int end = start; + for (int c=0; c<branching; ++c) { + int s = count[c]; + + DistanceType variance = 0; + DistanceType mean_radius =0; + for (int i=0; i<indices_length; ++i) { + if (belongs_to[i]==c) { + DistanceType d = distance_(dataset_[indices[i]], ZeroIterator<ElementType>(), veclen_); + variance += d; + mean_radius += sqrt(d); + std::swap(indices[i],indices[end]); + std::swap(belongs_to[i],belongs_to[end]); + end++; + } + } + variance /= s; + mean_radius /= s; + variance -= distance_(centers[c], ZeroIterator<ElementType>(), veclen_); + + node->childs[c] = pool_.allocate<KMeansNode>(); + std::memset(node->childs[c], 0, sizeof(KMeansNode)); + node->childs[c]->radius = radiuses[c]; + node->childs[c]->pivot = centers[c]; + node->childs[c]->variance = variance; + node->childs[c]->mean_radius = mean_radius; + computeClustering(node->childs[c],indices+start, end-start, branching, level+1); + start=end; + } + + delete[] centers; + } + + + + /** + * Performs one descent in the hierarchical k-means tree. The branches not + * visited are stored in a priority queue. + * + * Params: + * node = node to explore + * result = container for the k-nearest neighbors found + * vec = query points + * checks = how many points in the dataset have been checked so far + * maxChecks = maximum dataset points to checks + */ + + + void findNN(KMeansNodePtr node, ResultSet<DistanceType>& result, const ElementType* vec, int& checks, int maxChecks, + Heap<BranchSt>* heap) + { + // Ignore those clusters that are too far away + { + DistanceType bsq = distance_(vec, node->pivot, veclen_); + DistanceType rsq = node->radius; + DistanceType wsq = result.worstDist(); + + DistanceType val = bsq-rsq-wsq; + DistanceType val2 = val*val-4*rsq*wsq; + + //if (val>0) { + if ((val>0)&&(val2>0)) { + return; + } + } + + if (node->childs==NULL) { + if (checks>=maxChecks) { + if (result.full()) return; + } + checks += node->size; + for (int i=0; i<node->size; ++i) { + int index = node->indices[i]; + DistanceType dist = distance_(dataset_[index], vec, veclen_); + result.addPoint(dist, index); + } + } + else { + DistanceType* domain_distances = new DistanceType[branching_]; + int closest_center = exploreNodeBranches(node, vec, domain_distances, heap); + delete[] domain_distances; + findNN(node->childs[closest_center],result,vec, checks, maxChecks, heap); + } + } + + /** + * Helper function that computes the nearest childs of a node to a given query point. + * Params: + * node = the node + * q = the query point + * distances = array with the distances to each child node. + * Returns: + */ + int exploreNodeBranches(KMeansNodePtr node, const ElementType* q, DistanceType* domain_distances, Heap<BranchSt>* heap) + { + + int best_index = 0; + domain_distances[best_index] = distance_(q, node->childs[best_index]->pivot, veclen_); + for (int i=1; i<branching_; ++i) { + domain_distances[i] = distance_(q, node->childs[i]->pivot, veclen_); + if (domain_distances[i]<domain_distances[best_index]) { + best_index = i; + } + } + + // float* best_center = node->childs[best_index]->pivot; + for (int i=0; i<branching_; ++i) { + if (i != best_index) { + domain_distances[i] -= cb_index_*node->childs[i]->variance; + + // float dist_to_border = getDistanceToBorder(node.childs[i].pivot,best_center,q); + // if (domain_distances[i]<dist_to_border) { + // domain_distances[i] = dist_to_border; + // } + heap->insert(BranchSt(node->childs[i],domain_distances[i])); + } + } + + return best_index; + } + + + /** + * Function the performs exact nearest neighbor search by traversing the entire tree. + */ + void findExactNN(KMeansNodePtr node, ResultSet<DistanceType>& result, const ElementType* vec) + { + // Ignore those clusters that are too far away + { + DistanceType bsq = distance_(vec, node->pivot, veclen_); + DistanceType rsq = node->radius; + DistanceType wsq = result.worstDist(); + + DistanceType val = bsq-rsq-wsq; + DistanceType val2 = val*val-4*rsq*wsq; + + // if (val>0) { + if ((val>0)&&(val2>0)) { + return; + } + } + + + if (node->childs==NULL) { + for (int i=0; i<node->size; ++i) { + int index = node->indices[i]; + DistanceType dist = distance_(dataset_[index], vec, veclen_); + result.addPoint(dist, index); + } + } + else { + int* sort_indices = new int[branching_]; + + getCenterOrdering(node, vec, sort_indices); + + for (int i=0; i<branching_; ++i) { + findExactNN(node->childs[sort_indices[i]],result,vec); + } + + delete[] sort_indices; + } + } + + + /** + * Helper function. + * + * I computes the order in which to traverse the child nodes of a particular node. + */ + void getCenterOrdering(KMeansNodePtr node, const ElementType* q, int* sort_indices) + { + DistanceType* domain_distances = new DistanceType[branching_]; + for (int i=0; i<branching_; ++i) { + DistanceType dist = distance_(q, node->childs[i]->pivot, veclen_); + + int j=0; + while (domain_distances[j]<dist && j<i) j++; + for (int k=i; k>j; --k) { + domain_distances[k] = domain_distances[k-1]; + sort_indices[k] = sort_indices[k-1]; + } + domain_distances[j] = dist; + sort_indices[j] = i; + } + delete[] domain_distances; + } + + /** + * Method that computes the squared distance from the query point q + * from inside region with center c to the border between this + * region and the region with center p + */ + DistanceType getDistanceToBorder(DistanceType* p, DistanceType* c, DistanceType* q) + { + DistanceType sum = 0; + DistanceType sum2 = 0; + + for (int i=0; i<veclen_; ++i) { + DistanceType t = c[i]-p[i]; + sum += t*(q[i]-(c[i]+p[i])/2); + sum2 += t*t; + } + + return sum*sum/sum2; + } + + + /** + * Helper function the descends in the hierarchical k-means tree by spliting those clusters that minimize + * the overall variance of the clustering. + * Params: + * root = root node + * clusters = array with clusters centers (return value) + * varianceValue = variance of the clustering (return value) + * Returns: + */ + int getMinVarianceClusters(KMeansNodePtr root, KMeansNodePtr* clusters, int clusters_length, DistanceType& varianceValue) + { + int clusterCount = 1; + clusters[0] = root; + + DistanceType meanVariance = root->variance*root->size; + + while (clusterCount<clusters_length) { + DistanceType minVariance = (std::numeric_limits<DistanceType>::max)(); + int splitIndex = -1; + + for (int i=0; i<clusterCount; ++i) { + if (clusters[i]->childs != NULL) { + + DistanceType variance = meanVariance - clusters[i]->variance*clusters[i]->size; + + for (int j=0; j<branching_; ++j) { + variance += clusters[i]->childs[j]->variance*clusters[i]->childs[j]->size; + } + if (variance<minVariance) { + minVariance = variance; + splitIndex = i; + } + } + } + + if (splitIndex==-1) break; + if ( (branching_+clusterCount-1) > clusters_length) break; + + meanVariance = minVariance; + + // split node + KMeansNodePtr toSplit = clusters[splitIndex]; + clusters[splitIndex] = toSplit->childs[0]; + for (int i=1; i<branching_; ++i) { + clusters[clusterCount++] = toSplit->childs[i]; + } + } + + varianceValue = meanVariance/root->size; + return clusterCount; + } + +private: + /** The branching factor used in the hierarchical k-means clustering */ + int branching_; + + /** Maximum number of iterations to use when performing k-means clustering */ + int iterations_; + + /** Algorithm for choosing the cluster centers */ + flann_centers_init_t centers_init_; + + /** + * Cluster border index. This is used in the tree search phase when determining + * the closest cluster to explore next. A zero value takes into account only + * the cluster centres, a value greater then zero also take into account the size + * of the cluster. + */ + float cb_index_; + + /** + * The dataset used by this index + */ + const Matrix<ElementType> dataset_; + + /** Index parameters */ + IndexParams index_params_; + + /** + * Number of features in the dataset. + */ + size_t size_; + + /** + * Length of each feature. + */ + size_t veclen_; + + /** + * The root node in the tree. + */ + KMeansNodePtr root_; + + /** + * Array of indices to vectors in the dataset. + */ + int* indices_; + + /** + * The distance + */ + Distance distance_; + + /** + * Pooled memory allocator. + */ + PooledAllocator pool_; + + /** + * Memory occupied by the index. + */ + int memoryCounter_; +}; + +} + +#endif //OPENCV_FLANN_KMEANS_INDEX_H_ diff --git a/thirdparty/linux/include/opencv2/flann/linear_index.h b/thirdparty/linux/include/opencv2/flann/linear_index.h new file mode 100644 index 0000000..5aa7a5c --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/linear_index.h @@ -0,0 +1,132 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_LINEAR_INDEX_H_ +#define OPENCV_FLANN_LINEAR_INDEX_H_ + +#include "general.h" +#include "nn_index.h" + +namespace cvflann +{ + +struct LinearIndexParams : public IndexParams +{ + LinearIndexParams() + { + (* this)["algorithm"] = FLANN_INDEX_LINEAR; + } +}; + +template <typename Distance> +class LinearIndex : public NNIndex<Distance> +{ +public: + + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + + LinearIndex(const Matrix<ElementType>& inputData, const IndexParams& params = LinearIndexParams(), + Distance d = Distance()) : + dataset_(inputData), index_params_(params), distance_(d) + { + } + + LinearIndex(const LinearIndex&); + LinearIndex& operator=(const LinearIndex&); + + flann_algorithm_t getType() const + { + return FLANN_INDEX_LINEAR; + } + + + size_t size() const + { + return dataset_.rows; + } + + size_t veclen() const + { + return dataset_.cols; + } + + + int usedMemory() const + { + return 0; + } + + void buildIndex() + { + /* nothing to do here for linear search */ + } + + void saveIndex(FILE*) + { + /* nothing to do here for linear search */ + } + + + void loadIndex(FILE*) + { + /* nothing to do here for linear search */ + + index_params_["algorithm"] = getType(); + } + + void findNeighbors(ResultSet<DistanceType>& resultSet, const ElementType* vec, const SearchParams& /*searchParams*/) + { + ElementType* data = dataset_.data; + for (size_t i = 0; i < dataset_.rows; ++i, data += dataset_.cols) { + DistanceType dist = distance_(data, vec, dataset_.cols); + resultSet.addPoint(dist, (int)i); + } + } + + IndexParams getParameters() const + { + return index_params_; + } + +private: + /** The dataset */ + const Matrix<ElementType> dataset_; + /** Index parameters */ + IndexParams index_params_; + /** Index distance */ + Distance distance_; + +}; + +} + +#endif // OPENCV_FLANN_LINEAR_INDEX_H_ diff --git a/thirdparty/linux/include/opencv2/flann/logger.h b/thirdparty/linux/include/opencv2/flann/logger.h new file mode 100644 index 0000000..24f3fb6 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/logger.h @@ -0,0 +1,130 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_LOGGER_H +#define OPENCV_FLANN_LOGGER_H + +#include <stdio.h> +#include <stdarg.h> + +#include "defines.h" + + +namespace cvflann +{ + +class Logger +{ + Logger() : stream(stdout), logLevel(FLANN_LOG_WARN) {} + + ~Logger() + { + if ((stream!=NULL)&&(stream!=stdout)) { + fclose(stream); + } + } + + static Logger& instance() + { + static Logger logger; + return logger; + } + + void _setDestination(const char* name) + { + if (name==NULL) { + stream = stdout; + } + else { + stream = fopen(name,"w"); + if (stream == NULL) { + stream = stdout; + } + } + } + + int _log(int level, const char* fmt, va_list arglist) + { + if (level > logLevel ) return -1; + int ret = vfprintf(stream, fmt, arglist); + return ret; + } + +public: + /** + * Sets the logging level. All messages with lower priority will be ignored. + * @param level Logging level + */ + static void setLevel(int level) { instance().logLevel = level; } + + /** + * Sets the logging destination + * @param name Filename or NULL for console + */ + static void setDestination(const char* name) { instance()._setDestination(name); } + + /** + * Print log message + * @param level Log level + * @param fmt Message format + * @return + */ + static int log(int level, const char* fmt, ...) + { + va_list arglist; + va_start(arglist, fmt); + int ret = instance()._log(level,fmt,arglist); + va_end(arglist); + return ret; + } + +#define LOG_METHOD(NAME,LEVEL) \ + static int NAME(const char* fmt, ...) \ + { \ + va_list ap; \ + va_start(ap, fmt); \ + int ret = instance()._log(LEVEL, fmt, ap); \ + va_end(ap); \ + return ret; \ + } + + LOG_METHOD(fatal, FLANN_LOG_FATAL) + LOG_METHOD(error, FLANN_LOG_ERROR) + LOG_METHOD(warn, FLANN_LOG_WARN) + LOG_METHOD(info, FLANN_LOG_INFO) + +private: + FILE* stream; + int logLevel; +}; + +} + +#endif //OPENCV_FLANN_LOGGER_H diff --git a/thirdparty/linux/include/opencv2/flann/lsh_index.h b/thirdparty/linux/include/opencv2/flann/lsh_index.h new file mode 100644 index 0000000..4d4670e --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/lsh_index.h @@ -0,0 +1,392 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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. + *************************************************************************/ + +/*********************************************************************** + * Author: Vincent Rabaud + *************************************************************************/ + +#ifndef OPENCV_FLANN_LSH_INDEX_H_ +#define OPENCV_FLANN_LSH_INDEX_H_ + +#include <algorithm> +#include <cassert> +#include <cstring> +#include <map> +#include <vector> + +#include "general.h" +#include "nn_index.h" +#include "matrix.h" +#include "result_set.h" +#include "heap.h" +#include "lsh_table.h" +#include "allocator.h" +#include "random.h" +#include "saving.h" + +namespace cvflann +{ + +struct LshIndexParams : public IndexParams +{ + LshIndexParams(unsigned int table_number = 12, unsigned int key_size = 20, unsigned int multi_probe_level = 2) + { + (* this)["algorithm"] = FLANN_INDEX_LSH; + // The number of hash tables to use + (*this)["table_number"] = table_number; + // The length of the key in the hash tables + (*this)["key_size"] = key_size; + // Number of levels to use in multi-probe (0 for standard LSH) + (*this)["multi_probe_level"] = multi_probe_level; + } +}; + +/** + * Randomized kd-tree index + * + * Contains the k-d trees and other information for indexing a set of points + * for nearest-neighbor matching. + */ +template<typename Distance> +class LshIndex : public NNIndex<Distance> +{ +public: + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + + /** Constructor + * @param input_data dataset with the input features + * @param params parameters passed to the LSH algorithm + * @param d the distance used + */ + LshIndex(const Matrix<ElementType>& input_data, const IndexParams& params = LshIndexParams(), + Distance d = Distance()) : + dataset_(input_data), index_params_(params), distance_(d) + { + // cv::flann::IndexParams sets integer params as 'int', so it is used with get_param + // in place of 'unsigned int' + table_number_ = (unsigned int)get_param<int>(index_params_,"table_number",12); + key_size_ = (unsigned int)get_param<int>(index_params_,"key_size",20); + multi_probe_level_ = (unsigned int)get_param<int>(index_params_,"multi_probe_level",2); + + feature_size_ = (unsigned)dataset_.cols; + fill_xor_mask(0, key_size_, multi_probe_level_, xor_masks_); + } + + + LshIndex(const LshIndex&); + LshIndex& operator=(const LshIndex&); + + /** + * Builds the index + */ + void buildIndex() + { + tables_.resize(table_number_); + for (unsigned int i = 0; i < table_number_; ++i) { + lsh::LshTable<ElementType>& table = tables_[i]; + table = lsh::LshTable<ElementType>(feature_size_, key_size_); + + // Add the features to the table + table.add(dataset_); + } + } + + flann_algorithm_t getType() const + { + return FLANN_INDEX_LSH; + } + + + void saveIndex(FILE* stream) + { + save_value(stream,table_number_); + save_value(stream,key_size_); + save_value(stream,multi_probe_level_); + save_value(stream, dataset_); + } + + void loadIndex(FILE* stream) + { + load_value(stream, table_number_); + load_value(stream, key_size_); + load_value(stream, multi_probe_level_); + load_value(stream, dataset_); + // Building the index is so fast we can afford not storing it + buildIndex(); + + index_params_["algorithm"] = getType(); + index_params_["table_number"] = table_number_; + index_params_["key_size"] = key_size_; + index_params_["multi_probe_level"] = multi_probe_level_; + } + + /** + * Returns size of index. + */ + size_t size() const + { + return dataset_.rows; + } + + /** + * Returns the length of an index feature. + */ + size_t veclen() const + { + return feature_size_; + } + + /** + * Computes the index memory usage + * Returns: memory used by the index + */ + int usedMemory() const + { + return (int)(dataset_.rows * sizeof(int)); + } + + + IndexParams getParameters() const + { + return index_params_; + } + + /** + * \brief Perform k-nearest neighbor search + * \param[in] queries The query points for which to find the nearest neighbors + * \param[out] indices The indices of the nearest neighbors found + * \param[out] dists Distances to the nearest neighbors found + * \param[in] knn Number of nearest neighbors to return + * \param[in] params Search parameters + */ + virtual void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params) + { + assert(queries.cols == veclen()); + assert(indices.rows >= queries.rows); + assert(dists.rows >= queries.rows); + assert(int(indices.cols) >= knn); + assert(int(dists.cols) >= knn); + + + KNNUniqueResultSet<DistanceType> resultSet(knn); + for (size_t i = 0; i < queries.rows; i++) { + resultSet.clear(); + std::fill_n(indices[i], knn, -1); + std::fill_n(dists[i], knn, std::numeric_limits<DistanceType>::max()); + findNeighbors(resultSet, queries[i], params); + if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices[i], dists[i], knn); + else resultSet.copy(indices[i], dists[i], knn); + } + } + + + /** + * Find set of nearest neighbors to vec. Their indices are stored inside + * the result object. + * + * Params: + * result = the result object in which the indices of the nearest-neighbors are stored + * vec = the vector for which to search the nearest neighbors + * maxCheck = the maximum number of restarts (in a best-bin-first manner) + */ + void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& /*searchParams*/) + { + getNeighbors(vec, result); + } + +private: + /** Defines the comparator on score and index + */ + typedef std::pair<float, unsigned int> ScoreIndexPair; + struct SortScoreIndexPairOnSecond + { + bool operator()(const ScoreIndexPair& left, const ScoreIndexPair& right) const + { + return left.second < right.second; + } + }; + + /** Fills the different xor masks to use when getting the neighbors in multi-probe LSH + * @param key the key we build neighbors from + * @param lowest_index the lowest index of the bit set + * @param level the multi-probe level we are at + * @param xor_masks all the xor mask + */ + void fill_xor_mask(lsh::BucketKey key, int lowest_index, unsigned int level, + std::vector<lsh::BucketKey>& xor_masks) + { + xor_masks.push_back(key); + if (level == 0) return; + for (int index = lowest_index - 1; index >= 0; --index) { + // Create a new key + lsh::BucketKey new_key = key | (1 << index); + fill_xor_mask(new_key, index, level - 1, xor_masks); + } + } + + /** Performs the approximate nearest-neighbor search. + * @param vec the feature to analyze + * @param do_radius flag indicating if we check the radius too + * @param radius the radius if it is a radius search + * @param do_k flag indicating if we limit the number of nn + * @param k_nn the number of nearest neighbors + * @param checked_average used for debugging + */ + void getNeighbors(const ElementType* vec, bool /*do_radius*/, float radius, bool do_k, unsigned int k_nn, + float& /*checked_average*/) + { + static std::vector<ScoreIndexPair> score_index_heap; + + if (do_k) { + unsigned int worst_score = std::numeric_limits<unsigned int>::max(); + typename std::vector<lsh::LshTable<ElementType> >::const_iterator table = tables_.begin(); + typename std::vector<lsh::LshTable<ElementType> >::const_iterator table_end = tables_.end(); + for (; table != table_end; ++table) { + size_t key = table->getKey(vec); + std::vector<lsh::BucketKey>::const_iterator xor_mask = xor_masks_.begin(); + std::vector<lsh::BucketKey>::const_iterator xor_mask_end = xor_masks_.end(); + for (; xor_mask != xor_mask_end; ++xor_mask) { + size_t sub_key = key ^ (*xor_mask); + const lsh::Bucket* bucket = table->getBucketFromKey(sub_key); + if (bucket == 0) continue; + + // Go over each descriptor index + std::vector<lsh::FeatureIndex>::const_iterator training_index = bucket->begin(); + std::vector<lsh::FeatureIndex>::const_iterator last_training_index = bucket->end(); + DistanceType hamming_distance; + + // Process the rest of the candidates + for (; training_index < last_training_index; ++training_index) { + hamming_distance = distance_(vec, dataset_[*training_index], dataset_.cols); + + if (hamming_distance < worst_score) { + // Insert the new element + score_index_heap.push_back(ScoreIndexPair(hamming_distance, training_index)); + std::push_heap(score_index_heap.begin(), score_index_heap.end()); + + if (score_index_heap.size() > (unsigned int)k_nn) { + // Remove the highest distance value as we have too many elements + std::pop_heap(score_index_heap.begin(), score_index_heap.end()); + score_index_heap.pop_back(); + // Keep track of the worst score + worst_score = score_index_heap.front().first; + } + } + } + } + } + } + else { + typename std::vector<lsh::LshTable<ElementType> >::const_iterator table = tables_.begin(); + typename std::vector<lsh::LshTable<ElementType> >::const_iterator table_end = tables_.end(); + for (; table != table_end; ++table) { + size_t key = table->getKey(vec); + std::vector<lsh::BucketKey>::const_iterator xor_mask = xor_masks_.begin(); + std::vector<lsh::BucketKey>::const_iterator xor_mask_end = xor_masks_.end(); + for (; xor_mask != xor_mask_end; ++xor_mask) { + size_t sub_key = key ^ (*xor_mask); + const lsh::Bucket* bucket = table->getBucketFromKey(sub_key); + if (bucket == 0) continue; + + // Go over each descriptor index + std::vector<lsh::FeatureIndex>::const_iterator training_index = bucket->begin(); + std::vector<lsh::FeatureIndex>::const_iterator last_training_index = bucket->end(); + DistanceType hamming_distance; + + // Process the rest of the candidates + for (; training_index < last_training_index; ++training_index) { + // Compute the Hamming distance + hamming_distance = distance_(vec, dataset_[*training_index], dataset_.cols); + if (hamming_distance < radius) score_index_heap.push_back(ScoreIndexPair(hamming_distance, training_index)); + } + } + } + } + } + + /** Performs the approximate nearest-neighbor search. + * This is a slower version than the above as it uses the ResultSet + * @param vec the feature to analyze + */ + void getNeighbors(const ElementType* vec, ResultSet<DistanceType>& result) + { + typename std::vector<lsh::LshTable<ElementType> >::const_iterator table = tables_.begin(); + typename std::vector<lsh::LshTable<ElementType> >::const_iterator table_end = tables_.end(); + for (; table != table_end; ++table) { + size_t key = table->getKey(vec); + std::vector<lsh::BucketKey>::const_iterator xor_mask = xor_masks_.begin(); + std::vector<lsh::BucketKey>::const_iterator xor_mask_end = xor_masks_.end(); + for (; xor_mask != xor_mask_end; ++xor_mask) { + size_t sub_key = key ^ (*xor_mask); + const lsh::Bucket* bucket = table->getBucketFromKey((lsh::BucketKey)sub_key); + if (bucket == 0) continue; + + // Go over each descriptor index + std::vector<lsh::FeatureIndex>::const_iterator training_index = bucket->begin(); + std::vector<lsh::FeatureIndex>::const_iterator last_training_index = bucket->end(); + DistanceType hamming_distance; + + // Process the rest of the candidates + for (; training_index < last_training_index; ++training_index) { + // Compute the Hamming distance + hamming_distance = distance_(vec, dataset_[*training_index], (int)dataset_.cols); + result.addPoint(hamming_distance, *training_index); + } + } + } + } + + /** The different hash tables */ + std::vector<lsh::LshTable<ElementType> > tables_; + + /** The data the LSH tables where built from */ + Matrix<ElementType> dataset_; + + /** The size of the features (as ElementType[]) */ + unsigned int feature_size_; + + IndexParams index_params_; + + /** table number */ + unsigned int table_number_; + /** key size */ + unsigned int key_size_; + /** How far should we look for neighbors in multi-probe LSH */ + unsigned int multi_probe_level_; + + /** The XOR masks to apply to a key to get the neighboring buckets */ + std::vector<lsh::BucketKey> xor_masks_; + + Distance distance_; +}; +} + +#endif //OPENCV_FLANN_LSH_INDEX_H_ diff --git a/thirdparty/linux/include/opencv2/flann/lsh_table.h b/thirdparty/linux/include/opencv2/flann/lsh_table.h new file mode 100644 index 0000000..8ef2bd3 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/lsh_table.h @@ -0,0 +1,492 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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. + *************************************************************************/ + +/*********************************************************************** + * Author: Vincent Rabaud + *************************************************************************/ + +#ifndef OPENCV_FLANN_LSH_TABLE_H_ +#define OPENCV_FLANN_LSH_TABLE_H_ + +#include <algorithm> +#include <iostream> +#include <iomanip> +#include <limits.h> +// TODO as soon as we use C++0x, use the code in USE_UNORDERED_MAP +#ifdef __GXX_EXPERIMENTAL_CXX0X__ +# define USE_UNORDERED_MAP 1 +#else +# define USE_UNORDERED_MAP 0 +#endif +#if USE_UNORDERED_MAP +#include <unordered_map> +#else +#include <map> +#endif +#include <math.h> +#include <stddef.h> + +#include "dynamic_bitset.h" +#include "matrix.h" + +namespace cvflann +{ + +namespace lsh +{ + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** What is stored in an LSH bucket + */ +typedef uint32_t FeatureIndex; +/** The id from which we can get a bucket back in an LSH table + */ +typedef unsigned int BucketKey; + +/** A bucket in an LSH table + */ +typedef std::vector<FeatureIndex> Bucket; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** POD for stats about an LSH table + */ +struct LshStats +{ + std::vector<unsigned int> bucket_sizes_; + size_t n_buckets_; + size_t bucket_size_mean_; + size_t bucket_size_median_; + size_t bucket_size_min_; + size_t bucket_size_max_; + size_t bucket_size_std_dev; + /** Each contained vector contains three value: beginning/end for interval, number of elements in the bin + */ + std::vector<std::vector<unsigned int> > size_histogram_; +}; + +/** Overload the << operator for LshStats + * @param out the streams + * @param stats the stats to display + * @return the streams + */ +inline std::ostream& operator <<(std::ostream& out, const LshStats& stats) +{ + int w = 20; + out << "Lsh Table Stats:\n" << std::setw(w) << std::setiosflags(std::ios::right) << "N buckets : " + << stats.n_buckets_ << "\n" << std::setw(w) << std::setiosflags(std::ios::right) << "mean size : " + << std::setiosflags(std::ios::left) << stats.bucket_size_mean_ << "\n" << std::setw(w) + << std::setiosflags(std::ios::right) << "median size : " << stats.bucket_size_median_ << "\n" << std::setw(w) + << std::setiosflags(std::ios::right) << "min size : " << std::setiosflags(std::ios::left) + << stats.bucket_size_min_ << "\n" << std::setw(w) << std::setiosflags(std::ios::right) << "max size : " + << std::setiosflags(std::ios::left) << stats.bucket_size_max_; + + // Display the histogram + out << std::endl << std::setw(w) << std::setiosflags(std::ios::right) << "histogram : " + << std::setiosflags(std::ios::left); + for (std::vector<std::vector<unsigned int> >::const_iterator iterator = stats.size_histogram_.begin(), end = + stats.size_histogram_.end(); iterator != end; ++iterator) out << (*iterator)[0] << "-" << (*iterator)[1] << ": " << (*iterator)[2] << ", "; + + return out; +} + + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** Lsh hash table. As its key is a sub-feature, and as usually + * the size of it is pretty small, we keep it as a continuous memory array. + * The value is an index in the corpus of features (we keep it as an unsigned + * int for pure memory reasons, it could be a size_t) + */ +template<typename ElementType> +class LshTable +{ +public: + /** A container of all the feature indices. Optimized for space + */ +#if USE_UNORDERED_MAP + typedef std::unordered_map<BucketKey, Bucket> BucketsSpace; +#else + typedef std::map<BucketKey, Bucket> BucketsSpace; +#endif + + /** A container of all the feature indices. Optimized for speed + */ + typedef std::vector<Bucket> BucketsSpeed; + + /** Default constructor + */ + LshTable() + { + } + + /** Default constructor + * Create the mask and allocate the memory + * @param feature_size is the size of the feature (considered as a ElementType[]) + * @param key_size is the number of bits that are turned on in the feature + */ + LshTable(unsigned int feature_size, unsigned int key_size) + { + (void)feature_size; + (void)key_size; + std::cerr << "LSH is not implemented for that type" << std::endl; + assert(0); + } + + /** Add a feature to the table + * @param value the value to store for that feature + * @param feature the feature itself + */ + void add(unsigned int value, const ElementType* feature) + { + // Add the value to the corresponding bucket + BucketKey key = (lsh::BucketKey)getKey(feature); + + switch (speed_level_) { + case kArray: + // That means we get the buckets from an array + buckets_speed_[key].push_back(value); + break; + case kBitsetHash: + // That means we can check the bitset for the presence of a key + key_bitset_.set(key); + buckets_space_[key].push_back(value); + break; + case kHash: + { + // That means we have to check for the hash table for the presence of a key + buckets_space_[key].push_back(value); + break; + } + } + } + + /** Add a set of features to the table + * @param dataset the values to store + */ + void add(Matrix<ElementType> dataset) + { +#if USE_UNORDERED_MAP + buckets_space_.rehash((buckets_space_.size() + dataset.rows) * 1.2); +#endif + // Add the features to the table + for (unsigned int i = 0; i < dataset.rows; ++i) add(i, dataset[i]); + // Now that the table is full, optimize it for speed/space + optimize(); + } + + /** Get a bucket given the key + * @param key + * @return + */ + inline const Bucket* getBucketFromKey(BucketKey key) const + { + // Generate other buckets + switch (speed_level_) { + case kArray: + // That means we get the buckets from an array + return &buckets_speed_[key]; + break; + case kBitsetHash: + // That means we can check the bitset for the presence of a key + if (key_bitset_.test(key)) return &buckets_space_.find(key)->second; + else return 0; + break; + case kHash: + { + // That means we have to check for the hash table for the presence of a key + BucketsSpace::const_iterator bucket_it, bucket_end = buckets_space_.end(); + bucket_it = buckets_space_.find(key); + // Stop here if that bucket does not exist + if (bucket_it == bucket_end) return 0; + else return &bucket_it->second; + break; + } + } + return 0; + } + + /** Compute the sub-signature of a feature + */ + size_t getKey(const ElementType* /*feature*/) const + { + std::cerr << "LSH is not implemented for that type" << std::endl; + assert(0); + return 1; + } + + /** Get statistics about the table + * @return + */ + LshStats getStats() const; + +private: + /** defines the speed fo the implementation + * kArray uses a vector for storing data + * kBitsetHash uses a hash map but checks for the validity of a key with a bitset + * kHash uses a hash map only + */ + enum SpeedLevel + { + kArray, kBitsetHash, kHash + }; + + /** Initialize some variables + */ + void initialize(size_t key_size) + { + const size_t key_size_lower_bound = 1; + //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 + const size_t key_size_upper_bound = (std::min)(sizeof(BucketKey) * CHAR_BIT + 1, sizeof(size_t) * CHAR_BIT); + if (key_size < key_size_lower_bound || key_size >= key_size_upper_bound) + { + 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)); + } + + speed_level_ = kHash; + key_size_ = (unsigned)key_size; + } + + /** Optimize the table for speed/space + */ + void optimize() + { + // If we are already using the fast storage, no need to do anything + if (speed_level_ == kArray) return; + + // Use an array if it will be more than half full + if (buckets_space_.size() > ((size_t(1) << key_size_) / 2)) { + speed_level_ = kArray; + // Fill the array version of it + buckets_speed_.resize(size_t(1) << key_size_); + for (BucketsSpace::const_iterator key_bucket = buckets_space_.begin(); key_bucket != buckets_space_.end(); ++key_bucket) buckets_speed_[key_bucket->first] = key_bucket->second; + + // Empty the hash table + buckets_space_.clear(); + return; + } + + // 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 + // for the vector) or less than 512MB (key_size_ <= 30) + if (((std::max(buckets_space_.size(), buckets_speed_.size()) * CHAR_BIT * 3 * sizeof(BucketKey)) / 10 + >= (size_t(1) << key_size_)) || (key_size_ <= 32)) { + speed_level_ = kBitsetHash; + key_bitset_.resize(size_t(1) << key_size_); + key_bitset_.reset(); + // Try with the BucketsSpace + for (BucketsSpace::const_iterator key_bucket = buckets_space_.begin(); key_bucket != buckets_space_.end(); ++key_bucket) key_bitset_.set(key_bucket->first); + } + else { + speed_level_ = kHash; + key_bitset_.clear(); + } + } + + /** The vector of all the buckets if they are held for speed + */ + BucketsSpeed buckets_speed_; + + /** The hash table of all the buckets in case we cannot use the speed version + */ + BucketsSpace buckets_space_; + + /** What is used to store the data */ + SpeedLevel speed_level_; + + /** If the subkey is small enough, it will keep track of which subkeys are set through that bitset + * That is just a speedup so that we don't look in the hash table (which can be mush slower that checking a bitset) + */ + DynamicBitset key_bitset_; + + /** The size of the sub-signature in bits + */ + unsigned int key_size_; + + // Members only used for the unsigned char specialization + /** The mask to apply to a feature to get the hash key + * Only used in the unsigned char case + */ + std::vector<size_t> mask_; +}; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Specialization for unsigned char + +template<> +inline LshTable<unsigned char>::LshTable(unsigned int feature_size, unsigned int subsignature_size) +{ + initialize(subsignature_size); + // Allocate the mask + mask_ = std::vector<size_t>((size_t)ceil((float)(feature_size * sizeof(char)) / (float)sizeof(size_t)), 0); + + // A bit brutal but fast to code + std::vector<size_t> indices(feature_size * CHAR_BIT); + for (size_t i = 0; i < feature_size * CHAR_BIT; ++i) indices[i] = i; + std::random_shuffle(indices.begin(), indices.end()); + + // Generate a random set of order of subsignature_size_ bits + for (unsigned int i = 0; i < key_size_; ++i) { + size_t index = indices[i]; + + // Set that bit in the mask + size_t divisor = CHAR_BIT * sizeof(size_t); + size_t idx = index / divisor; //pick the right size_t index + mask_[idx] |= size_t(1) << (index % divisor); //use modulo to find the bit offset + } + + // Set to 1 if you want to display the mask for debug +#if 0 + { + size_t bcount = 0; + BOOST_FOREACH(size_t mask_block, mask_){ + out << std::setw(sizeof(size_t) * CHAR_BIT / 4) << std::setfill('0') << std::hex << mask_block + << std::endl; + bcount += __builtin_popcountll(mask_block); + } + out << "bit count : " << std::dec << bcount << std::endl; + out << "mask size : " << mask_.size() << std::endl; + return out; + } +#endif +} + +/** Return the Subsignature of a feature + * @param feature the feature to analyze + */ +template<> +inline size_t LshTable<unsigned char>::getKey(const unsigned char* feature) const +{ + // no need to check if T is dividable by sizeof(size_t) like in the Hamming + // distance computation as we have a mask + const size_t* feature_block_ptr = reinterpret_cast<const size_t*> ((const void*)feature); + + // Figure out the subsignature of the feature + // Given the feature ABCDEF, and the mask 001011, the output will be + // 000CEF + size_t subsignature = 0; + size_t bit_index = 1; + + for (std::vector<size_t>::const_iterator pmask_block = mask_.begin(); pmask_block != mask_.end(); ++pmask_block) { + // get the mask and signature blocks + size_t feature_block = *feature_block_ptr; + size_t mask_block = *pmask_block; + while (mask_block) { + // Get the lowest set bit in the mask block + size_t lowest_bit = mask_block & (-(ptrdiff_t)mask_block); + // Add it to the current subsignature if necessary + subsignature += (feature_block & lowest_bit) ? bit_index : 0; + // Reset the bit in the mask block + mask_block ^= lowest_bit; + // increment the bit index for the subsignature + bit_index <<= 1; + } + // Check the next feature block + ++feature_block_ptr; + } + return subsignature; +} + +template<> +inline LshStats LshTable<unsigned char>::getStats() const +{ + LshStats stats; + stats.bucket_size_mean_ = 0; + if ((buckets_speed_.empty()) && (buckets_space_.empty())) { + stats.n_buckets_ = 0; + stats.bucket_size_median_ = 0; + stats.bucket_size_min_ = 0; + stats.bucket_size_max_ = 0; + return stats; + } + + if (!buckets_speed_.empty()) { + for (BucketsSpeed::const_iterator pbucket = buckets_speed_.begin(); pbucket != buckets_speed_.end(); ++pbucket) { + stats.bucket_sizes_.push_back((lsh::FeatureIndex)pbucket->size()); + stats.bucket_size_mean_ += pbucket->size(); + } + stats.bucket_size_mean_ /= buckets_speed_.size(); + stats.n_buckets_ = buckets_speed_.size(); + } + else { + for (BucketsSpace::const_iterator x = buckets_space_.begin(); x != buckets_space_.end(); ++x) { + stats.bucket_sizes_.push_back((lsh::FeatureIndex)x->second.size()); + stats.bucket_size_mean_ += x->second.size(); + } + stats.bucket_size_mean_ /= buckets_space_.size(); + stats.n_buckets_ = buckets_space_.size(); + } + + std::sort(stats.bucket_sizes_.begin(), stats.bucket_sizes_.end()); + + // BOOST_FOREACH(int size, stats.bucket_sizes_) + // std::cout << size << " "; + // std::cout << std::endl; + stats.bucket_size_median_ = stats.bucket_sizes_[stats.bucket_sizes_.size() / 2]; + stats.bucket_size_min_ = stats.bucket_sizes_.front(); + stats.bucket_size_max_ = stats.bucket_sizes_.back(); + + // TODO compute mean and std + /*float mean, stddev; + stats.bucket_size_mean_ = mean; + stats.bucket_size_std_dev = stddev;*/ + + // Include a histogram of the buckets + unsigned int bin_start = 0; + unsigned int bin_end = 20; + bool is_new_bin = true; + for (std::vector<unsigned int>::iterator iterator = stats.bucket_sizes_.begin(), end = stats.bucket_sizes_.end(); iterator + != end; ) + if (*iterator < bin_end) { + if (is_new_bin) { + stats.size_histogram_.push_back(std::vector<unsigned int>(3, 0)); + stats.size_histogram_.back()[0] = bin_start; + stats.size_histogram_.back()[1] = bin_end - 1; + is_new_bin = false; + } + ++stats.size_histogram_.back()[2]; + ++iterator; + } + else { + bin_start += 20; + bin_end += 20; + is_new_bin = true; + } + + return stats; +} + +// End the two namespaces +} +} + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +#endif /* OPENCV_FLANN_LSH_TABLE_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/matrix.h b/thirdparty/linux/include/opencv2/flann/matrix.h new file mode 100644 index 0000000..51b6c63 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/matrix.h @@ -0,0 +1,116 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_DATASET_H_ +#define OPENCV_FLANN_DATASET_H_ + +#include <stdio.h> + +#include "general.h" + +namespace cvflann +{ + +/** + * Class that implements a simple rectangular matrix stored in a memory buffer and + * provides convenient matrix-like access using the [] operators. + */ +template <typename T> +class Matrix +{ +public: + typedef T type; + + size_t rows; + size_t cols; + size_t stride; + T* data; + + Matrix() : rows(0), cols(0), stride(0), data(NULL) + { + } + + Matrix(T* data_, size_t rows_, size_t cols_, size_t stride_ = 0) : + rows(rows_), cols(cols_), stride(stride_), data(data_) + { + if (stride==0) stride = cols; + } + + /** + * Convenience function for deallocating the storage data. + */ + FLANN_DEPRECATED void free() + { + fprintf(stderr, "The cvflann::Matrix<T>::free() method is deprecated " + "and it does not do any memory deallocation any more. You are" + "responsible for deallocating the matrix memory (by doing" + "'delete[] matrix.data' for example)"); + } + + /** + * Operator that return a (pointer to a) row of the data. + */ + T* operator[](size_t index) const + { + return data+index*stride; + } +}; + + +class UntypedMatrix +{ +public: + size_t rows; + size_t cols; + void* data; + flann_datatype_t type; + + UntypedMatrix(void* data_, long rows_, long cols_) : + rows(rows_), cols(cols_), data(data_) + { + } + + ~UntypedMatrix() + { + } + + + template<typename T> + Matrix<T> as() + { + return Matrix<T>((T*)data, rows, cols); + } +}; + + + +} + +#endif //OPENCV_FLANN_DATASET_H_ diff --git a/thirdparty/linux/include/opencv2/flann/miniflann.hpp b/thirdparty/linux/include/opencv2/flann/miniflann.hpp new file mode 100644 index 0000000..5d25f5e --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/miniflann.hpp @@ -0,0 +1,158 @@ +/*M/////////////////////////////////////////////////////////////////////////////////////// +// +// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. +// +// By downloading, copying, installing or using the software you agree to this license. +// If you do not agree to this license, do not download, install, +// copy or use the software. +// +// +// License Agreement +// For Open Source Computer Vision Library +// +// Copyright (C) 2000-2008, Intel Corporation, all rights reserved. +// Copyright (C) 2009, Willow Garage Inc., all rights reserved. +// Third party copyrights are property of their respective owners. +// +// Redistribution and use in source and binary forms, with or without modification, +// are permitted provided that the following conditions are met: +// +// * Redistribution's of source code must retain the above copyright notice, +// this list of conditions and the following disclaimer. +// +// * Redistribution's 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. +// +// * The name of the copyright holders may not be used to endorse or promote products +// derived from this software without specific prior written permission. +// +// This software is provided by the copyright holders and contributors "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 Intel Corporation or contributors 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. +// +//M*/ + +#ifndef OPENCV_MINIFLANN_HPP +#define OPENCV_MINIFLANN_HPP + +#include "opencv2/core.hpp" +#include "opencv2/flann/defines.h" + +namespace cv +{ + +namespace flann +{ + +struct CV_EXPORTS IndexParams +{ + IndexParams(); + ~IndexParams(); + + String getString(const String& key, const String& defaultVal=String()) const; + int getInt(const String& key, int defaultVal=-1) const; + double getDouble(const String& key, double defaultVal=-1) const; + + void setString(const String& key, const String& value); + void setInt(const String& key, int value); + void setDouble(const String& key, double value); + void setFloat(const String& key, float value); + void setBool(const String& key, bool value); + void setAlgorithm(int value); + + void getAll(std::vector<String>& names, + std::vector<int>& types, + std::vector<String>& strValues, + std::vector<double>& numValues) const; + + void* params; +}; + +struct CV_EXPORTS KDTreeIndexParams : public IndexParams +{ + KDTreeIndexParams(int trees=4); +}; + +struct CV_EXPORTS LinearIndexParams : public IndexParams +{ + LinearIndexParams(); +}; + +struct CV_EXPORTS CompositeIndexParams : public IndexParams +{ + CompositeIndexParams(int trees = 4, int branching = 32, int iterations = 11, + cvflann::flann_centers_init_t centers_init = cvflann::FLANN_CENTERS_RANDOM, float cb_index = 0.2f ); +}; + +struct CV_EXPORTS AutotunedIndexParams : public IndexParams +{ + AutotunedIndexParams(float target_precision = 0.8f, float build_weight = 0.01f, + float memory_weight = 0, float sample_fraction = 0.1f); +}; + +struct CV_EXPORTS HierarchicalClusteringIndexParams : public IndexParams +{ + HierarchicalClusteringIndexParams(int branching = 32, + cvflann::flann_centers_init_t centers_init = cvflann::FLANN_CENTERS_RANDOM, int trees = 4, int leaf_size = 100 ); +}; + +struct CV_EXPORTS KMeansIndexParams : public IndexParams +{ + KMeansIndexParams(int branching = 32, int iterations = 11, + cvflann::flann_centers_init_t centers_init = cvflann::FLANN_CENTERS_RANDOM, float cb_index = 0.2f ); +}; + +struct CV_EXPORTS LshIndexParams : public IndexParams +{ + LshIndexParams(int table_number, int key_size, int multi_probe_level); +}; + +struct CV_EXPORTS SavedIndexParams : public IndexParams +{ + SavedIndexParams(const String& filename); +}; + +struct CV_EXPORTS SearchParams : public IndexParams +{ + SearchParams( int checks = 32, float eps = 0, bool sorted = true ); +}; + +class CV_EXPORTS_W Index +{ +public: + CV_WRAP Index(); + CV_WRAP Index(InputArray features, const IndexParams& params, cvflann::flann_distance_t distType=cvflann::FLANN_DIST_L2); + virtual ~Index(); + + CV_WRAP virtual void build(InputArray features, const IndexParams& params, cvflann::flann_distance_t distType=cvflann::FLANN_DIST_L2); + CV_WRAP virtual void knnSearch(InputArray query, OutputArray indices, + OutputArray dists, int knn, const SearchParams& params=SearchParams()); + + CV_WRAP virtual int radiusSearch(InputArray query, OutputArray indices, + OutputArray dists, double radius, int maxResults, + const SearchParams& params=SearchParams()); + + CV_WRAP virtual void save(const String& filename) const; + CV_WRAP virtual bool load(InputArray features, const String& filename); + CV_WRAP virtual void release(); + CV_WRAP cvflann::flann_distance_t getDistance() const; + CV_WRAP cvflann::flann_algorithm_t getAlgorithm() const; + +protected: + cvflann::flann_distance_t distType; + cvflann::flann_algorithm_t algo; + int featureType; + void* index; +}; + +} } // namespace cv::flann + +#endif diff --git a/thirdparty/linux/include/opencv2/flann/nn_index.h b/thirdparty/linux/include/opencv2/flann/nn_index.h new file mode 100644 index 0000000..381d4bc --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/nn_index.h @@ -0,0 +1,177 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_NNINDEX_H +#define OPENCV_FLANN_NNINDEX_H + +#include "general.h" +#include "matrix.h" +#include "result_set.h" +#include "params.h" + +namespace cvflann +{ + +/** + * Nearest-neighbour index base class + */ +template <typename Distance> +class NNIndex +{ + typedef typename Distance::ElementType ElementType; + typedef typename Distance::ResultType DistanceType; + +public: + + virtual ~NNIndex() {} + + /** + * \brief Builds the index + */ + virtual void buildIndex() = 0; + + /** + * \brief Perform k-nearest neighbor search + * \param[in] queries The query points for which to find the nearest neighbors + * \param[out] indices The indices of the nearest neighbors found + * \param[out] dists Distances to the nearest neighbors found + * \param[in] knn Number of nearest neighbors to return + * \param[in] params Search parameters + */ + virtual void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params) + { + assert(queries.cols == veclen()); + assert(indices.rows >= queries.rows); + assert(dists.rows >= queries.rows); + assert(int(indices.cols) >= knn); + assert(int(dists.cols) >= knn); + +#if 0 + KNNResultSet<DistanceType> resultSet(knn); + for (size_t i = 0; i < queries.rows; i++) { + resultSet.init(indices[i], dists[i]); + findNeighbors(resultSet, queries[i], params); + } +#else + KNNUniqueResultSet<DistanceType> resultSet(knn); + for (size_t i = 0; i < queries.rows; i++) { + resultSet.clear(); + findNeighbors(resultSet, queries[i], params); + if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices[i], dists[i], knn); + else resultSet.copy(indices[i], dists[i], knn); + } +#endif + } + + /** + * \brief Perform radius search + * \param[in] query The query point + * \param[out] indices The indinces of the neighbors found within the given radius + * \param[out] dists The distances to the nearest neighbors found + * \param[in] radius The radius used for search + * \param[in] params Search parameters + * \returns Number of neighbors found + */ + virtual int radiusSearch(const Matrix<ElementType>& query, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params) + { + if (query.rows != 1) { + fprintf(stderr, "I can only search one feature at a time for range search\n"); + return -1; + } + assert(query.cols == veclen()); + assert(indices.cols == dists.cols); + + int n = 0; + int* indices_ptr = NULL; + DistanceType* dists_ptr = NULL; + if (indices.cols > 0) { + n = (int)indices.cols; + indices_ptr = indices[0]; + dists_ptr = dists[0]; + } + + RadiusUniqueResultSet<DistanceType> resultSet((DistanceType)radius); + resultSet.clear(); + findNeighbors(resultSet, query[0], params); + if (n>0) { + if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices_ptr, dists_ptr, n); + else resultSet.copy(indices_ptr, dists_ptr, n); + } + + return (int)resultSet.size(); + } + + /** + * \brief Saves the index to a stream + * \param stream The stream to save the index to + */ + virtual void saveIndex(FILE* stream) = 0; + + /** + * \brief Loads the index from a stream + * \param stream The stream from which the index is loaded + */ + virtual void loadIndex(FILE* stream) = 0; + + /** + * \returns number of features in this index. + */ + virtual size_t size() const = 0; + + /** + * \returns The dimensionality of the features in this index. + */ + virtual size_t veclen() const = 0; + + /** + * \returns The amount of memory (in bytes) used by the index. + */ + virtual int usedMemory() const = 0; + + /** + * \returns The index type (kdtree, kmeans,...) + */ + virtual flann_algorithm_t getType() const = 0; + + /** + * \returns The index parameters + */ + virtual IndexParams getParameters() const = 0; + + + /** + * \brief Method that searches for nearest-neighbours + */ + virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) = 0; +}; + +} + +#endif //OPENCV_FLANN_NNINDEX_H diff --git a/thirdparty/linux/include/opencv2/flann/object_factory.h b/thirdparty/linux/include/opencv2/flann/object_factory.h new file mode 100644 index 0000000..7f971c5 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/object_factory.h @@ -0,0 +1,91 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_OBJECT_FACTORY_H_ +#define OPENCV_FLANN_OBJECT_FACTORY_H_ + +#include <map> + +namespace cvflann +{ + +class CreatorNotFound +{ +}; + +template<typename BaseClass, + typename UniqueIdType, + typename ObjectCreator = BaseClass* (*)()> +class ObjectFactory +{ + typedef ObjectFactory<BaseClass,UniqueIdType,ObjectCreator> ThisClass; + typedef std::map<UniqueIdType, ObjectCreator> ObjectRegistry; + + // singleton class, private constructor + ObjectFactory() {} + +public: + + bool subscribe(UniqueIdType id, ObjectCreator creator) + { + if (object_registry.find(id) != object_registry.end()) return false; + + object_registry[id] = creator; + return true; + } + + bool unregister(UniqueIdType id) + { + return object_registry.erase(id) == 1; + } + + ObjectCreator create(UniqueIdType id) + { + typename ObjectRegistry::const_iterator iter = object_registry.find(id); + + if (iter == object_registry.end()) { + throw CreatorNotFound(); + } + + return iter->second; + } + + static ThisClass& instance() + { + static ThisClass the_factory; + return the_factory; + } +private: + ObjectRegistry object_registry; +}; + +} + +#endif /* OPENCV_FLANN_OBJECT_FACTORY_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/params.h b/thirdparty/linux/include/opencv2/flann/params.h new file mode 100644 index 0000000..95ef4cd --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/params.h @@ -0,0 +1,99 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2011 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2011 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_PARAMS_H_ +#define OPENCV_FLANN_PARAMS_H_ + +#include "any.h" +#include "general.h" +#include <iostream> +#include <map> + + +namespace cvflann +{ + +typedef std::map<cv::String, any> IndexParams; + +struct SearchParams : public IndexParams +{ + SearchParams(int checks = 32, float eps = 0, bool sorted = true ) + { + // how many leafs to visit when searching for neighbours (-1 for unlimited) + (*this)["checks"] = checks; + // search for eps-approximate neighbours (default: 0) + (*this)["eps"] = eps; + // only for radius search, require neighbours sorted by distance (default: true) + (*this)["sorted"] = sorted; + } +}; + + +template<typename T> +T get_param(const IndexParams& params, cv::String name, const T& default_value) +{ + IndexParams::const_iterator it = params.find(name); + if (it != params.end()) { + return it->second.cast<T>(); + } + else { + return default_value; + } +} + +template<typename T> +T get_param(const IndexParams& params, cv::String name) +{ + IndexParams::const_iterator it = params.find(name); + if (it != params.end()) { + return it->second.cast<T>(); + } + else { + throw FLANNException(cv::String("Missing parameter '")+name+cv::String("' in the parameters given")); + } +} + +inline void print_params(const IndexParams& params, std::ostream& stream) +{ + IndexParams::const_iterator it; + + for(it=params.begin(); it!=params.end(); ++it) { + stream << it->first << " : " << it->second << std::endl; + } +} + +inline void print_params(const IndexParams& params) +{ + print_params(params, std::cout); +} + +} + + +#endif /* OPENCV_FLANN_PARAMS_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/random.h b/thirdparty/linux/include/opencv2/flann/random.h new file mode 100644 index 0000000..a3cf5ec --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/random.h @@ -0,0 +1,133 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_RANDOM_H +#define OPENCV_FLANN_RANDOM_H + +#include <algorithm> +#include <cstdlib> +#include <vector> + +#include "general.h" + +namespace cvflann +{ + +/** + * Seeds the random number generator + * @param seed Random seed + */ +inline void seed_random(unsigned int seed) +{ + srand(seed); +} + +/* + * Generates a random double value. + */ +/** + * Generates a random double value. + * @param high Upper limit + * @param low Lower limit + * @return Random double value + */ +inline double rand_double(double high = 1.0, double low = 0) +{ + return low + ((high-low) * (std::rand() / (RAND_MAX + 1.0))); +} + +/** + * Generates a random integer value. + * @param high Upper limit + * @param low Lower limit + * @return Random integer value + */ +inline int rand_int(int high = RAND_MAX, int low = 0) +{ + return low + (int) ( double(high-low) * (std::rand() / (RAND_MAX + 1.0))); +} + +/** + * Random number generator that returns a distinct number from + * the [0,n) interval each time. + */ +class UniqueRandom +{ + std::vector<int> vals_; + int size_; + int counter_; + +public: + /** + * Constructor. + * @param n Size of the interval from which to generate + * @return + */ + UniqueRandom(int n) + { + init(n); + } + + /** + * Initializes the number generator. + * @param n the size of the interval from which to generate random numbers. + */ + void init(int n) + { + // create and initialize an array of size n + vals_.resize(n); + size_ = n; + for (int i = 0; i < size_; ++i) vals_[i] = i; + + // shuffle the elements in the array + std::random_shuffle(vals_.begin(), vals_.end()); + + counter_ = 0; + } + + /** + * Return a distinct random integer in greater or equal to 0 and less + * than 'n' on each call. It should be called maximum 'n' times. + * Returns: a random integer + */ + int next() + { + if (counter_ == size_) { + return -1; + } + else { + return vals_[counter_++]; + } + } +}; + +} + +#endif //OPENCV_FLANN_RANDOM_H diff --git a/thirdparty/linux/include/opencv2/flann/result_set.h b/thirdparty/linux/include/opencv2/flann/result_set.h new file mode 100644 index 0000000..9750019 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/result_set.h @@ -0,0 +1,543 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_RESULTSET_H +#define OPENCV_FLANN_RESULTSET_H + +#include <algorithm> +#include <cstring> +#include <iostream> +#include <limits> +#include <set> +#include <vector> + +namespace cvflann +{ + +/* This record represents a branch point when finding neighbors in + the tree. It contains a record of the minimum distance to the query + point, as well as the node at which the search resumes. + */ + +template <typename T, typename DistanceType> +struct BranchStruct +{ + T node; /* Tree node at which search resumes */ + DistanceType mindist; /* Minimum distance to query for all nodes below. */ + + BranchStruct() {} + BranchStruct(const T& aNode, DistanceType dist) : node(aNode), mindist(dist) {} + + bool operator<(const BranchStruct<T, DistanceType>& rhs) const + { + return mindist<rhs.mindist; + } +}; + + +template <typename DistanceType> +class ResultSet +{ +public: + virtual ~ResultSet() {} + + virtual bool full() const = 0; + + virtual void addPoint(DistanceType dist, int index) = 0; + + virtual DistanceType worstDist() const = 0; + +}; + +/** + * KNNSimpleResultSet does not ensure that the element it holds are unique. + * Is used in those cases where the nearest neighbour algorithm used does not + * attempt to insert the same element multiple times. + */ +template <typename DistanceType> +class KNNSimpleResultSet : public ResultSet<DistanceType> +{ + int* indices; + DistanceType* dists; + int capacity; + int count; + DistanceType worst_distance_; + +public: + KNNSimpleResultSet(int capacity_) : capacity(capacity_), count(0) + { + } + + void init(int* indices_, DistanceType* dists_) + { + indices = indices_; + dists = dists_; + count = 0; + worst_distance_ = (std::numeric_limits<DistanceType>::max)(); + dists[capacity-1] = worst_distance_; + } + + size_t size() const + { + return count; + } + + bool full() const + { + return count == capacity; + } + + + void addPoint(DistanceType dist, int index) + { + if (dist >= worst_distance_) return; + int i; + for (i=count; i>0; --i) { +#ifdef FLANN_FIRST_MATCH + if ( (dists[i-1]>dist) || ((dist==dists[i-1])&&(indices[i-1]>index)) ) +#else + if (dists[i-1]>dist) +#endif + { + if (i<capacity) { + dists[i] = dists[i-1]; + indices[i] = indices[i-1]; + } + } + else break; + } + if (count < capacity) ++count; + dists[i] = dist; + indices[i] = index; + worst_distance_ = dists[capacity-1]; + } + + DistanceType worstDist() const + { + return worst_distance_; + } +}; + +/** + * K-Nearest neighbour result set. Ensures that the elements inserted are unique + */ +template <typename DistanceType> +class KNNResultSet : public ResultSet<DistanceType> +{ + int* indices; + DistanceType* dists; + int capacity; + int count; + DistanceType worst_distance_; + +public: + KNNResultSet(int capacity_) : capacity(capacity_), count(0) + { + } + + void init(int* indices_, DistanceType* dists_) + { + indices = indices_; + dists = dists_; + count = 0; + worst_distance_ = (std::numeric_limits<DistanceType>::max)(); + dists[capacity-1] = worst_distance_; + } + + size_t size() const + { + return count; + } + + bool full() const + { + return count == capacity; + } + + + void addPoint(DistanceType dist, int index) + { + if (dist >= worst_distance_) return; + int i; + for (i = count; i > 0; --i) { +#ifdef FLANN_FIRST_MATCH + if ( (dists[i-1]<=dist) && ((dist!=dists[i-1])||(indices[i-1]<=index)) ) +#else + if (dists[i-1]<=dist) +#endif + { + // Check for duplicate indices + int j = i - 1; + while ((j >= 0) && (dists[j] == dist)) { + if (indices[j] == index) { + return; + } + --j; + } + break; + } + } + + if (count < capacity) ++count; + for (int j = count-1; j > i; --j) { + dists[j] = dists[j-1]; + indices[j] = indices[j-1]; + } + dists[i] = dist; + indices[i] = index; + worst_distance_ = dists[capacity-1]; + } + + DistanceType worstDist() const + { + return worst_distance_; + } +}; + + +/** + * A result-set class used when performing a radius based search. + */ +template <typename DistanceType> +class RadiusResultSet : public ResultSet<DistanceType> +{ + DistanceType radius; + int* indices; + DistanceType* dists; + size_t capacity; + size_t count; + +public: + RadiusResultSet(DistanceType radius_, int* indices_, DistanceType* dists_, int capacity_) : + radius(radius_), indices(indices_), dists(dists_), capacity(capacity_) + { + init(); + } + + ~RadiusResultSet() + { + } + + void init() + { + count = 0; + } + + size_t size() const + { + return count; + } + + bool full() const + { + return true; + } + + void addPoint(DistanceType dist, int index) + { + if (dist<radius) { + if ((capacity>0)&&(count < capacity)) { + dists[count] = dist; + indices[count] = index; + } + count++; + } + } + + DistanceType worstDist() const + { + return radius; + } + +}; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** Class that holds the k NN neighbors + * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays + */ +template<typename DistanceType> +class UniqueResultSet : public ResultSet<DistanceType> +{ +public: + struct DistIndex + { + DistIndex(DistanceType dist, unsigned int index) : + dist_(dist), index_(index) + { + } + bool operator<(const DistIndex dist_index) const + { + return (dist_ < dist_index.dist_) || ((dist_ == dist_index.dist_) && index_ < dist_index.index_); + } + DistanceType dist_; + unsigned int index_; + }; + + /** Default cosntructor */ + UniqueResultSet() : + worst_distance_(std::numeric_limits<DistanceType>::max()) + { + } + + /** Check the status of the set + * @return true if we have k NN + */ + inline bool full() const + { + return is_full_; + } + + /** Remove all elements in the set + */ + virtual void clear() = 0; + + /** Copy the set to two C arrays + * @param indices pointer to a C array of indices + * @param dist pointer to a C array of distances + * @param n_neighbors the number of neighbors to copy + */ + virtual void copy(int* indices, DistanceType* dist, int n_neighbors = -1) const + { + if (n_neighbors < 0) { + for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end = + dist_indices_.end(); dist_index != dist_index_end; ++dist_index, ++indices, ++dist) { + *indices = dist_index->index_; + *dist = dist_index->dist_; + } + } + else { + int i = 0; + for (typename std::set<DistIndex>::const_iterator dist_index = dist_indices_.begin(), dist_index_end = + dist_indices_.end(); (dist_index != dist_index_end) && (i < n_neighbors); ++dist_index, ++indices, ++dist, ++i) { + *indices = dist_index->index_; + *dist = dist_index->dist_; + } + } + } + + /** Copy the set to two C arrays but sort it according to the distance first + * @param indices pointer to a C array of indices + * @param dist pointer to a C array of distances + * @param n_neighbors the number of neighbors to copy + */ + virtual void sortAndCopy(int* indices, DistanceType* dist, int n_neighbors = -1) const + { + copy(indices, dist, n_neighbors); + } + + /** The number of neighbors in the set + * @return + */ + size_t size() const + { + return dist_indices_.size(); + } + + /** The distance of the furthest neighbor + * If we don't have enough neighbors, it returns the max possible value + * @return + */ + inline DistanceType worstDist() const + { + return worst_distance_; + } +protected: + /** Flag to say if the set is full */ + bool is_full_; + + /** The worst distance found so far */ + DistanceType worst_distance_; + + /** The best candidates so far */ + std::set<DistIndex> dist_indices_; +}; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** Class that holds the k NN neighbors + * Faster than KNNResultSet as it uses a binary heap and does not maintain two arrays + */ +template<typename DistanceType> +class KNNUniqueResultSet : public UniqueResultSet<DistanceType> +{ +public: + /** Constructor + * @param capacity the number of neighbors to store at max + */ + KNNUniqueResultSet(unsigned int capacity) : capacity_(capacity) + { + this->is_full_ = false; + this->clear(); + } + + /** Add a possible candidate to the best neighbors + * @param dist distance for that neighbor + * @param index index of that neighbor + */ + inline void addPoint(DistanceType dist, int index) + { + // Don't do anything if we are worse than the worst + if (dist >= worst_distance_) return; + dist_indices_.insert(DistIndex(dist, index)); + + if (is_full_) { + if (dist_indices_.size() > capacity_) { + dist_indices_.erase(*dist_indices_.rbegin()); + worst_distance_ = dist_indices_.rbegin()->dist_; + } + } + else if (dist_indices_.size() == capacity_) { + is_full_ = true; + worst_distance_ = dist_indices_.rbegin()->dist_; + } + } + + /** Remove all elements in the set + */ + void clear() + { + dist_indices_.clear(); + worst_distance_ = std::numeric_limits<DistanceType>::max(); + is_full_ = false; + } + +protected: + typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex; + using UniqueResultSet<DistanceType>::is_full_; + using UniqueResultSet<DistanceType>::worst_distance_; + using UniqueResultSet<DistanceType>::dist_indices_; + + /** The number of neighbors to keep */ + unsigned int capacity_; +}; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** Class that holds the radius nearest neighbors + * It is more accurate than RadiusResult as it is not limited in the number of neighbors + */ +template<typename DistanceType> +class RadiusUniqueResultSet : public UniqueResultSet<DistanceType> +{ +public: + /** Constructor + * @param radius the maximum distance of a neighbor + */ + RadiusUniqueResultSet(DistanceType radius) : + radius_(radius) + { + is_full_ = true; + } + + /** Add a possible candidate to the best neighbors + * @param dist distance for that neighbor + * @param index index of that neighbor + */ + void addPoint(DistanceType dist, int index) + { + if (dist <= radius_) dist_indices_.insert(DistIndex(dist, index)); + } + + /** Remove all elements in the set + */ + inline void clear() + { + dist_indices_.clear(); + } + + + /** Check the status of the set + * @return alwys false + */ + inline bool full() const + { + return true; + } + + /** The distance of the furthest neighbor + * If we don't have enough neighbors, it returns the max possible value + * @return + */ + inline DistanceType worstDist() const + { + return radius_; + } +private: + typedef typename UniqueResultSet<DistanceType>::DistIndex DistIndex; + using UniqueResultSet<DistanceType>::dist_indices_; + using UniqueResultSet<DistanceType>::is_full_; + + /** The furthest distance a neighbor can be */ + DistanceType radius_; +}; + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/** Class that holds the k NN neighbors within a radius distance + */ +template<typename DistanceType> +class KNNRadiusUniqueResultSet : public KNNUniqueResultSet<DistanceType> +{ +public: + /** Constructor + * @param capacity the number of neighbors to store at max + * @param radius the maximum distance of a neighbor + */ + KNNRadiusUniqueResultSet(unsigned int capacity, DistanceType radius) + { + this->capacity_ = capacity; + this->radius_ = radius; + this->dist_indices_.reserve(capacity_); + this->clear(); + } + + /** Remove all elements in the set + */ + void clear() + { + dist_indices_.clear(); + worst_distance_ = radius_; + is_full_ = false; + } +private: + using KNNUniqueResultSet<DistanceType>::dist_indices_; + using KNNUniqueResultSet<DistanceType>::is_full_; + using KNNUniqueResultSet<DistanceType>::worst_distance_; + + /** The maximum number of neighbors to consider */ + unsigned int capacity_; + + /** The maximum distance of a neighbor */ + DistanceType radius_; +}; +} + +#endif //OPENCV_FLANN_RESULTSET_H diff --git a/thirdparty/linux/include/opencv2/flann/sampling.h b/thirdparty/linux/include/opencv2/flann/sampling.h new file mode 100644 index 0000000..396f177 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/sampling.h @@ -0,0 +1,81 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_SAMPLING_H_ +#define OPENCV_FLANN_SAMPLING_H_ + +#include "matrix.h" +#include "random.h" + +namespace cvflann +{ + +template<typename T> +Matrix<T> random_sample(Matrix<T>& srcMatrix, long size, bool remove = false) +{ + Matrix<T> newSet(new T[size * srcMatrix.cols], size,srcMatrix.cols); + + T* src,* dest; + for (long i=0; i<size; ++i) { + long r = rand_int((int)(srcMatrix.rows-i)); + dest = newSet[i]; + src = srcMatrix[r]; + std::copy(src, src+srcMatrix.cols, dest); + if (remove) { + src = srcMatrix[srcMatrix.rows-i-1]; + dest = srcMatrix[r]; + std::copy(src, src+srcMatrix.cols, dest); + } + } + if (remove) { + srcMatrix.rows -= size; + } + return newSet; +} + +template<typename T> +Matrix<T> random_sample(const Matrix<T>& srcMatrix, size_t size) +{ + UniqueRandom rand((int)srcMatrix.rows); + Matrix<T> newSet(new T[size * srcMatrix.cols], size,srcMatrix.cols); + + T* src,* dest; + for (size_t i=0; i<size; ++i) { + long r = rand.next(); + dest = newSet[i]; + src = srcMatrix[r]; + std::copy(src, src+srcMatrix.cols, dest); + } + return newSet; +} + +} // namespace + + +#endif /* OPENCV_FLANN_SAMPLING_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/saving.h b/thirdparty/linux/include/opencv2/flann/saving.h new file mode 100644 index 0000000..7e3bea5 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/saving.h @@ -0,0 +1,187 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 NNIndexGOODS 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 OPENCV_FLANN_SAVING_H_ +#define OPENCV_FLANN_SAVING_H_ + +#include <cstring> +#include <vector> + +#include "general.h" +#include "nn_index.h" + +#ifdef FLANN_SIGNATURE_ +#undef FLANN_SIGNATURE_ +#endif +#define FLANN_SIGNATURE_ "FLANN_INDEX" + +namespace cvflann +{ + +template <typename T> +struct Datatype {}; +template<> +struct Datatype<char> { static flann_datatype_t type() { return FLANN_INT8; } }; +template<> +struct Datatype<short> { static flann_datatype_t type() { return FLANN_INT16; } }; +template<> +struct Datatype<int> { static flann_datatype_t type() { return FLANN_INT32; } }; +template<> +struct Datatype<unsigned char> { static flann_datatype_t type() { return FLANN_UINT8; } }; +template<> +struct Datatype<unsigned short> { static flann_datatype_t type() { return FLANN_UINT16; } }; +template<> +struct Datatype<unsigned int> { static flann_datatype_t type() { return FLANN_UINT32; } }; +template<> +struct Datatype<float> { static flann_datatype_t type() { return FLANN_FLOAT32; } }; +template<> +struct Datatype<double> { static flann_datatype_t type() { return FLANN_FLOAT64; } }; + + +/** + * Structure representing the index header. + */ +struct IndexHeader +{ + char signature[16]; + char version[16]; + flann_datatype_t data_type; + flann_algorithm_t index_type; + size_t rows; + size_t cols; +}; + +/** + * Saves index header to stream + * + * @param stream - Stream to save to + * @param index - The index to save + */ +template<typename Distance> +void save_header(FILE* stream, const NNIndex<Distance>& index) +{ + IndexHeader header; + memset(header.signature, 0, sizeof(header.signature)); + strcpy(header.signature, FLANN_SIGNATURE_); + memset(header.version, 0, sizeof(header.version)); + strcpy(header.version, FLANN_VERSION_); + header.data_type = Datatype<typename Distance::ElementType>::type(); + header.index_type = index.getType(); + header.rows = index.size(); + header.cols = index.veclen(); + + std::fwrite(&header, sizeof(header),1,stream); +} + + +/** + * + * @param stream - Stream to load from + * @return Index header + */ +inline IndexHeader load_header(FILE* stream) +{ + IndexHeader header; + size_t read_size = fread(&header,sizeof(header),1,stream); + + if (read_size!=(size_t)1) { + throw FLANNException("Invalid index file, cannot read"); + } + + if (strcmp(header.signature,FLANN_SIGNATURE_)!=0) { + throw FLANNException("Invalid index file, wrong signature"); + } + + return header; + +} + + +template<typename T> +void save_value(FILE* stream, const T& value, size_t count = 1) +{ + fwrite(&value, sizeof(value),count, stream); +} + +template<typename T> +void save_value(FILE* stream, const cvflann::Matrix<T>& value) +{ + fwrite(&value, sizeof(value),1, stream); + fwrite(value.data, sizeof(T),value.rows*value.cols, stream); +} + +template<typename T> +void save_value(FILE* stream, const std::vector<T>& value) +{ + size_t size = value.size(); + fwrite(&size, sizeof(size_t), 1, stream); + fwrite(&value[0], sizeof(T), size, stream); +} + +template<typename T> +void load_value(FILE* stream, T& value, size_t count = 1) +{ + size_t read_cnt = fread(&value, sizeof(value), count, stream); + if (read_cnt != count) { + throw FLANNException("Cannot read from file"); + } +} + +template<typename T> +void load_value(FILE* stream, cvflann::Matrix<T>& value) +{ + size_t read_cnt = fread(&value, sizeof(value), 1, stream); + if (read_cnt != 1) { + throw FLANNException("Cannot read from file"); + } + value.data = new T[value.rows*value.cols]; + read_cnt = fread(value.data, sizeof(T), value.rows*value.cols, stream); + if (read_cnt != (size_t)(value.rows*value.cols)) { + throw FLANNException("Cannot read from file"); + } +} + + +template<typename T> +void load_value(FILE* stream, std::vector<T>& value) +{ + size_t size; + size_t read_cnt = fread(&size, sizeof(size_t), 1, stream); + if (read_cnt!=1) { + throw FLANNException("Cannot read from file"); + } + value.resize(size); + read_cnt = fread(&value[0], sizeof(T), size, stream); + if (read_cnt != size) { + throw FLANNException("Cannot read from file"); + } +} + +} + +#endif /* OPENCV_FLANN_SAVING_H_ */ diff --git a/thirdparty/linux/include/opencv2/flann/simplex_downhill.h b/thirdparty/linux/include/opencv2/flann/simplex_downhill.h new file mode 100644 index 0000000..145901a --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/simplex_downhill.h @@ -0,0 +1,186 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_SIMPLEX_DOWNHILL_H_ +#define OPENCV_FLANN_SIMPLEX_DOWNHILL_H_ + +namespace cvflann +{ + +/** + Adds val to array vals (and point to array points) and keeping the arrays sorted by vals. + */ +template <typename T> +void addValue(int pos, float val, float* vals, T* point, T* points, int n) +{ + vals[pos] = val; + for (int i=0; i<n; ++i) { + points[pos*n+i] = point[i]; + } + + // bubble down + int j=pos; + while (j>0 && vals[j]<vals[j-1]) { + swap(vals[j],vals[j-1]); + for (int i=0; i<n; ++i) { + swap(points[j*n+i],points[(j-1)*n+i]); + } + --j; + } +} + + +/** + Simplex downhill optimization function. + Preconditions: points is a 2D mattrix of size (n+1) x n + func is the cost function taking n an array of n params and returning float + vals is the cost function in the n+1 simplex points, if NULL it will be computed + + Postcondition: returns optimum value and points[0..n] are the optimum parameters + */ +template <typename T, typename F> +float optimizeSimplexDownhill(T* points, int n, F func, float* vals = NULL ) +{ + const int MAX_ITERATIONS = 10; + + assert(n>0); + + T* p_o = new T[n]; + T* p_r = new T[n]; + T* p_e = new T[n]; + + int alpha = 1; + + int iterations = 0; + + bool ownVals = false; + if (vals == NULL) { + ownVals = true; + vals = new float[n+1]; + for (int i=0; i<n+1; ++i) { + float val = func(points+i*n); + addValue(i, val, vals, points+i*n, points, n); + } + } + int nn = n*n; + + while (true) { + + if (iterations++ > MAX_ITERATIONS) break; + + // compute average of simplex points (except the highest point) + for (int j=0; j<n; ++j) { + p_o[j] = 0; + for (int i=0; i<n; ++i) { + p_o[i] += points[j*n+i]; + } + } + for (int i=0; i<n; ++i) { + p_o[i] /= n; + } + + bool converged = true; + for (int i=0; i<n; ++i) { + if (p_o[i] != points[nn+i]) { + converged = false; + } + } + if (converged) break; + + // trying a reflection + for (int i=0; i<n; ++i) { + p_r[i] = p_o[i] + alpha*(p_o[i]-points[nn+i]); + } + float val_r = func(p_r); + + if ((val_r>=vals[0])&&(val_r<vals[n])) { + // reflection between second highest and lowest + // add it to the simplex + Logger::info("Choosing reflection\n"); + addValue(n, val_r,vals, p_r, points, n); + continue; + } + + if (val_r<vals[0]) { + // value is smaller than smalest in simplex + + // expand some more to see if it drops further + for (int i=0; i<n; ++i) { + p_e[i] = 2*p_r[i]-p_o[i]; + } + float val_e = func(p_e); + + if (val_e<val_r) { + Logger::info("Choosing reflection and expansion\n"); + addValue(n, val_e,vals,p_e,points,n); + } + else { + Logger::info("Choosing reflection\n"); + addValue(n, val_r,vals,p_r,points,n); + } + continue; + } + if (val_r>=vals[n]) { + for (int i=0; i<n; ++i) { + p_e[i] = (p_o[i]+points[nn+i])/2; + } + float val_e = func(p_e); + + if (val_e<vals[n]) { + Logger::info("Choosing contraction\n"); + addValue(n,val_e,vals,p_e,points,n); + continue; + } + } + { + Logger::info("Full contraction\n"); + for (int j=1; j<=n; ++j) { + for (int i=0; i<n; ++i) { + points[j*n+i] = (points[j*n+i]+points[i])/2; + } + float val = func(points+j*n); + addValue(j,val,vals,points+j*n,points,n); + } + } + } + + float bestVal = vals[0]; + + delete[] p_r; + delete[] p_o; + delete[] p_e; + if (ownVals) delete[] vals; + + return bestVal; +} + +} + +#endif //OPENCV_FLANN_SIMPLEX_DOWNHILL_H_ diff --git a/thirdparty/linux/include/opencv2/flann/timer.h b/thirdparty/linux/include/opencv2/flann/timer.h new file mode 100644 index 0000000..f771a34 --- /dev/null +++ b/thirdparty/linux/include/opencv2/flann/timer.h @@ -0,0 +1,94 @@ +/*********************************************************************** + * Software License Agreement (BSD License) + * + * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved. + * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). 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 OPENCV_FLANN_TIMER_H +#define OPENCV_FLANN_TIMER_H + +#include <time.h> +#include "opencv2/core.hpp" +#include "opencv2/core/utility.hpp" + +namespace cvflann +{ + +/** + * A start-stop timer class. + * + * Can be used to time portions of code. + */ +class StartStopTimer +{ + int64 startTime; + +public: + /** + * Value of the timer. + */ + double value; + + + /** + * Constructor. + */ + StartStopTimer() + { + reset(); + } + + /** + * Starts the timer. + */ + void start() + { + startTime = cv::getTickCount(); + } + + /** + * Stops the timer and updates timer value. + */ + void stop() + { + int64 stopTime = cv::getTickCount(); + value += ( (double)stopTime - startTime) / cv::getTickFrequency(); + } + + /** + * Resets the timer value to 0. + */ + void reset() + { + value = 0; + } + +}; + +} + +#endif // FLANN_TIMER_H |