cvapprox.cpp.svn-base

来自「非结构化路识别」· SVN-BASE 代码 · 共 897 行 · 第 1/2 页

            case CV_CHAIN_APPROX_NONE:
            case CV_CHAIN_APPROX_SIMPLE:
            case CV_CHAIN_APPROX_TC89_L1:
            case CV_CHAIN_APPROX_TC89_KCOS:
                IPPI_CALL( icvApproximateChainTC89( (CvChain *) src_seq,
                                                    sizeof( CvContour ), storage,
                                                    (CvSeq**)&contour, method ));
                break;
            default:
                assert(0);
                CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR );
            }

            assert( contour );

            if( contour->total > 0 )
            {
                cvContourBoundingRect( contour, 1 );

                contour->v_prev = parent;
                contour->h_prev = prev_contour;

                if( prev_contour )
                    prev_contour->h_next = contour;
                else if( parent )
                    parent->v_next = contour;
                prev_contour = contour;
                if( !dst_seq )
                    dst_seq = prev_contour;
            }
            else                /* if resultant contour has zero length, skip it */
            {
                len = -1;
            }
        }

        if( !recursive )
            break;

        if( src_seq->v_next && len >= minimal_perimeter )
        {
            assert( prev_contour != 0 );
            parent = prev_contour;
            prev_contour = 0;
            src_seq = src_seq->v_next;
        }
        else
        {
            while( src_seq->h_next == 0 )
            {
                src_seq = src_seq->v_prev;
                if( src_seq == 0 )
                    break;
                prev_contour = parent;
                if( parent )
                    parent = parent->v_prev;
            }
            if( src_seq )
                src_seq = src_seq->h_next;
        }
    }

    __END__;

    return dst_seq;
}


/****************************************************************************************\
*                               Polygonal Approximation                                  *
\****************************************************************************************/


/* Ramer-Douglas-Peucker algorithm for polygon simplification */
static CvStatus
icvApproxPolyDP( CvSeq* src_contour, int header_size, 
                 CvMemStorage* storage,
                 CvSeq** dst_contour, float eps )
{
    int             init_iters = 2;
    CvSlice         slice = {0, 0}, right_slice = {0, 0};
    CvSeqReader     reader;
    CvSeqWriter     writer;
    CvPoint         start_pt = {INT_MIN, INT_MIN}, end_pt = { 0, 0 }, pt;
    int             count;
    int             i = 0;
    int             is_closed;
    int             le_eps = 0;
    CvMemStorage*   temp_storage = 0;
    CvSeq*          stack = 0;
    int             is_float = CV_SEQ_ELTYPE(src_contour)==CV_32FC2;
    
    cvStartWriteSeq( src_contour->flags, header_size, 
                     sizeof( CvPoint ), storage, &writer );

    if( src_contour->total == 0  )
    {
        *dst_contour = cvEndWriteSeq( &writer );
        return CV_OK;
    }

    temp_storage = cvCreateChildMemStorage( storage );

    assert( src_contour->first != 0 );
    stack = cvCreateSeq( 0, sizeof( CvSeq ), sizeof( CvSlice ), temp_storage );
    eps *= eps;
    
    cvStartReadSeq( src_contour, &reader, 0 );
    count = src_contour->total;
    is_closed = CV_IS_SEQ_CLOSED( src_contour );

    if( !is_closed )
    {
        right_slice.startIndex = count;
        end_pt = *(CvPoint*)(reader.ptr);
        start_pt = *(CvPoint*)cvGetSeqElem( src_contour, -1, 0 );

        if( start_pt.x != end_pt.x || start_pt.y != end_pt.y )
        {
            slice.startIndex = 0;
            slice.endIndex = count - 1;
            cvSeqPush( stack, &slice );
        }
        else
        {
            is_closed = 1;
            init_iters = 1;
        }
    }
    
    if( is_closed )
    {
        /* 1. Find approximately two farthest points of the contour */
        right_slice.startIndex = 0;

        for( i = 0; i < init_iters; i++ )
        {
            int j;

            cvSetSeqReaderPos( &reader, right_slice.startIndex, 1 );
            CV_READ_SEQ_ELEM( start_pt, reader );   /* read the first point */

            if( !is_float )
            {
                int max_dist = 0;

                for( j = 1; j < count; j++ )
                {
                    int dx, dy, dist;

                    CV_READ_SEQ_ELEM( pt, reader );
                    dx = pt.x - start_pt.x;
                    dy = pt.y - start_pt.y;

                    dist = dx * dx + dy * dy;

                    if( dist > max_dist )
                    {
                        max_dist = dist;
                        right_slice.startIndex = j;
                    }
                }

                le_eps = max_dist <= eps;
            }
            else
            {
                CvPoint2D32f start_ptfl = {(float&)start_pt.x,(float&)start_pt.y};
                float max_dist = 0;

                for( j = 1; j < count; j++ )
                {
                    float dx, dy, dist;
                    CvPoint2D32f ptfl;

                    CV_READ_SEQ_ELEM( ptfl, reader );
                    dx = ptfl.x - start_ptfl.x;
                    dy = ptfl.y - start_ptfl.y;
                    dist = dx * dx + dy * dy;

                    if( dist > max_dist )
                    {
                        max_dist = dist;
                        right_slice.startIndex = j;
                    }
                }

                le_eps = max_dist <= eps;
            }
        }

        /* 2. initialize the stack */
        if( !le_eps )
        {
            slice.startIndex = cvGetSeqReaderPos( &reader );
            slice.endIndex = right_slice.startIndex += slice.startIndex;

            right_slice.startIndex -= right_slice.startIndex >= count ? count : 0;
            right_slice.endIndex = slice.startIndex;
            if( right_slice.endIndex < right_slice.startIndex )
                right_slice.endIndex += count;

            cvSeqPush( stack, &right_slice );
            cvSeqPush( stack, &slice );
        }
        else
        {
            CV_WRITE_SEQ_ELEM( start_pt, writer );
        }
    }

    /* 3. run recursive process */
    while( stack->total != 0 )
    {
        cvSeqPop( stack, &slice );

        assert( slice.startIndex < slice.endIndex );

        if( slice.endIndex - slice.startIndex != 1 )
        {
            cvSetSeqReaderPos( &reader, slice.endIndex );
            CV_READ_SEQ_ELEM( end_pt, reader );

            cvSetSeqReaderPos( &reader, slice.startIndex );
            CV_READ_SEQ_ELEM( start_pt, reader );

            if( !is_float )
            {
                int dx = end_pt.x - start_pt.x;
                int dy = end_pt.y - start_pt.y;
                int max_dist = 0;

                assert( (dx | dy) != 0 );

                for( i = slice.startIndex + 1; i < slice.endIndex; i++ )
                {
                    int dist;

                    CV_READ_SEQ_ELEM( pt, reader );

                    dist = (pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy;
                    dist = CV_IABS( dist );

                    if( dist > max_dist )
                    {
                        max_dist = dist;
                        right_slice.startIndex = i;
                    }
                }

                le_eps = (double)max_dist * max_dist <= eps * ((double)dx * dx + (double)dy * dy);
            }
            else
            {
                float sx = (float&)start_pt.x;
                float sy = (float&)start_pt.y;
                float dx = (float&)end_pt.x - sx;
                float dy = (float&)end_pt.y - sy;
                float max_dist = 0;

                assert( ((int&)dx | (int&)dy) != 0 );

                for( i = slice.startIndex + 1; i < slice.endIndex; i++ )
                {
                    float dist;
                    CvPoint2D32f ptfl;

                    CV_READ_SEQ_ELEM( ptfl, reader );

                    dist = (float)fabs((ptfl.y - sy)*dx - (ptfl.x - sx)*dy);

                    if( dist > max_dist )
                    {
                        max_dist = dist;
                        right_slice.startIndex = i;
                    }
                }

                le_eps = (double)max_dist * max_dist <= eps * ((double)dx * dx + (double)dy * dy);
            }
        }
        else
        {
            le_eps = 1;
            /* read starting point */
            cvSetSeqReaderPos( &reader, slice.startIndex );
            CV_READ_SEQ_ELEM( start_pt, reader );
        }

        if( le_eps )
        {
            CV_WRITE_SEQ_ELEM( start_pt, writer );
        }
        else
        {
            right_slice.endIndex = slice.endIndex;
            slice.endIndex = right_slice.startIndex;
            cvSeqPush( stack, &right_slice );
            cvSeqPush( stack, &slice );
        }
    }

    if( !CV_IS_SEQ_CLOSED( src_contour ) )
    {
        CV_WRITE_SEQ_ELEM( end_pt, writer );
    }

    *dst_contour = cvEndWriteSeq( &writer );
    cvReleaseMemStorage( &temp_storage );

    return CV_OK;
}


CV_IMPL CvSeq*
cvApproxPoly( const void*  array, int  header_size,
              CvMemStorage*  storage,
              CvPolyApproxMethod  method, 
              double  parameter, int parameter2 )
{
    CvSeq* dst_seq = 0;
    CvSeq *prev_contour = 0, *parent = 0;
    CvContour contour_header;
    CvSeq* src_seq = 0;
    CvSeqBlock block;
    int recursive = 0;

    CV_FUNCNAME( "cvApproxPoly" );

    __BEGIN__;

    if( CV_IS_SEQ( array ))
    {
        src_seq = (CvSeq*)array;
        if( !CV_IS_SEQ_POLYLINE( src_seq ))
            CV_ERROR( CV_StsBadArg, "Unsupported sequence type" );

        recursive = parameter2;

        if( !storage )
            storage = src_seq->storage;
    }
    else
    {
        CV_CALL( src_seq = icvPointSeqFromMat(
            CV_SEQ_KIND_CURVE | (parameter2 ? CV_SEQ_FLAG_CLOSED : 0),
            array, &contour_header, &block ));
    }

    if( !storage )
        CV_ERROR( CV_StsNullPtr, "NULL storage pointer " );

    if( header_size < 0 )
        CV_ERROR( CV_StsOutOfRange, "header_size is negative. "
                  "Pass 0 to make the destination header_size == input header_size" );

    if( header_size == 0 )
        header_size = src_seq->header_size;

    if( !CV_IS_SEQ_POLYLINE( src_seq ))
    {
        if( CV_IS_SEQ_CHAIN( src_seq ))
        {
            CV_ERROR( CV_StsBadArg, "Input curves are not polygonal. "
                                    "Use cvApproxChains first" );
        }
        else
        {
            CV_ERROR( CV_StsBadArg, "Input curves have uknown type" );
        }
    }

    if( header_size == 0 )
        header_size = src_seq->header_size;

    if( header_size < (int)sizeof(CvContour) )
        CV_ERROR( CV_StsBadSize, "New header size must be non-less than sizeof(CvContour)" );

    if( method != CV_POLY_APPROX_DP )
        CV_ERROR( CV_StsOutOfRange, "Unknown approximation method" );

    while( src_seq != 0 )
    {
        CvSeq *contour = 0;

        switch (method)
        {
        case CV_POLY_APPROX_DP:
            if( parameter < 0 )
                CV_ERROR( CV_StsOutOfRange, "Accuracy must be non-negative" );

            IPPI_CALL( icvApproxPolyDP( src_seq, header_size,
                                        storage, &contour, (float)parameter ));
            break;
        default:
            assert(0);
            CV_ERROR( CV_StsBadArg, "Invalid approximation method" );
        }

        assert( contour );

        if( header_size >= (int)sizeof(CvContour))
            cvBoundingRect( contour, 1 );

        contour->v_prev = parent;
        contour->h_prev = prev_contour;

        if( prev_contour )
            prev_contour->h_next = contour;
        else if( parent )
            parent->v_next = contour;
        prev_contour = contour;
        if( !dst_seq )
            dst_seq = prev_contour;

        if( !recursive )
            break;

        if( src_seq->v_next )
        {
            assert( prev_contour != 0 );
            parent = prev_contour;
            prev_contour = 0;
            src_seq = src_seq->v_next;
        }
        else
        {
            while( src_seq->h_next == 0 )
            {
                src_seq = src_seq->v_prev;
                if( src_seq == 0 )
                    break;
                prev_contour = parent;
                if( parent )
                    parent = parent->v_prev;
            }
            if( src_seq )
                src_seq = src_seq->h_next;
        }
    }

    __END__;

    return dst_seq;
}

/* End of file. */