OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / flann / composite_index.h
1 /***********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6  *
7  * THE BSD LICENSE
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  *************************************************************************/
30
31 #ifndef OPENCV_FLANN_COMPOSITE_INDEX_H_
32 #define OPENCV_FLANN_COMPOSITE_INDEX_H_
33
34 #include "general.h"
35 #include "nn_index.h"
36 #include "kdtree_index.h"
37 #include "kmeans_index.h"
38
39 namespace cvflann
40 {
41
42 /**
43  * Index parameters for the CompositeIndex.
44  */
45 struct CompositeIndexParams : public IndexParams
46 {
47     CompositeIndexParams(int trees = 4, int branching = 32, int iterations = 11,
48                          flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM, float cb_index = 0.2 )
49     {
50         (*this)["algorithm"] = FLANN_INDEX_KMEANS;
51         // number of randomized trees to use (for kdtree)
52         (*this)["trees"] = trees;
53         // branching factor
54         (*this)["branching"] = branching;
55         // max iterations to perform in one kmeans clustering (kmeans tree)
56         (*this)["iterations"] = iterations;
57         // algorithm used for picking the initial cluster centers for kmeans tree
58         (*this)["centers_init"] = centers_init;
59         // cluster boundary index. Used when searching the kmeans tree
60         (*this)["cb_index"] = cb_index;
61     }
62 };
63
64
65 /**
66  * This index builds a kd-tree index and a k-means index and performs nearest
67  * neighbour search both indexes. This gives a slight boost in search performance
68  * as some of the neighbours that are missed by one index are found by the other.
69  */
70 template <typename Distance>
71 class CompositeIndex : public NNIndex<Distance>
72 {
73 public:
74     typedef typename Distance::ElementType ElementType;
75     typedef typename Distance::ResultType DistanceType;
76
77     /**
78      * Index constructor
79      * @param inputData dataset containing the points to index
80      * @param params Index parameters
81      * @param d Distance functor
82      * @return
83      */
84     CompositeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = CompositeIndexParams(),
85                    Distance d = Distance()) : index_params_(params)
86     {
87         kdtree_index_ = new KDTreeIndex<Distance>(inputData, params, d);
88         kmeans_index_ = new KMeansIndex<Distance>(inputData, params, d);
89
90     }
91
92     CompositeIndex(const CompositeIndex&);
93     CompositeIndex& operator=(const CompositeIndex&);
94
95     virtual ~CompositeIndex()
96     {
97         delete kdtree_index_;
98         delete kmeans_index_;
99     }
100
101     /**
102      * @return The index type
103      */
104     flann_algorithm_t getType() const
105     {
106         return FLANN_INDEX_COMPOSITE;
107     }
108
109     /**
110      * @return Size of the index
111      */
112     size_t size() const
113     {
114         return kdtree_index_->size();
115     }
116
117     /**
118      * \returns The dimensionality of the features in this index.
119      */
120     size_t veclen() const
121     {
122         return kdtree_index_->veclen();
123     }
124
125     /**
126      * \returns The amount of memory (in bytes) used by the index.
127      */
128     int usedMemory() const
129     {
130         return kmeans_index_->usedMemory() + kdtree_index_->usedMemory();
131     }
132
133     /**
134      * \brief Builds the index
135      */
136     void buildIndex()
137     {
138         Logger::info("Building kmeans tree...\n");
139         kmeans_index_->buildIndex();
140         Logger::info("Building kdtree tree...\n");
141         kdtree_index_->buildIndex();
142     }
143
144     /**
145      * \brief Saves the index to a stream
146      * \param stream The stream to save the index to
147      */
148     void saveIndex(FILE* stream)
149     {
150         kmeans_index_->saveIndex(stream);
151         kdtree_index_->saveIndex(stream);
152     }
153
154     /**
155      * \brief Loads the index from a stream
156      * \param stream The stream from which the index is loaded
157      */
158     void loadIndex(FILE* stream)
159     {
160         kmeans_index_->loadIndex(stream);
161         kdtree_index_->loadIndex(stream);
162     }
163
164     /**
165      * \returns The index parameters
166      */
167     IndexParams getParameters() const
168     {
169         return index_params_;
170     }
171
172     /**
173      * \brief Method that searches for nearest-neighbours
174      */
175     void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams)
176     {
177         kmeans_index_->findNeighbors(result, vec, searchParams);
178         kdtree_index_->findNeighbors(result, vec, searchParams);
179     }
180
181 private:
182     /** The k-means index */
183     KMeansIndex<Distance>* kmeans_index_;
184
185     /** The kd-tree index */
186     KDTreeIndex<Distance>* kdtree_index_;
187
188     /** The index parameters */
189     const IndexParams index_params_;
190 };
191
192 }
193
194 #endif //OPENCV_FLANN_COMPOSITE_INDEX_H_