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;