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_GROUND_TRUTH_H_ 00032 #define _OPENCV_GROUND_TRUTH_H_ 00033 00034 #include "opencv2/flann/dist.h" 00035 #include "opencv2/flann/matrix.h" 00036 00037 namespace cvflann 00038 { 00039 00040 template <typename T> 00041 void find_nearest(const Matrix<T>& dataset, T* query, int* matches, int nn, int skip = 0) 00042 { 00043 int n = nn + skip; 00044 00045 T* query_end = query + dataset.cols; 00046 00047 long* match = new long[n]; 00048 T* dists = new T[n]; 00049 00050 dists[0] = (float)flann_dist(query, query_end, dataset[0]); 00051 match[0] = 0; 00052 int dcnt = 1; 00053 00054 for (size_t i=1;i<dataset.rows;++i) { 00055 T tmp = (T)flann_dist(query, query_end, dataset[i]); 00056 00057 if (dcnt<n) { 00058 match[dcnt] = (long)i; 00059 dists[dcnt++] = tmp; 00060 } 00061 else if (tmp < dists[dcnt-1]) { 00062 dists[dcnt-1] = tmp; 00063 match[dcnt-1] = (long)i; 00064 } 00065 00066 int j = dcnt-1; 00067 // bubble up 00068 while (j>=1 && dists[j]<dists[j-1]) { 00069 std::swap(dists[j],dists[j-1]); 00070 std::swap(match[j],match[j-1]); 00071 j--; 00072 } 00073 } 00074 00075 for (int i=0;i<nn;++i) { 00076 matches[i] = match[i+skip]; 00077 } 00078 00079 delete[] match; 00080 delete[] dists; 00081 } 00082 00083 00084 template <typename T> 00085 void compute_ground_truth(const Matrix<T>& dataset, const Matrix<T>& testset, Matrix<int>& matches, int skip=0) 00086 { 00087 for (size_t i=0;i<testset.rows;++i) { 00088 find_nearest(dataset, testset[i], matches[i], (int)matches.cols, skip); 00089 } 00090 } 00091 00092 00093 } // namespace cvflann 00094 00095 #endif //_OPENCV_GROUND_TRUTH_H_