Skip to content

Instantly share code, notes, and snippets.

@gylns

gylns/detect_mser.cpp

Created July 5, 2017 14:57
Show Gist options
  • Save gylns/10ddce082dca917e6d1902272a13092f to your computer and use it in GitHub Desktop.
Save gylns/10ddce082dca917e6d1902272a13092f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
detect_mser.cpp
#include "mser.hpp"
#include <opencv2/imgcodecs.hpp>
#include <opencv2/highgui.hpp>
#include <vector>
#include <iostream>
using namespace std;
using namespace cv;
vector<Point> selectPoints(const String &video_name, const Mat &frame)
{
struct Data
{
vector<Point> points;
static void mouseHandler(int event, int x, int y, int flags, void *param)
{
Data *data = (Data*)param;
switch (event)
{
// start to select the bounding box
case EVENT_LBUTTONDOWN:
data->points.push_back(Point(x, y));
break;
// update the selected bounding box
case EVENT_MOUSEMOVE:
break;
// cleaning up the selected bounding box
case EVENT_LBUTTONUP:
break;
case EVENT_RBUTTONDOWN:
data->points.clear();
break;
}
}
} data;
namedWindow(video_name);
setMouseCallback(video_name, Data::mouseHandler, &data);
while (waitKey(10) != ' ')
{
Mat draw;
cvtColor(frame, draw, CV_GRAY2BGR);
for (const auto& it : data.points)
circle(draw, it, 2, Scalar(0, 255, 0));
imshow(video_name, draw);
}
destroyWindow(video_name);
return data.points;
}
int main(int argc, char *argv[])
{
Mat imgOrig, img;
cv::CommandLineParser parser(argc, argv, "{ @input | | }");
vector<Point> seeds;
string input = parser.get<string>("@input");
if (!input.empty())
{
imgOrig = imread(input, IMREAD_GRAYSCALE);
imgOrig.copyTo(img);
}
else
{
cerr << "Usage: " << argv[0] << " input_image" << endl;
return 1;
}
seeds = selectPoints("MSER", img);
Mat result(img.rows, img.cols, CV_8UC3);
cvtColor(img, result, CV_GRAY2BGR);
MSERFeat::Params para;
if (img.cols <= 100 && img.rows <= 100)
para.maxArea = img.cols * img.rows / 2;
else
para.maxArea = 5000;
try
{
// We can detect regions using detectRegions method
vector<Rect> zone;
vector<vector <Point> > region;
MSERFeat erf(para);
erf.detectRegions(img, region, zone,seeds);
int i = 0;
int nbPixelInMSER = 0;
for (vector<vector <Point> >::iterator itr = region.begin(); itr != region.end(); ++itr, ++i)
{
Mat m = Mat::zeros(img.size(), img.type());
m = 255;
for (vector <Point>::iterator itp = region[i].begin(); itp != region[i].end(); ++itp)
{
// all pixels belonging to region become blue
result.at<Vec3b>(itp->y, itp->x) = Vec3b(128, 0, 0);
m.at<uchar>(itp->y, itp->x) = img.at<uchar>(itp->y, itp->x);
nbPixelInMSER++;
}
}
cout << "Number of MSER region " << region.size() << " Number of pixels in all MSER region : " << nbPixelInMSER << "\n";
namedWindow("MSER", WINDOW_AUTOSIZE);
imshow("MSER", result);
}
catch (Exception& e)
{
cout << e.msg << endl;
}
waitKey();
return 0;
}
Raw
mser.hpp
/* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
* Redistributions of source code must retain the above
* copyright notice, this list of conditions and the following
* disclaimer.
* Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
* The name of Contributor may not be used to endorse or
* promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
* OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
* OF SUCH DAMAGE.
* Copyright© 2009, Liu Liu All rights reserved.
*
* OpenCV functions for MSER extraction
*
* 1. there are two different implementation of MSER, one for gray image, one for color image
* 2. the gray image algorithm is taken from: Linear Time Maximally Stable Extremal Regions;
* the paper claims to be faster than union-find method;
* it actually get 1.5~2m/s on my centrino L7200 1.2GHz laptop.
* 3. the color image algorithm is taken from: Maximally Stable Colour Regions for Recognition and Match;
* it should be much slower than gray image method ( 3~4 times );
* the chi_table.h file is taken directly from paper's source code which is distributed under GPL.
* 4. though the name is *contours*, the result actually is a list of point set.
*/
#include <limits>
#include <opencv2/imgproc.hpp>
#include <opencv2/highgui.hpp>
namespace cv
{
using std::stringstream;
using std::vector;
class MSERFeat
{
public:
struct Params
{
Params(int _delta = 5, int _min_area = 60, int _max_area = 14400,
double _max_variation = 0.25, double _min_diversity = .2)
{
delta = _delta;
minArea = _min_area;
maxArea = _max_area;
maxVariation = _max_variation;
minDiversity = _min_diversity;
pass2Only = false;
}
int delta;
int minArea;
int maxArea;
double maxVariation;
double minDiversity;
bool pass2Only;
};
explicit MSERFeat(const Params& _params) : params(_params) {}
virtual ~MSERFeat() {}
void setDelta(int delta) { params.delta = delta; }
int getDelta() const { return params.delta; }
void setMinArea(int minArea) { params.minArea = minArea; }
int getMinArea() const { return params.minArea; }
void setMaxArea(int maxArea) { params.maxArea = maxArea; }
int getMaxArea() const { return params.maxArea; }
void setPass2Only(bool f) { params.pass2Only = f; }
bool getPass2Only() const { return params.pass2Only; }
enum { DIR_SHIFT = 29, NEXT_MASK = ((1 << DIR_SHIFT) - 1) };
struct Pixel
{
Pixel() : val(0) {}
Pixel(int _val) : val(_val) {}
int getGray(const Pixel* ptr0, const uchar* imgptr0, int mask) const
{
return imgptr0[this - ptr0] ^ mask;
}
int getNext() const { return (val & NEXT_MASK); }
void setNext(int next) { val = (val & ~NEXT_MASK) | next; }
int getDir() const { return (int)((unsigned)val >> DIR_SHIFT); }
void setDir(int dir) { val = (val & NEXT_MASK) | (dir << DIR_SHIFT); }
bool isVisited() const { return (val & ~NEXT_MASK) != 0; }
int val;
};
typedef int PPixel;
struct WParams
{
Params p;
vector<vector<Point> >* msers;
vector<Rect>* bboxvec;
Pixel* pix0;
int step;
Mat img;
vector<PPixel> seeds;
};
// the history of region grown
struct CompHistory
{
CompHistory()
{
parent_ = child_ = next_ = 0;
val = size = 0;
var = -1.f;
head = 0;
checked = false;
isMSER = false;
bbox_ = Rect();
}
void updateTree(WParams& wp, CompHistory** _h0, CompHistory** _h1, bool force)
{
if (var >= 0.f)
return;
int delta = wp.p.delta;
CompHistory* h0_ = 0, *h1_ = 0;
CompHistory* c = child_;
if (size >= wp.p.minArea)
{
for (; c != 0; c = c->next_)
{
if (c->var < 0.f)
c->updateTree(wp, c == child_ ? &h0_ : 0, c == child_ ? &h1_ : 0, force);
if (c->var < 0.f)
return;
}
}
// find h0 and h1 such that:
// h0->val >= h->val - delta and (h0->parent == 0 or h0->parent->val < h->val - delta)
// h1->val <= h->val + delta and (h1->child == 0 or h1->child->val < h->val + delta)
// then we will adjust h0 and h1 as h moves towards latest
CompHistory* h0 = this, *h1 = h1_ && h1_->size > size ? h1_ : this;
if (h0_)
{
for (h0 = h0_; h0 != this && h0->val < val - delta; h0 = h0->parent_)
;
}
else
{
for (; h0->child_ && h0->child_->val >= val - delta; h0 = h0->child_)
;
}
for (; h1->parent_ && h1->parent_->val <= val + delta; h1 = h1->parent_)
;
if (_h0) *_h0 = h0;
if (_h1) *_h1 = h1;
// when we do not well-defined ER(h->val + delta), we stop
// the process of computing variances unless we are at the final step
if (!force && !h1->parent_ && h1->val < val + delta)
return;
var = (float)(h1->size - h0->size) / size;
c = child_;
for (; c != 0; c = c->next_)
c->checkAndCapture(wp);
if (force && !parent_)
checkAndCapture(wp);
}
void checkAndCapture(WParams& wp)
{
if (checked)
return;
checked = true;
if (size < wp.p.minArea || size > wp.p.maxArea || var < 0.f || var > wp.p.maxVariation)
return;
if (child_)
{
CompHistory* c = child_;
for (; c != 0; c = c->next_)
{
if (c->var >= 0.f && var > c->var)
return;
}
}
if (var > 0.f && parent_ && parent_->var >= 0.f && var >= parent_->var)
return;
int j = 0;
wp.msers->push_back(vector<Point>());
vector<Point>& region = wp.msers->back();
region.resize(size);
const Pixel* pix0 = wp.pix0;
int step = wp.step;
for (PPixel pix = head; j < size; j++, pix = pix0[pix].getNext())
{
int y = pix / step;
int x = pix - y*step;
region[j] = Point(x, y);
}
wp.bboxvec->push_back(bbox_);
isMSER = true;
}
CompHistory* child_;
CompHistory* parent_;
CompHistory* next_;
int val;
int size;
float var;
PPixel head;
bool checked;
bool isMSER;
Rect bbox_;
};
struct ConnectedComp
{
ConnectedComp()
{
init(0);
}
void init(int gray)
{
head = tail = 0;
history = 0;
size = 0;
gray_level = gray;
xmin = ymin = INT_MAX;
xmax = ymax = INT_MIN;
}
// add history chunk to a connected component
void growHistory(CompHistory*& hptr, WParams& wp, int new_gray_level, bool final)
{
if (new_gray_level < gray_level)
new_gray_level = gray_level;
CompHistory *h;
if (history && history->val == gray_level)
{
h = history;
}
else
{
h = hptr++;
h->parent_ = 0;
h->child_ = history;
h->next_ = 0;
if (history)
{
history->parent_ = h;
}
}
h->val = gray_level;
h->size = size;
h->head = head;
h->var = FLT_MAX;
h->checked = true;
h->isMSER = false;
if (h->size > 0)
{
h->bbox_ = Rect(xmin, ymin, xmax - xmin + 1, ymax - ymin + 1);
}
if (h->size >= wp.p.minArea)
{
h->var = -1.f;
h->checked = false;
}
gray_level = new_gray_level;
history = h;
if (history && history->val != gray_level)
{
history->updateTree(wp, 0, 0, final);
}
}
// merging two connected components
void merge(ConnectedComp* comp1, ConnectedComp* comp2,
CompHistory*& hptr, WParams& wp)
{
if (comp1->gray_level < comp2->gray_level)
std::swap(comp1, comp2);
gray_level = comp1->gray_level;
comp1->growHistory(hptr, wp, gray_level, false);
comp2->growHistory(hptr, wp, gray_level, false);
if (comp1->size == 0)
{
head = comp2->head;
tail = comp2->tail;
xmin = comp2->xmin;
xmax = comp2->xmax;
ymin = comp2->ymin;
ymax = comp2->ymax;
}
else
{
head = comp1->head;
wp.pix0[comp1->tail].setNext(comp2->head);
tail = comp2->tail;
xmin = std::min(comp1->xmin, comp2->xmin);
ymin = std::min(comp1->ymin, comp2->ymin);
xmax = std::max(comp1->xmax, comp2->xmax);
ymax = std::max(comp1->ymax, comp2->ymax);
}
size = comp1->size + comp2->size;
history = comp1->history;
CompHistory *h1 = history->child_;
CompHistory *h2 = comp2->history;
// the child_'s size should be the large one
if (h1 && h1->size > h2->size)
{
// add h2 as a child only if its size is large enough
if (h2->size >= wp.p.minArea)
{
h2->next_ = h1->next_;
h1->next_ = h2;
}
}
else
{
history->child_ = h2;
// reserve h1 as a child only if its size is large enough
if (h1 && h1->size >= wp.p.minArea)
{
h2->next_ = h1;
}
}
h2->parent_ = history;
}
PPixel head;
PPixel tail;
CompHistory* history;
int gray_level;
int size;
int xmin, ymin;
int xmax, ymax;
vector<PPixel> seeds;
};
void detectRegions(InputArray image,
std::vector<std::vector<Point> >& msers,
std::vector<Rect>& bboxes, vector<Point> seeds = vector<Point>());
void preprocess1(const Mat& img, int* level_size)
{
memset(level_size, 0, 256 * sizeof(level_size[0]));
int i, j, cols = img.cols, rows = img.rows;
int step = cols;
pixbuf.resize(step*rows);
heapbuf.resize(cols*rows + 256);
histbuf.resize(cols*rows);
pixHist.resize(cols*rows);
Pixel borderpix;
borderpix.setDir(5);
for (j = 0; j < step; j++)
{
pixbuf[j] = pixbuf[j + (rows - 1)*step] = borderpix;
pixHist[j] = pixHist[j + (rows - 1)*step] = 0;
}
for (i = 1; i < rows - 1; i++)
{
const uchar* imgptr = img.ptr(i);
Pixel* pptr = &pixbuf[i*step];
CompHistory **histptr = &pixHist[i*step];
pptr[0] = pptr[cols - 1] = borderpix;
histptr[0] = histptr[cols - 1] = 0;
for (j = 1; j < cols - 1; j++)
{
int val = imgptr[j];
level_size[val]++;
pptr[j].val = 0;
histptr[j] = 0;
}
}
}
void preprocess2(const Mat& img, int* level_size)
{
int i;
for (i = 0; i < 128; i++)
std::swap(level_size[i], level_size[255 - i]);
if (!params.pass2Only)
{
int j, cols = img.cols, rows = img.rows;
int step = cols;
for (i = 1; i < rows - 1; i++)
{
Pixel* pptr = &pixbuf[i*step];
CompHistory **histptr = &pixHist[i*step];
for (j = 1; j < cols - 1; j++)
{
pptr[j].val = 0;
histptr[j] = 0;
}
}
}
}
void pass(const Mat& img, vector<vector<Point> >& msers, vector<Rect>& bboxvec,
Size size, const int* level_size, int mask, vector<Point> seeds = vector<Point>())
{
CompHistory* histptr = &histbuf[0];
int step = size.width;
Pixel *ptr0 = &pixbuf[0], *ptr = &ptr0[step + 1];
const uchar* imgptr0 = img.ptr();
Pixel** heap[256];
ConnectedComp comp[257];
ConnectedComp* comptr = &comp[0];
ConnectedComp* seedComp = 0;
WParams wp;
wp.p = params;
wp.msers = &msers;
wp.bboxvec = &bboxvec;
wp.pix0 = ptr0;
wp.step = step;
wp.img = img ^ mask;
heap[0] = &heapbuf[0];
heap[0][0] = 0;
for (int i = 1; i < 256; i++)
{
heap[i] = heap[i - 1] + level_size[i - 1] + 1;
heap[i][0] = 0;
}
comptr->gray_level = 256;
comptr++;
comptr->gray_level = ptr->getGray(ptr0, imgptr0, mask);
ptr->setDir(1);
int dir[] = { 0, 1, step, -1, -step };
for (;;)
{
int curr_gray = ptr->getGray(ptr0, imgptr0, mask);
int nbr_idx = ptr->getDir();
// take tour of all the 4 directions
for (; nbr_idx <= 4; nbr_idx++)
{
// get the neighbor
Pixel* ptr_nbr = ptr + dir[nbr_idx];
if (!ptr_nbr->isVisited())
{
// set dir=1, next=0
ptr_nbr->val = 1 << DIR_SHIFT;
int nbr_gray = ptr_nbr->getGray(ptr0, imgptr0, mask);
if (nbr_gray < curr_gray)
{
// 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
*(++heap[curr_gray]) = ptr;
ptr->val = (nbr_idx + 1) << DIR_SHIFT;
ptr = ptr_nbr;
comptr++;
comptr->init(nbr_gray);
curr_gray = nbr_gray;
nbr_idx = 0;
continue;
}
// otherwise, push the neighbor to boundary heap
*(++heap[nbr_gray]) = ptr_nbr;
}
}
// set dir = nbr_idx, next = 0
ptr->val = nbr_idx << DIR_SHIFT;
int ptrofs = (int)(ptr - ptr0);
CV_Assert(ptrofs != 0);
// add a pixel to the pixel list
if (comptr->tail)
ptr0[comptr->tail].setNext(ptrofs);
else
comptr->head = ptrofs;
comptr->tail = ptrofs;
comptr->size++;
// update the bbox
{
int y = ptrofs / step;
int x = ptrofs - y*step;
comptr->xmin = std::min(comptr->xmin, x);
comptr->xmax = std::max(comptr->xmax, x);
comptr->ymin = std::min(comptr->ymin, y);
comptr->ymax = std::max(comptr->ymax, y);
}
comptr->seeds.push_back(ptrofs);
// get the next pixel from boundary heap
if (*heap[curr_gray])
{
ptr = *heap[curr_gray];
heap[curr_gray]--;
}
else
{
for (curr_gray++; curr_gray < 256; curr_gray++)
{
if (*heap[curr_gray])
break;
}
if (curr_gray >= 256)
break;
ptr = *heap[curr_gray];
heap[curr_gray]--;
if (curr_gray < comptr[-1].gray_level)
{
comptr->growHistory(histptr, wp, curr_gray, false);
CV_DbgAssert(comptr->size == comptr->history->size);
for (const auto& it: comptr->seeds)
{
CV_DbgAssert(pixHist[it] == 0);
pixHist[it] = comptr->history;
CV_DbgAssert(pixHist[it]->val == pixbuf[it].getGray(ptr0, imgptr0, mask));
}
comptr->seeds.clear();
}
else
{
// there must one pixel with the second component's gray level in the heap,
// so curr_gray is not large than the second component's gray level
comptr--;
CV_DbgAssert(curr_gray == comptr->gray_level);
comptr->merge(comptr, comptr + 1, histptr, wp);
CV_DbgAssert(curr_gray == comptr->gray_level);
for (const auto& it : (comptr+1)->seeds)
{
CV_DbgAssert(pixHist[it] == 0);
pixHist[it] = (comptr+1)->history;
CV_DbgAssert(pixHist[it]->val == pixbuf[it].getGray(ptr0, imgptr0, mask));
}
(comptr+1)->seeds.clear();
}
}
}
for (; comptr->gray_level != 256; comptr--)
{
comptr->growHistory(histptr, wp, 256, true);
}
for (const auto& it : seeds)
{
wp.seeds.push_back(it.y*step + it.x);
}
drawERs(img, mask, wp.seeds, ptr0);
}
void drawERs(const Mat& img, int mask, const vector<PPixel>& seeds, Pixel *ptr0)
{
if (seeds.size() > 0)
{
vector<CompHistory *> seedComps;
vector<CompHistory *> drawHists;
seedComps.resize(seeds.size());
for (int i = 0; i < seeds.size(); i++)
{
seedComps[i] = pixHist[seeds[i]];
}
sort(seedComps.begin(), seedComps.end(), [](CompHistory *a, CompHistory *b) {
if (b == 0) return true;
else if (a == 0) return false;
else return a->val < b->val;
});
bool paused = false;
for (;;)
{
Mat drawImg = img ^ mask;
cvtColor(drawImg, drawImg, CV_GRAY2BGR);
bool drawed = false;
for (auto it = drawHists.begin(); it != drawHists.end();)
{
if ((*it) && (*it)->parent_ == seedComps[0])
it = drawHists.erase(it);
else
it++;
}
drawHists.push_back(seedComps[0]);
for (auto& pHist : drawHists)
{
if (pHist == 0)
continue;
drawed = true;
stringstream ss;
PPixel pp = pHist->head;
for (int i = 0; i < pHist->size; i++)
{
int y = pp / img.cols;
int x = pp - y*img.cols;
if (!pHist->isMSER)
drawImg.at<Vec3b>(y, x) = Vec3b(0, 255, 0);
else
drawImg.at<Vec3b>(y, x) = Vec3b(0, 0, 255);
Pixel p = ptr0[pp];
pp = p.getNext();
}
rectangle(drawImg, pHist->bbox_, Scalar(0, 255, 255));
if (seeds.size() == 1)
{
Mat res = Mat::zeros(30, drawImg.cols, CV_8UC3);
ss.clear();
ss.str("");
ss << "v: " << pHist->val << " s: " << pHist->size;
putText(res, ss.str(), Point(0, 10), FONT_HERSHEY_SIMPLEX, .4, Scalar(0, 255, 255));
//putText(drawImg, ss.str(), pHist->bbox_.tl() + Point(0, -10), FONT_HERSHEY_SIMPLEX, .4, Scalar(0, 0, 128));
ss.clear();
ss.str("");
ss << "var: " << pHist->var;
putText(res, ss.str(), Point(0, 25), FONT_HERSHEY_SIMPLEX, .4, Scalar(0, 255, 255));
//putText(drawImg, ss.str(), pHist->bbox_.tl(), FONT_HERSHEY_SIMPLEX, .4, Scalar(0, 0, 128));
vector<Mat> matrices = { drawImg, res };
vconcat(matrices, drawImg);
}
}
imshow("MSER", drawImg);
int c;
if (paused == false)
c = waitKey(200);
else
c = waitKey();
if (c == ' ')
paused = !paused;
else if (c == 'q')
break;
if (drawed == false)
break;
CompHistory *temp = seedComps[0]->parent_;
seedComps.erase(seedComps.begin());
auto it = seedComps.begin();
for (; it != seedComps.end(); it++)
{
if (*it == 0 || (temp && temp->val <= (*it)->val))
break;
}
seedComps.insert(it, temp);
}
}
}
Mat tempsrc;
vector<Pixel> pixbuf;
vector<Pixel*> heapbuf;
vector<CompHistory> histbuf;
vector<CompHistory*> pixHist;
Params params;
};
void MSERFeat::detectRegions(InputArray _src, vector<vector<Point> >& msers, vector<Rect>& bboxes, vector<Point> seeds)
{
Mat src = _src.getMat();
msers.clear();
bboxes.clear();
if (src.rows < 3 || src.cols < 3)
CV_Error(Error::StsBadArg, "Input image is too small. Expected at least 3x3");
Size size = src.size();
if (src.type() == CV_8U)
{
int level_size[256];
if (!src.isContinuous())
{
src.copyTo(tempsrc);
src = tempsrc;
}
// darker to brighter (MSER+)
preprocess1(src, level_size);
if (!params.pass2Only)
pass(src, msers, bboxes, size, level_size, 0, seeds);
// brighter to darker (MSER-)
preprocess2(src, level_size);
pass(src, msers, bboxes, size, level_size, 255, seeds);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment