vcs.maemo.org Git - opencv/blob - src/cv/cvkdtree.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   5 //  By downloading, copying, installing or using the software you agree to this license.
   6 //  If you do not agree to this license, do not download, install,
   7 //  copy or use the software.
   8 //
   9 //
  10 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2008, Xavier Delacour, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  22 //   * Redistribution's in binary form must reproduce the above copyright notice,
  23 //     this list of conditions and the following disclaimer in the documentation
  24 //     and/or other materials provided with the distribution.
  25 //
  26 //   * The name of Intel Corporation may not be used to endorse or promote products
  27 //     derived from this software without specific prior written permission.
  28 //
  29 // This software is provided by the copyright holders and contributors "as is" and
  30 // any express or implied warranties, including, but not limited to, the implied
  31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  32 // In no event shall the Intel Corporation or contributors be liable for any direct,
  33 // indirect, incidental, special, exemplary, or consequential damages
  34 // (including, but not limited to, procurement of substitute goods or services;
  35 // loss of use, data, or profits; or business interruption) however caused
  36 // and on any theory of liability, whether in contract, strict liability,
  37 // or tort (including negligence or otherwise) arising in any way out of
  38 // the use of this software, even if advised of the possibility of such damage.
  39 //
  40 //M*/
  41
  42 // 2008-05-13, Xavier Delacour <xavier.delacour@gmail.com>
  43
  44 #include "_cv.h"
  45
  46 #if !defined _MSC_VER || defined __ICL || _MSC_VER >= 1300
  47
  48 #include "_cvkdtree.hpp"
  49 #include "_cvfeaturetree.h"
  50
  51 #if _MSC_VER >= 1400
  52 #pragma warning(disable:4996) // suppress "function call with parameters may be unsafe" in std::copy
  53 #endif
  54
  55 class CvKDTreeWrap : public CvFeatureTree {
  56   template <class __scalartype, int __cvtype>
  57   struct deref {
  58     typedef __scalartype scalar_type;
  59     typedef double accum_type;
  60
  61     CvMat* mat;
  62     deref(CvMat* _mat) : mat(_mat) {
  63       assert(CV_ELEM_SIZE1(__cvtype) == sizeof(__scalartype));
  64     }
  65     scalar_type operator() (int i, int j) const {
  66       return *((scalar_type*)(mat->data.ptr + i * mat->step) + j);
  67     }
  68   };
  69
  70 #define dispatch_cvtype(mat, c) \
  71     switch (CV_MAT_DEPTH((mat)->type)) { \
  72     case CV_32F: \
  73       { typedef CvKDTree<int, deref<float, CV_32F> > tree_type; c; break; } \
  74     case CV_64F: \
  75       { typedef CvKDTree<int, deref<double, CV_64F> > tree_type; c; break; } \
  76     default: assert(0); \
  77     }
  78
  79   CvMat* mat;
  80   void* data;
  81
  82   template <class __treetype>
  83   void find_nn(const CvMat* d, int k, int emax, CvMat* results, CvMat* dist) {
  84     __treetype* tr = (__treetype*) data;
  85     const uchar* dptr = d->data.ptr;
  86     uchar* resultsptr = results->data.ptr;
  87     uchar* distptr = dist->data.ptr;
  88     typename __treetype::bbf_nn_pqueue nn;
  89
  90     assert(d->cols == tr->dims());
  91     assert(results->rows == d->rows);
  92     assert(results->rows == dist->rows);
  93     assert(results->cols == k);
  94     assert(dist->cols == k);
  95
  96     for (int j = 0; j < d->rows; ++j) {
  97       const typename __treetype::scalar_type* dj =
  98         (const typename __treetype::scalar_type*) dptr;
  99
 100       int* resultsj = (int*) resultsptr;
 101       double* distj = (double*) distptr;
 102       tr->find_nn_bbf(dj, k, emax, nn);
 103
 104       assert((int)nn.size() <= k);
 105       for (unsigned int j = 0; j < nn.size(); ++j) {
 106         *resultsj++ = *nn[j].p;
 107         *distj++ = nn[j].dist;
 108       }
 109       std::fill(resultsj, resultsj + k - nn.size(), -1);
 110       std::fill(distj, distj + k - nn.size(), 0);
 111
 112       dptr += d->step;
 113       resultsptr += results->step;
 114       distptr += dist->step;
 115     }
 116   }
 117
 118   template <class __treetype>
 119   int find_ortho_range(CvMat* bounds_min, CvMat* bounds_max,
 120                        CvMat* results) {
 121     int rn = results->rows * results->cols;
 122     std::vector<int> inbounds;
 123     dispatch_cvtype(mat, ((__treetype*)data)->
 124                     find_ortho_range((typename __treetype::scalar_type*)bounds_min->data.ptr,
 125                                      (typename __treetype::scalar_type*)bounds_max->data.ptr,
 126                                      inbounds));
 127     std::copy(inbounds.begin(),
 128               inbounds.begin() + std::min((int)inbounds.size(), rn),
 129               (int*) results->data.ptr);
 130     return (int)inbounds.size();
 131   }
 132
 133   CvKDTreeWrap(const CvKDTreeWrap& x);
 134   CvKDTreeWrap& operator= (const CvKDTreeWrap& rhs);
 135 public:
 136   CvKDTreeWrap(CvMat* _mat) : mat(_mat) {
 137     // * a flag parameter should tell us whether
 138     // * (a) user ensures *mat outlives *this and is unchanged,
 139     // * (b) we take reference and user ensures mat is unchanged,
 140     // * (c) we copy data, (d) we own and release data.
 141
 142     std::vector<int> tmp(mat->rows);
 143     for (unsigned int j = 0; j < tmp.size(); ++j)
 144       tmp[j] = j;
 145
 146     dispatch_cvtype(mat, data = new tree_type
 147                     (&tmp[0], &tmp[0] + tmp.size(), mat->cols,
 148                      tree_type::deref_type(mat)));
 149   }
 150   ~CvKDTreeWrap() {
 151     dispatch_cvtype(mat, delete (tree_type*) data);
 152   }
 153
 154   int dims() {
 155     int d = 0;
 156     dispatch_cvtype(mat, d = ((tree_type*) data)->dims());
 157     return d;
 158   }
 159   int type() {
 160     return mat->type;
 161   }
 162
 163   void FindFeatures(const CvMat* desc, int k, int emax, CvMat* results, CvMat* dist) {
 164     CvMat* tmp_desc = 0;
 165
 166     __BEGIN__;
 167     CV_FUNCNAME("cvFindFeatures");
 168
 169     if (desc->cols != dims())
 170       CV_ERROR(CV_StsUnmatchedSizes, "desc columns be equal feature dimensions");
 171     if (results->rows != desc->rows && results->cols != k)
 172       CV_ERROR(CV_StsUnmatchedSizes, "results and desc must be same height");
 173     if (dist->rows != desc->rows && dist->cols != k)
 174       CV_ERROR(CV_StsUnmatchedSizes, "dist and desc must be same height");
 175     if (CV_MAT_TYPE(results->type) != CV_32SC1)
 176       CV_ERROR(CV_StsUnsupportedFormat, "results must be CV_32SC1");
 177     if (CV_MAT_TYPE(dist->type) != CV_64FC1)
 178       CV_ERROR(CV_StsUnsupportedFormat, "dist must be CV_64FC1");
 179
 180     if (CV_MAT_TYPE(type()) != CV_MAT_TYPE(desc->type)) {
 181       tmp_desc = cvCreateMat(desc->rows, desc->cols, type());
 182       cvConvert(desc, tmp_desc);
 183       desc = tmp_desc;
 184     }
 185
 186
 187     assert(CV_MAT_TYPE(desc->type) == CV_MAT_TYPE(mat->type));
 188     assert(CV_MAT_TYPE(dist->type) == CV_64FC1);
 189     assert(CV_MAT_TYPE(results->type) == CV_32SC1);
 190
 191     dispatch_cvtype(mat, find_nn<tree_type>
 192                     (desc, k, emax, results, dist));
 193
 194     __END__;
 195
 196     if (tmp_desc)
 197       cvReleaseMat(&tmp_desc);
 198   }
 199   int FindOrthoRange(CvMat* bounds_min, CvMat* bounds_max,
 200                      CvMat* results) {
 201     bool free_bounds = false;
 202     int count = -1;
 203
 204     __BEGIN__;
 205     CV_FUNCNAME("cvFindFeaturesBoxed");
 206
 207     if (bounds_min->cols * bounds_min->rows != dims() ||
 208         bounds_max->cols * bounds_max->rows != dims())
 209       CV_ERROR(CV_StsUnmatchedSizes, "bounds_{min,max} must 1 x dims or dims x 1");
 210     if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(bounds_max->type))
 211       CV_ERROR(CV_StsUnmatchedFormats, "bounds_{min,max} must have same type");
 212     if (CV_MAT_TYPE(results->type) != CV_32SC1)
 213       CV_ERROR(CV_StsUnsupportedFormat, "results must be CV_32SC1");
 214
 215     if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(type())) {
 216       free_bounds = true;
 217
 218       CvMat* old_bounds_min = bounds_min;
 219       bounds_min = cvCreateMat(bounds_min->rows, bounds_min->cols, type());
 220       cvConvert(old_bounds_min, bounds_min);
 221
 222       CvMat* old_bounds_max = bounds_max;
 223       bounds_max = cvCreateMat(bounds_max->rows, bounds_max->cols, type());
 224       cvConvert(old_bounds_max, bounds_max);
 225     }
 226
 227     assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(mat->type));
 228     assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(bounds_max->type));
 229     assert(bounds_min->rows * bounds_min->cols == dims());
 230     assert(bounds_max->rows * bounds_max->cols == dims());
 231
 232     dispatch_cvtype(mat, count = find_ortho_range<tree_type>
 233                     (bounds_min, bounds_max,results));
 234
 235     __END__;
 236     if (free_bounds) {
 237       cvReleaseMat(&bounds_min);
 238       cvReleaseMat(&bounds_max);
 239     }
 240
 241     return count;
 242   }
 243 };
 244
 245 CvFeatureTree* cvCreateKDTree(CvMat* desc) {
 246   __BEGIN__;
 247   CV_FUNCNAME("cvCreateKDTree");
 248
 249   if (CV_MAT_TYPE(desc->type) != CV_32FC1 &&
 250       CV_MAT_TYPE(desc->type) != CV_64FC1)
 251     CV_ERROR(CV_StsUnsupportedFormat, "descriptors must be either CV_32FC1 or CV_64FC1");
 252
 253   return new CvKDTreeWrap(desc);
 254   __END__;
 255
 256   return 0;
 257 }
 258
 259 #endif