OpenCV 소스 코드 중 분수령 알고리즘 watershed 함수 소스 코드 주석

#include "precomp.hpp"

/*******************************************************                                    Watershed                                    **************************************************************************************/
//   ，       img           mask       
typedef struct CvWSNode
{
    struct CvWSNode* next;
    int mask_ofs;
    int img_ofs;
}
CvWSNode;

//   ，       CvWSNode
typedef struct CvWSQueue
{
    CvWSNode* first;
    CvWSNode* last;
}
CvWSQueue;

//     
static CvWSNode*
icvAllocWSNodes( CvMemStorage* storage )
{
    CvWSNode* n = 0;

    int i, count = (storage->block_size - sizeof(CvMemBlock))/sizeof(*n) - 1;

    n = (CvWSNode*)cvMemStorageAlloc( storage, count*sizeof(*n) );
    for( i = 0; i < count-1; i++ )
        n[i].next = n + i + 1;
    n[count-1].next = 0;

    return n;
}


CV_IMPL void
cvWatershed( const CvArr* srcarr, CvArr* dstarr )
{
    const int IN_QUEUE = -2;        //      q       -2
    const int WSHED = -1;           // “   ” mask     -1 
    const int NQ = 256;             //       256，          
    cv::Ptr storage;

    CvMat sstub, *src;
    CvMat dstub, *dst;
    CvSize size;
    CvWSNode* free_node = 0, *node;
    CvWSQueue q[NQ];                //    256 CvWSQueue  ，               ，            
    int active_queue;               //          ，q[active_queue]
    int i, j;
    int db, dg, dr;
    int* mask;                      //          
    uchar* img;                     //          
    int mstep, istep;               // mstep mask        （     ），istep img        
    int subs_tab[513];

    // MAX(a,b) = b + MAX(a-b,0)        
    #define ws_max(a,b) ((b) + subs_tab[(a)-(b)+NQ])
    // MIN(a,b) = a - MAX(a-b,0)        
    #define ws_min(a,b) ((a) - subs_tab[(a)-(b)+NQ])

    //     
    #define ws_push(idx,mofs,iofs)  \
    {                               \
        if( !free_node )            \
            free_node = icvAllocWSNodes( storage );\
        node = free_node;           \
        free_node = free_node->next;\
        node->next = 0;             \
        node->mask_ofs = mofs;      \
        node->img_ofs = iofs;       \
        if( q[idx].last )           \
            q[idx].last->next=node; \
        else                        \
            q[idx].first = node;    \
        q[idx].last = node;         \
    }

    //     
    #define ws_pop(idx,mofs,iofs)   \
    {                               \
        node = q[idx].first;        \
        q[idx].first = node->next;  \
        if( !node->next )           \
            q[idx].last = 0;        \
        node->next = free_node;     \
        free_node = node;           \
        mofs = node->mask_ofs;      \
        iofs = node->img_ofs;       \
    }

    //    ptr1   ptr2       r,g,b       
    #define c_diff(ptr1,ptr2,diff)      \
    {                                   \
        db = abs((ptr1)[0] - (ptr2)[0]);\
        dg = abs((ptr1)[1] - (ptr2)[1]);\
        dr = abs((ptr1)[2] - (ptr2)[2]);\
        diff = ws_max(db,dg);           \
        diff = ws_max(diff,dr);         \
        assert( 0 <= diff && diff <= 255 ); \
    }

    src = cvGetMat( srcarr, &sstub );
    dst = cvGetMat( dstarr, &dstub );

    //       ，    src    8UC3,dst    32SC1，src dst size  
    if( CV_MAT_TYPE(src->type) != CV_8UC3 )
        CV_Error( CV_StsUnsupportedFormat, "Only 8-bit, 3-channel input images are supported" );

    if( CV_MAT_TYPE(dst->type) != CV_32SC1 )
        CV_Error( CV_StsUnsupportedFormat,
            "Only 32-bit, 1-channel output images are supported" );

    if( !CV_ARE_SIZES_EQ( src, dst ))
        CV_Error( CV_StsUnmatchedSizes, "The input and output images must have the same size" );

    size = cvGetMatSize(src);       //      size
    storage = cvCreateMemStorage();

    //    =       / sizeof(      )
    istep = src->step;            // img uchar ， sizeof(uchar) = 1，        
    img = src->data.ptr;          //    uchar    
    mstep = dst->step / sizeof(mask[0]);    // mask int（32SC1） ，sizeof(mask[0]) = 4
    mask = dst->data.i;           //    int    

    memset( q, 0, NQ*sizeof(q[0]) );    //      q

    for( i = 0; i < 256; i++ )
        subs_tab[i] = 0;
    for( i = 256; i <= 512; i++ )
        subs_tab[i] = i - 256;

    // draw a pixel-wide border of dummy "watershed" (i.e. boundary) pixels
    //               
    // mask           
    for( j = 0; j < size.width; j++ )
        mask[j] = mask[j + mstep*(size.height-1)] = WSHED;

    // initial phase: put all the neighbor pixels of each marker to the ordered queue -
    // determine the initial boundaries of the basins
    //     ：                    ，           
    //      （  ，    ，1,2,3...）         ，                      
    //            ，      ，                 ,  ，                   
    //           ，             ，          
    for( i = 1; i < size.height-1; i++ )
    {
        img += istep; mask += mstep;            //     
        mask[0] = mask[size.width-1] = WSHED;   //               ，          ，mask         

        for( j = 1; j < size.width-1; j++ )     //   
        {
            int* m = mask + j;                  // mask     
            if( m[0] < 0 ) m[0] = 0;            //       ，    （             (-1)          ？）
            if( m[0] == 0 && (m[-1] > 0 || m[1] > 0 || m[-mstep] > 0 || m[mstep] > 0) ) //         （0），         （>0）
            {
                //                  ，     （idx）    ，              q[idex]   
                //      r,g,b                     
                uchar* ptr = img + j*3;
                int idx = 256, t;
                if( m[-1] > 0 )                
                    c_diff( ptr, ptr - 3, idx );
                if( m[1] > 0 )
                {
                    c_diff( ptr, ptr + 3, t );
                    idx = ws_min( idx, t );
                }
                if( m[-mstep] > 0 )
                {
                    c_diff( ptr, ptr - istep, t );
                    idx = ws_min( idx, t );
                }
                if( m[mstep] > 0 )
                {
                    c_diff( ptr, ptr + istep, t );
                    idx = ws_min( idx, t );
                }
                assert( 0 <= idx && idx <= 255 );
                ws_push( idx, i*mstep + j, i*istep + j*3 );     //     img mask    （    ）   q[idx]   
                m[0] = IN_QUEUE;         //  mask        
            }
        }
    }

    // find the first non-empty queue
    //            
    for( i = 0; i < NQ; i++ )
        if( q[i].first )
            break;

    // if there is no markers, exit immediately
    //  i=256，    q       
    if( i == NQ )
        return;

    active_queue = i;
    img = src->data.ptr;
    mask = dst->data.i;

    // recursively fill the basins
    //         
    for(;;)
    {
        int mofs, iofs;         //                  mask_offset   img_offset    
        int lab = 0, t;
        int* m;
        uchar* ptr;

        //               ，           
        if( q[active_queue].first == 0 )
        {
            for( i = active_queue+1; i < NQ; i++ )
                if( q[i].first )
                    break;
            if( i == NQ )
                break;
            active_queue = i;
        }

        ws_pop( active_queue, mofs, iofs );     //  q[active_queue]           

        //          img mask     ，     mask     
        //           ：             ，       ；            ，     
        //        ：           
        m = mask + mofs;
        ptr = img + iofs;
        t = m[-1];
        if( t > 0 ) lab = t;
        t = m[1];
        if( t > 0 )
        {
            if( lab == 0 ) lab = t;
            else if( t != lab ) lab = WSHED;            //                       > 0    ，     
        }
        t = m[-mstep];
        if( t > 0 )
        {
            if( lab == 0 ) lab = t;
            else if( t != lab ) lab = WSHED;
        }
        t = m[mstep];
        if( t > 0 )
        {
            if( lab == 0 ) lab = t;
            else if( t != lab ) lab = WSHED;
        }
         //              ，                 
         //                ，  lab       ，   0
        assert( lab != 0 );  
        //  lab > 0 ，            ； lab = -1（WSHED）,         ，             
        m[0] = lab;                 
        if( lab == WSHED )
            continue;
        // lab > 0    ，        ，              ，           
        if( m[-1] == 0 )
        {
            c_diff( ptr, ptr - 3, t );                  //     t
            ws_push( t, mofs - 1, iofs - 3 );           //  m[-1]             ，  
            active_queue = ws_min( active_queue, t );   //   ， t <        active_queue ，         q[t]  ，          
            m[-1] = IN_QUEUE;
        }
        if( m[1] == 0 )
        {
            c_diff( ptr, ptr + 3, t );
            ws_push( t, mofs + 1, iofs + 3 );
            active_queue = ws_min( active_queue, t );
            m[1] = IN_QUEUE;
        }
        if( m[-mstep] == 0 )
        {
            c_diff( ptr, ptr - istep, t );
            ws_push( t, mofs - mstep, iofs - istep );
            active_queue = ws_min( active_queue, t );
            m[-mstep] = IN_QUEUE;
        }
        if( m[mstep] == 0 )
        {
            c_diff( ptr, ptr + istep, t );
            ws_push( t, mofs + mstep, iofs + istep );
            active_queue = ws_min( active_queue, t );
            m[mstep] = IN_QUEUE;
        }
    }
}


void cv::watershed( InputArray _src, InputOutputArray markers )
{
    Mat src = _src.getMat();
    CvMat c_src = _src.getMat(), c_markers = markers.getMat();
    cvWatershed( &c_src, &c_markers );
}