NearestNeighbor.cpp
Go to the documentation of this file.
1 // ****************************************************************************
2 // This file is part of the Integrating Vision Toolkit (IVT).
3 //
4 // The IVT is maintained by the Karlsruhe Institute of Technology (KIT)
5 // (www.kit.edu) in cooperation with the company Keyetech (www.keyetech.de).
6 //
7 // Copyright (C) 2014 Karlsruhe Institute of Technology (KIT).
8 // All rights reserved.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions 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 //
16 // 2. Redistributions in binary form must reproduce the above copyright
17 // notice, this list of conditions and the following disclaimer in the
18 // documentation and/or other materials provided with the distribution.
19 //
20 // 3. Neither the name of the KIT nor the names of its contributors may be
21 // used to endorse or promote products derived from this software
22 // without specific prior written permission.
23 //
24 // THIS SOFTWARE IS PROVIDED BY THE KIT AND CONTRIBUTORS “AS IS” AND ANY
25 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 // DISCLAIMED. IN NO EVENT SHALL THE KIT OR CONTRIBUTORS BE LIABLE FOR ANY
28 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 // ****************************************************************************
35 // ****************************************************************************
36 // Filename: NearestNeighbor.cpp
37 // Author: Pedram Azad
38 // Date: 06.10.2009
39 // ****************************************************************************
40 
41 
42 // ****************************************************************************
43 // Includes
44 // ****************************************************************************
45 
46 #include <new> // for explicitly using correct new/delete operators on VC DSPs
47 
48 #include "NearestNeighbor.h"
51 
52 #include <string.h>
53 #include <float.h>
54 #include <math.h>
55 #include <stdio.h>
56 
57 
58 
59 // ****************************************************************************
60 // Constructor / Destructor
61 // ****************************************************************************
62 
64 {
65  m_pData = 0;
66  m_pKdTree = 0;
67  m_nDimension = 0;
68  m_nDataSets = 0;
69  m_nKdTreeMaxLeaves = -1;
70  m_method = method;
71  m_bTrained = false;
72 }
73 
75 {
76  if (m_pData)
77  delete [] m_pData;
78 
79  if (m_pKdTree)
80  delete m_pKdTree;
81 
82  OPTIMIZED_FUNCTION_HEADER_0(NearestNeighbor_CleanupGPU)
84 }
85 
86 
87 // ****************************************************************************
88 // Methods
89 // ****************************************************************************
90 
91 bool CNearestNeighbor::Train(const float *pData, int nDimension, int nDataSets)
92 {
93  if (nDataSets < 1)
94  {
95  m_bTrained = false;
96  return false;
97  }
98 
99  m_nDimension = nDimension;
100  m_nDataSets = nDataSets;
101  m_bTrained = false;
102 
103  if (m_method == eBruteForce)
104  {
105  if (m_pData)
106  delete [] m_pData;
107 
108  m_pData = new float[nDimension * nDataSets];
109 
110  memcpy(m_pData, pData, nDimension * nDataSets * sizeof(float));
111  }
112  else if (m_method == eKdTree)
113  {
114  const int nOverallDimension = nDimension + 2;
115  int i;
116 
117  float **ppValues = new float*[nDataSets];
118 
119  // build values for search tree generation
120  for (i = 0; i < nDataSets; i++)
121  {
122  ppValues[i] = new float[nOverallDimension];
123 
124  // copy data
125  memcpy(ppValues[i], pData + i * nDimension, nDimension * sizeof(float));
126 
127  // set user data
128  memcpy(&ppValues[i][nDimension], &i, sizeof(int));
129  }
130 
131  if (m_pKdTree)
132  delete m_pKdTree;
133 
134  m_pKdTree = new CKdTree();
135  m_pKdTree->Build(ppValues, 0, nDataSets - 1, 3, nDimension, 2);
136 
137  for (i = 0; i < nDataSets; i++)
138  delete [] ppValues[i];
139 
140  delete [] ppValues;
141  }
142  else if (m_method == eBruteForceGPU)
143  {
144  OPTIMIZED_FUNCTION_HEADER_3(NearestNeighbor_TrainGPU, pData, nDimension, nDataSets)
145  return false;
147  }
148 
149  m_bTrained = true;
150 
151  return true;
152 }
153 
154 int CNearestNeighbor::Classify(const float *pQuery, int nDimension, float &fResultError)
155 {
156  if (!m_bTrained)
157  {
158  printf("error: classifier not trained in CNearestNeighbor::Classify\n");
159  return -1;
160  }
161 
162  if (m_nDimension != nDimension)
163  {
164  printf("error: query dimension and trained dimension do not match in CNearestNeighbor::Classify\n");
165  return -1;
166  }
167 
168  if (m_method == eBruteForce)
169  {
170  const float *pData = m_pData;
171 
172  int best_i = -1;
173  float min = FLT_MAX;
174 
175  for (int i = 0; i < m_nDataSets; i++)
176  {
177  float error = 0.0f;
178 
179  for (int j = 0; j < m_nDimension; j++)
180  {
181  register float v = pQuery[j] - pData[j];
182  error += v * v;
183  }
184 
185  if (error < min)
186  {
187  min = error;
188  best_i = i;
189  }
190 
191  pData += m_nDimension;
192  }
193 
194  fResultError = min;
195 
196  return best_i;
197  }
198  else if (m_method == eKdTree)
199  {
200  float *pData, error;
201  m_pKdTree->NearestNeighborBBF(pQuery, error, pData, m_nKdTreeMaxLeaves);
202 
203  int nResultIndex;
204  memcpy(&nResultIndex, pData + m_nDimension, sizeof(int));
205 
206  fResultError = error;
207 
208  return nResultIndex;
209  }
210  else if (m_method == eBruteForceGPU)
211  {
212  int nResult;
213  OPTIMIZED_FUNCTION_HEADER_4(NearestNeighbor_ClassifyGPU, pQuery, nDimension, nResult, fResultError)
214  return nResult;
216  }
217 
218  return -1; // will never happen
219 }
220 
221 bool CNearestNeighbor::Classify(const float *pQueries, int nDimension, int nQueries, int *pResults, float *pResultErrors)
222 {
223  if (!m_bTrained)
224  {
225  printf("error: classifier not trained in CNearestNeighbor::Classify\n");
226  return false;
227  }
228 
229  if (m_nDimension != nDimension)
230  {
231  printf("error: query dimension and trained dimension do not match in CNearestNeighbor::Classify\n");
232  return false;
233  }
234 
235  if (m_method == eBruteForce)
236  {
237  const float *pQuery = pQueries;
238 
239  for (int k = 0; k < nQueries; k++)
240  {
241  const float *pData = m_pData;
242 
243  int best_i = -1;
244  float min = FLT_MAX;
245 
246  for (int i = 0; i < m_nDataSets; i++)
247  {
248  float error = 0.0f;
249 
250  for (int j = 0; j < m_nDimension; j++)
251  {
252  register float v = pQuery[j] - pData[j];
253  error += v * v;
254  }
255 
256  if (error < min)
257  {
258  min = error;
259  best_i = i;
260  }
261 
262  pData += m_nDimension;
263  }
264 
265  pResults[k] = best_i;
266  pResultErrors[k] = min;
267 
268  pQuery += m_nDimension;
269  }
270 
271  return true;
272  }
273  else if (m_method == eKdTree)
274  {
275  const float *pQuery = pQueries;
276 
277  for (int k = 0; k < nQueries; k++)
278  {
279  float *pData, error;
280  m_pKdTree->NearestNeighborBBF(pQuery, error, pData, m_nKdTreeMaxLeaves);
281 
282  memcpy(pResults + k, pData + m_nDimension, sizeof(int)); // index
283  pResultErrors[k] = error;
284 
285  pQuery += m_nDimension;
286  }
287 
288  return true;
289  }
290  else if (m_method == eBruteForceGPU)
291  {
292  OPTIMIZED_FUNCTION_HEADER_5(NearestNeighbor_ClassifyBundleGPU, pQueries, nDimension, nQueries, pResults, pResultErrors)
293  return false;
295  return true;
296  }
297 
298  return false; // will never happen
299 }
#define OPTIMIZED_FUNCTION_HEADER_3(name, p1, p2, p3)
#define OPTIMIZED_FUNCTION_HEADER_4(name, p1, p2, p3, p4)
CNearestNeighbor(ComputationMethod method)
int Classify(const float *pQuery, int nDimension, float &fResultError)
#define OPTIMIZED_FUNCTION_HEADER_0(name)
void NearestNeighborBBF(const float *pfQuery, float &fError, float *&pfNN, int nMaximumLeavesToVisit=-1)
Definition: KdTree.cpp:276
#define OPTIMIZED_FUNCTION_FOOTER
void Build(float **ppfValues, int nLow, int nHigh, int nBucketSize, int nDimensions, int nUserDataSize)
Definition: KdTree.cpp:122
bool Train(const float *pData, int nDimension, int nDataSets)
const GLdouble * v
Definition: glext.h:3212
ComputationMethod m_method
#define OPTIMIZED_FUNCTION_HEADER_5(name, p1, p2, p3, p4, p5)


asr_ivt
Author(s): Allgeyer Tobias, Hutmacher Robin, Kleinert Daniel, Meißner Pascal, Scholz Jonas, Stöckle Patrick
autogenerated on Mon Dec 2 2019 03:47:28