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) 2000, Intel Corporation, 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.
43 #include "_cvmodelest.h"
50 CvModelEstimator2::CvModelEstimator2(int _modelPoints, CvSize _modelSize, int _maxBasicSolutions)
52 modelPoints = _modelPoints;
53 modelSize = _modelSize;
54 maxBasicSolutions = _maxBasicSolutions;
55 checkPartialSubsets = true;
59 CvModelEstimator2::~CvModelEstimator2()
63 void CvModelEstimator2::setSeed( int64 seed )
69 int CvModelEstimator2::findInliers( const CvMat* m1, const CvMat* m2,
70 const CvMat* model, CvMat* _err,
71 CvMat* _mask, double threshold )
73 int i, count = _err->rows*_err->cols, goodCount = 0;
74 const float* err = _err->data.fl;
75 uchar* mask = _mask->data.ptr;
77 computeReprojError( m1, m2, model, _err );
78 threshold *= threshold;
79 for( i = 0; i < count; i++ )
80 goodCount += mask[i] = err[i] <= threshold;
86 cvRANSACUpdateNumIters( double p, double ep,
87 int model_points, int max_iters )
91 CV_FUNCNAME( "cvRANSACUpdateNumIters" );
97 if( model_points <= 0 )
98 CV_ERROR( CV_StsOutOfRange, "the number of model points should be positive" );
105 // avoid inf's & nan's
106 num = MAX(1. - p, DBL_MIN);
107 denom = 1. - pow(1. - ep,model_points);
108 if( denom < DBL_MIN )
114 result = denom >= 0 || -num >= max_iters*(-denom) ?
115 max_iters : cvRound(num/denom);
122 bool CvModelEstimator2::runRANSAC( const CvMat* m1, const CvMat* m2, CvMat* model,
123 CvMat* mask, double reprojThreshold,
124 double confidence, int maxIters )
127 CvMat* mask0 = mask, *tmask = 0, *t;
128 CvMat* models = 0, *err = 0;
129 CvMat *ms1 = 0, *ms2 = 0;
131 CV_FUNCNAME( "CvModelEstimator2::estimateRansac" );
135 int iter, niters = maxIters;
136 int count = m1->rows*m1->cols, maxGoodCount = 0;
137 CV_ASSERT( CV_ARE_SIZES_EQ(m1, m2) && CV_ARE_SIZES_EQ(m1, mask) );
139 if( count < modelPoints )
142 models = cvCreateMat( modelSize.height*maxBasicSolutions, modelSize.width, CV_64FC1 );
143 err = cvCreateMat( 1, count, CV_32FC1 );
144 tmask = cvCreateMat( 1, count, CV_8UC1 );
146 if( count > modelPoints )
148 ms1 = cvCreateMat( 1, modelPoints, m1->type );
149 ms2 = cvCreateMat( 1, modelPoints, m2->type );
158 for( iter = 0; iter < niters; iter++ )
160 int i, goodCount, nmodels;
161 if( count > modelPoints )
163 bool found = getSubset( m1, m2, ms1, ms2, 300 );
172 nmodels = runKernel( ms1, ms2, models );
175 for( i = 0; i < nmodels; i++ )
178 cvGetRows( models, &model_i, i*modelSize.height, (i+1)*modelSize.height );
179 goodCount = findInliers( m1, m2, &model_i, err, tmask, reprojThreshold );
181 if( goodCount > MAX(maxGoodCount, modelPoints-1) )
183 CV_SWAP( tmask, mask, t );
184 cvCopy( &model_i, model );
185 maxGoodCount = goodCount;
186 niters = cvRANSACUpdateNumIters( confidence,
187 (double)(count - goodCount)/count, modelPoints, niters );
192 if( maxGoodCount > 0 )
196 CV_SWAP( tmask, mask, t );
197 cvCopy( tmask, mask );
205 cvReleaseMat( &ms1 );
207 cvReleaseMat( &ms2 );
208 cvReleaseMat( &models );
209 cvReleaseMat( &err );
210 cvReleaseMat( &tmask );
215 static CV_IMPLEMENT_QSORT( icvSortDistances, int, CV_LT )
217 bool CvModelEstimator2::runLMeDS( const CvMat* m1, const CvMat* m2, CvMat* model,
218 CvMat* mask, double confidence, int maxIters )
220 const double outlierRatio = 0.45;
223 CvMat *ms1 = 0, *ms2 = 0;
226 CV_FUNCNAME( "CvModelEstimator2::estimateLMeDS" );
230 int iter, niters = maxIters;
231 int count = m1->rows*m1->cols;
232 double minMedian = DBL_MAX, sigma;
234 CV_ASSERT( CV_ARE_SIZES_EQ(m1, m2) && CV_ARE_SIZES_EQ(m1, mask) );
236 if( count < modelPoints )
239 models = cvCreateMat( modelSize.height*maxBasicSolutions, modelSize.width, CV_64FC1 );
240 err = cvCreateMat( 1, count, CV_32FC1 );
242 if( count > modelPoints )
244 ms1 = cvCreateMat( 1, modelPoints, m1->type );
245 ms2 = cvCreateMat( 1, modelPoints, m2->type );
254 niters = cvRound(log(1-confidence)/log(1-pow(1-outlierRatio,(double)modelPoints)));
255 niters = MIN( MAX(niters, 3), maxIters );
257 for( iter = 0; iter < niters; iter++ )
260 if( count > modelPoints )
262 bool found = getSubset( m1, m2, ms1, ms2, 300 );
271 nmodels = runKernel( ms1, ms2, models );
274 for( i = 0; i < nmodels; i++ )
277 cvGetRows( models, &model_i, i*modelSize.height, (i+1)*modelSize.height );
278 computeReprojError( m1, m2, &model_i, err );
279 icvSortDistances( err->data.i, count, 0 );
281 double median = count % 2 != 0 ?
282 err->data.fl[count/2] : (err->data.fl[count/2-1] + err->data.fl[count/2])*0.5;
284 if( median < minMedian )
287 cvCopy( &model_i, model );
292 if( minMedian < DBL_MAX )
294 sigma = 2.5*1.4826*(1 + 5./(count - modelPoints))*sqrt(minMedian);
295 sigma = MAX( sigma, FLT_EPSILON*100 );
297 count = findInliers( m1, m2, model, err, mask, sigma );
298 result = count >= modelPoints;
304 cvReleaseMat( &ms1 );
306 cvReleaseMat( &ms2 );
307 cvReleaseMat( &models );
308 cvReleaseMat( &err );
313 bool CvModelEstimator2::getSubset( const CvMat* m1, const CvMat* m2,
314 CvMat* ms1, CvMat* ms2, int maxAttempts )
316 int* idx = (int*)cvStackAlloc( modelPoints*sizeof(idx[0]) );
317 int i = 0, j, k, idx_i, iters = 0;
318 int type = CV_MAT_TYPE(m1->type), elemSize = CV_ELEM_SIZE(type);
319 const int *m1ptr = m1->data.i, *m2ptr = m2->data.i;
320 int *ms1ptr = ms1->data.i, *ms2ptr = ms2->data.i;
321 int count = m1->cols*m1->rows;
323 assert( CV_IS_MAT_CONT(m1->type & m2->type) && (elemSize % sizeof(int) == 0) );
324 elemSize /= sizeof(int);
326 for(; iters < maxAttempts; iters++)
328 for( i = 0; i < modelPoints && iters < maxAttempts; )
330 idx[i] = idx_i = cvRandInt(&rng) % count;
331 for( j = 0; j < i; j++ )
332 if( idx_i == idx[j] )
336 for( k = 0; k < elemSize; k++ )
338 ms1ptr[i*elemSize + k] = m1ptr[idx_i*elemSize + k];
339 ms2ptr[i*elemSize + k] = m2ptr[idx_i*elemSize + k];
341 if( checkPartialSubsets && (!checkSubset( ms1, i+1 ) || !checkSubset( ms2, i+1 )))
348 if( !checkPartialSubsets && i == modelPoints &&
349 (!checkSubset( ms1, i ) || !checkSubset( ms2, i )))
354 return i == modelPoints && iters < maxAttempts;
358 bool CvModelEstimator2::checkSubset( const CvMat* m, int count )
361 CvPoint2D64f* ptr = (CvPoint2D64f*)m->data.ptr;
363 assert( CV_MAT_TYPE(m->type) == CV_64FC2 );
365 if( checkPartialSubsets )
368 i0 = 0, i1 = count - 1;
370 for( i = i0; i <= i1; i++ )
372 // check that the i-th selected point does not belong
373 // to a line connecting some previously selected points
374 for( j = 0; j < i; j++ )
376 double dx1 = ptr[j].x - ptr[i].x;
377 double dy1 = ptr[j].y - ptr[i].y;
378 for( k = 0; k < j; k++ )
380 double dx2 = ptr[k].x - ptr[i].x;
381 double dy2 = ptr[k].y - ptr[i].y;
382 if( fabs(dx2*dy1 - dy2*dx1) < FLT_EPSILON*(fabs(dx1) + fabs(dy1) + fabs(dx2) + fabs(dy2)))
399 class Affine3DEstimator : public CvModelEstimator2
402 Affine3DEstimator() : CvModelEstimator2(4, cvSize(4, 3), 1) {}
403 virtual int runKernel( const CvMat* m1, const CvMat* m2, CvMat* model );
405 virtual void computeReprojError( const CvMat* m1, const CvMat* m2, const CvMat* model, CvMat* error );
406 virtual bool checkSubset( const CvMat* ms1, int count );
411 int cv::Affine3DEstimator::runKernel( const CvMat* m1, const CvMat* m2, CvMat* model )
413 const Point3d* from = reinterpret_cast<const Point3d*>(m1->data.ptr);
414 const Point3d* to = reinterpret_cast<const Point3d*>(m2->data.ptr);
416 Mat A(12, 12, CV_64F);
417 Mat B(12, 1, CV_64F);
420 for(int i = 0; i < modelPoints; ++i)
422 *B.ptr<Point3d>(3*i) = to[i];
424 double *aptr = A.ptr<double>(3*i);
425 for(int k = 0; k < 3; ++k)
428 *reinterpret_cast<Point3d*>(aptr) = from[i];
436 cvReshape(model, &cvX, 1, 12);
437 cvSolve(&cvA, &cvB, &cvX, CV_SVD );
442 void cv::Affine3DEstimator::computeReprojError( const CvMat* m1, const CvMat* m2, const CvMat* model, CvMat* error )
444 int count = m1->rows * m1->cols;
445 const Point3d* from = reinterpret_cast<const Point3d*>(m1->data.ptr);
446 const Point3d* to = reinterpret_cast<const Point3d*>(m2->data.ptr);
447 const double* F = model->data.db;
448 float* err = error->data.fl;
450 for(int i = 0; i < count; i++ )
452 const Point3d& f = from[i];
453 const Point3d& t = to[i];
455 double a = F[0]*f.x + F[1]*f.y + F[ 2]*f.z + F[ 3] - t.x;
456 double b = F[4]*f.x + F[5]*f.y + F[ 6]*f.z + F[ 7] - t.y;
457 double c = F[8]*f.x + F[9]*f.y + F[10]*f.z + F[11] - t.z;
459 err[i] = (float)sqrt(a*a + b*b + c*c);
463 bool cv::Affine3DEstimator::checkSubset( const CvMat* ms1, int count )
465 CV_Assert( CV_MAT_TYPE(ms1->type) == CV_64FC3 );
467 int j, k, i = count - 1;
468 const Point3d* ptr = reinterpret_cast<const Point3d*>(ms1->data.ptr);
470 // check that the i-th selected point does not belong
471 // to a line connecting some previously selected points
473 for(j = 0; j < i; ++j)
475 Point3d d1 = ptr[j] - ptr[i];
476 double n1 = norm(d1);
478 for(k = 0; k < j; ++k)
480 Point3d d2 = ptr[k] - ptr[i];
481 double n = norm(d2) * n1;
483 if (fabs(d1.dot(d2) / n) > 0.996)
493 int cv::estimateAffine3D(const Mat& from, const Mat& to, Mat& out, vector<uchar>& outliers, double param1, double param2)
495 size_t count = from.cols*from.rows*from.channels()/3;
497 CV_Assert( count >= 4 && from.isContinuous() && to.isContinuous() &&
498 from.depth() == CV_32F && to.depth() == CV_32F &&
499 ((from.rows == 1 && from.channels() == 3) || from.cols*from.channels() == 3) &&
500 ((to.rows == 1 && to.channels() == 3) || to.cols*to.channels() == 3) &&
501 count == (size_t)to.cols*to.rows*to.channels()/3);
503 out.create(3, 4, CV_64F);
504 outliers.resize(count);
505 fill(outliers.begin(), outliers.end(), (uchar)1);
507 vector<Point3d> dFrom;
510 copy(from.ptr<Point3f>(), from.ptr<Point3f>() + count, back_inserter(dFrom));
511 copy(to.ptr<Point3f>(), to.ptr<Point3f>() + count, back_inserter(dTo));
514 CvMat mask = cvMat( 1, count, CV_8U, &outliers[0] );
515 CvMat m1 = cvMat( 1, count, CV_64FC3, &dFrom[0] );
516 CvMat m2 = cvMat( 1, count, CV_64FC3, &dTo[0] );
518 const double epsilon = numeric_limits<double>::epsilon();
519 param1 = param1 <= 0 ? 3 : param1;
520 param2 = (param2 < epsilon) ? 0.99 : (param2 > 1 - epsilon) ? 0.99 : param2;
522 return Affine3DEstimator().runRANSAC(&m1,& m2, &F3x4, &mask, param1, param2 );