欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

mser 最大稳定极值区域(文字区域定位)算法 附完整C代码

程序员文章站 2022-04-11 18:12:37
mser 的全称:Maximally Stable Extremal Regions 第一次听说这个算法时,是来自当时部门的一个同事, 提及到他的项目用它来做文字区域的定位,对这个算法做了一些优化。 也就是中文车牌识别开源项目EasyPR的作者liuruoze,刘兄。 自那时起就有一块石头没放下,想 ......

mser 的全称:Maximally Stable Extremal Regions

第一次听说这个算法时,是来自当时部门的一个同事,

提及到他的项目用它来做文字区域的定位,对这个算法做了一些优化。

也就是中文车牌识别开源项目EasyPR的作者liuruoze,刘兄。

自那时起就有一块石头没放下,想要找个时间好好理理这个算法。

学习一些它的一些思路。

因为一般我学习算法的思路:3个做法,

第一步,编写demo示例。

第二步,进行算法移植或效果改进。

第三步,进行算法性能优化。

然后在这三个过程中,不断来回地验证,实测。

任何事情,一下子囫囵吞枣,容易呛到。

找了不少资料,mser这方面的资料还挺少。

比较不错的资料自然就是开源项目opencv以及VLFeat。

opencv用了太多依赖和封装,阅读代码非常费事。

VLFeat则友好得多。

嗯,花了点时间把mser从VLFeat抽离出来,并编写相应的测试用例。

代码注释比较详尽,写这个示例 demo 的时候,

来回翻阅官方文档无头绪,阅读代码以及注释才大致理清楚逻辑。

项目地址:https://github.com/cpuimage/mser

附完整代码:

/*
* Copyright (C) 2007-12 Andrea Vedaldi and Brian Fulkerson.
* All rights reserved.
* This file is part of the VLFeat library and is made available under
* the terms of the BSD license (see the COPYING file).
*/
#define MSER_DRIVER_VERSION 0.2

#define STB_IMAGE_STATIC
#define STB_IMAGE_IMPLEMENTATION
#include "stb_image.h"
/* ref:https://github.com/nothings/stb/blob/master/stb_image.h */
#define TJE_IMPLEMENTATION
#include "tiny_jpeg.h"
/* ref:https://github.com/serge-rgb/TinyJPEG/blob/master/tiny_jpeg.h */

#include <stdlib.h>
#include <stdio.h>
/* 计时 */
#include <stdint.h>
#if   defined(__APPLE__)
#include <mach/mach_time.h>
#elif defined(_WIN32)
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#else /* __linux */
#include <time.h>
#ifndef  CLOCK_MONOTONIC  /* _RAW */
#define CLOCK_MONOTONIC CLOCK_REALTIME
#endif
#endif
static
uint64_t nanotimer()
{
    static int ever = 0;
#if defined(__APPLE__)
    static mach_timebase_info_data_t frequency;
    if (!ever)
    {
        if (mach_timebase_info(&frequency) != KERN_SUCCESS)
        {
            return(0);
        }
        ever = 1;
    }
    return;
#elif defined(_WIN32)
    static LARGE_INTEGER frequency;
    if (!ever)
    {
        QueryPerformanceFrequency(&frequency);
        ever = 1;
    }
    LARGE_INTEGER t;
    QueryPerformanceCounter(&t);
    return((t.QuadPart * (uint64_t) 1e9) / frequency.QuadPart);
#else   /* __linux */
    struct timespec t;
    if (!ever)
    {
        if (clock_gettime(CLOCK_MONOTONIC, &spec) != 0)
        {
            return(0);
        }
        ever = 1;
    }
    clock_gettime(CLOCK_MONOTONIC, &spec);
    return((t.tv_sec * (uint64_t) 1e9) + t.tv_nsec);
#endif
}


static double now()
{
    static uint64_t epoch = 0;
    if (!epoch)
    {
        epoch = nanotimer();
    }
    return((nanotimer() - epoch) / 1e9);
};

double  calcElapsed(double start, double end)
{
    double took = -start;
    return(took + end);
}


unsigned char* loadImage(const char * filename, int * width, int * height, int * depth)
{
    unsigned char *output = stbi_load(filename, width, height, depth, 1);
    *depth = 1;
    return(output);
}


bool saveJpeg(const char * filename, int width, int height, int depth, unsigned char* bits)
{
    if (!tje_encode_to_file(filename, width, height, depth, true, bits))
    {
        fprintf(stderr, "save JPEG fail.\n");
        return(false);
    }

    return(true);
}
 

/** @brief Maximum value
**
** Maximum value of the integer type ::unsigned char.
**/
#define MSER_PIX_MAXVAL 256


/** @brief MSER Filter
**
** The MSER filter computes the Maximally Stable Extremal Regions of
** an image.
**
** @sa @ref mser
**/
typedef struct _MserFilt MserFilt;

/** @brief MSER filter statistics */
typedef struct _MserStats MserStats;

/** @brief MSER filter statistics definition */
struct _MserStats
{
    int    num_extremal;           /**< number of extremal regions                                */
    int    num_unstable;           /**< number of unstable extremal regions                       */
    int    num_abs_unstable;       /**< number of regions that failed the absolute stability test */
    int    num_too_big;            /**< number of regions that failed the maximum size test       */
    int    num_too_small;          /**< number of regions that failed the minimum size test       */
    int    num_duplicates;         /**< number of regions that failed the duplicate test          */
};


/** @name Construction and Destruction
** @{
**/
MserFilt* mser_new(int ndims, int const* dims);


void mser_delete(MserFilt *f);


/** @} */


/** @name Processing
** @{
**/
void mser_process(MserFilt *f,
    unsigned char const *im);


void mser_ell_fit(MserFilt *f);


/** @} */


/** @name Retrieving data
** @{
**/
unsigned int mser_get_regions_num(MserFilt const *f);


unsigned int const* mser_get_regions(MserFilt const *f);


float const* mser_get_ell(MserFilt const *f);


unsigned int mser_get_ell_num(MserFilt const *f);


unsigned int mser_get_ell_dof(MserFilt const *f);


MserStats const* mser_get_stats(MserFilt const *f);


/** @} */


/** @name Retrieving parameters
** @{
**/
unsigned char mser_get_delta(MserFilt const *f);


float mser_get_min_area(MserFilt const *f);


float mser_get_max_area(MserFilt const *f);


float mser_get_max_variation(MserFilt const *f);


float mser_get_min_diversity(MserFilt const *f);


/** @} */


/** @name Setting parameters
** @{
**/
void mser_set_delta(MserFilt *f, unsigned char x);


void mser_set_min_area(MserFilt *f, float x);


void mser_set_max_area(MserFilt *f, float x);


void mser_set_max_variation(MserFilt *f, float x);


void mser_set_min_diversity(MserFilt *f, float x);


/** @} */


/* ====================================================================
*                                                   INLINE DEFINITIONS
* ================================================================== */


/** @internal
** @brief MSER accumulator data type
**
** This is a large integer type. It should be large enough to contain
** a number equal to the area (volume) of the image by the image
** width by the image height (for instance, if the image is a square
** of side 256, the maximum value is 256 x 256 x 256).
**/
typedef float mser_acc;

/** @internal @brief Basic region flag: null region */
#ifdef COMPILER_MSC
#define MSER_VOID_NODE ( (1ui64 << 32) - 1)
#else
#define MSER_VOID_NODE ( (1ULL << 32) - 1)
#endif

/* ----------------------------------------------------------------- */


/** @internal
** @brief MSER: basic region (declaration)
**
** Extremal regions and maximally stable extremal regions are
** instances of image regions.
**
** There is an image region for each pixel of the image. Each region
** is represented by an instance of this structure.  Regions are
** stored into an array in pixel order.
**
** Regions are arranged into a forest. MserReg::parent points to
** the parent node, or to the node itself if the node is a root.
** MserReg::parent is the index of the node in the node array
** (which therefore is also the index of the corresponding
** pixel). MserReg::height is the distance of the fartest leaf. If
** the node itself is a leaf, then MserReg::height is zero.
**
** MserReg::area is the area of the image region corresponding to
** this node.
**
** MserReg::region is the extremal region identifier. Not all
** regions are extremal regions however; if the region is NOT
** extremal, this field is set to ....
**/
struct _MserReg
{
    unsigned int    parent;         /**< points to the parent region.            */
    unsigned int    shortcut;       /**< points to a region closer to a root.    */
    unsigned int    height;         /**< region height in the forest.            */
    unsigned int    area;           /**< area of the region.                     */
};

/** @internal @brief MSER: basic region */
typedef struct _MserReg MserReg;

/* ----------------------------------------------------------------- */


/** @internal
** @brief MSER: extremal region (declaration)
**
** Extremal regions (ER) are extracted from the region forest. Each
** region is represented by an instance of this structure. The
** structures are stored into an array, in arbitrary order.
**
** ER are arranged into a tree. @a parent points to the parent ER, or
** to itself if the ER is the root.
**
** An instance of the structure represents the extremal region of the
** level set of intensity MserExtrReg::value and containing the
** pixel MserExtReg::index.
**
** MserExtrReg::area is the area of the extremal region and
** MserExtrReg::area_top is the area of the extremal region
** containing this region in the level set of intensity
** MserExtrReg::area + @c delta.
**
** MserExtrReg::variation is the relative area variation @c
** (area_top-area)/area.
**
** MserExtrReg::max_stable is a flag signaling whether this extremal
** region is also maximally stable.
**/
struct _MserExtrReg
{
    int        parent;         /**< index of the parent region                   */
    int        index;          /**< index of pivot pixel                         */
    unsigned char    value;          /**< value of pivot pixel                         */
    unsigned int    shortcut;       /**< shortcut used when building a tree           */
    unsigned int    area;           /**< area of the region                           */
    float        variation;      /**< rel. area variation                          */
    unsigned int    max_stable;     /**< max stable number (=0 if not maxstable)      */
};


/** @internal
** @brief MSER: extremal region */
typedef struct _MserExtrReg MserExtrReg;

/* ----------------------------------------------------------------- */


/** @internal
** @brief MSER filter
** @see @ref mser
**/
struct _MserFilt
{
    /** @name Image data and meta data @internal */
    /*@{*/
    int    ndims;          /**< number of dimensions                    */
    int    *dims;          /**< dimensions                              */
    int    nel;            /**< number of image elements (pixels)       */
    int    *subs;          /**< N-dimensional subscript                 */
    int    *dsubs;         /**< another subscript                       */
    int    *strides;       /**< strides to move in image data           */
                        /*@}*/

    unsigned int    *perm;  /**< pixel ordering                          */
    unsigned int    *joins; /**< sequence of join ops                    */
    int        njoins; /**< number of join ops                      */

                    /** @name Regions */
                    /*@{*/
    MserReg        *r;     /**< basic regions                           */
    MserExtrReg    *er;    /**< extremal tree                           */
    unsigned int    *mer;   /**< maximally stable extremal regions       */
    int        ner;    /**< number of extremal regions              */
    int        nmer;   /**< number of maximally stable extr. reg.   */
    int        rer;    /**< size of er buffer                       */
    int        rmer;   /**< size of mer buffer                      */
                    /*@}*/

                    /** @name Ellipsoids fitting */
                    /*@{*/
    float    *acc;           /**< moment accumulator.                    */
    float    *ell;           /**< ellipsoids list.                       */
    int    rell;           /**< size of ell buffer                     */
    int    nell;           /**< number of ellipsoids extracted         */
    int    dof;            /**< number of dof of ellipsoids.           */

                        /*@}*/

                        /** @name Configuration */
                        /*@{*/
    int    verbose;        /**< be verbose                             */
    int    delta;          /**< delta filter parameter                 */
    float    max_area;       /**< badness test parameter                 */
    float    min_area;       /**< badness test parameter                 */
    float    max_variation;  /**< badness test parameter                 */
    float    min_diversity;  /**< minimum diversity                      */
                            /*@}*/

    MserStats stats;        /** run statistic                           */
};

/* ----------------------------------------------------------------- */


/** @brief Get delta
** @param f MSER filter.
** @return value of @c delta.
**/
unsigned char
mser_get_delta(MserFilt const *f)
{
    return(f->delta);
}


/** @brief Set delta
** @param f MSER filter.
** @param x value of @c delta.
**/
void
mser_set_delta(MserFilt *f, unsigned char x)
{
    f->delta = x;
}


/* ----------------------------------------------------------------- */


/** @brief Get minimum diversity
** @param  f MSER filter.
** @return value of @c minimum diversity.
**/
float
mser_get_min_diversity(MserFilt const *f)
{
    return(f->min_diversity);
}


/** @brief Set minimum diversity
** @param f MSER filter.
** @param x value of @c minimum diversity.
**/
void
mser_set_min_diversity(MserFilt *f, float x)
{
    f->min_diversity = x;
}


/* ----------------------------------------------------------------- */


/** @brief Get statistics
** @param f MSER filter.
** @return statistics.
**/
MserStats const*
mser_get_stats(MserFilt const *f)
{
    return(&f->stats);
}


/* ----------------------------------------------------------------- */


/** @brief Get maximum region area
** @param f MSER filter.
** @return maximum region area.
**/
float
mser_get_max_area(MserFilt const *f)
{
    return(f->max_area);
}


/** @brief Set maximum region area
** @param f MSER filter.
** @param x maximum region area.
**/
void
mser_set_max_area(MserFilt *f, float x)
{
    f->max_area = x;
}


/* ----------------------------------------------------------------- */


/** @brief Get minimum region area
** @param f MSER filter.
** @return minimum region area.
**/
float
mser_get_min_area(MserFilt const *f)
{
    return(f->min_area);
}


/** @brief Set minimum region area
** @param f MSER filter.
** @param x minimum region area.
**/
void
mser_set_min_area(MserFilt *f, float x)
{
    f->min_area = x;
}


/* ----------------------------------------------------------------- */


/** @brief Get maximum region variation
** @param f MSER filter.
** @return maximum region variation.
**/
float
mser_get_max_variation(MserFilt const *f)
{
    return(f->max_variation);
}


/** @brief Set maximum region variation
** @param f MSER filter.
** @param x maximum region variation.
**/
void
mser_set_max_variation(MserFilt *f, float x)
{
    f->max_variation = x;
}


/* ----------------------------------------------------------------- */


/** @brief Get maximally stable extremal regions
** @param f MSER filter.
** @return array of MSER pivots.
**/
unsigned int const *
mser_get_regions(MserFilt const* f)
{
    return(f->mer);
}


/** @brief Get number of maximally stable extremal regions
** @param f MSER filter.
** @return number of MSERs.
**/
unsigned int
mser_get_regions_num(MserFilt const* f)
{
    return(f->nmer);
}


/* ----------------------------------------------------------------- */


/** @brief Get ellipsoids
** @param f MSER filter.
** @return ellipsoids.
**/
float const *
mser_get_ell(MserFilt const* f)
{
    return(f->ell);
}


/** @brief Get number of degrees of freedom of ellipsoids
** @param f MSER filter.
** @return number of degrees of freedom.
**/
unsigned int
mser_get_ell_dof(MserFilt const* f)
{
    return(f->dof);
}


/** @brief Get number of ellipsoids
** @param f MSER filter.
** @return number of ellipsoids
**/
unsigned int
mser_get_ell_num(MserFilt const* f)
{
    return(f->nell);
}


/*MSER */


/** -------------------------------------------------------------------
** @brief Advance N-dimensional subscript
**
** The function increments by one the subscript @a subs indexing an
** array the @a ndims dimensions @a dims.
**
** @param ndims number of dimensions.
** @param dims dimensions.
** @param subs subscript to advance.
**/

void adv(int ndims, int const *dims, int *subs)
{
    int d = 0;
    while (d < ndims)
    {
        if (++subs[d] < dims[d])
            return;
        subs[d++] = 0;
    }
}


/** -------------------------------------------------------------------
** @brief Climb the region forest to reach aa root
**
** The function climbs the regions forest @a r starting from the node
** @a idx to the corresponding root.
**
** To speed-up the operation, the function uses the
** MserReg::shortcut field to quickly jump to the root. After the
** root is reached, all the used shortcut are updated.
**
** @param r regions' forest.
** @param idx stating node.
** @return index of the reached root.
**/

unsigned int climb(MserReg* r, unsigned int idx)
{
    unsigned int    prev_idx = idx;
    unsigned int    next_idx;
    unsigned int    root_idx;

    /* move towards root to find it */
    while (1)
    {
        /* next jump to the root */
        next_idx = r[idx].shortcut;

        /* recycle shortcut to remember how we came here */
        r[idx].shortcut = prev_idx;

        /* stop if the root is found */
        if (next_idx == idx)
            break;

        /* next guy */
        prev_idx = idx;
        idx = next_idx;
    }

    root_idx = idx;

    /* move backward to update shortcuts */
    while (1)
    {
        /* get previously visited one */
        prev_idx = r[idx].shortcut;

        /* update shortcut to point to the new root */
        r[idx].shortcut = root_idx;

        /* stop if the first visited node is reached */
        if (prev_idx == idx)
            break;

        /* next guy */
        idx = prev_idx;
    }

    return(root_idx);
}


/** -------------------------------------------------------------------
** @brief Create a new MSER filter
**
** Initializes a new MSER filter for images of the specified
** dimensions. Images are @a ndims -dimensional arrays of dimensions
** @a dims.
**
** @param ndims number of dimensions.
** @param dims  dimensions.
**/

MserFilt*
mser_new(int ndims, int const* dims)
{
    MserFilt* f = (MserFilt *)calloc(sizeof(MserFilt), 1);

    f->ndims = ndims;
    f->dims = (int *)malloc(sizeof(int) * ndims);
    f->subs = (int *)malloc(sizeof(int) * ndims);
    f->dsubs = (int *)malloc(sizeof(int) * ndims);
    f->strides = (int *)malloc(sizeof(int) * ndims);
    /* shortcuts */
    if (f->dims != NULL && f->subs != NULL && f->dsubs != NULL && f->strides != NULL)
    {
        int k = 0;

        /* copy dims to f->dims */
        memcpy(f->dims, dims, sizeof(int) * ndims);

        /* compute strides to move into the N-dimensional image array */
        f->strides[0] = 1;
        for (k = 1; k < ndims; ++k)
        {
            f->strides[k] = f->strides[k - 1] * dims[k - 1];
        }

        /* total number of pixels */
        f->nel = f->strides[ndims - 1] * dims[ndims - 1];

        /* dof of ellipsoids */
        f->dof = ndims * (ndims + 1) / 2 + ndims;

        /* more buffers */
        f->perm = (unsigned int *)malloc(sizeof(unsigned int) * f->nel);
        f->joins = (unsigned int *)malloc(sizeof(unsigned int) * f->nel);
        f->r = (MserReg *)malloc(sizeof(MserReg) * f->nel);

        f->er = 0;
        f->rer = 0;
        f->mer = 0;
        f->rmer = 0;
        f->ell = 0;
        f->rell = 0;

        /* other parameters */
        f->delta = 5;
        f->max_area = 0.75f;
        f->min_area = 3.0f / f->nel;
        f->max_variation = 0.25f;
        f->min_diversity = 0.2f;
    }
    return(f);
}


/** -------------------------------------------------------------------
** @brief Delete MSER filter
**
** The function releases the MSER filter @a f and all its resources.
**
** @param f MSER filter to be deleted.
**/

void
mser_delete(MserFilt* f)
{
    if (f)
    {
        if (f->acc)
            free(f->acc);
        if (f->ell)
            free(f->ell);

        if (f->er)
            free(f->er);
        if (f->r)
            free(f->r);
        if (f->joins)
            free(f->joins);
        if (f->perm)
            free(f->perm);

        if (f->strides)
            free(f->strides);
        if (f->dsubs)
            free(f->dsubs);
        if (f->subs)
            free(f->subs);
        if (f->dims)
            free(f->dims);

        if (f->mer)
            free(f->mer);
        free(f);
    }
}


#define MAX( x, y ) ( ( (x) > (y) ) ? (x) : (y) )


/** -------------------------------------------------------------------
** @brief Process image
**
** The functions calculates the Maximally Stable Extremal Regions
** (MSERs) of image @a im using the MSER filter @a f.
**
** The filter @a f must have been initialized to be compatible with
** the dimensions of @a im.
**
** @param f MSER filter.
** @param im image data.
**/

void
mser_process(MserFilt* f, unsigned char const* im)
{
    /* shortcuts */
    unsigned int    nel = f->nel;
    unsigned int    *perm = f->perm;
    unsigned int    *joins = f->joins;
    int        ndims = f->ndims;
    int        *dims = f->dims;
    int        *subs = f->subs;
    int        *dsubs = f->dsubs;
    int        *strides = f->strides;
    MserReg        *r = f->r;
    MserExtrReg    *er = f->er;
    unsigned int    *mer = f->mer;
    int        delta = f->delta;

    int    njoins = 0;
    int    ner = 0;
    int    nmer = 0;
    int    nbig = 0;
    int    nsmall = 0;
    int    nbad = 0;
    int    ndup = 0;

    int i, j, k;

    /* delete any previosuly computed ellipsoid */
    f->nell = 0;


    /* -----------------------------------------------------------------
    *                                          Sort pixels by intensity
    * -------------------------------------------------------------- */

    {
        unsigned int buckets[MSER_PIX_MAXVAL];

        /* clear buckets */
        memset(buckets, 0, sizeof(unsigned int) * MSER_PIX_MAXVAL);


        /* compute bucket size (how many pixels for each intensity
        * value) */
        for (i = 0; i < (int)nel; ++i)
        {
            unsigned char v = im[i];
            ++buckets[v];
        }

        /* cumulatively add bucket sizes */
        for (i = 1; i < MSER_PIX_MAXVAL; ++i)
        {
            buckets[i] += buckets[i - 1];
        }

        /* empty buckets computing pixel ordering */
        for (i = nel; i >= 1; )
        {
            unsigned char    v = im[--i];
            unsigned int    j = --buckets[v];
            perm[j] = i;
        }
    }

    /* initialize the forest with all void nodes */
    for (i = 0; i < (int)nel; ++i)
    {
        r[i].parent = MSER_VOID_NODE;
    }


    /* -----------------------------------------------------------------
    *                        Compute regions and count extremal regions
    * -------------------------------------------------------------- */


    /*
    * In the following:
    * idx    : index of the current pixel
    * val    : intensity of the current pixel
    * r_idx  : index of the root of the current pixel
    * n_idx  : index of the neighbors of the current pixel
    * nr_idx : index of the root of the neighbor of the current pixel
    */

    /* process each pixel by increasing intensity */
    for (i = 0; i < (int)nel; ++i)
    {
        /* pop next node xi */
        unsigned int    idx = perm[i];
        unsigned char    val = im[idx];
        unsigned int    r_idx;

        /* add the pixel to the forest as a root for now */
        r[idx].parent = idx;
        r[idx].shortcut = idx;
        r[idx].area = 1;
        r[idx].height = 1;

        r_idx = idx;


        /* convert the index IDX into the subscript SUBS; also initialize
        * DSUBS to (-1,-1,...,-1) */
        {
            unsigned int temp = idx;
            for (k = ndims - 1; k >= 0; --k)
            {
                dsubs[k] = -1;
                subs[k] = temp / strides[k];
                temp = temp % strides[k];
            }
        }

        /* examine the neighbors of the current pixel */
        while (1)
        {
            unsigned int    n_idx = 0;
            int        good = 1;


            /*
            * Compute the neighbor subscript as NSUBS+SUB, the
            * corresponding neighbor index NINDEX and check that the
            * neighbor is within the image domain.
            */
            for (k = 0; k < ndims && good; ++k)
            {
                int temp = dsubs[k] + subs[k];
                good &= (0 <= temp) && (temp < dims[k]);
                n_idx += temp * strides[k];
            }


            /*
            * The neighbor should be processed if the following conditions
            * are met:
            * 1. The neighbor is within image boundaries.
            * 2. The neighbor is indeed different from the current node
            * (the opposite happens when DSUB=(0,0,...,0)).
            * 3. The neighbor is already in the forest, meaning that it has
            * already been processed.
            */
            if (good &&
                n_idx != idx &&
                r[n_idx].parent != MSER_VOID_NODE)
            {
                unsigned char    nr_val = 0;
                unsigned int    nr_idx = 0;
                int        hgt = r[r_idx].height;
                int        n_hgt = r[nr_idx].height;


                /*
                * Now we join the two subtrees rooted at
                * R_IDX = ROOT(  IDX)
                * NR_IDX = ROOT(N_IDX).
                * Note that R_IDX = ROOT(IDX) might change as we process more
                * neighbors, so we need keep updating it.
                */

                r_idx = climb(r, idx);
                nr_idx = climb(r, n_idx);


                /*
                * At this point we have three possibilities:
                * (A) ROOT(IDX) == ROOT(NR_IDX). In this case the two trees
                * have already been joined and we do not do anything.
                * (B) I(ROOT(IDX)) == I(ROOT(NR_IDX)). In this case the pixel
                * IDX is extending an extremal region with the same
                * intensity value. Since ROOT(NR_IDX) will NOT be an
                * extremal region of the full image, ROOT(IDX) can be
                * safely added as children of ROOT(NR_IDX) if this
                * reduces the height according to the union rank
                * heuristic.
                * (C) I(ROOT(IDX)) > I(ROOT(NR_IDX)). In this case the pixel
                * IDX is starting a new extremal region. Thus ROOT(NR_IDX)
                * WILL be an extremal region of the final image and the
                * only possibility is to add ROOT(NR_IDX) as children of
                * ROOT(IDX), which becomes parent.
                */

                if (r_idx != nr_idx) /* skip if (A) */

                {
                    nr_val = im[nr_idx];

                    if (nr_val == val && hgt < n_hgt)
                    {
                        /* ROOT(IDX) becomes the child */
                        r[r_idx].parent = nr_idx;
                        r[r_idx].shortcut = nr_idx;
                        r[nr_idx].area += r[r_idx].area;
                        r[nr_idx].height = MAX(n_hgt, hgt + 1);

                        joins[njoins++] = r_idx;
                    }
                    else {
                        /* cases ROOT(IDX) becomes the parent */
                        r[nr_idx].parent = r_idx;
                        r[nr_idx].shortcut = r_idx;
                        r[r_idx].area += r[nr_idx].area;
                        r[r_idx].height = MAX(hgt, n_hgt + 1);

                        joins[njoins++] = nr_idx;

                        /* count if extremal */
                        if (nr_val != val)
                            ++ner;
                    }       /* check b vs c */
                }               /* check a vs b or c */
            }                       /* neighbor done */

                                    /* move to next neighbor */
            k = 0;
            while (++dsubs[k] > 1)
            {
                dsubs[k++] = -1;
                if (k == ndims)
                    goto done_all_neighbors;
            }
        } /* next neighbor */
    done_all_neighbors:;
    }        /* next pixel */

             /* the last root is extremal too */
    ++ner;

    /* save back */
    f->njoins = njoins;

    f->stats.num_extremal = ner;


    /* -----------------------------------------------------------------
    *                                          Extract extremal regions
    * -------------------------------------------------------------- */


    /*
    * Extremal regions are extracted and stored into the array ER.  The
    * structure R is also updated so that .SHORTCUT indexes the
    * corresponding extremal region if any (otherwise it is set to
    * VOID).
    */

    /* make room */
    if (f->rer < ner)
    {
        if (er)
            free(er);
        f->er = er = (MserExtrReg *)malloc(sizeof(MserExtrReg) * ner);
        f->rer = ner;
    }
    ;

    /* save back */
    f->nmer = ner;

    /* count again */
    ner = 0;

    /* scan all regions Xi */
    if (er != NULL)
    {
        for (i = 0; i < (int)nel; ++i)
        {
            /* pop next node xi */
            unsigned int idx = perm[i];

            unsigned char    val = im[idx];
            unsigned int    p_idx = r[idx].parent;
            unsigned char    p_val = im[p_idx];

            /* is extremal ? */
            int is_extr = (p_val > val) || idx == p_idx;

            if (is_extr)
            {
                /* if so, add it */
                er[ner].index = idx;
                er[ner].parent = ner;
                er[ner].value = im[idx];
                er[ner].area = r[idx].area;

                /* link this region to this extremal region */
                r[idx].shortcut = ner;

                /* increase count */
                ++ner;
            }
            else {
                /* link this region to void */
                r[idx].shortcut = MSER_VOID_NODE;
            }
        }
    }


    /* -----------------------------------------------------------------
    *                                   Link extremal regions in a tree
    * -------------------------------------------------------------- */

    for (i = 0; i < ner; ++i)
    {
        unsigned int idx = er[i].index;

        do
        {
            idx = r[idx].parent;
        } while (r[idx].shortcut == MSER_VOID_NODE);

        er[i].parent = r[idx].shortcut;
        er[i].shortcut = i;
    }


    /* -----------------------------------------------------------------
    *                            Compute variability of +DELTA branches
    * -------------------------------------------------------------- */


    /* For each extremal region Xi of value VAL we look for the biggest
    * parent that has value not greater than VAL+DELTA. This is dubbed
    * `top parent'. */

    for (i = 0; i < ner; ++i)
    {
        /* Xj is the current region the region and Xj are the parents */
        int    top_val = er[i].value + delta;
        int    top = er[i].shortcut;

        /* examine all parents */
        while (1)
        {
            int    next = er[top].parent;
            int    next_val = er[next].value;


            /* Break if:
            * - there is no node above the top or
            * - the next node is above the top value.
            */
            if (next == top || next_val > top_val)
                break;

            /* so next could be the top */
            top = next;
        }

        /* calculate branch variation */
        {
            int    area = er[i].area;
            int    area_top = er[top].area;
            er[i].variation = (float)(area_top - area) / area;
            er[i].max_stable = 1;
        }


        /* Optimization: since extremal regions are processed by
        * increasing intensity, all next extremal regions being processed
        * have value at least equal to the one of Xi. If any of them has
        * parent the parent of Xi (this comprises the parent itself), we
        * can safely skip most intermediate node along the branch and
        * skip directly to the top to start our search. */
        {
            int    parent = er[i].parent;
            int    curr = er[parent].shortcut;
            er[parent].shortcut = MAX(top, curr);
        }
    }


    /* -----------------------------------------------------------------
    *                                  Select maximally stable branches
    * -------------------------------------------------------------- */

    nmer = ner;
    for (i = 0; i < ner; ++i)
    {
        unsigned int    parent = er[i].parent;
        unsigned char    val = er[i].value;
        float        var = er[i].variation;
        unsigned char    p_val = er[parent].value;
        float        p_var = er[parent].variation;
        unsigned int    loser;


        /*
        * Notice that R_parent = R_{l+1} only if p_val = val + 1. If not,
        * this and the parent region coincide and there is nothing to do.
        */
        if (p_val > val + 1)
            continue;

        /* decide which one to keep and put that in loser */
        if (var < p_var)
            loser = parent;
        else loser = i;

        /* make loser NON maximally stable */
        if (er[loser].max_stable)
        {
            --nmer;
            er[loser].max_stable = 0;
        }
    }

    f->stats.num_unstable = ner - nmer;


    /* -----------------------------------------------------------------
    *                                                 Further filtering
    * -------------------------------------------------------------- */


    /* It is critical for correct duplicate detection to remove regions
    * from the bottom (smallest one first).                          */
    {
        float    max_area = (float)f->max_area * nel;
        float    min_area = (float)f->min_area * nel;
        float    max_var = (float)f->max_variation;
        float    min_div = (float)f->min_diversity;

        /* scan all extremal regions (intensity value order) */
        for (i = ner - 1; i >= 0L; --i)
        {
            /* process only maximally stable extremal regions */
            if (!er[i].max_stable)
                continue;

            if (er[i].variation >= max_var)
            {
                ++nbad;   goto remove;
            }
            if (er[i].area > max_area)
            {
                ++nbig;   goto remove;
            }
            if (er[i].area < min_area)
            {
                ++nsmall; goto remove;
            }


            /*
            * Remove duplicates
            */
            if (min_div < 1.0)
            {
                unsigned int    parent = er[i].parent;
                int        area, p_area;
                float        div;

                /* check all but the root mser */
                if ((int)parent != i)
                {
                    /* search for the maximally stable parent region */
                    while (!er[parent].max_stable)
                    {
                        unsigned int next = er[parent].parent;
                        if (next == parent)
                            break;
                        parent = next;
                    }


                    /* Compare with the parent region; if the current and parent
                    * regions are too similar, keep only the parent. */
                    area = er[i].area;
                    p_area = er[parent].area;
                    div = (float)(p_area - area) / (float)p_area;

                    if (div < min_div)
                    {
                        ++ndup; goto remove;
                    }
                } /* remove dups end */
            }
            continue;
        remove:
            er[i].max_stable = 0;
            --nmer;
        }         /* check next region */

        f->stats.num_abs_unstable = nbad;
        f->stats.num_too_big = nbig;
        f->stats.num_too_small = nsmall;
        f->stats.num_duplicates = ndup;
    }


    /* -----------------------------------------------------------------
    *                                                   Save the result
    * -------------------------------------------------------------- */

    /* make room */
    if (f->rmer < nmer)
    {
        if (mer)
            free(mer);
        f->mer = mer = (unsigned int *)malloc(sizeof(unsigned int) * nmer);
        f->rmer = nmer;
    }

    /* save back */
    f->nmer = nmer;

    j = 0;
    if (er != NULL && mer != NULL)
    {
        for (i = 0; i < ner; ++i)
        {
            if (er[i].max_stable)
                mer[j++] = er[i].index;
        }
    }
}


/** -------------------------------------------------------------------
** @brief Fit ellipsoids
**
** @param f MSER filter.
**
** @sa @ref mser-ell
**/


void
mser_ell_fit(MserFilt* f)
{
    /* shortcuts */
    int        nel = f->nel;
    int        dof = f->dof;
    int        *dims = f->dims;
    int        ndims = f->ndims;
    int        *subs = f->subs;
    int        njoins = f->njoins;
    unsigned int    *joins = f->joins;
    MserReg        *r = f->r;
    unsigned int    *mer = f->mer;
    int        nmer = f->nmer;
    mser_acc    *acc = f->acc;
    mser_acc    *ell = f->ell;

    int d, index, i, j;

    /* already fit ? */
    if (f->nell == f->nmer)
        return;

    /* make room */
    if (f->rell < f->nmer)
    {
        if (f->ell)
            free(f->ell);
        f->ell = (float *)malloc(sizeof(float) * f->nmer * f->dof);
        f->rell = f->nmer;
    }

    if (f->acc == 0)
    {
        f->acc = (float *)malloc(sizeof(float) * f->nel);
    }

    acc = f->acc;
    ell = f->ell;


    /* -----------------------------------------------------------------
    *                                                 Integrate moments
    * -------------------------------------------------------------- */

    /* for each dof */
    for (d = 0; d < f->dof; ++d)
    {
        /* start from the upper-left pixel (0,0,...,0) */
        memset(subs, 0, sizeof(int) * ndims);

        /* step 1: fill acc pretending that each region has only one pixel */
        if (d < ndims)
        {
            /* 1-order ................................................... */

            for (index = 0; index < nel; ++index)
            {
                acc[index] = (float)subs[d];
                adv(ndims, dims, subs);
            }
        }
        else {
            /* 2-order ................................................... */

            /* map the dof d to a second order moment E[x_i x_j] */
            i = d - ndims;
            j = 0;
            while (i > j)
            {
                i -= j + 1;
                j++;
            }
            /* initialize acc with  x_i * x_j */
            for (index = 0; index < nel; ++index)
            {
                acc[index] = (float)(subs[i] * subs[j]);
                adv(ndims, dims, subs);
            }
        }

        /* step 2: integrate */
        for (i = 0; i < njoins; ++i)
        {
            unsigned int    index = joins[i];
            unsigned int    parent = r[index].parent;
            acc[parent] += acc[index];
        }

        /* step 3: save back to ellpises */
        for (i = 0; i < nmer; ++i)
        {
            unsigned int idx = mer[i];
            ell[d + dof * i] = acc[idx];
        }
    } /* next dof */


      /* -----------------------------------------------------------------
      *                                           Compute central moments
      * -------------------------------------------------------------- */

    for (index = 0; index < nmer; ++index)
    {
        float        *pt = ell + index * dof;
        unsigned int    idx = mer[index];
        float        area = (float)r[idx].area;

        for (d = 0; d < dof; ++d)
        {
            pt[d] /= area;

            if (d >= ndims)
            {
                /* remove squared mean from moment to get variance */
                i = d - ndims;
                j = 0;
                while (i > j)
                {
                    i -= j + 1;
                    j++;
                }
                pt[d] -= pt[i] * pt[j];
            }
        }
    }

    /* save back */
    f->nell = nmer;
}

 

void drawEllipse(const float * region, int width, int height, int depth, unsigned char*  bits, const uint8_t * color)
{
    /* Centroid (mean) */
    const float    x = region[0];
    const float    y = region[1];

    /* Covariance matrix [a b; b c] */
    const float    a = region[2];
    const float    b = region[3];
    const float    c = region[4];

    /* Eigenvalues of the covariance matrix */
    const float    d = a + c;
    const float    e = a - c;
    const float    f = sqrtf(4.0f * b * b + e * e);
    const float    e0 = (d + f) / 2.0f;       /* First eigenvalue */
    const float    e1 = (d - f) / 2.0f;       /* Second eigenvalue */

                                           /* Desired norm of the eigenvectors */
    const float    e0sq = sqrtf(e0);
    const float    e1sq = sqrtf(e1);

    /* Eigenvectors */
    float    v0x = e0sq;
    float    v0y = 0.0f;
    float    v1x = 0.0f;
    float    v1y = e1sq;

    if (b)
    {
        v0x = e0 - c;
        v0y = b;
        v1x = e1 - c;
        v1y = b;

        /* Normalize the eigenvectors */
        const float n0 = e0sq / sqrtf(v0x * v0x + v0y * v0y);
        v0x *= n0;
        v0y *= n0;

        const float n1 = e1sq / sqrtf(v1x * v1x + v1y * v1y);
        v1x *= n1;
        v1y *= n1;
    }

    for (float t = 0.0f; t < 2.0f * M_PI; t += 0.001f)
    {
        int    x2 = (int)(x + (cosf(t) * v0x + sinf(t) * v1x) * 2.0f + 0.5f);
        int    y2 = (int)(y + (cosf(t) * v0y + sinf(t) * v1y) * 2.0f + 0.5f);

        if ((x2 >= 0) && (x2 < width) && (y2 >= 0) && (y2 < height))
            for (int i = 0; i < min(depth, 3); ++i)
                bits[(y2 * width + x2) * depth + i] = color[i];
    }
}


/** @brief MSER driver entry point
**/
int
main(int argc, char **argv)
{
    /* algorithm parameters */
    float    delta = 2;
    float    max_area = 0.5f;
    float    min_area = 0.0001f;
    float    max_variation = 0.5f;
    float    min_diversity = 0.33f;
    int    dark_on_bright = 1;

    bool        err = false;
    char        err_msg[1024];
    int        exit_code = 0;
    MserFilt    *filt = 0;
    MserFilt    *filtinv = 0;

    unsigned int const    *regions;
    unsigned int const    *regionsinv;
    float const        *frames;
    float const        *framesinv;
    enum { ndims = 2 };
    int    dims[ndims];
    int    nregions = 0, nregionsinv = 0, nframes = 0, nframesinv = 0;
    int    i, dof;

    if (argc != 3)
    {
        fprintf
        (stderr,
            "Usage: %s input.jpg output.jpg\n",
            argv[0]);
        return(-1);
    }
    char    * inputfile = argv[1];
    char    * outputfile = argv[2];

    int        width;
    int        height;
    int        depth;
    unsigned char    * data = loadImage(inputfile, &width, &height, &depth);

    unsigned char *datainv = NULL;
    if (!data)
    {
        err = false;
        snprintf(err_msg, sizeof(err_msg),
            "Could not allocate enough memory.");
        goto done;
    }
    dims[0] = width;
    dims[1] = height;

    filt = mser_new(ndims, dims);
    filtinv = mser_new(ndims, dims);

    if (!filt || !filtinv)
    {
        snprintf(err_msg, sizeof(err_msg),
            "Could not create an MSER filter.");
        goto done;
    }

    if (delta >= 0)
        mser_set_delta(filt, (unsigned char)delta);
    if (max_area >= 0)
        mser_set_max_area(filt, max_area);
    if (min_area >= 0)
        mser_set_min_area(filt, min_area);
    if (max_variation >= 0)
        mser_set_max_variation(filt, max_variation);
    if (min_diversity >= 0)
        mser_set_min_diversity(filt, min_diversity);
    if (delta >= 0)
        mser_set_delta(filtinv, (unsigned char)delta);
    if (max_area >= 0)
        mser_set_max_area(filtinv, max_area);
    if (min_area >= 0)
        mser_set_min_area(filtinv, min_area);
    if (max_variation >= 0)
        mser_set_max_variation(filtinv, max_variation);
    if (min_diversity >= 0)
        mser_set_min_diversity(filtinv, min_diversity);


    printf("mser: parameters:\n");
    printf("mser:   delta         = %d\n", mser_get_delta(filt));
    printf("mser:   max_area      = %g\n", mser_get_max_area(filt));
    printf("mser:   min_area      = %g\n", mser_get_min_area(filt));
    printf("mser:   max_variation = %g\n", mser_get_max_variation(filt));
    printf("mser:   min_diversity = %g\n", mser_get_min_diversity(filt));

    if (dark_on_bright)
    {
        double startTime = now();
        mser_process(filt, (unsigned char *)data);
        double nProcessTime = calcElapsed(startTime, now());
        printf("Elapsed: %d ms \n ", (int)(nProcessTime * 1000));
        /* Save result  ----------------------------------------------- */
        nregions = mser_get_regions_num(filt);
        regions = mser_get_regions(filt);

        printf("nregions: %d \t", nregions); 

        /*
        * for (i = 0; i < nregions; ++i) {
        * printf(" %d \t", regions[i]);
        * }
        */
        mser_ell_fit(filt);

        nframes = mser_get_ell_num(filt);
        dof = mser_get_ell_dof(filt);

        printf("dof: %d \t", dof);
        printf("nframes: %d \t", nframes);
        /* Draw ellipses in the original image */
        const uint8_t colors[3] = { 127, 127, 127 };
        for (int x = 0; x < 2; ++x)
        {
            frames = mser_get_ell(filt);
            for (i = 0; i < nframes; ++i)
            {
                drawEllipse(frames, width, height, depth, data, colors);
                frames += dof;
            }
        }
        saveJpeg(outputfile, width, height, depth, data);
    }
    else {
        /* allocate buffer */
        datainv = (unsigned char *)malloc(width * height * depth);
        for (i = 0; i < width * height * depth; i++)
        {
            datainv[i] = ~data[i]; /* 255 - data[i] */
        }

        if (!datainv)
        {
            err = false;
            snprintf(err_msg, sizeof(err_msg),
                "Could not allocate enough memory.");
            goto done;
        }
        double startTime = now();
        mser_process(filtinv, (unsigned char *)datainv);
        double nProcessTime = calcElapsed(startTime, now());
        printf("Elapsed: %d ms \n ", (int)(nProcessTime * 1000));
        /* Save result  ----------------------------------------------- */
        nregionsinv = mser_get_regions_num(filtinv);
        regionsinv = mser_get_regions(filtinv);


        /*
        * for (i = 0; i < nregionsinv; ++i) {
        * printf("%d \t ", -regionsinv[i]);
        * }
        */

        mser_ell_fit(filtinv);

        nframesinv = mser_get_ell_num(filtinv);
        dof = mser_get_ell_dof(filtinv);


        const uint8_t colors[3] = { 0, 0, 0 };

        framesinv = mser_get_ell(filtinv);
        for (i = 0; i < nframesinv; ++i)
        {
            drawEllipse(framesinv, width, height, depth, data, colors);
            framesinv += dof;
        }
        saveJpeg(outputfile, width, height, depth, data);
    }

    /* Next guy  ----------------------------------------------- */
done:
    /* release filter */
    if (filt)
    {
        mser_delete(filt);
        filt = 0;
    }
    if (filtinv)
    {
        mser_delete(filtinv);
        filtinv = 0;
    }

    /* release image data */
    if (data)
    {
        free(data);
        data = 0;
    }
    if (datainv)
    {
        free(datainv);
        datainv = 0;
    }

    /* if bad print error message */
    if (err)
    {
        fprintf
        (stderr,
            "mser: err: %s (%d)\n",
            err_msg,
            err);
        exit_code = 1;
    }
    /* quit */
    return(exit_code);
}

算法有两种模式,白底黑字,白字黑底,可根据具体需求进行开关。

可参照《图片文档倾斜矫正算法 附完整c代码》中判断是否为文本图片的方式进行算法思路的改进。

效果图例:

mser 最大稳定极值区域(文字区域定位)算法 附完整C代码

mser 最大稳定极值区域(文字区域定位)算法 附完整C代码

mser 最大稳定极值区域(文字区域定位)算法 附完整C代码mser 最大稳定极值区域(文字区域定位)算法 附完整C代码

以上,再一次抛砖引玉。

若有其他相关问题或者需求也可以邮件联系俺探讨。

邮箱地址是: 
gaozhihan@vip.qq.com