kdtree_cpu.cpp
Go to the documentation of this file.
00001 /*
00002 
00003 Copyright (c) 2010--2011, Stephane Magnenat, ASL, ETHZ, Switzerland
00004 You can contact the author at <stephane at magnenat dot net>
00005 
00006 All rights reserved.
00007 
00008 Redistribution and use in source and binary forms, with or without
00009 modification, are permitted provided that the following conditions are met:
00010     * Redistributions of source code must retain the above copyright
00011       notice, this list of conditions and the following disclaimer.
00012     * Redistributions in binary form must reproduce the above copyright
00013       notice, this list of conditions and the following disclaimer in the
00014       documentation and/or other materials provided with the distribution.
00015     * Neither the name of the <organization> nor the
00016       names of its contributors may be used to endorse or promote products
00017       derived from this software without specific prior written permission.
00018 
00019 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
00020 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022 DISCLAIMED. IN NO EVENT SHALL ETH-ASL BE LIABLE FOR ANY
00023 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 
00030 */
00031 
00032 #include "nabo_experimental.h"
00033 #include "../nabo/index_heap.h"
00034 #include <iostream>
00035 #include <stdexcept>
00036 #include <limits>
00037 #include <queue>
00038 #include <algorithm>
00039 #include <boost/numeric/conversion/bounds.hpp>
00040 #include <boost/limits.hpp>
00041 
00042 namespace Nabo
00043 {
00044         using namespace std;
00045         
00046         template<typename T, typename CloudType>
00047         size_t argMax(const typename NearestNeighbourSearch<T, CloudType>::Vector& v)
00048         {
00049                 T maxVal(0);
00050                 size_t maxIdx(0);
00051                 for (int i = 0; i < v.size(); ++i)
00052                 {
00053                         if (v[i] > maxVal)
00054                         {
00055                                 maxVal = v[i];
00056                                 maxIdx = i;
00057                         }
00058                 }
00059                 return maxIdx;
00060         }
00061 
00062         template<typename T, typename CloudType>
00063         size_t KDTreeBalancedPtInNodes<T, CloudType>::getTreeSize(size_t elCount) const
00064         {
00065                 // FIXME: 64 bits safe stuff, only work for 2^32 elements right now
00066                 size_t count = 0;
00067                 int i = 31;
00068                 for (; i >= 0; --i)
00069                 {
00070                         if (elCount & (1 << i))
00071                                 break;
00072                 }
00073                 for (int j = 0; j <= i; ++j)
00074                         count |= (1 << j);
00075                 //cerr << "tree size " << count << " (" << elCount << " elements)\n";
00076                 return count;
00077         }
00078         
00079         template<typename T, typename CloudType>
00080         typename KDTreeBalancedPtInNodes<T, CloudType>::IndexVector KDTreeBalancedPtInNodes<T, CloudType>::cloudIndexesFromNodesIndexes(const IndexVector& indexes) const
00081         {
00082                 IndexVector cloudIndexes(indexes.size());
00083                 for (int i = 0; i < indexes.size(); ++i)
00084                         cloudIndexes.coeffRef(i) = nodes[indexes[i]].index;
00085                 return cloudIndexes;
00086         }
00087 
00088         template<typename T, typename CloudType>
00089         void KDTreeBalancedPtInNodes<T, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos)
00090         {
00091                 const size_t count(last - first);
00092                 //cerr << count << endl;
00093                 if (count == 1)
00094                 {
00095                         nodes[pos] = Node(first->pos, -1, first->index);
00096                         return;
00097                 }
00098                 
00099                 // estimate variance
00100                 // get mean
00101                 Vector mean(Vector::Zero(this->dim));
00102                 for (BuildPointsCstIt it(first); it != last; ++it)
00103                         mean += it->pos;
00104                 mean /= last - first;
00105                 // get sum of variance
00106                 Vector var(Vector::Zero(this->dim));
00107                 for (BuildPointsCstIt it(first); it != last; ++it)
00108                         var += (it->pos - mean).cwise() * (it->pos - mean);
00109                 // get dimension of maxmial variance
00110                 const size_t cutDim = argMax<T>(var);
00111                 
00112                 // sort
00113                 sort(first, last, CompareDim(cutDim));
00114                 
00115                 // set node
00116                 const size_t recurseCount(count-1);
00117                 const size_t rightCount(recurseCount/2);
00118                 const size_t leftCount(recurseCount-rightCount);
00119                 assert(last - rightCount == first + leftCount + 1);
00120                 
00121                 nodes[pos] = Node((first+leftCount)->pos, cutDim, (first+leftCount)->index);
00122                 
00123                 //cerr << pos << " cutting on " << cutDim << " at " << (first+leftCount)->pos[cutDim] << endl;
00124                 
00125                 // recurse
00126                 if (count > 2)
00127                 {
00128                         buildNodes(first, first + leftCount, childLeft(pos));
00129                         buildNodes(first + leftCount + 1, last, childRight(pos));
00130                 }
00131                 else
00132                 {
00133                         nodes[childLeft(pos)] = Node(first->pos, -1, first->index);
00134                         nodes[childRight(pos)] = Node(Vector(), -2, 0);
00135                 }
00136         }
00137 
00138         template<typename T, typename CloudType>
00139         void KDTreeBalancedPtInNodes<T, CloudType>::dump(const Vector minValues, const Vector maxValues, const size_t pos) const
00140         {
00141                 const Node& node(nodes[pos]);
00142                 
00143                 if (node.dim >= -1)
00144                 {
00145                         if (this->dim == 2)
00146                                 cout << "<circle cx=\"" << 100*node.pos(0) << "\" cy=\"" << 100*node.pos(1) << "\" r=\"1\" stroke=\"black\" stroke-width=\"0.2\" fill=\"red\"/>" << endl;
00147                         else
00148                                 cout << "pt at\n" << node.pos << endl;
00149                 }
00150                 if (node.dim >= 0)
00151                 {
00152                         //cerr << "in bounds:\n" << minValues << "\nto\n" << maxValues << endl;
00153                         
00154                         // update bounds for left
00155                         Vector leftMaxValues(maxValues);
00156                         leftMaxValues[node.dim] = node.pos[node.dim];
00157                         // update bounds for right
00158                         Vector rightMinValues(minValues);
00159                         rightMinValues[node.dim] = node.pos[node.dim];
00160                         
00161                         // print line
00162                         if (this->dim == 2)
00163                                 cout << "<line x1=\"" << 100*rightMinValues(0) << "\" y1=\"" << 100*rightMinValues(1) << "\" x2=\"" << 100*leftMaxValues(0) << "\" y2=\"" << 100*leftMaxValues(1) << "\" style=\"stroke:rgb(0,0,0);stroke-width:0.2\"/>" << endl;
00164                         else
00165                                 cout << "cut from\n" << rightMinValues << "\nto\n" << leftMaxValues << endl;
00166                         // recurs
00167                         dump(minValues, leftMaxValues, childLeft(pos));
00168                         dump(rightMinValues, maxValues, childRight(pos));
00169                 }
00170         }
00171 
00172         template<typename T, typename CloudType>
00173         KDTreeBalancedPtInNodes<T, CloudType>::KDTreeBalancedPtInNodes(const CloudType& cloud):
00174                 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00175         {
00176                 // build point vector and compute bounds
00177                 BuildPoints buildPoints;
00178                 buildPoints.reserve(cloud.cols());
00179                 for (int i = 0; i < cloud.cols(); ++i)
00180                 {
00181                         const Vector& v(cloud.col(i));
00182                         buildPoints.push_back(BuildPoint(v, i));
00183                         const_cast<Vector&>(this->minBound) = this->minBound.cwise().min(v);
00184                         const_cast<Vector&>(this->maxBound) = this->maxBound.cwise().max(v);
00185                 }
00186                 
00187                 // create nodes
00188                 nodes.resize(getTreeSize(cloud.cols()));
00189                 buildNodes(buildPoints.begin(), buildPoints.end(), 0);
00190                 
00191                 // dump nodes
00192                 //dump(minBound, maxBound, 0);
00193         }
00194         
00195         // points in nodes, priority queue
00196         
00197         template<typename T, typename CloudType>
00198         KDTreeBalancedPtInNodesPQ<T, CloudType>::KDTreeBalancedPtInNodesPQ(const CloudType& cloud):
00199                 KDTreeBalancedPtInNodes<T, CloudType>::KDTreeBalancedPtInNodes(cloud)
00200         {
00201         }
00202 
00203         template<typename T, typename CloudType>
00204         typename KDTreeBalancedPtInNodesPQ<T, CloudType>::IndexVector KDTreeBalancedPtInNodesPQ<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00205         {
00206                 typedef priority_queue<SearchElement> Queue;
00207                 
00208                 const T maxError(1 + epsilon);
00209                 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T>::ALLOW_SELF_MATCH);
00210                 
00211                 Queue queue;
00212                 queue.push(SearchElement(0, 0));
00213                 IndexHeapSTL<Index, T> heap(k);
00214                 statistics.lastQueryVisitCount = 0;
00215                 
00216                 while (!queue.empty())
00217                 {
00218                         SearchElement el(queue.top());
00219                         queue.pop();
00220                         
00221                         // nothing is closer, we found best
00222                         if (el.minDist * maxError > heap.headValue())
00223                                 break;
00224                         
00225                         size_t n(el.index);
00226                         while (1)
00227                         {
00228                                 const Node& node(nodes[n]);
00229                                 assert (node.dim != -2);
00230                                 
00231                                 // TODO: optimise dist while going down
00232                                 const T dist(dist2<T>(node.pos, query));
00233                                 if ((dist < heap.headValue()) &&
00234                                         (allowSelfMatch || (dist > numeric_limits<T>::epsilon())))
00235                                         heap.replaceHead(n, dist);
00236                                 
00237                                 // if we are at leaf, stop
00238                                 if (node.dim < 0)
00239                                         break;
00240                                 
00241                                 const T offset(query.coeff(node.dim) - node.pos.coeff(node.dim));
00242                                 const T offset2(offset * offset);
00243                                 const T bestDist(heap.headValue());
00244                                 if (offset > 0)
00245                                 {
00246                                         // enqueue offside ?
00247                                         if (offset2 < bestDist && nodes[childLeft(n)].dim != -2)
00248                                                 queue.push(SearchElement(childLeft(n), offset2));
00249                                         // continue onside
00250                                         if (nodes[childRight(n)].dim != -2)
00251                                                 n = childRight(n);
00252                                         else
00253                                                 break;
00254                                 }
00255                                 else
00256                                 {
00257                                         // enqueue offside ?
00258                                         if (offset2 < bestDist && nodes[childRight(n)].dim != -2)
00259                                                 queue.push(SearchElement(childRight(n), offset2));
00260                                         // continue onside
00261                                         if (nodes[childLeft(n)].dim != -2)
00262                                                 n = childLeft(n);
00263                                         else
00264                                                 break;
00265                                 }
00266                                 ++statistics.lastQueryVisitCount;
00267                         }
00268                 }
00269                 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00270                 
00271                 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00272                         heap.sort();
00273                 
00274                 return cloudIndexesFromNodesIndexes(heap.getIndexes());
00275         }
00276 
00277         template struct KDTreeBalancedPtInNodesPQ<float>;
00278         template struct KDTreeBalancedPtInNodesPQ<double>;
00279         template struct KDTreeBalancedPtInNodesPQ<float, Eigen::Matrix3Xf>;
00280         template struct KDTreeBalancedPtInNodesPQ<double, Eigen::Matrix3Xd>;
00281         template struct KDTreeBalancedPtInNodesPQ<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00282         template struct KDTreeBalancedPtInNodesPQ<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00283         
00284         // points in nodes, stack
00285         
00286         template<typename T, typename CloudType>
00287         KDTreeBalancedPtInNodesStack<T, CloudType>::KDTreeBalancedPtInNodesStack(const CloudType& cloud):
00288                 KDTreeBalancedPtInNodes<T, CloudType>::KDTreeBalancedPtInNodes(cloud)
00289         {
00290         }
00291         
00292         template<typename T, typename CloudType>
00293         typename KDTreeBalancedPtInNodesStack<T, CloudType>::IndexVector KDTreeBalancedPtInNodesStack<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00294         {
00295                 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T>::ALLOW_SELF_MATCH);
00296                 
00297                 assert(nodes.size() > 0);
00298                 assert(nodes[0].pos.size() == query.size());
00299                 Heap heap(k);
00300                 Vector off(Vector::Zero(nodes[0].pos.size()));
00301                 
00302                 statistics.lastQueryVisitCount = 0;
00303                 
00304                 recurseKnn(query, 0, 0, heap, off, 1 + epsilon, allowSelfMatch);
00305                 
00306                 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00307                         heap.sort();
00308                 
00309                 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00310                 
00311                 return cloudIndexesFromNodesIndexes(heap.getIndexes());
00312         }
00313         
00314         template<typename T, typename CloudType>
00315         void KDTreeBalancedPtInNodesStack<T, CloudType>::recurseKnn(const Vector& query, const size_t n, T rd, Heap& heap, Vector& off, const T maxError, const bool allowSelfMatch)
00316         {
00317                 const Node& node(nodes[n]);
00318                 const int cd(node.dim);
00319                 
00320                 ++statistics.lastQueryVisitCount;
00321                 
00322                 if (cd == -2)
00323                         return;
00324                 
00325                 const T dist(dist2<T, CloudType>(node.pos, query));
00326                 if ((dist < heap.headValue()) &&
00327                         (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00328                 )
00329                         heap.replaceHead(n, dist);
00330                 
00331                 if (cd != -1)
00332                 {
00333                         const T old_off(off.coeff(cd));
00334                         const T new_off(query.coeff(cd) - node.pos.coeff(cd));
00335                         if (new_off > 0)
00336                         {
00337                                 recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00338                                 rd += - old_off*old_off + new_off*new_off;
00339                                 if (rd * maxError < heap.headValue())
00340                                 {
00341                                         off.coeffRef(cd) = new_off;
00342                                         recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00343                                         off.coeffRef(cd) = old_off;
00344                                 }
00345                         }
00346                         else
00347                         {
00348                                 recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00349                                 rd += - old_off*old_off + new_off*new_off;
00350                                 if (rd * maxError < heap.headValue())
00351                                 {
00352                                         off.coeffRef(cd) = new_off;
00353                                         recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00354                                         off.coeffRef(cd) = old_off;
00355                                 }
00356                         }
00357                 }
00358         }
00359         
00360         template struct KDTreeBalancedPtInNodesStack<float>;
00361         template struct KDTreeBalancedPtInNodesStack<double>;
00362         template struct KDTreeBalancedPtInNodesStack<float, Eigen::Matrix3Xf>;
00363         template struct KDTreeBalancedPtInNodesStack<double, Eigen::Matrix3Xd>;
00364         template struct KDTreeBalancedPtInNodesStack<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00365         template struct KDTreeBalancedPtInNodesStack<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00366         
00367         // NEW:
00368         
00369         template<typename T, typename CloudType>
00370         size_t KDTreeBalancedPtInLeavesStack<T, CloudType>::getTreeSize(size_t elCount) const
00371         {
00372                 // FIXME: 64 bits safe stuff, only work for 2^32 elements right now
00373                 assert(elCount > 0);
00374                 elCount --;
00375                 size_t count = 0;
00376                 int i = 31;
00377                 for (; i >= 0; --i)
00378                 {
00379                         if (elCount & (1 << i))
00380                                 break;
00381                 }
00382                 for (int j = 0; j <= i; ++j)
00383                         count |= (1 << j);
00384                 count <<= 1;
00385                 count |= 1;
00386                 return count;
00387         }
00388         
00389         template<typename T, typename CloudType>
00390         void KDTreeBalancedPtInLeavesStack<T, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const size_t pos, const Vector minValues, const Vector maxValues, const bool balanceVariance)
00391         {
00392                 const size_t count(last - first);
00393                 //cerr << count << endl;
00394                 if (count == 1)
00395                 {
00396                         const int dim = -2-(first->index);
00397                         assert(pos < nodes.size());
00398                         nodes[pos] = Node(dim);
00399                         return;
00400                 }
00401                 
00402                 size_t cutDim;
00403                 if (balanceVariance)
00404                 {
00405                         // estimate variance
00406                         // get mean
00407                         Vector mean(Vector::Zero(this->dim));
00408                         for (BuildPointsCstIt it(first); it != last; ++it)
00409                                 mean += it->pos;
00410                         mean /= last - first;
00411                         // get sum of variance
00412                         Vector var(Vector::Zero(this->dim));
00413                         for (BuildPointsCstIt it(first); it != last; ++it)
00414                                 var += (it->pos - mean).cwise() * (it->pos - mean);
00415                         // get dimension of maxmial variance
00416                         cutDim = argMax<T>(var);
00417                 }
00418                 else
00419                 {
00420                         // find the largest dimension of the box
00421                         cutDim = argMax<T>(maxValues - minValues);
00422                 }
00423                 
00424                 // compute number of elements
00425                 const size_t rightCount(count/2);
00426                 const size_t leftCount(count - rightCount);
00427                 assert(last - rightCount == first + leftCount);
00428                 
00429                 // sort
00430                 //sort(first, last, CompareDim(cutDim));
00431                 nth_element(first, first + leftCount, last, CompareDim(cutDim));
00432                 
00433                 // set node
00434                 const T cutVal((first+leftCount)->pos.coeff(cutDim));
00435                 nodes[pos] = Node(cutDim, cutVal);
00436                 
00437                 //cerr << pos << " cutting on " << cutDim << " at " << (first+leftCount)->pos[cutDim] << endl;
00438                 
00439                 // update bounds for left
00440                 Vector leftMaxValues(maxValues);
00441                 leftMaxValues[cutDim] = cutVal;
00442                 // update bounds for right
00443                 Vector rightMinValues(minValues);
00444                 rightMinValues[cutDim] = cutVal;
00445                 
00446                 // recurse
00447                 buildNodes(first, first + leftCount, childLeft(pos), minValues, leftMaxValues, balanceVariance);
00448                 buildNodes(first + leftCount, last, childRight(pos), rightMinValues, maxValues, balanceVariance);
00449         }
00450 
00451         template<typename T, typename CloudType>
00452         KDTreeBalancedPtInLeavesStack<T, CloudType>::KDTreeBalancedPtInLeavesStack(const CloudType& cloud, const bool balanceVariance):
00453                 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00454         {
00455                 // build point vector and compute bounds
00456                 BuildPoints buildPoints;
00457                 buildPoints.reserve(cloud.cols());
00458                 for (int i = 0; i < cloud.cols(); ++i)
00459                 {
00460                         const Vector& v(cloud.col(i));
00461                         buildPoints.push_back(BuildPoint(v, i));
00462                         const_cast<Vector&>(minBound) = minBound.cwise().min(v);
00463                         const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
00464                 }
00465                 
00466                 // create nodes
00467                 nodes.resize(getTreeSize(cloud.cols()));
00468                 buildNodes(buildPoints.begin(), buildPoints.end(), 0, minBound, maxBound, balanceVariance);
00469                 //for (size_t i = 0; i < nodes.size(); ++i)
00470                 //      cout << i << ": " << nodes[i].dim << " " << nodes[i].cutVal << endl;
00471         }
00472         
00473         template<typename T, typename CloudType>
00474         typename KDTreeBalancedPtInLeavesStack<T, CloudType>::IndexVector KDTreeBalancedPtInLeavesStack<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00475         {
00476                 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00477                 
00478                 assert(nodes.size() > 0);
00479                 Heap heap(k);
00480                 Vector off(Vector::Zero(query.size()));
00481                 
00482                 statistics.lastQueryVisitCount = 0;
00483                 
00484                 recurseKnn(query, 0, 0, heap, off, 1 + epsilon, allowSelfMatch);
00485                 
00486                 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00487                         heap.sort();
00488                 
00489                 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00490                 
00491                 return heap.getIndexes();
00492         }
00493         
00494         template<typename T, typename CloudType>
00495         void KDTreeBalancedPtInLeavesStack<T, CloudType>::recurseKnn(const Vector& query, const size_t n, T rd, Heap& heap, Vector& off, const T maxError, const bool allowSelfMatch)
00496         {
00497                 const Node& node(nodes[n]);
00498                 const int cd(node.dim);
00499                 
00500                 ++statistics.lastQueryVisitCount;
00501                 
00502                 if (cd < 0)
00503                 {
00504                         if (cd == -1)
00505                                 return;
00506                         const int index(-(cd + 2));
00507                         const T dist(dist2<T>(query, cloud.col(index)));
00508                         if ((dist < heap.headValue()) &&
00509                                 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00510                         )
00511                                 heap.replaceHead(index, dist);
00512                 }
00513                 else
00514                 {
00515                         const T old_off(off.coeff(cd));
00516                         const T new_off(query.coeff(cd) - node.cutVal);
00517                         if (new_off > 0)
00518                         {
00519                                 recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00520                                 rd += - old_off*old_off + new_off*new_off;
00521                                 if (rd * maxError < heap.headValue())
00522                                 {
00523                                         off.coeffRef(cd) = new_off;
00524                                         recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00525                                         off.coeffRef(cd) = old_off;
00526                                 }
00527                         }
00528                         else
00529                         {
00530                                 recurseKnn(query, childLeft(n), rd, heap, off, maxError, allowSelfMatch);
00531                                 rd += - old_off*old_off + new_off*new_off;
00532                                 if (rd * maxError < heap.headValue())
00533                                 {
00534                                         off.coeffRef(cd) = new_off;
00535                                         recurseKnn(query, childRight(n), rd, heap, off, maxError, allowSelfMatch);
00536                                         off.coeffRef(cd) = old_off;
00537                                 }
00538                         }
00539                 }
00540         }
00541         
00542         template struct KDTreeBalancedPtInLeavesStack<float>;
00543         template struct KDTreeBalancedPtInLeavesStack<double>;
00544         template struct KDTreeBalancedPtInLeavesStack<float, Eigen::Matrix3Xf>;
00545         template struct KDTreeBalancedPtInLeavesStack<double, Eigen::Matrix3Xd>;
00546         template struct KDTreeBalancedPtInLeavesStack<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00547         template struct KDTreeBalancedPtInLeavesStack<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00548         
00549         
00550         
00551         template<typename T, typename Heap, typename CloudType>
00552         unsigned KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
00553         {
00554                 const size_t count(last - first);
00555                 const unsigned pos(nodes.size());
00556                 
00557                 //cerr << count << endl;
00558                 if (count == 1)
00559                 {
00560                         nodes.push_back(Node(first->index));
00561                         return pos;
00562                 }
00563                 
00564                 // find the largest dimension of the box
00565                 const unsigned cutDim = argMax<T>(maxValues - minValues);
00566                 T cutVal((maxValues(cutDim) + minValues(cutDim))/2);
00567                 
00568                 // TODO: do only sort once
00569                 // sort
00570                 sort(first, last, CompareDim(cutDim));
00571                 
00572                 // TODO: optimise using binary search
00573                 size_t rightStart(0);
00574                 while (rightStart < count && (first+rightStart)->pos.coeff(cutDim) < cutVal)
00575                         ++rightStart;
00576                 
00577                 // prevent trivial splits
00578                 if (rightStart == 0)
00579                 {
00580                         cutVal = first->pos.coeff(cutDim);
00581                         rightStart = 1;
00582                 }
00583                 else if (rightStart == count)
00584                 {
00585                         rightStart = count - 1;
00586                         cutVal = (first + rightStart)->pos.coeff(cutDim);
00587                 }
00588                 
00589                 // update bounds for left
00590                 Vector leftMaxValues(maxValues);
00591                 leftMaxValues[cutDim] = cutVal;
00592                 // update bounds for right
00593                 Vector rightMinValues(minValues);
00594                 rightMinValues[cutDim] = cutVal;
00595                 
00596                 // count for recursion
00597                 const size_t rightCount(count - rightStart);
00598                 const size_t leftCount(count - rightCount);
00599                 
00600                 // add this
00601                 nodes.push_back(Node(cutDim, cutVal, 0));
00602                 
00603                 // recurse
00604                 const unsigned __attribute__ ((unused)) leftChild = buildNodes(first, first + leftCount, minValues, leftMaxValues);
00605                 assert(leftChild == pos + 1);
00606                 const unsigned rightChild = buildNodes(first + leftCount, last, rightMinValues, maxValues);
00607                 
00608                 // write right child index and return
00609                 nodes[pos].rightChild = rightChild;
00610                 return pos;
00611         }
00612 
00613         template<typename T, typename Heap, typename CloudType>
00614         KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::KDTreeUnbalancedPtInLeavesImplicitBoundsStack(const CloudType& cloud):
00615                 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00616         {
00617                 // build point vector and compute bounds
00618                 BuildPoints buildPoints;
00619                 buildPoints.reserve(cloud.cols());
00620                 for (int i = 0; i < cloud.cols(); ++i)
00621                 {
00622                         const Vector& v(cloud.col(i));
00623                         buildPoints.push_back(BuildPoint(v, i));
00624                         const_cast<Vector&>(minBound) = minBound.cwise().min(v);
00625                         const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
00626                 }
00627                 
00628                 // create nodes
00629                 //nodes.resize(getTreeSize(cloud.cols()));
00630                 buildNodes(buildPoints.begin(), buildPoints.end(), minBound, maxBound);
00631                 //for (size_t i = 0; i < nodes.size(); ++i)
00632                 //      cout << i << ": " << nodes[i].dim << " " << nodes[i].cutVal <<  " " << nodes[i].rightChild << endl;
00633         }
00634         
00635         template<typename T, typename Heap, typename CloudType>
00636         typename KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::IndexVector KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00637         {
00638                 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00639                 
00640                 assert(nodes.size() > 0);
00641                 Heap heap(k);
00642                 Vector off(Vector::Zero(query.size()));
00643                 
00644                 statistics.lastQueryVisitCount = 0;
00645                 
00646                 recurseKnn(query, 0, 0, heap, off, 1+epsilon, allowSelfMatch);
00647                 
00648                 if (optionFlags & NearestNeighbourSearch<T, CloudType>::SORT_RESULTS)
00649                         heap.sort();
00650                 
00651                 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00652                 
00653                 return heap.getIndexes();
00654         }
00655         
00656         template<typename T, typename Heap, typename CloudType>
00657         typename KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::IndexMatrix KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::knnM(const Matrix& query, const Index k, const T epsilon, const unsigned optionFlags)
00658         {
00659                 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00660                 assert(nodes.size() > 0);
00661                 
00662                 assert(nodes.size() > 0);
00663                 Heap heap(k);
00664                 Vector off(query.rows());
00665                 
00666                 IndexMatrix result(k, query.cols());
00667                 const int colCount(query.cols());
00668                 
00669                 for (int i = 0; i < colCount; ++i)
00670                 {
00671                         const Vector& q(query.col(i));
00672                         
00673                         off.setZero();
00674                         heap.reset();
00675                         
00676                         statistics.lastQueryVisitCount = 0;
00677                         
00678                         recurseKnn(q, 0, 0, heap, off, 1+epsilon, allowSelfMatch);
00679                         
00680                         if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00681                                 heap.sort();
00682                         
00683                         result.col(i) = heap.getIndexes();
00684                         
00685                         statistics.totalVisitCount += statistics.lastQueryVisitCount;
00686                 }
00687                 
00688                 return result;
00689         }
00690         
00691         template<typename T, typename Heap, typename CloudType>
00692         void KDTreeUnbalancedPtInLeavesImplicitBoundsStack<T, Heap, CloudType>::recurseKnn(const Vector& query, const unsigned n, T rd, Heap& heap, Vector& off, const T maxError, const bool allowSelfMatch)
00693         {
00694                 const Node& node(nodes[n]);
00695                 //++statistics.lastQueryVisitCount;
00696                 
00697                 if (node.rightChild == Node::INVALID_CHILD)
00698                 {
00699                         const unsigned index(node.ptIndex);
00700                         //const T dist(dist2<T>(query, cloud.col(index)));
00701                         //const T dist((query - cloud.col(index)).squaredNorm());
00702                         T dist(0);
00703                         const T* qPtr(&query.coeff(0));
00704                         const T* dPtr(&cloud.coeff(0, index));
00705                         const int dim(query.size());
00706                         for (int i = 0; i < dim; ++i)
00707                         {
00708                                 const T diff(*qPtr - *dPtr);
00709                                 dist += diff*diff;
00710                                 qPtr++; dPtr++;
00711                         }
00712                         if ((dist < heap.headValue()) &&
00713                                 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00714                         )
00715                                 heap.replaceHead(index, dist);
00716                 }
00717                 else
00718                 {
00719                         const unsigned cd(node.dim);
00720                         const T old_off(off.coeff(cd));
00721                         const T new_off(query.coeff(cd) - node.cutVal);
00722                         if (new_off > 0)
00723                         {
00724                                 recurseKnn(query, node.rightChild, rd, heap, off, maxError, allowSelfMatch);
00725                                 rd += - old_off*old_off + new_off*new_off;
00726                                 if (rd * maxError < heap.headValue())
00727                                 {
00728                                         off.coeffRef(cd) = new_off;
00729                                         recurseKnn(query, n + 1, rd, heap, off, maxError, allowSelfMatch);
00730                                         off.coeffRef(cd) = old_off;
00731                                 }
00732                         }
00733                         else
00734                         {
00735                                 recurseKnn(query, n+1, rd, heap, off, maxError, allowSelfMatch);
00736                                 rd += - old_off*old_off + new_off*new_off;
00737                                 if (rd * maxError < heap.headValue())
00738                                 {
00739                                         off.coeffRef(cd) = new_off;
00740                                         recurseKnn(query, node.rightChild, rd, heap, off, maxError, allowSelfMatch);
00741                                         off.coeffRef(cd) = old_off;
00742                                 }
00743                         }
00744                 }
00745         }
00746         
00747         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapSTL<int,float>>;
00748         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapBruteForceVector<int,float>>;
00749         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapSTL<int,double>>;
00750         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapBruteForceVector<int,double>>;
00751 
00752         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapSTL<int,float>,Eigen::Matrix3Xf>;
00753         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapBruteForceVector<int,float>,Eigen::Matrix3Xf>;
00754         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapSTL<int,double>,Eigen::Matrix3Xd>;
00755         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapBruteForceVector<int,double>,Eigen::Matrix3Xd>;
00756 
00757         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapSTL<int,float>,Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00758         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<float,IndexHeapBruteForceVector<int,float>,Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00759         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapSTL<int,double>,Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00760         template struct KDTreeUnbalancedPtInLeavesImplicitBoundsStack<double,IndexHeapBruteForceVector<int,double>,Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00761         
00762         template<typename T, typename CloudType>
00763         unsigned KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::buildNodes(const BuildPointsIt first, const BuildPointsIt last, const Vector minValues, const Vector maxValues)
00764         {
00765                 const size_t count(last - first);
00766                 const unsigned pos(nodes.size());
00767                 
00768                 //cerr << count << endl;
00769                 if (count == 1)
00770                 {
00771                         const int dim = -1-(first->index);
00772                         nodes.push_back(Node(dim));
00773                         return pos;
00774                 }
00775                 
00776                 // find the largest dimension of the box
00777                 const int cutDim = argMax<T>(maxValues - minValues);
00778                 T cutVal((maxValues(cutDim) + minValues(cutDim))/2);
00779                 
00780                 // TODO: do only sort once
00781                 // sort
00782                 sort(first, last, CompareDim(cutDim));
00783                 
00784                 // TODO: optimise using binary search
00785                 size_t rightStart(0);
00786                 while (rightStart < count && (first+rightStart)->pos.coeff(cutDim) < cutVal)
00787                         ++rightStart;
00788                 
00789                 // prevent trivial splits
00790                 if (rightStart == 0)
00791                 {
00792                         cutVal = first->pos.coeff(cutDim);
00793                         rightStart = 1;
00794                 }
00795                 else if (rightStart == count)
00796                 {
00797                         rightStart = count - 1;
00798                         cutVal = (first + rightStart)->pos.coeff(cutDim);
00799                 }
00800                 
00801                 // update bounds for left
00802                 Vector leftMaxValues(maxValues);
00803                 leftMaxValues[cutDim] = cutVal;
00804                 // update bounds for right
00805                 Vector rightMinValues(minValues);
00806                 rightMinValues[cutDim] = cutVal;
00807                 
00808                 // count for recursion
00809                 const size_t rightCount(count - rightStart);
00810                 const size_t leftCount(count - rightCount);
00811                 
00812                 // add this
00813                 nodes.push_back(Node(cutDim, cutVal, minValues.coeff(cutDim), maxValues.coeff(cutDim)));
00814                 
00815                 // recurse
00816                 const unsigned __attribute__ ((unused)) leftChild = buildNodes(first, first + leftCount, minValues, leftMaxValues);
00817                 assert(leftChild == pos + 1);
00818                 const unsigned rightChild = buildNodes(first + leftCount, last, rightMinValues, maxValues);
00819                 
00820                 // write right child index and return
00821                 nodes[pos].rightChild = rightChild;
00822                 return pos;
00823         }
00824 
00825         template<typename T, typename CloudType>
00826         KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::KDTreeUnbalancedPtInLeavesExplicitBoundsStack(const CloudType& cloud):
00827                 NearestNeighbourSearch<T, CloudType>::NearestNeighbourSearch(cloud)
00828         {
00829                 // build point vector and compute bounds
00830                 BuildPoints buildPoints;
00831                 buildPoints.reserve(cloud.cols());
00832                 for (int i = 0; i < cloud.cols(); ++i)
00833                 {
00834                         const Vector& v(cloud.col(i));
00835                         buildPoints.push_back(BuildPoint(v, i));
00836                         const_cast<Vector&>(minBound) = minBound.cwise().min(v);
00837                         const_cast<Vector&>(maxBound) = maxBound.cwise().max(v);
00838                 }
00839                 
00840                 // create nodes
00841                 //nodes.resize(getTreeSize(cloud.cols()));
00842                 buildNodes(buildPoints.begin(), buildPoints.end(), minBound, maxBound);
00843                 //for (size_t i = 0; i < nodes.size(); ++i)
00844                 //      cout << i << ": " << nodes[i].dim << " " << nodes[i].cutVal <<  " " << nodes[i].rightChild << endl;
00845         }
00846         
00847         template<typename T, typename CloudType>
00848         typename KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::IndexVector KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::knn(const Vector& query, const Index k, const T epsilon, const unsigned optionFlags)
00849         {
00850                 const bool allowSelfMatch(optionFlags & NearestNeighbourSearch<T, CloudType>::ALLOW_SELF_MATCH);
00851                 
00852                 assert(nodes.size() > 0);
00853                 Heap heap(k);
00854                 
00855                 statistics.lastQueryVisitCount = 0;
00856                 
00857                 recurseKnn(query, 0, 0, heap, 1+epsilon, allowSelfMatch);
00858                 
00859                 if (optionFlags & NearestNeighbourSearch<T>::SORT_RESULTS)
00860                         heap.sort();
00861                 
00862                 statistics.totalVisitCount += statistics.lastQueryVisitCount;
00863                 
00864                 return heap.getIndexes();
00865         }
00866         
00867         template<typename T, typename CloudType>
00868         void KDTreeUnbalancedPtInLeavesExplicitBoundsStack<T, CloudType>::recurseKnn(const Vector& query, const size_t n, T rd, Heap& heap, const T maxError, const bool allowSelfMatch)
00869         {
00870                 const Node& node(nodes[n]);
00871                 const int cd(node.dim);
00872                 
00873                 ++statistics.lastQueryVisitCount;
00874                 
00875                 if (cd < 0)
00876                 {
00877                         const int index(-(cd + 1));
00878                         const T dist(dist2<T>(query, cloud.col(index)));
00879                         if ((dist < heap.headValue()) &&
00880                                 (allowSelfMatch || (dist > numeric_limits<T>::epsilon()))
00881                         )
00882                                 heap.replaceHead(index, dist);
00883                 }
00884                 else
00885                 {
00886                         const T q_val(query.coeff(cd));
00887                         const T cut_diff(q_val - node.cutVal);
00888                         if (cut_diff < 0)
00889                         {
00890                                 recurseKnn(query, n+1, rd, heap, maxError, allowSelfMatch);
00891                                 
00892                                 T box_diff = node.lowBound - q_val;
00893                                 if (box_diff < 0)
00894                                         box_diff = 0;
00895                                 
00896                                 rd += cut_diff*cut_diff - box_diff*box_diff;
00897                                 
00898                                 if (rd * maxError < heap.headValue())
00899                                         recurseKnn(query, node.rightChild, rd, heap, maxError, allowSelfMatch);
00900                         }
00901                         else
00902                         {
00903                                 recurseKnn(query, node.rightChild, rd, heap, maxError, allowSelfMatch);
00904                                 
00905                                 T box_diff = q_val - node.highBound;
00906                                 if (box_diff < 0)
00907                                         box_diff = 0;
00908                                 
00909                                 rd += cut_diff*cut_diff - box_diff*box_diff;
00910                                 
00911                                 if (rd * maxError < heap.headValue())
00912                                         recurseKnn(query, n + 1, rd, heap, maxError, allowSelfMatch);
00913                         }
00914                 }
00915         }
00916         
00917         template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<float>;
00918         template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<double>;
00919         template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<float, Eigen::Matrix3Xf>;
00920         template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<double, Eigen::Matrix3Xd>;
00921         template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<float, Eigen::Map<const Eigen::Matrix3Xf, Eigen::Aligned> >;
00922         template struct KDTreeUnbalancedPtInLeavesExplicitBoundsStack<double, Eigen::Map<const Eigen::Matrix3Xd, Eigen::Aligned> >;
00923 }


libnabo
Author(s): Stéphane Magnenat
autogenerated on Thu Sep 10 2015 10:54:55