cvfloodfill.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 CvFFillSegment
{
    ushort y;
    ushort l;
    ushort r;
    ushort prevl;
    ushort prevr;
    short dir;
}
CvFFillSegment;

#define UP 1
#define DOWN -1             

#define ICV_PUSH( Y, L, R, PREV_L, PREV_R, DIR )\
{                                               \
    tail->y = (ushort)(Y);                      \
    tail->l = (ushort)(L);                      \
    tail->r = (ushort)(R);                      \
    tail->prevl = (ushort)(PREV_L);             \
    tail->prevr = (ushort)(PREV_R);             \
    tail->dir = (short)(DIR);                   \
    if( ++tail >= buffer_end )                  \
        tail = buffer;                          \
}


#define ICV_POP( Y, L, R, PREV_L, PREV_R, DIR ) \
{                                               \
    Y = head->y;                                \
    L = head->l;                                \
    R = head->r;                                \
    PREV_L = head->prevl;                       \
    PREV_R = head->prevr;                       \
    DIR = head->dir;                            \
    if( ++head >= buffer_end )                  \
        head = buffer;                          \
}


#define ICV_EQ_C3( p1, p2 ) \
    ((p1)[0] == (p2)[0] && (p1)[1] == (p2)[1] && (p1)[2] == (p2)[2])

#define ICV_SET_C3( p, q ) \
    ((p)[0] = (q)[0], (p)[1] = (q)[1], (p)[2] = (q)[2])

/****************************************************************************************\
*              Simple Floodfill (repainting single-color connected component)            *
\****************************************************************************************/

static CvStatus
icvFloodFill_8u_CnIR( uchar* pImage, int step, CvSize roi, CvPoint seed,
                      uchar* _newVal, CvConnectedComp* region, int flags,
                      CvFFillSegment* buffer, int buffer_size, int cn )
{
    uchar* img = pImage + step * seed.y;
    int i, L, R; 
    int area = 0;
    int val0[] = {0,0,0};
    uchar newVal[] = {0,0,0};
    int XMin, XMax, YMin = seed.y, YMax = seed.y;
    int _8_connectivity = (flags & 255) == 8;
    CvFFillSegment* buffer_end = buffer + buffer_size, *head = buffer, *tail = buffer;

    L = R = XMin = XMax = seed.x;

    if( cn == 1 )
    {
        val0[0] = img[L];
        newVal[0] = _newVal[0];

        img[L] = newVal[0];

        while( ++R < roi.width && img[R] == val0[0] )
            img[R] = newVal[0];

        while( --L >= 0 && img[L] == val0[0] )
            img[L] = newVal[0];
    }
    else
    {
        assert( cn == 3 );
        ICV_SET_C3( val0, img + L*3 );
        ICV_SET_C3( newVal, _newVal );
        
        ICV_SET_C3( img + L*3, newVal );
    
        while( --L >= 0 && ICV_EQ_C3( img + L*3, val0 ))
            ICV_SET_C3( img + L*3, newVal );
    
        while( ++R < roi.width && ICV_EQ_C3( img + R*3, val0 ))
            ICV_SET_C3( img + R*3, newVal );
    }

    XMax = --R;
    XMin = ++L;
    ICV_PUSH( seed.y, L, R, R + 1, R, UP );

    while( head != tail )
    {
        int k, YC, PL, PR, dir;
        ICV_POP( YC, L, R, PL, PR, dir );

        int data[][3] =
        {
            {-dir, L - _8_connectivity, R + _8_connectivity},
            {dir, L - _8_connectivity, PL - 1},
            {dir, PR + 1, R + _8_connectivity}
        };

        if( region )
        {
            area += R - L + 1;

            if( XMax < R ) XMax = R;
            if( XMin > L ) XMin = L;
            if( YMax < YC ) YMax = YC;
            if( YMin > YC ) YMin = YC;
        }

        for( k = 0/*(unsigned)(YC - dir) >= (unsigned)roi.height*/; k < 3; k++ )
        {
            dir = data[k][0];
            img = pImage + (YC + dir) * step;
            int left = data[k][1];
            int right = data[k][2];

            if( (unsigned)(YC + dir) >= (unsigned)roi.height )
                continue;

            if( cn == 1 )
                for( i = left; i <= right; i++ )
                {
                    if( (unsigned)i < (unsigned)roi.width && img[i] == val0[0] )
                    {
                        int j = i;
                        img[i] = newVal[0];
                        while( --j >= 0 && img[j] == val0[0] )
                            img[j] = newVal[0];

                        while( ++i < roi.width && img[i] == val0[0] )
                            img[i] = newVal[0];

                        ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
                    }
                }
            else
                for( i = left; i <= right; i++ )
                {
                    if( (unsigned)i < (unsigned)roi.width && ICV_EQ_C3( img + i*3, val0 ))
                    {
                        int j = i;
                        ICV_SET_C3( img + i*3, newVal );
                        while( --j >= 0 && ICV_EQ_C3( img + j*3, val0 ))
                            ICV_SET_C3( img + j*3, newVal );

                        while( ++i < roi.width && ICV_EQ_C3( img + i*3, val0 ))
                            ICV_SET_C3( img + i*3, newVal );

                        ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
                    }
                }
        }
    }

    if( region )
    {
        region->area = area;
        region->rect.x = XMin;
        region->rect.y = YMin;
        region->rect.width = XMax - XMin + 1;
        region->rect.height = YMax - YMin + 1;
        region->value = cvScalar(newVal[0], newVal[1], newVal[2], 0);
    }

    return CV_NO_ERR;
}


/* because all the operations on floats that are done during non-gradient floodfill
   are just copying and comparison on equality,
   we can do the whole op on 32-bit integers instead */
static CvStatus
icvFloodFill_32f_CnIR( int* pImage, int step, CvSize roi, CvPoint seed,
                       int* _newVal, CvConnectedComp* region, int flags,
                       CvFFillSegment* buffer, int buffer_size, int cn )
{
    int* img = pImage + (step /= sizeof(pImage[0])) * seed.y;
    int i, L, R; 
    int area = 0;
    int val0[] = {0,0,0};
    int newVal[] = {0,0,0};
    int XMin, XMax, YMin = seed.y, YMax = seed.y;
    int _8_connectivity = (flags & 255) == 8;
    CvFFillSegment* buffer_end = buffer + buffer_size, *head = buffer, *tail = buffer;

    L = R = XMin = XMax = seed.x;

    if( cn == 1 )
    {
        val0[0] = img[L];
        newVal[0] = _newVal[0];

        img[L] = newVal[0];

        while( ++R < roi.width && img[R] == val0[0] )
            img[R] = newVal[0];

        while( --L >= 0 && img[L] == val0[0] )
            img[L] = newVal[0];
    }
    else
    {
        assert( cn == 3 );
        ICV_SET_C3( val0, img + L*3 );
        ICV_SET_C3( newVal, _newVal );
        
        ICV_SET_C3( img + L*3, newVal );
    
        while( --L >= 0 && ICV_EQ_C3( img + L*3, val0 ))
            ICV_SET_C3( img + L*3, newVal );
    
        while( ++R < roi.width && ICV_EQ_C3( img + R*3, val0 ))
            ICV_SET_C3( img + R*3, newVal );
    }

    XMax = --R;
    XMin = ++L;
    ICV_PUSH( seed.y, L, R, R + 1, R, UP );

    while( head != tail )
    {
        int k, YC, PL, PR, dir;
        ICV_POP( YC, L, R, PL, PR, dir );

        int data[][3] =
        {
            {-dir, L - _8_connectivity, R + _8_connectivity},
            {dir, L - _8_connectivity, PL - 1},
            {dir, PR + 1, R + _8_connectivity}
        };

        if( region )
        {
            area += R - L + 1;

            if( XMax < R ) XMax = R;
            if( XMin > L ) XMin = L;
            if( YMax < YC ) YMax = YC;
            if( YMin > YC ) YMin = YC;
        }

        for( k = 0/*(unsigned)(YC - dir) >= (unsigned)roi.height*/; k < 3; k++ )
        {
            dir = data[k][0];
            img = pImage + (YC + dir) * step;
            int left = data[k][1];
            int right = data[k][2];

            if( (unsigned)(YC + dir) >= (unsigned)roi.height )
                continue;

            if( cn == 1 )
                for( i = left; i <= right; i++ )
                {
                    if( (unsigned)i < (unsigned)roi.width && img[i] == val0[0] )
                    {
                        int j = i;
                        img[i] = newVal[0];
                        while( --j >= 0 && img[j] == val0[0] )
                            img[j] = newVal[0];

                        while( ++i < roi.width && img[i] == val0[0] )
                            img[i] = newVal[0];

                        ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
                    }
                }
            else
                for( i = left; i <= right; i++ )
                {
                    if( (unsigned)i < (unsigned)roi.width && ICV_EQ_C3( img + i*3, val0 ))
                    {
                        int j = i;
                        ICV_SET_C3( img + i*3, newVal );
                        while( --j >= 0 && ICV_EQ_C3( img + j*3, val0 ))
                            ICV_SET_C3( img + j*3, newVal );

                        while( ++i < roi.width && ICV_EQ_C3( img + i*3, val0 ))
                            ICV_SET_C3( img + i*3, newVal );

                        ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
                    }
                }
        }
    }

    if( region )
    {
        Cv32suf v0, v1, v2;
        region->area = area;
        region->rect.x = XMin;
        region->rect.y = YMin;
        region->rect.width = XMax - XMin + 1;
        region->rect.height = YMax - YMin + 1;
        v0.i = newVal[0]; v1.i = newVal[1]; v2.i = newVal[2];
        region->value = cvScalar( v0.f, v1.f, v2.f );
    }

    return CV_NO_ERR;
}

/****************************************************************************************\
*                                   Gradient Floodfill                                   *
\****************************************************************************************/

#define DIFF_INT_C1(p1,p2) ((unsigned)((p1)[0] - (p2)[0] + d_lw[0]) <= interval[0])

#define DIFF_INT_C3(p1,p2) ((unsigned)((p1)[0] - (p2)[0] + d_lw[0])<= interval[0] && \
                            (unsigned)((p1)[1] - (p2)[1] + d_lw[1])<= interval[1] && \
                            (unsigned)((p1)[2] - (p2)[2] + d_lw[2])<= interval[2])

#define DIFF_FLT_C1(p1,p2) (fabs((p1)[0] - (p2)[0] + d_lw[0]) <= interval[0])

#define DIFF_FLT_C3(p1,p2) (fabs((p1)[0] - (p2)[0] + d_lw[0]) <= interval[0] && \
                            fabs((p1)[1] - (p2)[1] + d_lw[1]) <= interval[1] && \
                            fabs((p1)[2] - (p2)[2] + d_lw[2]) <= interval[2])

static CvStatus
icvFloodFill_Grad_8u_CnIR( uchar* pImage, int step, uchar* pMask, int maskStep,
                           CvSize /*roi*/, CvPoint seed, uchar* _newVal, uchar* _d_lw,
                           uchar* _d_up, CvConnectedComp* region, int flags,
                           CvFFillSegment* buffer, int buffer_size, int cn )
{
    uchar* img = pImage + step*seed.y;
    uchar* mask = (pMask += maskStep + 1) + maskStep*seed.y;
    int i, L, R;
    int area = 0;
    int sum[] = {0,0,0}, val0[] = {0,0,0};
    uchar newVal[] = {0,0,0};
    int d_lw[] = {0,0,0};