////////////////////////////////////////////////////////////////////////////////////////////  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.////  By downloading, copying, installing or using the software you agree to this license.//  If you do not agree to this license, do not download, install,//  copy or use the software.//////                 License For Embedded Computer Vision Library//// Copyright (c) 2008, EMCV Project,// Copyright (c) 2000-2007, Intel Corporation,// All rights reserved.// Third party copyrights are property of their respective owners.//// Redistribution and use in source and binary forms, with or without modification, // are permitted provided that the following conditions are met:////    * Redistributions of source code must retain the above copyright notice, //      this list of conditions and the following disclaimer.//    * Redistributions in binary form must reproduce the above copyright notice, //      this list of conditions and the following disclaimer in the documentation //      and/or other materials provided with the distribution.//    * Neither the name of the copyright holders nor the names of their contributors //      may be used to endorse or promote products derived from this software //      without specific prior written permission.//// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. // IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY // OF SUCH DAMAGE.//// Contributors://    * Shiqi Yu (Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences)#include "_cv.h"/* initializes 8-element array for fast access to 3x3 neighborhood of a pixel */#define  CV_INIT_3X3_DELTAS( deltas, step, nch )            \    ((deltas)[0] =  (nch),  (deltas)[1] = -(step) + (nch),  \     (deltas)[2] = -(step), (deltas)[3] = -(step) - (nch),  \     (deltas)[4] = -(nch),  (deltas)[5] =  (step) - (nch),  \     (deltas)[6] =  (step), (deltas)[7] =  (step) + (nch))static const CvPoint icvCodeDeltas[8] =    { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };CV_IMPL voidcvStartReadChainPoints( CvChain * chain, CvChainPtReader * reader ){    int i;    CV_FUNCNAME( "cvStartReadChainPoints" );    __BEGIN__;    if( !chain || !reader )        CV_ERROR( CV_StsNullPtr, "" );    if( chain->elem_size != 1 || chain->header_size < (int)sizeof(CvChain))        CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );    cvStartReadSeq( (CvSeq *) chain, (CvSeqReader *) reader, 0 );    CV_CHECK();    reader->pt = chain->origin;    for( i = 0; i < 8; i++ )    {        reader->deltas[i][0] = (char) icvCodeDeltas[i].x;        reader->deltas[i][1] = (char) icvCodeDeltas[i].y;    }    __END__;}/* retrieves next point of the chain curve and updates reader */CV_IMPL CvPointcvReadChainPoint( CvChainPtReader * reader ){    char *ptr;    int code;    CvPoint pt = { 0, 0 };    CV_FUNCNAME( "cvReadChainPoint" );    __BEGIN__;    if( !reader )        CV_ERROR( CV_StsNullPtr, "" );    pt = reader->pt;        ptr = reader->ptr;    if( ptr )    {        code = *ptr++;        if( ptr >= reader->block_max )        {            cvChangeSeqBlock( (CvSeqReader *) reader, 1 );            ptr = reader->ptr;        }        reader->ptr = ptr;        reader->code = (char)code;        assert( (code & ~7) == 0 );        reader->pt.x = pt.x + icvCodeDeltas[code].x;        reader->pt.y = pt.y + icvCodeDeltas[code].y;    }    __END__;    return pt;}/****************************************************************************************\*                         Raster->Chain Tree (Suzuki algorithms)                         *\****************************************************************************************/typedef struct _CvContourInfo{    int flags;    struct _CvContourInfo *next;        /* next contour with the same mark value */    struct _CvContourInfo *parent;      /* information about parent contour */    CvSeq *contour;             /* corresponding contour (may be 0, if rejected) */    CvRect rect;                /* bounding rectangle */    CvPoint origin;             /* origin point (where the contour was traced from) */    int is_hole;                /* hole flag */}_CvContourInfo;/*  Structure that is used for sequental retrieving contours from the image.  It supports both hierarchical and plane variants of Suzuki algorithm.*/typedef struct _CvContourScanner{    CvMemStorage *storage1;     /* contains fetched contours */    CvMemStorage *storage2;     /* contains approximated contours                                   (!=storage1 if approx_method2 != approx_method1) */    CvMemStorage *cinfo_storage;        /* contains _CvContourInfo nodes */    CvSet *cinfo_set;           /* set of _CvContourInfo nodes */    CvMemStoragePos initial_pos;        /* starting storage pos */    CvMemStoragePos backup_pos; /* beginning of the latest approx. contour */    CvMemStoragePos backup_pos2;        /* ending of the latest approx. contour */    char *img0;                 /* image origin */    char *img;                  /* current image row */    int img_step;               /* image step */    CvSize img_size;            /* ROI size */    CvPoint offset;             /* ROI offset: coordinates, added to each contour point */    CvPoint pt;                 /* current scanner position */    CvPoint lnbd;               /* position of the last met contour */    int nbd;                    /* current mark val */    _CvContourInfo *l_cinfo;    /* information about latest approx. contour */    _CvContourInfo cinfo_temp;  /* temporary var which is used in simple modes */    _CvContourInfo frame_info;  /* information about frame */    CvSeq frame;                /* frame itself */    int approx_method1;         /* approx method when tracing */    int approx_method2;         /* final approx method */    int mode;                   /* contour scanning mode:                                   0 - external only                                   1 - all the contours w/o any hierarchy                                   2 - connected components (i.e. two-level structure -                                   external contours and holes) */    int subst_flag;    int seq_type1;              /* type of fetched contours */    int header_size1;           /* hdr size of fetched contours */    int elem_size1;             /* elem size of fetched contours */    int seq_type2;              /*                                       */    int header_size2;           /*        the same for approx. contours  */    int elem_size2;             /*                                       */    _CvContourInfo *cinfo_table[126];}_CvContourScanner;#define _CV_FIND_CONTOURS_FLAGS_EXTERNAL_ONLY    1#define _CV_FIND_CONTOURS_FLAGS_HIERARCHIC       2/*    Initializes scanner structure.   Prepare image for scanning ( clear borders and convert all pixels to 0-1.*/CV_IMPL CvContourScannercvStartFindContours( void* _img, CvMemStorage* storage,                     int  header_size, int mode,                      int  method, CvPoint offset ){    int y;    int step;    CvSize size;    uchar *img = 0;    CvContourScanner scanner = 0;    CvMat stub, *mat = (CvMat*)_img;    CV_FUNCNAME( "cvStartFindContours" );    __BEGIN__;    if( !storage )        CV_ERROR( CV_StsNullPtr, "" );    CV_CALL( mat = cvGetMat( mat, &stub ));    if( !CV_IS_MASK_ARR( mat ))        CV_ERROR( CV_StsUnsupportedFormat, "[Start]FindContours support only 8uC1 images" );    size = cvSize( mat->width, mat->height );    step = mat->step;    img = (uchar*)(mat->data.ptr);    if( method < 0 || method > CV_CHAIN_APPROX_TC89_KCOS )        CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR );    if( header_size < (int) (method == CV_CHAIN_CODE ? sizeof( CvChain ) : sizeof( CvContour )))        CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR );    scanner = (CvContourScanner)cvAlloc( sizeof( *scanner ));    if( !scanner )        CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );    memset( scanner, 0, sizeof( *scanner ));    scanner->storage1 = scanner->storage2 = storage;    scanner->img0 = (char *) img;    scanner->img = (char *) (img + step);    scanner->img_step = step;    scanner->img_size.width = size.width - 1;   /* exclude rightest column */    scanner->img_size.height = size.height - 1; /* exclude bottomost row */    scanner->mode = mode;    scanner->offset = offset;    scanner->pt.x = scanner->pt.y = 1;    scanner->lnbd.x = 0;    scanner->lnbd.y = 1;    scanner->nbd = 2;    scanner->mode = (int) mode;    scanner->frame_info.contour = &(scanner->frame);    scanner->frame_info.is_hole = 1;    scanner->frame_info.next = 0;    scanner->frame_info.parent = 0;    scanner->frame_info.rect = cvRect( 0, 0, size.width, size.height );    scanner->l_cinfo = 0;    scanner->subst_flag = 0;    scanner->frame.flags = CV_SEQ_FLAG_HOLE;    scanner->approx_method2 = scanner->approx_method1 = method;    if( method == CV_CHAIN_APPROX_TC89_L1 || method == CV_CHAIN_APPROX_TC89_KCOS )        scanner->approx_method1 = CV_CHAIN_CODE;    if( scanner->approx_method1 == CV_CHAIN_CODE )    {        scanner->seq_type1 = CV_SEQ_CHAIN_CONTOUR;        scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?            header_size : sizeof( CvChain );        scanner->elem_size1 = sizeof( char );    }    else    {        scanner->seq_type1 = CV_SEQ_POLYGON;        scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ?            header_size : sizeof( CvContour );        scanner->elem_size1 = sizeof( CvPoint );    }    scanner->header_size2 = header_size;    if( scanner->approx_method2 == CV_CHAIN_CODE )    {        scanner->seq_type2 = scanner->seq_type1;        scanner->elem_size2 = scanner->elem_size1;    }    else    {        scanner->seq_type2 = CV_SEQ_POLYGON;        scanner->elem_size2 = sizeof( CvPoint );    }    scanner->seq_type1 = scanner->approx_method1 == CV_CHAIN_CODE ?        CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;    scanner->seq_type2 = scanner->approx_method2 == CV_CHAIN_CODE ?        CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON;    cvSaveMemStoragePos( storage, &(scanner->initial_pos) );    if( method > CV_CHAIN_APPROX_SIMPLE )    {        scanner->storage1 = cvCreateChildMemStorage( scanner->storage2 );    }    if( mode > CV_RETR_LIST )    {        scanner->cinfo_storage = cvCreateChildMemStorage( scanner->storage2 );        scanner->cinfo_set = cvCreateSet( 0, sizeof( CvSet ), sizeof( _CvContourInfo ),                                          scanner->cinfo_storage );        if( scanner->cinfo_storage == 0 || scanner->cinfo_set == 0 )            CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );    }    /* make zero borders */    memset( img, 0, size.width );    memset( img + step * (size.height - 1), 0, size.width );    for( y = 1, img += step; y < size.height - 1; y++, img += step )    {        img[0] = img[size.width - 1] = 0;    }    /* converts all pixels to 0 or 1 */    cvThreshold( mat, mat, 0, 1, CV_THRESH_BINARY );    CV_CHECK();    __END__;    if( cvGetErrStatus() < 0 )        cvFree( &scanner );    return scanner;}/*    Final stage of contour processing.   Three variants possible:      1. Contour, which was retrieved using border following, is added to         the contour tree. It is the case when the icvSubstituteContour function         was not called after retrieving the contour.      2. New contour, assigned by icvSubstituteContour function, is added to the         tree. The retrieved contour itself is removed from the storage.         Here two cases are possible:            2a. If one deals with plane variant of algorithm                (hierarchical strucutre is not reconstructed),                the contour is removed completely.            2b. In hierarchical case, the header of the contour is not removed.                It's marked as "link to contour" and h_next pointer of it is set to                new, substituting contour.      3. The similar to 2, but when NULL pointer was assigned by          icvSubstituteContour function. In this case, the function removes         retrieved contour completely if plane case and          leaves header if hierarchical (but doesn't mark header as "link").      ------------------------------------------------------------------------      The 1st variant can be used to retrieve and store all the contours from the image      (with optional convertion from chains to contours using some approximation from       restriced set of methods). Some characteristics of contour can be computed in the      same pass.            The usage scheme can look like:      icvContourScanner scanner;      CvMemStorage*  contour_storage;      CvSeq*  first_contour;      CvStatus  result;      ...      icvCreateMemStorage( &contour_storage, block_size/0 );      ...                    cvStartFindContours              ( img, contour_storage,                header_size, approx_method,                [external_only,]                &scanner );      for(;;)      {          [CvSeq* contour;]          result = icvFindNextContour( &scanner, &contour/0 );          if( result != CV_OK ) break;          // calculate some characteristics          ...      }      if( result < 0 ) goto error_processing;