cvpyrsegmentation.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"

typedef struct _CvRGBf
{   float blue;
    float green;
    float red;
}
_CvRGBf;

typedef struct _CvRect16u
{
    ushort x1, y1, x2, y2;
}
_CvRect16u;

typedef struct _CvPyramid
{
    float c;
    struct _CvPyramid *p;
    int a;
    _CvRect16u rect;      /*  ROI for the connected component    */
} _CvPyramid;

/* element of base layer */
typedef struct _CvPyramidBase
{
    float c;
    struct _CvPyramid *p;
}
_CvPyramidBase;

typedef struct _CvPyramidC3
{
    _CvRGBf c;
    struct _CvPyramidC3 *p;
    int a;
    _CvRect16u rect;      /*  ROI for the connected component    */
} _CvPyramidC3;

/* element of base layer */
typedef struct _CvPyramidBaseC3
{
    _CvRGBf c;
    struct _CvPyramidC3 *p;
}
_CvPyramidBaseC3;

typedef struct _CvListNode
{
    struct _CvListNode* next;
    void* data;
}
_CvListNode;


static CvStatus  icvSegmentClusterC1( CvSeq* cmp_seq, CvSeq* res_seq,
                                 double threshold,
                                 _CvPyramid* first_level_end,
                                 CvSize first_level_size );

static CvStatus  icvSegmentClusterC3( CvSeq* cmp_seq, CvSeq* res_seq,
                                 double threshold,
                                 _CvPyramidC3* first_level_end,
                                 CvSize first_level_size );

static CvStatus icvUpdatePyrLinks_8u_C1
    (int layer, void *layer_data, CvSize size, void *parent_layer,
     void *_writer, float threshold, int is_last_iter, void *_stub, CvWriteNodeFunction /*func*/);

static CvStatus icvUpdatePyrLinks_8u_C3
    (int layer, void *layer_data, CvSize size, void *parent_layer,
     void *_writer, float threshold, int is_last_iter, void *_stub, CvWriteNodeFunction /*func*/);

static void icvMaxRoi( _CvRect16u *max_rect, _CvRect16u* cur_rect );
static void icvMaxRoi1( _CvRect16u *max_rect, int x, int y );


#define _CV_CHECK( icvFun )                                             \
  {                                                                     \
    if( icvFun != CV_OK )                                               \
     goto M_END;                                                        \
  }


#define _CV_MAX3( a, b, c) ((a)>(b) ? ((a)>(c) ? (a) : (c)) : ((b)>(c) ? (b) : (c)))

/*#define _CV_RGB_DIST(a, b)  _CV_MAX3((float)fabs((a).red - (b).red),      \
                                       (float)fabs((a).green - (b).green),  \
                                       (float)fabs((a).blue - (b).blue))*/

#define _CV_NEXT_BASE_C1(p,n) (_CvPyramid*)((char*)(p) + (n)*sizeof(_CvPyramidBase))
#define _CV_NEXT_BASE_C3(p,n) (_CvPyramidC3*)((char*)(p) + (n)*sizeof(_CvPyramidBaseC3))


CV_INLINE float icvRGBDist_Max( const _CvRGBf& a, const _CvRGBf& b )
{
    float tr = (float)fabs(a.red - b.red);
    float tg = (float)fabs(a.green - b.green);
    float tb = (float)fabs(a.blue - b.blue);

    return _CV_MAX3( tr, tg, tb );
}

CV_INLINE float icvRGBDist_Sum( const _CvRGBf& a, const _CvRGBf& b )
{
    float tr = (float)fabs(a.red - b.red);
    float tg = (float)fabs(a.green - b.green);
    float tb = (float)fabs(a.blue - b.blue);
    
    return (tr + tg + tb);
}

#if 1
#define _CV_RGB_DIST  icvRGBDist_Max
#define _CV_RGB_THRESH_SCALE   1
#else
#define _CV_RGB_DIST  icvRGBDist_Sum
#define _CV_RGB_THRESH_SCALE   3
#endif

#define _CV_INV_TAB_SIZE   32

static const float icvInvTab[ /*_CV_INV_TAB_SIZE*/ ] =
{
    1.00000000f, 0.50000000f, 0.33333333f, 0.25000000f, 0.20000000f, 0.16666667f,
    0.14285714f, 0.12500000f, 0.11111111f, 0.10000000f, 0.09090909f, 0.08333333f,
    0.07692308f, 0.07142857f, 0.06666667f, 0.06250000f, 0.05882353f, 0.05555556f,
    0.05263158f, 0.05000000f, 0.04761905f, 0.04545455f, 0.04347826f, 0.04166667f,
    0.04000000f, 0.03846154f, 0.03703704f, 0.03571429f, 0.03448276f, 0.03333333f,
    0.03225806f, 0.03125000f
};

static void
icvWritePyrNode( void *elem, void *writer )
{
    CV_WRITE_SEQ_ELEM( *(_CvListNode *) elem, *(CvSeqWriter *) writer );
}


static CvStatus
icvPyrSegmentation8uC1R( uchar * src_image, int src_step,
                         uchar * dst_image, int dst_step,
                         CvSize roi, CvFilter filter,
                         CvSeq ** dst_comp, CvMemStorage * storage,
                         int level, int threshold1, int threshold2 )
{
    int i, j, l;
    int step;
    const int max_iter = 3;     /* maximum number of iterations */
    int cur_iter = 0;           /* current iteration */

    _CvPyramid *pyram[16];      /* pointers to the pyramid down up to level */

    float *pyramida = 0;
    _CvPyramid stub;

    _CvPyramid *p_cur;
    _CvPyramidBase *p_base;
    _CvListNode cmp_node;

    CvSeq *cmp_seq = 0;
    CvSeq *res_seq = 0;
    CvMemStorage *temp_storage = 0;
    CvSize size;
    CvStatus status;
    CvSeqWriter writer;

    int buffer_size;
    char *buffer = 0;

    status = CV_OK;

    /* clear pointer to resultant sequence */
    if( dst_comp )
        *dst_comp = 0;

    /* check args */
    if( !src_image || !dst_image || !storage || !dst_comp )
        return CV_NULLPTR_ERR;
    if( roi.width <= 0 || roi.height <= 0 || src_step < roi.width || dst_step < roi.width )
        return CV_BADSIZE_ERR;
    if( filter != CV_GAUSSIAN_5x5 )
        return CV_BADRANGE_ERR;
    if( threshold1 < 0 || threshold2 < 0 )
        return CV_BADRANGE_ERR;
    if( level <= 0 )
        return CV_BADRANGE_ERR;

    if( ((roi.width | roi.height) & ((1 << level) - 1)) != 0 )
        return CV_BADCOEF_ERR;

    temp_storage = cvCreateChildMemStorage( storage );

    /* sequence for temporary components */
    cmp_seq = cvCreateSeq( 0, sizeof( CvSeq ), sizeof( _CvListNode ), temp_storage );
    assert( cmp_seq != 0 );

    res_seq = cvCreateSeq( CV_SEQ_CONNECTED_COMP, sizeof( CvSeq ),
                           sizeof( CvConnectedComp ), storage );
    assert( res_seq != 0 );

    /* calculate buffer size */
    buffer_size = roi.width * roi.height * (sizeof( float ) + sizeof( _CvPyramidBase ));

    for( l = 1; l <= level; l++ )
        buffer_size += ((roi.width >> l) + 1) * ((roi.height >> l) + 1) * sizeof(_CvPyramid);

    /* allocate buffer */
    buffer = (char *) cvAlloc( buffer_size );
    if( !buffer )
    {
        status = CV_OUTOFMEM_ERR;
        goto M_END;
    }

    pyramida = (float *) buffer;

    /* initialization pyramid-linking properties down up to level */
    step = roi.width * sizeof( float );

    {
        CvMat _src;
        CvMat _pyramida;
        cvInitMatHeader( &_src, roi.height, roi.width, CV_8UC1, src_image, src_step );
        cvInitMatHeader( &_pyramida, roi.height, roi.width, CV_32FC1, pyramida, step );
        cvConvert( &_src, &_pyramida );
        /*_CV_CHECK( icvCvtTo_32f_C1R( src_image, src_step, pyramida, step, roi, CV_8UC1 ));*/
    }
    p_base = (_CvPyramidBase *) (buffer + step * roi.height);
    pyram[0] = (_CvPyramid *) p_base;

    /* fill base level of pyramid */
    for( i = 0; i < roi.height; i++ )
    {
        for( j = 0; j < roi.width; j++, p_base++ )
        {
            p_base->c = pyramida[i * roi.width + j];
            p_base->p = &stub;
        }
    }

    p_cur = (_CvPyramid *) p_base;
    size = roi;

    /* calculate initial pyramid */
    for( l = 1; l <= level; l++ )
    {
        CvSize dst_size = { size.width/2+1, size.height/2+1 };
        CvMat prev_level = cvMat( size.height, size.width, CV_32FC1 );
        CvMat next_level = cvMat( dst_size.height, dst_size.width, CV_32FC1 );

        cvSetData( &prev_level, pyramida, step );
        cvSetData( &next_level, pyramida, step );
        cvPyrDown( &prev_level, &next_level );
        
        //_CV_CHECK( icvPyrDown_Gauss5x5_32f_C1R( pyramida, step, pyramida, step, size, buff ));
        //_CV_CHECK( icvPyrDownBorder_32f_CnR( pyramida, step, size, pyramida, step, dst_size, 1 ));
        pyram[l] = p_cur;

        size.width = dst_size.width - 1;
        size.height = dst_size.height - 1;

        /* fill layer #l */
        for( i = 0; i <= size.height; i++ )
        {
            for( j = 0; j <= size.width; j++, p_cur++ )
            {
                p_cur->c = pyramida[i * roi.width + j];
                p_cur->p = &stub;
                p_cur->a = 0;
                p_cur->rect.x2 = 0;
            }
        }
    }

    cvStartAppendToSeq( cmp_seq, &writer );

    /* do several iterations to determine son-father links */
    for( cur_iter = 0; cur_iter < max_iter; cur_iter++ )
    {
        int is_last_iter = cur_iter == max_iter - 1;

        size = roi;

        /* build son-father links down up to level */
        for( l = 0; l < level; l++ )
        {
            icvUpdatePyrLinks_8u_C1( l, pyram[l], size, pyram[l + 1], &writer,
                                      (float) threshold1, is_last_iter, &stub,
                                      (CvWriteNodeFunction)icvWritePyrNode );

            /* clear last border row */
            if( l > 0 )
            {
                p_cur = pyram[l] + (size.width + 1) * size.height;
                for( j = 0; j <= size.width; j++ )
                    p_cur[j].c = 0;
            }

            size.width >>= 1;
            size.height >>= 1;
        }

/*  clear the old c value for the last level     */
        p_cur = pyram[level];
        for( i = 0; i <= size.height; i++, p_cur += size.width + 1 )
            for( j = 0; j <= size.width; j++ )
                p_cur[j].c = 0;

        size = roi;
        step = roi.width;

/* calculate average c value for the 0 < l <=level   */
        for( l = 0; l < level; l++, step = (step >> 1) + 1 )
        {
            _CvPyramid *p_prev, *p_row_prev;

            stub.c = 0;

            /* calculate average c value for the next level   */
            if( l == 0 )
            {
                p_base = (_CvPyramidBase *) pyram[0];
                for( i = 0; i < roi.height; i++, p_base += size.width )
                {
                    for( j = 0; j < size.width; j += 2 )
                    {
                        _CvPyramid *p1 = p_base[j].p;
                        _CvPyramid *p2 = p_base[j + 1].p;

                        p1->c += p_base[j].c;
                        p2->c += p_base[j + 1].c;
                    }
                }
            }
            else
            {
                p_cur = pyram[l];
                for( i = 0; i < size.height; i++, p_cur += size.width + 1 )
                {
                    for( j = 0; j < size.width; j += 2 )
                    {
                        _CvPyramid *p1 = p_cur[j].p;
                        _CvPyramid *p2 = p_cur[j + 1].p;

                        float t0 = (float) p_cur[j].a * p_cur[j].c;
                        float t1 = (float) p_cur[j + 1].a * p_cur[j + 1].c;

                        p1->c += t0;
                        p2->c += t1;

                        if( !is_last_iter )
                            p_cur[j].a = p_cur[j + 1].a = 0;
                    }
                    if( !is_last_iter )
                        p_cur[size.width].a = 0;
                }
                if( !is_last_iter )
                {
                    for( j = 0; j <= size.width; j++ )
                    {
                        p_cur[j].a = 0;
                    }
                }
            }

            /* assign random values of the next level null c   */
            p_cur = pyram[l + 1];
            p_row_prev = p_prev = pyram[l];

            size.width >>= 1;
            size.height >>= 1;

            for( i = 0; i <= size.height; i++, p_cur += size.width + 1 )
            {
                if( i < size.height || !is_last_iter )
                {
                    for( j = 0; j < size.width; j++ )
                    {
                        int a = p_cur[j].a;

                        if( a != 0 )
                        {
                            if( a <= _CV_INV_TAB_SIZE )
                            {
                                p_cur[j].c *= icvInvTab[a - 1];
                            }
                            else
                            {
                                p_cur[j].c /= a;
                            }
                        }
                        else
                        {
                            p_cur[j].c = p_prev->c;
                        }
                        
                        if( l == 0 )
                            p_prev = _CV_NEXT_BASE_C1(p_prev,2);
                        else
                            p_prev += 2;
                    }

                    if( p_cur[size.width].a == 0 )
                    {
                        p_cur[size.width].c = p_prev[(l != 0) - 1].c;
                    }
                    else
                    {
                        p_cur[size.width].c /= p_cur[size.width].a;
                        if( is_last_iter )
                        {
                            cmp_node.data = p_cur + size.width;
                            CV_WRITE_SEQ_ELEM( cmp_node, writer );
                        }
                    }
                }
                else
                {
                    for( j = 0; j <= size.width; j++ )
                    {
                        int a = p_cur[j].a;

                        if( a != 0 )
                        {
                            if( a <= _CV_INV_TAB_SIZE )
                            {
                                p_cur[j].c *= icvInvTab[a - 1];
                            }
                            else
                            {