Revisiting graph-cut segmentation with SLIC and color histograms [w/Python]

As part of the computer vision class I'm teaching at SBU I asked students to implement a segmentation method based on SLIC superpixels. Here is my boilerplate implementation.

This follows the work I've done a very long time ago (2010) on the same subject.

For graph-cut I've used PyMaxflow:, which is very easily installed by just pip install PyMaxflow

The method is simple:

  • Calculate SLIC superpixels (the SKImage implementation)
  • Use markings to determine the foreground and background color histograms (from the superpixels under the markings)
  • Setup a graph with a straightforward energy model: Smoothness term = K-L-Div between superpix histogram and neighbor superpix histogram, and Match term = inf if marked as BG or FG, or K-L-Div between SuperPix histogram and FG and BG.
  • To find neighbors I've used Delaunay tessellation (from scipy.spatial), for simplicity. But a full neighbor finding could be implemented by looking at all the neighbors on the superpix's boundary.
  • Color histograms are 2D over H-S (from the HSV)



Using Hidden Markov Models for staff line removal (in OMR) [w/code]

So lately I'm into Optical Music Recognition (OMR), and a central part of that is doing staff line removal. That is when you get rid of the staff lines that obscure the musical symbols to make recognition much easier. There are a lot of ways to do it, but I'm going to share with you how I did it (fairly easily) with Hidden Markov Models (HMMs), which will also teach us a good lesson on this wonderfully useful approach.

OMR has been around for ages, and if you're interested in learning about it [Fornes 2014] and [Rebelo 2012] are good summary articles.
The matter of Staff Line Removal has occupied dozens of researchers for as long as OMR exists; [Dalitz 2008] give a good overview. Basically the goal is to remove the staff lines that obscure the musical symbols, so they would be easier to recognize.
Screen Shot 2015-01-24 at 10.11.00 PM
But, the staff lines are connected to the symbols, so simply removing them will cut up the symbols and make them hardly recognizable.
So let's see how we could do this with HMMs.
Continue reading "Using Hidden Markov Models for staff line removal (in OMR) [w/code]"


Bust out your own graphcut based image segmentation with OpenCV [w/ code]

This is a tutorial on using Graph-Cuts and Gaussian-Mixture-Models for image segmentation with OpenCV in C++ environment.

Update 10/30/2017: See a new implementation of this method using OpenCV-Python, PyMaxflow, SLIC superpixels, Delaunay and other tricks.

Been wokring on my masters thesis for a while now, and the path of my work came across image segmentation. Naturally I became interested in Max-Flow Graph Cuts algorithms, being the "hottest fish in the fish-market" right now if the fish market was the image segmentation scene.

So I went looking for a CPP implementation of graphcut, only to find out that OpenCV already implemented it in v2.0 as part of their GrabCut impl. But I wanted to explore a bit, so I found this implementation by Olga Vexler, which is build upon Kolmogorov's framework for max-flow algorithms. I was also inspired by Shai Bagon's usage example of this implementation for Matlab.

Let's jump in...
Continue reading "Bust out your own graphcut based image segmentation with OpenCV [w/ code]"


Extending Justin Talbot's GrabCut Impl [w/ code]

Justin Talbot has done a tremendous job implementing the GrabCut algorithm in C [link to paper, link to code]. I was missing though, the option to load ANY kind of file, not just PPMs and PGMs.
So I tweaked the code a bit to receive a filename and determine how to load it: use the internal P[P|G]M loaders, or offload the work to the OpenCV image loaders that take in many more type. If the OpenCV method is used, the IplImage is converted to the internal GrabCut code representation.

Image<Color>* load( std::string file_name )
 if( file_name.find( ".pgm" ) != std::string::npos )
 return loadFromPGM( file_name );

 else if( file_name.find( ".ppm" ) != std::string::npos )
 return loadFromPPM( file_name );

 return loadOpenCV(file_name);

void fromImageMaskToIplImage(const Image<Real>* image, IplImage* ipli) {
 for(int x=0;x<image->width();x++) {
 for(int y=0;y<image->height();y++) {
 //Color c = (*image)(x,y);
 Real r = (*image)(x,y);
 CvScalar s = cvScalarAll(0);
 if(r == 0.0) {
 s.val[0] = 255.0;
 cvSet2D(ipli,ipli->height - y - 1,x,s);

Image<Color>* loadIplImage(IplImage* im) {
 Image<Color>* image = new Image<Color>(im->width, im->height);
 for(int x=0;x<im->width;x++) {
 for(int y=0;y<im->height;y++) {
 CvScalar v = cvGet2D(im,im->height-y-1,x);
 Real R, G, B;
 R = (Real)((unsigned char)v.val[2])/255.0f;
 G = (Real)((unsigned char)v.val[1])/255.0f;
 B = (Real)((unsigned char)v.val[0])/255.0f;
 (*image)(x,y) = Color(R,G,B);
 return image;

Image<Color>* loadOpenCV(std::string file_name) {
 IplImage* im = cvLoadImage(file_name.c_str(),1);
 Image<Color>* i = loadIplImage(im);
 return i;

Well, there's nothing fancy here, but it does give you a fully working GrabCut implementation on top of OpenCV... so there's the contribution.

GrabCutNS::Image<GrabCutNS::Color>* imageGC = GrabCutNS::loadIplImage(orig);
 GrabCutNS::Image<GrabCutNS::Color>* maskGC = GrabCutNS::loadIplImage(mask);

 GrabCutNS::GrabCut *grabCut = new GrabCutNS::GrabCut( imageGC );

 IplImage* __GCtmp = cvCreateImage(cvSize(orig->width,orig->height),8,1);

I also added the GrabCutNS namespace, to differentiate the Image class from the rest of the code (that probably has an Image already).

Code is as usual available online in the SVN repo.