cvcontourtree.cpp

opencv库在TI DM6437上的移植,目前包括两个库cv.lib和cxcore.lib的工程

    a_sp1_c = fabs( sp1_c - sn1_c );

    if( a_s_c > a_sp1_c )
/*   form child vertexs for the root     */
    {
        tree_one.pt = t;
        tree_one.sign = (char) (CV_SIGN( s ));
        tree_one.area = fabs( s );
        tree_one.r1 = h / a;
        tree_one.r2 = b / a;
        tree_one.next_v1 = ptr2[3];
        tree_one.next_v2 = ptr2[0];

        tree_two.pt = tn2;
        tree_two.sign = (char) (CV_SIGN( sn2 ));
        tree_two.area = fabs( sn2 );
        tree_two.r1 = hn2 / an2;
        tree_two.r2 = bn2 / an2;
        tree_two.next_v1 = ptr2[1];
        tree_two.next_v2 = ptr2[2];

        CV_WRITE_SEQ_ELEM( tree_one, writer );
        cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

        if( s_c > sn2_c )
        {
            if( ptr2[3] != NULL )
                ptr2[3]->prev_v = cur_adr;
            if( ptr2[0] != NULL )
                ptr2[0]->prev_v = cur_adr;
            ptr1[0] = cur_adr;

            i_tree++;

            CV_WRITE_SEQ_ELEM( tree_two, writer );
            cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

            if( ptr2[1] != NULL )
                ptr2[1]->prev_v = cur_adr;
            if( ptr2[2] != NULL )
                ptr2[2]->prev_v = cur_adr;
            ptr1[1] = cur_adr;

            i_tree++;

            pt1[0] = tp1;
            pt1[1] = tn1;
        }
        else
        {
            CV_WRITE_SEQ_ELEM( tree_two, writer );
            cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

            if( ptr2[1] != NULL )
                ptr2[1]->prev_v = cur_adr;
            if( ptr2[2] != NULL )
                ptr2[2]->prev_v = cur_adr;
            ptr1[0] = cur_adr;

            i_tree++;

            CV_WRITE_SEQ_ELEM( tree_one, writer );
            cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

            if( ptr2[3] != NULL )
                ptr2[3]->prev_v = cur_adr;
            if( ptr2[0] != NULL )
                ptr2[0]->prev_v = cur_adr;
            ptr1[1] = cur_adr;

            i_tree++;

            pt1[0] = tn1;
            pt1[1] = tp1;
        }
    }
    else
    {
        tree_one.pt = tp1;
        tree_one.sign = (char) (CV_SIGN( sp1 ));
        tree_one.area = fabs( sp1 );
        tree_one.r1 = hp1 / ap1;
        tree_one.r2 = bp1 / ap1;
        tree_one.next_v1 = ptr2[2];
        tree_one.next_v2 = ptr2[3];

        tree_two.pt = tn1;
        tree_two.sign = (char) (CV_SIGN( sn1 ));
        tree_two.area = fabs( sn1 );
        tree_two.r1 = hn1 / an1;
        tree_two.r2 = bn1 / an1;
        tree_two.next_v1 = ptr2[0];
        tree_two.next_v2 = ptr2[1];

        CV_WRITE_SEQ_ELEM( tree_one, writer );
        cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

        if( sp1_c > sn1_c )
        {
            if( ptr2[2] != NULL )
                ptr2[2]->prev_v = cur_adr;
            if( ptr2[3] != NULL )
                ptr2[3]->prev_v = cur_adr;
            ptr1[0] = cur_adr;

            i_tree++;

            CV_WRITE_SEQ_ELEM( tree_two, writer );
            cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

            if( ptr2[0] != NULL )
                ptr2[0]->prev_v = cur_adr;
            if( ptr2[1] != NULL )
                ptr2[1]->prev_v = cur_adr;
            ptr1[1] = cur_adr;

            i_tree++;

            pt1[0] = tn2;
            pt1[1] = t;
        }
        else
        {
            CV_WRITE_SEQ_ELEM( tree_two, writer );
            cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

            if( ptr2[0] != NULL )
                ptr2[0]->prev_v = cur_adr;
            if( ptr2[1] != NULL )
                ptr2[1]->prev_v = cur_adr;
            ptr1[0] = cur_adr;

            i_tree++;

            CV_WRITE_SEQ_ELEM( tree_one, writer );
            cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);

            if( ptr2[2] != NULL )
                ptr2[2]->prev_v = cur_adr;
            if( ptr2[3] != NULL )
                ptr2[3]->prev_v = cur_adr;
            ptr1[1] = cur_adr;

            i_tree++;

            pt1[0] = t;
            pt1[1] = tn2;

        }
    }

/*    form root   */
    s = cvContourArea( contour );

    tree_root->pt = pt1[1];
    tree_root->sign = 0;
    tree_root->area = fabs( s );
    tree_root->r1 = 0;
    tree_root->r2 = 0;
    tree_root->next_v1 = ptr1[0];
    tree_root->next_v2 = ptr1[1];
    tree_root->prev_v = NULL;

    ptr1[0]->prev_v = (_CvTrianAttr *) tree_root;
    ptr1[1]->prev_v = (_CvTrianAttr *) tree_root;

/*     write binary tree root   */
/*    CV_WRITE_SEQ_ELEM (tree_one, start_writer);   */
    i_tree++;
/*  create Sequence hearder     */
    *((CvSeq **) tree) = cvEndWriteSeq( &writer );
/*   write points for the main segment into sequence header   */
    (*tree)->p1 = pt1[0];

  M_END:

    cvFree( &ptr_n );
    cvFree( &ptr_p );
    cvFree( &num_n );
    cvFree( &num_p );
    cvFree( &pt_n );
    cvFree( &pt_p );

    return status;
}

/****************************************************************************************\

 triangle attributes calculations 

\****************************************************************************************/
static CvStatus
icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1,
                CvPoint t3, int n3, double *s, double *s_c,
                double *h, double *a, double *b )
{
    double x13, y13, x12, y12, l_base, nx, ny, qq;
    double eps = 1.e-5;

    x13 = t3.x - t1.x;
    y13 = t3.y - t1.y;
    x12 = t2.x - t1.x;
    y12 = t2.y - t1.y;
    qq = x13 * x13 + y13 * y13;
    l_base = cvSqrt( (float) (qq) );
    if( l_base > eps )
    {
        nx = y13 / l_base;
        ny = -x13 / l_base;

        *h = nx * x12 + ny * y12;

        *s = (*h) * l_base / 2.;

        *b = nx * y12 - ny * x12;

        *a = l_base;
/*   calculate interceptive area   */
        *s_c = cvContourArea( contour, cvSlice(n1, n3+1));
    }
    else
    {
        *h = 0;
        *s = 0;
        *s_c = 0;
        *b = 0;
        *a = 0;
    }

    return CV_OK;
}

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Name: cvCreateContourTree
//    Purpose:
//    Create binary tree representation for the contour 
//    Context:
//    Parameters:
//      contour - pointer to input contour object.
//      storage - pointer to the current storage block
//      tree   -  output pointer to the binary tree representation 
//      threshold - threshold for the binary tree building 
//
//F*/
CV_IMPL CvContourTree*
cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold )
{
    CvContourTree* tree = 0;
    
    CV_FUNCNAME( "cvCreateContourTree" );
    __BEGIN__;

    IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold ));

    __CLEANUP__;
    __END__;

    return tree;
}


/*F///////////////////////////////////////////////////////////////////////////////////////
//    Name: icvContourFromContourTree
//    Purpose:
//    reconstracts contour from binary tree representation  
//    Context:
//    Parameters:
//      tree   -  pointer to the input binary tree representation 
//      storage - pointer to the current storage block
//      contour - pointer to output contour object.
//      criteria - criteria for the definition threshold value
//                 for the contour reconstracting (level or precision)
//F*/
CV_IMPL CvSeq*
cvContourFromContourTree( const CvContourTree*  tree,
                          CvMemStorage*  storage,
                          CvTermCriteria  criteria )
{
    CvSeq* contour = 0;
    _CvTrianAttr **ptr_buf = 0;     /*  pointer to the pointer's buffer  */
    int *level_buf = 0;
    int i_buf;

    int lpt;
    double area_all;
    double threshold;
    int cur_level;
    int level;
    int seq_flags;
    char log_iter, log_eps;
    int out_hearder_size;
    _CvTrianAttr *tree_one = 0, tree_root;  /*  current vertex  */

    CvSeqReader reader;
    CvSeqWriter writer;

    CV_FUNCNAME("cvContourFromContourTree");

    __BEGIN__;

    if( !tree )
        CV_ERROR( CV_StsNullPtr, "" );

    if( !CV_IS_SEQ_POLYGON_TREE( tree ))
        CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR );

    criteria = cvCheckTermCriteria( criteria, 0., 100 );

    lpt = tree->total;
    ptr_buf = NULL;
    level_buf = NULL;
    i_buf = 0;
    cur_level = 0;
    log_iter = (char) (criteria.type == CV_TERMCRIT_ITER ||
                       (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
    log_eps = (char) (criteria.type == CV_TERMCRIT_EPS ||
                      (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));

    cvStartReadSeq( (CvSeq *) tree, &reader, 0 );

    out_hearder_size = sizeof( CvContour );

    seq_flags = CV_SEQ_POLYGON;
    cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer );

    ptr_buf = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
    if( ptr_buf == NULL )
        CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
    if( log_iter )
    {
        level_buf = (int *) cvAlloc( lpt * (sizeof( int )));

        if( level_buf == NULL )
            CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
    }

    memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * ));

/*     write the first tree root's point as a start point of the result contour  */
    CV_WRITE_SEQ_ELEM( tree->p1, writer );
/*     write the second tree root"s point into buffer    */

/*     read the root of the tree   */
    CV_READ_SEQ_ELEM( tree_root, reader );

    tree_one = &tree_root;
    area_all = tree_one->area;

    if( log_eps )
        threshold = criteria.epsilon * area_all;
    else
        threshold = 10 * area_all;

    if( log_iter )
        level = criteria.max_iter;
    else
        level = -1;

/*  contour from binary tree constraction    */
    while( i_buf >= 0 )
    {
        if( tree_one != NULL && (cur_level <= level || tree_one->area >= threshold) )
/*   go to left sub tree for the vertex and save pointer to the right vertex   */
/*   into the buffer     */
        {
            ptr_buf[i_buf] = tree_one;
            if( log_iter )
            {
                level_buf[i_buf] = cur_level;
                cur_level++;
            }
            i_buf++;
            tree_one = tree_one->next_v1;
        }
        else
        {
            i_buf--;
            if( i_buf >= 0 )
            {
                CvPoint pt = ptr_buf[i_buf]->pt;
                CV_WRITE_SEQ_ELEM( pt, writer );
                tree_one = ptr_buf[i_buf]->next_v2;
                if( log_iter )
                {
                    cur_level = level_buf[i_buf] + 1;
                }
            }
        }
    }

    contour = cvEndWriteSeq( &writer );
    cvBoundingRect( contour, 1 );

    __CLEANUP__;
    __END__;

    cvFree( &level_buf );
    cvFree( &ptr_buf );

    return contour;
}