11
$\begingroup$

I was doing some reading up on image segmentation techniques and I was wondering about modern day, state-of-the-art segmentation algorithms.

What current segmentation techniques that are a 'must-read', i.e. currently most commonly used in the community? Which techniques did you came in contact with and found most effective and useful (and for which application)?

$\endgroup$
4
  • $\begingroup$ Where have you looked so far? $\endgroup$
    – Phonon
    Feb 5, 2013 at 0:34
  • 1
    $\begingroup$ I've been doing some reading on Normalized Cuts, Graph Cuts, Min Cuts in addition to Level set methods and Fast marching methods. $\endgroup$
    – GamingX
    Feb 5, 2013 at 2:54
  • 3
    $\begingroup$ Nice and short, from November 2012: Image Segmentation: A Review. $\endgroup$
    – Emre
    Feb 5, 2013 at 19:05
  • $\begingroup$ (edit inspired by this question on thresolding, maybe this question could become a similar reference to segmentation methods) $\endgroup$
    – penelope
    Oct 9, 2013 at 9:09

3 Answers 3

7
$\begingroup$

I do not know about many segmentation techniques, but I have been dealing with structures that offer a "choice" of segmentation pieces that can be further examined to produce a satisfying segmentation.

Hopefully somebody else can write about some different state-of-the-art segmentation method that I don't know much about.

A small introduction as to why it is nice to have choices, or levels, of segmentation for a different image: segmentation is an ill defined problem. The ground truth does not exist: the desired results always depend on the user requirements and specifications. A nice quote:

Even for a fixed image, there may be more than one "best" segmentation because the criteria defining the quality of a segmentation are application dependent. This motivated us to focus our research on image-partitioning techniques delivering "puzzle pieces" that can be used (...) to generate a segmentation satisfying specific user requirements

(P. Soille: Constrained Connectivity for Hierarchical Image Partitioning and Simplification (2008))

There are hierarchical structures, hierarchical image decompositions that propose image partitions with varying complexities. These structures are most simply represented as tree structures, where each node represents a region in the image. The idea with the structures:

  • the leaves of the structure are regions of a fine partition, or over-segmentation of an image (e.g. pixels, flat zones - connected regions of same intensity, watershed)
  • the links in the tree represent merging or union of (neighboring) regions and forming a more complex region, and are constructed in a way most likely to produce regions corresponding to objects (hopefully :) )
  • the complexity of the regions increases along each branch from nodes towards the root of the tree
  • every level of the tree (also, every cut) is a partitioning/segmentation of an image (coarser the closer to the root it is)
  • the root of the tree covers the whole image domain

The segmentation than consists of examining the regions and their proposed unions, to determine the regions in the tree or the cut of the tree corresponding to the required precision, or some known properties about object of interest, or other pre-defined user specifications.

Trees (that is, hierarchical image decompositions) with such properties are:

In addition to links to papers already provided, some more specific and less specific current papers on these kind of segmentation techniques:

(more practical):

$\endgroup$
2
  • 1
    $\begingroup$ For "modern" (and trendy) segmentation algorithmic families, I would add superpixels. Googling for this term is really impressive. $\endgroup$
    – sansuiso
    Oct 10, 2013 at 8:06
  • $\begingroup$ @sansuiso Well, add it as an answer :) Hopefully we can collect several interesting state-of-the-art segmentation approaches in this question $\endgroup$
    – penelope
    Oct 10, 2013 at 8:09
6
+100
$\begingroup$

As an addendum to Penelope's answer, two popular families (and trendy) of algorithms.

Superpixels

A very popular family of algorithms called Superpixels is very trendy right now (there are even some Superpixel sessions in CV conferences). Superpixels are a lot like over-segmentation (like what watershed gives you), so some post-processing is required.

Superpixels can be seen as small homogeneous images regions. The distance between pixels is evaluated as in bilateral filtering, i.e., it is a mix between their spatial distance and their visual similarity that goes to 0 when they are close and similar and to some bigger value otherwise.
Then, superpixels methods try various criteria to form small homogeneous regions with respect to this measure. There is many of them (graph-based, mode seeking / clustering based...), so I guess it's best to refer you to this tech report.

(edit:) In case somebody is looking for a published peer-reviewed work, this article is by the same authors and covers the same material as the tech report: R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Susstrunk: SLIC Superpixels Compared to State-of-the-Art Superpixel Methods

Note as I wrote the first version of the answer that visually the results is very similar to what watershed over-segmentation provides you. This is confirmed by the authors of the tech report who include watersheds in the related work part. Thus, you also need to do the same post-processing: while superpixels can be handy features to use instead of pixels, they still need to be grouped in order to form higher-level regions if you need to track / detect objects.

Graph based segmentation methods

Another popular family of algorithms comes from the analysis of pixel relationship, i.e., how pixels are close in their appearance. This yields a graph-theory based family of segmentation methods such as the normalized cut (J. Shi, J. Malik: Normalized Cuts and Image Segmentation).

Here is the intuition for this approach: suppose your pixels are now points (vertices) of an high-dimensional graph.
In the graph, two vertices can be connected by an edge, whose weight is inversely proportional to some distance between the vertices. Typically, the weight function will be some reciprocal of a mix between their spatial distance and their visual similarity 8as in bilateral filtering).
Then, given this graph, segmentation algorithms can look for the best clusters of vertices, i.e., groups of vertices that have a small intra-group distance and a large extra-group distance.

In the Normalized Cut approach, some additional care is taken in order to avoid any bias introduced by the different population sizes of the clusters. Furthermore, graph exploration can be avoided by computing the SVD of the weights matrix, also known as connectivity matrix in graph theory.

$\endgroup$
3
  • $\begingroup$ Hey, it took me a while, thanks for the answer, but... could you expand at least a tiny bit on the 2 techniques you mentioned? I don't mean explain them in detail here, but I would really appreciate one or two descriptive sentences about each of those. $\endgroup$
    – penelope
    Oct 17, 2013 at 14:02
  • $\begingroup$ I expanded the answer. It's sill a bit confusing though, the best is to refer to the tech report that I link in the answer (I have to admit that I'm not a superpixels guy and I'm still a bit skeptical about their interest, although they are really trendy). $\endgroup$
    – sansuiso
    Oct 24, 2013 at 9:21
  • $\begingroup$ For the graph based segmentation methods, I think this work suggests one of the best state of the art results: research.microsoft.com/pubs/167600/jmiv_bnm_final.pdf It is an intuitive paper and code is available. $\endgroup$ Jan 15, 2014 at 16:13
3
$\begingroup$

I guess for a global overview of the state of the art algorithms for segmentation one needs to look for the latest surveys. A good global overview with challenges are presented in Szeliski's Book.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.