cvcontourtree.cpp

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

/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  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.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, 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:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's 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.
//
//   * The name of Intel Corporation may not 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 Intel Corporation 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.
//
//M*/
#include "_cv.h"

#define CV_MATCH_CHECK( status, cvFun )                                    \
  {                                                                        \
    status = cvFun;                                                        \
    if( status != CV_OK )                                                  \
     goto M_END;                                                           \
  }

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 );

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Name: icvCreateContourTree
//    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*/
static CvStatus
icvCreateContourTree( const CvSeq * contour, CvMemStorage * storage,
                      CvContourTree ** tree, double threshold )
{
    CvPoint *pt_p;              /*  pointer to previos points   */
    CvPoint *pt_n;              /*  pointer to next points      */
    CvPoint *pt1, *pt2;         /*  pointer to current points   */

    CvPoint t, tp1, tp2, tp3, tn1, tn2, tn3;
    int lpt, flag, i, j, i_tree, j_1, j_3, i_buf;
    double s, sp1, sp2, sn1, sn2, s_c, sp1_c, sp2_c, sn1_c, sn2_c, h, hp1, hp2, hn1, hn2,
        a, ap1, ap2, an1, an2, b, bp1, bp2, bn1, bn2;
    double a_s_c, a_sp1_c;

    _CvTrianAttr **ptr_p, **ptr_n, **ptr1, **ptr2;      /*  pointers to pointers of triangles  */
    _CvTrianAttr *cur_adr;

    int *num_p, *num_n, *num1, *num2;   /*   numbers of input contour points   */
    int nm, nmp1, nmp2, nmp3, nmn1, nmn2, nmn3;
    int seq_flags = 1, i_end, prev_null, prev2_null;
    double koef = 1.5;
    double eps = 1.e-7;
    double e;
    CvStatus status;
    int hearder_size;
    _CvTrianAttr tree_one, tree_two, *tree_end, *tree_root;

    CvSeqWriter writer;

    assert( contour != NULL && contour->total >= 4 );
    status = CV_OK;

    if( contour == NULL )
        return CV_NULLPTR_ERR;
    if( contour->total < 4 )
        return CV_BADSIZE_ERR;

    if( !CV_IS_SEQ_POLYGON( contour ))
        return CV_BADFLAG_ERR;


/*   Convert Sequence to array    */
    lpt = contour->total;
    pt_p = pt_n = NULL;
    num_p = num_n = NULL;
    ptr_p = ptr_n = ptr1 = ptr2 = NULL;
    tree_end = NULL;

    pt_p = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
    pt_n = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));

    num_p = (int *) cvAlloc( lpt * sizeof( int ));
    num_n = (int *) cvAlloc( lpt * sizeof( int ));

    hearder_size = sizeof( CvContourTree );
    seq_flags = CV_SEQ_POLYGON_TREE;
    cvStartWriteSeq( seq_flags, hearder_size, sizeof( _CvTrianAttr ), storage, &writer );

    ptr_p = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
    ptr_n = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));

    memset( ptr_p, 0, lpt * sizeof( _CvTrianAttr * ));
    memset( ptr_n, 0, lpt * sizeof( _CvTrianAttr * ));

    if( pt_p == NULL || pt_n == NULL )
        return CV_OUTOFMEM_ERR;
    if( ptr_p == NULL || ptr_n == NULL )
        return CV_OUTOFMEM_ERR;

/*     write fild for the binary tree root   */
/*  start_writer = writer;   */

    tree_one.pt.x = tree_one.pt.y = 0;
    tree_one.sign = 0;
    tree_one.area = 0;
    tree_one.r1 = tree_one.r2 = 0;
    tree_one.next_v1 = tree_one.next_v2 = tree_one.prev_v = NULL;

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

    if( cvCvtSeqToArray( contour, (char *) pt_p ) == (char *) contour )
        return CV_BADPOINT_ERR;

    for( i = 0; i < lpt; i++ )
        num_p[i] = i;

    i = lpt;
    flag = 0;
    i_tree = 0;
    e = 20.;                    /*  initial threshold value   */
    ptr1 = ptr_p;
    ptr2 = ptr_n;
    pt1 = pt_p;
    pt2 = pt_n;
    num1 = num_p;
    num2 = num_n;
/*  binary tree constraction    */
    while( i > 4 )
    {
        if( flag == 0 )
        {
            ptr1 = ptr_p;
            ptr2 = ptr_n;
            pt1 = pt_p;
            pt2 = pt_n;
            num1 = num_p;
            num2 = num_n;
            flag = 1;
        }
        else
        {
            ptr1 = ptr_n;
            ptr2 = ptr_p;
            pt1 = pt_n;
            pt2 = pt_p;
            num1 = num_n;
            num2 = num_p;
            flag = 0;
        }
        t = pt1[0];
        nm = num1[0];
        tp1 = pt1[i - 1];
        nmp1 = num1[i - 1];
        tp2 = pt1[i - 2];
        nmp2 = num1[i - 2];
        tp3 = pt1[i - 3];
        nmp3 = num1[i - 3];
        tn1 = pt1[1];
        nmn1 = num1[1];
        tn2 = pt1[2];
        nmn2 = num1[2];

        i_buf = 0;
        i_end = -1;
        CV_MATCH_CHECK( status,
                        icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a,
                                        &b ));
        CV_MATCH_CHECK( status,
                        icvCalcTriAttr( contour, tp1, tp2, nmp2, t, nm, &sp1, &sp1_c, &hp1,
                                        &ap1, &bp1 ));
        CV_MATCH_CHECK( status,
                        icvCalcTriAttr( contour, tp2, tp3, nmp3, tp1, nmp1, &sp2, &sp2_c, &hp2,
                                        &ap2, &bp2 ));
        CV_MATCH_CHECK( status,
                        icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1,
                                        &an1, &bn1 ));


        j_3 = 3;
        prev_null = prev2_null = 0;
        for( j = 0; j < i; j++ )
        {
            tn3 = pt1[j_3];
            nmn3 = num1[j_3];
            if( j == 0 )
                j_1 = i - 1;
            else
                j_1 = j - 1;

            CV_MATCH_CHECK( status, icvCalcTriAttr( contour, tn2, tn1, nmn1, tn3, nmn3,
                                                    &sn2, &sn2_c, &hn2, &an2, &bn2 ));

            if( (s_c < sp1_c && s_c < sp2_c && s_c <= sn1_c && s_c <= sn2_c && s_c < e) ||
                (s_c == sp1_c && s_c <= sp2_c || s_c == sp2_c && s_c <= sp1_c) && s_c <= sn1_c
                && s_c <= sn2_c && s_c < e && j > 1 && prev2_null == 0 || (s_c < eps && j > 0
                                                                           && prev_null == 0) )

            {
                prev_null = prev2_null = 1;
                if( s_c < threshold )
                {
                    if( ptr1[j_1] == NULL && ptr1[j] == NULL )
                    {
                        if( i_buf > 0 )
                            ptr2[i_buf - 1] = NULL;
                        else
                            i_end = 0;
                    }
                    else
                    {
/*   form next vertex  */
                        tree_one.pt = t;
                        tree_one.sign = (char) (CV_SIGN( s ));
                        tree_one.r1 = h / a;
                        tree_one.r2 = b / a;
                        tree_one.area = fabs( s );
                        tree_one.next_v1 = ptr1[j_1];
                        tree_one.next_v2 = ptr1[j];

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

                        if( ptr1[j_1] != NULL )
                            ptr1[j_1]->prev_v = cur_adr;
                        if( ptr1[j] != NULL )
                            ptr1[j]->prev_v = cur_adr;

                        if( i_buf > 0 )
                            ptr2[i_buf - 1] = cur_adr;
                        else
                        {
                            tree_end = (_CvTrianAttr *) writer.ptr;
                            i_end = 1;
                        }
                        i_tree++;
                    }
                }
                else
/*   form next vertex    */
                {
                    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 = ptr1[j_1];
                    tree_one.next_v2 = ptr1[j];

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

                    if( ptr1[j_1] != NULL )
                        ptr1[j_1]->prev_v = cur_adr;
                    if( ptr1[j] != NULL )
                        ptr1[j]->prev_v = cur_adr;

                    if( i_buf > 0 )
                        ptr2[i_buf - 1] = cur_adr;
                    else
                    {
                        tree_end = cur_adr;
                        i_end = 1;
                    }
                    i_tree++;
                }
            }
            else
/*   the current triangle is'not LMIAT    */
            {
                prev_null = 0;
                switch (prev2_null)
                {
                case 0:
                    break;
                case 1:
                    {
                        prev2_null = 2;
                        break;
                    }
                case 2:
                    {
                        prev2_null = 0;
                        break;
                    }
                }
                if( j != i - 1 || i_end == -1 )
                    ptr2[i_buf] = ptr1[j];
                else if( i_end == 0 )
                    ptr2[i_buf] = NULL;
                else
                    ptr2[i_buf] = tree_end;
                pt2[i_buf] = t;
                num2[i_buf] = num1[j];
                i_buf++;
            }
/*    go to next vertex    */
            tp3 = tp2;
            tp2 = tp1;
            tp1 = t;
            t = tn1;
            tn1 = tn2;
            tn2 = tn3;
            nmp3 = nmp2;
            nmp2 = nmp1;
            nmp1 = nm;
            nm = nmn1;
            nmn1 = nmn2;
            nmn2 = nmn3;

            sp2 = sp1;
            sp1 = s;
            s = sn1;
            sn1 = sn2;
            sp2_c = sp1_c;
            sp1_c = s_c;
            s_c = sn1_c;
            sn1_c = sn2_c;

            ap2 = ap1;
            ap1 = a;
            a = an1;
            an1 = an2;
            bp2 = bp1;
            bp1 = b;
            b = bn1;
            bn1 = bn2;
            hp2 = hp1;
            hp1 = h;
            h = hn1;
            hn1 = hn2;
            j_3++;
            if( j_3 >= i )
                j_3 = 0;
        }

        i = i_buf;
        e = e * koef;
    }

/*  constract tree root  */
    if( i != 4 )
        return CV_BADFACTOR_ERR;

    t = pt2[0];
    tn1 = pt2[1];
    tn2 = pt2[2];
    tp1 = pt2[3];
    nm = num2[0];
    nmn1 = num2[1];
    nmn2 = num2[2];
    nmp1 = num2[3];
/*   first pair of the triangles   */
    CV_MATCH_CHECK( status,
                    icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, &b ));
    CV_MATCH_CHECK( status,
                    icvCalcTriAttr( contour, tn2, tn1, nmn1, tp1, nmp1, &sn2, &sn2_c, &hn2,
                                    &an2, &bn2 ));
/*   second pair of the triangles   */
    CV_MATCH_CHECK( status,
                    icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1,
                                    &bn1 ));
    CV_MATCH_CHECK( status,
                    icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1,
                                    &bp1 ));

    a_s_c = fabs( s_c - sn2_c );