Some links between extremum spanning forests, watersheds and min-cuts

doi:10.1016/j.imavis.2009.06.017

Image and Vision Computing

Volume 28, Issue 10, October 2010, Pages 1460-1471

https://doi.org/10.1016/j.imavis.2009.06.017 Get rights and content

Abstract

Minimum cuts, extremum spanning forests and watersheds have been used as the basis for powerful image segmentation procedures. In this paper, we present some results about the links which exist between these different approaches. Especially, we show that extremum spanning forests are particular cases of watersheds from arbitrary markers and that min-cuts coincide with extremum spanning forests for some particular weight functions.

Introduction

Min-cuts (graph cuts) and watersheds are two popular tools for image segmentation, which can both be expressed in the framework of graphs and are well suited to computer implementations. Informally, a cut in a connected graph is a set of edges which, when removed from the graph, separates it into several connected components. Given a set of nodes or subgraphs called markers, the goal of these operators is to find a cut for which each induced component contains exactly one marker and which best matches a criterion based on the image contents. For example, the criterion is often designed in such a way that the cut is located along the contours of the objects present in the image. To this end, edges of the pixel adjacency graph can be weighted for example with the inverse of the gradient modulus. The principle of min-cut segmentation is then to find a cut (relative to the markers) whose sum of edge weights is minimal [1].

The watershed is a well-known notion from the field of topography, introduced for image segmentation purposes by Beucher and Lantuéjoul [2]. Intuitively, the watershed of a function (seen as a topographical surface) is composed by the locations from which a drop of water could flow down towards different minima. In a framework of edge-weighted graphs, the watershed is defined in [3], [4] as a cut relative to the regional minima of the weight function, and which satisfies this “drop of water” principle. In [5], Meyer shows the link between minimum spanning forests and flooding algorithms, which are most often used to compute watersheds. There is indeed an equivalence between watersheds defined as cuts satisfying the drop of water principle and cuts induced by minimum spanning forests (MinSF) relative to the minima, as proved in [3], [4].

The goal of this paper is to clarify the links between these different optimal structures used for image segmentation. For this purpose, we first give a set of definitions for these different paradigms in a same unifying framework of edge-weighted graphs. We show that the cuts induced by MinSFs are particular cases of watersheds from arbitrary markers. Furthermore, these particular cases are often preferable in practice to the watersheds. At last, we prove a property which links graph cuts and watersheds, through the notion of MinSF. It is well known that the MinSFs, and hence the watersheds, are invariant if an increasing transformation is applied simultaneously to all the weights. For example, if we raise all the weights to a same positive power n, a MinSF remains a MinSF. On the contrary, min-cuts may be different for different values of n. We show that, for any weighted graph, there exists a value n such that min-cuts coincide with cuts induced by maximum spanning forests relative to the markers, furthermore, this will also be true for any number greater than n.

The results of Section 7 of this paper were stated, without proof, in a conference paper [6]. In this conference paper, a link between MinSFs and a framework based on shortest path forests was also established. This aspect is developed in [4]. Proofs of the theorems (respectively, 6.2, 6.3 and 7.1) are given in the Appendix A Proof of, Appendix B Proof of, Appendix C Proof of.

Section snippets

Basic notions on graphs

In this section, we state basic notions on graphs before presenting the definitions of extension and cut over a graph, which will be necessary in the sequel of the paper.

We define a graph as a pair $G = (V, E)$ where V is a finite set and E is composed of unordered pairs of elements of V, precisely, E is a subset of ${{x, y} \subseteq V | x \neq y}$ . Each element of V is called a node or a vertex (of G) and each element of E is called an edge (of G). We denote by $G_{\emptyset}$ the empty graph, i.e. $G_{\emptyset} = (\emptyset, \emptyset)$ .

Let $X = (V^{'}, E^{'})$ be a

Notions on edge weighted graphs

In this section, we recall in particular the definition of a Minimum Spanning Forest (MinSF) relative to a subgraph of G.

It is shown in [4] that the problem of computing a MinSF is equivalent to the one of computing a minimum spanning tree, which has been studied for many years in combinatorial optimization (see [8], [9]).

In the following, P will denote a map from E to $R^{+}$ .

The pair $(G, P)$ is an edge weighted graph. If e is an edge of $G, P (e)$ is called the weight, or the altitude, of e. The weight

Watersheds on edge weighted graphs

The intuitive idea underlying the notion of watershed comes from the field of topography: a drop of water falling down on a topographic surface follows a descending path and reaches a regional minimum area. The watershed may be thought of as the separating lines of the domain of attraction of drops of water (see [2], [10], [11], [12]).

The regions of a watershed, also called catchment basins, are associated with the regional minima of the map. In other words, each catchment basin contains a

Watersheds relative to markers

Usually, when one wants to compute a watershed of a map, one obtains an over-segmented result since the number of regions in the final result is equal to the number of regional minima. Sometimes, it is desirable to use a set of markers instead of the minima of the map to fix the number of regions and mark some vertices with a specific label. Traditionally, to do this, one has to proceed to a morphological reconstruction of the map before computing the watershed. This reconstruction is needed on

Relations between MinSF cuts and watersheds

In this section, we recall the equivalence between MinSF cuts and watersheds relative to the minima of a map (see [3]) before describing a new theorem stating that a MinSF cut relative to any marker is a relative watershed.

Theorem 6.1

Theorem 2 in [3]

Let C be a subset of E.

The set C is a MinSF cut relative to $Min (P)$ (for P) if and only if C is a watershed (for P).

An illustration of this theorem is shown in Fig. 9.

The two following theorems lead us to the conclusion that reconstruction plus watershed can be advantageously

Link between minimum cuts (min-cuts) and MaxSF cuts

In this section, we show that min-cuts and MaxSF cuts are linked through a modification of the map P preserving the order and increasing the weight difference between the edges. Let us first recall the notion of minimum cut.

Let M be a subgraph of G and let $C \subseteq E$ . We say that C is a minimum cut (min-cut) relative to M (for P) if for any cut $C^{'} \subseteq E$ relative to M, $P (C) ⩽ P (C^{'})$ . It can be seen that a cut C relative to M is of minimum weight if and only if $\bar{C}$ is a (spanning) extension of maximum weight

Conclusion

In the framework of edge-weighted graphs, the notions of minimum spanning forest relative to the minima of a map and watershed are equivalent [3], [4]. The first contribution of this paper is to clarify the extension of this result to relative watersheds, that is, watersheds from arbitrary markers. We proved that any relative MinSF is a relative watershed, but the converse is not true. Furthermore, the relative watersheds which are not MinSFs are not interesting for usual segmentation tasks,

References (20)

F. Meyer et al.
Morphological segmentation
Journal of Visual Communication and Image Representation
(1990)
Y. Boykov et al.
Fast approximate energy minimization via graph cuts
IEEE Transactions on Pattern Analysis and Machine Intelligence
(2001)
S. Beucher, C. Lantuéjoul, Use of watersheds in contour detection, in: Proceedings of the International Workshop on...
J. Cousty, G. Bertrand, L. Najman, M. Couprie, Watershed cuts, in: Proceedings of the Eighth International Symposium on...
J. Cousty et al.
Watershed cuts: minimum spanning forests and the drop of water principle
IEEE Transactions on Pattern Analysis and Machine Intelligence
(2009)
F. Meyer, Minimum spanning forests for morphological segmentation, in: Proceedings of the Second International...
C. Allène, J.-Y. Audibert, M. Couprie, J. Cousty, R. Keriven, Some links between min-cuts, optimal spanning forests and...
G. Bertrand
On topological watersheds
Journal of Mathematical Imaging and Vision
(2005)
T.H. Cormen et al.
Introduction to Algorithms
(2001)
B. Korte et al.
Combinatorial Optimization: Theory and Algorithms
(2000)

There are more references available in the full text version of this article.

Cited by (53)

Generic parallel data structures and algorithms to GPU superpixel image segmentation
2022, Displays
Citation Excerpt :
Minimum spanning forest are special types of graph cuts. It has been shown also that a watershed is equivalent to minimum spanning forest relative to the minima of the cost function [30,44]. The intuitive idea behind watershed segmentation originates from topography [45].
We propose parallel implementation on GPU (graphics processing unit) system for some generic algorithms applied to superpixel image segmentation problem. The aim is to provide standard algorithms based on generic decentralized data structures that could be easily improved and customized on many optimization problems on parallel platforms. Note that superpixel segmentation are clustering algorithms applied to image processing. Two types of algorithms are presented and implemented on GPU based on common parallel data structures. Firstly, we present a parallel implementation of the well-known k-means algorithm with application to 3D data. It is based on a cellular grid subdivision of space that allows closest point findings in constant optimal time for bounded distributions. Secondly, we present an application of the parallel Boruvka minimum spanning forest algorithm to compute watershed segmentation. Both techniques are fully executed on GPU and share the same data structures that embed disjoint-set-trees and distributed-link-lists. We evaluate our k-means approach with regards to state-of-the-art methods, that are, the well known SLIC algorithm, and the adaptive segmentation approach SPASM. We argue that our implementation has the shortest execution time among the tested methods, with a near real time performance and quasi linear acceleration factor, while it provides more regular shape superpixel segmentation based on hexagonal tessellation. Watershed minimum spanning forest method is presented and evaluated accordingly to the same experimental framework.
Theoretical background and related works
2022, Optimum-Path Forest: Theory, Algorithms, and Applications
The Optimum-Path Forest (OPF) is a framework for the design of graph-based classifiers, which covers supervised, semisupervised, and unsupervised applications. The OPF is mainly characterized by its low training and classification times as well as competitive results against well-established machine learning techniques, such as Support Vector Machine and Artificial Neural Networks. Besides, the framework allows the design of different approaches based on the problem itself, which means a specific OPF-based classifier can be built for a given particular task. This paper surveyed several works published in the past years concerning OPF-based classifiers and sheds light on future trends concerning such a framework in the context of the deep learning era.
Optimum-Path Forest based on k-connectivity: Theory and applications
2017, Pattern Recognition Letters
Graph-based pattern recognition techniques have been in the spotlight for many years, since there is a constant need for faster and more effective approaches. Among them, the Optimum-Path Forest (OPF) framework has gained considerable attention in the last years, mainly due to the promising results obtained by OPF-based classifiers, which range from unsupervised, semi-supervised and supervised learning. In this paper, we consider a deeper theoretical explanation concerning the supervised OPF classifier with k-neighborhood (OPF_k), as well as we proposed two different training and classification algorithms that allow OPF_k to work faster. The experimental validation against standard OPF and Support Vector Machines also validates the robustness of OPF_k in real and synthetic datasets.
Improving land cover classification through contextual-based optimum-path forest
2015, Information Sciences
Traditional machine learning algorithms very often assume statistically independent data samples. However, this is clearly not the case in remote sensing image applications, in which pixels present spatial and/or temporal dependencies. In this work, it has been presented an approach to improve land cover image classification using a contextual approach based on optimum-path forest (OPF) and the well-known Markov random fields (MRFs), hereinafter called OPF–MRF. In addition, it is also introduced a framework to the optimization of the amount of contextual information used by OPF–MRF. Experiments over high- and medium-resolution satellite (CBERS-2B, Landsat 5 TM, Ikonos-2 MS and Geoeye) and radar (ALOS-PALSAR) images covering the area of two Brazilian cities have shown the proposed approach can overcome several shortcomings related to standard OPF classification. In some cases, the proposed approach outperformed traditional OPF in about 9% of recognition rate, which is crucial for land cover classification.
Interactive Segmentation with Incremental Watershed Cuts
2024, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Nature-inspired optimum-path forest
2023, Evolutionary Intelligence

View all citing articles on Scopus

View full text

Some links between extremum spanning forests, watersheds and min-cuts

Abstract

Introduction

Section snippets

Basic notions on graphs

Notions on edge weighted graphs

Watersheds on edge weighted graphs

Watersheds relative to markers

Relations between MinSF cuts and watersheds

Theorem 2 in [3]

Link between minimum cuts (min-cuts) and MaxSF cuts

Conclusion

Journal of Visual Communication and Image Representation

Fast approximate energy minimization via graph cuts

IEEE Transactions on Pattern Analysis and Machine Intelligence

Watershed cuts: minimum spanning forests and the drop of water principle

IEEE Transactions on Pattern Analysis and Machine Intelligence

On topological watersheds

Journal of Mathematical Imaging and Vision

Introduction to Algorithms

Combinatorial Optimization: Theory and Algorithms