16acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//M*////////////////////////////////////////////////////////////////////////////////////// 26acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 36acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 46acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 56acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// By downloading, copying, installing or using the software you agree to this license. 66acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// If you do not agree to this license, do not download, install, 76acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// copy or use the software. 86acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 96acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Intel License Agreement 116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// For Open Source Computer Vision Library 126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Copyright (C) 2000, Intel Corporation, all rights reserved. 146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Third party copyrights are property of their respective owners. 156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Redistribution and use in source and binary forms, with or without modification, 176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// are permitted provided that the following conditions are met: 186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's of source code must retain the above copyright notice, 206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer. 216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's in binary form must reproduce the above copyright notice, 236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer in the documentation 246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and/or other materials provided with the distribution. 256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * The name of Intel Corporation may not be used to endorse or promote products 276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// derived from this software without specific prior written permission. 286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// This software is provided by the copyright holders and contributors "as is" and 306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// any express or implied warranties, including, but not limited to, the implied 316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// warranties of merchantability and fitness for a particular purpose are disclaimed. 326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// In no event shall the Intel Corporation or contributors be liable for any direct, 336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// indirect, incidental, special, exemplary, or consequential damages 346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// (including, but not limited to, procurement of substitute goods or services; 356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// loss of use, data, or profits; or business interruption) however caused 366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and on any theory of liability, whether in contract, strict liability, 376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// or tort (including negligence or otherwise) arising in any way out of 386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// the use of this software, even if advised of the possibility of such damage. 396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//M*/ 416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/************************************************************************************\ 436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn This is improved variant of chessboard corner detection algorithm that 446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn uses a graph of connected quads. It is based on the code contributed 456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn by Vladimir Vezhnevets and Philip Gruebele. 466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Here is the copyright notice from the original Vladimir's code: 476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn =============================================================== 486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn The algorithms developed and implemented by Vezhnevets Vldimir 506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn aka Dead Moroz (vvp@graphics.cs.msu.ru) 516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn See http://graphics.cs.msu.su/en/research/calibration/opencv.html 526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for detailed information. 536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Reliability additions and modifications made by Philip Gruebele. 556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn <a href="mailto:pgruebele@cox.net">pgruebele@cox.net</a> 566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Some further improvements for detection of partially ocluded boards at non-ideal 586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lighting conditions have been made by Alex Bovyrin and Kurt Kolonige 596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\************************************************************************************/ 616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "_cv.h" 636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include <stdarg.h> 646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//#define DEBUG_CHESSBOARD 666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int PRINTF( const char* fmt, ... ) 686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn va_list args; 706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn va_start(args, fmt); 716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return vprintf(fmt, args); 726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "..//..//otherlibs/highgui/highgui.h" 746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#else 756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int PRINTF( const char*, ... ) 766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; 786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Implementation for the enhanced calibration object detection 846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define MAX_CONTOUR_APPROX 7 876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvContourEx 896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CONTOUR_FIELDS() 916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int counter; 926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvContourEx; 946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/// Corner info structure 986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/** This structure stores information about the chessboard corner.*/ 996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvCBCorner 1006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt; // Coordinates of the corner 1026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row; // Board row index 1036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int count; // Number of neighbor corners 1046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn struct CvCBCorner* neighbors[4]; // Neighbor corners 1056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvCBCorner; 1076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 1096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/// Quadrangle contour info structure 1106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/** This structure stores information about the chessboard quadrange.*/ 1116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct CvCBQuad 1126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int count; // Number of quad neighbors 1146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int group_idx; // quad group ID 1156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row, col; // row and column of this quad 1166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn bool ordered; // true if corners/neighbors are ordered counter-clockwise 1176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float edge_len; // quad edge len, in pix^2 1186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // neighbors and corners are synced, i.e., neighbor 0 shares corner 0 1196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner *corners[4]; // Coordinates of quad corners 1206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn struct CvCBQuad *neighbors[4]; // Pointers of quad neighbors 1216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvCBQuad; 1236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 1256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//static CvMat* debug_img = 0; 1276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvGenerateQuads( CvCBQuad **quads, CvCBCorner **corners, 1296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *storage, CvMat *image, int flags ); 1306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 1326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvGenerateQuadsEx( CvCBQuad **out_quads, CvCBCorner **out_corners, 1336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *storage, CvMat *image, CvMat *thresh_img, int dilation, int flags ); 1346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count ); 1366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvFindConnectedQuads( CvCBQuad *quads, int quad_count, 1386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad **quad_group, int group_idx, 1396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage ); 1406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvCheckQuadGroup( CvCBQuad **quad_group, int count, 1426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner **out_corners, CvSize pattern_size ); 1436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvCleanFoundConnectedQuads( int quad_count, 1456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad **quads, CvSize pattern_size ); 1466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads, 1486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *all_count, CvCBQuad **all_quads, CvCBCorner **corners, 1496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSize pattern_size, CvMemStorage* storage ); 1506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void icvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common); 1526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvTrimCol(CvCBQuad **quads, int count, int col, int dir); 1546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvTrimRow(CvCBQuad **quads, int count, int row, int dir); 1566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvAddOuterQuad(CvCBQuad *quad, CvCBQuad **quads, int quad_count, 1586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad **all_quads, int all_count, CvCBCorner **corners); 1596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void icvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0); 1616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int icvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size ); 1636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#if 0 1656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 1666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCalcAffineTranf2D32f(CvPoint2D32f* pts1, CvPoint2D32f* pts2, int count, CvMat* affine_trans) 1676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j; 1696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int real_count = 0; 1706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < count; j++ ) 1716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pts1[j].x >= 0 ) real_count++; 1736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if(real_count < 3) return; 1756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* xy = cvCreateMat( 2*real_count, 6, CV_32FC1 ); 1766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* uv = cvCreateMat( 2*real_count, 1, CV_32FC1 ); 1776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //estimate affine transfromation 1786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0, j = 0; j < count; j++ ) 1796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pts1[j].x >= 0 ) 1816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *xy, float, i*2+1, 2 ) = CV_MAT_ELEM( *xy, float, i*2, 0 ) = pts2[j].x; 1836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *xy, float, i*2+1, 3 ) = CV_MAT_ELEM( *xy, float, i*2, 1 ) = pts2[j].y; 1846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *xy, float, i*2, 2 ) = CV_MAT_ELEM( *xy, float, i*2, 3 ) = CV_MAT_ELEM( *xy, float, i*2, 5 ) = \ 1856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *xy, float, i*2+1, 0 ) = CV_MAT_ELEM( *xy, float, i*2+1, 1 ) = CV_MAT_ELEM( *xy, float, i*2+1, 4 ) = 0; 1866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *xy, float, i*2, 4 ) = CV_MAT_ELEM( *xy, float, i*2+1, 5 ) = 1; 1876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *uv, float, i*2, 0 ) = pts1[j].x; 1886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MAT_ELEM( *uv, float, i*2+1, 0 ) = pts1[j].y; 1896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i++; 1906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSolve( xy, uv, affine_trans, CV_SVD ); 1946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat(&xy); 1956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat(&uv); 1966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 1986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL 2006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennint cvFindChessboardCorners( const void* arr, CvSize pattern_size, 2016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f* out_corners, int* out_corner_count, 2026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int flags ) 2036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 2046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int k = 0; 2056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int min_dilations = 0; 2066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int max_dilations = 3; 2076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int found = 0; 2086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* norm_img = 0; 2096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat* thresh_img = 0; 2106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 2116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IplImage *dbg_img = 0; 2126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IplImage *dbg1_img = 0; 2136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IplImage *dbg2_img = 0; 2146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 2156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage = 0; 2166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *quads = 0, **quad_group = 0; 2186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner *corners = 0, **corner_group = 0; 2196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int expected_corners_num = (pattern_size.width/2+1)*(pattern_size.height/2+1); 2216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corner_count ) 2236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *out_corner_count = 0; 2246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvFindChessBoardCornerGuesses2" ); 2266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 2286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int quad_count = 0, group_idx = 0, i = 0, dilations = 0; 2306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat stub, *img = (CvMat*)arr; 2316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( img = cvGetMat( img, &stub )); 2336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //debug_img = img; 2346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_DEPTH( img->type ) != CV_8U || CV_MAT_CN( img->type ) == 2 ) 2366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnsupportedFormat, "Only 8-bit grayscale or color images are supported" ); 2376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pattern_size.width <= 2 || pattern_size.height <= 2 ) 2396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "Both width and height of the pattern should have bigger than 2" ); 2406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !out_corners ) 2426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "Null pointer to corners" ); 2436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( storage = cvCreateMemStorage(0) ); 2456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( thresh_img = cvCreateMat( img->rows, img->cols, CV_8UC1 )); 2466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 2486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( dbg_img = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 3 )); 2496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( dbg1_img = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 3 )); 2506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( dbg2_img = cvCreateImage(cvGetSize(img), IPL_DEPTH_8U, 3 )); 2516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 2526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_CN(img->type) != 1 || (flags & CV_CALIB_CB_NORMALIZE_IMAGE) ) 2546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // equalize the input image histogram - 2566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // that should make the contrast between "black" and "white" areas big enough 2576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( norm_img = cvCreateMat( img->rows, img->cols, CV_8UC1 )); 2586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_MAT_CN(img->type) != 1 ) 2606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( cvCvtColor( img, norm_img, CV_BGR2GRAY )); 2626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn img = norm_img; 2636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( flags & CV_CALIB_CB_NORMALIZE_IMAGE ) 2666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvEqualizeHist( img, norm_img ); 2686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn img = norm_img; 2696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Try our standard "1" dilation, but if the pattern is not found, iterate the whole procedure with higher dilations. 2736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // This is necessary because some squares simply do not separate properly with a single dilation. However, 2746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // we want to use the minimum number of dilations possible since dilations cause the squares to become smaller, 2756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // making it difficult to detect smaller squares. 2766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 2; k++ ) 2776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( dilations = min_dilations; dilations <= max_dilations; dilations++ ) 2796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (found) break; // already found it 2816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k == 1 ) 2836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //Pattern was not found using binarization 2856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Run multi-level quads extraction 2866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // In case one-level binarization did not give enough number of quads 2876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( quad_count = icvGenerateQuadsEx( &quads, &corners, storage, img, thresh_img, dilations, flags )); 2886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("EX quad count: %d/%d\n", quad_count, expected_corners_num); 2896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // convert the input grayscale image to binary (black-n-white) 2936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( flags & CV_CALIB_CB_ADAPTIVE_THRESH ) 2946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int block_size = cvRound(MIN(img->cols,img->rows)*0.2)|1; 2966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // convert to binary 2986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvAdaptiveThreshold( img, thresh_img, 255, 2996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ADAPTIVE_THRESH_MEAN_C, CV_THRESH_BINARY, block_size, 0 ); 3006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (dilations > 0) 3016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvDilate( thresh_img, thresh_img, 0, dilations-1 ); 3026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Make dilation before the thresholding. 3066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // It splits chessboard corners 3076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //cvDilate( img, thresh_img, 0, 1 ); 3086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // empiric threshold level 3106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double mean = cvMean( img ); 3116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int thresh_level = cvRound( mean - 10 ); 3126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn thresh_level = MAX( thresh_level, 10 ); 3136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvThreshold( img, thresh_img, thresh_level, 255, CV_THRESH_BINARY ); 3156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvDilate( thresh_img, thresh_img, 0, dilations ); 3166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 3216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCvtColor(thresh_img,dbg_img,CV_GRAY2BGR); 3226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 3236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // So we can find rectangles that go to the edge, we draw a white line around the image edge. 3256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Otherwise FindContours will miss those clipped rectangle contours. 3266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // The border color will be the image mean, because otherwise we risk screwing up filters like cvSmooth()... 3276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvRectangle( thresh_img, cvPoint(0,0), cvPoint(thresh_img->cols-1, 3286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn thresh_img->rows-1), CV_RGB(255,255,255), 3, 8); 3296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( quad_count = icvGenerateQuads( &quads, &corners, storage, thresh_img, flags )); 3316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Quad count: %d/%d\n", quad_count, expected_corners_num); 3346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 3386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCopy(dbg_img, dbg1_img); 3396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvNamedWindow("all_quads", 1); 3406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // copy corners to temp array 3416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < quad_count; i++ ) 3426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int k=0; k<4; k++) 3446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt1, pt2; 3466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvScalar color = CV_RGB(30,255,30); 3476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1 = quads[i].corners[k]->pt; 3486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2 = quads[i].corners[(k+1)%4]->pt; 3496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2.x = (pt1.x + pt2.x)/2; 3506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2.y = (pt1.y + pt2.y)/2; 3516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (k>0) 3526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color = CV_RGB(200,200,0); 3536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( dbg1_img, cvPointFrom32f(pt1), cvPointFrom32f(pt2), color, 3, 8); 3546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// cvShowImage("all_quads", (IplImage*)dbg1_img); 3596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvWaitKey(); 3606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 3616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( quad_count <= 0 ) 3646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 3656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Find quad's neighbors 3676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( icvFindQuadNeighbors( quads, quad_count )); 3686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // allocate extra for adding in icvOrderFoundQuads 3706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( quad_group = (CvCBQuad**)cvAlloc( sizeof(quad_group[0]) * (quad_count+quad_count / 2))); 3716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( corner_group = (CvCBCorner**)cvAlloc( sizeof(corner_group[0]) * (quad_count+quad_count / 2)*4 )); 3726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( group_idx = 0; ; group_idx++ ) 3746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int count = 0; 3766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( count = icvFindConnectedQuads( quads, quad_count, quad_group, group_idx, storage )); 3776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int icount = count; 3796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( count == 0 ) 3806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 3816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // order the quad corners globally 3836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // maybe delete or add some 3846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Starting ordering of inner quads\n"); 3856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = icvOrderFoundConnectedQuads(count, quad_group, &quad_count, &quads, &corners, 3866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pattern_size, storage ); 3876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Orig count: %d After ordering: %d\n", icount, count); 3886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 3916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCopy(dbg_img,dbg2_img); 3926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvNamedWindow("connected_group", 1); 3936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // copy corners to temp array 3946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < quad_count; i++ ) 3956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i].group_idx == group_idx) 3976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int k=0; k<4; k++) 3986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt1, pt2; 4006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvScalar color = CV_RGB(30,255,30); 4016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i].ordered) 4026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color = CV_RGB(255,30,30); 4036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1 = quads[i].corners[k]->pt; 4046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2 = quads[i].corners[(k+1)%4]->pt; 4056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2.x = (pt1.x + pt2.x)/2; 4066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2.y = (pt1.y + pt2.y)/2; 4076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (k>0) 4086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color = CV_RGB(200,200,0); 4096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( dbg2_img, cvPointFrom32f(pt1), cvPointFrom32f(pt2), color, 3, 8); 4106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// cvShowImage("connected_group", (IplImage*)dbg2_img); 4136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvWaitKey(); 4146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 4156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (count == 0) 4176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; // haven't found inner quads 4186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // If count is more than it should be, this will remove those quads 4216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // which cause maximum deviation from a nice square pattern. 4226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( count = icvCleanFoundConnectedQuads( count, quad_group, pattern_size )); 4236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Connected group: %d orig count: %d cleaned: %d\n", group_idx, icount, count); 4246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( count = icvCheckQuadGroup( quad_group, count, corner_group, pattern_size )); 4266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Connected group: %d count: %d cleaned: %d\n", group_idx, icount, count); 4276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( count > 0 || (out_corner_count && -count > *out_corner_count) ) 4296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int n = count > 0 ? pattern_size.width * pattern_size.height : -count; 4316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn n = MIN( n, pattern_size.width * pattern_size.height ); 4326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // copy corners to output array 4346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < n; i++ ) 4356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_corners[i] = corner_group[i]->pt; 4366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corner_count ) 4386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *out_corner_count = n; 4396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( count > 0 ) 4416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn found = 1; 4436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &quads ); 4496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &corners ); 4506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &quad_group ); 4516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &corner_group ); 4526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn }//dilations 4536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn }// 4546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 4576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &storage ); 4596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &norm_img ); 4606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMat( &thresh_img ); 4616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &quads ); 4626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &corners ); 4636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( found ) 4656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn found = icvCheckBoardMonotony( out_corners, pattern_size ); 4666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( found && pattern_size.height % 2 == 0 && pattern_size.width % 2 == 0 ) 4686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int last_row = (pattern_size.height-1)*pattern_size.width; 4706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double dy0 = out_corners[last_row].y - out_corners[0].y; 4716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dy0 < 0 ) 4726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, n = pattern_size.width*pattern_size.height; 4746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < n/2; i++ ) 4756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f temp; 4776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SWAP(out_corners[i], out_corners[n-i-1], temp); 4786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return found; 4836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 4846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 4866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Checks that each board row and column is pretty much monotonous curve: 4876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// It analyzes each row and each column of the chessboard as following: 4886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// for each corner c lying between end points in the same row/column it checks that 4896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// the point projection to the line segment (a,b) is lying between projections 4906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// of the neighbor corners in the same row/column. 4916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 4926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// This function has been created as temporary workaround for the bug in current implementation 4936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// of cvFindChessboardCornes that produces absolutely unordered sets of corners. 4946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 4956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 4976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCheckBoardMonotony( CvPoint2D32f* corners, CvSize pattern_size ) 4986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 4996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, k; 5006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 2; k++ ) 5026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < (k == 0 ? pattern_size.height : pattern_size.width); i++ ) 5046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f a = k == 0 ? corners[i*pattern_size.width] : corners[i]; 5066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f b = k == 0 ? corners[(i+1)*pattern_size.width-1] : 5076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corners[(pattern_size.height-1)*pattern_size.width + i]; 5086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float prevt = 0, dx0 = b.x - a.x, dy0 = b.y - a.y; 5096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs(dx0) + fabs(dy0) < FLT_EPSILON ) 5106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; 5116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 1; j < (k == 0 ? pattern_size.width : pattern_size.height) - 1; j++ ) 5126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f c = k == 0 ? corners[i*pattern_size.width + j] : 5146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corners[j*pattern_size.width + i]; 5156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float t = ((c.x - a.x)*dx0 + (c.y - a.y)*dy0)/(dx0*dx0 + dy0*dy0); 5166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( t < prevt || t > 1 ) 5176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; 5186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prevt = t; 5196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 1; 5246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 5256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 5276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// order a group of connected quads 5286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// order of corners: 5296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 0 is top left 5306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// clockwise from there 5316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// note: "top left" is nominal, depends on initial ordering of starting quad 5326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// but all other quads are ordered consistently 5336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 5346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// can change the number of quads in the group 5356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// can add quads, so we need to have quad/corner arrays passed in 5366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 5376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 5396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvOrderFoundConnectedQuads( int quad_count, CvCBQuad **quads, 5406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *all_count, CvCBQuad **all_quads, CvCBCorner **corners, 5416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSize pattern_size, CvMemStorage* storage ) 5426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 5436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* temp_storage = cvCreateChildMemStorage( storage ); 5446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage ); 5456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i; 5466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // first find an interior quad 5486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *start = NULL; 5496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (i=0; i<quad_count; i++) 5506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->count == 4) 5526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start = quads[i]; 5546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 5556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (start == NULL) 5596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 5616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; // no 4-connected quad 5626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // start with first one, assign rows/cols 5656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row_min = 0, col_min = 0, row_max=0, col_max = 0; 5666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define HSIZE 20 5676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int col_hist[HSIZE*2]; 5686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row_hist[HSIZE*2]; // bad programming, should allow variable size 5696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (i=0; i<HSIZE*2; i++) // init to zero 5716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col_hist[i] = row_hist[i] = 0; 5726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush(stack, &start); 5736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start->row = 0; 5746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start->col = 0; 5756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start->ordered = true; 5766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Recursively order the quads so that all position numbers (e.g., 5786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // 0,1,2,3) are in the at the same relative corner (e.g., lower right). 5796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( stack->total ) 5816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q; 5836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPop( stack, &q ); 5846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int col = q->col; 5856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row = q->row; 5866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col_hist[col+HSIZE]++; 5876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn row_hist[row+HSIZE]++; 5886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check min/max 5906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (row > row_max) row_max = row; 5916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (row < row_min) row_min = row; 5926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (col > col_max) col_max = col; 5936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (col < col_min) col_min = col; 5946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(int i = 0; i < 4; i++ ) 5966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *neighbor = q->neighbors[i]; 5986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch(i) // adjust col, row for this quad 5996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { // start at top left, go clockwise 6006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 0: 6016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn row--; col--; break; 6026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 1: 6036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col += 2; break; 6046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 2: 6056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn row += 2; break; 6066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 3: 6076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col -= 2; break; 6086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // just do inside quads 6116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (neighbor && neighbor->ordered == false && neighbor->count == 4) 6126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("col: %d row: %d\n", col, row); 6146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvOrderQuad(neighbor, q->corners[i], (i+2)%4); // set in order 6156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->ordered = true; 6166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->row = row; 6176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->col = col; 6186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &neighbor ); 6196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 6246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (i=col_min; i<=col_max; i++) 6266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("HIST[%d] = %d\n", i, col_hist[i+HSIZE]); 6276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // analyze inner quad structure 6296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int w = pattern_size.width - 1; 6306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int h = pattern_size.height - 1; 6316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int drow = row_max - row_min + 1; 6326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dcol = col_max - col_min + 1; 6336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // normalize pattern and found quad indices 6356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if ((w > h && dcol < drow) || 6366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (w < h && drow < dcol)) 6376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h = pattern_size.width - 1; 6396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn w = pattern_size.height - 1; 6406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Size: %dx%d Pattern: %dx%d\n", dcol, drow, w, h); 6436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check if there are enough inner quads 6456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (dcol < w || drow < h) // found enough inner quads? 6466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Too few inner quad rows/cols\n"); 6486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; // no, return 6496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // too many columns, not very common 6526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (dcol == w+1) // too many, trim 6536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Trimming cols\n"); 6556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (col_hist[col_max+HSIZE] > col_hist[col_min+HSIZE]) 6566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Trimming left col\n"); 6586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count = icvTrimCol(quads,quad_count,col_min,-1); 6596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Trimming right col\n"); 6636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count = icvTrimCol(quads,quad_count,col_max,+1); 6646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // too many rows, not very common 6686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (drow == h+1) // too many, trim 6696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Trimming rows\n"); 6716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (row_hist[row_max+HSIZE] > row_hist[row_min+HSIZE]) 6726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Trimming top row\n"); 6746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count = icvTrimRow(quads,quad_count,row_min,-1); 6756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Trimming bottom row\n"); 6796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count = icvTrimRow(quads,quad_count,row_max,+1); 6806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check edges of inner quads 6856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // if there is an outer quad missing, fill it in 6866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // first order all inner quads 6876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int found = 0; 6886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (i=0; i<quad_count; i++) 6896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->count == 4) 6916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { // ok, look at neighbors 6926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int col = quads[i]->col; 6936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row = quads[i]->row; 6946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int j=0; j<4; j++) 6956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch(j) // adjust col, row for this quad 6976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { // start at top left, go clockwise 6986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 0: 6996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn row--; col--; break; 7006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 1: 7016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col += 2; break; 7026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 2: 7036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn row += 2; break; 7046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 3: 7056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col -= 2; break; 7066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *neighbor = quads[i]->neighbors[j]; 7086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (neighbor && !neighbor->ordered && // is it an inner quad? 7096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn col <= col_max && col >= col_min && 7106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn row <= row_max && row >= row_min) 7116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // if so, set in order 7136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Adding inner: col: %d row: %d\n", col, row); 7146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn found++; 7156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvOrderQuad(neighbor, quads[i]->corners[j], (j+2)%4); 7166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->ordered = true; 7176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->row = row; 7186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->col = col; 7196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // if we have found inner quads, add corresponding outer quads, 7256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // which are missing 7266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (found > 0) 7276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Found %d inner quads not connected to outer quads, repairing\n", found); 7296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int i=0; i<quad_count; i++) 7306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->count < 4 && quads[i]->ordered) 7326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int added = icvAddOuterQuad(quads[i],quads,quad_count,all_quads,*all_count,corners); 7346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *all_count += added; 7356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count += added; 7366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // final trimming of outer quads 7426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (dcol == w && drow == h) // found correct inner quads 7436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Inner bounds ok, check outer quads\n"); 7456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int rcount = quad_count; 7466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int i=quad_count-1; i>=0; i--) // eliminate any quad not connected to 7476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // an ordered quad 7486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->ordered == false) 7506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn bool outer = false; 7526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int j=0; j<4; j++) // any neighbors that are ordered? 7536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[j] && quads[i]->neighbors[j]->ordered) 7556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn outer = true; 7566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (!outer) // not an outer quad, eliminate 7586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Removing quad %d\n", i); 7606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]); 7616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 7626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return rcount; 7676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; 7706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// add an outer quad 7746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// looks for the neighbor of <quad> that isn't present, 7756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// tries to add it in. 7766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// <quad> is ordered 7776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 7796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvAddOuterQuad( CvCBQuad *quad, CvCBQuad **quads, int quad_count, 7806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad **all_quads, int all_count, CvCBCorner **corners ) 7816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int added = 0; 7846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int i=0; i<4; i++) // find no-neighbor corners 7856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (!quad->neighbors[i]) // ok, create and add neighbor 7876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int j = (i+2)%4; 7896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Adding quad as neighbor 2\n"); 7906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *q = &(*all_quads)[all_count]; 7916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( q, 0, sizeof(*q) ); 7926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn added++; 7936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quads[quad_count] = q; 7946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count++; 7956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // set neighbor and group id 7976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->neighbors[i] = q; 7986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->count += 1; 7996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->neighbors[j] = quad; 8006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->group_idx = quad->group_idx; 8016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count = 1; // number of neighbors 8026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->ordered = false; 8036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->edge_len = quad->edge_len; 8046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // make corners of new quad 8066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // same as neighbor quad, but offset 8076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt = quad->corners[i]->pt; 8086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner* corner; 8096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dx = pt.x - quad->corners[j]->pt.x; 8106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dy = pt.y - quad->corners[j]->pt.y; 8116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int k=0; k<4; k++) 8126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner = &(*corners)[all_count*4+k]; 8146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt = quad->corners[k]->pt; 8156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( corner, 0, sizeof(*corner) ); 8166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner->pt = pt; 8176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->corners[k] = corner; 8186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner->pt.x += dx; 8196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner->pt.y += dy; 8206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // have to set exact corner 8226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->corners[j] = quad->corners[i]; 8236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // now find other neighbor and add it, if possible 8256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quad->neighbors[(i+3)%4] && 8266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->neighbors[(i+3)%4]->ordered && 8276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->neighbors[(i+3)%4]->neighbors[i] && 8286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->neighbors[(i+3)%4]->neighbors[i]->ordered ) 8296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *qn = quad->neighbors[(i+3)%4]->neighbors[i]; 8316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count = 2; 8326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->neighbors[(j+1)%4] = qn; 8336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn qn->neighbors[(i+1)%4] = q; 8346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn qn->count += 1; 8356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // have to set exact corner 8366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->corners[(j+1)%4] = qn->corners[(i+1)%4]; 8376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn all_count++; 8406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return added; 8436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 8446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// trimming routines 8476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 8496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvTrimCol(CvCBQuad **quads, int count, int col, int dir) 8506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 8516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int rcount = count; 8526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find the right quad(s) 8536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int i=0; i<count; i++) 8546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 8566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->ordered) 8576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("index: %d cur: %d\n", col, quads[i]->col); 8586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 8596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->ordered && quads[i]->col == col) 8606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (dir == 1) 8626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[1]) 8646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]); 8666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 8676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[2]) 8696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]); 8716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 8726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[0]) 8776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]); 8796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 8806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[3]) 8826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]); 8846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 8856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return rcount; 8916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 8926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 8946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvTrimRow(CvCBQuad **quads, int count, int row, int dir) 8956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 8966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, rcount = count; 8976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find the right quad(s) 8986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (i=0; i<count; i++) 8996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#ifdef DEBUG_CHESSBOARD 9016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->ordered) 9026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("index: %d cur: %d\n", row, quads[i]->row); 9036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 9046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->ordered && quads[i]->row == row) 9056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (dir == 1) // remove from bottom 9076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[2]) 9096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[2]); 9116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 9126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[3]) 9146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[3]); 9166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 9176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else // remove from top 9206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[0]) 9226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[0]); 9246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 9256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quads[i]->neighbors[1]) 9276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvRemoveQuadFromGroup(quads,rcount,quads[i]->neighbors[1]); 9296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn rcount--; 9306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return rcount; 9366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 9376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 9406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// remove quad from quad group 9416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 9426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 9446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvRemoveQuadFromGroup(CvCBQuad **quads, int count, CvCBQuad *q0) 9456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 9466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j; 9476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // remove any references to this quad as a neighbor 9486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(i = 0; i < count; i++ ) 9496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *q = quads[i]; 9516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(j = 0; j < 4; j++ ) 9526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q->neighbors[j] == q0 ) 9546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->neighbors[j] = 0; 9566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count--; 9576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(int k = 0; k < 4; k++ ) 9586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q0->neighbors[k] == q ) 9596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q0->neighbors[k] = 0; 9616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q0->count--; 9626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 9636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 9656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // remove the quad 9706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(i = 0; i < count; i++ ) 9716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *q = quads[i]; 9736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (q == q0) 9746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quads[i] = quads[count-1]; 9766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 9776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 9806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 9826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// put quad into correct order, where <corner> has value <common> 9836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 9846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 9866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvOrderQuad(CvCBQuad *quad, CvCBCorner *corner, int common) 9876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 9886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find the corner 9896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int tc; 9906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (tc=0; tc<4; tc++) 9916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (quad->corners[tc]->pt.x == corner->pt.x && 9926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->corners[tc]->pt.y == corner->pt.y) 9936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 9946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // set corner order 9966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // shift 9976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while (tc != common) 9986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // shift by one 10006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner *tempc; 10016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *tempq; 10026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tempc = quad->corners[3]; 10036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tempq = quad->neighbors[3]; 10046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for (int i=3; i>0; i--) 10056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->corners[i] = quad->corners[i-1]; 10076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->neighbors[i] = quad->neighbors[i-1]; 10086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->corners[0] = tempc; 10106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad->neighbors[0] = tempq; 10116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tc++; 10126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tc = tc%4; 10136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 10156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// if we found too many connect quads, remove those which probably do not belong. 10186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 10196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCleanFoundConnectedQuads( int quad_count, CvCBQuad **quad_group, CvSize pattern_size ) 10206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 10216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *temp_storage = 0; 10226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f *centers = 0; 10236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvCleanFoundConnectedQuads" ); 10256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 10276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f center = {0,0}; 10296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, k; 10306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // number of quads this pattern should contain 10316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int count = ((pattern_size.width + 1)*(pattern_size.height + 1) + 1)/2; 10326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // if we have more quadrangles than we should, 10346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // try to eliminate duplicates or ones which don't belong to the pattern rectangle... 10356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( quad_count <= count ) 10366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 10376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // create an array of quadrangle centers 10396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( centers = (CvPoint2D32f *)cvAlloc( sizeof(centers[0])*quad_count )); 10406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( temp_storage = cvCreateMemStorage(0)); 10416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < quad_count; i++ ) 10436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f ci = {0,0}; 10456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q = quad_group[i]; 10466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < 4; j++ ) 10486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt = q->corners[j]->pt; 10506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ci.x += pt.x; 10516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ci.y += pt.y; 10526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ci.x *= 0.25f; 10556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ci.y *= 0.25f; 10566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn centers[i] = ci; 10586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn center.x += ci.x; 10596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn center.y += ci.y; 10606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn center.x /= quad_count; 10626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn center.y /= quad_count; 10636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // If we still have more quadrangles than we should, 10656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // we try to eliminate bad ones based on minimizing the bounding box. 10666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // We iteratively remove the point which reduces the size of 10676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // the bounding box of the blobs the most 10686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // (since we want the rectangle to be as small as possible) 10696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // remove the quadrange that causes the biggest reduction 10706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // in pattern size until we have the correct number 10716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ; quad_count > count; quad_count-- ) 10726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double min_box_area = DBL_MAX; 10746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int skip, min_box_area_index = -1; 10756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *q0, *q; 10766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // For each point, calculate box area without that point 10786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( skip = 0; skip < quad_count; skip++ ) 10796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // get bounding rectangle 10816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f temp = centers[skip]; // temporarily make index 'skip' the same as 10826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn centers[skip] = center; // pattern center (so it is not counted for convex hull) 10836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat pointMat = cvMat(1, quad_count, CV_32FC2, centers); 10846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *hull = cvConvexHull2( &pointMat, temp_storage, CV_CLOCKWISE, 1 ); 10856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn centers[skip] = temp; 10866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double hull_area = fabs(cvContourArea(hull, CV_WHOLE_SEQ)); 10876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // remember smallest box area 10896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( hull_area < min_box_area ) 10906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_box_area = hull_area; 10926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_box_area_index = skip; 10936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvClearMemStorage( temp_storage ); 10956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q0 = quad_group[min_box_area_index]; 10986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // remove any references to this quad as a neighbor 11006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < quad_count; i++ ) 11016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q = quad_group[i]; 11036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < 4; j++ ) 11046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q->neighbors[j] == q0 ) 11066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->neighbors[j] = 0; 11086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count--; 11096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 4; k++ ) 11106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q0->neighbors[k] == q ) 11116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q0->neighbors[k] = 0; 11136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q0->count--; 11146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 11156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 11176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // remove the quad 11226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count--; 11236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_group[min_box_area_index] = quad_group[quad_count]; 11246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn centers[min_box_area_index] = centers[quad_count]; 11256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 11286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 11306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( ¢ers ); 11316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return quad_count; 11336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 11366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 11386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvFindConnectedQuads( CvCBQuad *quad, int quad_count, CvCBQuad **out_group, 11396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int group_idx, CvMemStorage* storage ) 11406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 11416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* temp_storage = cvCreateChildMemStorage( storage ); 11426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* stack = cvCreateSeq( 0, sizeof(*stack), sizeof(void*), temp_storage ); 11436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, count = 0; 11446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Scan the array for a first unlabeled quad 11466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < quad_count; i++ ) 11476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( quad[i].count > 0 && quad[i].group_idx < 0) 11496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 11506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Recursively find a group of connected quads starting from the seed quad[i] 11536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i < quad_count ) 11546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q = &quad[i]; 11566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &q ); 11576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_group[count++] = q; 11586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->group_idx = group_idx; 11596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->ordered = false; 11606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( stack->total ) 11626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPop( stack, &q ); 11646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 11656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *neighbor = q->neighbors[i]; 11676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( neighbor && neighbor->count > 0 && neighbor->group_idx < 0 ) 11686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 11696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &neighbor ); 11706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_group[count++] = neighbor; 11716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->group_idx = group_idx; 11726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn neighbor->ordered = false; 11736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 11776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 11796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return count; 11806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 11816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 11846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 11866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCheckQuadGroup( CvCBQuad **quad_group, int quad_count, 11876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner **out_corners, CvSize pattern_size ) 11886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 11896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int ROW1 = 1000000; 11906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int ROW2 = 2000000; 11916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int ROW_ = 3000000; 11926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int result = 0; 11936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, out_corner_count = 0, corner_count = 0; 11946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner** corners = 0; 11956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvCheckQuadGroup" ); 11976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 11986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 11996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int j, k, kk; 12016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int width = 0, height = 0; 12026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int hist[5] = {0,0,0,0,0}; 12036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner* first = 0, *first2 = 0, *right, *cur, *below, *c; 12046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( corners = (CvCBCorner**)cvAlloc( quad_count*4*sizeof(corners[0]) )); 12056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // build dual graph, which vertices are internal quad corners 12076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // and two vertices are connected iff they lie on the same quad edge 12086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < quad_count; i++ ) 12096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q = quad_group[i]; 12116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /*CvScalar color = q->count == 0 ? cvScalar(0,255,255) : 12126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count == 1 ? cvScalar(0,0,255) : 12136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count == 2 ? cvScalar(0,255,0) : 12146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->count == 3 ? cvScalar(255,255,0) : 12156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvScalar(255,0,0);*/ 12166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < 4; j++ ) 12186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //cvLine( debug_img, cvPointFrom32f(q->corners[j]->pt), cvPointFrom32f(q->corners[(j+1)&3]->pt), color, 1, CV_AA, 0 ); 12206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q->neighbors[j] ) 12216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner *a = q->corners[j], *b = q->corners[(j+1)&3]; 12236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // mark internal corners that belong to: 12246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // - a quad with a single neighbor - with ROW1, 12256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // - a quad with two neighbors - with ROW2 12266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // make the rest of internal corners with ROW_ 12276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int row_flag = q->count == 1 ? ROW1 : q->count == 2 ? ROW2 : ROW_; 12286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( a->row == 0 ) 12306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corners[corner_count++] = a; 12326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a->row = row_flag; 12336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( a->row > row_flag ) 12356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a->row = row_flag; 12366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q->neighbors[(j+1)&3] ) 12386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( a->count >= 4 || b->count >= 4 ) 12406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 12416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 4; k++ ) 12426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( a->neighbors[k] == b ) 12446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 12456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( b->neighbors[k] == a ) 12466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 12476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a->neighbors[a->count++] = b; 12496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn b->neighbors[b->count++] = a; 12506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( corner_count != pattern_size.width*pattern_size.height ) 12566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 12576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < corner_count; i++ ) 12596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int n = corners[i]->count; 12616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( 0 <= n && n <= 4 ); 12626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn hist[n]++; 12636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !first && n == 2 ) 12646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( corners[i]->row == ROW1 ) 12666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = corners[i]; 12676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( !first2 && corners[i]->row == ROW2 ) 12686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first2 = corners[i]; 12696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // start with a corner that belongs to a quad with a signle neighbor. 12736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // if we do not have such, start with a corner of a quad with two neighbors. 12746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !first ) 12756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = first2; 12766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !first || hist[0] != 0 || hist[1] != 0 || hist[2] != 4 || 12786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn hist[3] != (pattern_size.width + pattern_size.height)*2 - 8 ) 12796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 12806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur = first; 12826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right = below = 0; 12836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_corners[out_corner_count++] = cur; 12846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 4; k++ ) 12866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn c = cur->neighbors[k]; 12886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( c ) 12896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 12906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !right ) 12916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right = c; 12926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( !below ) 12936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn below = c; 12946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 12966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 12976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !right || (right->count != 2 && right->count != 3) || 12986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn !below || (below->count != 2 && below->count != 3) ) 12996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 13006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur->row = 0; 13026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,255,0), -1, 8, 0 ); 13036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = below; // remember the first corner in the next row 13056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find and store the first row (or column) 13066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(j=1;;j++) 13076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right->row = 0; 13096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_corners[out_corner_count++] = right; 13106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //cvCircle( debug_img, cvPointFrom32f(right->pt), 3, cvScalar(0,255-j*10,0), -1, 8, 0 ); 13116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right->count == 2 ) 13126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 13136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right->count != 3 || out_corner_count >= MAX(pattern_size.width,pattern_size.height) ) 13146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 13156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur = right; 13166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 4; k++ ) 13176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn c = cur->neighbors[k]; 13196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( c && c->row > 0 ) 13206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( kk = 0; kk < 4; kk++ ) 13226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( c->neighbors[kk] == below ) 13246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 13256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( kk < 4 ) 13276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn below = c; 13286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 13296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right = c; 13306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn width = out_corner_count; 13356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( width == pattern_size.width ) 13366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn height = pattern_size.height; 13376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( width == pattern_size.height ) 13386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn height = pattern_size.width; 13396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 13406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 13416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find and store all the other rows 13436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 1; ; i++ ) 13446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !first ) 13466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 13476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur = first; 13486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = 0; 13496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0;; j++ ) 13506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur->row = i; 13526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_corners[out_corner_count++] = cur; 13536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //cvCircle( debug_img, cvPointFrom32f(cur->pt), 3, cvScalar(0,0,255-j*10), -1, 8, 0 ); 13546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cur->count == 2 + (i < height-1) && j > 0 ) 13556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 13566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right = 0; 13586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find a neighbor that has not been processed yet 13606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // and that has a neighbor from the previous row 13616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < 4; k++ ) 13626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn c = cur->neighbors[k]; 13646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( c && c->row > i ) 13656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( kk = 0; kk < 4; kk++ ) 13676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( c->neighbors[kk] && c->neighbors[kk]->row == i-1 ) 13696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 13706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( kk < 4 ) 13726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right = c; 13746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j > 0 ) 13756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 13766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( j == 0 ) 13786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = c; 13796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !right ) 13826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 13836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur = right; 13846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j != width - 1 ) 13876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 13886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 13896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corner_count != corner_count ) 13916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 13926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check if we need to transpose the board 13946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( width != pattern_size.width ) 13956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 13966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SWAP( width, height, k ); 13976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 13986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memcpy( corners, out_corners, corner_count*sizeof(corners[0]) ); 13996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < height; i++ ) 14006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < width; j++ ) 14016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_corners[i*width + j] = corners[j*height + i]; 14026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 14036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check if we need to revert the order in each row 14056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f p0 = out_corners[0]->pt, p1 = out_corners[pattern_size.width-1]->pt, 14076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn p2 = out_corners[pattern_size.width]->pt; 14086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (p1.x - p0.x)*(p2.y - p1.y) - (p1.y - p0.y)*(p2.x - p1.x) < 0 ) 14096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( width % 2 == 0 ) 14116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < height; i++ ) 14136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < width/2; j++ ) 14146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SWAP( out_corners[i*width+j], out_corners[i*width+width-j-1], c ); 14156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 14166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 14176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < width; j++ ) 14196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < height/2; i++ ) 14206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SWAP( out_corners[i*width+j], out_corners[(height - i - 1)*width+j], c ); 14216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 14226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 14236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 14246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn result = corner_count; 14266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 14286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( result <= 0 && corners ) 14306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner_count = MIN( corner_count, pattern_size.width*pattern_size.height ); 14326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < corner_count; i++ ) 14336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_corners[i] = corners[i]; 14346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn result = -corner_count; 14356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (result == -pattern_size.width*pattern_size.height) 14376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn result = -result; 14386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 14396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &corners ); 14416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return result; 14436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 14446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 14496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void icvFindQuadNeighbors( CvCBQuad *quads, int quad_count ) 14516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 14526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const float thresh_scale = 1.f; 14536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int idx, i, k, j; 14546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dx, dy, dist; 14556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find quad neighbors 14576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( idx = 0; idx < quad_count; idx++ ) 14586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* cur_quad = &quads[idx]; 14606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // choose the points of the current quadrangle that are close to 14626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // some points of the other quadrangles 14636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // (it can happen for split corners (due to dilation) of the 14646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // checker board). Search only in other quadrangles! 14656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // for each corner of this quadrangle 14676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 14686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt; 14706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float min_dist = FLT_MAX; 14716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int closest_corner_idx = -1; 14726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad *closest_quad = 0; 14736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner *closest_corner = 0; 14746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cur_quad->neighbors[i] ) 14766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 14776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt = cur_quad->corners[i]->pt; 14796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // find the closest corner in all other quadrangles 14816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < quad_count; k++ ) 14826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k == idx ) 14846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 14856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < 4; j++ ) 14876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( quads[k].neighbors[j] ) 14896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 14906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt.x - quads[k].corners[j]->pt.x; 14926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt.y - quads[k].corners[j]->pt.y; 14936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = dx * dx + dy * dy; 14946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 14956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist < min_dist && 14966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist <= cur_quad->edge_len*thresh_scale && 14976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist <= quads[k].edge_len*thresh_scale ) 14986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 14996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check edge lengths, make sure they're compatible 15006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // edges that are different by more than 1:4 are rejected 15016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float ediff = cur_quad->edge_len - quads[k].edge_len; 15026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if (ediff > 32*cur_quad->edge_len || 15036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ediff > 32*quads[k].edge_len) 15046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 15056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn PRINTF("Incompatible edge lengths\n"); 15066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 15076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_corner_idx = j; 15096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_quad = &quads[k]; 15106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_dist = dist; 15116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // we found a matching corner point? 15166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( closest_corner_idx >= 0 && min_dist < FLT_MAX ) 15176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 15186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // If another point from our current quad is closer to the found corner 15196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // than the current one, then we don't count this one after all. 15206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // This is necessary to support small squares where otherwise the wrong 15216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // corner will get matched to closest_quad; 15226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_corner = closest_quad->corners[closest_corner_idx]; 15236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < 4; j++ ) 15256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 15266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cur_quad->neighbors[j] == closest_quad ) 15276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 15286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = closest_corner->pt.x - cur_quad->corners[j]->pt.x; 15306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = closest_corner->pt.y - cur_quad->corners[j]->pt.y; 15316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dx * dx + dy * dy < min_dist ) 15336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 15346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j < 4 || cur_quad->count >= 4 || closest_quad->count >= 4 ) 15376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 15386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Check that each corner is a neighbor of different quads 15406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < closest_quad->count; j++ ) 15416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 15426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( closest_quad->neighbors[j] == cur_quad ) 15436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 15446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j < closest_quad->count ) 15466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 15476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // check whether the closest corner to closest_corner 15496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // is different from cur_quad->corners[i]->pt 15506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 0; k < quad_count; k++ ) 15516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 15526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q = &quads[k]; 15536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k == idx || q == closest_quad ) 15546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 15556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < 4; j++ ) 15576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !q->neighbors[j] ) 15586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 15596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = closest_corner->pt.x - q->corners[j]->pt.x; 15606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = closest_corner->pt.y - q->corners[j]->pt.y; 15616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = dx*dx + dy*dy; 15626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist < min_dist ) 15636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 15646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j < 4 ) 15666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 15676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k < quad_count ) 15706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 15716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_corner->pt.x = (pt.x + closest_corner->pt.x) * 0.5f; 15736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_corner->pt.y = (pt.y + closest_corner->pt.y) * 0.5f; 15746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // We've found one more corner - remember it 15766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_quad->count++; 15776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_quad->neighbors[i] = closest_quad; 15786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_quad->corners[i] = closest_corner; 15796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_quad->count++; 15816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn closest_quad->neighbors[closest_corner_idx] = cur_quad; 15826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 15856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 15866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 15886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// returns corners in clockwise order 15906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// corners don't necessarily start at same position on quad (e.g., 15916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// top left corner) 15926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 15936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 15946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvGenerateQuads( CvCBQuad **out_quads, CvCBCorner **out_corners, 15956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *storage, CvMat *image, int flags ) 15966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 15976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int quad_count = 0; 15986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *temp_storage = 0; 15996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_quads ) 16016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *out_quads = 0; 16026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corners ) 16046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *out_corners = 0; 16056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvGenerateQuads" ); 16076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 16096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *src_contour = 0; 16116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *root; 16126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourEx* board = 0; 16136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourScanner scanner; 16146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, idx, min_size; 16156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ASSERT( out_corners && out_quads ); 16176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // empiric bound for minimal allowed perimeter for squares 16196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_size = cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 ); 16206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // create temporary storage for contours and the sequence of pointers to found quadrangles 16226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( temp_storage = cvCreateChildMemStorage( storage )); 16236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( root = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage )); 16246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // initialize contour retrieving routine 16266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( scanner = cvStartFindContours( image, temp_storage, sizeof(CvContourEx), 16276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE )); 16286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // get all the contours one by one 16306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( (src_contour = cvFindNextContour( scanner )) != 0 ) 16316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 16326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *dst_contour = 0; 16336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvRect rect = ((CvContour*)src_contour)->rect; 16346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reject contours with too small perimeter 16366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_SEQ_HOLE(src_contour) && rect.width*rect.height >= min_size ) 16376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 16386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int min_approx_level = 2, max_approx_level = MAX_CONTOUR_APPROX; 16396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int approx_level; 16406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( approx_level = min_approx_level; approx_level <= max_approx_level; approx_level++ ) 16416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 16426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_contour = cvApproxPoly( src_contour, sizeof(CvContour), temp_storage, 16436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_POLY_APPROX_DP, (float)approx_level ); 16446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // we call this again on its own output, because sometimes 16456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // cvApproxPoly() does not simplify as much as it should. 16466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_contour = cvApproxPoly( dst_contour, sizeof(CvContour), temp_storage, 16476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_POLY_APPROX_DP, (float)approx_level ); 16486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dst_contour->total == 4 ) 16506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 16516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 16526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reject non-quadrangles 16546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dst_contour->total == 4 && cvCheckContourConvexity(dst_contour) ) 16556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 16566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt[4]; 16576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double d1, d2, p = cvContourPerimeter(dst_contour); 16586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double area = fabs(cvContourArea(dst_contour, CV_WHOLE_SEQ)); 16596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double dx, dy; 16606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 16626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt[i] = *(CvPoint*)cvGetSeqElem(dst_contour, i); 16636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[0].x - pt[2].x; 16656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[0].y - pt[2].y; 16666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d1 = sqrt(dx*dx + dy*dy); 16676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[1].x - pt[3].x; 16696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[1].y - pt[3].y; 16706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d2 = sqrt(dx*dx + dy*dy); 16716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // philipg. Only accept those quadrangles which are more square 16736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // than rectangular and which are big enough 16746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double d3, d4; 16756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[0].x - pt[1].x; 16766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[0].y - pt[1].y; 16776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d3 = sqrt(dx*dx + dy*dy); 16786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[1].x - pt[2].x; 16796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[1].y - pt[2].y; 16806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d4 = sqrt(dx*dx + dy*dy); 16816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !(flags & CV_CALIB_CB_FILTER_QUADS) || 16826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (d3*4 > d4 && d4*4 > d3 && d3*d4 < area*1.5 && area > min_size && 16836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d1 >= 0.15 * p && d2 >= 0.15 * p) ) 16846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 16856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourEx* parent = (CvContourEx*)(src_contour->v_prev); 16866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent->counter++; 16876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !board || board->counter < parent->counter ) 16886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn board = parent; 16896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_contour->v_prev = (CvSeq*)parent; 16906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //for( i = 0; i < 4; i++ ) cvLine( debug_img, pt[i], pt[(i+1)&3], cvScalar(200,255,255), 1, CV_AA, 0 ); 16916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( root, &dst_contour ); 16926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 16936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 16946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 16956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 16966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 16976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // finish contour retrieving 16986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvEndFindContours( &scanner ); 16996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // allocate quad & corner buffers 17016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( *out_quads = (CvCBQuad*)cvAlloc((root->total+root->total / 2) * sizeof((*out_quads)[0]))); 17026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( *out_corners = (CvCBCorner*)cvAlloc((root->total+root->total / 2) * 4 * sizeof((*out_corners)[0]))); 17036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Create array of quads structures 17056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( idx = 0; idx < root->total; idx++ ) 17066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 17076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q = &(*out_quads)[quad_count]; 17086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_contour = *(CvSeq**)cvGetSeqElem( root, idx ); 17096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (flags & CV_CALIB_CB_FILTER_QUADS) && src_contour->v_prev != (CvSeq*)board ) 17106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 17116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reset group ID 17136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( q, 0, sizeof(*q) ); 17146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->group_idx = -1; 17156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( src_contour->total == 4 ); 17166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 17176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 17186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt = cvPointTo32f(*(CvPoint*)cvGetSeqElem(src_contour, i)); 17196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner* corner = &(*out_corners)[quad_count*4 + i]; 17206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( corner, 0, sizeof(*corner) ); 17226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner->pt = pt; 17236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->corners[i] = corner; 17246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 17256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->edge_len = FLT_MAX; 17266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 17276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 17286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dx = q->corners[i]->pt.x - q->corners[(i+1)&3]->pt.x; 17296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dy = q->corners[i]->pt.y - q->corners[(i+1)&3]->pt.y; 17306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float d = dx*dx + dy*dy; 17316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q->edge_len > d ) 17326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->edge_len = d; 17336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 17346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count++; 17356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 17366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 17386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cvGetErrStatus() < 0 ) 17406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 17416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_quads ) 17426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( out_quads ); 17436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corners ) 17446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( out_corners ); 17456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count = 0; 17466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 17476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 17496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return quad_count; 17506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 17516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//===================================================================================== 17546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int is_equal_quad( const void* _a, const void* _b, void* ) 17566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 17576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvRect a = (*((CvContour**)_a))->rect; 17586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvRect b = (*((CvContour**)_b))->rect; 17596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dx = MIN( b.x + b.width - 1, a.x + a.width - 1) - MAX( b.x, a.x); 17616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dy = MIN( b.y + b.height - 1, a.y + a.height - 1) - MAX( b.y, a.y); 17626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int w = (a.width + b.width)>>1; 17636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int h = (a.height + b.height)>>1; 17646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dx > w*0.75 && dy > h*0.75 && dx < w*1.25 && dy < h*1.25 ) return 1; 17666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return 0; 17686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 17696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 17716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvGenerateQuadsEx( CvCBQuad **out_quads, CvCBCorner **out_corners, 17726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *storage, CvMat *image, CvMat *thresh_img, int dilations, int flags ) 17736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 17746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int l; 17756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int quad_count = 0; 17766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage *temp_storage = 0; 17776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_quads ) 17796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *out_quads = 0; 17806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corners ) 17826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *out_corners = 0; 17836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "icvGenerateQuads" ); 17856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 17876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *src_contour = 0; 17896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *root, *root_tmp; 17906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourEx* board = 0; 17916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourScanner scanner; 17926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, idx, min_size; 17936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int step_level = 25; 17946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ASSERT( out_corners && out_quads ); 17966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 17976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // empiric bound for minimal allowed perimeter for squares 17986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn min_size = cvRound( image->cols * image->rows * .03 * 0.01 * 0.92 ); 17996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // create temporary storage for contours and the sequence of pointers to found quadrangles 18016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( temp_storage = cvCreateChildMemStorage( storage )); 18026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( root_tmp = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage )); 18036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( root = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), temp_storage )); 18046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //perform contours slicing 18066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvEqualizeHist(image,image); 18076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(l = step_level; l < 256-step_level; l+= step_level) 18086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 18096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvThreshold( image, thresh_img, l, 255, CV_THRESH_BINARY ); 18106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvDilate( thresh_img, thresh_img, 0, dilations ); 18116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //draw frame to extract edge quads 18136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvRectangle( thresh_img, cvPoint(0,0), cvPoint(thresh_img->cols-1, 18146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn thresh_img->rows-1), CV_RGB(255,255,255), 3, 8); 18156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // initialize contour retrieving routine 18176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( scanner = cvStartFindContours( thresh_img, temp_storage, sizeof(CvContourEx), 18186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE )); 18196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // get all the contours one by one 18216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( (src_contour = cvFindNextContour( scanner )) != 0 ) 18226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 18236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *dst_contour = 0; 18246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvRect rect = ((CvContour*)src_contour)->rect; 18256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reject contours with too small perimeter 18276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_SEQ_HOLE(src_contour) && rect.width*rect.height >= min_size ) 18286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 18296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int min_approx_level = 2, max_approx_level = MAX_CONTOUR_APPROX; 18306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int approx_level; 18316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( approx_level = min_approx_level; approx_level <= max_approx_level; approx_level++ ) 18326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 18336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_contour = cvApproxPoly( src_contour, sizeof(CvContour), temp_storage, 18346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_POLY_APPROX_DP, (float)approx_level ); 18356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // we call this again on its own output, because sometimes 18366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // cvApproxPoly() does not simplify as much as it should. 18376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_contour = cvApproxPoly( dst_contour, sizeof(CvContour), temp_storage, 18386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_POLY_APPROX_DP, (float)approx_level ); 18396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dst_contour->total == 4 ) 18416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 18426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 18436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reject non-quadrangles 18456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dst_contour->total == 4 && cvCheckContourConvexity(dst_contour) ) 18466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 18476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt[4]; 18486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double d1, d2, p = cvContourPerimeter(dst_contour); 18496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double area = fabs(cvContourArea(dst_contour, CV_WHOLE_SEQ)); 18506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double dx, dy; 18516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 18536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt[i] = *(CvPoint*)cvGetSeqElem(dst_contour, i); 18546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //check border condition. if this is edge square we will add this as is 18566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int edge_flag = 0, eps = 2; 18576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 18586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pt[i].x <= eps || pt[i].y <= eps || 18596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt[i].x >= image->width - eps || 18606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt[i].y >= image->height - eps ) edge_flag = 1; 18616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[0].x - pt[2].x; 18636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[0].y - pt[2].y; 18646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d1 = sqrt(dx*dx + dy*dy); 18656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[1].x - pt[3].x; 18676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[1].y - pt[3].y; 18686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d2 = sqrt(dx*dx + dy*dy); 18696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // philipg. Only accept those quadrangles which are more square 18716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // than rectangular and which are big enough 18726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double d3, d4; 18736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[0].x - pt[1].x; 18746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[0].y - pt[1].y; 18756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d3 = sqrt(dx*dx + dy*dy); 18766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt[1].x - pt[2].x; 18776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt[1].y - pt[2].y; 18786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d4 = sqrt(dx*dx + dy*dy); 18796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( edge_flag || 18806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (!(flags & CV_CALIB_CB_FILTER_QUADS) || 18816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (d3*4 > d4 && d4*4 > d3 && d3*d4 < area*1.5 && area > min_size && 18826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d1 >= 0.15 * p && d2 >= 0.15 * p)) ) 18836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 18846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourEx* parent = (CvContourEx*)(src_contour->v_prev); 18856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent->counter++; 18866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !board || board->counter < parent->counter ) 18876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn board = parent; 18886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_contour->v_prev = (CvSeq*)parent; 18896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //for( i = 0; i < 4; i++ ) cvLine( debug_img, pt[i], pt[(i+1)&3], cvScalar(200,255,255), 1, CV_AA, 0 ); 18906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( root_tmp, &dst_contour ); 18916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 18926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 18936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 18946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 18956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // finish contour retrieving 18966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvEndFindContours( &scanner ); 18976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 18986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 18996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Perform clustering of extracted quads 19016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Same quad can be extracted from different binarization levels 19026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( root_tmp->total ) 19036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* idx_seq = 0; 19056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int n_quads = cvSeqPartition( root_tmp, temp_storage, &idx_seq, is_equal_quad, 0 ); 19066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < n_quads; i++ ) 19076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //extract biggest quad in group 19096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int max_size = 0; 19106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* max_seq = 0; 19116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( int j = 0; j < root_tmp->total; j++ ) 19126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int index = *(int*)cvGetSeqElem(idx_seq, j); 19146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if(index!=i) continue; 19156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContour* cnt = *(CvContour**)cvGetSeqElem(root_tmp, j); 19166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if(cnt->rect.width > max_size) 19176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_size = cnt->rect.width; 19196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_seq = (CvSeq*)cnt; 19206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( root, &max_seq); 19236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // allocate quad & corner buffers 19276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( *out_quads = (CvCBQuad*)cvAlloc((root->total+root->total / 2) * sizeof((*out_quads)[0]))); 19286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( *out_corners = (CvCBCorner*)cvAlloc((root->total+root->total / 2) * 4 * sizeof((*out_corners)[0]))); 19296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // Create array of quads structures 19316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( idx = 0; idx < root->total; idx++ ) 19326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBQuad* q = &(*out_quads)[quad_count]; 19346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_contour = *(CvSeq**)cvGetSeqElem( root, idx ); 19356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (flags & CV_CALIB_CB_FILTER_QUADS) && src_contour->v_prev != (CvSeq*)board ) 19366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 19376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn // reset group ID 19396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( q, 0, sizeof(*q) ); 19406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->group_idx = -1; 19416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( src_contour->total == 4 ); 19426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 19436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt = cvPointTo32f(*(CvPoint*)cvGetSeqElem(src_contour, i)); 19456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvCBCorner* corner = &(*out_corners)[quad_count*4 + i]; 19466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( corner, 0, sizeof(*corner) ); 19486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn corner->pt = pt; 19496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->corners[i] = corner; 19506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->edge_len = FLT_MAX; 19526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 4; i++ ) 19536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dx = q->corners[i]->pt.x - q->corners[(i+1)&3]->pt.x; 19556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float dy = q->corners[i]->pt.y - q->corners[(i+1)&3]->pt.y; 19566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float d = dx*dx + dy*dy; 19576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( q->edge_len > d ) 19586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn q->edge_len = d; 19596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count++; 19616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 19646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cvGetErrStatus() < 0 ) 19666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 19676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_quads ) 19686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( out_quads ); 19696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( out_corners ) 19706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( out_corners ); 19716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quad_count = 0; 19726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 19736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 19756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return quad_count; 19766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 19776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL void 19806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvDrawChessboardCorners( CvArr* _image, CvSize pattern_size, 19816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f* corners, int count, int found ) 19826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 19836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvDrawChessboardCorners" ); 19846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 19866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int shift = 0; 19886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int radius = 4; 19896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int r = radius*(1 << shift); 19906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i; 19916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMat stub, *image; 19926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double scale = 1; 19936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int type, cn, line_type; 19946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( image = cvGetMat( _image, &stub )); 19966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 19976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn type = CV_MAT_TYPE(image->type); 19986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cn = CV_MAT_CN(type); 19996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cn != 1 && cn != 3 && cn != 4 ) 20006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnsupportedFormat, "Number of channels must be 1, 3 or 4" ); 20016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch( CV_MAT_DEPTH(image->type) ) 20036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_8U: 20056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn scale = 1; 20066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 20076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_16U: 20086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn scale = 256; 20096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 20106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_32F: 20116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn scale = 1./255; 20126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 20136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 20146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsUnsupportedFormat, 20156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "Only 8-bit, 16-bit or floating-point 32-bit images are supported" ); 20166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 20176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn line_type = type == CV_8UC1 || type == CV_8UC3 ? CV_AA : 8; 20196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !found ) 20216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvScalar color = {{0,0,255}}; 20236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cn == 1 ) 20246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color = cvScalarAll(200); 20256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[0] *= scale; 20266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[1] *= scale; 20276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[2] *= scale; 20286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[3] *= scale; 20296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < count; i++ ) 20316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt; 20336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt.x = cvRound(corners[i].x*(1 << shift)); 20346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt.y = cvRound(corners[i].y*(1 << shift)); 20356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( image, cvPoint( pt.x - r, pt.y - r ), 20366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvPoint( pt.x + r, pt.y + r ), color, 1, line_type, shift ); 20376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( image, cvPoint( pt.x - r, pt.y + r), 20386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvPoint( pt.x + r, pt.y - r), color, 1, line_type, shift ); 20396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift ); 20406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 20416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 20426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 20436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int x, y; 20456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint prev_pt = {0, 0}; 20466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn const int line_max = 7; 20476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn static const CvScalar line_colors[line_max] = 20486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{0,0,255}}, 20506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{0,128,255}}, 20516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{0,200,200}}, 20526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{0,255,0}}, 20536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{200,200,0}}, 20546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{255,0,0}}, 20556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn {{255,0,255}} 20566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn }; 20576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( y = 0, i = 0; y < pattern_size.height; y++ ) 20596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvScalar color = line_colors[y % line_max]; 20616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cn == 1 ) 20626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color = cvScalarAll(200); 20636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[0] *= scale; 20646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[1] *= scale; 20656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[2] *= scale; 20666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn color.val[3] *= scale; 20676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( x = 0; x < pattern_size.width; x++, i++ ) 20696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 20706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt; 20716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt.x = cvRound(corners[i].x*(1 << shift)); 20726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt.y = cvRound(corners[i].y*(1 << shift)); 20736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i != 0 ) 20756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( image, prev_pt, pt, color, 1, line_type, shift ); 20766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( image, cvPoint(pt.x - r, pt.y - r), 20786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvPoint(pt.x + r, pt.y + r), color, 1, line_type, shift ); 20796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvLine( image, cvPoint(pt.x - r, pt.y + r), 20806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvPoint(pt.x + r, pt.y - r), color, 1, line_type, shift ); 20816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCircle( image, pt, r+(1<<shift), color, 1, line_type, shift ); 20826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_pt = pt; 20836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 20846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 20856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 20866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 20886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 20896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 20916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* End of file. */ 2092