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.
45 cvMaxRect( const CvRect* rect1, const CvRect* rect2 )
52 max_rect.x = a = rect1->x;
57 max_rect.width = a += rect1->width;
60 if( max_rect.width < b )
62 max_rect.width -= max_rect.x;
64 max_rect.y = a = rect1->y;
69 max_rect.height = a += rect1->height;
72 if( max_rect.height < b )
74 max_rect.height -= max_rect.y;
82 return cvRect(0,0,0,0);
87 cvBoxPoints( CvBox2D box, CvPoint2D32f pt[4] )
89 CV_FUNCNAME( "cvBoxPoints" );
93 double angle = box.angle*CV_PI/180.;
94 float a = (float)cos(angle)*0.5f;
95 float b = (float)sin(angle)*0.5f;
98 CV_ERROR( CV_StsNullPtr, "NULL vertex array pointer" );
100 pt[0].x = box.center.x - a*box.size.height - b*box.size.width;
101 pt[0].y = box.center.y + b*box.size.height - a*box.size.width;
102 pt[1].x = box.center.x + a*box.size.height - b*box.size.width;
103 pt[1].y = box.center.y - b*box.size.height - a*box.size.width;
104 pt[2].x = 2*box.center.x - pt[0].x;
105 pt[2].y = 2*box.center.y - pt[0].y;
106 pt[3].x = 2*box.center.x - pt[1].x;
107 pt[3].y = 2*box.center.y - pt[1].y;
114 icvIntersectLines( double x1, double dx1, double y1, double dy1,
115 double x2, double dx2, double y2, double dy2, double *t2 )
117 double d = dx1 * dy2 - dx2 * dy1;
122 *t2 = ((x2 - x1) * dy1 - (y2 - y1) * dx1) / d;
130 icvCreateCenterNormalLine( CvSubdiv2DEdge edge, double *_a, double *_b, double *_c )
132 CvPoint2D32f org = cvSubdiv2DEdgeOrg( edge )->pt;
133 CvPoint2D32f dst = cvSubdiv2DEdgeDst( edge )->pt;
135 double a = dst.x - org.x;
136 double b = dst.y - org.y;
137 double c = -(a * (dst.x + org.x) + b * (dst.y + org.y));
146 icvIntersectLines3( double *a0, double *b0, double *c0,
147 double *a1, double *b1, double *c1, CvPoint2D32f * point )
149 double det = a0[0] * b1[0] - a1[0] * b0[0];
154 point->x = (float) ((b0[0] * c1[0] - b1[0] * c0[0]) * det);
155 point->y = (float) ((a1[0] * c0[0] - a0[0] * c1[0]) * det);
159 point->x = point->y = FLT_MAX;
165 cvPointPolygonTest( const CvArr* _contour, CvPoint2D32f pt, int measure_dist )
168 CV_FUNCNAME( "cvCheckPointPolygon" );
174 CvSeq* contour = (CvSeq*)_contour;
176 int i, total, counter = 0;
178 double min_dist_num = FLT_MAX, min_dist_denom = 1;
181 if( !CV_IS_SEQ(contour) )
183 CV_CALL( contour = cvPointSeqFromMat( CV_SEQ_KIND_CURVE + CV_SEQ_FLAG_CLOSED,
184 _contour, &header, &block ));
186 else if( CV_IS_SEQ_POINT_SET(contour) )
188 if( contour->header_size == sizeof(CvContour) && !measure_dist )
190 CvRect r = ((CvContour*)contour)->rect;
191 if( pt.x < r.x || pt.y < r.y ||
192 pt.x >= r.x + r.width || pt.y >= r.y + r.height )
196 else if( CV_IS_SEQ_CHAIN(contour) )
198 CV_ERROR( CV_StsBadArg,
199 "Chains are not supported. Convert them to polygonal representation using cvApproxChains()" );
202 CV_ERROR( CV_StsBadArg, "Input contour is neither a valid sequence nor a matrix" );
204 total = contour->total;
205 is_float = CV_SEQ_ELTYPE(contour) == CV_32FC2;
206 cvStartReadSeq( contour, &reader, -1 );
208 if( !is_float && !measure_dist && (ip.x = cvRound(pt.x)) == pt.x && (ip.y = cvRound(pt.y)) == pt.y )
210 // the fastest "pure integer" branch
212 CV_READ_SEQ_ELEM( v, reader );
214 for( i = 0; i < total; i++ )
218 CV_READ_SEQ_ELEM( v, reader );
220 if( (v0.y <= ip.y && v.y <= ip.y) ||
221 (v0.y > ip.y && v.y > ip.y) ||
222 (v0.x < ip.x && v.x < ip.x) )
224 if( ip.y == v.y && (ip.x == v.x || (ip.y == v0.y &&
225 ((v0.x <= ip.x && ip.x <= v.x) || (v.x <= ip.x && ip.x <= v0.x)))) )
230 dist = (ip.y - v0.y)*(v.x - v0.x) - (ip.x - v0.x)*(v.y - v0.y);
238 result = counter % 2 == 0 ? -100 : 100;
247 CV_READ_SEQ_ELEM( v, reader );
251 CV_READ_SEQ_ELEM( iv, reader );
252 v = cvPointTo32f( iv );
257 for( i = 0; i < total; i++ )
263 CV_READ_SEQ_ELEM( v, reader );
267 CV_READ_SEQ_ELEM( iv, reader );
268 v = cvPointTo32f( iv );
271 if( (v0.y <= pt.y && v.y <= pt.y) ||
272 (v0.y > pt.y && v.y > pt.y) ||
273 (v0.x < pt.x && v.x < pt.x) )
275 if( pt.y == v.y && (pt.x == v.x || (pt.y == v0.y &&
276 ((v0.x <= pt.x && pt.x <= v.x) || (v.x <= pt.x && pt.x <= v0.x)))) )
281 dist = (double)(pt.y - v0.y)*(v.x - v0.x) - (double)(pt.x - v0.x)*(v.y - v0.y);
289 result = counter % 2 == 0 ? -100 : 100;
293 for( i = 0; i < total; i++ )
295 double dx, dy, dx1, dy1, dx2, dy2, dist_num, dist_denom = 1;
300 CV_READ_SEQ_ELEM( v, reader );
304 CV_READ_SEQ_ELEM( iv, reader );
305 v = cvPointTo32f( iv );
308 dx = v.x - v0.x; dy = v.y - v0.y;
309 dx1 = pt.x - v0.x; dy1 = pt.y - v0.y;
310 dx2 = pt.x - v.x; dy2 = pt.y - v.y;
312 if( dx1*dx + dy1*dy <= 0 )
313 dist_num = dx1*dx1 + dy1*dy1;
314 else if( dx2*dx + dy2*dy >= 0 )
315 dist_num = dx2*dx2 + dy2*dy2;
318 dist_num = (dy1*dx - dx1*dy);
319 dist_num *= dist_num;
320 dist_denom = dx*dx + dy*dy;
323 if( dist_num*min_dist_denom < min_dist_num*dist_denom )
325 min_dist_num = dist_num;
326 min_dist_denom = dist_denom;
327 if( min_dist_num == 0 )
331 if( (v0.y <= pt.y && v.y <= pt.y) ||
332 (v0.y > pt.y && v.y > pt.y) ||
333 (v0.x < pt.x && v.x < pt.x) )
336 dist_num = dy1*dx - dx1*dy;
338 dist_num = -dist_num;
339 counter += dist_num > 0;
342 result = sqrt(min_dist_num/min_dist_denom);
343 if( counter % 2 == 0 )
355 cvRQDecomp3x3( const CvMat *matrixM, CvMat *matrixR, CvMat *matrixQ,
356 CvMat *matrixQx, CvMat *matrixQy, CvMat *matrixQz,
357 CvPoint3D64f *eulerAngles)
359 CV_FUNCNAME("cvRQDecomp3x3");
362 double _M[3][3], _R[3][3], _Q[3][3];
363 CvMat M = cvMat(3, 3, CV_64F, _M);
364 CvMat R = cvMat(3, 3, CV_64F, _R);
365 CvMat Q = cvMat(3, 3, CV_64F, _Q);
368 /* Validate parameters. */
369 CV_ASSERT( CV_IS_MAT(matrixM) && CV_IS_MAT(matrixR) && CV_IS_MAT(matrixQ) &&
370 matrixM->cols == 3 && matrixM->rows == 3 &&
371 CV_ARE_SIZES_EQ(matrixM, matrixR) && CV_ARE_SIZES_EQ(matrixM, matrixQ));
373 cvConvert(matrixM, &M);
376 /* Find Givens rotation Q_x for x axis (left multiplication). */
379 Qx = ( 0 c s ), c = m33/sqrt(m32^2 + m33^2), s = m32/sqrt(m32^2 + m33^2)
384 z = 1./sqrt(c * c + s * s + DBL_EPSILON);
388 double _Qx[3][3] = { {1, 0, 0}, {0, c, s}, {0, -s, c} };
389 CvMat Qx = cvMat(3, 3, CV_64F, _Qx);
391 cvMatMul(&M, &Qx, &R);
392 assert(fabs(_R[2][1]) < FLT_EPSILON);
395 /* Find Givens rotation for y axis. */
398 Qy = ( 0 1 0 ), c = m33/sqrt(m31^2 + m33^2), s = m31/sqrt(m31^2 + m33^2)
403 z = 1./sqrt(c * c + s * s + DBL_EPSILON);
407 double _Qy[3][3] = { {c, 0, s}, {0, 1, 0}, {-s, 0, c} };
408 CvMat Qy = cvMat(3, 3, CV_64F, _Qy);
409 cvMatMul(&R, &Qy, &M);
411 assert(fabs(_M[2][0]) < FLT_EPSILON);
414 /* Find Givens rotation for z axis. */
417 Qz = (-s c 0 ), c = m22/sqrt(m21^2 + m22^2), s = m21/sqrt(m21^2 + m22^2)
423 z = 1./sqrt(c * c + s * s + DBL_EPSILON);
427 double _Qz[3][3] = { {c, s, 0}, {-s, c, 0}, {0, 0, 1} };
428 CvMat Qz = cvMat(3, 3, CV_64F, _Qz);
430 cvMatMul(&M, &Qz, &R);
431 assert(fabs(_R[1][0]) < FLT_EPSILON);
434 // Solve the decomposition ambiguity.
435 // Diagonal entries of R, except the last one, shall be positive.
436 // Further rotate R by 180 degree if necessary
441 // rotate around z for 180 degree, i.e. a rotation matrix of
456 // rotate around y for 180 degree, i.e. a rotation matrix of
465 cvTranspose( &Qz, &Qz );
473 else if( _R[1][1] < 0 )
475 // ??? for some reason, we never get here ???
477 // rotate around x for 180 degree, i.e. a rotation matrix of
487 cvTranspose( &Qz, &Qz );
488 cvTranspose( &Qy, &Qy );
496 // calculate the euler angle
499 eulerAngles->x = acos(_Qx[1][1]) * (_Qx[1][2] >= 0 ? 1 : -1) * (180.0 / CV_PI);
500 eulerAngles->y = acos(_Qy[0][0]) * (_Qy[0][2] >= 0 ? 1 : -1) * (180.0 / CV_PI);
501 eulerAngles->z = acos(_Qz[0][0]) * (_Qz[0][1] >= 0 ? 1 : -1) * (180.0 / CV_PI);
504 /* Calulate orthogonal matrix. */
508 cvGEMM( &Qz, &Qy, 1, 0, 0, &M, CV_GEMM_A_T + CV_GEMM_B_T );
509 cvGEMM( &M, &Qx, 1, 0, 0, &Q, CV_GEMM_B_T );
511 /* Save R and Q matrices. */
512 cvConvert( &R, matrixR );
513 cvConvert( &Q, matrixQ );
516 cvConvert(&Qx, matrixQx);
518 cvConvert(&Qy, matrixQy);
520 cvConvert(&Qz, matrixQz);
528 cvDecomposeProjectionMatrix( const CvMat *projMatr, CvMat *calibMatr,
529 CvMat *rotMatr, CvMat *posVect,
530 CvMat *rotMatrX, CvMat *rotMatrY,
531 CvMat *rotMatrZ, CvPoint3D64f *eulerAngles)
533 CvMat *tmpProjMatr = 0;
534 CvMat *tmpMatrixD = 0;
535 CvMat *tmpMatrixV = 0;
536 CvMat *tmpMatrixM = 0;
538 CV_FUNCNAME("cvDecomposeProjectionMatrix");
541 /* Validate parameters. */
542 if(projMatr == 0 || calibMatr == 0 || rotMatr == 0 || posVect == 0)
543 CV_ERROR(CV_StsNullPtr, "Some of parameters is a NULL pointer!");
545 if(!CV_IS_MAT(projMatr) || !CV_IS_MAT(calibMatr) || !CV_IS_MAT(rotMatr) || !CV_IS_MAT(posVect))
546 CV_ERROR(CV_StsUnsupportedFormat, "Input parameters must be a matrices!");
548 if(projMatr->cols != 4 || projMatr->rows != 3)
549 CV_ERROR(CV_StsUnmatchedSizes, "Size of projection matrix must be 3x4!");
551 if(calibMatr->cols != 3 || calibMatr->rows != 3 || rotMatr->cols != 3 || rotMatr->rows != 3)
552 CV_ERROR(CV_StsUnmatchedSizes, "Size of calibration and rotation matrices must be 3x3!");
554 if(posVect->cols != 1 || posVect->rows != 4)
555 CV_ERROR(CV_StsUnmatchedSizes, "Size of position vector must be 4x1!");
557 CV_CALL(tmpProjMatr = cvCreateMat(4, 4, CV_64F));
558 CV_CALL(tmpMatrixD = cvCreateMat(4, 4, CV_64F));
559 CV_CALL(tmpMatrixV = cvCreateMat(4, 4, CV_64F));
560 CV_CALL(tmpMatrixM = cvCreateMat(3, 3, CV_64F));
562 /* Compute position vector. */
564 cvSetZero(tmpProjMatr); // Add zero row to make matrix square.
566 for(i = 0; i < 3; i++)
567 for(k = 0; k < 4; k++)
568 cvmSet(tmpProjMatr, i, k, cvmGet(projMatr, i, k));
570 CV_CALL(cvSVD(tmpProjMatr, tmpMatrixD, NULL, tmpMatrixV, CV_SVD_MODIFY_A + CV_SVD_V_T));
572 /* Save position vector. */
574 for(i = 0; i < 4; i++)
575 cvmSet(posVect, i, 0, cvmGet(tmpMatrixV, 3, i)); // Solution is last row of V.
577 /* Compute calibration and rotation matrices via RQ decomposition. */
579 cvGetCols(projMatr, tmpMatrixM, 0, 3); // M is first square matrix of P.
581 assert(cvDet(tmpMatrixM) != 0.0); // So far only finite cameras could be decomposed, so M has to be nonsingular [det(M) != 0].
583 CV_CALL(cvRQDecomp3x3(tmpMatrixM, calibMatr, rotMatr, rotMatrX, rotMatrY, rotMatrZ, eulerAngles));
587 cvReleaseMat(&tmpProjMatr);
588 cvReleaseMat(&tmpMatrixD);
589 cvReleaseMat(&tmpMatrixV);
590 cvReleaseMat(&tmpMatrixM);
596 void RQDecomp3x3( const Mat& M, Mat& R, Mat& Q )
598 R.create(3, 3, M.type());
599 Q.create(3, 3, M.type());
601 CvMat _M = M, _R = R, _Q = Q;
602 cvRQDecomp3x3(&_M, &_R, &_Q, 0, 0, 0, 0);
605 Vec3d RQDecomp3x3( const Mat& M, Mat& R, Mat& Q,
606 Mat& Qx, Mat& Qy, Mat& Qz )
608 R.create(3, 3, M.type());
609 Q.create(3, 3, M.type());
612 CvMat _M = M, _R = R, _Q = Q, _Qx = Qx, _Qy = Qy, _Qz = Qz;
613 cvRQDecomp3x3(&_M, &_R, &_Q, &_Qx, &_Qy, &_Qz, (CvPoint3D64f*)&eulerAngles[0]);
617 void decomposeProjectionMatrix( const Mat& projMatrix, Mat& cameraMatrix,
618 Mat& rotMatrix, Mat& transVect )
620 int type = projMatrix.type();
621 cameraMatrix.create(3, 3, type);
622 rotMatrix.create(3, 3, type);
623 transVect.create(3, 3, type);
624 CvMat _projMatrix = projMatrix, _cameraMatrix = cameraMatrix;
625 CvMat _rotMatrix = rotMatrix, _transVect = transVect;
626 cvDecomposeProjectionMatrix(&_projMatrix, &_cameraMatrix, &_rotMatrix,
627 &_transVect, 0, 0, 0, 0);
630 void decomposeProjectionMatrix( const Mat& projMatrix, Mat& cameraMatrix,
631 Mat& rotMatrix, Mat& transVect,
632 Mat& rotMatrixX, Mat& rotMatrixY,
633 Mat& rotMatrixZ, Vec3d& eulerAngles )
635 int type = projMatrix.type();
636 cameraMatrix.create(3, 3, type);
637 rotMatrix.create(3, 3, type);
638 transVect.create(3, 3, type);
639 rotMatrixX.create(3, 3, type);
640 rotMatrixY.create(3, 3, type);
641 rotMatrixZ.create(3, 3, type);
642 CvMat _projMatrix = projMatrix, _cameraMatrix = cameraMatrix;
643 CvMat _rotMatrix = rotMatrix, _transVect = transVect;
644 CvMat _rotMatrixX = rotMatrixX, _rotMatrixY = rotMatrixY;
645 CvMat _rotMatrixZ = rotMatrixZ;
646 cvDecomposeProjectionMatrix(&_projMatrix, &_cameraMatrix, &_rotMatrix,
647 &_transVect, &_rotMatrixX, &_rotMatrixY,
648 &_rotMatrixZ, (CvPoint3D64f*)&eulerAngles[0]);