Image Segmentation with boost graph

I recently discovered boost::graph. Since I have never used Graph theory before I was wondering how i would solve the following problem with boost graph.

Lets say I've got a sim开发者_如何学JAVAple(greyscale) 2D Image and I'd like to extract Regions from it which suffice a specific criterion, e.g. pixel value > threshold. Lets above is white, below is black.

How would I implement that?

My first clue was adding one single Vertex to the graph for every pixel in the image. And then connect every pixel Vertex to its neighbours with the same colour(white/black). And then I could extract regions with the connected_components() function.

Or is it more effective to connect all neighbouring pixels and encode the border information into the edge(border edge, nonborder edge)?

Actually there are some interesting graph-theory based segmentation algorithms out there, called graph-cut segmentation. They use colored edges to encode differential information between neighboring pixels.

For your very simple segmentation though using graphs at all seems overkill to me.

I would definitely do the former where you create a vertex for each pixel, and then connect pixels (or adjacent pixels depending on what you are trying to do) that share your criterion. That way you could do a "pixel-walk" to find all the areas of your image (or at least adjacent areas) that satisfy a specific criterion.

In order to find the first pixel that fits your criterion in order to start the walking sequence there are a couple methods you could use. 1) a random pick of pixels from the image, 2) save a list pointers to pixels that fit your different criteria (you only need one pixel for each criteria), or 3) save some type of gradient information on the image so that by picking just one pixel from the image, you can then search along the gradient flows to find the pixel you're looking for (i.e., the gradients would give you directional information on where you need to pick you next pixel to get closer to the desired criterion you're looking for). I would think choices 1 or 2 would be easiest to implement.

Hope this helps,

Jason