1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2008, Xavier Delacour, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
42 // 2008-05-13, Xavier Delacour <xavier.delacour@gmail.com>
44 #include "precomp.hpp"
46 #if !defined _MSC_VER || defined __ICL || _MSC_VER >= 1300
48 #include "_kdtree.hpp"
49 #include "_featuretree.h"
51 class CvKDTreeWrap : public CvFeatureTree {
52 template <class __scalartype, int __cvtype>
54 typedef __scalartype scalar_type;
55 typedef double accum_type;
58 deref(CvMat* _mat) : mat(_mat) {
59 assert(CV_ELEM_SIZE1(__cvtype) == sizeof(__scalartype));
61 scalar_type operator() (int i, int j) const {
62 return *((scalar_type*)(mat->data.ptr + i * mat->step) + j);
66 #define dispatch_cvtype(mat, c) \
67 switch (CV_MAT_DEPTH((mat)->type)) { \
69 { typedef CvKDTree<int, deref<float, CV_32F> > tree_type; c; break; } \
71 { typedef CvKDTree<int, deref<double, CV_64F> > tree_type; c; break; } \
78 template <class __treetype>
79 void find_nn(const CvMat* d, int k, int emax, CvMat* results, CvMat* dist) {
80 __treetype* tr = (__treetype*) data;
81 const uchar* dptr = d->data.ptr;
82 uchar* resultsptr = results->data.ptr;
83 uchar* distptr = dist->data.ptr;
84 typename __treetype::bbf_nn_pqueue nn;
86 assert(d->cols == tr->dims());
87 assert(results->rows == d->rows);
88 assert(results->rows == dist->rows);
89 assert(results->cols == k);
90 assert(dist->cols == k);
92 for (int j = 0; j < d->rows; ++j)
94 const typename __treetype::scalar_type* dj = (const typename __treetype::scalar_type*) dptr;
96 int* resultsj = (int*) resultsptr;
97 double* distj = (double*) distptr;
98 tr->find_nn_bbf(dj, k, emax, nn);
100 assert((int)nn.size() <= k);
101 for (unsigned int i = 0; i < nn.size(); ++i)
103 *resultsj++ = *nn[i].p;
104 *distj++ = nn[i].dist;
106 std::fill(resultsj, resultsj + k - nn.size(), -1);
107 std::fill(distj, distj + k - nn.size(), 0);
110 resultsptr += results->step;
111 distptr += dist->step;
115 template <class __treetype>
116 int find_ortho_range(CvMat* bounds_min, CvMat* bounds_max,
118 int rn = results->rows * results->cols;
119 std::vector<int> inbounds;
120 assert(CV_MAT_DEPTH(mat->type) == CV_32F || CV_MAT_DEPTH(mat->type) == CV_64F);
121 ((__treetype*)data)->find_ortho_range((typename __treetype::scalar_type*)bounds_min->data.ptr,
122 (typename __treetype::scalar_type*)bounds_max->data.ptr,
124 std::copy(inbounds.begin(),
125 inbounds.begin() + std::min((int)inbounds.size(), rn),
126 (int*) results->data.ptr);
127 return (int)inbounds.size();
130 CvKDTreeWrap(const CvKDTreeWrap& x);
131 CvKDTreeWrap& operator= (const CvKDTreeWrap& rhs);
133 CvKDTreeWrap(CvMat* _mat) : mat(_mat) {
134 // * a flag parameter should tell us whether
135 // * (a) user ensures *mat outlives *this and is unchanged,
136 // * (b) we take reference and user ensures mat is unchanged,
137 // * (c) we copy data, (d) we own and release data.
139 std::vector<int> tmp(mat->rows);
140 for (unsigned int j = 0; j < tmp.size(); ++j)
143 dispatch_cvtype(mat, data = new tree_type
144 (&tmp[0], &tmp[0] + tmp.size(), mat->cols,
145 tree_type::deref_type(mat)));
148 dispatch_cvtype(mat, delete (tree_type*) data);
153 dispatch_cvtype(mat, d = ((tree_type*) data)->dims());
160 void FindFeatures(const CvMat* desc, int k, int emax, CvMat* results, CvMat* dist) {
161 cv::Ptr<CvMat> tmp_desc;
163 if (desc->cols != dims())
164 CV_Error(CV_StsUnmatchedSizes, "desc columns be equal feature dimensions");
165 if (results->rows != desc->rows && results->cols != k)
166 CV_Error(CV_StsUnmatchedSizes, "results and desc must be same height");
167 if (dist->rows != desc->rows && dist->cols != k)
168 CV_Error(CV_StsUnmatchedSizes, "dist and desc must be same height");
169 if (CV_MAT_TYPE(results->type) != CV_32SC1)
170 CV_Error(CV_StsUnsupportedFormat, "results must be CV_32SC1");
171 if (CV_MAT_TYPE(dist->type) != CV_64FC1)
172 CV_Error(CV_StsUnsupportedFormat, "dist must be CV_64FC1");
174 if (CV_MAT_TYPE(type()) != CV_MAT_TYPE(desc->type)) {
175 tmp_desc.reset(cvCreateMat(desc->rows, desc->cols, type()));
176 cvConvert(desc, tmp_desc);
180 assert(CV_MAT_TYPE(desc->type) == CV_MAT_TYPE(mat->type));
181 assert(CV_MAT_TYPE(dist->type) == CV_64FC1);
182 assert(CV_MAT_TYPE(results->type) == CV_32SC1);
184 dispatch_cvtype(mat, find_nn<tree_type>
185 (desc, k, emax, results, dist));
187 int FindOrthoRange(CvMat* bounds_min, CvMat* bounds_max,
189 bool free_bounds = false;
192 if (bounds_min->cols * bounds_min->rows != dims() ||
193 bounds_max->cols * bounds_max->rows != dims())
194 CV_Error(CV_StsUnmatchedSizes, "bounds_{min,max} must 1 x dims or dims x 1");
195 if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(bounds_max->type))
196 CV_Error(CV_StsUnmatchedFormats, "bounds_{min,max} must have same type");
197 if (CV_MAT_TYPE(results->type) != CV_32SC1)
198 CV_Error(CV_StsUnsupportedFormat, "results must be CV_32SC1");
200 if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(type())) {
203 CvMat* old_bounds_min = bounds_min;
204 bounds_min = cvCreateMat(bounds_min->rows, bounds_min->cols, type());
205 cvConvert(old_bounds_min, bounds_min);
207 CvMat* old_bounds_max = bounds_max;
208 bounds_max = cvCreateMat(bounds_max->rows, bounds_max->cols, type());
209 cvConvert(old_bounds_max, bounds_max);
212 assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(mat->type));
213 assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(bounds_max->type));
214 assert(bounds_min->rows * bounds_min->cols == dims());
215 assert(bounds_max->rows * bounds_max->cols == dims());
217 dispatch_cvtype(mat, count = find_ortho_range<tree_type>
218 (bounds_min, bounds_max,results));
221 cvReleaseMat(&bounds_min);
222 cvReleaseMat(&bounds_max);
229 CvFeatureTree* cvCreateKDTree(CvMat* desc) {
231 if (CV_MAT_TYPE(desc->type) != CV_32FC1 &&
232 CV_MAT_TYPE(desc->type) != CV_64FC1)
233 CV_Error(CV_StsUnsupportedFormat, "descriptors must be either CV_32FC1 or CV_64FC1");
235 return new CvKDTreeWrap(desc);