include/opencv2/flann/ground_truth.h
Go to the documentation of this file.
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_