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 (at) gmail.com> 43 44 #include "_cv.h" 45 46 #if !defined _MSC_VER || defined __ICL || _MSC_VER >= 1400 47 #include "_cvkdtree.hpp" 48 49 // * write up some docs 50 51 // * removing __valuetype parameter from CvKDTree and using virtuals instead 52 // * of void* data here could simplify things. 53 54 struct CvFeatureTree { 55 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(CvMat* d, int k, int emax, CvMat* results, CvMat* dist) { 84 __treetype* tr = (__treetype*) data; 85 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 typename __treetype::scalar_type* dj = (typename __treetype::scalar_type*) dptr; 98 99 int* resultsj = (int*) resultsptr; 100 double* distj = (double*) distptr; 101 tr->find_nn_bbf(dj, k, emax, nn); 102 103 assert((int)nn.size() <= k); 104 for (unsigned int j = 0; j < nn.size(); ++j) { 105 *resultsj++ = *nn[j].p; 106 *distj++ = nn[j].dist; 107 } 108 std::fill(resultsj, resultsj + k - nn.size(), -1); 109 std::fill(distj, distj + k - nn.size(), 0); 110 111 dptr += d->step; 112 resultsptr += results->step; 113 distptr += dist->step; 114 } 115 } 116 117 template <class __treetype> 118 int find_ortho_range(CvMat* bounds_min, CvMat* bounds_max, 119 CvMat* results) { 120 int rn = results->rows * results->cols; 121 std::vector<int> inbounds; 122 dispatch_cvtype(mat, ((__treetype*)data)-> 123 find_ortho_range((typename __treetype::scalar_type*)bounds_min->data.ptr, 124 (typename __treetype::scalar_type*)bounds_max->data.ptr, 125 inbounds)); 126 std::copy(inbounds.begin(), 127 inbounds.begin() + std::min((int)inbounds.size(), rn), 128 (int*) results->data.ptr); 129 return inbounds.size(); 130 } 131 132 CvFeatureTree(const CvFeatureTree& x); 133 CvFeatureTree& operator= (const CvFeatureTree& rhs); 134 public: 135 CvFeatureTree(CvMat* _mat) : mat(_mat) { 136 // * a flag parameter should tell us whether 137 // * (a) user ensures *mat outlives *this and is unchanged, 138 // * (b) we take reference and user ensures mat is unchanged, 139 // * (c) we copy data, (d) we own and release data. 140 141 std::vector<int> tmp(mat->rows); 142 for (unsigned int j = 0; j < tmp.size(); ++j) 143 tmp[j] = j; 144 145 dispatch_cvtype(mat, data = new tree_type 146 (&tmp[0], &tmp[0] + tmp.size(), mat->cols, 147 tree_type::deref_type(mat))); 148 } 149 ~CvFeatureTree() { 150 dispatch_cvtype(mat, delete (tree_type*) data); 151 } 152 153 int dims() { 154 int d = 0; 155 dispatch_cvtype(mat, d = ((tree_type*) data)->dims()); 156 return d; 157 } 158 int type() { 159 return mat->type; 160 } 161 162 void find_nn(CvMat* d, int k, int emax, CvMat* results, CvMat* dist) { 163 assert(CV_MAT_TYPE(d->type) == CV_MAT_TYPE(mat->type)); 164 assert(CV_MAT_TYPE(dist->type) == CV_64FC1); 165 assert(CV_MAT_TYPE(results->type) == CV_32SC1); 166 167 dispatch_cvtype(mat, find_nn<tree_type> 168 (d, k, emax, results, dist)); 169 } 170 int find_ortho_range(CvMat* bounds_min, CvMat* bounds_max, 171 CvMat* results) { 172 assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(mat->type)); 173 assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(bounds_max->type)); 174 assert(bounds_min->rows * bounds_min->cols == dims()); 175 assert(bounds_max->rows * bounds_max->cols == dims()); 176 177 int count = 0; 178 dispatch_cvtype(mat, count = find_ortho_range<tree_type> 179 (bounds_min, bounds_max,results)); 180 return count; 181 } 182 }; 183 184 185 186 CvFeatureTree* cvCreateFeatureTree(CvMat* desc) { 187 __BEGIN__; 188 CV_FUNCNAME("cvCreateFeatureTree"); 189 190 if (CV_MAT_TYPE(desc->type) != CV_32FC1 && 191 CV_MAT_TYPE(desc->type) != CV_64FC1) 192 CV_ERROR(CV_StsUnsupportedFormat, "descriptors must be either CV_32FC1 or CV_64FC1"); 193 194 return new CvFeatureTree(desc); 195 __END__; 196 197 return 0; 198 } 199 200 void cvReleaseFeatureTree(CvFeatureTree* tr) { 201 delete tr; 202 } 203 204 // desc is m x d set of candidate points. 205 // results is m x k set of row indices of matching points. 206 // dist is m x k distance to matching points. 207 void cvFindFeatures(CvFeatureTree* tr, CvMat* desc, 208 CvMat* results, CvMat* dist, int k, int emax) { 209 bool free_desc = false; 210 int dims = tr->dims(); 211 int type = tr->type(); 212 213 __BEGIN__; 214 CV_FUNCNAME("cvFindFeatures"); 215 216 if (desc->cols != dims) 217 CV_ERROR(CV_StsUnmatchedSizes, "desc columns be equal feature dimensions"); 218 if (results->rows != desc->rows && results->cols != k) 219 CV_ERROR(CV_StsUnmatchedSizes, "results and desc must be same height"); 220 if (dist->rows != desc->rows && dist->cols != k) 221 CV_ERROR(CV_StsUnmatchedSizes, "dist and desc must be same height"); 222 if (CV_MAT_TYPE(results->type) != CV_32SC1) 223 CV_ERROR(CV_StsUnsupportedFormat, "results must be CV_32SC1"); 224 if (CV_MAT_TYPE(dist->type) != CV_64FC1) 225 CV_ERROR(CV_StsUnsupportedFormat, "dist must be CV_64FC1"); 226 227 if (CV_MAT_TYPE(type) != CV_MAT_TYPE(desc->type)) { 228 CvMat* old_desc = desc; 229 desc = cvCreateMat(desc->rows, desc->cols, type); 230 cvConvert(old_desc, desc); 231 free_desc = true; 232 } 233 234 tr->find_nn(desc, k, emax, results, dist); 235 236 __END__; 237 238 if (free_desc) 239 cvReleaseMat(&desc); 240 } 241 242 int cvFindFeaturesBoxed(CvFeatureTree* tr, 243 CvMat* bounds_min, CvMat* bounds_max, 244 CvMat* results) { 245 int nr = -1; 246 bool free_bounds = false; 247 int dims = tr->dims(); 248 int type = tr->type(); 249 250 __BEGIN__; 251 CV_FUNCNAME("cvFindFeaturesBoxed"); 252 253 if (bounds_min->cols * bounds_min->rows != dims || 254 bounds_max->cols * bounds_max->rows != dims) 255 CV_ERROR(CV_StsUnmatchedSizes, "bounds_{min,max} must 1 x dims or dims x 1"); 256 if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(bounds_max->type)) 257 CV_ERROR(CV_StsUnmatchedFormats, "bounds_{min,max} must have same type"); 258 if (CV_MAT_TYPE(results->type) != CV_32SC1) 259 CV_ERROR(CV_StsUnsupportedFormat, "results must be CV_32SC1"); 260 261 if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(type)) { 262 free_bounds = true; 263 264 CvMat* old_bounds_min = bounds_min; 265 bounds_min = cvCreateMat(bounds_min->rows, bounds_min->cols, type); 266 cvConvert(old_bounds_min, bounds_min); 267 268 CvMat* old_bounds_max = bounds_max; 269 bounds_max = cvCreateMat(bounds_max->rows, bounds_max->cols, type); 270 cvConvert(old_bounds_max, bounds_max); 271 } 272 273 nr = tr->find_ortho_range(bounds_min, bounds_max, results); 274 275 __END__; 276 if (free_bounds) { 277 cvReleaseMat(&bounds_min); 278 cvReleaseMat(&bounds_max); 279 } 280 281 return nr; 282 } 283 #endif 284
