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 >= 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;
derefCvFeatureTree::deref62 deref(CvMat* _mat) : mat(_mat) {
63 assert(CV_ELEM_SIZE1(__cvtype) == sizeof(__scalartype));
64 }
operator ()CvFeatureTree::deref65 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>
find_nnCvFeatureTree83 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>
find_ortho_rangeCvFeatureTree118 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:
CvFeatureTreeCvFeatureTree135 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 }
~CvFeatureTreeCvFeatureTree149 ~CvFeatureTree() {
150 dispatch_cvtype(mat, delete (tree_type*) data);
151 }
152
dimsCvFeatureTree153 int dims() {
154 int d = 0;
155 dispatch_cvtype(mat, d = ((tree_type*) data)->dims());
156 return d;
157 }
typeCvFeatureTree158 int type() {
159 return mat->type;
160 }
161
find_nnCvFeatureTree162 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 }
find_ortho_rangeCvFeatureTree170 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
cvCreateFeatureTree(CvMat * desc)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
cvReleaseFeatureTree(CvFeatureTree * tr)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.
cvFindFeatures(CvFeatureTree * tr,CvMat * desc,CvMat * results,CvMat * dist,int k,int emax)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
cvFindFeaturesBoxed(CvFeatureTree * tr,CvMat * bounds_min,CvMat * bounds_max,CvMat * results)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