• MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会被淹没,如果从天空往下看

    最大稳定极值区域(MSER-Maximally Stable Extremal Regions)可以用于图像的斑点区域检测。该算法最早是由Matas等人于2002年提出,它是基于分水岭的概念。

    MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会被淹没,如果从天空往下看,则大地分为陆地和水域两个部分,这类似于二值图像。在得到的所有二值图像中,图像中的某些连通区域变化很小,甚至没有变化,则该区域就被称为最大稳定极值区域。这类似于当水面持续上升的时候,有些被水淹没的地方的面积没有变化。它的数学定义为:

    q(i)=|Qi+-Qi-|/|Qi|            (1)

    其中,Qi表示阈值为i时的某一连通区域,△为灰度阈值的微小变化量,q(i)为阈值是i时的区域Qi的变化率。当q(i)为局部极小值时,则Qi为最大稳定极值区域。

    需要说明的是,上述做法只能检测出灰度图像的黑色区域,不能检测出白色区域,因此还需要对原图进行反转,然后再进行阈值从0~255的二值化处理过程。这两种操作又分别称为MSER+和MSER-。

    MSER具有以下特点:

    1、对图像灰度具有仿射变换的不变性;

    2、稳定性:具有相同阈值范围内所支持的区域才会被选择;

    3、无需任何平滑处理就可以实现多尺度检测,即小的和大的结构都可以被检测到。

    MSER的原理比较简单,但要更快更好的实现它,是需要一定的算法、数据结构和编程技巧的。David Nister等人于2008年提出了Linear Time Maximally Stable Extremal Regions算法,该算法要比原著提出的算法快,opencv就是利用该算法实现MSER的。但这里要说明一点的是,opencv不是利用公式1计算MSER的,而是利用更易于实现的改进方法:

    q(i)=|Qi-Qi-|/|Qi-|            (2)

    David Nister提出的算法是基于改进的分水岭算法,即当往一个固定的地方注水的时候,只有当该地方的沟壑被水填满以后,水才会向其四周溢出,随着注水量的不断增加,各个沟壑也会逐渐被水淹没,但各个沟壑的水面不是同时上升的,它是根据水漫过地方的先后顺序,一个沟壑一个沟壑地填满水,只有当相邻两个沟壑被水连通在一起以后,水面对于这两个沟壑来说才是同时上升的。该算法的具体步骤如下:

    1、初始化栈和堆,栈用于存储组块(组块就是区域,就相当于水面,水漫过的地方就会出现水面,水面的高度就是图像的灰度值,因此用灰度值来表示组块的值),堆用于存储组块的边界像素,相当于水域的岸边,岸边要高于水面的,因此边界像素的灰度值一定不小于它所包围的区域(即组块)的灰度值。首先向栈内放入一个虚假的组块,当该组块被弹出时意味着程序的结束;

    2、把图像中的任意一个像素(一般选取图像的左上角像素)作为源像素,标注该像素为已访问过,并且把该像素的灰度值作为当前值。这一步相当于往源像素这一地点注水;

    3、向栈内放入一个空组块,该组块的值是当前值;

    4、按照顺序搜索当前值的4-领域内剩余的边缘,对于每一个邻域,检查它是否已经被访问过,如果没有,则标注它为已访问过并检索它的灰度值,如果灰度值不小于当前值,则把它放入用于存放边界像素的堆中。另一方面,如果领域灰度值小于当前值,则把当前值放入堆中,而把领域值作为当前值,并回到步骤3;

    5、累计栈顶组块的像素个数,即计算区域面积,这是通过循环累计得到的,这一步相当于水面的饱和;

    6、弹出堆中的边界像素。如果堆是空的,则程序结束;如果弹出的边界像素的灰度值等于当前值,则回到步骤4;

    7、从堆中得到的像素值会大于当前值,因此我们需要处理栈中所有的组块,直到栈中的组块的灰度值大于当前边界像素灰度值为止。然后回到步骤4。

    至于如何处理组块,则需要进入处理栈子模块中,传入该子模块的值为步骤7中从堆中提取得到的边界像素灰度值。子模块的具体步骤为:

    1)、处理栈顶的组块,即根据公式2计算最大稳定区域,判断其是否为极值区域;

    2)、如果边界像素灰度值小于距栈顶第二个组块的灰度值,那么设栈顶组块的灰度值为边界像素灰度值,并退出该子模块。之所以会出现这种情况,是因为在栈顶组块和第二个组块之间还有组块没有被检测处理,因此我们需要改变栈顶组块的灰度值为边界像素灰度值(相当于这两层的组块进行了合并),并回到主程序,再次搜索组块;

    3)、弹出栈顶组块,并与目前栈顶组块合并;

    4)、如果边界像素灰度值大于栈顶组块的灰度值,则回到步骤1。

    在opencv2.4.9中,MSER算法是用类的方法给出的:

    class MserFeatureDetector : public FeatureDetector
    {
    public:
    MserFeatureDetector( CvMSERParams params=cvMSERParams() );
    MserFeatureDetector( int delta, int minArea, int maxArea,
    double maxVariation, double minDiversity,
    int maxEvolution, double areaThreshold,
    double minMargin, int edgeBlurSize );
    virtual void read( const FileNode& fn );
    virtual void write( FileStorage& fs ) const;
    protected:
    ...
    };
    
    而具体的MSER类为:

    class MSER : public CvMSERParams
    {
    public:
    // default constructor
    //缺省的构造函数
    MSER();
    // constructor that initializes all the algorithm parameters
    //带有所有算法参数的构造函数
    MSER( int _delta, int _min_area, int _max_area,
    float _max_variation, float _min_diversity,
    int _max_evolution, double _area_threshold,
    double _min_margin, int _edge_blur_size );
    // runs the extractor on the specified image; returns the MSERs,
    // each encoded as a contour (vector<Point>, see findContours)
    // the optional mask marks the area where MSERs are searched for
    void operator()( const Mat& image, vector<vector<Point> >& msers, const Mat& mask ) const;
    };
    
    MSER算法所需要的参数较多:
    delta为灰度值的变化量,即公式1和2中的△;
    _min_area和_max_area为检测到的组块面积的范围;
    _max_variation为最大的变化率,即如果公式1和2中的q(i)小于该值,则被认为是最大稳定极值区域;
    _min_diversity为稳定区域的最小变换量。
    其他的参数用于对彩色图像的MSER检测,这里不做介绍。
    MSER类通过重载( )运算符,得到了最大稳定极值区域的点集msers,其中image为输入图像,mask为掩码矩阵。
    下面我们就对MSER类的源码进行分析:
    
    void MSER::operator()( const Mat& image, vector<vector<Point> >& dstcontours, const Mat& mask ) const
    {
        CvMat _image = image, _mask, *pmask = 0;
        if( mask.data )
            pmask = &(_mask = mask);
        MemStorage storage(cvCreateMemStorage(0));
        Seq<CvSeq*> contours;
        //调用extractMSER函数,得到MSER的区域点集序列contours.seq
        //MSERParams为MSER所需要的参数
        extractMSER( &_image, pmask, &contours.seq, storage,
                     MSERParams(delta, minArea, maxArea, maxVariation, minDiversity,
                                maxEvolution, areaThreshold, minMargin, edgeBlurSize));
        SeqIterator<CvSeq*> it = contours.begin();
        size_t i, ncontours = contours.size();
        dstcontours.resize(ncontours);
        //复制点集序列
        for( i = 0; i < ncontours; i++, ++it )
            Seq<Point>(*it).copyTo(dstcontours[i]);
    }
    
    extractMSER函数首先定义了一些变量,并进行参数的判断。然后根据输入图像的类型分别调用不同的函数:

    static void
    extractMSER( CvArr* _img,
               CvArr* _mask,
               CvSeq** _contours,
               CvMemStorage* storage,
               MSERParams params )
    {
        CvMat srchdr, *src = cvGetMat( _img, &srchdr );
        CvMat maskhdr, *mask = _mask ? cvGetMat( _mask, &maskhdr ) : 0;
        CvSeq* contours = 0;
    
        CV_Assert(src != 0);
        CV_Assert(CV_MAT_TYPE(src->type) == CV_8UC1 || CV_MAT_TYPE(src->type) == CV_8UC3);
        CV_Assert(mask == 0 || (CV_ARE_SIZES_EQ(src, mask) && CV_MAT_TYPE(mask->type) == CV_8UC1));
        CV_Assert(storage != 0);
    
        contours = *_contours = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), storage );
    
        // choose different method for different image type
        // for grey image, it is: Linear Time Maximally Stable Extremal Regions
        // for color image, it is: Maximally Stable Colour Regions for Recognition and Matching
        switch ( CV_MAT_TYPE(src->type) )
        {
            case CV_8UC1:    //处理灰度图像
                extractMSER_8UC1( src, mask, contours, storage, params );
                break;
            case CV_8UC3:    //处理彩色图像
                extractMSER_8UC3( src, mask, contours, storage, params );
                break;
        }
    }
    
    灰度图像的MSER处理方法就是应用本文介绍的方法:

    static void extractMSER_8UC1( CvMat* src,
                 CvMat* mask,
                 CvSeq* contours,
                 CvMemStorage* storage,
                 MSERParams params )
    {
        //为了加快运算速度,把原图的宽扩展成高度复合数,即2^N的形式
        //step为扩展后的宽,初始值为8
        int step = 8;
        //stepgap为N,初始值为3,即8=2^3
        int stepgap = 3;
        //通过step向左移位的方式扩展原图的宽
        while ( step < src->step+2 )
        {
            step <<= 1;
            stepgap++;
        }
        int stepmask = step-1;
    
        // to speedup the process, make the width to be 2^N
        //创建扩展后的图像矩阵,宽为2^N,高为原图高+2
        CvMat* img = cvCreateMat( src->rows+2, step, CV_32SC1 );
        //定义第二行地址
        int* ioptr = img->data.i+step+1;
        int* imgptr;
    
        // pre-allocate boundary heap
        //步骤1,初始化堆和栈
        //定义堆,用于存储组块的边界像素
        int** heap = (int**)cvAlloc( (src->rows*src->cols+256)*sizeof(heap[0]) );
        int** heap_start[256];
        //heap_start为三指针变量,heap_start为边界像素的灰度值,因此它数量为256个;*heap_start表示边界像素中该灰度值的数量;**heap_start表示边界像素中该灰度值中第*heap_start个所对应的像素地址指针。
        heap_start[0] = heap;
    
        // pre-allocate linked point and grow history
        //pts表示组块内像素链表,即像素间相互链接
        LinkedPoint* pts = (LinkedPoint*)cvAlloc( src->rows*src->cols*sizeof(pts[0]) );
        //history表示每个组块生长的状况,即随着阈值的增加,组块的大小是在不断扩大的
        MSERGrowHistory* history = (MSERGrowHistory*)cvAlloc( src->rows*src->cols*sizeof(history[0]) );
        //comp表示图像内连通的组块(即区域),原则上每一个灰度值就会有一个组块,但之所以组块的个数是257个,是因为有一个组块是虚假组块,用于表示程序的结束。用栈的形式来管理各个组块
        MSERConnectedComp comp[257];
    
        // darker to brighter (MSER-)
        //MSER-
        //先对原图进行预处理
        imgptr = preprocessMSER_8UC1( img, heap_start, src, mask );
        //执行MSER操作
        extractMSER_8UC1_Pass( ioptr, imgptr, heap_start, pts, history, comp, step, stepmask, stepgap, params, -1, contours, storage );
        // brighter to darker (MSER+)
        //MSER+
        imgptr = preprocessMSER_8UC1( img, heap_start, src, mask );
        extractMSER_8UC1_Pass( ioptr, imgptr, heap_start, pts, history, comp, step, stepmask, stepgap, params, 1, contours, storage );
    
        // clean up
        //清理内存
        cvFree( &history );
        cvFree( &heap );
        cvFree( &pts );
        cvReleaseMat( &img );
    }
    

    preprocessMSER_8UC1函数为预处理的过程,主要就是对宽度扩展以后的图像矩阵进行赋值,每一位都赋予不同的含义:

    // to preprocess src image to followingformat

    // 32-bit image

    // > 0 is available, < 0 is visited

    // 17~19 bits is the direction

    // 8~11 bits is the bucket it falls to (forBitScanForward)

    // 0~8 bits is the color

    /*定义图像矩阵的数据格式为有符号32位整型,最高一位表示是否被访问过,0表示没有被访问过,1表示被访问过(因为是有符号数,所以最高一位是1也就是负数);16~18位(这里源码注解有误)表示4邻域的方向;0~7位表示该像素的灰度值*/

    //img代表图像矩阵,MSER处理的是该矩阵

    //src为输入原图

    //heap_cur为边界像素堆

    //mask为掩码

    static int* preprocessMSER_8UC1( CvMat* img,
                int*** heap_cur,
                CvMat* src,
                CvMat* mask )
    {
        int srccpt = src->step-src->cols;
        //由于图像矩阵的宽经过了2^N处理,所以它的宽比原图的宽要长,cpt_1代表两个宽度的差值
        int cpt_1 = img->cols-src->cols-1;
        //图像矩阵的地址指针
        int* imgptr = img->data.i;
        //定义真实的图像起始地址
        int* startptr;
    
        //定义并初始化灰度值数组
        int level_size[256];
        for ( int i = 0; i < 256; i++ )
            level_size[i] = 0;
        //为图像矩阵的第一行赋值
        for ( int i = 0; i < src->cols+2; i++ )
        {
            *imgptr = -1;
            imgptr++;
        }
        //地址指针指向图像矩阵的第二行
        imgptr += cpt_1-1;
        //原图首地址指针
        uchar* srcptr = src->data.ptr;
        if ( mask )    //如果定义了掩码矩阵
        {
            startptr = 0;
            //掩码矩阵首地址指针
            uchar* maskptr = mask->data.ptr;
            //遍历整个原图
            for ( int i = 0; i < src->rows; i++ )
            {
                *imgptr = -1;
                imgptr++;
                for ( int j = 0; j < src->cols; j++ )
                {
                    if ( *maskptr )
                    {
                        if ( !startptr )
                            startptr = imgptr;    //赋值
                        *srcptr = 0xff-*srcptr;    //反转图像的灰度值
                        level_size[*srcptr]++;    //为灰度值计数
                        //为图像矩阵赋值,它的低8位是原图灰度值,8~10位是灰度值的高3位
                        *imgptr = ((*srcptr>>5)<<8)|(*srcptr);
                    } else {    //掩码覆盖的像素值为-1
                        *imgptr = -1;
                    }
                    //地址加1
                    imgptr++;
                    srcptr++;
                    maskptr++;
                }
                //跳过图像矩阵比原图多出的部分
                *imgptr = -1;
                imgptr += cpt_1;
                srcptr += srccpt;
                maskptr += srccpt;
            }
        } else {    //没有定义掩码
            startptr = imgptr+img->cols+1;    //赋值
            //遍历整幅图像,为图像矩阵赋值
            for ( int i = 0; i < src->rows; i++ )
            {
                *imgptr = -1;
                imgptr++;
                for ( int j = 0; j < src->cols; j++ )
                {
                    *srcptr = 0xff-*srcptr;
                    level_size[*srcptr]++;
                    *imgptr = ((*srcptr>>5)<<8)|(*srcptr);
                    imgptr++;
                    srcptr++;
                }
                *imgptr = -1;
                imgptr += cpt_1;
                srcptr += srccpt;
            }
        }
        //为图像矩阵的最后一行赋值
        for ( int i = 0; i < src->cols+2; i++ )
        {
            *imgptr = -1;
            imgptr++;
        }
        //定义边界像素堆的大小
        //heap_cur[]对应灰度值,heap_cur[][]对应该灰度值的个数
        //根据灰度值的个数定义heap_cur的长度
        heap_cur[0][0] = 0;
        for ( int i = 1; i < 256; i++ )
        {
            heap_cur[i] = heap_cur[i-1]+level_size[i-1]+1;
            heap_cur[i][0] = 0;
        }
        //返回在图像矩阵中第一个真正的像素点的地址
        return startptr;
    }
    
    extractMSER_8UC1_Pass函数执行MSER算法,MSER-和MSER+都执行该函数,但可以通过参数color来区分。

    static void extractMSER_8UC1_Pass( int* ioptr,
                  int* imgptr,
                  int*** heap_cur,
                  LinkedPoint* ptsptr,
                  MSERGrowHistory* histptr,
                  MSERConnectedComp* comptr,
                  int step,
                  int stepmask,
                  int stepgap,
                  MSERParams params,
                  int color,
                  CvSeq* contours,
                  CvMemStorage* storage )
    {
        //设置第一个组块的灰度值为256,该灰度值是真实图像中不存在的灰度值,以区分真实图像的组块,从而判断程序是否结束
        comptr->grey_level = 256;
        //步骤2和步骤3
        //指向第二个组块
        comptr++;
        //设置第二个组块为输入图像第一个像素(左上角)的灰度值
        comptr->grey_level = (*imgptr)&0xff;
        //初始化该组块
        initMSERComp( comptr );
        //在最高位标注该像素为已被访问过,即该值小于0
        *imgptr |= 0x80000000;
        //得到该像素所对应的堆,即指向它所对应的灰度值
        heap_cur += (*imgptr)&0xff;
        //定义方向,即偏移量,因为是4邻域,所以该数组分别对应右、下、左、上
        int dir[] = { 1, step, -1, -step };
    #ifdef __INTRIN_ENABLED__
        unsigned long heapbit[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
        unsigned long* bit_cur = heapbit+(((*imgptr)&0x700)>>8);
    #endif
        //死循环,退出该死循环的条件有两个:一是到达组块的栈底;二是边界像素堆中没有任何值。达到栈底也就意味着堆中没有值,在此函数中两者是一致的。
        for ( ; ; )
        {
            // take tour of all the 4 directions
            //步骤4
            //在4邻域内进行搜索
            while ( ((*imgptr)&0x70000) < 0x40000 )
            {
                // get the neighbor
                /* ((*imgptr)&0x70000)>>16得到第16位至第18位数据,该数据对应的4邻域的方向,再通过dir数组得到4邻域的偏移量,因此imgptr_nbr为当前像素4邻域中某一个方向上邻域的地址指针 */
                int* imgptr_nbr = imgptr+dir[((*imgptr)&0x70000)>>16];
                //检查邻域像素是否被访问过,如果被访问过,则会在第一位置1,因此该值会小于0,否则第一位为0,该值大于0
                if ( *imgptr_nbr >= 0 ) // if the neighbor is not visited yet
                {
                    //标注该像素已被访问过,即把第一位置1
                    *imgptr_nbr |= 0x80000000; // mark it as visited
                    //比较当前像素与邻域像素灰度值
                    if ( ((*imgptr_nbr)&0xff) < ((*imgptr)&0xff) )
                    {
                        //如果邻域值小于当前值,把当前值放入堆中
                        // when the value of neighbor smaller than current
                        // push current to boundary heap and make the neighbor to be the current one
                        // create an empty comp
                        //堆中该像素灰度值的数量加1,即对该灰度值像素个数计数
                        (*heap_cur)++;
                        //把当前值的地址放入堆中
                        **heap_cur = imgptr;
                        //重新标注当前值的方向位,以备下一次访问该值时搜索下一个邻域
                        *imgptr += 0x10000;
                        //定位邻域值所对应的堆的位置
                        //当前heap_cur所指向的灰度值为while循环搜索中的最小灰度值,即水溢过的最低点
                        heap_cur += ((*imgptr_nbr)&0xff)-((*imgptr)&0xff);
    #ifdef __INTRIN_ENABLED__
                        _bitset( bit_cur, (*imgptr)&0x1f );
                        bit_cur += (((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8;
    #endif
                        imgptr = imgptr_nbr;    //邻域值换为当前值
                        //步骤3
                        comptr++;    //创建一个组块
                        initMSERComp( comptr );    //初始化该组块
                        comptr->grey_level = (*imgptr)&0xff;    //为该组块的灰度值赋值
                        //当某个邻域值小于当前值,则不对当前值再做任何操作,继续下次循环,在下次循环中,处理的则是该邻域值,即再次执行步骤4
                        continue;
                    } else {
                        //如果邻域值大于当前值,把邻域值放入堆中
                        // otherwise, push the neighbor to boundary heap
                        //找到该邻域值在堆中的灰度值位置,并对其计数,即对该灰度值像素个数计数 
                        heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)]++;
                        //把该邻域像素地址放入堆中
                        *heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)] = imgptr_nbr;
    #ifdef __INTRIN_ENABLED__
                        _bitset( bit_cur+((((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8), (*imgptr_nbr)&0x1f );
    #endif
                    }
                }
                *imgptr += 0x10000;    //重新标注当前值的领域方向
            }
            //imsk表示结束while循环后所得到的最后像素地址与图像首地址的相对距离
            int imsk = (int)(imgptr-ioptr);
            //得到结束while循环后的最后像素的坐标位置
            //从这里可以看出图像的宽采样2^N的好处,即imsk>>stepgap
            ptsptr->pt = cvPoint( imsk&stepmask, imsk>>stepgap );
            // get the current location
            //步骤5
            //对栈顶的组块的像素个数累加,即计算组块的面积大小,并链接组块内的像素点
            //结束while循环后,栈顶组块的灰度值就是该次循环后得到的最小灰度值,也就是该组块为极低点,就相当于水已经流到了最低的位置
            accumulateMSERComp( comptr, ptsptr );
            //指向下一个像素点链表位置
            ptsptr++;
            // get the next pixel from boundary heap
            //步骤6
            /*结束while循环后,如果**heap_cur有值的话,heap_cur指向的应该是while循环中得到的灰度值最小值,也就是在组块的边界像素中,有与组块相同的灰度值,因此要把该值作为当前值继续while循环,也就是相当于组块面积的扩展*/
            if ( **heap_cur )    //有值
            {
                imgptr = **heap_cur;    //把该像素点作为当前值
                (*heap_cur)--;    //像素的个数要相应的减1
    #ifdef __INTRIN_ENABLED__
                if ( !**heap_cur )
                    _bitreset( bit_cur, (*imgptr)&0x1f );
    #endif
            //步骤7
            //已经找到了最小灰度值的组块,并且边界像素堆中的灰度值都比组块的灰度值大,则这时需要组块,即计算最大稳定极值区域
            } else {
    #ifdef __INTRIN_ENABLED__
                bool found_pixel = 0;
                unsigned long pixel_val;
                for ( int i = ((*imgptr)&0x700)>>8; i < 8; i++ )
                {
                    if ( _BitScanForward( &pixel_val, *bit_cur ) )
                    {
                        found_pixel = 1;
                        pixel_val += i<<5;
                        heap_cur += pixel_val-((*imgptr)&0xff);
                        break;
                    }
                    bit_cur++;
                }
                if ( found_pixel )
    #else
                heap_cur++;    //指向高一级的灰度值
                unsigned long pixel_val = 0;
                //在边界像素堆中,找到边界像素中的最小灰度值
                for ( unsigned long i = ((*imgptr)&0xff)+1; i < 256; i++ )
                {
                    if ( **heap_cur )
                    {
                        pixel_val = i;    //灰度值
                        break;
                    }
                    //定位在堆中所对应的灰度值,与pixel_val是相等的
                    heap_cur++; 
                }
                if ( pixel_val )    //如果找到了像素值
    #endif
                {
                    imgptr = **heap_cur;    //从堆中提取出该像素
                    (*heap_cur)--;    //对应的像素个数减1
    #ifdef __INTRIN_ENABLED__
                    if ( !**heap_cur )
                        _bitreset( bit_cur, pixel_val&0x1f );
    #endif
                    //进入处理栈子模块
                    if ( pixel_val < comptr[-1].grey_level )
                    //如果从堆中提取出的最小灰度值小于距栈顶第二个组块的灰度值,则说明栈顶组块和第二个组块之间仍然有没有处理过的组块,因此在计算完MSER值后还要继续返回步骤4搜索该组块
                    {
                        // check the stablity and push a new history, increase the grey level
                        //利用公式2计算栈顶组块的q(i)值
                        if ( MSERStableCheck( comptr, params ) )    //是MSER
                        {
                            //得到组块内的像素点
                            CvContour* contour = MSERToContour( comptr, storage );
                            contour->color = color;    //标注是MSER-还是MSER+
                            //把组块像素点放入序列中
                            cvSeqPush( contours, &contour ); 
                        }
                        MSERNewHistory( comptr, histptr );
                        //改变栈顶组块的灰度值,这样就可以和上一层的组块进行合并
                        comptr[0].grey_level = pixel_val;
                        histptr++;
                    } else {
                        //从堆中提取出的最小灰度值大于等于距栈顶第二个组块的灰度值
                        // keep merging top two comp in stack until the grey level >= pixel_val
                        //死循环,用于处理灰度值相同并且相连的组块之间的合并
                        for ( ; ; )
                        {
                            //指向距栈顶第二个组块
                            comptr--;
                            //合并前两个组块,并把合并后的组块作为栈顶组块
                            MSERMergeComp( comptr+1, comptr, comptr, histptr );
                            histptr++;
                            /*如果pixel_val = comptr[0].grey_level,说明在边界上还有属于该组块的像素;如果pixel_val < comptr[0].grey_level,说明还有比栈顶组块灰度值更小的组块没有搜索到。这两种情况都需要回到步骤4中继续搜索组块*/
                            if ( pixel_val <= comptr[0].grey_level )
                                break;
                            //合并栈内前两个组块,直到pixel_val < comptr[-1].grey_level为止
                            if ( pixel_val < comptr[-1].grey_level )
                            {
                                // check the stablity here otherwise it wouldn't be an ER
                                if ( MSERStableCheck( comptr, params ) )
                                {
                                    CvContour* contour = MSERToContour( comptr, storage );
                                    contour->color = color;
                                    cvSeqPush( contours, &contour );
                                }
                                MSERNewHistory( comptr, histptr );
                                comptr[0].grey_level = pixel_val;
                                histptr++;
                                break;
                            }
                        }
                    }
                } else
                    //边界像素堆中没有任何像素,则退出死循环,该函数返回。
                    break;
            }
        }
    }
    

    MSER就分析到这里,至于其中用到的一些子函数就不再分析。这里还要说明一点的是,MSER+和MSER-使用的都是同一个函数,两者的区别是一个组块面积增加,另一个减少。说实话,该部分的内容数据结构较为复杂,有一些内容我理解得也不透彻,比如结构MSERGrowHistory真正的含义还比较模糊。

    下面就给出最大稳定极值区域检测的应用实例:

    #include "opencv2/core/core.hpp"
    #include "opencv2/highgui/highgui.hpp"
    #include "opencv2/imgproc/imgproc.hpp"
    #include <opencv2/features2d/features2d.hpp>
    #include <iostream>
    using namespace cv;
    using namespace std;
    
    int main(int argc, char *argv[])
    {
        Mat src,gray;
    	src = imread("lenna.bmp");
    	cvtColor( src, gray, CV_BGR2GRAY );
        //创建MSER类
        MSER ms;
        //用于组块区域的像素点集
        vector<vector<Point>> regions;
        ms(gray, regions, Mat());
        //在灰度图像中用椭圆形绘制组块
        for (int i = 0; i < regions.size(); i++)
        {
            ellipse(gray, fitEllipse(regions[i]), Scalar(255));
        }
        imshow("mser", gray);
        waitKey(0);
        return 0;
    }
    
    结果如下图所示。本文介绍的方法只适用于灰度图像,所以如果输入的是彩色图像,要把它转换为灰度图像。另外在创建MSER类的时候,我们使用的是缺省构造函数,因此MSER算法所需的参数是系统默认的。所以我们检测的结果与David Nister等人在原著中的检测结果略有不同。











    展开全文
  • 原文: ... 最大稳定极值区域(MSER-Maximally Stable Extremal Regions)可以用于图像的斑点区域检测。该算法最早是由Matas等人于...MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0...

    原文:

    http://blog.csdn.net/zhaocj/article/details/40742191

    最大稳定极值区域(MSER-Maximally Stable Extremal Regions)可以用于图像的斑点区域检测。该算法最早是由Matas等人于2002年提出,它是基于分水岭的概念。

    MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会被淹没,如果从天空往下看,则大地分为陆地和水域两个部分,这类似于二值图像。在得到的所有二值图像中,图像中的某些连通区域变化很小,甚至没有变化,则该区域就被称为最大稳定极值区域。这类似于当水面持续上升的时候,有些被水淹没的地方的面积没有变化。它的数学定义为:

    q(i)=|Qi+△-Qi-△|/|Qi|            (1)

    其中,Qi表示阈值为i时的某一连通区域,△为灰度阈值的微小变化量,q(i)为阈值是i时的区域Qi的变化率。当q(i)为局部极小值时,则Qi为最大稳定极值区域。

    需要说明的是,上述做法只能检测出灰度图像的黑色区域,不能检测出白色区域,因此还需要对原图进行反转,然后再进行阈值从0~255的二值化处理过程。这两种操作又分别称为MSER+和MSER-。

    MSER具有以下特点:

    1、对图像灰度具有仿射变换的不变性;

    2、稳定性:具有相同阈值范围内所支持的区域才会被选择;

    3、无需任何平滑处理就可以实现多尺度检测,即小的和大的结构都可以被检测到。

    MSER的原理比较简单,但要更快更好的实现它,是需要一定的算法、数据结构和编程技巧的。David Nister等人于2008年提出了Linear Time Maximally Stable Extremal Regions算法,该算法要比原著提出的算法快,opencv就是利用该算法实现MSER的。但这里要说明一点的是,opencv不是利用公式1计算MSER的,而是利用更易于实现的改进方法:

    q(i)=|Qi-Qi-△|/|Qi-△|            (2)

    David Nister提出的算法是基于改进的分水岭算法,即当往一个固定的地方注水的时候,只有当该地方的沟壑被水填满以后,水才会向其四周溢出,随着注水量的不断增加,各个沟壑也会逐渐被水淹没,但各个沟壑的水面不是同时上升的,它是根据水漫过地方的先后顺序,一个沟壑一个沟壑地填满水,只有当相邻两个沟壑被水连通在一起以后,水面对于这两个沟壑来说才是同时上升的。该算法的具体步骤如下:

    1、初始化栈和堆,栈用于存储组块(组块就是区域,就相当于水面,水漫过的地方就会出现水面,水面的高度就是图像的灰度值,因此用灰度值来表示组块的值),堆用于存储组块的边界像素,相当于水域的岸边,岸边要高于水面的,因此边界像素的灰度值一定不小于它所包围的区域(即组块)的灰度值。首先向栈内放入一个虚假的组块,当该组块被弹出时意味着程序的结束;

    2、把图像中的任意一个像素(一般选取图像的左上角像素)作为源像素,标注该像素为已访问过,并且把该像素的灰度值作为当前值。这一步相当于往源像素这一地点注水;

    3、向栈内放入一个空组块,该组块的值是当前值;

    4、按照顺序搜索当前值的4-领域内剩余的边缘,对于每一个邻域,检查它是否已经被访问过,如果没有,则标注它为已访问过并检索它的灰度值,如果灰度值不小于当前值,则把它放入用于存放边界像素的堆中。另一方面,如果领域灰度值小于当前值,则把当前值放入堆中,而把领域值作为当前值,并回到步骤3;

    5、累计栈顶组块的像素个数,即计算区域面积,这是通过循环累计得到的,这一步相当于水面的饱和;

    6、弹出堆中的边界像素。如果堆是空的,则程序结束;如果弹出的边界像素的灰度值等于当前值,则回到步骤4;

    7、从堆中得到的像素值会大于当前值,因此我们需要处理栈中所有的组块,直到栈中的组块的灰度值大于当前边界像素灰度值为止。然后回到步骤4。

    至于如何处理组块,则需要进入处理栈子模块中,传入该子模块的值为步骤7中从堆中提取得到的边界像素灰度值。子模块的具体步骤为:

    1)、处理栈顶的组块,即根据公式2计算最大稳定区域,判断其是否为极值区域;

    2)、如果边界像素灰度值小于距栈顶第二个组块的灰度值,那么设栈顶组块的灰度值为边界像素灰度值,并退出该子模块。之所以会出现这种情况,是因为在栈顶组块和第二个组块之间还有组块没有被检测处理,因此我们需要改变栈顶组块的灰度值为边界像素灰度值(相当于这两层的组块进行了合并),并回到主程序,再次搜索组块;

    3)、弹出栈顶组块,并与目前栈顶组块合并;

    4)、如果边界像素灰度值大于栈顶组块的灰度值,则回到步骤1。

    在opencv2.4.9中,MSER算法是用类的方法给出的:

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. class MserFeatureDetector : public FeatureDetector  
    2. {  
    3. public:  
    4. MserFeatureDetector( CvMSERParams params=cvMSERParams() );  
    5. MserFeatureDetector( int delta, int minArea, int maxArea,  
    6. double maxVariation, double minDiversity,  
    7. int maxEvolution, double areaThreshold,  
    8. double minMargin, int edgeBlurSize );  
    9. virtual void read( const FileNode& fn );  
    10. virtual void write( FileStorage& fs ) const;  
    11. protected:  
    12. ...  
    13. };  

    class MserFeatureDetector : public FeatureDetector
    {
    public:
    MserFeatureDetector( CvMSERParams params=cvMSERParams() );
    MserFeatureDetector( int delta, int minArea, int maxArea,
    double maxVariation, double minDiversity,
    int maxEvolution, double areaThreshold,
    double minMargin, int edgeBlurSize );
    virtual void read( const FileNode& fn );
    virtual void write( FileStorage& fs ) const;
    protected:
    ...
    };
    

    而具体的MSER类为:

     

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. class MSER : public CvMSERParams  
    2. {  
    3. public:  
    4. // default constructor  
    5. //缺省的构造函数  
    6. MSER();  
    7. // constructor that initializes all the algorithm parameters  
    8. //带有所有算法参数的构造函数  
    9. MSER( int _delta, int _min_area, int _max_area,  
    10. float _max_variation, float _min_diversity,  
    11. int _max_evolution, double _area_threshold,  
    12. double _min_margin, int _edge_blur_size );  
    13. // runs the extractor on the specified image; returns the MSERs,  
    14. // each encoded as a contour (vector<Point>, see findContours)  
    15. // the optional mask marks the area where MSERs are searched for  
    16. void operator()( const Mat& image, vector<vector<Point> >& msers, const Mat& mask ) const;  
    17. };  

    class MSER : public CvMSERParams
    {
    public:
    // default constructor
    //缺省的构造函数
    MSER();
    // constructor that initializes all the algorithm parameters
    //带有所有算法参数的构造函数
    MSER( int _delta, int _min_area, int _max_area,
    float _max_variation, float _min_diversity,
    int _max_evolution, double _area_threshold,
    double _min_margin, int _edge_blur_size );
    // runs the extractor on the specified image; returns the MSERs,
    // each encoded as a contour (vector<Point>, see findContours)
    // the optional mask marks the area where MSERs are searched for
    void operator()( const Mat& image, vector<vector<Point> >& msers, const Mat& mask ) const;
    };
    

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. MSER算法所需要的参数较多:  
    2. delta为灰度值的变化量,即公式1和2中的△;  
    3. _min_area和_max_area为检测到的组块面积的范围;  
    4. _max_variation为最大的变化率,即如果公式1和2中的q(i)小于该值,则被认为是最大稳定极值区域;  
    5. _min_diversity为稳定区域的最小变换量。  
    6. 其他的参数用于对彩色图像的MSER检测,这里不做介绍。  
    7. MSER类通过重载( )运算符,得到了最大稳定极值区域的点集msers,其中image为输入图像,mask为掩码矩阵。  
    8. 下面我们就对MSER类的源码进行分析:  

    MSER算法所需要的参数较多:
    delta为灰度值的变化量,即公式1和2中的△;
    _min_area和_max_area为检测到的组块面积的范围;
    _max_variation为最大的变化率,即如果公式1和2中的q(i)小于该值,则被认为是最大稳定极值区域;
    _min_diversity为稳定区域的最小变换量。
    其他的参数用于对彩色图像的MSER检测,这里不做介绍。
    MSER类通过重载( )运算符,得到了最大稳定极值区域的点集msers,其中image为输入图像,mask为掩码矩阵。
    下面我们就对MSER类的源码进行分析:
    

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. void MSER::operator()( const Mat& image, vector<vector<Point> >& dstcontours, const Mat& mask ) const  
    2. {  
    3.     CvMat _image = image, _mask, *pmask = 0;  
    4.     if( mask.data )  
    5.         pmask = &(_mask = mask);  
    6.     MemStorage storage(cvCreateMemStorage(0));  
    7.     Seq<CvSeq*> contours;  
    8.     //调用extractMSER函数,得到MSER的区域点集序列contours.seq  
    9.     //MSERParams为MSER所需要的参数  
    10.     extractMSER( &_image, pmask, &contours.seq, storage,  
    11.                  MSERParams(delta, minArea, maxArea, maxVariation, minDiversity,  
    12.                             maxEvolution, areaThreshold, minMargin, edgeBlurSize));  
    13.     SeqIterator<CvSeq*> it = contours.begin();  
    14.     size_t i, ncontours = contours.size();  
    15.     dstcontours.resize(ncontours);  
    16.     //复制点集序列  
    17.     for( i = 0; i < ncontours; i++, ++it )  
    18.         Seq<Point>(*it).copyTo(dstcontours[i]);  
    19. }  

    void MSER::operator()( const Mat& image, vector<vector<Point> >& dstcontours, const Mat& mask ) const
    {
        CvMat _image = image, _mask, *pmask = 0;
        if( mask.data )
            pmask = &(_mask = mask);
        MemStorage storage(cvCreateMemStorage(0));
        Seq<CvSeq*> contours;
        //调用extractMSER函数,得到MSER的区域点集序列contours.seq
        //MSERParams为MSER所需要的参数
        extractMSER( &_image, pmask, &contours.seq, storage,
                     MSERParams(delta, minArea, maxArea, maxVariation, minDiversity,
                                maxEvolution, areaThreshold, minMargin, edgeBlurSize));
        SeqIterator<CvSeq*> it = contours.begin();
        size_t i, ncontours = contours.size();
        dstcontours.resize(ncontours);
        //复制点集序列
        for( i = 0; i < ncontours; i++, ++it )
            Seq<Point>(*it).copyTo(dstcontours[i]);
    }
    

    extractMSER函数首先定义了一些变量,并进行参数的判断。然后根据输入图像的类型分别调用不同的函数:

     

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. static void  
    2. extractMSER( CvArr* _img,  
    3.            CvArr* _mask,  
    4.            CvSeq** _contours,  
    5.            CvMemStorage* storage,  
    6.            MSERParams params )  
    7. {  
    8.     CvMat srchdr, *src = cvGetMat( _img, &srchdr );  
    9.     CvMat maskhdr, *mask = _mask ? cvGetMat( _mask, &maskhdr ) : 0;  
    10.     CvSeq* contours = 0;  
    11.   
    12.     CV_Assert(src != 0);  
    13.     CV_Assert(CV_MAT_TYPE(src->type) == CV_8UC1 || CV_MAT_TYPE(src->type) == CV_8UC3);  
    14.     CV_Assert(mask == 0 || (CV_ARE_SIZES_EQ(src, mask) && CV_MAT_TYPE(mask->type) == CV_8UC1));  
    15.     CV_Assert(storage != 0);  
    16.   
    17.     contours = *_contours = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), storage );  
    18.   
    19.     // choose different method for different image type  
    20.     // for grey image, it is: Linear Time Maximally Stable Extremal Regions  
    21.     // for color image, it is: Maximally Stable Colour Regions for Recognition and Matching  
    22.     switch ( CV_MAT_TYPE(src->type) )  
    23.     {  
    24.         case CV_8UC1:    //处理灰度图像  
    25.             extractMSER_8UC1( src, mask, contours, storage, params );  
    26.             break;  
    27.         case CV_8UC3:    //处理彩色图像  
    28.             extractMSER_8UC3( src, mask, contours, storage, params );  
    29.             break;  
    30.     }  
    31. }  

    static void
    extractMSER( CvArr* _img,
               CvArr* _mask,
               CvSeq** _contours,
               CvMemStorage* storage,
               MSERParams params )
    {
        CvMat srchdr, *src = cvGetMat( _img, &srchdr );
        CvMat maskhdr, *mask = _mask ? cvGetMat( _mask, &maskhdr ) : 0;
        CvSeq* contours = 0;
    
        CV_Assert(src != 0);
        CV_Assert(CV_MAT_TYPE(src->type) == CV_8UC1 || CV_MAT_TYPE(src->type) == CV_8UC3);
        CV_Assert(mask == 0 || (CV_ARE_SIZES_EQ(src, mask) && CV_MAT_TYPE(mask->type) == CV_8UC1));
        CV_Assert(storage != 0);
    
        contours = *_contours = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSeq*), storage );
    
        // choose different method for different image type
        // for grey image, it is: Linear Time Maximally Stable Extremal Regions
        // for color image, it is: Maximally Stable Colour Regions for Recognition and Matching
        switch ( CV_MAT_TYPE(src->type) )
        {
            case CV_8UC1:    //处理灰度图像
                extractMSER_8UC1( src, mask, contours, storage, params );
                break;
            case CV_8UC3:    //处理彩色图像
                extractMSER_8UC3( src, mask, contours, storage, params );
                break;
        }
    }
    

    灰度图像的MSER处理方法就是应用本文介绍的方法:

     

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. static void extractMSER_8UC1( CvMat* src,  
    2.              CvMat* mask,  
    3.              CvSeq* contours,  
    4.              CvMemStorage* storage,  
    5.              MSERParams params )  
    6. {  
    7.     //为了加快运算速度,把原图的宽扩展成高度复合数,即2^N的形式  
    8.     //step为扩展后的宽,初始值为8  
    9.     int step = 8;  
    10.     //stepgap为N,初始值为3,即8=2^3  
    11.     int stepgap = 3;  
    12.     //通过step向左移位的方式扩展原图的宽  
    13.     while ( step < src->step+2 )  
    14.     {  
    15.         step <<= 1;  
    16.         stepgap++;  
    17.     }  
    18.     int stepmask = step-1;  
    19.   
    20.     // to speedup the process, make the width to be 2^N  
    21.     //创建扩展后的图像矩阵,宽为2^N,高为原图高+2  
    22.     CvMat* img = cvCreateMat( src->rows+2, step, CV_32SC1 );  
    23.     //定义第二行地址  
    24.     int* ioptr = img->data.i+step+1;  
    25.     int* imgptr;  
    26.   
    27.     // pre-allocate boundary heap  
    28.     //步骤1,初始化堆和栈  
    29.     //定义堆,用于存储组块的边界像素  
    30.     int** heap = (int**)cvAlloc( (src->rows*src->cols+256)*sizeof(heap[0]) );  
    31.     int** heap_start[256];  
    32.     //heap_start为三指针变量,heap_start为边界像素的灰度值,因此它数量为256个;*heap_start表示边界像素中该灰度值的数量;**heap_start表示边界像素中该灰度值中第*heap_start个所对应的像素地址指针。  
    33.     heap_start[0] = heap;  
    34.   
    35.     // pre-allocate linked point and grow history  
    36.     //pts表示组块内像素链表,即像素间相互链接  
    37.     LinkedPoint* pts = (LinkedPoint*)cvAlloc( src->rows*src->cols*sizeof(pts[0]) );  
    38.     //history表示每个组块生长的状况,即随着阈值的增加,组块的大小是在不断扩大的  
    39.     MSERGrowHistory* history = (MSERGrowHistory*)cvAlloc( src->rows*src->cols*sizeof(history[0]) );  
    40.     //comp表示图像内连通的组块(即区域),原则上每一个灰度值就会有一个组块,但之所以组块的个数是257个,是因为有一个组块是虚假组块,用于表示程序的结束。用栈的形式来管理各个组块  
    41.     MSERConnectedComp comp[257];  
    42.   
    43.     // darker to brighter (MSER-)  
    44.     //MSER-  
    45.     //先对原图进行预处理  
    46.     imgptr = preprocessMSER_8UC1( img, heap_start, src, mask );  
    47.     //执行MSER操作  
    48.     extractMSER_8UC1_Pass( ioptr, imgptr, heap_start, pts, history, comp, step, stepmask, stepgap, params, -1, contours, storage );  
    49.     // brighter to darker (MSER+)  
    50.     //MSER+  
    51.     imgptr = preprocessMSER_8UC1( img, heap_start, src, mask );  
    52.     extractMSER_8UC1_Pass( ioptr, imgptr, heap_start, pts, history, comp, step, stepmask, stepgap, params, 1, contours, storage );  
    53.   
    54.     // clean up  
    55.     //清理内存  
    56.     cvFree( &history );  
    57.     cvFree( &heap );  
    58.     cvFree( &pts );  
    59.     cvReleaseMat( &img );  
    60. }  

    static void extractMSER_8UC1( CvMat* src,
                 CvMat* mask,
                 CvSeq* contours,
                 CvMemStorage* storage,
                 MSERParams params )
    {
        //为了加快运算速度,把原图的宽扩展成高度复合数,即2^N的形式
        //step为扩展后的宽,初始值为8
        int step = 8;
        //stepgap为N,初始值为3,即8=2^3
        int stepgap = 3;
        //通过step向左移位的方式扩展原图的宽
        while ( step < src->step+2 )
        {
            step <<= 1;
            stepgap++;
        }
        int stepmask = step-1;
    
        // to speedup the process, make the width to be 2^N
        //创建扩展后的图像矩阵,宽为2^N,高为原图高+2
        CvMat* img = cvCreateMat( src->rows+2, step, CV_32SC1 );
        //定义第二行地址
        int* ioptr = img->data.i+step+1;
        int* imgptr;
    
        // pre-allocate boundary heap
        //步骤1,初始化堆和栈
        //定义堆,用于存储组块的边界像素
        int** heap = (int**)cvAlloc( (src->rows*src->cols+256)*sizeof(heap[0]) );
        int** heap_start[256];
        //heap_start为三指针变量,heap_start为边界像素的灰度值,因此它数量为256个;*heap_start表示边界像素中该灰度值的数量;**heap_start表示边界像素中该灰度值中第*heap_start个所对应的像素地址指针。
        heap_start[0] = heap;
    
        // pre-allocate linked point and grow history
        //pts表示组块内像素链表,即像素间相互链接
        LinkedPoint* pts = (LinkedPoint*)cvAlloc( src->rows*src->cols*sizeof(pts[0]) );
        //history表示每个组块生长的状况,即随着阈值的增加,组块的大小是在不断扩大的
        MSERGrowHistory* history = (MSERGrowHistory*)cvAlloc( src->rows*src->cols*sizeof(history[0]) );
        //comp表示图像内连通的组块(即区域),原则上每一个灰度值就会有一个组块,但之所以组块的个数是257个,是因为有一个组块是虚假组块,用于表示程序的结束。用栈的形式来管理各个组块
        MSERConnectedComp comp[257];
    
        // darker to brighter (MSER-)
        //MSER-
        //先对原图进行预处理
        imgptr = preprocessMSER_8UC1( img, heap_start, src, mask );
        //执行MSER操作
        extractMSER_8UC1_Pass( ioptr, imgptr, heap_start, pts, history, comp, step, stepmask, stepgap, params, -1, contours, storage );
        // brighter to darker (MSER+)
        //MSER+
        imgptr = preprocessMSER_8UC1( img, heap_start, src, mask );
        extractMSER_8UC1_Pass( ioptr, imgptr, heap_start, pts, history, comp, step, stepmask, stepgap, params, 1, contours, storage );
    
        // clean up
        //清理内存
        cvFree( &history );
        cvFree( &heap );
        cvFree( &pts );
        cvReleaseMat( &img );
    }
    

     

    preprocessMSER_8UC1函数为预处理的过程,主要就是对宽度扩展以后的图像矩阵进行赋值,每一位都赋予不同的含义:

    // to preprocess src image to followingformat

    // 32-bit image

    // > 0 is available, < 0 is visited

    // 17~19 bits is the direction

    // 8~11 bits is the bucket it falls to (forBitScanForward)

    // 0~8 bits is the color

    /*定义图像矩阵的数据格式为有符号32位整型,最高一位表示是否被访问过,0表示没有被访问过,1表示被访问过(因为是有符号数,所以最高一位是1也就是负数);16~18位(这里源码注解有误)表示4邻域的方向;0~7位表示该像素的灰度值*/

    //img代表图像矩阵,MSER处理的是该矩阵

    //src为输入原图

    //heap_cur为边界像素堆

    //mask为掩码

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. static int* preprocessMSER_8UC1( CvMat* img,  
    2.             int*** heap_cur,  
    3.             CvMat* src,  
    4.             CvMat* mask )  
    5. {  
    6.     int srccpt = src->step-src->cols;  
    7.     //由于图像矩阵的宽经过了2^N处理,所以它的宽比原图的宽要长,cpt_1代表两个宽度的差值  
    8.     int cpt_1 = img->cols-src->cols-1;  
    9.     //图像矩阵的地址指针  
    10.     int* imgptr = img->data.i;  
    11.     //定义真实的图像起始地址  
    12.     int* startptr;  
    13.   
    14.     //定义并初始化灰度值数组  
    15.     int level_size[256];  
    16.     for ( int i = 0; i < 256; i++ )  
    17.         level_size[i] = 0;  
    18.     //为图像矩阵的第一行赋值  
    19.     for ( int i = 0; i < src->cols+2; i++ )  
    20.     {  
    21.         *imgptr = -1;  
    22.         imgptr++;  
    23.     }  
    24.     //地址指针指向图像矩阵的第二行  
    25.     imgptr += cpt_1-1;  
    26.     //原图首地址指针  
    27.     uchar* srcptr = src->data.ptr;  
    28.     if ( mask )    //如果定义了掩码矩阵  
    29.     {  
    30.         startptr = 0;  
    31.         //掩码矩阵首地址指针  
    32.         uchar* maskptr = mask->data.ptr;  
    33.         //遍历整个原图  
    34.         for ( int i = 0; i < src->rows; i++ )  
    35.         {  
    36.             *imgptr = -1;  
    37.             imgptr++;  
    38.             for ( int j = 0; j < src->cols; j++ )  
    39.             {  
    40.                 if ( *maskptr )  
    41.                 {  
    42.                     if ( !startptr )  
    43.                         startptr = imgptr;    //赋值  
    44.                     *srcptr = 0xff-*srcptr;    //反转图像的灰度值  
    45.                     level_size[*srcptr]++;    //为灰度值计数  
    46.                     //为图像矩阵赋值,它的低8位是原图灰度值,8~10位是灰度值的高3位  
    47.                     *imgptr = ((*srcptr>>5)<<8)|(*srcptr);  
    48.                 } else {    //掩码覆盖的像素值为-1  
    49.                     *imgptr = -1;  
    50.                 }  
    51.                 //地址加1  
    52.                 imgptr++;  
    53.                 srcptr++;  
    54.                 maskptr++;  
    55.             }  
    56.             //跳过图像矩阵比原图多出的部分  
    57.             *imgptr = -1;  
    58.             imgptr += cpt_1;  
    59.             srcptr += srccpt;  
    60.             maskptr += srccpt;  
    61.         }  
    62.     } else {    //没有定义掩码  
    63.         startptr = imgptr+img->cols+1;    //赋值  
    64.         //遍历整幅图像,为图像矩阵赋值  
    65.         for ( int i = 0; i < src->rows; i++ )  
    66.         {  
    67.             *imgptr = -1;  
    68.             imgptr++;  
    69.             for ( int j = 0; j < src->cols; j++ )  
    70.             {  
    71.                 *srcptr = 0xff-*srcptr;  
    72.                 level_size[*srcptr]++;  
    73.                 *imgptr = ((*srcptr>>5)<<8)|(*srcptr);  
    74.                 imgptr++;  
    75.                 srcptr++;  
    76.             }  
    77.             *imgptr = -1;  
    78.             imgptr += cpt_1;  
    79.             srcptr += srccpt;  
    80.         }  
    81.     }  
    82.     //为图像矩阵的最后一行赋值  
    83.     for ( int i = 0; i < src->cols+2; i++ )  
    84.     {  
    85.         *imgptr = -1;  
    86.         imgptr++;  
    87.     }  
    88.     //定义边界像素堆的大小  
    89.     //heap_cur[]对应灰度值,heap_cur[][]对应该灰度值的个数  
    90.     //根据灰度值的个数定义heap_cur的长度  
    91.     heap_cur[0][0] = 0;  
    92.     for ( int i = 1; i < 256; i++ )  
    93.     {  
    94.         heap_cur[i] = heap_cur[i-1]+level_size[i-1]+1;  
    95.         heap_cur[i][0] = 0;  
    96.     }  
    97.     //返回在图像矩阵中第一个真正的像素点的地址  
    98.     return startptr;  
    99. }  

    static int* preprocessMSER_8UC1( CvMat* img,
                int*** heap_cur,
                CvMat* src,
                CvMat* mask )
    {
        int srccpt = src->step-src->cols;
        //由于图像矩阵的宽经过了2^N处理,所以它的宽比原图的宽要长,cpt_1代表两个宽度的差值
        int cpt_1 = img->cols-src->cols-1;
        //图像矩阵的地址指针
        int* imgptr = img->data.i;
        //定义真实的图像起始地址
        int* startptr;
    
        //定义并初始化灰度值数组
        int level_size[256];
        for ( int i = 0; i < 256; i++ )
            level_size[i] = 0;
        //为图像矩阵的第一行赋值
        for ( int i = 0; i < src->cols+2; i++ )
        {
            *imgptr = -1;
            imgptr++;
        }
        //地址指针指向图像矩阵的第二行
        imgptr += cpt_1-1;
        //原图首地址指针
        uchar* srcptr = src->data.ptr;
        if ( mask )    //如果定义了掩码矩阵
        {
            startptr = 0;
            //掩码矩阵首地址指针
            uchar* maskptr = mask->data.ptr;
            //遍历整个原图
            for ( int i = 0; i < src->rows; i++ )
            {
                *imgptr = -1;
                imgptr++;
                for ( int j = 0; j < src->cols; j++ )
                {
                    if ( *maskptr )
                    {
                        if ( !startptr )
                            startptr = imgptr;    //赋值
                        *srcptr = 0xff-*srcptr;    //反转图像的灰度值
                        level_size[*srcptr]++;    //为灰度值计数
                        //为图像矩阵赋值,它的低8位是原图灰度值,8~10位是灰度值的高3位
                        *imgptr = ((*srcptr>>5)<<8)|(*srcptr);
                    } else {    //掩码覆盖的像素值为-1
                        *imgptr = -1;
                    }
                    //地址加1
                    imgptr++;
                    srcptr++;
                    maskptr++;
                }
                //跳过图像矩阵比原图多出的部分
                *imgptr = -1;
                imgptr += cpt_1;
                srcptr += srccpt;
                maskptr += srccpt;
            }
        } else {    //没有定义掩码
            startptr = imgptr+img->cols+1;    //赋值
            //遍历整幅图像,为图像矩阵赋值
            for ( int i = 0; i < src->rows; i++ )
            {
                *imgptr = -1;
                imgptr++;
                for ( int j = 0; j < src->cols; j++ )
                {
                    *srcptr = 0xff-*srcptr;
                    level_size[*srcptr]++;
                    *imgptr = ((*srcptr>>5)<<8)|(*srcptr);
                    imgptr++;
                    srcptr++;
                }
                *imgptr = -1;
                imgptr += cpt_1;
                srcptr += srccpt;
            }
        }
        //为图像矩阵的最后一行赋值
        for ( int i = 0; i < src->cols+2; i++ )
        {
            *imgptr = -1;
            imgptr++;
        }
        //定义边界像素堆的大小
        //heap_cur[]对应灰度值,heap_cur[][]对应该灰度值的个数
        //根据灰度值的个数定义heap_cur的长度
        heap_cur[0][0] = 0;
        for ( int i = 1; i < 256; i++ )
        {
            heap_cur[i] = heap_cur[i-1]+level_size[i-1]+1;
            heap_cur[i][0] = 0;
        }
        //返回在图像矩阵中第一个真正的像素点的地址
        return startptr;
    }
    

    extractMSER_8UC1_Pass函数执行MSER算法,MSER-和MSER+都执行该函数,但可以通过参数color来区分。

     

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. static void extractMSER_8UC1_Pass( int* ioptr,  
    2.               int* imgptr,  
    3.               int*** heap_cur,  
    4.               LinkedPoint* ptsptr,  
    5.               MSERGrowHistory* histptr,  
    6.               MSERConnectedComp* comptr,  
    7.               int step,  
    8.               int stepmask,  
    9.               int stepgap,  
    10.               MSERParams params,  
    11.               int color,  
    12.               CvSeq* contours,  
    13.               CvMemStorage* storage )  
    14. {  
    15.     //设置第一个组块的灰度值为256,该灰度值是真实图像中不存在的灰度值,以区分真实图像的组块,从而判断程序是否结束  
    16.     comptr->grey_level = 256;  
    17.     //步骤2和步骤3  
    18.     //指向第二个组块  
    19.     comptr++;  
    20.     //设置第二个组块为输入图像第一个像素(左上角)的灰度值  
    21.     comptr->grey_level = (*imgptr)&0xff;  
    22.     //初始化该组块  
    23.     initMSERComp( comptr );  
    24.     //在最高位标注该像素为已被访问过,即该值小于0  
    25.     *imgptr |= 0x80000000;  
    26.     //得到该像素所对应的堆,即指向它所对应的灰度值  
    27.     heap_cur += (*imgptr)&0xff;  
    28.     //定义方向,即偏移量,因为是4邻域,所以该数组分别对应右、下、左、上  
    29.     int dir[] = { 1, step, -1, -step };  
    30. #ifdef __INTRIN_ENABLED__  
    31.     unsigned long heapbit[] = { 0, 0, 0, 0, 0, 0, 0, 0 };  
    32.     unsigned long* bit_cur = heapbit+(((*imgptr)&0x700)>>8);  
    33. #endif  
    34.     //死循环,退出该死循环的条件有两个:一是到达组块的栈底;二是边界像素堆中没有任何值。达到栈底也就意味着堆中没有值,在此函数中两者是一致的。  
    35.     for ( ; ; )  
    36.     {  
    37.         // take tour of all the 4 directions  
    38.         //步骤4  
    39.         //在4邻域内进行搜索  
    40.         while ( ((*imgptr)&0x70000) < 0x40000 )  
    41.         {  
    42.             // get the neighbor  
    43.             /* ((*imgptr)&0x70000)>>16得到第16位至第18位数据,该数据对应的4邻域的方向,再通过dir数组得到4邻域的偏移量,因此imgptr_nbr为当前像素4邻域中某一个方向上邻域的地址指针 */  
    44.             int* imgptr_nbr = imgptr+dir[((*imgptr)&0x70000)>>16];  
    45.             //检查邻域像素是否被访问过,如果被访问过,则会在第一位置1,因此该值会小于0,否则第一位为0,该值大于0  
    46.             if ( *imgptr_nbr >= 0 ) // if the neighbor is not visited yet  
    47.             {  
    48.                 //标注该像素已被访问过,即把第一位置1  
    49.                 *imgptr_nbr |= 0x80000000; // mark it as visited  
    50.                 //比较当前像素与邻域像素灰度值  
    51.                 if ( ((*imgptr_nbr)&0xff) < ((*imgptr)&0xff) )  
    52.                 {  
    53.                     //如果邻域值小于当前值,把当前值放入堆中  
    54.                     // when the value of neighbor smaller than current  
    55.                     // push current to boundary heap and make the neighbor to be the current one  
    56.                     // create an empty comp  
    57.                     //堆中该像素灰度值的数量加1,即对该灰度值像素个数计数  
    58.                     (*heap_cur)++;  
    59.                     //把当前值的地址放入堆中  
    60.                     **heap_cur = imgptr;  
    61.                     //重新标注当前值的方向位,以备下一次访问该值时搜索下一个邻域  
    62.                     *imgptr += 0x10000;  
    63.                     //定位邻域值所对应的堆的位置  
    64.                     //当前heap_cur所指向的灰度值为while循环搜索中的最小灰度值,即水溢过的最低点  
    65.                     heap_cur += ((*imgptr_nbr)&0xff)-((*imgptr)&0xff);  
    66. #ifdef __INTRIN_ENABLED__  
    67.                     _bitset( bit_cur, (*imgptr)&0x1f );  
    68.                     bit_cur += (((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8;  
    69. #endif  
    70.                     imgptr = imgptr_nbr;    //邻域值换为当前值  
    71.                     //步骤3  
    72.                     comptr++;    //创建一个组块  
    73.                     initMSERComp( comptr );    //初始化该组块  
    74.                     comptr->grey_level = (*imgptr)&0xff;    //为该组块的灰度值赋值  
    75.                     //当某个邻域值小于当前值,则不对当前值再做任何操作,继续下次循环,在下次循环中,处理的则是该邻域值,即再次执行步骤4  
    76.                     continue;  
    77.                 } else {  
    78.                     //如果邻域值大于当前值,把邻域值放入堆中  
    79.                     // otherwise, push the neighbor to boundary heap  
    80.                     //找到该邻域值在堆中的灰度值位置,并对其计数,即对该灰度值像素个数计数   
    81.                     heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)]++;  
    82.                     //把该邻域像素地址放入堆中  
    83.                     *heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)] = imgptr_nbr;  
    84. #ifdef __INTRIN_ENABLED__  
    85.                     _bitset( bit_cur+((((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8), (*imgptr_nbr)&0x1f );  
    86. #endif  
    87.                 }  
    88.             }  
    89.             *imgptr += 0x10000;    //重新标注当前值的领域方向  
    90.         }  
    91.         //imsk表示结束while循环后所得到的最后像素地址与图像首地址的相对距离  
    92.         int imsk = (int)(imgptr-ioptr);  
    93.         //得到结束while循环后的最后像素的坐标位置  
    94.         //从这里可以看出图像的宽采样2^N的好处,即imsk>>stepgap  
    95.         ptsptr->pt = cvPoint( imsk&stepmask, imsk>>stepgap );  
    96.         // get the current location  
    97.         //步骤5  
    98.         //对栈顶的组块的像素个数累加,即计算组块的面积大小,并链接组块内的像素点  
    99.         //结束while循环后,栈顶组块的灰度值就是该次循环后得到的最小灰度值,也就是该组块为极低点,就相当于水已经流到了最低的位置  
    100.         accumulateMSERComp( comptr, ptsptr );  
    101.         //指向下一个像素点链表位置  
    102.         ptsptr++;  
    103.         // get the next pixel from boundary heap  
    104.         //步骤6  
    105.         /*结束while循环后,如果**heap_cur有值的话,heap_cur指向的应该是while循环中得到的灰度值最小值,也就是在组块的边界像素中,有与组块相同的灰度值,因此要把该值作为当前值继续while循环,也就是相当于组块面积的扩展*/  
    106.         if ( **heap_cur )    //有值  
    107.         {  
    108.             imgptr = **heap_cur;    //把该像素点作为当前值  
    109.             (*heap_cur)--;    //像素的个数要相应的减1  
    110. #ifdef __INTRIN_ENABLED__  
    111.             if ( !**heap_cur )  
    112.                 _bitreset( bit_cur, (*imgptr)&0x1f );  
    113. #endif  
    114.         //步骤7  
    115.         //已经找到了最小灰度值的组块,并且边界像素堆中的灰度值都比组块的灰度值大,则这时需要组块,即计算最大稳定极值区域  
    116.         } else {  
    117. #ifdef __INTRIN_ENABLED__  
    118.             bool found_pixel = 0;  
    119.             unsigned long pixel_val;  
    120.             for ( int i = ((*imgptr)&0x700)>>8; i < 8; i++ )  
    121.             {  
    122.                 if ( _BitScanForward( &pixel_val, *bit_cur ) )  
    123.                 {  
    124.                     found_pixel = 1;  
    125.                     pixel_val += i<<5;  
    126.                     heap_cur += pixel_val-((*imgptr)&0xff);  
    127.                     break;  
    128.                 }  
    129.                 bit_cur++;  
    130.             }  
    131.             if ( found_pixel )  
    132. #else  
    133.             heap_cur++;    //指向高一级的灰度值  
    134.             unsigned long pixel_val = 0;  
    135.             //在边界像素堆中,找到边界像素中的最小灰度值  
    136.             for ( unsigned long i = ((*imgptr)&0xff)+1; i < 256; i++ )  
    137.             {  
    138.                 if ( **heap_cur )  
    139.                 {  
    140.                     pixel_val = i;    //灰度值  
    141.                     break;  
    142.                 }  
    143.                 //定位在堆中所对应的灰度值,与pixel_val是相等的  
    144.                 heap_cur++;   
    145.             }  
    146.             if ( pixel_val )    //如果找到了像素值  
    147. #endif  
    148.             {  
    149.                 imgptr = **heap_cur;    //从堆中提取出该像素  
    150.                 (*heap_cur)--;    //对应的像素个数减1  
    151. #ifdef __INTRIN_ENABLED__  
    152.                 if ( !**heap_cur )  
    153.                     _bitreset( bit_cur, pixel_val&0x1f );  
    154. #endif  
    155.                 //进入处理栈子模块  
    156.                 if ( pixel_val < comptr[-1].grey_level )  
    157.                 //如果从堆中提取出的最小灰度值小于距栈顶第二个组块的灰度值,则说明栈顶组块和第二个组块之间仍然有没有处理过的组块,因此在计算完MSER值后还要继续返回步骤4搜索该组块  
    158.                 {  
    159.                     // check the stablity and push a new history, increase the grey level  
    160.                     //利用公式2计算栈顶组块的q(i)值  
    161.                     if ( MSERStableCheck( comptr, params ) )    //是MSER  
    162.                     {  
    163.                         //得到组块内的像素点  
    164.                         CvContour* contour = MSERToContour( comptr, storage );  
    165.                         contour->color = color;    //标注是MSER-还是MSER+  
    166.                         //把组块像素点放入序列中  
    167.                         cvSeqPush( contours, &contour );   
    168.                     }  
    169.                     MSERNewHistory( comptr, histptr );  
    170.                     //改变栈顶组块的灰度值,这样就可以和上一层的组块进行合并  
    171.                     comptr[0].grey_level = pixel_val;  
    172.                     histptr++;  
    173.                 } else {  
    174.                     //从堆中提取出的最小灰度值大于等于距栈顶第二个组块的灰度值  
    175.                     // keep merging top two comp in stack until the grey level >= pixel_val  
    176.                     //死循环,用于处理灰度值相同并且相连的组块之间的合并  
    177.                     for ( ; ; )  
    178.                     {  
    179.                         //指向距栈顶第二个组块  
    180.                         comptr--;  
    181.                         //合并前两个组块,并把合并后的组块作为栈顶组块  
    182.                         MSERMergeComp( comptr+1, comptr, comptr, histptr );  
    183.                         histptr++;  
    184.                         /*如果pixel_val = comptr[0].grey_level,说明在边界上还有属于该组块的像素;如果pixel_val < comptr[0].grey_level,说明还有比栈顶组块灰度值更小的组块没有搜索到。这两种情况都需要回到步骤4中继续搜索组块*/  
    185.                         if ( pixel_val <= comptr[0].grey_level )  
    186.                             break;  
    187.                         //合并栈内前两个组块,直到pixel_val < comptr[-1].grey_level为止  
    188.                         if ( pixel_val < comptr[-1].grey_level )  
    189.                         {  
    190.                             // check the stablity here otherwise it wouldn't be an ER  
    191.                             if ( MSERStableCheck( comptr, params ) )  
    192.                             {  
    193.                                 CvContour* contour = MSERToContour( comptr, storage );  
    194.                                 contour->color = color;  
    195.                                 cvSeqPush( contours, &contour );  
    196.                             }  
    197.                             MSERNewHistory( comptr, histptr );  
    198.                             comptr[0].grey_level = pixel_val;  
    199.                             histptr++;  
    200.                             break;  
    201.                         }  
    202.                     }  
    203.                 }  
    204.             } else  
    205.                 //边界像素堆中没有任何像素,则退出死循环,该函数返回。  
    206.                 break;  
    207.         }  
    208.     }  
    209. }  

    static void extractMSER_8UC1_Pass( int* ioptr,
                  int* imgptr,
                  int*** heap_cur,
                  LinkedPoint* ptsptr,
                  MSERGrowHistory* histptr,
                  MSERConnectedComp* comptr,
                  int step,
                  int stepmask,
                  int stepgap,
                  MSERParams params,
                  int color,
                  CvSeq* contours,
                  CvMemStorage* storage )
    {
        //设置第一个组块的灰度值为256,该灰度值是真实图像中不存在的灰度值,以区分真实图像的组块,从而判断程序是否结束
        comptr->grey_level = 256;
        //步骤2和步骤3
        //指向第二个组块
        comptr++;
        //设置第二个组块为输入图像第一个像素(左上角)的灰度值
        comptr->grey_level = (*imgptr)&0xff;
        //初始化该组块
        initMSERComp( comptr );
        //在最高位标注该像素为已被访问过,即该值小于0
        *imgptr |= 0x80000000;
        //得到该像素所对应的堆,即指向它所对应的灰度值
        heap_cur += (*imgptr)&0xff;
        //定义方向,即偏移量,因为是4邻域,所以该数组分别对应右、下、左、上
        int dir[] = { 1, step, -1, -step };
    #ifdef __INTRIN_ENABLED__
        unsigned long heapbit[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
        unsigned long* bit_cur = heapbit+(((*imgptr)&0x700)>>8);
    #endif
        //死循环,退出该死循环的条件有两个:一是到达组块的栈底;二是边界像素堆中没有任何值。达到栈底也就意味着堆中没有值,在此函数中两者是一致的。
        for ( ; ; )
        {
            // take tour of all the 4 directions
            //步骤4
            //在4邻域内进行搜索
            while ( ((*imgptr)&0x70000) < 0x40000 )
            {
                // get the neighbor
                /* ((*imgptr)&0x70000)>>16得到第16位至第18位数据,该数据对应的4邻域的方向,再通过dir数组得到4邻域的偏移量,因此imgptr_nbr为当前像素4邻域中某一个方向上邻域的地址指针 */
                int* imgptr_nbr = imgptr+dir[((*imgptr)&0x70000)>>16];
                //检查邻域像素是否被访问过,如果被访问过,则会在第一位置1,因此该值会小于0,否则第一位为0,该值大于0
                if ( *imgptr_nbr >= 0 ) // if the neighbor is not visited yet
                {
                    //标注该像素已被访问过,即把第一位置1
                    *imgptr_nbr |= 0x80000000; // mark it as visited
                    //比较当前像素与邻域像素灰度值
                    if ( ((*imgptr_nbr)&0xff) < ((*imgptr)&0xff) )
                    {
                        //如果邻域值小于当前值,把当前值放入堆中
                        // when the value of neighbor smaller than current
                        // push current to boundary heap and make the neighbor to be the current one
                        // create an empty comp
                        //堆中该像素灰度值的数量加1,即对该灰度值像素个数计数
                        (*heap_cur)++;
                        //把当前值的地址放入堆中
                        **heap_cur = imgptr;
                        //重新标注当前值的方向位,以备下一次访问该值时搜索下一个邻域
                        *imgptr += 0x10000;
                        //定位邻域值所对应的堆的位置
                        //当前heap_cur所指向的灰度值为while循环搜索中的最小灰度值,即水溢过的最低点
                        heap_cur += ((*imgptr_nbr)&0xff)-((*imgptr)&0xff);
    #ifdef __INTRIN_ENABLED__
                        _bitset( bit_cur, (*imgptr)&0x1f );
                        bit_cur += (((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8;
    #endif
                        imgptr = imgptr_nbr;    //邻域值换为当前值
                        //步骤3
                        comptr++;    //创建一个组块
                        initMSERComp( comptr );    //初始化该组块
                        comptr->grey_level = (*imgptr)&0xff;    //为该组块的灰度值赋值
                        //当某个邻域值小于当前值,则不对当前值再做任何操作,继续下次循环,在下次循环中,处理的则是该邻域值,即再次执行步骤4
                        continue;
                    } else {
                        //如果邻域值大于当前值,把邻域值放入堆中
                        // otherwise, push the neighbor to boundary heap
                        //找到该邻域值在堆中的灰度值位置,并对其计数,即对该灰度值像素个数计数 
                        heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)]++;
                        //把该邻域像素地址放入堆中
                        *heap_cur[((*imgptr_nbr)&0xff)-((*imgptr)&0xff)] = imgptr_nbr;
    #ifdef __INTRIN_ENABLED__
                        _bitset( bit_cur+((((*imgptr_nbr)&0x700)-((*imgptr)&0x700))>>8), (*imgptr_nbr)&0x1f );
    #endif
                    }
                }
                *imgptr += 0x10000;    //重新标注当前值的领域方向
            }
            //imsk表示结束while循环后所得到的最后像素地址与图像首地址的相对距离
            int imsk = (int)(imgptr-ioptr);
            //得到结束while循环后的最后像素的坐标位置
            //从这里可以看出图像的宽采样2^N的好处,即imsk>>stepgap
            ptsptr->pt = cvPoint( imsk&stepmask, imsk>>stepgap );
            // get the current location
            //步骤5
            //对栈顶的组块的像素个数累加,即计算组块的面积大小,并链接组块内的像素点
            //结束while循环后,栈顶组块的灰度值就是该次循环后得到的最小灰度值,也就是该组块为极低点,就相当于水已经流到了最低的位置
            accumulateMSERComp( comptr, ptsptr );
            //指向下一个像素点链表位置
            ptsptr++;
            // get the next pixel from boundary heap
            //步骤6
            /*结束while循环后,如果**heap_cur有值的话,heap_cur指向的应该是while循环中得到的灰度值最小值,也就是在组块的边界像素中,有与组块相同的灰度值,因此要把该值作为当前值继续while循环,也就是相当于组块面积的扩展*/
            if ( **heap_cur )    //有值
            {
                imgptr = **heap_cur;    //把该像素点作为当前值
                (*heap_cur)--;    //像素的个数要相应的减1
    #ifdef __INTRIN_ENABLED__
                if ( !**heap_cur )
                    _bitreset( bit_cur, (*imgptr)&0x1f );
    #endif
            //步骤7
            //已经找到了最小灰度值的组块,并且边界像素堆中的灰度值都比组块的灰度值大,则这时需要组块,即计算最大稳定极值区域
            } else {
    #ifdef __INTRIN_ENABLED__
                bool found_pixel = 0;
                unsigned long pixel_val;
                for ( int i = ((*imgptr)&0x700)>>8; i < 8; i++ )
                {
                    if ( _BitScanForward( &pixel_val, *bit_cur ) )
                    {
                        found_pixel = 1;
                        pixel_val += i<<5;
                        heap_cur += pixel_val-((*imgptr)&0xff);
                        break;
                    }
                    bit_cur++;
                }
                if ( found_pixel )
    #else
                heap_cur++;    //指向高一级的灰度值
                unsigned long pixel_val = 0;
                //在边界像素堆中,找到边界像素中的最小灰度值
                for ( unsigned long i = ((*imgptr)&0xff)+1; i < 256; i++ )
                {
                    if ( **heap_cur )
                    {
                        pixel_val = i;    //灰度值
                        break;
                    }
                    //定位在堆中所对应的灰度值,与pixel_val是相等的
                    heap_cur++; 
                }
                if ( pixel_val )    //如果找到了像素值
    #endif
                {
                    imgptr = **heap_cur;    //从堆中提取出该像素
                    (*heap_cur)--;    //对应的像素个数减1
    #ifdef __INTRIN_ENABLED__
                    if ( !**heap_cur )
                        _bitreset( bit_cur, pixel_val&0x1f );
    #endif
                    //进入处理栈子模块
                    if ( pixel_val < comptr[-1].grey_level )
                    //如果从堆中提取出的最小灰度值小于距栈顶第二个组块的灰度值,则说明栈顶组块和第二个组块之间仍然有没有处理过的组块,因此在计算完MSER值后还要继续返回步骤4搜索该组块
                    {
                        // check the stablity and push a new history, increase the grey level
                        //利用公式2计算栈顶组块的q(i)值
                        if ( MSERStableCheck( comptr, params ) )    //是MSER
                        {
                            //得到组块内的像素点
                            CvContour* contour = MSERToContour( comptr, storage );
                            contour->color = color;    //标注是MSER-还是MSER+
                            //把组块像素点放入序列中
                            cvSeqPush( contours, &contour ); 
                        }
                        MSERNewHistory( comptr, histptr );
                        //改变栈顶组块的灰度值,这样就可以和上一层的组块进行合并
                        comptr[0].grey_level = pixel_val;
                        histptr++;
                    } else {
                        //从堆中提取出的最小灰度值大于等于距栈顶第二个组块的灰度值
                        // keep merging top two comp in stack until the grey level >= pixel_val
                        //死循环,用于处理灰度值相同并且相连的组块之间的合并
                        for ( ; ; )
                        {
                            //指向距栈顶第二个组块
                            comptr--;
                            //合并前两个组块,并把合并后的组块作为栈顶组块
                            MSERMergeComp( comptr+1, comptr, comptr, histptr );
                            histptr++;
                            /*如果pixel_val = comptr[0].grey_level,说明在边界上还有属于该组块的像素;如果pixel_val < comptr[0].grey_level,说明还有比栈顶组块灰度值更小的组块没有搜索到。这两种情况都需要回到步骤4中继续搜索组块*/
                            if ( pixel_val <= comptr[0].grey_level )
                                break;
                            //合并栈内前两个组块,直到pixel_val < comptr[-1].grey_level为止
                            if ( pixel_val < comptr[-1].grey_level )
                            {
                                // check the stablity here otherwise it wouldn't be an ER
                                if ( MSERStableCheck( comptr, params ) )
                                {
                                    CvContour* contour = MSERToContour( comptr, storage );
                                    contour->color = color;
                                    cvSeqPush( contours, &contour );
                                }
                                MSERNewHistory( comptr, histptr );
                                comptr[0].grey_level = pixel_val;
                                histptr++;
                                break;
                            }
                        }
                    }
                } else
                    //边界像素堆中没有任何像素,则退出死循环,该函数返回。
                    break;
            }
        }
    }
    

     

    MSER就分析到这里,至于其中用到的一些子函数就不再分析。这里还要说明一点的是,MSER+和MSER-使用的都是同一个函数,两者的区别是一个组块面积增加,另一个减少。说实话,该部分的内容数据结构较为复杂,有一些内容我理解得也不透彻,比如结构MSERGrowHistory真正的含义还比较模糊。

    下面就给出最大稳定极值区域检测的应用实例:

     

    [cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

    1. #include "opencv2/core/core.hpp"  
    2. #include "opencv2/highgui/highgui.hpp"  
    3. #include "opencv2/imgproc/imgproc.hpp"  
    4. #include <opencv2/features2d/features2d.hpp>  
    5. #include <iostream>  
    6. using namespace cv;  
    7. using namespace std;  
    8.   
    9. int main(int argc, char *argv[])  
    10. {  
    11.     Mat src,gray;  
    12.     src = imread("lenna.bmp");  
    13.     cvtColor( src, gray, CV_BGR2GRAY );  
    14.     //创建MSER类  
    15.     MSER ms;  
    16.     //用于组块区域的像素点集  
    17.     vector<vector<Point>> regions;  
    18.     ms(gray, regions, Mat());  
    19.     //在灰度图像中用椭圆形绘制组块  
    20.     for (int i = 0; i < regions.size(); i++)  
    21.     {  
    22.         ellipse(gray, fitEllipse(regions[i]), Scalar(255));  
    23.     }  
    24.     imshow("mser", gray);  
    25.     waitKey(0);  
    26.     return 0;  
    27. }  

    #include "opencv2/core/core.hpp"
    #include "opencv2/highgui/highgui.hpp"
    #include "opencv2/imgproc/imgproc.hpp"
    #include <opencv2/features2d/features2d.hpp>
    #include <iostream>
    using namespace cv;
    using namespace std;
    
    int main(int argc, char *argv[])
    {
        Mat src,gray;
    	src = imread("lenna.bmp");
    	cvtColor( src, gray, CV_BGR2GRAY );
        //创建MSER类
        MSER ms;
        //用于组块区域的像素点集
        vector<vector<Point>> regions;
        ms(gray, regions, Mat());
        //在灰度图像中用椭圆形绘制组块
        for (int i = 0; i < regions.size(); i++)
        {
            ellipse(gray, fitEllipse(regions[i]), Scalar(255));
        }
        imshow("mser", gray);
        waitKey(0);
        return 0;
    }
    

    结果如下图所示。本文介绍的方法只适用于灰度图像,所以如果输入的是彩色图像,要把它转换为灰度图像。另外在创建MSER类的时候,我们使用的是缺省构造函数,因此MSER算法所需的参数是系统默认的。所以我们检测的结果与David Nister等人在原著中的检测结果略有不同。

     



     

    展开全文
  • 处理流程首先是输入一幅图像,想进行必要的预处理如灰度化,然后提取MSER区域(这里直接利用的是matlab自带的函数detectMSERFeature),然后将得到的区域转换成二值图像(主要是利用取得区域的坐标信息)。...

    利用matlab的detectMSERFeature来实现简单文本定位

    1.处理流程


    首先是输入一幅图像,想进行必要的预处理如灰度化,然后提取MSER区域

    (这里直接利用的是matlab自带的函数detectMSERFeature),然后将得到的区域转换成二值图像(主要是利用取得区域的坐标信息)。对得到的MSER区域二值图像进行连通域分析,

    先粗过滤一些明显不符合字符的区域,然后对过滤后的图像进行闭运算。

    闭运算之后再进行一次细滤除,最后得到包围文本区域的包围盒。

    先看几组效果,左边是原图,右边是定位后的图,绿色线画出来的区域,不是很明显。

    图是比较简单,说明这个方法还是比较初级的,存在比较多的经验阈值。

    CODE


    怎样把mser算法中分割的region坐标取出来?

    如果用的OpenCV, mser.detectRegions()返回值第一个就是region,数据结构差不多是

    [[[x11, y11], [x12, y12], [], ...], [[x21, y21], []...]]

    用的都是np数组。第二个返回值是一组bounding box的list。

    代码包里的EXAMPLE里有mser.py这个例子可参考。

    Has anyone used MSER in OpenCV to detect regions?


    Opencv MSER detectRegions C++

    following steps are performed:

    1. Read image using imread

    2. Convert to gray scale using cvtColor with COLOR_BGR2GRAY

    3. Perform histogram equalization:

      a. CLAHE object is created using clipLimit=2.0, tileGridSize - 8x8
      
      b. apply CLAHE on gray image
      
    4. Get height and width of image.
    5. Scale image to 600X800 SVGA size

      a. if width > height then scale = width / 800.0

      b. else scale = height / 600.0

      c. Use 'resize' with above scaling factor 'scale'

    6. Create MSER object
    7. setDelta(4)
    8. Call detectRegions


    cv::MSER(2, 10, 5000, 0.5, 0.3)(gray, regContours);

    cv::MSER(2, 10, 5000, 0.5, 0.3)已经实例化对象了啊。
    编译器已经知道此处有个实例对象,当然可以直接调用成员函数了。
    只不过这个实力对象没有载体,只能这里调用一次。

    之后就丢失了可寻的载体,你就没法用了而已。


    cv::MSER(2, 10, 5000, 0.5, 0.3)
    这样已经是调用构造函数构造出一个匿名对象了

    随后调用了该对象的void operator()方法








    展开全文
  • 传统的局部特征描述子如SIFT、SURF等,如果不做别的处理,往往会得到大量的特征向量,虽然特征向量的数目越多,对图像的描述越精确,检索的准确率较高,但是这也会增加硬件成本同时也会耗费大量的计算时间。...

    在做图像检索时,需要提取图像的特征向量。传统的局部特征描述子如SIFT、SURF等,如果不做别的处理,往往会得到大量的特征向量,虽然特征向量的数目越多,对图像的描述越精确,检索的准确率较高,但是这也会增加硬件成本同时也会耗费大量的计算时间。

    从博主的试验结果来看,单张图384×256大小,提取出的SIFT平均有200个,如果直接和库中的数据进行相似度计算,大概要1分钟的时间。对于时间要求很高的产业,这是不能接受的。所以,在不进行压缩图像损失信息的前提下,大大减少SIFT的数目是很有必要,也是很有价值的。

    在查阅了大量的资料后,博主发现在做keypoint的compute之前,用MSER 检测出的keypoint代替SIFT检测出的keypoint,可以大大减少SIFT 的数目。对MSER 有疑问的,可以在找几篇相关的博客看一看,不是很复杂。

    简单的说一下MSER(最大稳定值检测),基于分水岭的概念,对图像进行二值化,阈值范围[0,255],然后不断变化阈值,变化量可以自己设置,二值图像就会经历一个从全黑0到全白255的过程,就像水位不断上升时陆地和海平面的俯瞰图。在这个过程中,有些连通区域面积随着阈值的变化量很小或基本不变,这些区域就叫MSER 。关于MSER的算法细节和具体实现就不在这说了,有兴趣的可以自己研究一下。

    当用MSER检测出keypoint之后,就可以利用SIFT的方式计算这些keypoint的描述子了。

    import cv2
    import numpy as np
    import skimage.io as io
    import matplotlib.pyplot as plt
    filename="/home/mysj/文档/testpicture"
    str=filename+"/*.jpg"
    mat=io.ImageCollection(str)
    img=mat[0]
    ##创建一个MSER检测器,并检测图像的MSER区域
    ##kpkp保存检测到的keypoint
    mser=cv2.MSER_create()
    regions,boxes=mser.detectRegions(img)
    kpkp=mser.detect(img)
    print len(mser.detect(img))
    ##用红框框出检测到的MSER区域,boxes保存这些区域的左上角的坐标和区域的宽和高
    for i in range(len(boxes)):
        x,y,w,h=boxes[i]
        cv2.rectangle(img,(x,y),(x+w,y+h),(255,0,0),2)
    #创建一个SIFT特征提取器
    siftt=cv2.xfeatures2d.SIFT_create()
     
    print len(regions)
    print len(boxes)
    kp=siftt.detect(img,None)
    ##计算kpkp的局部描述子
    des=siftt.compute(img,kpkp)
    print len(des[0])
    ##在图像上画出这些keypoint
    cv2.drawKeypoints(img,kpkp,mat[0])
    plt.imshow(mat[0])    
    

    SIFT-SIFT方式提取的特征点有243个,MSER-SIFT提取的特征点有57个,虽然精度会有些下降,但是带来的时间上的提升是很客观的。时间缩短为原来的1/4,相当于原来跑一张的时间现在可以跑4张图。红框是MSER区域。
    在这里插入图片描述

    展开全文
  • 本人为研究生,最近的研究方向是物体识别。所以就将常用的几种特征提取方式做了一个简要的实验和分析。这些实验都是借助于openCV在vs2010下完成的。基本上都是使用的openCV中内置的一些功能函数。...

    本人为研究生,最近的研究方向是物体识别。所以就将常用的几种特征提取方式做了一个简要的实验和分析。这些实验都是借助于openCV在vs2010下完成的。基本上都是使用的openCV中内置的一些功能函数。

    1. SIFT算法

    尺度不变特征转换(Scale-invariant feature transform或SIFT)算法是一种特征提取的方法。它在尺度空间中寻找极值点,并提取出其位置、尺度、旋转不变量,并以此作为特征点并利用特征点的邻域产生特征向量。
    SIFT算法对于光线、噪声、和微小视角改变的容忍度相当高,且对于部分遮挡的物体也有较高的识别相率。
    2. 实验过程

    利用SIFT算法进行特征提取,然后进行物体识别,以下是实验的相关结果。(红色圆圈表示匹配成功的特征点,圆圈的大小代表匹配程度的多少,圆圈半径越大,代表匹配程度越高,绿色的方框为识别出的物体。)






    以上几个实验中,基本上可以正确的识别出罐子,玩偶,蜘蛛侠,鞋子和玩具车。但是,对于苹果的识别实验,则未能达到理想的要求。实验结果如下。


    由实验结果可以看出,特征点的匹配大部分都是错误的,且未能正确识别出图片中的苹果。对苹果使用SIFT算法进行特征提取,结果如下图(红色箭头表示特征点,箭头的起始位置为特征点位置,箭头的方向为特征点最大梯度方向,箭头的长度代表该特征点的权重)。


    通过上图还可以发现,苹果的边界特征点都仅仅有很小的权重(箭头很短),于是尝试设置一个阈值将这些特征点去除,则剩下的大部分都为准确的特征点。选取阈值为1.7,将权值小于1.7的特征点剔除,实验结果如下:


    从上图可以发现,特征点的提取已经比较准确,且基本没有边界特征点带来的干扰。但是,特征点的数量太少,这种解决方法,依旧无法完成苹果的识别。

    3.实验结果分析

    经过查阅SIFT算法作者的文章,发现文章中提出,SIFT算法适合于识别旋转度达60度的平面形状,或是旋转度达到20度的三维物体。

    经过查询其他文章,发现很多人总结的经验表明,SIFT算法对模糊的图像和边缘平滑的图像,检测出的特征点过少,对圆更是无能为力

    4.尝试其他解决方法

    以下尝试几种openCV中常用的特征提取算法。

    FAST

    FAST特征点检测是公认的比较快速的特征点检测方法,只利用周围像素比较的信息就可以得到特征点,简单,有效。该方法多用于角点检测。

    FAST特征检测算法来源于corner的定义,这个定义基于特征点周围的图像灰度值,检测候选特征点周围一圈的像素值,如果候选点周围邻域内有足够多的像素点与该候选点的灰度值差别够大,则认为该候选点为一个特征点。

    以下是利用FAST算法对鞋子和苹果进行特征提取(黑色圆圈为提取得到的特征点)。



    由苹果和鞋子的特征点提取对比试验可以发现,该算法对于鞋子可以提取众多特征点,但是对于苹果仅仅能提取很少量的特征点,可见该方法依旧不适合用于苹果特征点的提取。

    分析原因可以发现,苹果表面颜色和灰度是光滑过渡,所以该算法无法有效的提取特征点。

    MSER

    最大稳定极值区域(MSER-Maximally Stable Extremal Regions)可以用于图像的斑点区域检测。该算法最早是由Matas等人于2002年提出,它是基于分水岭的概念。

    MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会被淹没,如果从天空往下看,则大地分为陆地和水域两个部分,这类似于二值图像。在得到的所有二值图像中,图像中的某些连通区域变化很小,甚至没有变化,则该区域就被称为最大稳定极值区域。这类似于当水面持续上升的时候,有些被水淹没的地方的面积没有变化。

    利用此算法,同样对苹果和鞋子两个物体进行检测,结果如下




    通过对比试验发现,苹果的特征区域依旧非常少。可见该算法依旧不适合于苹果的特征提取。

    分析原因可以发现,苹果的表面的灰度为比较光滑的过渡,当阈值不断增大时,陆地和水面的边界也在平缓的变化,所以很难得到一个最大稳定的极值区域。

    STAR

    利用STAR特征提取算法,实验结果如下:




    由实验结果可以看出,该方法依旧无法提取出苹果的特征点。

    5.总结分析

    由上面的几个试验可知,以这些方法,都无法对苹果进行有效的特征提取。原因基本上都是因为苹果表面颜色过渡比较光滑,其表面大多数点和周围的点颜色差别太小,不宜作为特征点。

    通过这几个实验还可以发现,无论是哪种特征点提取的方法,提取的特征点都位于苹果的上边部分和苹果的右边部分,即不同的特征提取算法提取的特征点的位置还是极为相似的,由此也可以看出不同的特征提取算法虽然方法不同,但是也存在着一定的相似性。


    本人刚刚开始从事物体识别和特征提取的研究不久,还算是个初学者,为了提高自己,也为了和大家多多的交流并互相学习,将最近的一些实验发布出来,欢迎各位批评指正。也非常欢迎和我交流。


    2015年3月9日   西安交通大学


    转载自:https://blog.csdn.net/qq_25352981/article/details/44150753

    展开全文
  • (1)常用图像处理功能,包括颜色空间变换、几何变换(作为Matlab的补充,一般可用于数据集的扩充),常用的机器学习的算法,包括GMM、SVM、KMeans等,常用的图像处理plot工具。 (2)特征提取,包括Covariant、...
  • 最大稳定极值区域MSER是一种...MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会...
  • MSER最稳定极值区域源码分析 最稳定极值区域介绍 本文源于http://www.cnblogs.com/shangd/p/6164916.html 如把灰度图看成高低起伏的地形图,其中灰度值看成海平面高度的话,MSER的作用就是在灰度图中找到...
  • (五)用MSER算法提取特征区域 分水岭算法,通过逐步水淹创建分水岭,把图像分割成多...计算图像MSER的基础类是cv::MSER,它是一个抽象接口,继承自cv::Feature2D类。OpenCV中的所有特征检测类都是从这个类继承的,...
  • 发现很多人都用mser,swt等进行场景文字的检测,最近也去实现了一下,虽然swt较新的算法,但实现过程中传统的mser算法反而更稳定,速度也会更快,可能是我还没有完全领会swt的精髓。ps:暂时只做水平及水平倾斜的文字 ...
  • 最大稳定极值区域(MSER-Maximally Stable Extremal Regions)可以用于图像的斑点区域检测。它是基于分水岭的概念。 SIFT和SURF算法高效实现了具有尺度和旋转不变性的特征检测,但这些特征不具有仿射不变性。区域...
  • MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理SIFT和SURF算法高效实现了具有尺度和旋转不变性的特征检测,但这些特征不具有仿射不变性。区域检测针对各种不同形状的图像区域,通过...
  • MSER算法
  • Matlab 图像处理工具箱

    2015-04-08 21:51:24
    计算机视觉/图像处理研究中经常要用到Matlab,虽然其自带了图像处理和计算机视觉的许多功能,但是术业有专攻,在进行深入的视觉算法研究的时候Matlab的自带功能难免会不够用。本文收集了一些比较优秀的Matlab计算机...
  • MSER算法

    2018-09-25 11:25:39
    注:转载处的文章也是转载的,但是该作者没有给出原创地址,所以我只能先给出该作者的...如把灰度图看成高低起伏的地形图,其中灰度值看成海平面高度的话,MSER的作用就是在灰度图中找到符合条件的坑洼。条件为坑的...
  • Matlab计算机视觉/图像处理工具箱推荐 2014年4月9日机器学习...计算机视觉/图像处理研究中经常要用到Matlab,虽然其自带了图像处理和计算机视觉的许多功能,但是术业有专攻,在进行深入的视觉算法研究的时候Matl
1 2 3 4 5 ... 20
收藏数 826
精华内容 330