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.
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 ===============================================================
49 The algorithms developed and implemented by Vezhnevets Vldimir
50 aka Dead Moroz (vvp@graphics.cs.msu.ru)
51 See http://graphics.cs.msu.su/en/research/calibration/opencv.html
52 for detailed information.
54 Reliability additions and modifications made by Philip Gruebele.
55 <a href="mailto:pgruebele@cox.net">pgruebele@cox.net</a>
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
60 \************************************************************************************/
62 /************************************************************************************\
63 This version adds a new and improved variant of chessboard corner detection
64 that works better in poor lighting condition. It is based on work from
65 Oliver Schreer and Stefano Masneri. This method works faster than the previous
66 one and reverts back to the older method in case no chessboard detection is
67 possible. Overall performance improves also because now the method avoids
68 performing the same computation multiple times when not necessary.
70 \************************************************************************************/
72 #include "precomp.hpp"
73 #include "opencv2/imgproc/imgproc_c.h"
74 #include "opencv2/calib3d/calib3d_c.h"
75 #include "circlesgrid.hpp"
82 //#define ENABLE_TRIM_COL_ROW
84 //#define DEBUG_CHESSBOARD
86 #ifdef DEBUG_CHESSBOARD
87 static int PRINTF( const char* fmt, ... )
91 return vprintf(fmt, args);
97 //=====================================================================================
98 // Implementation for the enhanced calibration object detection
99 //=====================================================================================
101 #define MAX_CONTOUR_APPROX 7
109 //=====================================================================================
111 /// Corner info structure
112 /** This structure stores information about the chessboard corner.*/
115 CvPoint2D32f pt; // Coordinates of the corner
116 int row; // Board row index
117 int count; // Number of neighbor corners
118 struct CvCBCorner* neighbors[4]; // Neighbor corners
120 float meanDist(int *_n) const
124 for( int i = 0; i < 4; i++ )
128 float dx = neighbors[i]->pt.x - pt.x;
129 float dy = neighbors[i]->pt.y - pt.y;
130 sum += sqrt(dx*dx + dy*dy);
140 //=====================================================================================
141 /// Quadrangle contour info structure
142 /** This structure stores information about the chessboard quadrange.*/
145 int count; // Number of quad neighbors
146 int group_idx; // quad group ID
147 int row, col; // row and column of this quad
148 bool ordered; // true if corners/neighbors are ordered counter-clockwise
149 float edge_len; // quad edge len, in pix^2
150 // neighbors and corners are synced, i.e., neighbor 0 shares corner 0
151 CvCBCorner *corners[4]; // Coordinates of quad corners
152 struct CvCBQuad *neighbors[4]; // Pointers of quad neighbors
155 //=====================================================================================
157 #ifdef DEBUG_CHESSBOARD
158 #include "opencv2/highgui.hpp"
159 #include "opencv2/imgproc.hpp"
160 static void SHOW(const std::string & name, Mat & img)
163 while ((uchar)waitKey(0) != 'q') {}
165 static void SHOW_QUADS(const std::string & name, const Mat & img_, CvCBQuad * quads, int quads_count)
167 Mat img = img_.clone();
168 if (img.channels() == 1)
169 cvtColor(img, img, COLOR_GRAY2BGR);
170 for (int i = 0; i < quads_count; ++i)
172 CvCBQuad & quad = quads[i];
173 for (int j = 0; j < 4; ++j)
175 line(img, quad.corners[j]->pt, quad.corners[(j + 1) % 4]->pt, Scalar(0, 240, 0), 1, LINE_AA);
179 while ((uchar)waitKey(0) != 'q') {}
183 #define SHOW_QUADS(...)
186 //=====================================================================================
188 static int icvGenerateQuads( CvCBQuad **quads, CvCBCorner **corners,
189 CvMemStorage *storage, const Mat &image_, int flags, int *max_quad_buf_size);
191 static bool processQuads(CvCBQuad *quads, int quad_count, CvSize pattern_size, int max_quad_buf_size,
192 CvMemStorage * storage, CvCBCorner *corners, CvPoint2D32f *out_corners, int *out_corner_count, int & prev_sqr_size);
195 icvGenerateQuadsEx( CvCBQuad **out_quads, CvCBCorner **out_corners,
196 CvMemStorage *storage, CvMat *image, CvMat *thresh_img, int dilation, int flags );*/
198 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count );
200 static int icvFindConnectedQuads( CvCBQuad *quads, int quad_count,
201 CvCBQuad **quad_group, int group_idx,
202 CvMemStorage* storage );
204 static int icvCheckQuadGroup( CvCBQuad **quad_group, int count,
205 CvCBCorner **out_corners, CvSize pattern_size );
207 static int icvCleanFoundConnectedQuads( int quad_count,
208 CvCBQuad **quads, CvSize pattern_size );
210 static int icvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads,
211 int *all_count, CvCBQuad **all_quads, CvCBCorner **corners,
212 CvSize pattern_size, int max_quad_buf_size, CvMemStorage* storage );
214 static void icvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common);
216 #ifdef ENABLE_TRIM_COL_ROW
217 static int icvTrimCol(CvCBQuad **quads, int count, int col, int dir);
219 static int icvTrimRow(CvCBQuad **quads, int count, int row, int dir);
222 static int icvAddOuterQuad(CvCBQuad *quad, CvCBQuad **quads, int quad_count,
223 CvCBQuad **all_quads, int all_count, CvCBCorner **corners, int max_quad_buf_size);
225 static void icvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0);
227 static int icvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size );
229 /***************************************************************************************************/
230 //COMPUTE INTENSITY HISTOGRAM OF INPUT IMAGE
231 static int icvGetIntensityHistogram( const Mat & img, std::vector<int>& piHist )
233 // sum up all pixel in row direction and divide by number of columns
234 for ( int j=0; j<img.rows; j++ )
236 const uchar * row = img.ptr(j);
237 for ( int i=0; i<img.cols; i++ )
244 /***************************************************************************************************/
245 //SMOOTH HISTOGRAM USING WINDOW OF SIZE 2*iWidth+1
246 static int icvSmoothHistogram( const std::vector<int>& piHist, std::vector<int>& piHistSmooth, int iWidth )
249 for ( int i=0; i<256; i++)
252 for ( int ii=-iWidth; ii<=iWidth; ii++)
255 if (iIdx > 0 && iIdx < 256)
257 iSmooth += piHist[iIdx];
260 piHistSmooth[i] = iSmooth/(2*iWidth+1);
264 /***************************************************************************************************/
265 //COMPUTE FAST HISTOGRAM GRADIENT
266 static int icvGradientOfHistogram( const std::vector<int>& piHist, std::vector<int>& piHistGrad )
269 for ( int i=1; i<255; i++)
271 piHistGrad[i] = piHist[i-1] - piHist[i+1];
272 if ( abs(piHistGrad[i]) < 100 )
274 if ( piHistGrad[i-1] == 0)
275 piHistGrad[i] = -100;
277 piHistGrad[i] = piHistGrad[i-1];
282 /***************************************************************************************************/
283 //PERFORM SMART IMAGE THRESHOLDING BASED ON ANALYSIS OF INTENSTY HISTOGRAM
284 static bool icvBinarizationHistogramBased( Mat & img )
286 CV_Assert(img.channels() == 1 && img.depth() == CV_8U);
287 int iCols = img.cols;
288 int iRows = img.rows;
289 int iMaxPix = iCols*iRows;
290 int iMaxPix1 = iMaxPix/100;
291 const int iNumBins = 256;
292 std::vector<int> piHistIntensity(iNumBins, 0);
293 std::vector<int> piHistSmooth(iNumBins, 0);
294 std::vector<int> piHistGrad(iNumBins, 0);
295 std::vector<int> piAccumSum(iNumBins, 0);
296 std::vector<int> piMaxPos(20, 0);
301 icvGetIntensityHistogram( img, piHistIntensity );
303 // get accumulated sum starting from bright
304 piAccumSum[iNumBins-1] = piHistIntensity[iNumBins-1];
305 for ( int i=iNumBins-2; i>=0; i-- )
307 piAccumSum[i] = piHistIntensity[i] + piAccumSum[i+1];
310 // first smooth the distribution
311 icvSmoothHistogram( piHistIntensity, piHistSmooth, iWidth );
314 icvGradientOfHistogram( piHistSmooth, piHistGrad );
318 for ( int i=iNumBins-2; (i>2) && (iCntMaxima<20); i--)
320 if ( (piHistGrad[i-1] < 0) && (piHistGrad[i] > 0) )
322 piMaxPos[iCntMaxima] = i;
328 int iSumAroundMax = 0;
329 for ( int i=0; i<iCntMaxima; i++ )
332 iSumAroundMax = piHistSmooth[iIdx-1] + piHistSmooth[iIdx] + piHistSmooth[iIdx+1];
333 if ( iSumAroundMax < iMaxPix1 && iIdx < 64 )
335 for ( int j=i; j<iCntMaxima-1; j++ )
337 piMaxPos[j] = piMaxPos[j+1];
343 if ( iCntMaxima == 1)
345 iThresh = piMaxPos[0]/2;
347 else if ( iCntMaxima == 2)
349 iThresh = (piMaxPos[0] + piMaxPos[1])/2;
351 else // iCntMaxima >= 3
353 // CHECKING THRESHOLD FOR WHITE
354 int iIdxAccSum = 0, iAccum = 0;
355 for (int i=iNumBins-1; i>0; i--)
357 iAccum += piHistIntensity[i];
358 // iMaxPix/18 is about 5,5%, minimum required number of pixels required for white part of chessboard
359 if ( iAccum > (iMaxPix/18) )
367 int iBrightMax = piMaxPos[0];
368 // printf("iBrightMax = %d\n", iBrightMax);
369 for ( int n=0; n<iCntMaxima-1; n++)
372 if ( piMaxPos[n] < iIdxAccSum )
376 iBrightMax = piMaxPos[n];
379 // CHECKING THRESHOLD FOR BLACK
380 int iMaxVal = piHistIntensity[piMaxPos[iIdxBGMax]];
382 //IF TOO CLOSE TO 255, jump to next maximum
383 if ( piMaxPos[iIdxBGMax] >= 250 && iIdxBGMax < iCntMaxima )
386 iMaxVal = piHistIntensity[piMaxPos[iIdxBGMax]];
389 for ( int n=iIdxBGMax + 1; n<iCntMaxima; n++)
391 if ( piHistIntensity[piMaxPos[n]] >= iMaxVal )
393 iMaxVal = piHistIntensity[piMaxPos[n]];
398 //SETTING THRESHOLD FOR BINARIZATION
399 int iDist2 = (iBrightMax - piMaxPos[iIdxBGMax])/2;
400 iThresh = iBrightMax - iDist2;
401 PRINTF("THRESHOLD SELECTED = %d, BRIGHTMAX = %d, DARKMAX = %d\n", iThresh, iBrightMax, piMaxPos[iIdxBGMax]);
407 for ( int jj=0; jj<iRows; jj++)
409 uchar * row = img.ptr(jj);
410 for ( int ii=0; ii<iCols; ii++)
412 if ( row[ii] < iThresh )
424 int cvFindChessboardCorners( const void* arr, CvSize pattern_size,
425 CvPoint2D32f* out_corners, int* out_corner_count,
430 CvCBCorner *corners = 0;
432 cv::Ptr<CvMemStorage> storage;
437 const int min_dilations = 0;
438 const int max_dilations = 7;
440 if( out_corner_count )
441 *out_corner_count = 0;
443 Mat img = cvarrToMat((CvMat*)arr).clone();
445 if( img.depth() != CV_8U || (img.channels() != 1 && img.channels() != 3 && img.channels() != 4) )
446 CV_Error( CV_StsUnsupportedFormat, "Only 8-bit grayscale or color images are supported" );
448 if( pattern_size.width <= 2 || pattern_size.height <= 2 )
449 CV_Error( CV_StsOutOfRange, "Both width and height of the pattern should have bigger than 2" );
452 CV_Error( CV_StsNullPtr, "Null pointer to corners" );
454 if (img.channels() != 1)
456 cvtColor(img, img, COLOR_BGR2GRAY);
460 Mat thresh_img_new = img.clone();
461 icvBinarizationHistogramBased( thresh_img_new ); // process image in-place
462 SHOW("New binarization", thresh_img_new);
464 if( flags & CV_CALIB_CB_FAST_CHECK)
466 //perform new method for checking chessboard using a binary image.
467 //image is binarised using a threshold dependent on the image histogram
468 if (checkChessboardBinary(thresh_img_new, pattern_size) <= 0) //fall back to the old method
470 if (checkChessboard(img, pattern_size) <= 0)
477 storage.reset(cvCreateMemStorage(0));
479 int prev_sqr_size = 0;
481 // Try our standard "1" dilation, but if the pattern is not found, iterate the whole procedure with higher dilations.
482 // This is necessary because some squares simply do not separate properly with a single dilation. However,
483 // we want to use the minimum number of dilations possible since dilations cause the squares to become smaller,
484 // making it difficult to detect smaller squares.
485 for( int dilations = min_dilations; dilations <= max_dilations; dilations++ )
488 break; // already found it
490 //USE BINARY IMAGE COMPUTED USING icvBinarizationHistogramBased METHOD
491 dilate( thresh_img_new, thresh_img_new, Mat(), Point(-1, -1), 1 );
493 // So we can find rectangles that go to the edge, we draw a white line around the image edge.
494 // Otherwise FindContours will miss those clipped rectangle contours.
495 // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()...
496 rectangle( thresh_img_new, Point(0,0), Point(thresh_img_new.cols-1, thresh_img_new.rows-1), Scalar(255,255,255), 3, LINE_8);
497 int max_quad_buf_size = 0;
500 int quad_count = icvGenerateQuads( &quads, &corners, storage, thresh_img_new, flags, &max_quad_buf_size );
501 PRINTF("Quad count: %d/%d\n", quad_count, (pattern_size.width/2+1)*(pattern_size.height/2+1));
502 SHOW_QUADS("New quads", thresh_img_new, quads, quad_count);
503 if (processQuads(quads, quad_count, pattern_size, max_quad_buf_size, storage, corners, out_corners, out_corner_count, prev_sqr_size))
507 PRINTF("Chessboard detection result 0: %d\n", found);
509 // revert to old, slower, method if detection failed
512 if( flags & CV_CALIB_CB_NORMALIZE_IMAGE )
514 equalizeHist( img, img );
520 PRINTF("Fallback to old algorithm\n");
521 const bool useAdaptive = flags & CV_CALIB_CB_ADAPTIVE_THRESH;
524 // empiric threshold level
525 // thresholding performed here and not inside the cycle to save processing time
526 double mean = cv::mean(img).val[0];
527 int thresh_level = MAX(cvRound( mean - 10 ), 10);
528 threshold( img, thresh_img, thresh_level, 255, THRESH_BINARY );
530 //if flag CV_CALIB_CB_ADAPTIVE_THRESH is not set it doesn't make sense to iterate over k
531 int max_k = useAdaptive ? 6 : 1;
532 for( k = 0; k < max_k; k++ )
534 for( int dilations = min_dilations; dilations <= max_dilations; dilations++ )
537 break; // already found it
539 // convert the input grayscale image to binary (black-n-white)
542 int block_size = cvRound(prev_sqr_size == 0
543 ? MIN(img.cols, img.rows) * (k % 2 == 0 ? 0.2 : 0.1)
544 : prev_sqr_size * 2);
545 block_size = block_size | 1;
547 adaptiveThreshold( img, thresh_img, 255, ADAPTIVE_THRESH_MEAN_C, THRESH_BINARY, block_size, (k/2)*5 );
549 dilate( thresh_img, thresh_img, Mat(), Point(-1, -1), dilations-1 );
554 dilate( thresh_img, thresh_img, Mat(), Point(-1, -1), 1 );
556 SHOW("Old binarization", thresh_img);
558 // So we can find rectangles that go to the edge, we draw a white line around the image edge.
559 // Otherwise FindContours will miss those clipped rectangle contours.
560 // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()...
561 rectangle( thresh_img, Point(0,0), Point(thresh_img.cols-1, thresh_img.rows-1), Scalar(255,255,255), 3, LINE_8);
562 int max_quad_buf_size = 0;
565 int quad_count = icvGenerateQuads( &quads, &corners, storage, thresh_img, flags, &max_quad_buf_size);
566 PRINTF("Quad count: %d/%d\n", quad_count, (pattern_size.width/2+1)*(pattern_size.height/2+1));
567 SHOW_QUADS("Old quads", thresh_img, quads, quad_count);
568 if (processQuads(quads, quad_count, pattern_size, max_quad_buf_size, storage, corners, out_corners, out_corner_count, prev_sqr_size))
574 PRINTF("Chessboard detection result 1: %d\n", found);
577 found = icvCheckBoardMonotony( out_corners, pattern_size );
579 PRINTF("Chessboard detection result 2: %d\n", found);
581 // check that none of the found corners is too close to the image boundary
584 const int BORDER = 8;
585 for( k = 0; k < pattern_size.width*pattern_size.height; k++ )
587 if( out_corners[k].x <= BORDER || out_corners[k].x > img.cols - BORDER ||
588 out_corners[k].y <= BORDER || out_corners[k].y > img.rows - BORDER )
592 found = k == pattern_size.width*pattern_size.height;
595 PRINTF("Chessboard detection result 3: %d\n", found);
599 if ( pattern_size.height % 2 == 0 && pattern_size.width % 2 == 0 )
601 int last_row = (pattern_size.height-1)*pattern_size.width;
602 double dy0 = out_corners[last_row].y - out_corners[0].y;
605 int n = pattern_size.width*pattern_size.height;
606 for(int i = 0; i < n/2; i++ )
609 CV_SWAP(out_corners[i], out_corners[n-i-1], temp);
615 cvFindCornerSubPix( &old_img, out_corners, pattern_size.width*pattern_size.height,
616 cvSize(wsize, wsize), cvSize(-1,-1),
617 cvTermCriteria(CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 15, 0.1));
632 // Checks that each board row and column is pretty much monotonous curve:
633 // It analyzes each row and each column of the chessboard as following:
634 // for each corner c lying between end points in the same row/column it checks that
635 // the point projection to the line segment (a,b) is lying between projections
636 // of the neighbor corners in the same row/column.
638 // This function has been created as temporary workaround for the bug in current implementation
639 // of cvFindChessboardCornes that produces absolutely unordered sets of corners.
643 icvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size )
647 for( k = 0; k < 2; k++ )
649 for( i = 0; i < (k == 0 ? pattern_size.height : pattern_size.width); i++ )
651 CvPoint2D32f a = k == 0 ? corners[i*pattern_size.width] : corners[i];
652 CvPoint2D32f b = k == 0 ? corners[(i+1)*pattern_size.width-1] :
653 corners[(pattern_size.height-1)*pattern_size.width + i];
654 float prevt = 0, dx0 = b.x - a.x, dy0 = b.y - a.y;
655 if( fabs(dx0) + fabs(dy0) < FLT_EPSILON )
657 for( j = 1; j < (k == 0 ? pattern_size.width : pattern_size.height) - 1; j++ )
659 CvPoint2D32f c = k == 0 ? corners[i*pattern_size.width + j] :
660 corners[j*pattern_size.width + i];
661 float t = ((c.x - a.x)*dx0 + (c.y - a.y)*dy0)/(dx0*dx0 + dy0*dy0);
662 if( t < prevt || t > 1 )
673 // order a group of connected quads
676 // clockwise from there
677 // note: "top left" is nominal, depends on initial ordering of starting quad
678 // but all other quads are ordered consistently
680 // can change the number of quads in the group
681 // can add quads, so we need to have quad/corner arrays passed in
685 icvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads,
686 int *all_count, CvCBQuad **all_quads, CvCBCorner **corners,
687 CvSize pattern_size, int max_quad_buf_size, CvMemStorage* storage )
689 cv::Ptr<CvMemStorage> temp_storage(cvCreateChildMemStorage( storage ));
690 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage );
692 // first find an interior quad
693 CvCBQuad *start = NULL;
694 for (int i=0; i<quad_count; i++)
696 if (quads[i]->count == 4)
704 return 0; // no 4-connected quad
706 // start with first one, assign rows/cols
707 int row_min = 0, col_min = 0, row_max=0, col_max = 0;
709 std::map<int, int> col_hist;
710 std::map<int, int> row_hist;
712 cvSeqPush(stack, &start);
715 start->ordered = true;
717 // Recursively order the quads so that all position numbers (e.g.,
718 // 0,1,2,3) are in the at the same relative corner (e.g., lower right).
720 while( stack->total )
723 cvSeqPop( stack, &q );
730 if (row > row_max) row_max = row;
731 if (row < row_min) row_min = row;
732 if (col > col_max) col_max = col;
733 if (col < col_min) col_min = col;
735 for(int i = 0; i < 4; i++ )
737 CvCBQuad *neighbor = q->neighbors[i];
738 switch(i) // adjust col, row for this quad
739 { // start at top left, go clockwise
750 // just do inside quads
751 if (neighbor && neighbor->ordered == false && neighbor->count == 4)
753 PRINTF("col: %d row: %d\n", col, row);
754 icvOrderQuad(neighbor, q->corners[i], (i+2)%4); // set in order
755 neighbor->ordered = true;
758 cvSeqPush( stack, &neighbor );
763 for (int i=col_min; i<=col_max; i++)
764 PRINTF("HIST[%d] = %d\n", i, col_hist[i]);
766 // analyze inner quad structure
767 int w = pattern_size.width - 1;
768 int h = pattern_size.height - 1;
769 int drow = row_max - row_min + 1;
770 int dcol = col_max - col_min + 1;
772 // normalize pattern and found quad indices
773 if ((w > h && dcol < drow) ||
774 (w < h && drow < dcol))
776 h = pattern_size.width - 1;
777 w = pattern_size.height - 1;
780 PRINTF("Size: %dx%d Pattern: %dx%d\n", dcol, drow, w, h);
782 // check if there are enough inner quads
783 if (dcol < w || drow < h) // found enough inner quads?
785 PRINTF("Too few inner quad rows/cols\n");
786 return 0; // no, return
788 #ifdef ENABLE_TRIM_COL_ROW
789 // too many columns, not very common
790 if (dcol == w+1) // too many, trim
792 PRINTF("Trimming cols\n");
793 if (col_hist[col_max] > col_hist[col_min])
795 PRINTF("Trimming left col\n");
796 quad_count = icvTrimCol(quads,quad_count,col_min,-1);
800 PRINTF("Trimming right col\n");
801 quad_count = icvTrimCol(quads,quad_count,col_max,+1);
805 // too many rows, not very common
806 if (drow == h+1) // too many, trim
808 PRINTF("Trimming rows\n");
809 if (row_hist[row_max] > row_hist[row_min])
811 PRINTF("Trimming top row\n");
812 quad_count = icvTrimRow(quads,quad_count,row_min,-1);
816 PRINTF("Trimming bottom row\n");
817 quad_count = icvTrimRow(quads,quad_count,row_max,+1);
822 // check edges of inner quads
823 // if there is an outer quad missing, fill it in
824 // first order all inner quads
826 for (int i=0; i<quad_count; i++)
828 if (quads[i]->count == 4)
829 { // ok, look at neighbors
830 int col = quads[i]->col;
831 int row = quads[i]->row;
832 for (int j=0; j<4; j++)
834 switch(j) // adjust col, row for this quad
835 { // start at top left, go clockwise
845 CvCBQuad *neighbor = quads[i]->neighbors[j];
846 if (neighbor && !neighbor->ordered && // is it an inner quad?
847 col <= col_max && col >= col_min &&
848 row <= row_max && row >= row_min)
850 // if so, set in order
851 PRINTF("Adding inner: col: %d row: %d\n", col, row);
853 icvOrderQuad(neighbor, quads[i]->corners[j], (j+2)%4);
854 neighbor->ordered = true;
862 // if we have found inner quads, add corresponding outer quads,
866 PRINTF("Found %d inner quads not connected to outer quads, repairing\n", found);
867 for (int i=0; i<quad_count && *all_count < max_quad_buf_size; i++)
869 if (quads[i]->count < 4 && quads[i]->ordered)
871 int added = icvAddOuterQuad(quads[i],quads,quad_count,all_quads,*all_count,corners, max_quad_buf_size);
877 if (*all_count >= max_quad_buf_size)
882 // final trimming of outer quads
883 if (dcol == w && drow == h) // found correct inner quads
885 PRINTF("Inner bounds ok, check outer quads\n");
886 int rcount = quad_count;
887 for (int i=quad_count-1; i>=0; i--) // eliminate any quad not connected to
890 if (quads[i]->ordered == false)
893 for (int j=0; j<4; j++) // any neighbors that are ordered?
895 if (quads[i]->neighbors[j] && quads[i]->neighbors[j]->ordered)
898 if (!outer) // not an outer quad, eliminate
900 PRINTF("Removing quad %d\n", i);
901 icvRemoveQuadFromGroup(quads,rcount,quads[i]);
915 // looks for the neighbor of <quad> that isn't present,
916 // tries to add it in.
920 icvAddOuterQuad( CvCBQuad *quad, CvCBQuad **quads, int quad_count,
921 CvCBQuad **all_quads, int all_count, CvCBCorner **corners, int max_quad_buf_size )
925 for (int i=0; i<4 && all_count < max_quad_buf_size; i++) // find no-neighbor corners
927 if (!quad->neighbors[i]) // ok, create and add neighbor
930 PRINTF("Adding quad as neighbor 2\n");
931 CvCBQuad *q = &(*all_quads)[all_count];
932 memset( q, 0, sizeof(*q) );
934 quads[quad_count] = q;
937 // set neighbor and group id
938 quad->neighbors[i] = q;
940 q->neighbors[j] = quad;
941 q->group_idx = quad->group_idx;
942 q->count = 1; // number of neighbors
944 q->edge_len = quad->edge_len;
946 // make corners of new quad
947 // same as neighbor quad, but offset
948 CvPoint2D32f pt = quad->corners[i]->pt;
950 float dx = pt.x - quad->corners[j]->pt.x;
951 float dy = pt.y - quad->corners[j]->pt.y;
952 for (int k=0; k<4; k++)
954 corner = &(*corners)[all_count*4+k];
955 pt = quad->corners[k]->pt;
956 memset( corner, 0, sizeof(*corner) );
958 q->corners[k] = corner;
962 // have to set exact corner
963 q->corners[j] = quad->corners[i];
965 // now find other neighbor and add it, if possible
966 if (quad->neighbors[(i+3)%4] &&
967 quad->neighbors[(i+3)%4]->ordered &&
968 quad->neighbors[(i+3)%4]->neighbors[i] &&
969 quad->neighbors[(i+3)%4]->neighbors[i]->ordered )
971 CvCBQuad *qn = quad->neighbors[(i+3)%4]->neighbors[i];
973 q->neighbors[(j+1)%4] = qn;
974 qn->neighbors[(i+1)%4] = q;
976 // have to set exact corner
977 q->corners[(j+1)%4] = qn->corners[(i+1)%4];
988 #ifdef ENABLE_TRIM_COL_ROW
990 icvTrimCol(CvCBQuad **quads, int count, int col, int dir)
993 // find the right quad(s)
994 for (int i=0; i<count; i++)
996 #ifdef DEBUG_CHESSBOARD
997 if (quads[i]->ordered)
998 PRINTF("index: %d cur: %d\n", col, quads[i]->col);
1000 if (quads[i]->ordered && quads[i]->col == col)
1004 if (quads[i]->neighbors[1])
1006 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]);
1009 if (quads[i]->neighbors[2])
1011 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]);
1017 if (quads[i]->neighbors[0])
1019 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]);
1022 if (quads[i]->neighbors[3])
1024 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]);
1035 icvTrimRow(CvCBQuad **quads, int count, int row, int dir)
1037 int i, rcount = count;
1038 // find the right quad(s)
1039 for (i=0; i<count; i++)
1041 #ifdef DEBUG_CHESSBOARD
1042 if (quads[i]->ordered)
1043 PRINTF("index: %d cur: %d\n", row, quads[i]->row);
1045 if (quads[i]->ordered && quads[i]->row == row)
1047 if (dir == 1) // remove from bottom
1049 if (quads[i]->neighbors[2])
1051 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]);
1054 if (quads[i]->neighbors[3])
1056 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]);
1060 else // remove from top
1062 if (quads[i]->neighbors[0])
1064 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]);
1067 if (quads[i]->neighbors[1])
1069 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]);
1081 // remove quad from quad group
1085 icvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0)
1088 // remove any references to this quad as a neighbor
1089 for(i = 0; i < count; i++ )
1091 CvCBQuad *q = quads[i];
1092 for(j = 0; j < 4; j++ )
1094 if( q->neighbors[j] == q0 )
1096 q->neighbors[j] = 0;
1098 for(int k = 0; k < 4; k++ )
1099 if( q0->neighbors[k] == q )
1101 q0->neighbors[k] = 0;
1111 for(i = 0; i < count; i++ )
1113 CvCBQuad *q = quads[i];
1116 quads[i] = quads[count-1];
1123 // put quad into correct order, where <corner> has value <common>
1127 icvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common)
1131 for (tc=0; tc<4; tc++)
1132 if (quad->corners[tc]->pt.x == corner->pt.x &&
1133 quad->corners[tc]->pt.y == corner->pt.y)
1138 while (tc != common)
1143 tempc = quad->corners[3];
1144 tempq = quad->neighbors[3];
1145 for (int i=3; i>0; i--)
1147 quad->corners[i] = quad->corners[i-1];
1148 quad->neighbors[i] = quad->neighbors[i-1];
1150 quad->corners[0] = tempc;
1151 quad->neighbors[0] = tempq;
1158 // if we found too many connect quads, remove those which probably do not belong.
1160 icvCleanFoundConnectedQuads( int quad_count, CvCBQuad **quad_group, CvSize pattern_size )
1162 CvPoint2D32f center;
1164 // number of quads this pattern should contain
1165 int count = ((pattern_size.width + 1)*(pattern_size.height + 1) + 1)/2;
1167 // if we have more quadrangles than we should,
1168 // try to eliminate duplicates or ones which don't belong to the pattern rectangle...
1169 if( quad_count <= count )
1172 // create an array of quadrangle centers
1173 cv::AutoBuffer<CvPoint2D32f> centers( quad_count );
1174 cv::Ptr<CvMemStorage> temp_storage(cvCreateMemStorage(0));
1176 for( i = 0; i < quad_count; i++ )
1179 CvCBQuad* q = quad_group[i];
1181 for( j = 0; j < 4; j++ )
1183 CvPoint2D32f pt = q->corners[j]->pt;
1195 center.x /= quad_count;
1196 center.y /= quad_count;
1198 // If we still have more quadrangles than we should,
1199 // we try to eliminate bad ones based on minimizing the bounding box.
1200 // We iteratively remove the point which reduces the size of
1201 // the bounding box of the blobs the most
1202 // (since we want the rectangle to be as small as possible)
1203 // remove the quadrange that causes the biggest reduction
1204 // in pattern size until we have the correct number
1205 for( ; quad_count > count; quad_count-- )
1207 double min_box_area = DBL_MAX;
1208 int skip, min_box_area_index = -1;
1210 // For each point, calculate box area without that point
1211 for( skip = 0; skip < quad_count; skip++ )
1213 // get bounding rectangle
1214 CvPoint2D32f temp = centers[skip]; // temporarily make index 'skip' the same as
1215 centers[skip] = center; // pattern center (so it is not counted for convex hull)
1216 CvMat pointMat = cvMat(1, quad_count, CV_32FC2, centers);
1217 CvSeq *hull = cvConvexHull2( &pointMat, temp_storage, CV_CLOCKWISE, 1 );
1218 centers[skip] = temp;
1219 double hull_area = fabs(cvContourArea(hull, CV_WHOLE_SEQ));
1221 // remember smallest box area
1222 if( hull_area < min_box_area )
1224 min_box_area = hull_area;
1225 min_box_area_index = skip;
1227 cvClearMemStorage( temp_storage );
1230 CvCBQuad *q0 = quad_group[min_box_area_index];
1232 // remove any references to this quad as a neighbor
1233 for( i = 0; i < quad_count; i++ )
1235 CvCBQuad *q = quad_group[i];
1236 for( j = 0; j < 4; j++ )
1238 if( q->neighbors[j] == q0 )
1240 q->neighbors[j] = 0;
1242 for( k = 0; k < 4; k++ )
1243 if( q0->neighbors[k] == q )
1245 q0->neighbors[k] = 0;
1256 quad_group[min_box_area_index] = quad_group[quad_count];
1257 centers[min_box_area_index] = centers[quad_count];
1263 //=====================================================================================
1266 icvFindConnectedQuads( CvCBQuad *quad, int quad_count, CvCBQuad **out_group,
1267 int group_idx, CvMemStorage* storage )
1269 cv::Ptr<CvMemStorage> temp_storage(cvCreateChildMemStorage( storage ));
1270 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage );
1273 // Scan the array for a first unlabeled quad
1274 for( i = 0; i < quad_count; i++ )
1276 if( quad[i].count > 0 && quad[i].group_idx < 0)
1280 // Recursively find a group of connected quads starting from the seed quad[i]
1281 if( i < quad_count )
1283 CvCBQuad* q = &quad[i];
1284 cvSeqPush( stack, &q );
1285 out_group[count++] = q;
1286 q->group_idx = group_idx;
1289 while( stack->total )
1291 cvSeqPop( stack, &q );
1292 for( i = 0; i < 4; i++ )
1294 CvCBQuad *neighbor = q->neighbors[i];
1295 if( neighbor && neighbor->count > 0 && neighbor->group_idx < 0 )
1297 cvSeqPush( stack, &neighbor );
1298 out_group[count++] = neighbor;
1299 neighbor->group_idx = group_idx;
1300 neighbor->ordered = false;
1310 //=====================================================================================
1313 icvCheckQuadGroup( CvCBQuad **quad_group, int quad_count,
1314 CvCBCorner **out_corners, CvSize pattern_size )
1316 const int ROW1 = 1000000;
1317 const int ROW2 = 2000000;
1318 const int ROW_ = 3000000;
1320 int i, out_corner_count = 0, corner_count = 0;
1321 std::vector<CvCBCorner*> corners(quad_count*4);
1324 int width = 0, height = 0;
1325 int hist[5] = {0,0,0,0,0};
1326 CvCBCorner* first = 0, *first2 = 0, *right, *cur, *below, *c;
1328 // build dual graph, which vertices are internal quad corners
1329 // and two vertices are connected iff they lie on the same quad edge
1330 for( i = 0; i < quad_count; i++ )
1332 CvCBQuad* q = quad_group[i];
1333 /*CvScalar color = q->count == 0 ? cvScalar(0,255,255) :
1334 q->count == 1 ? cvScalar(0,0,255) :
1335 q->count == 2 ? cvScalar(0,255,0) :
1336 q->count == 3 ? cvScalar(255,255,0) :
1337 cvScalar(255,0,0);*/
1339 for( j = 0; j < 4; j++ )
1341 //cvLine( debug_img, cvPointFrom32f(q->corners[j]->pt), cvPointFrom32f(q->corners[(j+1)&3]->pt), color, 1, CV_AA, 0 );
1342 if( q->neighbors[j] )
1344 CvCBCorner *a = q->corners[j], *b = q->corners[(j+1)&3];
1345 // mark internal corners that belong to:
1346 // - a quad with a single neighbor - with ROW1,
1347 // - a quad with two neighbors - with ROW2
1348 // make the rest of internal corners with ROW_
1349 int row_flag = q->count == 1 ? ROW1 : q->count == 2 ? ROW2 : ROW_;
1353 corners[corner_count++] = a;
1356 else if( a->row > row_flag )
1359 if( q->neighbors[(j+1)&3] )
1361 if( a->count >= 4 || b->count >= 4 )
1363 for( k = 0; k < 4; k++ )
1365 if( a->neighbors[k] == b )
1367 if( b->neighbors[k] == a )
1370 a->neighbors[a->count++] = b;
1371 b->neighbors[b->count++] = a;
1377 if( corner_count != pattern_size.width*pattern_size.height )
1380 for( i = 0; i < corner_count; i++ )
1382 int n = corners[i]->count;
1383 assert( 0 <= n && n <= 4 );
1385 if( !first && n == 2 )
1387 if( corners[i]->row == ROW1 )
1389 else if( !first2 && corners[i]->row == ROW2 )
1390 first2 = corners[i];
1394 // start with a corner that belongs to a quad with a single neighbor.
1395 // if we do not have such, start with a corner of a quad with two neighbors.
1399 if( !first || hist[0] != 0 || hist[1] != 0 || hist[2] != 4 ||
1400 hist[3] != (pattern_size.width + pattern_size.height)*2 - 8 )
1405 out_corners[out_corner_count++] = cur;
1407 for( k = 0; k < 4; k++ )
1409 c = cur->neighbors[k];
1419 if( !right || (right->count != 2 && right->count != 3) ||
1420 !below || (below->count != 2 && below->count != 3) )
1424 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,255,0), -1, 8, 0 );
1426 first = below; // remember the first corner in the next row
1427 // find and store the first row (or column)
1431 out_corners[out_corner_count++] = right;
1432 //cvCircle( debug_img, cvPointFrom32f(right->pt), 3, cvScalar(0,255-j*10,0), -1, 8, 0 );
1433 if( right->count == 2 )
1435 if( right->count != 3 || out_corner_count >= MAX(pattern_size.width,pattern_size.height) )
1438 for( k = 0; k < 4; k++ )
1440 c = cur->neighbors[k];
1441 if( c && c->row > 0 )
1443 for( kk = 0; kk < 4; kk++ )
1445 if( c->neighbors[kk] == below )
1456 width = out_corner_count;
1457 if( width == pattern_size.width )
1458 height = pattern_size.height;
1459 else if( width == pattern_size.height )
1460 height = pattern_size.width;
1464 // find and store all the other rows
1474 out_corners[out_corner_count++] = cur;
1475 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,0,255-j*10), -1, 8, 0 );
1476 if( cur->count == 2 + (i < height-1) && j > 0 )
1481 // find a neighbor that has not been processed yet
1482 // and that has a neighbor from the previous row
1483 for( k = 0; k < 4; k++ )
1485 c = cur->neighbors[k];
1486 if( c && c->row > i )
1488 for( kk = 0; kk < 4; kk++ )
1490 if( c->neighbors[kk] && c->neighbors[kk]->row == i-1 )
1508 if( j != width - 1 )
1512 if( out_corner_count != corner_count )
1515 // check if we need to transpose the board
1516 if( width != pattern_size.width )
1518 CV_SWAP( width, height, k );
1520 memcpy( &corners[0], out_corners, corner_count*sizeof(corners[0]) );
1521 for( i = 0; i < height; i++ )
1522 for( j = 0; j < width; j++ )
1523 out_corners[i*width + j] = corners[j*height + i];
1526 // check if we need to revert the order in each row
1528 CvPoint2D32f p0 = out_corners[0]->pt, p1 = out_corners[pattern_size.width-1]->pt,
1529 p2 = out_corners[pattern_size.width]->pt;
1530 if( (p1.x - p0.x)*(p2.y - p1.y) - (p1.y - p0.y)*(p2.x - p1.x) < 0 )
1532 if( width % 2 == 0 )
1534 for( i = 0; i < height; i++ )
1535 for( j = 0; j < width/2; j++ )
1536 CV_SWAP( out_corners[i*width+j], out_corners[i*width+width-j-1], c );
1540 for( j = 0; j < width; j++ )
1541 for( i = 0; i < height/2; i++ )
1542 CV_SWAP( out_corners[i*width+j], out_corners[(height - i - 1)*width+j], c );
1547 result = corner_count;
1553 corner_count = MIN( corner_count, pattern_size.width*pattern_size.height );
1554 for( i = 0; i < corner_count; i++ )
1555 out_corners[i] = corners[i];
1556 result = -corner_count;
1558 if (result == -pattern_size.width*pattern_size.height)
1568 //=====================================================================================
1570 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count )
1572 const float thresh_scale = 1.f;
1576 // find quad neighbors
1577 for( idx = 0; idx < quad_count; idx++ )
1579 CvCBQuad* cur_quad = &quads[idx];
1581 // choose the points of the current quadrangle that are close to
1582 // some points of the other quadrangles
1583 // (it can happen for split corners (due to dilation) of the
1584 // checker board). Search only in other quadrangles!
1586 // for each corner of this quadrangle
1587 for( i = 0; i < 4; i++ )
1590 float min_dist = FLT_MAX;
1591 int closest_corner_idx = -1;
1592 CvCBQuad *closest_quad = 0;
1593 CvCBCorner *closest_corner = 0;
1595 if( cur_quad->neighbors[i] )
1598 pt = cur_quad->corners[i]->pt;
1600 // find the closest corner in all other quadrangles
1601 for( k = 0; k < quad_count; k++ )
1606 for( j = 0; j < 4; j++ )
1608 if( quads[k].neighbors[j] )
1611 dx = pt.x - quads[k].corners[j]->pt.x;
1612 dy = pt.y - quads[k].corners[j]->pt.y;
1613 dist = dx * dx + dy * dy;
1615 if( dist < min_dist &&
1616 dist <= cur_quad->edge_len*thresh_scale &&
1617 dist <= quads[k].edge_len*thresh_scale )
1619 // check edge lengths, make sure they're compatible
1620 // edges that are different by more than 1:4 are rejected
1621 float ediff = cur_quad->edge_len - quads[k].edge_len;
1622 if (ediff > 32*cur_quad->edge_len ||
1623 ediff > 32*quads[k].edge_len)
1625 PRINTF("Incompatible edge lengths\n");
1628 closest_corner_idx = j;
1629 closest_quad = &quads[k];
1635 // we found a matching corner point?
1636 if( closest_corner_idx >= 0 && min_dist < FLT_MAX )
1638 // If another point from our current quad is closer to the found corner
1639 // than the current one, then we don't count this one after all.
1640 // This is necessary to support small squares where otherwise the wrong
1641 // corner will get matched to closest_quad;
1642 closest_corner = closest_quad->corners[closest_corner_idx];
1644 for( j = 0; j < 4; j++ )
1646 if( cur_quad->neighbors[j] == closest_quad )
1649 dx = closest_corner->pt.x - cur_quad->corners[j]->pt.x;
1650 dy = closest_corner->pt.y - cur_quad->corners[j]->pt.y;
1652 if( dx * dx + dy * dy < min_dist )
1656 if( j < 4 || cur_quad->count >= 4 || closest_quad->count >= 4 )
1659 // Check that each corner is a neighbor of different quads
1660 for( j = 0; j < closest_quad->count; j++ )
1662 if( closest_quad->neighbors[j] == cur_quad )
1665 if( j < closest_quad->count )
1668 // check whether the closest corner to closest_corner
1669 // is different from cur_quad->corners[i]->pt
1670 for( k = 0; k < quad_count; k++ )
1672 CvCBQuad* q = &quads[k];
1673 if( k == idx || q == closest_quad )
1676 for( j = 0; j < 4; j++ )
1677 if( !q->neighbors[j] )
1679 dx = closest_corner->pt.x - q->corners[j]->pt.x;
1680 dy = closest_corner->pt.y - q->corners[j]->pt.y;
1681 dist = dx*dx + dy*dy;
1682 if( dist < min_dist )
1689 if( k < quad_count )
1692 closest_corner->pt.x = (pt.x + closest_corner->pt.x) * 0.5f;
1693 closest_corner->pt.y = (pt.y + closest_corner->pt.y) * 0.5f;
1695 // We've found one more corner - remember it
1697 cur_quad->neighbors[i] = closest_quad;
1698 cur_quad->corners[i] = closest_corner;
1700 closest_quad->count++;
1701 closest_quad->neighbors[closest_corner_idx] = cur_quad;
1707 //=====================================================================================
1709 // returns corners in clockwise order
1710 // corners don't necessarily start at same position on quad (e.g.,
1714 icvGenerateQuads( CvCBQuad **out_quads, CvCBCorner **out_corners,
1715 CvMemStorage *storage, const cv::Mat & image_, int flags, int *max_quad_buf_size )
1717 CvMat image_old(image_), *image = &image_old;
1719 cv::Ptr<CvMemStorage> temp_storage;
1727 CvSeq *src_contour = 0;
1729 CvContourEx* board = 0;
1730 CvContourScanner scanner;
1731 int i, idx, min_size;
1733 CV_Assert( out_corners && out_quads );
1735 // empiric bound for minimal allowed perimeter for squares
1736 min_size = 25; //cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 );
1738 // create temporary storage for contours and the sequence of pointers to found quadrangles
1739 temp_storage.reset(cvCreateChildMemStorage( storage ));
1740 root = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage );
1742 // initialize contour retrieving routine
1743 scanner = cvStartFindContours( image, temp_storage, sizeof(CvContourEx),
1744 CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE );
1746 // get all the contours one by one
1747 while( (src_contour = cvFindNextContour( scanner )) != 0 )
1749 CvSeq *dst_contour = 0;
1750 CvRect rect = ((CvContour*)src_contour)->rect;
1752 // reject contours with too small perimeter
1753 if( CV_IS_SEQ_HOLE(src_contour) && rect.width*rect.height >= min_size )
1755 const int min_approx_level = 1, max_approx_level = MAX_CONTOUR_APPROX;
1757 for( approx_level = min_approx_level; approx_level <= max_approx_level; approx_level++ )
1759 dst_contour = cvApproxPoly( src_contour, sizeof(CvContour), temp_storage,
1760 CV_POLY_APPROX_DP, (float)approx_level );
1761 if( dst_contour->total == 4 )
1764 // we call this again on its own output, because sometimes
1765 // cvApproxPoly() does not simplify as much as it should.
1766 dst_contour = cvApproxPoly( dst_contour, sizeof(CvContour), temp_storage,
1767 CV_POLY_APPROX_DP, (float)approx_level );
1769 if( dst_contour->total == 4 )
1773 // reject non-quadrangles
1774 if( dst_contour->total == 4 && cvCheckContourConvexity(dst_contour) )
1777 double d1, d2, p = cvContourPerimeter(dst_contour);
1778 double area = fabs(cvContourArea(dst_contour, CV_WHOLE_SEQ));
1781 for( i = 0; i < 4; i++ )
1782 pt[i] = *(CvPoint*)cvGetSeqElem(dst_contour, i);
1784 dx = pt[0].x - pt[2].x;
1785 dy = pt[0].y - pt[2].y;
1786 d1 = sqrt(dx*dx + dy*dy);
1788 dx = pt[1].x - pt[3].x;
1789 dy = pt[1].y - pt[3].y;
1790 d2 = sqrt(dx*dx + dy*dy);
1792 // philipg. Only accept those quadrangles which are more square
1793 // than rectangular and which are big enough
1795 dx = pt[0].x - pt[1].x;
1796 dy = pt[0].y - pt[1].y;
1797 d3 = sqrt(dx*dx + dy*dy);
1798 dx = pt[1].x - pt[2].x;
1799 dy = pt[1].y - pt[2].y;
1800 d4 = sqrt(dx*dx + dy*dy);
1801 if( !(flags & CV_CALIB_CB_FILTER_QUADS) ||
1802 (d3*4 > d4 && d4*4 > d3 && d3*d4 < area*1.5 && area > min_size &&
1803 d1 >= 0.15 * p && d2 >= 0.15 * p) )
1805 CvContourEx* parent = (CvContourEx*)(src_contour->v_prev);
1807 if( !board || board->counter < parent->counter )
1809 dst_contour->v_prev = (CvSeq*)parent;
1810 //for( i = 0; i < 4; i++ ) cvLine( debug_img, pt[i], pt[(i+1)&3], cvScalar(200,255,255), 1, CV_AA, 0 );
1811 cvSeqPush( root, &dst_contour );
1817 // finish contour retrieving
1818 cvEndFindContours( &scanner );
1820 // allocate quad & corner buffers
1821 *max_quad_buf_size = MAX(1, (root->total+root->total / 2)) * 2;
1822 *out_quads = (CvCBQuad*)cvAlloc(*max_quad_buf_size * sizeof((*out_quads)[0]));
1823 *out_corners = (CvCBCorner*)cvAlloc(*max_quad_buf_size * 4 * sizeof((*out_corners)[0]));
1825 // Create array of quads structures
1826 for( idx = 0; idx < root->total; idx++ )
1828 CvCBQuad* q = &(*out_quads)[quad_count];
1829 src_contour = *(CvSeq**)cvGetSeqElem( root, idx );
1830 if( (flags & CV_CALIB_CB_FILTER_QUADS) && src_contour->v_prev != (CvSeq*)board )
1834 memset( q, 0, sizeof(*q) );
1836 assert( src_contour->total == 4 );
1837 for( i = 0; i < 4; i++ )
1839 CvPoint * onePoint = (CvPoint*)cvGetSeqElem(src_contour, i);
1840 CV_Assert(onePoint != NULL);
1841 CvPoint2D32f pt = cvPointTo32f(*onePoint);
1842 CvCBCorner* corner = &(*out_corners)[quad_count*4 + i];
1844 memset( corner, 0, sizeof(*corner) );
1846 q->corners[i] = corner;
1848 q->edge_len = FLT_MAX;
1849 for( i = 0; i < 4; i++ )
1851 float dx = q->corners[i]->pt.x - q->corners[(i+1)&3]->pt.x;
1852 float dy = q->corners[i]->pt.y - q->corners[(i+1)&3]->pt.y;
1853 float d = dx*dx + dy*dy;
1854 if( q->edge_len > d )
1863 static bool processQuads(CvCBQuad *quads, int quad_count, CvSize pattern_size, int max_quad_buf_size,
1864 CvMemStorage * storage, CvCBCorner *corners, CvPoint2D32f *out_corners, int *out_corner_count, int & prev_sqr_size)
1866 if( quad_count <= 0 )
1871 // Find quad's neighbors
1872 icvFindQuadNeighbors( quads, quad_count );
1874 // allocate extra for adding in icvOrderFoundQuads
1875 CvCBQuad **quad_group = 0;
1876 CvCBCorner **corner_group = 0;
1878 quad_group = (CvCBQuad**)cvAlloc( sizeof(quad_group[0]) * max_quad_buf_size);
1879 corner_group = (CvCBCorner**)cvAlloc( sizeof(corner_group[0]) * max_quad_buf_size * 4 );
1881 for( int group_idx = 0; ; group_idx++ )
1883 int count = icvFindConnectedQuads( quads, quad_count, quad_group, group_idx, storage );
1888 // order the quad corners globally
1889 // maybe delete or add some
1890 PRINTF("Starting ordering of inner quads (%d)\n", count);
1891 count = icvOrderFoundConnectedQuads(count, quad_group, &quad_count, &quads, &corners,
1892 pattern_size, max_quad_buf_size, storage );
1893 PRINTF("Finished ordering of inner quads (%d)\n", count);
1896 continue; // haven't found inner quads
1898 // If count is more than it should be, this will remove those quads
1899 // which cause maximum deviation from a nice square pattern.
1900 count = icvCleanFoundConnectedQuads( count, quad_group, pattern_size );
1901 PRINTF("Connected group: %d, count: %d\n", group_idx, count);
1903 count = icvCheckQuadGroup( quad_group, count, corner_group, pattern_size );
1904 PRINTF("Connected group: %d, count: %d\n", group_idx, count);
1906 int n = count > 0 ? pattern_size.width * pattern_size.height : -count;
1907 n = MIN( n, pattern_size.width * pattern_size.height );
1911 for(int i = 0; i < n; i++ )
1914 float avgi = corner_group[i]->meanDist(&ni);
1915 sum_dist += avgi*ni;
1918 prev_sqr_size = cvRound(sum_dist/MAX(total, 1));
1920 if( count > 0 || (out_corner_count && -count > *out_corner_count) )
1922 // copy corners to output array
1923 for(int i = 0; i < n; i++ )
1924 out_corners[i] = corner_group[i]->pt;
1926 if( out_corner_count )
1927 *out_corner_count = n;
1929 if( count == pattern_size.width*pattern_size.height
1930 && icvCheckBoardMonotony( out_corners, pattern_size ))
1938 cvFree(&quad_group);
1939 cvFree(&corner_group);
1944 //==================================================================================================
1947 cvDrawChessboardCorners( CvArr* _image, CvSize pattern_size,
1948 CvPoint2D32f* corners, int count, int found )
1950 const int shift = 0;
1951 const int radius = 4;
1952 const int r = radius*(1 << shift);
1956 int type, cn, line_type;
1958 image = cvGetMat( _image, &stub );
1960 type = CV_MAT_TYPE(image->type);
1961 cn = CV_MAT_CN(type);
1962 if( cn != 1 && cn != 3 && cn != 4 )
1963 CV_Error( CV_StsUnsupportedFormat, "Number of channels must be 1, 3 or 4" );
1965 switch( CV_MAT_DEPTH(image->type) )
1977 CV_Error( CV_StsUnsupportedFormat,
1978 "Only 8-bit, 16-bit or floating-point 32-bit images are supported" );
1981 line_type = type == CV_8UC1 || type == CV_8UC3 ? CV_AA : 8;
1985 CvScalar color(0,0,255,0);
1987 color = cvScalarAll(200);
1988 color.val[0] *= scale;
1989 color.val[1] *= scale;
1990 color.val[2] *= scale;
1991 color.val[3] *= scale;
1993 for( i = 0; i < count; i++ )
1996 pt.x = cvRound(corners[i].x*(1 << shift));
1997 pt.y = cvRound(corners[i].y*(1 << shift));
1998 cvLine( image, cvPoint( pt.x - r, pt.y - r ),
1999 cvPoint( pt.x + r, pt.y + r ), color, 1, line_type, shift );
2000 cvLine( image, cvPoint( pt.x - r, pt.y + r),
2001 cvPoint( pt.x + r, pt.y - r), color, 1, line_type, shift );
2002 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift );
2009 const int line_max = 7;
2010 static const CvScalar line_colors[line_max] =
2013 CvScalar(0,128,255),
2014 CvScalar(0,200,200),
2016 CvScalar(200,200,0),
2021 for( y = 0, i = 0; y < pattern_size.height; y++ )
2023 CvScalar color = line_colors[y % line_max];
2025 color = cvScalarAll(200);
2026 color.val[0] *= scale;
2027 color.val[1] *= scale;
2028 color.val[2] *= scale;
2029 color.val[3] *= scale;
2031 for( x = 0; x < pattern_size.width; x++, i++ )
2034 pt.x = cvRound(corners[i].x*(1 << shift));
2035 pt.y = cvRound(corners[i].y*(1 << shift));
2038 cvLine( image, prev_pt, pt, color, 1, line_type, shift );
2040 cvLine( image, cvPoint(pt.x - r, pt.y - r),
2041 cvPoint(pt.x + r, pt.y + r), color, 1, line_type, shift );
2042 cvLine( image, cvPoint(pt.x - r, pt.y + r),
2043 cvPoint(pt.x + r, pt.y - r), color, 1, line_type, shift );
2044 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift );
2051 bool cv::findChessboardCorners( InputArray _image, Size patternSize,
2052 OutputArray corners, int flags )
2054 CV_INSTRUMENT_REGION()
2056 int count = patternSize.area()*2;
2057 std::vector<Point2f> tmpcorners(count+1);
2058 Mat image = _image.getMat(); CvMat c_image = image;
2059 bool ok = cvFindChessboardCorners(&c_image, patternSize,
2060 (CvPoint2D32f*)&tmpcorners[0], &count, flags ) > 0;
2063 tmpcorners.resize(count);
2064 Mat(tmpcorners).copyTo(corners);
2073 int quiet_error(int /*status*/, const char* /*func_name*/,
2074 const char* /*err_msg*/, const char* /*file_name*/,
2075 int /*line*/, void* /*userdata*/ )
2081 void cv::drawChessboardCorners( InputOutputArray _image, Size patternSize,
2082 InputArray _corners,
2083 bool patternWasFound )
2085 CV_INSTRUMENT_REGION()
2087 Mat corners = _corners.getMat();
2088 if( corners.empty() )
2090 Mat image = _image.getMat(); CvMat c_image = image;
2091 int nelems = corners.checkVector(2, CV_32F, true);
2092 CV_Assert(nelems >= 0);
2093 cvDrawChessboardCorners( &c_image, patternSize, corners.ptr<CvPoint2D32f>(),
2094 nelems, patternWasFound );
2097 bool cv::findCirclesGrid( InputArray image, Size patternSize,
2098 OutputArray centers, int flags,
2099 const Ptr<FeatureDetector> &blobDetector,
2100 CirclesGridFinderParameters parameters)
2102 CirclesGridFinderParameters2 parameters2;
2103 *((CirclesGridFinderParameters*)¶meters2) = parameters;
2104 return cv::findCirclesGrid2(image, patternSize, centers, flags, blobDetector, parameters2);
2107 bool cv::findCirclesGrid2( InputArray _image, Size patternSize,
2108 OutputArray _centers, int flags, const Ptr<FeatureDetector> &blobDetector,
2109 CirclesGridFinderParameters2 parameters)
2111 CV_INSTRUMENT_REGION()
2113 bool isAsymmetricGrid = (flags & CALIB_CB_ASYMMETRIC_GRID) ? true : false;
2114 bool isSymmetricGrid = (flags & CALIB_CB_SYMMETRIC_GRID ) ? true : false;
2115 CV_Assert(isAsymmetricGrid ^ isSymmetricGrid);
2117 Mat image = _image.getMat();
2118 std::vector<Point2f> centers;
2120 std::vector<KeyPoint> keypoints;
2121 blobDetector->detect(image, keypoints);
2122 std::vector<Point2f> points;
2123 for (size_t i = 0; i < keypoints.size(); i++)
2125 points.push_back (keypoints[i].pt);
2128 if(flags & CALIB_CB_ASYMMETRIC_GRID)
2129 parameters.gridType = CirclesGridFinderParameters::ASYMMETRIC_GRID;
2130 if(flags & CALIB_CB_SYMMETRIC_GRID)
2131 parameters.gridType = CirclesGridFinderParameters::SYMMETRIC_GRID;
2133 if(flags & CALIB_CB_CLUSTERING)
2135 CirclesGridClusterFinder circlesGridClusterFinder(parameters);
2136 circlesGridClusterFinder.findGrid(points, patternSize, centers);
2137 Mat(centers).copyTo(_centers);
2138 return !centers.empty();
2141 const int attempts = 2;
2142 const size_t minHomographyPoints = 4;
2144 for (int i = 0; i < attempts; i++)
2147 CirclesGridFinder boxFinder(patternSize, points, parameters);
2148 bool isFound = false;
2152 ErrorCallback oldCbk = redirectError(quiet_error, 0, &oldCbkData);
2156 isFound = boxFinder.findHoles();
2158 CV_CATCH(Exception, e)
2163 redirectError(oldCbk, oldCbkData);
2167 switch(parameters.gridType)
2169 case CirclesGridFinderParameters::SYMMETRIC_GRID:
2170 boxFinder.getHoles(centers);
2172 case CirclesGridFinderParameters::ASYMMETRIC_GRID:
2173 boxFinder.getAsymmetricHoles(centers);
2176 CV_Error(CV_StsBadArg, "Unknown pattern type");
2182 transform(centers, orgPointsMat, H.inv());
2183 convertPointsFromHomogeneous(orgPointsMat, centers);
2185 Mat(centers).copyTo(_centers);
2189 boxFinder.getHoles(centers);
2190 if (i != attempts - 1)
2192 if (centers.size() < minHomographyPoints)
2194 H = CirclesGridFinder::rectifyGrid(boxFinder.getDetectedGridSize(), centers, points, points);
2197 Mat(centers).copyTo(_centers);
2201 bool cv::findCirclesGrid( InputArray _image, Size patternSize,
2202 OutputArray _centers, int flags, const Ptr<FeatureDetector> &blobDetector)
2204 return cv::findCirclesGrid2(_image, patternSize, _centers, flags, blobDetector, CirclesGridFinderParameters2());