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 \************************************************************************************/
61 //=====================================================================================
62 // Implementation for the enhanced calibration object detection
63 //=====================================================================================
65 #define MAX_CONTOUR_APPROX 7
67 typedef struct CvContourEx
74 //=====================================================================================
76 /// Corner info structure
77 /** This structure stores information about the chessboard corner.*/
78 typedef struct CvCBCorner
80 CvPoint2D32f pt; // Coordinates of the corner
81 int row; // Board row index
82 int count; // Number of neighbor corners
83 struct CvCBCorner* neighbors[4]; // Neighbor corners
87 //=====================================================================================
88 /// Quadrangle contour info structure
89 /** This structure stores information about the chessboard quadrange.*/
90 typedef struct CvCBQuad
92 int count; // Number of quad neibors
93 int group_idx; // quad group ID
94 float edge_len; // quad size characteristic
95 CvCBCorner *corners[4]; // Coordinates of quad corners
96 struct CvCBQuad *neighbors[4]; // Pointers of quad neighbors
100 //=====================================================================================
102 //static CvMat* debug_img = 0;
104 static int icvGenerateQuads( CvCBQuad **quads, CvCBCorner **corners,
105 CvMemStorage *storage, CvMat *image, int flags );
107 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count );
109 static int icvFindConnectedQuads( CvCBQuad *quads, int quad_count,
110 CvCBQuad **quad_group, int group_idx,
111 CvMemStorage* storage );
113 static int icvCheckQuadGroup( CvCBQuad **quad_group, int count,
114 CvCBCorner **out_corners, CvSize pattern_size );
116 static int icvCleanFoundConnectedQuads( int quad_count,
117 CvCBQuad **quads, CvSize pattern_size );
120 int cvFindChessboardCorners( const void* arr, CvSize pattern_size,
121 CvPoint2D32f* out_corners, int* out_corner_count,
124 const int min_dilations = 1;
125 const int max_dilations = 3;
128 CvMat* thresh_img = 0;
129 CvMemStorage* storage = 0;
131 CvCBQuad *quads = 0, **quad_group = 0;
132 CvCBCorner *corners = 0, **corner_group = 0;
134 if( out_corner_count )
135 *out_corner_count = 0;
137 CV_FUNCNAME( "cvFindChessBoardCornerGuesses2" );
141 int quad_count, group_idx, i, dilations;
142 CvMat stub, *img = (CvMat*)arr;
144 CV_CALL( img = cvGetMat( img, &stub ));
147 if( CV_MAT_DEPTH( img->type ) != CV_8U || CV_MAT_CN( img->type ) == 2 )
148 CV_ERROR( CV_StsUnsupportedFormat, "Only 8-bit grayscale or color images are supported" );
150 if( pattern_size.width <= 2 || pattern_size.height <= 2 )
151 CV_ERROR( CV_StsOutOfRange, "pattern should have at least 2x2 size" );
154 CV_ERROR( CV_StsNullPtr, "Null pointer to corners" );
156 CV_CALL( storage = cvCreateMemStorage(0) );
157 CV_CALL( thresh_img = cvCreateMat( img->rows, img->cols, CV_8UC1 ));
159 if( CV_MAT_CN(img->type) != 1 || (flags & CV_CALIB_CB_NORMALIZE_IMAGE) )
161 // equalize the input image histogram -
162 // that should make the contrast between "black" and "white" areas big enough
163 CV_CALL( norm_img = cvCreateMat( img->rows, img->cols, CV_8UC1 ));
165 if( CV_MAT_CN(img->type) != 1 )
167 CV_CALL( cvCvtColor( img, norm_img, CV_BGR2GRAY ));
171 if( flags & CV_CALIB_CB_NORMALIZE_IMAGE )
173 cvEqualizeHist( img, norm_img );
178 // Try our standard "1" dilation, but if the pattern is not found, iterate the whole procedure with higher dilations.
179 // This is necessary because some squares simply do not separate properly with a single dilation. However,
180 // we want to use the minimum number of dilations possible since dilations cause the squares to become smaller,
181 // making it difficult to detect smaller squares.
182 for( dilations = min_dilations; dilations <= max_dilations; dilations++ )
184 // convert the input grayscale image to binary (black-n-white)
185 if( flags & CV_CALIB_CB_ADAPTIVE_THRESH )
187 int block_size = cvRound(MIN(img->cols,img->rows)*0.2)|1;
188 cvDilate( img, thresh_img, 0, dilations );
191 cvAdaptiveThreshold( img, thresh_img, 255,
192 CV_ADAPTIVE_THRESH_MEAN_C, CV_THRESH_BINARY, block_size, 0 );
193 cvDilate( thresh_img, thresh_img, 0, dilations-1 );
197 // Make dilation before the thresholding.
198 // It splits chessboard corners
199 //cvDilate( img, thresh_img, 0, 1 );
201 // empiric threshold level
202 double mean = cvMean( img );
203 int thresh_level = cvRound( mean - 10 );
204 thresh_level = MAX( thresh_level, 10 );
206 cvThreshold( img, thresh_img, thresh_level, 255, CV_THRESH_BINARY );
207 cvDilate( thresh_img, thresh_img, 0, dilations );
210 // So we can find rectangles that go to the edge, we draw a white line around the image edge.
211 // Otherwise FindContours will miss those clipped rectangle contours.
212 // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()...
213 cvRectangle( thresh_img, cvPoint(0,0), cvPoint(thresh_img->cols-1,
214 thresh_img->rows-1), CV_RGB(255,255,255), 3, 8);
216 CV_CALL( quad_count = icvGenerateQuads( &quads, &corners, storage, thresh_img, flags ));
217 if( quad_count <= 0 )
220 // Find quad's neighbors
221 CV_CALL( icvFindQuadNeighbors( quads, quad_count ));
223 CV_CALL( quad_group = (CvCBQuad**)cvAlloc( sizeof(quad_group[0]) * quad_count));
224 CV_CALL( corner_group = (CvCBCorner**)cvAlloc( sizeof(corner_group[0]) * quad_count*4 ));
226 for( group_idx = 0; ; group_idx++ )
229 CV_CALL( count = icvFindConnectedQuads( quads, quad_count, quad_group, group_idx, storage ));
234 // If count is more than it should be, this will remove those quads
235 // which cause maximum deviation from a nice square pattern.
236 CV_CALL( count = icvCleanFoundConnectedQuads( count, quad_group, pattern_size ));
237 CV_CALL( count = icvCheckQuadGroup( quad_group, count, corner_group, pattern_size ));
239 if( count > 0 || (out_corner_count && -count > *out_corner_count) )
241 int n = count > 0 ? pattern_size.width * pattern_size.height : -count;
242 n = MIN( n, pattern_size.width * pattern_size.height );
244 // copy corners to output array
245 for( i = 0; i < n; i++ )
246 out_corners[i] = corner_group[i]->pt;
248 if( out_corner_count )
249 *out_corner_count = n;
265 cvReleaseMemStorage( &storage );
266 cvReleaseMat( &norm_img );
267 cvReleaseMat( &thresh_img );
270 cvFree( &quad_group );
271 cvFree( &corner_group );
277 // if we found too many connect quads, remove those which probably do not belong.
279 icvCleanFoundConnectedQuads( int quad_count, CvCBQuad **quad_group, CvSize pattern_size )
281 CvMemStorage *temp_storage = 0;
282 CvPoint2D32f *centers = 0;
284 CV_FUNCNAME( "icvCleanFoundConnectedQuads" );
288 CvPoint2D32f center = {0,0};
290 // number of quads this pattern should contain
291 int count = ((pattern_size.width + 1)*(pattern_size.height + 1) + 1)/2;
293 // if we have more quadrangles than we should,
294 // try to eliminate duplicates or ones which don't belong to the pattern rectangle...
295 if( quad_count <= count )
298 // create an array of quadrangle centers
299 CV_CALL( centers = (CvPoint2D32f *)cvAlloc( sizeof(centers[0])*quad_count ));
300 CV_CALL( temp_storage = cvCreateMemStorage(0));
302 for( i = 0; i < quad_count; i++ )
304 CvPoint2D32f ci = {0,0};
305 CvCBQuad* q = quad_group[i];
307 for( j = 0; j < 4; j++ )
309 CvPoint2D32f pt = q->corners[j]->pt;
321 center.x /= quad_count;
322 center.y /= quad_count;
324 // If we still have more quadrangles than we should,
325 // we try to eliminate bad ones based on minimizing the bounding box.
326 // We iteratively remove the point which reduces the size of
327 // the bounding box of the blobs the most
328 // (since we want the rectangle to be as small as possible)
329 // remove the quadrange that causes the biggest reduction
330 // in pattern size until we have the correct number
331 for( ; quad_count > count; quad_count-- )
333 double min_box_area = DBL_MAX;
334 int skip, min_box_area_index = -1;
337 // For each point, calculate box area without that point
338 for( skip = 0; skip < quad_count; skip++ )
340 // get bounding rectangle
341 CvPoint2D32f temp = centers[skip]; // temporarily make index 'skip' the same as
342 centers[skip] = center; // pattern center (so it is not counted for convex hull)
343 CvMat pointMat = cvMat(1, quad_count, CV_32FC2, centers);
344 CvSeq *hull = cvConvexHull2( &pointMat, temp_storage, CV_CLOCKWISE, 1 );
345 centers[skip] = temp;
346 double hull_area = fabs(cvContourArea(hull, CV_WHOLE_SEQ));
348 // remember smallest box area
349 if( hull_area < min_box_area )
351 min_box_area = hull_area;
352 min_box_area_index = skip;
354 cvClearMemStorage( temp_storage );
357 q0 = quad_group[min_box_area_index];
359 // remove any references to this quad as a neighbor
360 for( i = 0; i < quad_count; i++ )
363 for( j = 0; j < 4; j++ )
365 if( q->neighbors[j] == q0 )
369 for( k = 0; k < 4; k++ )
370 if( q0->neighbors[k] == q )
372 q0->neighbors[k] = 0;
383 quad_group[min_box_area_index] = quad_group[quad_count];
384 centers[min_box_area_index] = centers[quad_count];
389 cvReleaseMemStorage( &temp_storage );
395 //=====================================================================================
398 icvFindConnectedQuads( CvCBQuad *quad, int quad_count, CvCBQuad **out_group,
399 int group_idx, CvMemStorage* storage )
401 CvMemStorage* temp_storage = cvCreateChildMemStorage( storage );
402 CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage );
405 // Scan the array for a first unlabeled quad
406 for( i = 0; i < quad_count; i++ )
408 if( quad[i].count > 0 && quad[i].group_idx < 0)
412 // Recursively find a group of connected quads starting from the seed quad[i]
415 CvCBQuad* q = &quad[i];
416 cvSeqPush( stack, &q );
417 out_group[count++] = q;
418 q->group_idx = group_idx;
420 while( stack->total )
422 cvSeqPop( stack, &q );
423 for( i = 0; i < 4; i++ )
425 CvCBQuad *neighbor = q->neighbors[i];
426 if( neighbor && neighbor->count > 0 && neighbor->group_idx < 0 )
428 cvSeqPush( stack, &neighbor );
429 out_group[count++] = neighbor;
430 neighbor->group_idx = group_idx;
436 cvReleaseMemStorage( &temp_storage );
441 //=====================================================================================
444 icvCheckQuadGroup( CvCBQuad **quad_group, int quad_count,
445 CvCBCorner **out_corners, CvSize pattern_size )
447 const int ROW1 = 1000000;
448 const int ROW2 = 2000000;
449 const int ROW_ = 3000000;
451 int i, out_corner_count = 0, corner_count = 0;
452 CvCBCorner** corners = 0;
454 CV_FUNCNAME( "icvCheckQuadGroup" );
459 int width = 0, height = 0;
460 int hist[5] = {0,0,0,0,0};
461 CvCBCorner* first = 0, *first2 = 0, *right, *cur, *below, *c;
462 CV_CALL( corners = (CvCBCorner**)cvAlloc( quad_count*4*sizeof(corners[0]) ));
464 // build dual graph, which vertices are internal quad corners
465 // and two vertices are connected iff they lie on the same quad edge
466 for( i = 0; i < quad_count; i++ )
468 CvCBQuad* q = quad_group[i];
469 /*CvScalar color = q->count == 0 ? cvScalar(0,255,255) :
470 q->count == 1 ? cvScalar(0,0,255) :
471 q->count == 2 ? cvScalar(0,255,0) :
472 q->count == 3 ? cvScalar(255,255,0) :
475 for( j = 0; j < 4; j++ )
477 //cvLine( debug_img, cvPointFrom32f(q->corners[j]->pt), cvPointFrom32f(q->corners[(j+1)&3]->pt), color, 1, CV_AA, 0 );
478 if( q->neighbors[j] )
480 CvCBCorner *a = q->corners[j], *b = q->corners[(j+1)&3];
481 // mark internal corners that belong to:
482 // - a quad with a single neighbor - with ROW1,
483 // - a quad with two neighbors - with ROW2
484 // make the rest of internal corners with ROW_
485 int row_flag = q->count == 1 ? ROW1 : q->count == 2 ? ROW2 : ROW_;
489 corners[corner_count++] = a;
492 else if( a->row > row_flag )
495 if( q->neighbors[(j+1)&3] )
497 if( a->count >= 4 || b->count >= 4 )
499 for( k = 0; k < 4; k++ )
501 if( a->neighbors[k] == b )
503 if( b->neighbors[k] == a )
506 a->neighbors[a->count++] = b;
507 b->neighbors[b->count++] = a;
513 if( corner_count != pattern_size.width*pattern_size.height )
516 for( i = 0; i < corner_count; i++ )
518 int n = corners[i]->count;
519 assert( 0 <= n && n <= 4 );
521 if( !first && n == 2 )
523 if( corners[i]->row == ROW1 )
525 else if( !first2 && corners[i]->row == ROW2 )
530 // start with a corner that belongs to a quad with a signle neighbor.
531 // if we do not have such, start with a corner of a quad with two neighbors.
535 if( !first || hist[0] != 0 || hist[1] != 0 || hist[2] != 4 ||
536 hist[3] != (pattern_size.width + pattern_size.height)*2 - 8 )
541 out_corners[out_corner_count++] = cur;
543 for( k = 0; k < 4; k++ )
545 c = cur->neighbors[k];
555 if( !right || right->count != 2 && right->count != 3 ||
556 !below || below->count != 2 && below->count != 3 )
560 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,255,0), -1, 8, 0 );
562 first = below; // remember the first corner in the next row
563 // find and store the first row (or column)
567 out_corners[out_corner_count++] = right;
568 //cvCircle( debug_img, cvPointFrom32f(right->pt), 3, cvScalar(0,255-j*10,0), -1, 8, 0 );
569 if( right->count == 2 )
571 if( right->count != 3 || out_corner_count >= MAX(pattern_size.width,pattern_size.height) )
574 for( k = 0; k < 4; k++ )
576 c = cur->neighbors[k];
577 if( c && c->row > 0 )
579 for( kk = 0; kk < 4; kk++ )
581 if( c->neighbors[kk] == below )
592 width = out_corner_count;
593 if( width == pattern_size.width )
594 height = pattern_size.height;
595 else if( width == pattern_size.height )
596 height = pattern_size.width;
600 // find and store all the other rows
610 out_corners[out_corner_count++] = cur;
611 //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,0,255-j*10), -1, 8, 0 );
612 if( cur->count == 2 + (i < height-1) && j > 0 )
617 // find a neighbor that has not been processed yet
618 // and that has a neighbor from the previous row
619 for( k = 0; k < 4; k++ )
621 c = cur->neighbors[k];
622 if( c && c->row > i )
624 for( kk = 0; kk < 4; kk++ )
626 if( c->neighbors[kk] && c->neighbors[kk]->row == i-1 )
648 if( out_corner_count != corner_count )
651 // check if we need to transpose the board
652 if( width != pattern_size.width )
654 CV_SWAP( width, height, k );
656 memcpy( corners, out_corners, corner_count*sizeof(corners[0]) );
657 for( i = 0; i < height; i++ )
658 for( j = 0; j < width; j++ )
659 out_corners[i*width + j] = corners[j*height + i];
662 // check if we need to revert the order in each row
664 CvPoint2D32f p0 = out_corners[0]->pt, p1 = out_corners[pattern_size.width-1]->pt,
665 p2 = out_corners[pattern_size.width]->pt;
666 if( (p1.x - p0.x)*(p2.y - p1.y) - (p1.y - p0.y)*(p2.x - p1.x) < 0 )
670 for( i = 0; i < height; i++ )
671 for( j = 0; j < width/2; j++ )
672 CV_SWAP( out_corners[i*width+j], out_corners[i*width+width-j-1], c );
676 for( j = 0; j < width; j++ )
677 for( i = 0; i < height/2; i++ )
678 CV_SWAP( out_corners[i*width+j], out_corners[(height - i - 1)*width+j], c );
683 result = corner_count;
687 if( result <= 0 && corners )
689 corner_count = MIN( corner_count, pattern_size.width*pattern_size.height );
690 for( i = 0; i < corner_count; i++ )
691 out_corners[i] = corners[i];
692 result = -corner_count;
700 //=====================================================================================
702 static void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count )
704 const float thresh_scale = 1.f;
708 // find quad neighbors
709 for( idx = 0; idx < quad_count; idx++ )
711 CvCBQuad* cur_quad = &quads[idx];
713 // choose the points of the current quadrangle that are close to
714 // some points of the other quadrangles
715 // (it can happen for split corners (due to dilation) of the
716 // checker board). Search only in other quadrangles!
718 // for each corner of this quadrangle
719 for( i = 0; i < 4; i++ )
722 float min_dist = FLT_MAX;
723 int closest_corner_idx = -1;
724 CvCBQuad *closest_quad = 0;
725 CvCBCorner *closest_corner = 0;
727 if( cur_quad->neighbors[i] )
730 pt = cur_quad->corners[i]->pt;
732 // find the closest corner in all other quadrangles
733 for( k = 0; k < quad_count; k++ )
738 for( j = 0; j < 4; j++ )
740 if( quads[k].neighbors[j] )
743 dx = pt.x - quads[k].corners[j]->pt.x;
744 dy = pt.y - quads[k].corners[j]->pt.y;
745 dist = dx * dx + dy * dy;
747 if( dist < min_dist &&
748 dist <= cur_quad->edge_len*thresh_scale &&
749 dist <= quads[k].edge_len*thresh_scale )
751 closest_corner_idx = j;
752 closest_quad = &quads[k];
758 // we found a matching corner point?
759 if( closest_corner_idx >= 0 && min_dist < FLT_MAX )
761 // If another point from our current quad is closer to the found corner
762 // than the current one, then we don't count this one after all.
763 // This is necessary to support small squares where otherwise the wrong
764 // corner will get matched to closest_quad;
765 closest_corner = closest_quad->corners[closest_corner_idx];
767 for( j = 0; j < 4; j++ )
769 if( cur_quad->neighbors[j] == closest_quad )
772 dx = closest_corner->pt.x - cur_quad->corners[j]->pt.x;
773 dy = closest_corner->pt.y - cur_quad->corners[j]->pt.y;
775 if( dx * dx + dy * dy < min_dist )
779 if( j < 4 || cur_quad->count >= 4 || closest_quad->count >= 4 )
782 // Check that each corner is a neighbor of different quads
783 for( j = 0; j < closest_quad->count; j++ )
785 if( closest_quad->neighbors[j] == cur_quad )
788 if( j < closest_quad->count )
791 // check whether the closest corner to closest_corner
792 // is different from cur_quad->corners[i]->pt
793 for( k = 0; k < quad_count; k++ )
795 CvCBQuad* q = &quads[k];
796 if( k == idx || q == closest_quad )
799 for( j = 0; j < 4; j++ )
800 if( !q->neighbors[j] )
802 dx = closest_corner->pt.x - q->corners[j]->pt.x;
803 dy = closest_corner->pt.y - q->corners[j]->pt.y;
804 dist = dx*dx + dy*dy;
805 if( dist < min_dist )
815 closest_corner->pt.x = (pt.x + closest_corner->pt.x) * 0.5f;
816 closest_corner->pt.y = (pt.y + closest_corner->pt.y) * 0.5f;
818 // We've found one more corner - remember it
820 cur_quad->neighbors[i] = closest_quad;
821 cur_quad->corners[i] = closest_corner;
823 closest_quad->count++;
824 closest_quad->neighbors[closest_corner_idx] = cur_quad;
830 //=====================================================================================
833 icvGenerateQuads( CvCBQuad **out_quads, CvCBCorner **out_corners,
834 CvMemStorage *storage, CvMat *image, int flags )
837 CvMemStorage *temp_storage = 0;
845 CV_FUNCNAME( "icvGenerateQuads" );
849 CvSeq *src_contour = 0;
851 CvContourEx* board = 0;
852 CvContourScanner scanner;
853 int i, idx, min_size;
855 CV_ASSERT( out_corners && out_quads );
857 // empiric bound for minimal allowed perimeter for squares
858 min_size = cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 );
860 // create temporary storage for contours and the sequence of pointers to found quadrangles
861 CV_CALL( temp_storage = cvCreateChildMemStorage( storage ));
862 CV_CALL( root = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage ));
864 // initialize contour retrieving routine
865 CV_CALL( scanner = cvStartFindContours( image, temp_storage, sizeof(CvContourEx),
866 CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE ));
868 // get all the contours one by one
869 while( (src_contour = cvFindNextContour( scanner )) != 0 )
871 CvSeq *dst_contour = 0;
872 CvRect rect = ((CvContour*)src_contour)->rect;
874 // reject contours with too small perimeter
875 if( CV_IS_SEQ_HOLE(src_contour) && rect.width*rect.height >= min_size )
877 const int min_approx_level = 2, max_approx_level = MAX_CONTOUR_APPROX;
879 for( approx_level = min_approx_level; approx_level <= max_approx_level; approx_level++ )
881 dst_contour = cvApproxPoly( src_contour, sizeof(CvContour), temp_storage,
882 CV_POLY_APPROX_DP, (float)approx_level );
883 // we call this again on its own output, because sometimes
884 // cvApproxPoly() does not simplify as much as it should.
885 dst_contour = cvApproxPoly( dst_contour, sizeof(CvContour), temp_storage,
886 CV_POLY_APPROX_DP, (float)approx_level );
888 if( dst_contour->total == 4 )
892 // reject non-quadrangles
893 if( dst_contour->total == 4 && cvCheckContourConvexity(dst_contour) )
896 double d1, d2, p = cvContourPerimeter(dst_contour);
897 double area = fabs(cvContourArea(dst_contour, CV_WHOLE_SEQ));
900 for( i = 0; i < 4; i++ )
901 pt[i] = *(CvPoint*)cvGetSeqElem(dst_contour, i);
903 dx = pt[0].x - pt[2].x;
904 dy = pt[0].y - pt[2].y;
905 d1 = sqrt(dx*dx + dy*dy);
907 dx = pt[1].x - pt[3].x;
908 dy = pt[1].y - pt[3].y;
909 d2 = sqrt(dx*dx + dy*dy);
911 // philipg. Only accept those quadrangles which are more square
912 // than rectangular and which are big enough
914 dx = pt[0].x - pt[1].x;
915 dy = pt[0].y - pt[1].y;
916 d3 = sqrt(dx*dx + dy*dy);
917 dx = pt[1].x - pt[2].x;
918 dy = pt[1].y - pt[2].y;
919 d4 = sqrt(dx*dx + dy*dy);
920 if( !(flags & CV_CALIB_CB_FILTER_QUADS) ||
921 d3*4 > d4 && d4*4 > d3 && d3*d4 < area*1.5 && area > min_size &&
922 d1 >= 0.15 * p && d2 >= 0.15 * p )
924 CvContourEx* parent = (CvContourEx*)(src_contour->v_prev);
926 if( !board || board->counter < parent->counter )
928 dst_contour->v_prev = (CvSeq*)parent;
929 //for( i = 0; i < 4; i++ ) cvLine( debug_img, pt[i], pt[(i+1)&3], cvScalar(200,255,255), 1, CV_AA, 0 );
930 cvSeqPush( root, &dst_contour );
936 // finish contour retrieving
937 cvEndFindContours( &scanner );
939 // allocate quad & corner buffers
940 CV_CALL( *out_quads = (CvCBQuad*)cvAlloc(root->total * sizeof((*out_quads)[0])));
941 CV_CALL( *out_corners = (CvCBCorner*)cvAlloc(root->total * 4 * sizeof((*out_corners)[0])));
943 // Create array of quads structures
944 for( idx = 0; idx < root->total; idx++ )
946 CvCBQuad* q = &(*out_quads)[quad_count];
947 src_contour = *(CvSeq**)cvGetSeqElem( root, idx );
948 if( (flags & CV_CALIB_CB_FILTER_QUADS) && src_contour->v_prev != (CvSeq*)board )
952 memset( q, 0, sizeof(*q) );
954 assert( src_contour->total == 4 );
955 for( i = 0; i < 4; i++ )
957 CvPoint2D32f pt = cvPointTo32f(*(CvPoint*)cvGetSeqElem(src_contour, i));
958 CvCBCorner* corner = &(*out_corners)[quad_count*4 + i];
960 memset( corner, 0, sizeof(*corner) );
962 q->corners[i] = corner;
964 q->edge_len = FLT_MAX;
965 for( i = 0; i < 4; i++ )
967 float dx = q->corners[i]->pt.x - q->corners[(i+1)&3]->pt.x;
968 float dy = q->corners[i]->pt.y - q->corners[(i+1)&3]->pt.y;
969 float d = dx*dx + dy*dy;
970 if( q->edge_len > d )
978 if( cvGetErrStatus() < 0 )
983 cvFree( out_corners );
987 cvReleaseMemStorage( &temp_storage );
993 cvDrawChessboardCorners( CvArr* _image, CvSize pattern_size,
994 CvPoint2D32f* corners, int count, int found )
996 CV_FUNCNAME( "cvDrawChessboardCorners" );
1000 const int shift = 0;
1001 const int radius = 4;
1002 const int r = radius*(1 << shift);
1006 int type, cn, line_type;
1008 CV_CALL( image = cvGetMat( _image, &stub ));
1010 type = CV_MAT_TYPE(image->type);
1011 cn = CV_MAT_CN(type);
1012 if( cn != 1 && cn != 3 && cn != 4 )
1013 CV_ERROR( CV_StsUnsupportedFormat, "Number of channels must be 1, 3 or 4" );
1015 switch( CV_MAT_DEPTH(image->type) )
1027 CV_ERROR( CV_StsUnsupportedFormat,
1028 "Only 8-bit, 16-bit or floating-point 32-bit images are supported" );
1031 line_type = type == CV_8UC1 || type == CV_8UC3 ? CV_AA : 8;
1035 CvScalar color = {{0,0,255}};
1037 color = cvScalarAll(200);
1038 color.val[0] *= scale;
1039 color.val[1] *= scale;
1040 color.val[2] *= scale;
1041 color.val[3] *= scale;
1043 for( i = 0; i < count; i++ )
1046 pt.x = cvRound(corners[i].x*(1 << shift));
1047 pt.y = cvRound(corners[i].y*(1 << shift));
1048 cvLine( image, cvPoint( pt.x - r, pt.y - r ),
1049 cvPoint( pt.x + r, pt.y + r ), color, 1, line_type, shift );
1050 cvLine( image, cvPoint( pt.x - r, pt.y + r),
1051 cvPoint( pt.x + r, pt.y - r), color, 1, line_type, shift );
1052 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift );
1058 CvPoint prev_pt = {0, 0};
1059 const int line_max = 7;
1060 static const CvScalar line_colors[line_max] =
1071 for( y = 0, i = 0; y < pattern_size.height; y++ )
1073 CvScalar color = line_colors[y % line_max];
1075 color = cvScalarAll(200);
1076 color.val[0] *= scale;
1077 color.val[1] *= scale;
1078 color.val[2] *= scale;
1079 color.val[3] *= scale;
1081 for( x = 0; x < pattern_size.width; x++, i++ )
1084 pt.x = cvRound(corners[i].x*(1 << shift));
1085 pt.y = cvRound(corners[i].y*(1 << shift));
1088 cvLine( image, prev_pt, pt, color, 1, line_type, shift );
1090 cvLine( image, cvPoint(pt.x - r, pt.y - r),
1091 cvPoint(pt.x + r, pt.y + r), color, 1, line_type, shift );
1092 cvLine( image, cvPoint(pt.x - r, pt.y + r),
1093 cvPoint(pt.x + r, pt.y - r), color, 1, line_type, shift );
1094 cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift );