Main MRPT website > C++ reference
MRPT logo
descriptor_kdtrees.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 
29 #ifndef mrpt_vision_descriptor_kdtrees_H
30 #define mrpt_vision_descriptor_kdtrees_H
31 
32 #include <mrpt/vision/types.h>
33 #include <mrpt/vision/CFeature.h>
34 
35 namespace mrpt
36 {
37  namespace vision
38  {
39  namespace detail {
40  // Private auxiliary classes
41  template <typename distance_t,typename element_t = uint8_t> struct TSIFTDesc2KDTree_Adaptor;
42  template <typename distance_t,typename element_t = float> struct TSURFDesc2KDTree_Adaptor;
43  }
44 
45  /** \defgroup mrptvision_descr_kdtrees KD-Tree construction of visual descriptors
46  * \ingroup mrpt_vision_grp
47  */
48 
49  /** \addtogroup mrptvision_descr_kdtrees
50  @{ */
51 
52  /** A kd-tree builder for sets of features with SIFT descriptors.
53  * Example of usage:
54  * \code
55  * TSIFTDescriptorsKDTreeIndex<double> feats_kdtree(feats);
56  * feats_kdtree.get_kdtree().knnSearch( ... );
57  * \endcode
58  * \sa CFeatureList, mrpt::vision::find_descriptor_pairings
59  */
60  template <
61  typename distance_t,
62  class metric_t = nanoflann::L2_Simple_Adaptor<uint8_t/*SIFT desc elements*/,detail::TSIFTDesc2KDTree_Adaptor<distance_t>, distance_t>
63  >
64  struct TSIFTDescriptorsKDTreeIndex
65  {
66  public:
67  typedef typename nanoflann::KDTreeSingleIndexAdaptor<metric_t,detail::TSIFTDesc2KDTree_Adaptor<distance_t> > kdtree_t;
68 
69  /** Constructor from a list of SIFT features.
70  * Automatically build the KD-tree index. The list of features must NOT be empty or an exception will be raised.
71  */
72  TSIFTDescriptorsKDTreeIndex(const CFeatureList &feats) :
73  m_adaptor(feats),
74  m_kdtree(NULL),
75  m_feats(feats)
76  {
77  ASSERT_(!feats.empty() && feats[0]->descriptors.hasDescriptorSIFT())
78  this->regenerate_kdtreee();
79  }
80 
81  /** Re-creates the kd-tree, which must be done whenever the data source (the CFeatureList) changes. */
82  void regenerate_kdtreee()
83  {
84  if (m_kdtree) delete m_kdtree;
85 
86  nanoflann::KDTreeSingleIndexAdaptorParams params;
87  m_kdtree = new kdtree_t( m_feats[0]->descriptors.SIFT.size() /* DIM */ , m_adaptor, params );
88  m_kdtree->buildIndex();
89  }
90 
91  /** Access to the kd-tree object */
92  kdtree_t & get_kdtree() { return *m_kdtree; }
93  const kdtree_t & get_kdtree() const { return *m_kdtree; }
94 
95  ~TSIFTDescriptorsKDTreeIndex()
96  {
97  delete m_kdtree;
98  m_kdtree=NULL;
99  }
100 
101  private:
102  detail::TSIFTDesc2KDTree_Adaptor<distance_t> m_adaptor;
103  kdtree_t *m_kdtree;
104 
105  const CFeatureList & m_feats;
106  }; // end of TSIFTDescriptorsKDTreeIndex
107 
108 
109  /** A kd-tree builder for sets of features with SURF descriptors.
110  * Example of usage:
111  * \code
112  * TSURFDescriptorsKDTreeIndex<double> feats_kdtree(feats);
113  * feats_kdtree.get_kdtree().knnSearch( ... );
114  * \endcode
115  * \sa CFeatureList, mrpt::vision::find_descriptor_pairings
116  */
117  template <
118  typename distance_t,
119  class metric_t = nanoflann::L2_Simple_Adaptor<float/*SURF desc elements*/,detail::TSURFDesc2KDTree_Adaptor<distance_t>, distance_t>
120  >
121  struct TSURFDescriptorsKDTreeIndex
122  {
123  public:
124  typedef typename nanoflann::KDTreeSingleIndexAdaptor<metric_t,detail::TSURFDesc2KDTree_Adaptor<distance_t> > kdtree_t;
125 
126  /** Constructor from a list of SIFT features.
127  * Automatically build the KD-tree index. The list of features must NOT be empty or an exception will be raised.
128  */
129  TSURFDescriptorsKDTreeIndex(const CFeatureList &feats) :
130  m_adaptor(feats),
131  m_kdtree(NULL),
132  m_feats(feats)
133  {
134  ASSERT_(!feats.empty() && feats[0]->descriptors.hasDescriptorSIFT())
135  this->regenerate_kdtreee();
136  }
137 
138  /** Re-creates the kd-tree, which must be done whenever the data source (the CFeatureList) changes. */
139  void regenerate_kdtreee()
140  {
141  if (m_kdtree) delete m_kdtree;
142 
143  nanoflann::KDTreeSingleIndexAdaptorParams params;
144  m_kdtree = new kdtree_t( m_feats[0]->descriptors.SIFT.size() /* DIM */ , m_adaptor, params );
145  m_kdtree->buildIndex();
146  }
147 
148  /** Access to the kd-tree object */
149  kdtree_t & get_kdtree() { return *m_kdtree; }
150  const kdtree_t & get_kdtree() const { return *m_kdtree; }
151 
152  ~TSURFDescriptorsKDTreeIndex()
153  {
154  delete m_kdtree;
155  m_kdtree=NULL;
156  }
157 
158  private:
159  detail::TSURFDesc2KDTree_Adaptor<distance_t> m_adaptor;
160  kdtree_t *m_kdtree;
161 
162  const CFeatureList & m_feats;
163  }; // end of TSURFDescriptorsKDTreeIndex
164 
165  /** @} */
166 
167  namespace detail
168  {
169  template <typename distance_t,typename element_t>
170  struct TSIFTDesc2KDTree_Adaptor
171  {
172  const CFeatureList & m_feats;
173  TSIFTDesc2KDTree_Adaptor(const CFeatureList &feats) : m_feats(feats) { }
174  // Must return the number of data points
175  inline size_t kdtree_get_point_count() const { return m_feats.size(); }
176  // Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
177  inline distance_t kdtree_distance(const element_t *p1, const size_t idx_p2,size_t size) const
178  {
179  const size_t dim=m_feats[idx_p2]->descriptors.SIFT.size();
180  const element_t *p2 = &m_feats[idx_p2]->descriptors.SIFT[0];
181  distance_t d=0;
182  for (size_t i=0;i<dim;i++)
183  {
184  d+=(*p1-*p2)*(*p1-*p2);
185  p1++;
186  p2++;
187  }
188  return d;
189  }
190  // Must return the dim'th component of the idx'th point in the class:
191  inline element_t kdtree_get_pt(const size_t idx, int dim) const { return m_feats[idx]->descriptors.SIFT[dim]; }
192  template <class BBOX> bool kdtree_get_bbox(BBOX &bb) const { return false; }
193  };
194 
195  template <typename distance_t,typename element_t>
196  struct TSURFDesc2KDTree_Adaptor
197  {
198  const CFeatureList & m_feats;
199  TSURFDesc2KDTree_Adaptor(const CFeatureList &feats) : m_feats(feats) { }
200  // Must return the number of data points
201  inline size_t kdtree_get_point_count() const { return m_feats.size(); }
202  // Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
203  inline distance_t kdtree_distance(const element_t *p1, const size_t idx_p2,size_t size) const
204  {
205  const size_t dim=m_feats[idx_p2]->descriptors.SURF.size();
206  const element_t *p2 = &m_feats[idx_p2]->descriptors.SURF[0];
207  distance_t d=0;
208  for (size_t i=0;i<dim;i++)
209  {
210  d+=(*p1-*p2)*(*p1-*p2);
211  p1++;
212  p2++;
213  }
214  return d;
215  }
216  // Must return the dim'th component of the idx'th point in the class:
217  inline element_t kdtree_get_pt(const size_t idx, int dim) const { return m_feats[idx]->descriptors.SURF[dim]; }
218  template <class BBOX> bool kdtree_get_bbox(BBOX &bb) const { return false; }
219  };
220  } // end detail
221  }
222 }
223 #endif
224 


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013