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) 2000, Intel Corporation, 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 /************************************************************************************\ 43 This is improved variant of chessboard corner detection algorithm that 44 uses a graph of connected quads. It is based on the code contributed 45 by Vladimir Vezhnevets and Philip Gruebele. 46 Here is the copyright notice from the original Vladimir's code: 47 =============================================================== 48 49 The algorithms developed and implemented by Vezhnevets Vldimir 50 aka Dead Moroz (vvp (at) graphics.cs.msu.ru) 51 See http://graphics.cs.msu.su/en/research/calibration/opencv.html 52 for detailed information. 53 54 Reliability additions and modifications made by Philip Gruebele. 55 <a href="mailto:pgruebele (at) cox.net">pgruebele (at) cox.net</a> 56 57 Some further improvements for detection of partially ocluded boards at non-ideal 58 lighting conditions have been made by Alex Bovyrin and Kurt Kolonige 59 60 \************************************************************************************/ 61 62 #include "precomp.hpp" 63 #include "opencv2/imgproc/imgproc_c.h" 64 #include "opencv2/calib3d/calib3d_c.h" 65 #include "circlesgrid.hpp" 66 #include <stdarg.h> 67 68 //#define ENABLE_TRIM_COL_ROW 69 70 //#define DEBUG_CHESSBOARD 71 #ifdef DEBUG_CHESSBOARD 72 # include "opencv2/opencv_modules.hpp" 73 # ifdef HAVE_OPENCV_HIGHGUI 74 # include "opencv2/highgui.hpp" 75 # else 76 # undef DEBUG_CHESSBOARD 77 # endif 78 #endif 79 #ifdef DEBUG_CHESSBOARD 80 static int PRINTF( const char* fmt, ... ) 81 { 82 va_list args; 83 va_start(args, fmt); 84 return vprintf(fmt, args); 85 } 86 #else 87 static int PRINTF( const char*, ... ) 88 { 89 return 0; 90 } 91 #endif 92 93 94 //===================================================================================== 95 // Implementation for the enhanced calibration object detection 96 //===================================================================================== 97 98 #define MAX_CONTOUR_APPROX 7 99 100 struct CvContourEx 101 { 102 CV_CONTOUR_FIELDS() 103 int counter; 104 }; 105 106 //===================================================================================== 107 108 /// Corner info structure 109 /** This structure stores information about the chessboard corner.*/ 110 struct CvCBCorner 111 { 112 CvPoint2D32f pt; // Coordinates of the corner 113 int row; // Board row index 114 int count; // Number of neighbor corners 115 struct CvCBCorner* neighbors[4]; // Neighbor corners 116 117 float meanDist(int *_n) const 118 { 119 float sum = 0; 120 int n = 0; 121 for( int i = 0; i < 4; i++ ) 122 { 123 if( neighbors[i] ) 124 { 125 float dx = neighbors[i]->pt.x - pt.x; 126 float dy = neighbors[i]->pt.y - pt.y; 127 sum += sqrt(dx*dx + dy*dy); 128 n++; 129 } 130 } 131 if(_n) 132 *_n = n; 133 return sum/MAX(n,1); 134 } 135 }; 136 137 //===================================================================================== 138 /// Quadrangle contour info structure 139 /** This structure stores information about the chessboard quadrange.*/ 140 struct CvCBQuad 141 { 142 int count; // Number of quad neighbors 143 int group_idx; // quad group ID 144 int row, col; // row and column of this quad 145 bool ordered; // true if corners/neighbors are ordered counter-clockwise 146 float edge_len; // quad edge len, in pix^2 147 // neighbors and corners are synced, i.e., neighbor 0 shares corner 0 148 CvCBCorner *corners[4]; // Coordinates of quad corners 149 struct CvCBQuad *neighbors[4]; // Pointers of quad neighbors 150 }; 151 152 //===================================================================================== 153 154 //static CvMat* debug_img = 0; 155 156 static int icvGenerateQuads( CvCBQuad **quads, CvCBCorner **corners, 157 CvMemStorage *storage, CvMat *image, int flags ); 158 159 /*static int 160 icvGenerateQuadsEx( CvCBQuad **out_quads, CvCBCorner **out_corners, 161 CvMemStorage *storage, CvMat *image, CvMat *thresh_img, int dilation, int flags );*/ 162 163 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count ); 164 165 static int icvFindConnectedQuads( CvCBQuad *quads, int quad_count, 166 CvCBQuad **quad_group, int group_idx, 167 CvMemStorage* storage ); 168 169 static int icvCheckQuadGroup( CvCBQuad **quad_group, int count, 170 CvCBCorner **out_corners, CvSize pattern_size ); 171 172 static int icvCleanFoundConnectedQuads( int quad_count, 173 CvCBQuad **quads, CvSize pattern_size ); 174 175 static int icvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads, 176 int *all_count, CvCBQuad **all_quads, CvCBCorner **corners, 177 CvSize pattern_size, CvMemStorage* storage ); 178 179 static void icvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common); 180 181 #ifdef ENABLE_TRIM_COL_ROW 182 static int icvTrimCol(CvCBQuad **quads, int count, int col, int dir); 183 184 static int icvTrimRow(CvCBQuad **quads, int count, int row, int dir); 185 #endif 186 187 static int icvAddOuterQuad(CvCBQuad *quad, CvCBQuad **quads, int quad_count, 188 CvCBQuad **all_quads, int all_count, CvCBCorner **corners); 189 190 static void icvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0); 191 192 static int icvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size ); 193 194 #if 0 195 static void 196 icvCalcAffineTranf2D32f(CvPoint2D32f* pts1, CvPoint2D32f* pts2, int count, CvMat* affine_trans) 197 { 198 int i, j; 199 int real_count = 0; 200 for( j = 0; j < count; j++ ) 201 { 202 if( pts1[j].x >= 0 ) real_count++; 203 } 204 if(real_count < 3) return; 205 cv::Ptr<CvMat> xy = cvCreateMat( 2*real_count, 6, CV_32FC1 ); 206 cv::Ptr<CvMat> uv = cvCreateMat( 2*real_count, 1, CV_32FC1 ); 207 //estimate affine transfromation 208 for( i = 0, j = 0; j < count; j++ ) 209 { 210 if( pts1[j].x >= 0 ) 211 { 212 CV_MAT_ELEM( *xy, float, i*2+1, 2 ) = CV_MAT_ELEM( *xy, float, i*2, 0 ) = pts2[j].x; 213 CV_MAT_ELEM( *xy, float, i*2+1, 3 ) = CV_MAT_ELEM( *xy, float, i*2, 1 ) = pts2[j].y; 214 CV_MAT_ELEM( *xy, float, i*2, 2 ) = CV_MAT_ELEM( *xy, float, i*2, 3 ) = CV_MAT_ELEM( *xy, float, i*2, 5 ) = \ 215 CV_MAT_ELEM( *xy, float, i*2+1, 0 ) = CV_MAT_ELEM( *xy, float, i*2+1, 1 ) = CV_MAT_ELEM( *xy, float, i*2+1, 4 ) = 0; 216 CV_MAT_ELEM( *xy, float, i*2, 4 ) = CV_MAT_ELEM( *xy, float, i*2+1, 5 ) = 1; 217 CV_MAT_ELEM( *uv, float, i*2, 0 ) = pts1[j].x; 218 CV_MAT_ELEM( *uv, float, i*2+1, 0 ) = pts1[j].y; 219 i++; 220 } 221 } 222 223 cvSolve( xy, uv, affine_trans, CV_SVD ); 224 } 225 #endif 226 227 CV_IMPL 228 int cvFindChessboardCorners( const void* arr, CvSize pattern_size, 229 CvPoint2D32f* out_corners, int* out_corner_count, 230 int flags ) 231 { 232 int found = 0; 233 CvCBQuad *quads = 0, **quad_group = 0; 234 CvCBCorner *corners = 0, **corner_group = 0; 235 236 try 237 { 238 int k = 0; 239 const int min_dilations = 0; 240 const int max_dilations = 7; 241 cv::Ptr<CvMat> norm_img, thresh_img; 242 #ifdef DEBUG_CHESSBOARD 243 cv::Ptr<IplImage> dbg_img; 244 cv::Ptr<IplImage> dbg1_img; 245 cv::Ptr<IplImage> dbg2_img; 246 #endif 247 cv::Ptr<CvMemStorage> storage; 248 249 CvMat stub, *img = (CvMat*)arr; 250 251 int expected_corners_num = (pattern_size.width/2+1)*(pattern_size.height/2+1); 252 253 int prev_sqr_size = 0; 254 255 if( out_corner_count ) 256 *out_corner_count = 0; 257 258 IplImage _img; 259 int quad_count = 0, group_idx = 0, dilations = 0; 260 261 img = cvGetMat( img, &stub ); 262 //debug_img = img; 263 264 if( CV_MAT_DEPTH( img->type ) != CV_8U || CV_MAT_CN( img->type ) == 2 ) 265 CV_Error( CV_StsUnsupportedFormat, "Only 8-bit grayscale or color images are supported" ); 266 267 if( pattern_size.width <= 2 || pattern_size.height <= 2 ) 268 CV_Error( CV_StsOutOfRange, "Both width and height of the pattern should have bigger than 2" ); 269 270 if( !out_corners ) 271 CV_Error( CV_StsNullPtr, "Null pointer to corners" ); 272 273 storage.reset(cvCreateMemStorage(0)); 274 thresh_img.reset(cvCreateMat( img->rows, img->cols, CV_8UC1 )); 275 276 #ifdef DEBUG_CHESSBOARD 277 dbg_img = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 3 ); 278 dbg1_img = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 3 ); 279 dbg2_img = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 3 ); 280 #endif 281 282 if( CV_MAT_CN(img->type) != 1 || (flags & CV_CALIB_CB_NORMALIZE_IMAGE) ) 283 { 284 // equalize the input image histogram - 285 // that should make the contrast between "black" and "white" areas big enough 286 norm_img.reset(cvCreateMat( img->rows, img->cols, CV_8UC1 )); 287 288 if( CV_MAT_CN(img->type) != 1 ) 289 { 290 cvCvtColor( img, norm_img, CV_BGR2GRAY ); 291 img = norm_img; 292 } 293 294 if( flags & CV_CALIB_CB_NORMALIZE_IMAGE ) 295 { 296 cvEqualizeHist( img, norm_img ); 297 img = norm_img; 298 } 299 } 300 301 if( flags & CV_CALIB_CB_FAST_CHECK) 302 { 303 cvGetImage(img, &_img); 304 int check_chessboard_result = cvCheckChessboard(&_img, pattern_size); 305 if(check_chessboard_result <= 0) 306 { 307 return 0; 308 } 309 } 310 311 // Try our standard "1" dilation, but if the pattern is not found, iterate the whole procedure with higher dilations. 312 // This is necessary because some squares simply do not separate properly with a single dilation. However, 313 // we want to use the minimum number of dilations possible since dilations cause the squares to become smaller, 314 // making it difficult to detect smaller squares. 315 for( k = 0; k < 6; k++ ) 316 { 317 for( dilations = min_dilations; dilations <= max_dilations; dilations++ ) 318 { 319 if (found) 320 break; // already found it 321 322 cvFree(&quads); 323 cvFree(&corners); 324 325 /*if( k == 1 ) 326 { 327 //Pattern was not found using binarization 328 // Run multi-level quads extraction 329 // In case one-level binarization did not give enough number of quads 330 CV_CALL( quad_count = icvGenerateQuadsEx( &quads, &corners, storage, img, thresh_img, dilations, flags )); 331 PRINTF("EX quad count: %d/%d\n", quad_count, expected_corners_num); 332 } 333 else*/ 334 { 335 // convert the input grayscale image to binary (black-n-white) 336 if( flags & CV_CALIB_CB_ADAPTIVE_THRESH ) 337 { 338 int block_size = cvRound(prev_sqr_size == 0 ? 339 MIN(img->cols,img->rows)*(k%2 == 0 ? 0.2 : 0.1): prev_sqr_size*2)|1; 340 341 // convert to binary 342 cvAdaptiveThreshold( img, thresh_img, 255, 343 CV_ADAPTIVE_THRESH_MEAN_C, CV_THRESH_BINARY, block_size, (k/2)*5 ); 344 if (dilations > 0) 345 cvDilate( thresh_img, thresh_img, 0, dilations-1 ); 346 } 347 else 348 { 349 // Make dilation before the thresholding. 350 // It splits chessboard corners 351 //cvDilate( img, thresh_img, 0, 1 ); 352 353 // empiric threshold level 354 double mean = cvAvg( img ).val[0]; 355 int thresh_level = cvRound( mean - 10 ); 356 thresh_level = MAX( thresh_level, 10 ); 357 358 cvThreshold( img, thresh_img, thresh_level, 255, CV_THRESH_BINARY ); 359 cvDilate( thresh_img, thresh_img, 0, dilations ); 360 } 361 362 #ifdef DEBUG_CHESSBOARD 363 cvCvtColor(thresh_img,dbg_img,CV_GRAY2BGR); 364 #endif 365 366 // So we can find rectangles that go to the edge, we draw a white line around the image edge. 367 // Otherwise FindContours will miss those clipped rectangle contours. 368 // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()... 369 cvRectangle( thresh_img, cvPoint(0,0), cvPoint(thresh_img->cols-1, 370 thresh_img->rows-1), CV_RGB(255,255,255), 3, 8); 371 372 quad_count = icvGenerateQuads( &quads, &corners, storage, thresh_img, flags ); 373 374 PRINTF("Quad count: %d/%d\n", quad_count, expected_corners_num); 375 } 376 377 378 #ifdef DEBUG_CHESSBOARD 379 cvCopy(dbg_img, dbg1_img); 380 cvNamedWindow("all_quads", 1); 381 // copy corners to temp array 382 for(int i = 0; i < quad_count; i++ ) 383 { 384 for (int k=0; k<4; k++) 385 { 386 CvPoint2D32f pt1, pt2; 387 CvScalar color = CV_RGB(30,255,30); 388 pt1 = quads[i].corners[k]->pt; 389 pt2 = quads[i].corners[(k+1)%4]->pt; 390 pt2.x = (pt1.x + pt2.x)/2; 391 pt2.y = (pt1.y + pt2.y)/2; 392 if (k>0) 393 color = CV_RGB(200,200,0); 394 cvLine( dbg1_img, cvPointFrom32f(pt1), cvPointFrom32f(pt2), color, 3, 8); 395 } 396 } 397 398 399 cvShowImage("all_quads", (IplImage*)dbg1_img); 400 cvWaitKey(); 401 #endif 402 403 if( quad_count <= 0 ) 404 continue; 405 406 // Find quad's neighbors 407 icvFindQuadNeighbors( quads, quad_count ); 408 409 // allocate extra for adding in icvOrderFoundQuads 410 cvFree(&quad_group); 411 cvFree(&corner_group); 412 quad_group = (CvCBQuad**)cvAlloc( sizeof(quad_group[0]) * (quad_count+quad_count / 2)); 413 corner_group = (CvCBCorner**)cvAlloc( sizeof(corner_group[0]) * (quad_count+quad_count / 2)*4 ); 414 415 for( group_idx = 0; ; group_idx++ ) 416 { 417 int count = 0; 418 count = icvFindConnectedQuads( quads, quad_count, quad_group, group_idx, storage ); 419 420 int icount = count; 421 if( count == 0 ) 422 break; 423 424 // order the quad corners globally 425 // maybe delete or add some 426 PRINTF("Starting ordering of inner quads\n"); 427 count = icvOrderFoundConnectedQuads(count, quad_group, &quad_count, &quads, &corners, 428 pattern_size, storage ); 429 PRINTF("Orig count: %d After ordering: %d\n", icount, count); 430 431 432 #ifdef DEBUG_CHESSBOARD 433 cvCopy(dbg_img,dbg2_img); 434 cvNamedWindow("connected_group", 1); 435 // copy corners to temp array 436 for(int i = 0; i < quad_count; i++ ) 437 { 438 if (quads[i].group_idx == group_idx) 439 for (int k=0; k<4; k++) 440 { 441 CvPoint2D32f pt1, pt2; 442 CvScalar color = CV_RGB(30,255,30); 443 if (quads[i].ordered) 444 color = CV_RGB(255,30,30); 445 pt1 = quads[i].corners[k]->pt; 446 pt2 = quads[i].corners[(k+1)%4]->pt; 447 pt2.x = (pt1.x + pt2.x)/2; 448 pt2.y = (pt1.y + pt2.y)/2; 449 if (k>0) 450 color = CV_RGB(200,200,0); 451 cvLine( dbg2_img, cvPointFrom32f(pt1), cvPointFrom32f(pt2), color, 3, 8); 452 } 453 } 454 cvShowImage("connected_group", (IplImage*)dbg2_img); 455 cvWaitKey(); 456 #endif 457 458 if (count == 0) 459 continue; // haven't found inner quads 460 461 462 // If count is more than it should be, this will remove those quads 463 // which cause maximum deviation from a nice square pattern. 464 count = icvCleanFoundConnectedQuads( count, quad_group, pattern_size ); 465 PRINTF("Connected group: %d orig count: %d cleaned: %d\n", group_idx, icount, count); 466 467 count = icvCheckQuadGroup( quad_group, count, corner_group, pattern_size ); 468 PRINTF("Connected group: %d count: %d cleaned: %d\n", group_idx, icount, count); 469 470 { 471 int n = count > 0 ? pattern_size.width * pattern_size.height : -count; 472 n = MIN( n, pattern_size.width * pattern_size.height ); 473 float sum_dist = 0; 474 int total = 0; 475 476 for(int i = 0; i < n; i++ ) 477 { 478 int ni = 0; 479 float avgi = corner_group[i]->meanDist(&ni); 480 sum_dist += avgi*ni; 481 total += ni; 482 } 483 prev_sqr_size = cvRound(sum_dist/MAX(total, 1)); 484 485 if( count > 0 || (out_corner_count && -count > *out_corner_count) ) 486 { 487 // copy corners to output array 488 for(int i = 0; i < n; i++ ) 489 out_corners[i] = corner_group[i]->pt; 490 491 if( out_corner_count ) 492 *out_corner_count = n; 493 494 if( count == pattern_size.width*pattern_size.height && 495 icvCheckBoardMonotony( out_corners, pattern_size )) 496 { 497 found = 1; 498 break; 499 } 500 } 501 } 502 } 503 }//dilations 504 }// 505 506 if( found ) 507 found = icvCheckBoardMonotony( out_corners, pattern_size ); 508 509 // check that none of the found corners is too close to the image boundary 510 if( found ) 511 { 512 const int BORDER = 8; 513 for( k = 0; k < pattern_size.width*pattern_size.height; k++ ) 514 { 515 if( out_corners[k].x <= BORDER || out_corners[k].x > img->cols - BORDER || 516 out_corners[k].y <= BORDER || out_corners[k].y > img->rows - BORDER ) 517 break; 518 } 519 520 found = k == pattern_size.width*pattern_size.height; 521 } 522 523 if( found && pattern_size.height % 2 == 0 && pattern_size.width % 2 == 0 ) 524 { 525 int last_row = (pattern_size.height-1)*pattern_size.width; 526 double dy0 = out_corners[last_row].y - out_corners[0].y; 527 if( dy0 < 0 ) 528 { 529 int n = pattern_size.width*pattern_size.height; 530 for(int i = 0; i < n/2; i++ ) 531 { 532 CvPoint2D32f temp; 533 CV_SWAP(out_corners[i], out_corners[n-i-1], temp); 534 } 535 } 536 } 537 538 if( found ) 539 { 540 cv::Ptr<CvMat> gray; 541 if( CV_MAT_CN(img->type) != 1 ) 542 { 543 gray.reset(cvCreateMat(img->rows, img->cols, CV_8UC1)); 544 cvCvtColor(img, gray, CV_BGR2GRAY); 545 } 546 else 547 { 548 gray.reset(cvCloneMat(img)); 549 } 550 int wsize = 2; 551 cvFindCornerSubPix( gray, out_corners, pattern_size.width*pattern_size.height, 552 cvSize(wsize, wsize), cvSize(-1,-1), cvTermCriteria(CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 15, 0.1)); 553 } 554 } 555 catch(...) 556 { 557 cvFree(&quads); 558 cvFree(&corners); 559 cvFree(&quad_group); 560 cvFree(&corner_group); 561 throw; 562 } 563 564 cvFree(&quads); 565 cvFree(&corners); 566 cvFree(&quad_group); 567 cvFree(&corner_group); 568 return found; 569 } 570 571 // 572 // Checks that each board row and column is pretty much monotonous curve: 573 // It analyzes each row and each column of the chessboard as following: 574 // for each corner c lying between end points in the same row/column it checks that 575 // the point projection to the line segment (a,b) is lying between projections 576 // of the neighbor corners in the same row/column. 577 // 578 // This function has been created as temporary workaround for the bug in current implementation 579 // of cvFindChessboardCornes that produces absolutely unordered sets of corners. 580 // 581 582 static int 583 icvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size ) 584 { 585 int i, j, k; 586 587 for( k = 0; k < 2; k++ ) 588 { 589 for( i = 0; i < (k == 0 ? pattern_size.height : pattern_size.width); i++ ) 590 { 591 CvPoint2D32f a = k == 0 ? corners[i*pattern_size.width] : corners[i]; 592 CvPoint2D32f b = k == 0 ? corners[(i+1)*pattern_size.width-1] : 593 corners[(pattern_size.height-1)*pattern_size.width + i]; 594 float prevt = 0, dx0 = b.x - a.x, dy0 = b.y - a.y; 595 if( fabs(dx0) + fabs(dy0) < FLT_EPSILON ) 596 return 0; 597 for( j = 1; j < (k == 0 ? pattern_size.width : pattern_size.height) - 1; j++ ) 598 { 599 CvPoint2D32f c = k == 0 ? corners[i*pattern_size.width + j] : 600 corners[j*pattern_size.width + i]; 601 float t = ((c.x - a.x)*dx0 + (c.y - a.y)*dy0)/(dx0*dx0 + dy0*dy0); 602 if( t < prevt || t > 1 ) 603 return 0; 604 prevt = t; 605 } 606 } 607 } 608 609 return 1; 610 } 611 612 // 613 // order a group of connected quads 614 // order of corners: 615 // 0 is top left 616 // clockwise from there 617 // note: "top left" is nominal, depends on initial ordering of starting quad 618 // but all other quads are ordered consistently 619 // 620 // can change the number of quads in the group 621 // can add quads, so we need to have quad/corner arrays passed in 622 // 623 624 static int 625 icvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads, 626 int *all_count, CvCBQuad **all_quads, CvCBCorner **corners, 627 CvSize pattern_size, CvMemStorage* storage ) 628 { 629 cv::Ptr<CvMemStorage> temp_storage(cvCreateChildMemStorage( storage )); 630 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage ); 631 632 // first find an interior quad 633 CvCBQuad *start = NULL; 634 for (int i=0; i<quad_count; i++) 635 { 636 if (quads[i]->count == 4) 637 { 638 start = quads[i]; 639 break; 640 } 641 } 642 643 if (start == NULL) 644 return 0; // no 4-connected quad 645 646 // start with first one, assign rows/cols 647 int row_min = 0, col_min = 0, row_max=0, col_max = 0; 648 649 std::map<int, int> col_hist; 650 std::map<int, int> row_hist; 651 652 cvSeqPush(stack, &start); 653 start->row = 0; 654 start->col = 0; 655 start->ordered = true; 656 657 // Recursively order the quads so that all position numbers (e.g., 658 // 0,1,2,3) are in the at the same relative corner (e.g., lower right). 659 660 while( stack->total ) 661 { 662 CvCBQuad* q; 663 cvSeqPop( stack, &q ); 664 int col = q->col; 665 int row = q->row; 666 col_hist[col]++; 667 row_hist[row]++; 668 669 // check min/max 670 if (row > row_max) row_max = row; 671 if (row < row_min) row_min = row; 672 if (col > col_max) col_max = col; 673 if (col < col_min) col_min = col; 674 675 for(int i = 0; i < 4; i++ ) 676 { 677 CvCBQuad *neighbor = q->neighbors[i]; 678 switch(i) // adjust col, row for this quad 679 { // start at top left, go clockwise 680 case 0: 681 row--; col--; break; 682 case 1: 683 col += 2; break; 684 case 2: 685 row += 2; break; 686 case 3: 687 col -= 2; break; 688 } 689 690 // just do inside quads 691 if (neighbor && neighbor->ordered == false && neighbor->count == 4) 692 { 693 PRINTF("col: %d row: %d\n", col, row); 694 icvOrderQuad(neighbor, q->corners[i], (i+2)%4); // set in order 695 neighbor->ordered = true; 696 neighbor->row = row; 697 neighbor->col = col; 698 cvSeqPush( stack, &neighbor ); 699 } 700 } 701 } 702 703 for (int i=col_min; i<=col_max; i++) 704 PRINTF("HIST[%d] = %d\n", i, col_hist[i]); 705 706 // analyze inner quad structure 707 int w = pattern_size.width - 1; 708 int h = pattern_size.height - 1; 709 int drow = row_max - row_min + 1; 710 int dcol = col_max - col_min + 1; 711 712 // normalize pattern and found quad indices 713 if ((w > h && dcol < drow) || 714 (w < h && drow < dcol)) 715 { 716 h = pattern_size.width - 1; 717 w = pattern_size.height - 1; 718 } 719 720 PRINTF("Size: %dx%d Pattern: %dx%d\n", dcol, drow, w, h); 721 722 // check if there are enough inner quads 723 if (dcol < w || drow < h) // found enough inner quads? 724 { 725 PRINTF("Too few inner quad rows/cols\n"); 726 return 0; // no, return 727 } 728 #ifdef ENABLE_TRIM_COL_ROW 729 // too many columns, not very common 730 if (dcol == w+1) // too many, trim 731 { 732 PRINTF("Trimming cols\n"); 733 if (col_hist[col_max] > col_hist[col_min]) 734 { 735 PRINTF("Trimming left col\n"); 736 quad_count = icvTrimCol(quads,quad_count,col_min,-1); 737 } 738 else 739 { 740 PRINTF("Trimming right col\n"); 741 quad_count = icvTrimCol(quads,quad_count,col_max,+1); 742 } 743 } 744 745 // too many rows, not very common 746 if (drow == h+1) // too many, trim 747 { 748 PRINTF("Trimming rows\n"); 749 if (row_hist[row_max] > row_hist[row_min]) 750 { 751 PRINTF("Trimming top row\n"); 752 quad_count = icvTrimRow(quads,quad_count,row_min,-1); 753 } 754 else 755 { 756 PRINTF("Trimming bottom row\n"); 757 quad_count = icvTrimRow(quads,quad_count,row_max,+1); 758 } 759 } 760 #endif 761 762 // check edges of inner quads 763 // if there is an outer quad missing, fill it in 764 // first order all inner quads 765 int found = 0; 766 for (int i=0; i<quad_count; i++) 767 { 768 if (quads[i]->count == 4) 769 { // ok, look at neighbors 770 int col = quads[i]->col; 771 int row = quads[i]->row; 772 for (int j=0; j<4; j++) 773 { 774 switch(j) // adjust col, row for this quad 775 { // start at top left, go clockwise 776 case 0: 777 row--; col--; break; 778 case 1: 779 col += 2; break; 780 case 2: 781 row += 2; break; 782 case 3: 783 col -= 2; break; 784 } 785 CvCBQuad *neighbor = quads[i]->neighbors[j]; 786 if (neighbor && !neighbor->ordered && // is it an inner quad? 787 col <= col_max && col >= col_min && 788 row <= row_max && row >= row_min) 789 { 790 // if so, set in order 791 PRINTF("Adding inner: col: %d row: %d\n", col, row); 792 found++; 793 icvOrderQuad(neighbor, quads[i]->corners[j], (j+2)%4); 794 neighbor->ordered = true; 795 neighbor->row = row; 796 neighbor->col = col; 797 } 798 } 799 } 800 } 801 802 // if we have found inner quads, add corresponding outer quads, 803 // which are missing 804 if (found > 0) 805 { 806 PRINTF("Found %d inner quads not connected to outer quads, repairing\n", found); 807 for (int i=0; i<quad_count; i++) 808 { 809 if (quads[i]->count < 4 && quads[i]->ordered) 810 { 811 int added = icvAddOuterQuad(quads[i],quads,quad_count,all_quads,*all_count,corners); 812 *all_count += added; 813 quad_count += added; 814 } 815 } 816 } 817 818 819 // final trimming of outer quads 820 if (dcol == w && drow == h) // found correct inner quads 821 { 822 PRINTF("Inner bounds ok, check outer quads\n"); 823 int rcount = quad_count; 824 for (int i=quad_count-1; i>=0; i--) // eliminate any quad not connected to 825 // an ordered quad 826 { 827 if (quads[i]->ordered == false) 828 { 829 bool outer = false; 830 for (int j=0; j<4; j++) // any neighbors that are ordered? 831 { 832 if (quads[i]->neighbors[j] && quads[i]->neighbors[j]->ordered) 833 outer = true; 834 } 835 if (!outer) // not an outer quad, eliminate 836 { 837 PRINTF("Removing quad %d\n", i); 838 icvRemoveQuadFromGroup(quads,rcount,quads[i]); 839 rcount--; 840 } 841 } 842 843 } 844 return rcount; 845 } 846 847 return 0; 848 } 849 850 851 // add an outer quad 852 // looks for the neighbor of <quad> that isn't present, 853 // tries to add it in. 854 // <quad> is ordered 855 856 static int 857 icvAddOuterQuad( CvCBQuad *quad, CvCBQuad **quads, int quad_count, 858 CvCBQuad **all_quads, int all_count, CvCBCorner **corners ) 859 860 { 861 int added = 0; 862 for (int i=0; i<4; i++) // find no-neighbor corners 863 { 864 if (!quad->neighbors[i]) // ok, create and add neighbor 865 { 866 int j = (i+2)%4; 867 PRINTF("Adding quad as neighbor 2\n"); 868 CvCBQuad *q = &(*all_quads)[all_count]; 869 memset( q, 0, sizeof(*q) ); 870 added++; 871 quads[quad_count] = q; 872 quad_count++; 873 874 // set neighbor and group id 875 quad->neighbors[i] = q; 876 quad->count += 1; 877 q->neighbors[j] = quad; 878 q->group_idx = quad->group_idx; 879 q->count = 1; // number of neighbors 880 q->ordered = false; 881 q->edge_len = quad->edge_len; 882 883 // make corners of new quad 884 // same as neighbor quad, but offset 885 CvPoint2D32f pt = quad->corners[i]->pt; 886 CvCBCorner* corner; 887 float dx = pt.x - quad->corners[j]->pt.x; 888 float dy = pt.y - quad->corners[j]->pt.y; 889 for (int k=0; k<4; k++) 890 { 891 corner = &(*corners)[all_count*4+k]; 892 pt = quad->corners[k]->pt; 893 memset( corner, 0, sizeof(*corner) ); 894 corner->pt = pt; 895 q->corners[k] = corner; 896 corner->pt.x += dx; 897 corner->pt.y += dy; 898 } 899 // have to set exact corner 900 q->corners[j] = quad->corners[i]; 901 902 // now find other neighbor and add it, if possible 903 if (quad->neighbors[(i+3)%4] && 904 quad->neighbors[(i+3)%4]->ordered && 905 quad->neighbors[(i+3)%4]->neighbors[i] && 906 quad->neighbors[(i+3)%4]->neighbors[i]->ordered ) 907 { 908 CvCBQuad *qn = quad->neighbors[(i+3)%4]->neighbors[i]; 909 q->count = 2; 910 q->neighbors[(j+1)%4] = qn; 911 qn->neighbors[(i+1)%4] = q; 912 qn->count += 1; 913 // have to set exact corner 914 q->corners[(j+1)%4] = qn->corners[(i+1)%4]; 915 } 916 917 all_count++; 918 } 919 } 920 return added; 921 } 922 923 924 // trimming routines 925 #ifdef ENABLE_TRIM_COL_ROW 926 static int 927 icvTrimCol(CvCBQuad **quads, int count, int col, int dir) 928 { 929 int rcount = count; 930 // find the right quad(s) 931 for (int i=0; i<count; i++) 932 { 933 #ifdef DEBUG_CHESSBOARD 934 if (quads[i]->ordered) 935 PRINTF("index: %d cur: %d\n", col, quads[i]->col); 936 #endif 937 if (quads[i]->ordered && quads[i]->col == col) 938 { 939 if (dir == 1) 940 { 941 if (quads[i]->neighbors[1]) 942 { 943 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]); 944 rcount--; 945 } 946 if (quads[i]->neighbors[2]) 947 { 948 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]); 949 rcount--; 950 } 951 } 952 else 953 { 954 if (quads[i]->neighbors[0]) 955 { 956 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]); 957 rcount--; 958 } 959 if (quads[i]->neighbors[3]) 960 { 961 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]); 962 rcount--; 963 } 964 } 965 966 } 967 } 968 return rcount; 969 } 970 971 static int 972 icvTrimRow(CvCBQuad **quads, int count, int row, int dir) 973 { 974 int i, rcount = count; 975 // find the right quad(s) 976 for (i=0; i<count; i++) 977 { 978 #ifdef DEBUG_CHESSBOARD 979 if (quads[i]->ordered) 980 PRINTF("index: %d cur: %d\n", row, quads[i]->row); 981 #endif 982 if (quads[i]->ordered && quads[i]->row == row) 983 { 984 if (dir == 1) // remove from bottom 985 { 986 if (quads[i]->neighbors[2]) 987 { 988 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]); 989 rcount--; 990 } 991 if (quads[i]->neighbors[3]) 992 { 993 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]); 994 rcount--; 995 } 996 } 997 else // remove from top 998 { 999 if (quads[i]->neighbors[0]) 1000 { 1001 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]); 1002 rcount--; 1003 } 1004 if (quads[i]->neighbors[1]) 1005 { 1006 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]); 1007 rcount--; 1008 } 1009 } 1010 1011 } 1012 } 1013 return rcount; 1014 } 1015 #endif 1016 1017 // 1018 // remove quad from quad group 1019 // 1020 1021 static void 1022 icvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0) 1023 { 1024 int i, j; 1025 // remove any references to this quad as a neighbor 1026 for(i = 0; i < count; i++ ) 1027 { 1028 CvCBQuad *q = quads[i]; 1029 for(j = 0; j < 4; j++ ) 1030 { 1031 if( q->neighbors[j] == q0 ) 1032 { 1033 q->neighbors[j] = 0; 1034 q->count--; 1035 for(int k = 0; k < 4; k++ ) 1036 if( q0->neighbors[k] == q ) 1037 { 1038 q0->neighbors[k] = 0; 1039 q0->count--; 1040 break; 1041 } 1042 break; 1043 } 1044 } 1045 } 1046 1047 // remove the quad 1048 for(i = 0; i < count; i++ ) 1049 { 1050 CvCBQuad *q = quads[i]; 1051 if (q == q0) 1052 { 1053 quads[i] = quads[count-1]; 1054 break; 1055 } 1056 } 1057 } 1058 1059 // 1060 // put quad into correct order, where <corner> has value <common> 1061 // 1062 1063 static void 1064 icvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common) 1065 { 1066 // find the corner 1067 int tc; 1068 for (tc=0; tc<4; tc++) 1069 if (quad->corners[tc]->pt.x == corner->pt.x && 1070 quad->corners[tc]->pt.y == corner->pt.y) 1071 break; 1072 1073 // set corner order 1074 // shift 1075 while (tc != common) 1076 { 1077 // shift by one 1078 CvCBCorner *tempc; 1079 CvCBQuad *tempq; 1080 tempc = quad->corners[3]; 1081 tempq = quad->neighbors[3]; 1082 for (int i=3; i>0; i--) 1083 { 1084 quad->corners[i] = quad->corners[i-1]; 1085 quad->neighbors[i] = quad->neighbors[i-1]; 1086 } 1087 quad->corners[0] = tempc; 1088 quad->neighbors[0] = tempq; 1089 tc++; 1090 tc = tc%4; 1091 } 1092 } 1093 1094 1095 // if we found too many connect quads, remove those which probably do not belong. 1096 static int 1097 icvCleanFoundConnectedQuads( int quad_count, CvCBQuad **quad_group, CvSize pattern_size ) 1098 { 1099 CvPoint2D32f center; 1100 int i, j, k; 1101 // number of quads this pattern should contain 1102 int count = ((pattern_size.width + 1)*(pattern_size.height + 1) + 1)/2; 1103 1104 // if we have more quadrangles than we should, 1105 // try to eliminate duplicates or ones which don't belong to the pattern rectangle... 1106 if( quad_count <= count ) 1107 return quad_count; 1108 1109 // create an array of quadrangle centers 1110 cv::AutoBuffer<CvPoint2D32f> centers( quad_count ); 1111 cv::Ptr<CvMemStorage> temp_storage(cvCreateMemStorage(0)); 1112 1113 for( i = 0; i < quad_count; i++ ) 1114 { 1115 CvPoint2D32f ci; 1116 CvCBQuad* q = quad_group[i]; 1117 1118 for( j = 0; j < 4; j++ ) 1119 { 1120 CvPoint2D32f pt = q->corners[j]->pt; 1121 ci.x += pt.x; 1122 ci.y += pt.y; 1123 } 1124 1125 ci.x *= 0.25f; 1126 ci.y *= 0.25f; 1127 1128 centers[i] = ci; 1129 center.x += ci.x; 1130 center.y += ci.y; 1131 } 1132 center.x /= quad_count; 1133 center.y /= quad_count; 1134 1135 // If we still have more quadrangles than we should, 1136 // we try to eliminate bad ones based on minimizing the bounding box. 1137 // We iteratively remove the point which reduces the size of 1138 // the bounding box of the blobs the most 1139 // (since we want the rectangle to be as small as possible) 1140 // remove the quadrange that causes the biggest reduction 1141 // in pattern size until we have the correct number 1142 for( ; quad_count > count; quad_count-- ) 1143 { 1144 double min_box_area = DBL_MAX; 1145 int skip, min_box_area_index = -1; 1146 1147 // For each point, calculate box area without that point 1148 for( skip = 0; skip < quad_count; skip++ ) 1149 { 1150 // get bounding rectangle 1151 CvPoint2D32f temp = centers[skip]; // temporarily make index 'skip' the same as 1152 centers[skip] = center; // pattern center (so it is not counted for convex hull) 1153 CvMat pointMat = cvMat(1, quad_count, CV_32FC2, centers); 1154 CvSeq *hull = cvConvexHull2( &pointMat, temp_storage, CV_CLOCKWISE, 1 ); 1155 centers[skip] = temp; 1156 double hull_area = fabs(cvContourArea(hull, CV_WHOLE_SEQ)); 1157 1158 // remember smallest box area 1159 if( hull_area < min_box_area ) 1160 { 1161 min_box_area = hull_area; 1162 min_box_area_index = skip; 1163 } 1164 cvClearMemStorage( temp_storage ); 1165 } 1166 1167 CvCBQuad *q0 = quad_group[min_box_area_index]; 1168 1169 // remove any references to this quad as a neighbor 1170 for( i = 0; i < quad_count; i++ ) 1171 { 1172 CvCBQuad *q = quad_group[i]; 1173 for( j = 0; j < 4; j++ ) 1174 { 1175 if( q->neighbors[j] == q0 ) 1176 { 1177 q->neighbors[j] = 0; 1178 q->count--; 1179 for( k = 0; k < 4; k++ ) 1180 if( q0->neighbors[k] == q ) 1181 { 1182 q0->neighbors[k] = 0; 1183 q0->count--; 1184 break; 1185 } 1186 break; 1187 } 1188 } 1189 } 1190 1191 // remove the quad 1192 quad_count--; 1193 quad_group[min_box_area_index] = quad_group[quad_count]; 1194 centers[min_box_area_index] = centers[quad_count]; 1195 } 1196 1197 return quad_count; 1198 } 1199 1200 //===================================================================================== 1201 1202 static int 1203 icvFindConnectedQuads( CvCBQuad *quad, int quad_count, CvCBQuad **out_group, 1204 int group_idx, CvMemStorage* storage ) 1205 { 1206 cv::Ptr<CvMemStorage> temp_storage(cvCreateChildMemStorage( storage )); 1207 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage ); 1208 int i, count = 0; 1209 1210 // Scan the array for a first unlabeled quad 1211 for( i = 0; i < quad_count; i++ ) 1212 { 1213 if( quad[i].count > 0 && quad[i].group_idx < 0) 1214 break; 1215 } 1216 1217 // Recursively find a group of connected quads starting from the seed quad[i] 1218 if( i < quad_count ) 1219 { 1220 CvCBQuad* q = &quad[i]; 1221 cvSeqPush( stack, &q ); 1222 out_group[count++] = q; 1223 q->group_idx = group_idx; 1224 q->ordered = false; 1225 1226 while( stack->total ) 1227 { 1228 cvSeqPop( stack, &q ); 1229 for( i = 0; i < 4; i++ ) 1230 { 1231 CvCBQuad *neighbor = q->neighbors[i]; 1232 if( neighbor && neighbor->count > 0 && neighbor->group_idx < 0 ) 1233 { 1234 cvSeqPush( stack, &neighbor ); 1235 out_group[count++] = neighbor; 1236 neighbor->group_idx = group_idx; 1237 neighbor->ordered = false; 1238 } 1239 } 1240 } 1241 } 1242 1243 return count; 1244 } 1245 1246 1247 //===================================================================================== 1248 1249 static int 1250 icvCheckQuadGroup( CvCBQuad **quad_group, int quad_count, 1251 CvCBCorner **out_corners, CvSize pattern_size ) 1252 { 1253 const int ROW1 = 1000000; 1254 const int ROW2 = 2000000; 1255 const int ROW_ = 3000000; 1256 int result = 0; 1257 int i, out_corner_count = 0, corner_count = 0; 1258 std::vector<CvCBCorner*> corners(quad_count*4); 1259 1260 int j, k, kk; 1261 int width = 0, height = 0; 1262 int hist[5] = {0,0,0,0,0}; 1263 CvCBCorner* first = 0, *first2 = 0, *right, *cur, *below, *c; 1264 1265 // build dual graph, which vertices are internal quad corners 1266 // and two vertices are connected iff they lie on the same quad edge 1267 for( i = 0; i < quad_count; i++ ) 1268 { 1269 CvCBQuad* q = quad_group[i]; 1270 /*CvScalar color = q->count == 0 ? cvScalar(0,255,255) : 1271 q->count == 1 ? cvScalar(0,0,255) : 1272 q->count == 2 ? cvScalar(0,255,0) : 1273 q->count == 3 ? cvScalar(255,255,0) : 1274 cvScalar(255,0,0);*/ 1275 1276 for( j = 0; j < 4; j++ ) 1277 { 1278 //cvLine( debug_img, cvPointFrom32f(q->corners[j]->pt), cvPointFrom32f(q->corners[(j+1)&3]->pt), color, 1, CV_AA, 0 ); 1279 if( q->neighbors[j] ) 1280 { 1281 CvCBCorner *a = q->corners[j], *b = q->corners[(j+1)&3]; 1282 // mark internal corners that belong to: 1283 // - a quad with a single neighbor - with ROW1, 1284 // - a quad with two neighbors - with ROW2 1285 // make the rest of internal corners with ROW_ 1286 int row_flag = q->count == 1 ? ROW1 : q->count == 2 ? ROW2 : ROW_; 1287 1288 if( a->row == 0 ) 1289 { 1290 corners[corner_count++] = a; 1291 a->row = row_flag; 1292 } 1293 else if( a->row > row_flag ) 1294 a->row = row_flag; 1295 1296 if( q->neighbors[(j+1)&3] ) 1297 { 1298 if( a->count >= 4 || b->count >= 4 ) 1299 goto finalize; 1300 for( k = 0; k < 4; k++ ) 1301 { 1302 if( a->neighbors[k] == b ) 1303 goto finalize; 1304 if( b->neighbors[k] == a ) 1305 goto finalize; 1306 } 1307 a->neighbors[a->count++] = b; 1308 b->neighbors[b->count++] = a; 1309 } 1310 } 1311 } 1312 } 1313 1314 if( corner_count != pattern_size.width*pattern_size.height ) 1315 goto finalize; 1316 1317 for( i = 0; i < corner_count; i++ ) 1318 { 1319 int n = corners[i]->count; 1320 assert( 0 <= n && n <= 4 ); 1321 hist[n]++; 1322 if( !first && n == 2 ) 1323 { 1324 if( corners[i]->row == ROW1 ) 1325 first = corners[i]; 1326 else if( !first2 && corners[i]->row == ROW2 ) 1327 first2 = corners[i]; 1328 } 1329 } 1330 1331 // start with a corner that belongs to a quad with a signle neighbor. 1332 // if we do not have such, start with a corner of a quad with two neighbors. 1333 if( !first ) 1334 first = first2; 1335 1336 if( !first || hist[0] != 0 || hist[1] != 0 || hist[2] != 4 || 1337 hist[3] != (pattern_size.width + pattern_size.height)*2 - 8 ) 1338 goto finalize; 1339 1340 cur = first; 1341 right = below = 0; 1342 out_corners[out_corner_count++] = cur; 1343 1344 for( k = 0; k < 4; k++ ) 1345 { 1346 c = cur->neighbors[k]; 1347 if( c ) 1348 { 1349 if( !right ) 1350 right = c; 1351 else if( !below ) 1352 below = c; 1353 } 1354 } 1355 1356 if( !right || (right->count != 2 && right->count != 3) || 1357 !below || (below->count != 2 && below->count != 3) ) 1358 goto finalize; 1359 1360 cur->row = 0; 1361 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,255,0), -1, 8, 0 ); 1362 1363 first = below; // remember the first corner in the next row 1364 // find and store the first row (or column) 1365 for(j=1;;j++) 1366 { 1367 right->row = 0; 1368 out_corners[out_corner_count++] = right; 1369 //cvCircle( debug_img, cvPointFrom32f(right->pt), 3, cvScalar(0,255-j*10,0), -1, 8, 0 ); 1370 if( right->count == 2 ) 1371 break; 1372 if( right->count != 3 || out_corner_count >= MAX(pattern_size.width,pattern_size.height) ) 1373 goto finalize; 1374 cur = right; 1375 for( k = 0; k < 4; k++ ) 1376 { 1377 c = cur->neighbors[k]; 1378 if( c && c->row > 0 ) 1379 { 1380 for( kk = 0; kk < 4; kk++ ) 1381 { 1382 if( c->neighbors[kk] == below ) 1383 break; 1384 } 1385 if( kk < 4 ) 1386 below = c; 1387 else 1388 right = c; 1389 } 1390 } 1391 } 1392 1393 width = out_corner_count; 1394 if( width == pattern_size.width ) 1395 height = pattern_size.height; 1396 else if( width == pattern_size.height ) 1397 height = pattern_size.width; 1398 else 1399 goto finalize; 1400 1401 // find and store all the other rows 1402 for( i = 1; ; i++ ) 1403 { 1404 if( !first ) 1405 break; 1406 cur = first; 1407 first = 0; 1408 for( j = 0;; j++ ) 1409 { 1410 cur->row = i; 1411 out_corners[out_corner_count++] = cur; 1412 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,0,255-j*10), -1, 8, 0 ); 1413 if( cur->count == 2 + (i < height-1) && j > 0 ) 1414 break; 1415 1416 right = 0; 1417 1418 // find a neighbor that has not been processed yet 1419 // and that has a neighbor from the previous row 1420 for( k = 0; k < 4; k++ ) 1421 { 1422 c = cur->neighbors[k]; 1423 if( c && c->row > i ) 1424 { 1425 for( kk = 0; kk < 4; kk++ ) 1426 { 1427 if( c->neighbors[kk] && c->neighbors[kk]->row == i-1 ) 1428 break; 1429 } 1430 if( kk < 4 ) 1431 { 1432 right = c; 1433 if( j > 0 ) 1434 break; 1435 } 1436 else if( j == 0 ) 1437 first = c; 1438 } 1439 } 1440 if( !right ) 1441 goto finalize; 1442 cur = right; 1443 } 1444 1445 if( j != width - 1 ) 1446 goto finalize; 1447 } 1448 1449 if( out_corner_count != corner_count ) 1450 goto finalize; 1451 1452 // check if we need to transpose the board 1453 if( width != pattern_size.width ) 1454 { 1455 CV_SWAP( width, height, k ); 1456 1457 memcpy( &corners[0], out_corners, corner_count*sizeof(corners[0]) ); 1458 for( i = 0; i < height; i++ ) 1459 for( j = 0; j < width; j++ ) 1460 out_corners[i*width + j] = corners[j*height + i]; 1461 } 1462 1463 // check if we need to revert the order in each row 1464 { 1465 CvPoint2D32f p0 = out_corners[0]->pt, p1 = out_corners[pattern_size.width-1]->pt, 1466 p2 = out_corners[pattern_size.width]->pt; 1467 if( (p1.x - p0.x)*(p2.y - p1.y) - (p1.y - p0.y)*(p2.x - p1.x) < 0 ) 1468 { 1469 if( width % 2 == 0 ) 1470 { 1471 for( i = 0; i < height; i++ ) 1472 for( j = 0; j < width/2; j++ ) 1473 CV_SWAP( out_corners[i*width+j], out_corners[i*width+width-j-1], c ); 1474 } 1475 else 1476 { 1477 for( j = 0; j < width; j++ ) 1478 for( i = 0; i < height/2; i++ ) 1479 CV_SWAP( out_corners[i*width+j], out_corners[(height - i - 1)*width+j], c ); 1480 } 1481 } 1482 } 1483 1484 result = corner_count; 1485 1486 finalize: 1487 1488 if( result <= 0 ) 1489 { 1490 corner_count = MIN( corner_count, pattern_size.width*pattern_size.height ); 1491 for( i = 0; i < corner_count; i++ ) 1492 out_corners[i] = corners[i]; 1493 result = -corner_count; 1494 1495 if (result == -pattern_size.width*pattern_size.height) 1496 result = -result; 1497 } 1498 1499 return result; 1500 } 1501 1502 1503 1504 1505 //===================================================================================== 1506 1507 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count ) 1508 { 1509 const float thresh_scale = 1.f; 1510 int idx, i, k, j; 1511 float dx, dy, dist; 1512 1513 // find quad neighbors 1514 for( idx = 0; idx < quad_count; idx++ ) 1515 { 1516 CvCBQuad* cur_quad = &quads[idx]; 1517 1518 // choose the points of the current quadrangle that are close to 1519 // some points of the other quadrangles 1520 // (it can happen for split corners (due to dilation) of the 1521 // checker board). Search only in other quadrangles! 1522 1523 // for each corner of this quadrangle 1524 for( i = 0; i < 4; i++ ) 1525 { 1526 CvPoint2D32f pt; 1527 float min_dist = FLT_MAX; 1528 int closest_corner_idx = -1; 1529 CvCBQuad *closest_quad = 0; 1530 CvCBCorner *closest_corner = 0; 1531 1532 if( cur_quad->neighbors[i] ) 1533 continue; 1534 1535 pt = cur_quad->corners[i]->pt; 1536 1537 // find the closest corner in all other quadrangles 1538 for( k = 0; k < quad_count; k++ ) 1539 { 1540 if( k == idx ) 1541 continue; 1542 1543 for( j = 0; j < 4; j++ ) 1544 { 1545 if( quads[k].neighbors[j] ) 1546 continue; 1547 1548 dx = pt.x - quads[k].corners[j]->pt.x; 1549 dy = pt.y - quads[k].corners[j]->pt.y; 1550 dist = dx * dx + dy * dy; 1551 1552 if( dist < min_dist && 1553 dist <= cur_quad->edge_len*thresh_scale && 1554 dist <= quads[k].edge_len*thresh_scale ) 1555 { 1556 // check edge lengths, make sure they're compatible 1557 // edges that are different by more than 1:4 are rejected 1558 float ediff = cur_quad->edge_len - quads[k].edge_len; 1559 if (ediff > 32*cur_quad->edge_len || 1560 ediff > 32*quads[k].edge_len) 1561 { 1562 PRINTF("Incompatible edge lengths\n"); 1563 continue; 1564 } 1565 closest_corner_idx = j; 1566 closest_quad = &quads[k]; 1567 min_dist = dist; 1568 } 1569 } 1570 } 1571 1572 // we found a matching corner point? 1573 if( closest_corner_idx >= 0 && min_dist < FLT_MAX ) 1574 { 1575 // If another point from our current quad is closer to the found corner 1576 // than the current one, then we don't count this one after all. 1577 // This is necessary to support small squares where otherwise the wrong 1578 // corner will get matched to closest_quad; 1579 closest_corner = closest_quad->corners[closest_corner_idx]; 1580 1581 for( j = 0; j < 4; j++ ) 1582 { 1583 if( cur_quad->neighbors[j] == closest_quad ) 1584 break; 1585 1586 dx = closest_corner->pt.x - cur_quad->corners[j]->pt.x; 1587 dy = closest_corner->pt.y - cur_quad->corners[j]->pt.y; 1588 1589 if( dx * dx + dy * dy < min_dist ) 1590 break; 1591 } 1592 1593 if( j < 4 || cur_quad->count >= 4 || closest_quad->count >= 4 ) 1594 continue; 1595 1596 // Check that each corner is a neighbor of different quads 1597 for( j = 0; j < closest_quad->count; j++ ) 1598 { 1599 if( closest_quad->neighbors[j] == cur_quad ) 1600 break; 1601 } 1602 if( j < closest_quad->count ) 1603 continue; 1604 1605 // check whether the closest corner to closest_corner 1606 // is different from cur_quad->corners[i]->pt 1607 for( k = 0; k < quad_count; k++ ) 1608 { 1609 CvCBQuad* q = &quads[k]; 1610 if( k == idx || q == closest_quad ) 1611 continue; 1612 1613 for( j = 0; j < 4; j++ ) 1614 if( !q->neighbors[j] ) 1615 { 1616 dx = closest_corner->pt.x - q->corners[j]->pt.x; 1617 dy = closest_corner->pt.y - q->corners[j]->pt.y; 1618 dist = dx*dx + dy*dy; 1619 if( dist < min_dist ) 1620 break; 1621 } 1622 if( j < 4 ) 1623 break; 1624 } 1625 1626 if( k < quad_count ) 1627 continue; 1628 1629 closest_corner->pt.x = (pt.x + closest_corner->pt.x) * 0.5f; 1630 closest_corner->pt.y = (pt.y + closest_corner->pt.y) * 0.5f; 1631 1632 // We've found one more corner - remember it 1633 cur_quad->count++; 1634 cur_quad->neighbors[i] = closest_quad; 1635 cur_quad->corners[i] = closest_corner; 1636 1637 closest_quad->count++; 1638 closest_quad->neighbors[closest_corner_idx] = cur_quad; 1639 } 1640 } 1641 } 1642 } 1643 1644 //===================================================================================== 1645 1646 // returns corners in clockwise order 1647 // corners don't necessarily start at same position on quad (e.g., 1648 // top left corner) 1649 1650 static int 1651 icvGenerateQuads( CvCBQuad **out_quads, CvCBCorner **out_corners, 1652 CvMemStorage *storage, CvMat *image, int flags ) 1653 { 1654 int quad_count = 0; 1655 cv::Ptr<CvMemStorage> temp_storage; 1656 1657 if( out_quads ) 1658 *out_quads = 0; 1659 1660 if( out_corners ) 1661 *out_corners = 0; 1662 1663 CvSeq *src_contour = 0; 1664 CvSeq *root; 1665 CvContourEx* board = 0; 1666 CvContourScanner scanner; 1667 int i, idx, min_size; 1668 1669 CV_Assert( out_corners && out_quads ); 1670 1671 // empiric bound for minimal allowed perimeter for squares 1672 min_size = 25; //cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 ); 1673 1674 // create temporary storage for contours and the sequence of pointers to found quadrangles 1675 temp_storage.reset(cvCreateChildMemStorage( storage )); 1676 root = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage ); 1677 1678 // initialize contour retrieving routine 1679 scanner = cvStartFindContours( image, temp_storage, sizeof(CvContourEx), 1680 CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE ); 1681 1682 // get all the contours one by one 1683 while( (src_contour = cvFindNextContour( scanner )) != 0 ) 1684 { 1685 CvSeq *dst_contour = 0; 1686 CvRect rect = ((CvContour*)src_contour)->rect; 1687 1688 // reject contours with too small perimeter 1689 if( CV_IS_SEQ_HOLE(src_contour) && rect.width*rect.height >= min_size ) 1690 { 1691 const int min_approx_level = 1, max_approx_level = MAX_CONTOUR_APPROX; 1692 int approx_level; 1693 for( approx_level = min_approx_level; approx_level <= max_approx_level; approx_level++ ) 1694 { 1695 dst_contour = cvApproxPoly( src_contour, sizeof(CvContour), temp_storage, 1696 CV_POLY_APPROX_DP, (float)approx_level ); 1697 if( dst_contour->total == 4 ) 1698 break; 1699 1700 // we call this again on its own output, because sometimes 1701 // cvApproxPoly() does not simplify as much as it should. 1702 dst_contour = cvApproxPoly( dst_contour, sizeof(CvContour), temp_storage, 1703 CV_POLY_APPROX_DP, (float)approx_level ); 1704 1705 if( dst_contour->total == 4 ) 1706 break; 1707 } 1708 1709 // reject non-quadrangles 1710 if( dst_contour->total == 4 && cvCheckContourConvexity(dst_contour) ) 1711 { 1712 CvPoint pt[4]; 1713 double d1, d2, p = cvContourPerimeter(dst_contour); 1714 double area = fabs(cvContourArea(dst_contour, CV_WHOLE_SEQ)); 1715 double dx, dy; 1716 1717 for( i = 0; i < 4; i++ ) 1718 pt[i] = *(CvPoint*)cvGetSeqElem(dst_contour, i); 1719 1720 dx = pt[0].x - pt[2].x; 1721 dy = pt[0].y - pt[2].y; 1722 d1 = sqrt(dx*dx + dy*dy); 1723 1724 dx = pt[1].x - pt[3].x; 1725 dy = pt[1].y - pt[3].y; 1726 d2 = sqrt(dx*dx + dy*dy); 1727 1728 // philipg. Only accept those quadrangles which are more square 1729 // than rectangular and which are big enough 1730 double d3, d4; 1731 dx = pt[0].x - pt[1].x; 1732 dy = pt[0].y - pt[1].y; 1733 d3 = sqrt(dx*dx + dy*dy); 1734 dx = pt[1].x - pt[2].x; 1735 dy = pt[1].y - pt[2].y; 1736 d4 = sqrt(dx*dx + dy*dy); 1737 if( !(flags & CV_CALIB_CB_FILTER_QUADS) || 1738 (d3*4 > d4 && d4*4 > d3 && d3*d4 < area*1.5 && area > min_size && 1739 d1 >= 0.15 * p && d2 >= 0.15 * p) ) 1740 { 1741 CvContourEx* parent = (CvContourEx*)(src_contour->v_prev); 1742 parent->counter++; 1743 if( !board || board->counter < parent->counter ) 1744 board = parent; 1745 dst_contour->v_prev = (CvSeq*)parent; 1746 //for( i = 0; i < 4; i++ ) cvLine( debug_img, pt[i], pt[(i+1)&3], cvScalar(200,255,255), 1, CV_AA, 0 ); 1747 cvSeqPush( root, &dst_contour ); 1748 } 1749 } 1750 } 1751 } 1752 1753 // finish contour retrieving 1754 cvEndFindContours( &scanner ); 1755 1756 // allocate quad & corner buffers 1757 *out_quads = (CvCBQuad*)cvAlloc((root->total+root->total / 2) * sizeof((*out_quads)[0])); 1758 *out_corners = (CvCBCorner*)cvAlloc((root->total+root->total / 2) * 4 * sizeof((*out_corners)[0])); 1759 1760 // Create array of quads structures 1761 for( idx = 0; idx < root->total; idx++ ) 1762 { 1763 CvCBQuad* q = &(*out_quads)[quad_count]; 1764 src_contour = *(CvSeq**)cvGetSeqElem( root, idx ); 1765 if( (flags & CV_CALIB_CB_FILTER_QUADS) && src_contour->v_prev != (CvSeq*)board ) 1766 continue; 1767 1768 // reset group ID 1769 memset( q, 0, sizeof(*q) ); 1770 q->group_idx = -1; 1771 assert( src_contour->total == 4 ); 1772 for( i = 0; i < 4; i++ ) 1773 { 1774 CvPoint2D32f pt = cvPointTo32f(*(CvPoint*)cvGetSeqElem(src_contour, i)); 1775 CvCBCorner* corner = &(*out_corners)[quad_count*4 + i]; 1776 1777 memset( corner, 0, sizeof(*corner) ); 1778 corner->pt = pt; 1779 q->corners[i] = corner; 1780 } 1781 q->edge_len = FLT_MAX; 1782 for( i = 0; i < 4; i++ ) 1783 { 1784 float dx = q->corners[i]->pt.x - q->corners[(i+1)&3]->pt.x; 1785 float dy = q->corners[i]->pt.y - q->corners[(i+1)&3]->pt.y; 1786 float d = dx*dx + dy*dy; 1787 if( q->edge_len > d ) 1788 q->edge_len = d; 1789 } 1790 quad_count++; 1791 } 1792 1793 return quad_count; 1794 } 1795 1796 1797 CV_IMPL void 1798 cvDrawChessboardCorners( CvArr* _image, CvSize pattern_size, 1799 CvPoint2D32f* corners, int count, int found ) 1800 { 1801 const int shift = 0; 1802 const int radius = 4; 1803 const int r = radius*(1 << shift); 1804 int i; 1805 CvMat stub, *image; 1806 double scale = 1; 1807 int type, cn, line_type; 1808 1809 image = cvGetMat( _image, &stub ); 1810 1811 type = CV_MAT_TYPE(image->type); 1812 cn = CV_MAT_CN(type); 1813 if( cn != 1 && cn != 3 && cn != 4 ) 1814 CV_Error( CV_StsUnsupportedFormat, "Number of channels must be 1, 3 or 4" ); 1815 1816 switch( CV_MAT_DEPTH(image->type) ) 1817 { 1818 case CV_8U: 1819 scale = 1; 1820 break; 1821 case CV_16U: 1822 scale = 256; 1823 break; 1824 case CV_32F: 1825 scale = 1./255; 1826 break; 1827 default: 1828 CV_Error( CV_StsUnsupportedFormat, 1829 "Only 8-bit, 16-bit or floating-point 32-bit images are supported" ); 1830 } 1831 1832 line_type = type == CV_8UC1 || type == CV_8UC3 ? CV_AA : 8; 1833 1834 if( !found ) 1835 { 1836 CvScalar color(0,0,255,0); 1837 if( cn == 1 ) 1838 color = cvScalarAll(200); 1839 color.val[0] *= scale; 1840 color.val[1] *= scale; 1841 color.val[2] *= scale; 1842 color.val[3] *= scale; 1843 1844 for( i = 0; i < count; i++ ) 1845 { 1846 CvPoint pt; 1847 pt.x = cvRound(corners[i].x*(1 << shift)); 1848 pt.y = cvRound(corners[i].y*(1 << shift)); 1849 cvLine( image, cvPoint( pt.x - r, pt.y - r ), 1850 cvPoint( pt.x + r, pt.y + r ), color, 1, line_type, shift ); 1851 cvLine( image, cvPoint( pt.x - r, pt.y + r), 1852 cvPoint( pt.x + r, pt.y - r), color, 1, line_type, shift ); 1853 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift ); 1854 } 1855 } 1856 else 1857 { 1858 int x, y; 1859 CvPoint prev_pt; 1860 const int line_max = 7; 1861 static const CvScalar line_colors[line_max] = 1862 { 1863 CvScalar(0,0,255), 1864 CvScalar(0,128,255), 1865 CvScalar(0,200,200), 1866 CvScalar(0,255,0), 1867 CvScalar(200,200,0), 1868 CvScalar(255,0,0), 1869 CvScalar(255,0,255) 1870 }; 1871 1872 for( y = 0, i = 0; y < pattern_size.height; y++ ) 1873 { 1874 CvScalar color = line_colors[y % line_max]; 1875 if( cn == 1 ) 1876 color = cvScalarAll(200); 1877 color.val[0] *= scale; 1878 color.val[1] *= scale; 1879 color.val[2] *= scale; 1880 color.val[3] *= scale; 1881 1882 for( x = 0; x < pattern_size.width; x++, i++ ) 1883 { 1884 CvPoint pt; 1885 pt.x = cvRound(corners[i].x*(1 << shift)); 1886 pt.y = cvRound(corners[i].y*(1 << shift)); 1887 1888 if( i != 0 ) 1889 cvLine( image, prev_pt, pt, color, 1, line_type, shift ); 1890 1891 cvLine( image, cvPoint(pt.x - r, pt.y - r), 1892 cvPoint(pt.x + r, pt.y + r), color, 1, line_type, shift ); 1893 cvLine( image, cvPoint(pt.x - r, pt.y + r), 1894 cvPoint(pt.x + r, pt.y - r), color, 1, line_type, shift ); 1895 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift ); 1896 prev_pt = pt; 1897 } 1898 } 1899 } 1900 } 1901 1902 bool cv::findChessboardCorners( InputArray _image, Size patternSize, 1903 OutputArray corners, int flags ) 1904 { 1905 int count = patternSize.area()*2; 1906 std::vector<Point2f> tmpcorners(count+1); 1907 Mat image = _image.getMat(); CvMat c_image = image; 1908 bool ok = cvFindChessboardCorners(&c_image, patternSize, 1909 (CvPoint2D32f*)&tmpcorners[0], &count, flags ) > 0; 1910 if( count > 0 ) 1911 { 1912 tmpcorners.resize(count); 1913 Mat(tmpcorners).copyTo(corners); 1914 } 1915 else 1916 corners.release(); 1917 return ok; 1918 } 1919 1920 namespace 1921 { 1922 int quiet_error(int /*status*/, const char* /*func_name*/, 1923 const char* /*err_msg*/, const char* /*file_name*/, 1924 int /*line*/, void* /*userdata*/ ) 1925 { 1926 return 0; 1927 } 1928 } 1929 1930 void cv::drawChessboardCorners( InputOutputArray _image, Size patternSize, 1931 InputArray _corners, 1932 bool patternWasFound ) 1933 { 1934 Mat corners = _corners.getMat(); 1935 if( corners.empty() ) 1936 return; 1937 Mat image = _image.getMat(); CvMat c_image = _image.getMat(); 1938 int nelems = corners.checkVector(2, CV_32F, true); 1939 CV_Assert(nelems >= 0); 1940 cvDrawChessboardCorners( &c_image, patternSize, corners.ptr<CvPoint2D32f>(), 1941 nelems, patternWasFound ); 1942 } 1943 1944 bool cv::findCirclesGrid( InputArray _image, Size patternSize, 1945 OutputArray _centers, int flags, const Ptr<FeatureDetector> &blobDetector ) 1946 { 1947 bool isAsymmetricGrid = (flags & CALIB_CB_ASYMMETRIC_GRID) ? true : false; 1948 bool isSymmetricGrid = (flags & CALIB_CB_SYMMETRIC_GRID ) ? true : false; 1949 CV_Assert(isAsymmetricGrid ^ isSymmetricGrid); 1950 1951 Mat image = _image.getMat(); 1952 std::vector<Point2f> centers; 1953 1954 std::vector<KeyPoint> keypoints; 1955 blobDetector->detect(image, keypoints); 1956 std::vector<Point2f> points; 1957 for (size_t i = 0; i < keypoints.size(); i++) 1958 { 1959 points.push_back (keypoints[i].pt); 1960 } 1961 1962 if(flags & CALIB_CB_CLUSTERING) 1963 { 1964 CirclesGridClusterFinder circlesGridClusterFinder(isAsymmetricGrid); 1965 circlesGridClusterFinder.findGrid(points, patternSize, centers); 1966 Mat(centers).copyTo(_centers); 1967 return !centers.empty(); 1968 } 1969 1970 CirclesGridFinderParameters parameters; 1971 parameters.vertexPenalty = -0.6f; 1972 parameters.vertexGain = 1; 1973 parameters.existingVertexGain = 10000; 1974 parameters.edgeGain = 1; 1975 parameters.edgePenalty = -0.6f; 1976 1977 if(flags & CALIB_CB_ASYMMETRIC_GRID) 1978 parameters.gridType = CirclesGridFinderParameters::ASYMMETRIC_GRID; 1979 if(flags & CALIB_CB_SYMMETRIC_GRID) 1980 parameters.gridType = CirclesGridFinderParameters::SYMMETRIC_GRID; 1981 1982 const int attempts = 2; 1983 const size_t minHomographyPoints = 4; 1984 Mat H; 1985 for (int i = 0; i < attempts; i++) 1986 { 1987 centers.clear(); 1988 CirclesGridFinder boxFinder(patternSize, points, parameters); 1989 bool isFound = false; 1990 #define BE_QUIET 1 1991 #if BE_QUIET 1992 void* oldCbkData; 1993 ErrorCallback oldCbk = redirectError(quiet_error, 0, &oldCbkData); 1994 #endif 1995 try 1996 { 1997 isFound = boxFinder.findHoles(); 1998 } 1999 catch (const cv::Exception &) 2000 { 2001 2002 } 2003 #if BE_QUIET 2004 redirectError(oldCbk, oldCbkData); 2005 #endif 2006 if (isFound) 2007 { 2008 switch(parameters.gridType) 2009 { 2010 case CirclesGridFinderParameters::SYMMETRIC_GRID: 2011 boxFinder.getHoles(centers); 2012 break; 2013 case CirclesGridFinderParameters::ASYMMETRIC_GRID: 2014 boxFinder.getAsymmetricHoles(centers); 2015 break; 2016 default: 2017 CV_Error(CV_StsBadArg, "Unkown pattern type"); 2018 } 2019 2020 if (i != 0) 2021 { 2022 Mat orgPointsMat; 2023 transform(centers, orgPointsMat, H.inv()); 2024 convertPointsFromHomogeneous(orgPointsMat, centers); 2025 } 2026 Mat(centers).copyTo(_centers); 2027 return true; 2028 } 2029 2030 boxFinder.getHoles(centers); 2031 if (i != attempts - 1) 2032 { 2033 if (centers.size() < minHomographyPoints) 2034 break; 2035 H = CirclesGridFinder::rectifyGrid(boxFinder.getDetectedGridSize(), centers, points, points); 2036 } 2037 } 2038 Mat(centers).copyTo(_centers); 2039 return false; 2040 } 2041 2042 /* End of file. */ 2043