nn_index.h

00001 /***********************************************************************
00002  * Software License Agreement (BSD License)
00003  *
00004  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
00005  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
00006  *
00007  * THE BSD LICENSE
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  *
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *************************************************************************/
00030 
00031 #ifndef OPENCV_FLANN_NNINDEX_H
00032 #define OPENCV_FLANN_NNINDEX_H
00033 
00034 #include "general.h"
00035 #include "matrix.h"
00036 #include "result_set.h"
00037 #include "params.h"
00038 
00039 namespace cvflann
00040 {
00041 
00042 /**
00043  * Nearest-neighbour index base class
00044  */
00045 template <typename Distance>
00046 class NNIndex
00047 {
00048     typedef typename Distance::ElementType ElementType;
00049     typedef typename Distance::ResultType DistanceType;
00050 
00051 public:
00052 
00053     virtual ~NNIndex() {}
00054 
00055     /**
00056      * \brief Builds the index
00057      */
00058     virtual void buildIndex() = 0;
00059 
00060     /**
00061      * \brief Perform k-nearest neighbor search
00062      * \param[in] queries The query points for which to find the nearest neighbors
00063      * \param[out] indices The indices of the nearest neighbors found
00064      * \param[out] dists Distances to the nearest neighbors found
00065      * \param[in] knn Number of nearest neighbors to return
00066      * \param[in] params Search parameters
00067      */
00068     virtual void knnSearch(const Matrix<ElementType> & queries, Matrix<int> & indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params)
00069     {
00070         assert(queries.cols == veclen ());
00071         assert(indices.rows >= queries.rows);
00072         assert(dists.rows >= queries.rows);
00073         assert(int(indices.cols) >= knn);
00074         assert(int(dists.cols) >= knn);
00075 
00076 #if 0
00077         KNNResultSet<DistanceType> resultSet(knn);
00078         for (size_t i = 0; i < queries.rows; i++) {
00079             resultSet.init(indices[i], dists[i]);
00080             findNeighbors(resultSet, queries[i], params);
00081         }
00082 #else
00083         KNNUniqueResultSet<DistanceType> resultSet(knn);
00084         for (size_t i = 0; i < queries.rows; i++) {
00085             resultSet.clear();
00086             findNeighbors(resultSet, queries[i], params);
00087             if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices[i], dists[i], knn);
00088             else resultSet.copy(indices[i], dists[i], knn);
00089         }
00090 #endif
00091     }
00092 
00093     /**
00094      * \brief Perform radius search
00095      * \param[in] query The query point
00096      * \param[out] indices The indinces of the neighbors found within the given radius
00097      * \param[out] dists The distances to the nearest neighbors found
00098      * \param[in] radius The radius used for search
00099      * \param[in] params Search parameters
00100      * \returns Number of neighbors found
00101      */
00102     virtual int radiusSearch(const Matrix<ElementType> & query, Matrix<int> & indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params)
00103     {
00104         if (query.rows != 1) {
00105             fprintf(stderr, "I can only search one feature at a time for range search\n");
00106             return -1;
00107         }
00108         assert(query.cols == veclen ());
00109         assert(indices.cols == dists.cols);
00110 
00111         int n = 0;
00112         int* indices_ptr = NULL;
00113         DistanceType* dists_ptr = NULL;
00114         if (indices.cols > 0) {
00115             n = (int)indices.cols;
00116             indices_ptr = indices[0];
00117             dists_ptr = dists[0];
00118         }
00119 
00120         RadiusUniqueResultSet<DistanceType> resultSet((DistanceType)radius);
00121         resultSet.clear();
00122         findNeighbors(resultSet, query[0], params);
00123         if (n>0) {
00124             if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices_ptr, dists_ptr, n);
00125             else resultSet.copy(indices_ptr, dists_ptr, n);
00126         }
00127 
00128         return (int)resultSet.size();
00129     }
00130 
00131     /**
00132      * \brief Saves the index to a stream
00133      * \param stream The stream to save the index to
00134      */
00135     virtual void saveIndex(FILE* stream) = 0;
00136 
00137     /**
00138      * \brief Loads the index from a stream
00139      * \param stream The stream from which the index is loaded
00140      */
00141     virtual void loadIndex(FILE* stream) = 0;
00142 
00143     /**
00144      * \returns number of features in this index.
00145      */
00146     virtual size_t size () const = 0;
00147 
00148     /**
00149      * \returns The dimensionality of the features in this index.
00150      */
00151     virtual size_t veclen () const = 0;
00152 
00153     /**
00154      * \returns The amount of memory (in bytes) used by the index.
00155      */
00156     virtual int usedMemory () const = 0;
00157 
00158     /**
00159      * \returns The index type (kdtree, kmeans,...)
00160      */
00161     virtual flann_algorithm_t getType () const = 0;
00162 
00163     /**
00164      * \returns The index parameters
00165      */
00166     virtual IndexParams getParameters () const = 0;
00167 
00168 
00169     /**
00170      * \brief Method that searches for nearest-neighbours
00171      */
00172     virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) = 0;
00173 };
00174 
00175 }
00176 
00177 #endif //OPENCV_FLANN_NNINDEX_H
00178