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; piMaxPos.reserve(20);
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.push_back(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 piMaxPos.erase(piMaxPos.begin() + i);
341 CV_Assert((size_t)iCntMaxima == piMaxPos.size());
343 PRINTF("HIST: MAXIMA COUNT: %d (%d, %d, %d, ...)\n", iCntMaxima,
344 iCntMaxima > 0 ? piMaxPos[0] : -1,
345 iCntMaxima > 1 ? piMaxPos[1] : -1,
346 iCntMaxima > 2 ? piMaxPos[2] : -1);
350 // no any maxima inside (except 0 and 255 which are not handled above)
351 // Does image black-write already?
352 const int iMaxPix2 = iMaxPix / 2;
353 for (int sum = 0, i = 0; i < 256; ++i) // select mean intensity
355 sum += piHistIntensity[i];
363 else if (iCntMaxima == 1)
365 iThresh = piMaxPos[0]/2;
367 else if ( iCntMaxima == 2)
369 iThresh = (piMaxPos[0] + piMaxPos[1])/2;
371 else // iCntMaxima >= 3
373 // CHECKING THRESHOLD FOR WHITE
374 int iIdxAccSum = 0, iAccum = 0;
375 for (int i=iNumBins-1; i>0; i--)
377 iAccum += piHistIntensity[i];
378 // iMaxPix/18 is about 5,5%, minimum required number of pixels required for white part of chessboard
379 if ( iAccum > (iMaxPix/18) )
387 int iBrightMax = piMaxPos[0];
388 // printf("iBrightMax = %d\n", iBrightMax);
389 for ( int n=0; n<iCntMaxima-1; n++)
392 if ( piMaxPos[n] < iIdxAccSum )
396 iBrightMax = piMaxPos[n];
399 // CHECKING THRESHOLD FOR BLACK
400 int iMaxVal = piHistIntensity[piMaxPos[iIdxBGMax]];
402 //IF TOO CLOSE TO 255, jump to next maximum
403 if ( piMaxPos[iIdxBGMax] >= 250 && iIdxBGMax + 1 < iCntMaxima )
406 iMaxVal = piHistIntensity[piMaxPos[iIdxBGMax]];
409 for ( int n=iIdxBGMax + 1; n<iCntMaxima; n++)
411 if ( piHistIntensity[piMaxPos[n]] >= iMaxVal )
413 iMaxVal = piHistIntensity[piMaxPos[n]];
418 //SETTING THRESHOLD FOR BINARIZATION
419 int iDist2 = (iBrightMax - piMaxPos[iIdxBGMax])/2;
420 iThresh = iBrightMax - iDist2;
421 PRINTF("THRESHOLD SELECTED = %d, BRIGHTMAX = %d, DARKMAX = %d\n", iThresh, iBrightMax, piMaxPos[iIdxBGMax]);
427 for ( int jj=0; jj<iRows; jj++)
429 uchar * row = img.ptr(jj);
430 for ( int ii=0; ii<iCols; ii++)
432 if ( row[ii] < iThresh )
444 int cvFindChessboardCorners( const void* arr, CvSize pattern_size,
445 CvPoint2D32f* out_corners, int* out_corner_count,
450 CvCBCorner *corners = 0;
452 cv::Ptr<CvMemStorage> storage;
457 const int min_dilations = 0;
458 const int max_dilations = 7;
460 if( out_corner_count )
461 *out_corner_count = 0;
463 Mat img = cvarrToMat((CvMat*)arr).clone();
465 if( img.depth() != CV_8U || (img.channels() != 1 && img.channels() != 3 && img.channels() != 4) )
466 CV_Error( CV_StsUnsupportedFormat, "Only 8-bit grayscale or color images are supported" );
468 if( pattern_size.width <= 2 || pattern_size.height <= 2 )
469 CV_Error( CV_StsOutOfRange, "Both width and height of the pattern should have bigger than 2" );
472 CV_Error( CV_StsNullPtr, "Null pointer to corners" );
474 if (img.channels() != 1)
476 cvtColor(img, img, COLOR_BGR2GRAY);
480 Mat thresh_img_new = img.clone();
481 icvBinarizationHistogramBased( thresh_img_new ); // process image in-place
482 SHOW("New binarization", thresh_img_new);
484 if( flags & CV_CALIB_CB_FAST_CHECK)
486 //perform new method for checking chessboard using a binary image.
487 //image is binarised using a threshold dependent on the image histogram
488 if (checkChessboardBinary(thresh_img_new, pattern_size) <= 0) //fall back to the old method
490 if (checkChessboard(img, pattern_size) <= 0)
497 storage.reset(cvCreateMemStorage(0));
499 int prev_sqr_size = 0;
501 // Try our standard "1" dilation, but if the pattern is not found, iterate the whole procedure with higher dilations.
502 // This is necessary because some squares simply do not separate properly with a single dilation. However,
503 // we want to use the minimum number of dilations possible since dilations cause the squares to become smaller,
504 // making it difficult to detect smaller squares.
505 for( int dilations = min_dilations; dilations <= max_dilations; dilations++ )
508 break; // already found it
510 //USE BINARY IMAGE COMPUTED USING icvBinarizationHistogramBased METHOD
511 dilate( thresh_img_new, thresh_img_new, Mat(), Point(-1, -1), 1 );
513 // So we can find rectangles that go to the edge, we draw a white line around the image edge.
514 // Otherwise FindContours will miss those clipped rectangle contours.
515 // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()...
516 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);
517 int max_quad_buf_size = 0;
520 Mat binarized_img = thresh_img_new.clone(); // make clone because cvFindContours modifies the source image
521 int quad_count = icvGenerateQuads( &quads, &corners, storage, binarized_img, flags, &max_quad_buf_size );
522 PRINTF("Quad count: %d/%d\n", quad_count, (pattern_size.width/2+1)*(pattern_size.height/2+1));
523 SHOW_QUADS("New quads", thresh_img_new, quads, quad_count);
524 if (processQuads(quads, quad_count, pattern_size, max_quad_buf_size, storage, corners, out_corners, out_corner_count, prev_sqr_size))
528 PRINTF("Chessboard detection result 0: %d\n", found);
530 // revert to old, slower, method if detection failed
533 if( flags & CV_CALIB_CB_NORMALIZE_IMAGE )
535 equalizeHist( img, img );
541 PRINTF("Fallback to old algorithm\n");
542 const bool useAdaptive = flags & CV_CALIB_CB_ADAPTIVE_THRESH;
545 // empiric threshold level
546 // thresholding performed here and not inside the cycle to save processing time
547 double mean = cv::mean(img).val[0];
548 int thresh_level = MAX(cvRound( mean - 10 ), 10);
549 threshold( img, thresh_img, thresh_level, 255, THRESH_BINARY );
551 //if flag CV_CALIB_CB_ADAPTIVE_THRESH is not set it doesn't make sense to iterate over k
552 int max_k = useAdaptive ? 6 : 1;
553 for( k = 0; k < max_k; k++ )
555 for( int dilations = min_dilations; dilations <= max_dilations; dilations++ )
558 break; // already found it
560 // convert the input grayscale image to binary (black-n-white)
563 int block_size = cvRound(prev_sqr_size == 0
564 ? MIN(img.cols, img.rows) * (k % 2 == 0 ? 0.2 : 0.1)
565 : prev_sqr_size * 2);
566 block_size = block_size | 1;
568 adaptiveThreshold( img, thresh_img, 255, ADAPTIVE_THRESH_MEAN_C, THRESH_BINARY, block_size, (k/2)*5 );
570 dilate( thresh_img, thresh_img, Mat(), Point(-1, -1), dilations-1 );
575 dilate( thresh_img, thresh_img, Mat(), Point(-1, -1), 1 );
577 SHOW("Old binarization", thresh_img);
579 // So we can find rectangles that go to the edge, we draw a white line around the image edge.
580 // Otherwise FindContours will miss those clipped rectangle contours.
581 // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()...
582 rectangle( thresh_img, Point(0,0), Point(thresh_img.cols-1, thresh_img.rows-1), Scalar(255,255,255), 3, LINE_8);
583 int max_quad_buf_size = 0;
586 Mat binarized_img = (useAdaptive) ? thresh_img : thresh_img.clone(); // make clone because cvFindContours modifies the source image
587 int quad_count = icvGenerateQuads( &quads, &corners, storage, binarized_img, flags, &max_quad_buf_size);
588 PRINTF("Quad count: %d/%d\n", quad_count, (pattern_size.width/2+1)*(pattern_size.height/2+1));
589 SHOW_QUADS("Old quads", thresh_img, quads, quad_count);
590 if (processQuads(quads, quad_count, pattern_size, max_quad_buf_size, storage, corners, out_corners, out_corner_count, prev_sqr_size))
596 PRINTF("Chessboard detection result 1: %d\n", found);
599 found = icvCheckBoardMonotony( out_corners, pattern_size );
601 PRINTF("Chessboard detection result 2: %d\n", found);
603 // check that none of the found corners is too close to the image boundary
606 const int BORDER = 8;
607 for( k = 0; k < pattern_size.width*pattern_size.height; k++ )
609 if( out_corners[k].x <= BORDER || out_corners[k].x > img.cols - BORDER ||
610 out_corners[k].y <= BORDER || out_corners[k].y > img.rows - BORDER )
614 found = k == pattern_size.width*pattern_size.height;
617 PRINTF("Chessboard detection result 3: %d\n", found);
621 if ( pattern_size.height % 2 == 0 && pattern_size.width % 2 == 0 )
623 int last_row = (pattern_size.height-1)*pattern_size.width;
624 double dy0 = out_corners[last_row].y - out_corners[0].y;
627 int n = pattern_size.width*pattern_size.height;
628 for(int i = 0; i < n/2; i++ )
631 CV_SWAP(out_corners[i], out_corners[n-i-1], temp);
637 cvFindCornerSubPix( &old_img, out_corners, pattern_size.width*pattern_size.height,
638 cvSize(wsize, wsize), cvSize(-1,-1),
639 cvTermCriteria(CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 15, 0.1));
654 // Checks that each board row and column is pretty much monotonous curve:
655 // It analyzes each row and each column of the chessboard as following:
656 // for each corner c lying between end points in the same row/column it checks that
657 // the point projection to the line segment (a,b) is lying between projections
658 // of the neighbor corners in the same row/column.
660 // This function has been created as temporary workaround for the bug in current implementation
661 // of cvFindChessboardCornes that produces absolutely unordered sets of corners.
665 icvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size )
669 for( k = 0; k < 2; k++ )
671 for( i = 0; i < (k == 0 ? pattern_size.height : pattern_size.width); i++ )
673 CvPoint2D32f a = k == 0 ? corners[i*pattern_size.width] : corners[i];
674 CvPoint2D32f b = k == 0 ? corners[(i+1)*pattern_size.width-1] :
675 corners[(pattern_size.height-1)*pattern_size.width + i];
676 float prevt = 0, dx0 = b.x - a.x, dy0 = b.y - a.y;
677 if( fabs(dx0) + fabs(dy0) < FLT_EPSILON )
679 for( j = 1; j < (k == 0 ? pattern_size.width : pattern_size.height) - 1; j++ )
681 CvPoint2D32f c = k == 0 ? corners[i*pattern_size.width + j] :
682 corners[j*pattern_size.width + i];
683 float t = ((c.x - a.x)*dx0 + (c.y - a.y)*dy0)/(dx0*dx0 + dy0*dy0);
684 if( t < prevt || t > 1 )
695 // order a group of connected quads
698 // clockwise from there
699 // note: "top left" is nominal, depends on initial ordering of starting quad
700 // but all other quads are ordered consistently
702 // can change the number of quads in the group
703 // can add quads, so we need to have quad/corner arrays passed in
707 icvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads,
708 int *all_count, CvCBQuad **all_quads, CvCBCorner **corners,
709 CvSize pattern_size, int max_quad_buf_size, CvMemStorage* storage )
711 cv::Ptr<CvMemStorage> temp_storage(cvCreateChildMemStorage( storage ));
712 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage );
714 // first find an interior quad
715 CvCBQuad *start = NULL;
716 for (int i=0; i<quad_count; i++)
718 if (quads[i]->count == 4)
726 return 0; // no 4-connected quad
728 // start with first one, assign rows/cols
729 int row_min = 0, col_min = 0, row_max=0, col_max = 0;
731 std::map<int, int> col_hist;
732 std::map<int, int> row_hist;
734 cvSeqPush(stack, &start);
737 start->ordered = true;
739 // Recursively order the quads so that all position numbers (e.g.,
740 // 0,1,2,3) are in the at the same relative corner (e.g., lower right).
742 while( stack->total )
745 cvSeqPop( stack, &q );
752 if (row > row_max) row_max = row;
753 if (row < row_min) row_min = row;
754 if (col > col_max) col_max = col;
755 if (col < col_min) col_min = col;
757 for(int i = 0; i < 4; i++ )
759 CvCBQuad *neighbor = q->neighbors[i];
760 switch(i) // adjust col, row for this quad
761 { // start at top left, go clockwise
772 // just do inside quads
773 if (neighbor && neighbor->ordered == false && neighbor->count == 4)
775 PRINTF("col: %d row: %d\n", col, row);
776 icvOrderQuad(neighbor, q->corners[i], (i+2)%4); // set in order
777 neighbor->ordered = true;
780 cvSeqPush( stack, &neighbor );
785 for (int i=col_min; i<=col_max; i++)
786 PRINTF("HIST[%d] = %d\n", i, col_hist[i]);
788 // analyze inner quad structure
789 int w = pattern_size.width - 1;
790 int h = pattern_size.height - 1;
791 int drow = row_max - row_min + 1;
792 int dcol = col_max - col_min + 1;
794 // normalize pattern and found quad indices
795 if ((w > h && dcol < drow) ||
796 (w < h && drow < dcol))
798 h = pattern_size.width - 1;
799 w = pattern_size.height - 1;
802 PRINTF("Size: %dx%d Pattern: %dx%d\n", dcol, drow, w, h);
804 // check if there are enough inner quads
805 if (dcol < w || drow < h) // found enough inner quads?
807 PRINTF("Too few inner quad rows/cols\n");
808 return 0; // no, return
810 #ifdef ENABLE_TRIM_COL_ROW
811 // too many columns, not very common
812 if (dcol == w+1) // too many, trim
814 PRINTF("Trimming cols\n");
815 if (col_hist[col_max] > col_hist[col_min])
817 PRINTF("Trimming left col\n");
818 quad_count = icvTrimCol(quads,quad_count,col_min,-1);
822 PRINTF("Trimming right col\n");
823 quad_count = icvTrimCol(quads,quad_count,col_max,+1);
827 // too many rows, not very common
828 if (drow == h+1) // too many, trim
830 PRINTF("Trimming rows\n");
831 if (row_hist[row_max] > row_hist[row_min])
833 PRINTF("Trimming top row\n");
834 quad_count = icvTrimRow(quads,quad_count,row_min,-1);
838 PRINTF("Trimming bottom row\n");
839 quad_count = icvTrimRow(quads,quad_count,row_max,+1);
844 // check edges of inner quads
845 // if there is an outer quad missing, fill it in
846 // first order all inner quads
848 for (int i=0; i<quad_count; i++)
850 if (quads[i]->count == 4)
851 { // ok, look at neighbors
852 int col = quads[i]->col;
853 int row = quads[i]->row;
854 for (int j=0; j<4; j++)
856 switch(j) // adjust col, row for this quad
857 { // start at top left, go clockwise
867 CvCBQuad *neighbor = quads[i]->neighbors[j];
868 if (neighbor && !neighbor->ordered && // is it an inner quad?
869 col <= col_max && col >= col_min &&
870 row <= row_max && row >= row_min)
872 // if so, set in order
873 PRINTF("Adding inner: col: %d row: %d\n", col, row);
875 icvOrderQuad(neighbor, quads[i]->corners[j], (j+2)%4);
876 neighbor->ordered = true;
884 // if we have found inner quads, add corresponding outer quads,
888 PRINTF("Found %d inner quads not connected to outer quads, repairing\n", found);
889 for (int i=0; i<quad_count && *all_count < max_quad_buf_size; i++)
891 if (quads[i]->count < 4 && quads[i]->ordered)
893 int added = icvAddOuterQuad(quads[i],quads,quad_count,all_quads,*all_count,corners, max_quad_buf_size);
899 if (*all_count >= max_quad_buf_size)
904 // final trimming of outer quads
905 if (dcol == w && drow == h) // found correct inner quads
907 PRINTF("Inner bounds ok, check outer quads\n");
908 int rcount = quad_count;
909 for (int i=quad_count-1; i>=0; i--) // eliminate any quad not connected to
912 if (quads[i]->ordered == false)
915 for (int j=0; j<4; j++) // any neighbors that are ordered?
917 if (quads[i]->neighbors[j] && quads[i]->neighbors[j]->ordered)
920 if (!outer) // not an outer quad, eliminate
922 PRINTF("Removing quad %d\n", i);
923 icvRemoveQuadFromGroup(quads,rcount,quads[i]);
937 // looks for the neighbor of <quad> that isn't present,
938 // tries to add it in.
942 icvAddOuterQuad( CvCBQuad *quad, CvCBQuad **quads, int quad_count,
943 CvCBQuad **all_quads, int all_count, CvCBCorner **corners, int max_quad_buf_size )
947 for (int i=0; i<4 && all_count < max_quad_buf_size; i++) // find no-neighbor corners
949 if (!quad->neighbors[i]) // ok, create and add neighbor
952 PRINTF("Adding quad as neighbor 2\n");
953 CvCBQuad *q = &(*all_quads)[all_count];
954 memset( q, 0, sizeof(*q) );
956 quads[quad_count] = q;
959 // set neighbor and group id
960 quad->neighbors[i] = q;
962 q->neighbors[j] = quad;
963 q->group_idx = quad->group_idx;
964 q->count = 1; // number of neighbors
966 q->edge_len = quad->edge_len;
968 // make corners of new quad
969 // same as neighbor quad, but offset
970 CvPoint2D32f pt = quad->corners[i]->pt;
972 float dx = pt.x - quad->corners[j]->pt.x;
973 float dy = pt.y - quad->corners[j]->pt.y;
974 for (int k=0; k<4; k++)
976 corner = &(*corners)[all_count*4+k];
977 pt = quad->corners[k]->pt;
978 memset( corner, 0, sizeof(*corner) );
980 q->corners[k] = corner;
984 // have to set exact corner
985 q->corners[j] = quad->corners[i];
987 // now find other neighbor and add it, if possible
988 if (quad->neighbors[(i+3)%4] &&
989 quad->neighbors[(i+3)%4]->ordered &&
990 quad->neighbors[(i+3)%4]->neighbors[i] &&
991 quad->neighbors[(i+3)%4]->neighbors[i]->ordered )
993 CvCBQuad *qn = quad->neighbors[(i+3)%4]->neighbors[i];
995 q->neighbors[(j+1)%4] = qn;
996 qn->neighbors[(i+1)%4] = q;
998 // have to set exact corner
999 q->corners[(j+1)%4] = qn->corners[(i+1)%4];
1009 // trimming routines
1010 #ifdef ENABLE_TRIM_COL_ROW
1012 icvTrimCol(CvCBQuad **quads, int count, int col, int dir)
1015 // find the right quad(s)
1016 for (int i=0; i<count; i++)
1018 #ifdef DEBUG_CHESSBOARD
1019 if (quads[i]->ordered)
1020 PRINTF("index: %d cur: %d\n", col, quads[i]->col);
1022 if (quads[i]->ordered && quads[i]->col == col)
1026 if (quads[i]->neighbors[1])
1028 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]);
1031 if (quads[i]->neighbors[2])
1033 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]);
1039 if (quads[i]->neighbors[0])
1041 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]);
1044 if (quads[i]->neighbors[3])
1046 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]);
1057 icvTrimRow(CvCBQuad **quads, int count, int row, int dir)
1059 int i, rcount = count;
1060 // find the right quad(s)
1061 for (i=0; i<count; i++)
1063 #ifdef DEBUG_CHESSBOARD
1064 if (quads[i]->ordered)
1065 PRINTF("index: %d cur: %d\n", row, quads[i]->row);
1067 if (quads[i]->ordered && quads[i]->row == row)
1069 if (dir == 1) // remove from bottom
1071 if (quads[i]->neighbors[2])
1073 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]);
1076 if (quads[i]->neighbors[3])
1078 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]);
1082 else // remove from top
1084 if (quads[i]->neighbors[0])
1086 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]);
1089 if (quads[i]->neighbors[1])
1091 icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]);
1103 // remove quad from quad group
1107 icvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0)
1110 // remove any references to this quad as a neighbor
1111 for(i = 0; i < count; i++ )
1113 CvCBQuad *q = quads[i];
1114 for(j = 0; j < 4; j++ )
1116 if( q->neighbors[j] == q0 )
1118 q->neighbors[j] = 0;
1120 for(int k = 0; k < 4; k++ )
1121 if( q0->neighbors[k] == q )
1123 q0->neighbors[k] = 0;
1133 for(i = 0; i < count; i++ )
1135 CvCBQuad *q = quads[i];
1138 quads[i] = quads[count-1];
1145 // put quad into correct order, where <corner> has value <common>
1149 icvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common)
1153 for (tc=0; tc<4; tc++)
1154 if (quad->corners[tc]->pt.x == corner->pt.x &&
1155 quad->corners[tc]->pt.y == corner->pt.y)
1160 while (tc != common)
1165 tempc = quad->corners[3];
1166 tempq = quad->neighbors[3];
1167 for (int i=3; i>0; i--)
1169 quad->corners[i] = quad->corners[i-1];
1170 quad->neighbors[i] = quad->neighbors[i-1];
1172 quad->corners[0] = tempc;
1173 quad->neighbors[0] = tempq;
1180 // if we found too many connect quads, remove those which probably do not belong.
1182 icvCleanFoundConnectedQuads( int quad_count, CvCBQuad **quad_group, CvSize pattern_size )
1184 CvPoint2D32f center;
1186 // number of quads this pattern should contain
1187 int count = ((pattern_size.width + 1)*(pattern_size.height + 1) + 1)/2;
1189 // if we have more quadrangles than we should,
1190 // try to eliminate duplicates or ones which don't belong to the pattern rectangle...
1191 if( quad_count <= count )
1194 // create an array of quadrangle centers
1195 cv::AutoBuffer<CvPoint2D32f> centers( quad_count );
1196 cv::Ptr<CvMemStorage> temp_storage(cvCreateMemStorage(0));
1198 for( i = 0; i < quad_count; i++ )
1201 CvCBQuad* q = quad_group[i];
1203 for( j = 0; j < 4; j++ )
1205 CvPoint2D32f pt = q->corners[j]->pt;
1217 center.x /= quad_count;
1218 center.y /= quad_count;
1220 // If we still have more quadrangles than we should,
1221 // we try to eliminate bad ones based on minimizing the bounding box.
1222 // We iteratively remove the point which reduces the size of
1223 // the bounding box of the blobs the most
1224 // (since we want the rectangle to be as small as possible)
1225 // remove the quadrange that causes the biggest reduction
1226 // in pattern size until we have the correct number
1227 for( ; quad_count > count; quad_count-- )
1229 double min_box_area = DBL_MAX;
1230 int skip, min_box_area_index = -1;
1232 // For each point, calculate box area without that point
1233 for( skip = 0; skip < quad_count; skip++ )
1235 // get bounding rectangle
1236 CvPoint2D32f temp = centers[skip]; // temporarily make index 'skip' the same as
1237 centers[skip] = center; // pattern center (so it is not counted for convex hull)
1238 CvMat pointMat = cvMat(1, quad_count, CV_32FC2, centers);
1239 CvSeq *hull = cvConvexHull2( &pointMat, temp_storage, CV_CLOCKWISE, 1 );
1240 centers[skip] = temp;
1241 double hull_area = fabs(cvContourArea(hull, CV_WHOLE_SEQ));
1243 // remember smallest box area
1244 if( hull_area < min_box_area )
1246 min_box_area = hull_area;
1247 min_box_area_index = skip;
1249 cvClearMemStorage( temp_storage );
1252 CvCBQuad *q0 = quad_group[min_box_area_index];
1254 // remove any references to this quad as a neighbor
1255 for( i = 0; i < quad_count; i++ )
1257 CvCBQuad *q = quad_group[i];
1258 for( j = 0; j < 4; j++ )
1260 if( q->neighbors[j] == q0 )
1262 q->neighbors[j] = 0;
1264 for( k = 0; k < 4; k++ )
1265 if( q0->neighbors[k] == q )
1267 q0->neighbors[k] = 0;
1278 quad_group[min_box_area_index] = quad_group[quad_count];
1279 centers[min_box_area_index] = centers[quad_count];
1285 //=====================================================================================
1288 icvFindConnectedQuads( CvCBQuad *quad, int quad_count, CvCBQuad **out_group,
1289 int group_idx, CvMemStorage* storage )
1291 cv::Ptr<CvMemStorage> temp_storage(cvCreateChildMemStorage( storage ));
1292 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage );
1295 // Scan the array for a first unlabeled quad
1296 for( i = 0; i < quad_count; i++ )
1298 if( quad[i].count > 0 && quad[i].group_idx < 0)
1302 // Recursively find a group of connected quads starting from the seed quad[i]
1303 if( i < quad_count )
1305 CvCBQuad* q = &quad[i];
1306 cvSeqPush( stack, &q );
1307 out_group[count++] = q;
1308 q->group_idx = group_idx;
1311 while( stack->total )
1313 cvSeqPop( stack, &q );
1314 for( i = 0; i < 4; i++ )
1316 CvCBQuad *neighbor = q->neighbors[i];
1317 if( neighbor && neighbor->count > 0 && neighbor->group_idx < 0 )
1319 cvSeqPush( stack, &neighbor );
1320 out_group[count++] = neighbor;
1321 neighbor->group_idx = group_idx;
1322 neighbor->ordered = false;
1332 //=====================================================================================
1335 icvCheckQuadGroup( CvCBQuad **quad_group, int quad_count,
1336 CvCBCorner **out_corners, CvSize pattern_size )
1338 const int ROW1 = 1000000;
1339 const int ROW2 = 2000000;
1340 const int ROW_ = 3000000;
1342 int i, out_corner_count = 0, corner_count = 0;
1343 std::vector<CvCBCorner*> corners(quad_count*4);
1346 int width = 0, height = 0;
1347 int hist[5] = {0,0,0,0,0};
1348 CvCBCorner* first = 0, *first2 = 0, *right, *cur, *below, *c;
1350 // build dual graph, which vertices are internal quad corners
1351 // and two vertices are connected iff they lie on the same quad edge
1352 for( i = 0; i < quad_count; i++ )
1354 CvCBQuad* q = quad_group[i];
1355 /*CvScalar color = q->count == 0 ? cvScalar(0,255,255) :
1356 q->count == 1 ? cvScalar(0,0,255) :
1357 q->count == 2 ? cvScalar(0,255,0) :
1358 q->count == 3 ? cvScalar(255,255,0) :
1359 cvScalar(255,0,0);*/
1361 for( j = 0; j < 4; j++ )
1363 //cvLine( debug_img, cvPointFrom32f(q->corners[j]->pt), cvPointFrom32f(q->corners[(j+1)&3]->pt), color, 1, CV_AA, 0 );
1364 if( q->neighbors[j] )
1366 CvCBCorner *a = q->corners[j], *b = q->corners[(j+1)&3];
1367 // mark internal corners that belong to:
1368 // - a quad with a single neighbor - with ROW1,
1369 // - a quad with two neighbors - with ROW2
1370 // make the rest of internal corners with ROW_
1371 int row_flag = q->count == 1 ? ROW1 : q->count == 2 ? ROW2 : ROW_;
1375 corners[corner_count++] = a;
1378 else if( a->row > row_flag )
1381 if( q->neighbors[(j+1)&3] )
1383 if( a->count >= 4 || b->count >= 4 )
1385 for( k = 0; k < 4; k++ )
1387 if( a->neighbors[k] == b )
1389 if( b->neighbors[k] == a )
1392 a->neighbors[a->count++] = b;
1393 b->neighbors[b->count++] = a;
1399 if( corner_count != pattern_size.width*pattern_size.height )
1402 for( i = 0; i < corner_count; i++ )
1404 int n = corners[i]->count;
1405 assert( 0 <= n && n <= 4 );
1407 if( !first && n == 2 )
1409 if( corners[i]->row == ROW1 )
1411 else if( !first2 && corners[i]->row == ROW2 )
1412 first2 = corners[i];
1416 // start with a corner that belongs to a quad with a single neighbor.
1417 // if we do not have such, start with a corner of a quad with two neighbors.
1421 if( !first || hist[0] != 0 || hist[1] != 0 || hist[2] != 4 ||
1422 hist[3] != (pattern_size.width + pattern_size.height)*2 - 8 )
1427 out_corners[out_corner_count++] = cur;
1429 for( k = 0; k < 4; k++ )
1431 c = cur->neighbors[k];
1441 if( !right || (right->count != 2 && right->count != 3) ||
1442 !below || (below->count != 2 && below->count != 3) )
1446 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,255,0), -1, 8, 0 );
1448 first = below; // remember the first corner in the next row
1449 // find and store the first row (or column)
1453 out_corners[out_corner_count++] = right;
1454 //cvCircle( debug_img, cvPointFrom32f(right->pt), 3, cvScalar(0,255-j*10,0), -1, 8, 0 );
1455 if( right->count == 2 )
1457 if( right->count != 3 || out_corner_count >= MAX(pattern_size.width,pattern_size.height) )
1460 for( k = 0; k < 4; k++ )
1462 c = cur->neighbors[k];
1463 if( c && c->row > 0 )
1465 for( kk = 0; kk < 4; kk++ )
1467 if( c->neighbors[kk] == below )
1478 width = out_corner_count;
1479 if( width == pattern_size.width )
1480 height = pattern_size.height;
1481 else if( width == pattern_size.height )
1482 height = pattern_size.width;
1486 // find and store all the other rows
1496 out_corners[out_corner_count++] = cur;
1497 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,0,255-j*10), -1, 8, 0 );
1498 if( cur->count == 2 + (i < height-1) && j > 0 )
1503 // find a neighbor that has not been processed yet
1504 // and that has a neighbor from the previous row
1505 for( k = 0; k < 4; k++ )
1507 c = cur->neighbors[k];
1508 if( c && c->row > i )
1510 for( kk = 0; kk < 4; kk++ )
1512 if( c->neighbors[kk] && c->neighbors[kk]->row == i-1 )
1530 if( j != width - 1 )
1534 if( out_corner_count != corner_count )
1537 // check if we need to transpose the board
1538 if( width != pattern_size.width )
1540 CV_SWAP( width, height, k );
1542 memcpy( &corners[0], out_corners, corner_count*sizeof(corners[0]) );
1543 for( i = 0; i < height; i++ )
1544 for( j = 0; j < width; j++ )
1545 out_corners[i*width + j] = corners[j*height + i];
1548 // check if we need to revert the order in each row
1550 CvPoint2D32f p0 = out_corners[0]->pt, p1 = out_corners[pattern_size.width-1]->pt,
1551 p2 = out_corners[pattern_size.width]->pt;
1552 if( (p1.x - p0.x)*(p2.y - p1.y) - (p1.y - p0.y)*(p2.x - p1.x) < 0 )
1554 if( width % 2 == 0 )
1556 for( i = 0; i < height; i++ )
1557 for( j = 0; j < width/2; j++ )
1558 CV_SWAP( out_corners[i*width+j], out_corners[i*width+width-j-1], c );
1562 for( j = 0; j < width; j++ )
1563 for( i = 0; i < height/2; i++ )
1564 CV_SWAP( out_corners[i*width+j], out_corners[(height - i - 1)*width+j], c );
1569 result = corner_count;
1575 corner_count = MIN( corner_count, pattern_size.width*pattern_size.height );
1576 for( i = 0; i < corner_count; i++ )
1577 out_corners[i] = corners[i];
1578 result = -corner_count;
1580 if (result == -pattern_size.width*pattern_size.height)
1590 //=====================================================================================
1592 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count )
1594 const float thresh_scale = 1.f;
1598 // find quad neighbors
1599 for( idx = 0; idx < quad_count; idx++ )
1601 CvCBQuad* cur_quad = &quads[idx];
1603 // choose the points of the current quadrangle that are close to
1604 // some points of the other quadrangles
1605 // (it can happen for split corners (due to dilation) of the
1606 // checker board). Search only in other quadrangles!
1608 // for each corner of this quadrangle
1609 for( i = 0; i < 4; i++ )
1612 float min_dist = FLT_MAX;
1613 int closest_corner_idx = -1;
1614 CvCBQuad *closest_quad = 0;
1615 CvCBCorner *closest_corner = 0;
1617 if( cur_quad->neighbors[i] )
1620 pt = cur_quad->corners[i]->pt;
1622 // find the closest corner in all other quadrangles
1623 for( k = 0; k < quad_count; k++ )
1628 for( j = 0; j < 4; j++ )
1630 if( quads[k].neighbors[j] )
1633 dx = pt.x - quads[k].corners[j]->pt.x;
1634 dy = pt.y - quads[k].corners[j]->pt.y;
1635 dist = dx * dx + dy * dy;
1637 if( dist < min_dist &&
1638 dist <= cur_quad->edge_len*thresh_scale &&
1639 dist <= quads[k].edge_len*thresh_scale )
1641 // check edge lengths, make sure they're compatible
1642 // edges that are different by more than 1:4 are rejected
1643 float ediff = cur_quad->edge_len - quads[k].edge_len;
1644 if (ediff > 32*cur_quad->edge_len ||
1645 ediff > 32*quads[k].edge_len)
1647 PRINTF("Incompatible edge lengths\n");
1650 closest_corner_idx = j;
1651 closest_quad = &quads[k];
1657 // we found a matching corner point?
1658 if( closest_corner_idx >= 0 && min_dist < FLT_MAX )
1660 // If another point from our current quad is closer to the found corner
1661 // than the current one, then we don't count this one after all.
1662 // This is necessary to support small squares where otherwise the wrong
1663 // corner will get matched to closest_quad;
1664 closest_corner = closest_quad->corners[closest_corner_idx];
1666 for( j = 0; j < 4; j++ )
1668 if( cur_quad->neighbors[j] == closest_quad )
1671 dx = closest_corner->pt.x - cur_quad->corners[j]->pt.x;
1672 dy = closest_corner->pt.y - cur_quad->corners[j]->pt.y;
1674 if( dx * dx + dy * dy < min_dist )
1678 if( j < 4 || cur_quad->count >= 4 || closest_quad->count >= 4 )
1681 // Check that each corner is a neighbor of different quads
1682 for( j = 0; j < closest_quad->count; j++ )
1684 if( closest_quad->neighbors[j] == cur_quad )
1687 if( j < closest_quad->count )
1690 // check whether the closest corner to closest_corner
1691 // is different from cur_quad->corners[i]->pt
1692 for( k = 0; k < quad_count; k++ )
1694 CvCBQuad* q = &quads[k];
1695 if( k == idx || q == closest_quad )
1698 for( j = 0; j < 4; j++ )
1699 if( !q->neighbors[j] )
1701 dx = closest_corner->pt.x - q->corners[j]->pt.x;
1702 dy = closest_corner->pt.y - q->corners[j]->pt.y;
1703 dist = dx*dx + dy*dy;
1704 if( dist < min_dist )
1711 if( k < quad_count )
1714 closest_corner->pt.x = (pt.x + closest_corner->pt.x) * 0.5f;
1715 closest_corner->pt.y = (pt.y + closest_corner->pt.y) * 0.5f;
1717 // We've found one more corner - remember it
1719 cur_quad->neighbors[i] = closest_quad;
1720 cur_quad->corners[i] = closest_corner;
1722 closest_quad->count++;
1723 closest_quad->neighbors[closest_corner_idx] = cur_quad;
1729 //=====================================================================================
1731 // returns corners in clockwise order
1732 // corners don't necessarily start at same position on quad (e.g.,
1736 icvGenerateQuads( CvCBQuad **out_quads, CvCBCorner **out_corners,
1737 CvMemStorage *storage, const cv::Mat & image_, int flags, int *max_quad_buf_size )
1739 CvMat image_old(image_), *image = &image_old;
1741 cv::Ptr<CvMemStorage> temp_storage;
1749 CvSeq *src_contour = 0;
1751 CvContourEx* board = 0;
1752 CvContourScanner scanner;
1753 int i, idx, min_size;
1755 CV_Assert( out_corners && out_quads );
1757 // empiric bound for minimal allowed perimeter for squares
1758 min_size = 25; //cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 );
1760 // create temporary storage for contours and the sequence of pointers to found quadrangles
1761 temp_storage.reset(cvCreateChildMemStorage( storage ));
1762 root = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage );
1764 // initialize contour retrieving routine
1765 scanner = cvStartFindContours( image, temp_storage, sizeof(CvContourEx),
1766 CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE );
1768 // get all the contours one by one
1769 while( (src_contour = cvFindNextContour( scanner )) != 0 )
1771 CvSeq *dst_contour = 0;
1772 CvRect rect = ((CvContour*)src_contour)->rect;
1774 // reject contours with too small perimeter
1775 if( CV_IS_SEQ_HOLE(src_contour) && rect.width*rect.height >= min_size )
1777 const int min_approx_level = 1, max_approx_level = MAX_CONTOUR_APPROX;
1779 for( approx_level = min_approx_level; approx_level <= max_approx_level; approx_level++ )
1781 dst_contour = cvApproxPoly( src_contour, sizeof(CvContour), temp_storage,
1782 CV_POLY_APPROX_DP, (float)approx_level );
1783 if( dst_contour->total == 4 )
1786 // we call this again on its own output, because sometimes
1787 // cvApproxPoly() does not simplify as much as it should.
1788 dst_contour = cvApproxPoly( dst_contour, sizeof(CvContour), temp_storage,
1789 CV_POLY_APPROX_DP, (float)approx_level );
1791 if( dst_contour->total == 4 )
1795 // reject non-quadrangles
1796 if( dst_contour->total == 4 && cvCheckContourConvexity(dst_contour) )
1799 double d1, d2, p = cvContourPerimeter(dst_contour);
1800 double area = fabs(cvContourArea(dst_contour, CV_WHOLE_SEQ));
1803 for( i = 0; i < 4; i++ )
1804 pt[i] = *(CvPoint*)cvGetSeqElem(dst_contour, i);
1806 dx = pt[0].x - pt[2].x;
1807 dy = pt[0].y - pt[2].y;
1808 d1 = sqrt(dx*dx + dy*dy);
1810 dx = pt[1].x - pt[3].x;
1811 dy = pt[1].y - pt[3].y;
1812 d2 = sqrt(dx*dx + dy*dy);
1814 // philipg. Only accept those quadrangles which are more square
1815 // than rectangular and which are big enough
1817 dx = pt[0].x - pt[1].x;
1818 dy = pt[0].y - pt[1].y;
1819 d3 = sqrt(dx*dx + dy*dy);
1820 dx = pt[1].x - pt[2].x;
1821 dy = pt[1].y - pt[2].y;
1822 d4 = sqrt(dx*dx + dy*dy);
1823 if( !(flags & CV_CALIB_CB_FILTER_QUADS) ||
1824 (d3*4 > d4 && d4*4 > d3 && d3*d4 < area*1.5 && area > min_size &&
1825 d1 >= 0.15 * p && d2 >= 0.15 * p) )
1827 CvContourEx* parent = (CvContourEx*)(src_contour->v_prev);
1829 if( !board || board->counter < parent->counter )
1831 dst_contour->v_prev = (CvSeq*)parent;
1832 //for( i = 0; i < 4; i++ ) cvLine( debug_img, pt[i], pt[(i+1)&3], cvScalar(200,255,255), 1, CV_AA, 0 );
1833 cvSeqPush( root, &dst_contour );
1839 // finish contour retrieving
1840 cvEndFindContours( &scanner );
1842 // allocate quad & corner buffers
1843 *max_quad_buf_size = MAX(1, (root->total+root->total / 2)) * 2;
1844 *out_quads = (CvCBQuad*)cvAlloc(*max_quad_buf_size * sizeof((*out_quads)[0]));
1845 *out_corners = (CvCBCorner*)cvAlloc(*max_quad_buf_size * 4 * sizeof((*out_corners)[0]));
1847 // Create array of quads structures
1848 for( idx = 0; idx < root->total; idx++ )
1850 CvCBQuad* q = &(*out_quads)[quad_count];
1851 src_contour = *(CvSeq**)cvGetSeqElem( root, idx );
1852 if( (flags & CV_CALIB_CB_FILTER_QUADS) && src_contour->v_prev != (CvSeq*)board )
1856 memset( q, 0, sizeof(*q) );
1858 assert( src_contour->total == 4 );
1859 for( i = 0; i < 4; i++ )
1861 CvPoint * onePoint = (CvPoint*)cvGetSeqElem(src_contour, i);
1862 CV_Assert(onePoint != NULL);
1863 CvPoint2D32f pt = cvPointTo32f(*onePoint);
1864 CvCBCorner* corner = &(*out_corners)[quad_count*4 + i];
1866 memset( corner, 0, sizeof(*corner) );
1868 q->corners[i] = corner;
1870 q->edge_len = FLT_MAX;
1871 for( i = 0; i < 4; i++ )
1873 float dx = q->corners[i]->pt.x - q->corners[(i+1)&3]->pt.x;
1874 float dy = q->corners[i]->pt.y - q->corners[(i+1)&3]->pt.y;
1875 float d = dx*dx + dy*dy;
1876 if( q->edge_len > d )
1885 static bool processQuads(CvCBQuad *quads, int quad_count, CvSize pattern_size, int max_quad_buf_size,
1886 CvMemStorage * storage, CvCBCorner *corners, CvPoint2D32f *out_corners, int *out_corner_count, int & prev_sqr_size)
1888 if( quad_count <= 0 )
1893 // Find quad's neighbors
1894 icvFindQuadNeighbors( quads, quad_count );
1896 // allocate extra for adding in icvOrderFoundQuads
1897 CvCBQuad **quad_group = 0;
1898 CvCBCorner **corner_group = 0;
1900 quad_group = (CvCBQuad**)cvAlloc( sizeof(quad_group[0]) * max_quad_buf_size);
1901 corner_group = (CvCBCorner**)cvAlloc( sizeof(corner_group[0]) * max_quad_buf_size * 4 );
1903 for( int group_idx = 0; ; group_idx++ )
1905 int count = icvFindConnectedQuads( quads, quad_count, quad_group, group_idx, storage );
1910 // order the quad corners globally
1911 // maybe delete or add some
1912 PRINTF("Starting ordering of inner quads (%d)\n", count);
1913 count = icvOrderFoundConnectedQuads(count, quad_group, &quad_count, &quads, &corners,
1914 pattern_size, max_quad_buf_size, storage );
1915 PRINTF("Finished ordering of inner quads (%d)\n", count);
1918 continue; // haven't found inner quads
1920 // If count is more than it should be, this will remove those quads
1921 // which cause maximum deviation from a nice square pattern.
1922 count = icvCleanFoundConnectedQuads( count, quad_group, pattern_size );
1923 PRINTF("Connected group: %d, count: %d\n", group_idx, count);
1925 count = icvCheckQuadGroup( quad_group, count, corner_group, pattern_size );
1926 PRINTF("Connected group: %d, count: %d\n", group_idx, count);
1928 int n = count > 0 ? pattern_size.width * pattern_size.height : -count;
1929 n = MIN( n, pattern_size.width * pattern_size.height );
1933 for(int i = 0; i < n; i++ )
1936 float avgi = corner_group[i]->meanDist(&ni);
1937 sum_dist += avgi*ni;
1940 prev_sqr_size = cvRound(sum_dist/MAX(total, 1));
1942 if( count > 0 || (out_corner_count && -count > *out_corner_count) )
1944 // copy corners to output array
1945 for(int i = 0; i < n; i++ )
1946 out_corners[i] = corner_group[i]->pt;
1948 if( out_corner_count )
1949 *out_corner_count = n;
1951 if( count == pattern_size.width*pattern_size.height
1952 && icvCheckBoardMonotony( out_corners, pattern_size ))
1960 cvFree(&quad_group);
1961 cvFree(&corner_group);
1966 //==================================================================================================
1969 cvDrawChessboardCorners( CvArr* _image, CvSize pattern_size,
1970 CvPoint2D32f* corners, int count, int found )
1972 const int shift = 0;
1973 const int radius = 4;
1974 const int r = radius*(1 << shift);
1978 int type, cn, line_type;
1980 image = cvGetMat( _image, &stub );
1982 type = CV_MAT_TYPE(image->type);
1983 cn = CV_MAT_CN(type);
1984 if( cn != 1 && cn != 3 && cn != 4 )
1985 CV_Error( CV_StsUnsupportedFormat, "Number of channels must be 1, 3 or 4" );
1987 switch( CV_MAT_DEPTH(image->type) )
1999 CV_Error( CV_StsUnsupportedFormat,
2000 "Only 8-bit, 16-bit or floating-point 32-bit images are supported" );
2003 line_type = type == CV_8UC1 || type == CV_8UC3 ? CV_AA : 8;
2007 CvScalar color(0,0,255,0);
2009 color = cvScalarAll(200);
2010 color.val[0] *= scale;
2011 color.val[1] *= scale;
2012 color.val[2] *= scale;
2013 color.val[3] *= scale;
2015 for( i = 0; i < count; i++ )
2018 pt.x = cvRound(corners[i].x*(1 << shift));
2019 pt.y = cvRound(corners[i].y*(1 << shift));
2020 cvLine( image, cvPoint( pt.x - r, pt.y - r ),
2021 cvPoint( pt.x + r, pt.y + r ), color, 1, line_type, shift );
2022 cvLine( image, cvPoint( pt.x - r, pt.y + r),
2023 cvPoint( pt.x + r, pt.y - r), color, 1, line_type, shift );
2024 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift );
2031 const int line_max = 7;
2032 static const CvScalar line_colors[line_max] =
2035 CvScalar(0,128,255),
2036 CvScalar(0,200,200),
2038 CvScalar(200,200,0),
2043 for( y = 0, i = 0; y < pattern_size.height; y++ )
2045 CvScalar color = line_colors[y % line_max];
2047 color = cvScalarAll(200);
2048 color.val[0] *= scale;
2049 color.val[1] *= scale;
2050 color.val[2] *= scale;
2051 color.val[3] *= scale;
2053 for( x = 0; x < pattern_size.width; x++, i++ )
2056 pt.x = cvRound(corners[i].x*(1 << shift));
2057 pt.y = cvRound(corners[i].y*(1 << shift));
2060 cvLine( image, prev_pt, pt, color, 1, line_type, shift );
2062 cvLine( image, cvPoint(pt.x - r, pt.y - r),
2063 cvPoint(pt.x + r, pt.y + r), color, 1, line_type, shift );
2064 cvLine( image, cvPoint(pt.x - r, pt.y + r),
2065 cvPoint(pt.x + r, pt.y - r), color, 1, line_type, shift );
2066 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift );
2073 bool cv::findChessboardCorners( InputArray _image, Size patternSize,
2074 OutputArray corners, int flags )
2076 CV_INSTRUMENT_REGION()
2078 int count = patternSize.area()*2;
2079 std::vector<Point2f> tmpcorners(count+1);
2080 Mat image = _image.getMat(); CvMat c_image = image;
2081 bool ok = cvFindChessboardCorners(&c_image, patternSize,
2082 (CvPoint2D32f*)&tmpcorners[0], &count, flags ) > 0;
2085 tmpcorners.resize(count);
2086 Mat(tmpcorners).copyTo(corners);
2095 int quiet_error(int /*status*/, const char* /*func_name*/,
2096 const char* /*err_msg*/, const char* /*file_name*/,
2097 int /*line*/, void* /*userdata*/ )
2103 void cv::drawChessboardCorners( InputOutputArray _image, Size patternSize,
2104 InputArray _corners,
2105 bool patternWasFound )
2107 CV_INSTRUMENT_REGION()
2109 Mat corners = _corners.getMat();
2110 if( corners.empty() )
2112 Mat image = _image.getMat(); CvMat c_image = image;
2113 int nelems = corners.checkVector(2, CV_32F, true);
2114 CV_Assert(nelems >= 0);
2115 cvDrawChessboardCorners( &c_image, patternSize, corners.ptr<CvPoint2D32f>(),
2116 nelems, patternWasFound );
2119 bool cv::findCirclesGrid( InputArray _image, Size patternSize,
2120 OutputArray _centers, int flags, const Ptr<FeatureDetector> &blobDetector,
2121 const CirclesGridFinderParameters& parameters_)
2123 CV_INSTRUMENT_REGION()
2125 CirclesGridFinderParameters parameters = parameters_; // parameters.gridType is amended below
2127 bool isAsymmetricGrid = (flags & CALIB_CB_ASYMMETRIC_GRID) ? true : false;
2128 bool isSymmetricGrid = (flags & CALIB_CB_SYMMETRIC_GRID ) ? true : false;
2129 CV_Assert(isAsymmetricGrid ^ isSymmetricGrid);
2131 Mat image = _image.getMat();
2132 std::vector<Point2f> centers;
2134 std::vector<KeyPoint> keypoints;
2135 blobDetector->detect(image, keypoints);
2136 std::vector<Point2f> points;
2137 for (size_t i = 0; i < keypoints.size(); i++)
2139 points.push_back (keypoints[i].pt);
2142 if(flags & CALIB_CB_ASYMMETRIC_GRID)
2143 parameters.gridType = CirclesGridFinderParameters::ASYMMETRIC_GRID;
2144 if(flags & CALIB_CB_SYMMETRIC_GRID)
2145 parameters.gridType = CirclesGridFinderParameters::SYMMETRIC_GRID;
2147 if(flags & CALIB_CB_CLUSTERING)
2149 CirclesGridClusterFinder circlesGridClusterFinder(parameters);
2150 circlesGridClusterFinder.findGrid(points, patternSize, centers);
2151 Mat(centers).copyTo(_centers);
2152 return !centers.empty();
2155 const int attempts = 2;
2156 const size_t minHomographyPoints = 4;
2158 for (int i = 0; i < attempts; i++)
2161 CirclesGridFinder boxFinder(patternSize, points, parameters);
2162 bool isFound = false;
2166 ErrorCallback oldCbk = redirectError(quiet_error, 0, &oldCbkData);
2170 isFound = boxFinder.findHoles();
2172 CV_CATCH(Exception, e)
2177 redirectError(oldCbk, oldCbkData);
2181 switch(parameters.gridType)
2183 case CirclesGridFinderParameters::SYMMETRIC_GRID:
2184 boxFinder.getHoles(centers);
2186 case CirclesGridFinderParameters::ASYMMETRIC_GRID:
2187 boxFinder.getAsymmetricHoles(centers);
2190 CV_Error(CV_StsBadArg, "Unknown pattern type");
2196 transform(centers, orgPointsMat, H.inv());
2197 convertPointsFromHomogeneous(orgPointsMat, centers);
2199 Mat(centers).copyTo(_centers);
2203 boxFinder.getHoles(centers);
2204 if (i != attempts - 1)
2206 if (centers.size() < minHomographyPoints)
2208 H = CirclesGridFinder::rectifyGrid(boxFinder.getDetectedGridSize(), centers, points, points);
2211 Mat(centers).copyTo(_centers);
2215 bool cv::findCirclesGrid( InputArray _image, Size patternSize,
2216 OutputArray _centers, int flags, const Ptr<FeatureDetector> &blobDetector)
2218 return cv::findCirclesGrid(_image, patternSize, _centers, flags, blobDetector, CirclesGridFinderParameters());