Project topics and materials
Get Complete Project Material File(s) Now! »
Maximum Spanning Trees and Forests
A spanning tree of a graph is a tree (a connected graph without cycles) connecting all the nodes of the graph. The weight of a spanning tree is defined by the sum of edge weights composing the tree. There exists several greedy algorithms minimizing or maximizing this weight, called respectively minimum or maximum spanning tree algorithms. Bor°uvka [28] was the first to propose an algorithm for this problem. The Prim [182], and Kruskal [144] algorithms are the most commonly used. When using a union-find data structure [207] for cycles detection, the complexity of maximum spanning tree algorithms is quasi-linear [57]. In clustering applications, at set of several maximum/minimum spanning trees may be computed, where different trees correspond to the different defined labels. The resulting set of trees is called a Maximum (or resp. Minimum) Spanning Forest. An illustration of Prim and Kruskal algorithms behavior for the construction of Maximum Spanning Forest (MSF) is given on Figure 1.7 in the context of image segmentation. The segmentation is given by the MSF cut, defined by the set of edges that separates different trees. The first appearance of such forest in image processing dates from 1986 with the work of Morris et al. [173]. It was later introduced by Meyer in a morphological context in [156]. Different criteria for regions merging appear in the literature, as for example in the widely used algorithm of Felzenszwalb et al. [95]. If the makers are located on the minima of the weight function, the cut obtained by minimum spanning forest computation was shown by Cousty et al. to be a watershed cut [77].
We shall see in Chapter 4 that these greedy procedures, which are very fast, may be used for optimizing meaningful and useful energies. The following section introduces a few convex optimization methods employed in Chapters 2 and 3.
A discrete calculus formulation
Before establishing the discrete calculus formulation of the continuous max-flow problem, we specify our notation. We refer to Section1.1 for general definitions on graphs. In this chapter, a transport graph G(V,E) comprises two additional nodes, a source s and a sink t, and additional edges linking some nodes to the sink and some to the source. Including the source and the sink nodes, the cardinalities of G are given by n = |V | and m = |E|. We define a flow through edge eij as Fij where Fij ∈ R and use the vector F ∈ Rm to denote the flows through all edges in the graph . Each edge is assumed to be oriented, such that a positive flow on edge eij indicates the direction of flow from vi to vj , while a negative flow indicates the direction of flow from vj to vi.
The incidence matrix is a key operator for defining a combinatorial formulation of the continuous max-flow problem. In our formulation of continuous max-flow, we use the expression |A| to denote the matrix formed by taking the absolute value of each entry individually. Given these definitions, we now produce a discrete (combinatorial) version of the continuous max-flow of (2.1) on a transport graph. As in [89, 113, 119], the continuous vector field indicating flows may be represented by a vector on the edge set, F. Additionally, the combinatorial divergence operator allows us to write the first constraint in (2.1) as A⊤F = 0. The second constraint in (2.1) involves the comparison of the point-wise norm of a vector field with a scalar field. Therefore, we can follow [89, 113, 119] to define the point-wise ℓ2 norm of the flow field F as p |A⊤|F2. In our notations here, as in the rest of the chapter, F2 = F · F denotes a element-wise product, “·” denoting the Hadamard (element-wise) product between the vectors, and the square root of a vector is also here and in the rest of the chapter the vector composed of the square roots of every elements.
Metrication artifacts and minimal surfaces
We begin by comparing the CCMF segmentation result with the classical max-flow algorithm (graph cuts). Figure 2.4 shows the segmentation of a brain, in which the contours obtained by graph cuts are noticeably blocky in the areas of weak gradient, while the contours obtained by both AT-CMF and CCMF are smooth. In the continuous setting, the maximum flow computed in a 3D volume produces a minimal surface. The CCMF formulation may be also recognized as a minimal surface problem. In the dual formulation, the objective function is equivalent to a weighted sum of surface nodes. In [10], Appleton and Talbot compared the surfaces obtained from their algorithm with the analytic solution of the catenoid problem to demonstrate that their algorithm was a good approximation of the continuous minimal surface and was not creating discretization artifacts. The catenoid problem arises from consideration of two circles with equal radius whose centers lie along the z axis. The minimal surface which forms to connect the two circles is known as a catenoid. The catenoid appears in nature, for example by creating a soap bubble between two rings. In order to demonstrate that CCMF is also finding a minimal surface, we performed the same catenoid experiment as was in [10]. The results are displayed in Figure 2.5, where we show that CCMF approximates the analytical solution of the catenoid with even greater fidelity than the AT-CMF example.
Table of contents :
Contents
1 Introduction
1.1 Discrete calculus
1.2 Regularization methods
1.2.1 Total variation
1.2.2 Max flow – Min cut
1.2.3 Combinatorial Dirichlet Problem
1.3 Some optimization tools
1.3.1 Combinatorial methods
1.3.1.1 Maximum Flow/Minimum cut algorithms
1.3.1.2 Shortest Path methods
1.3.1.3 Maximum Spanning Trees and Forests
1.3.2 Interior Point Method
1.3.3 Some proximal algorithms
1.3.3.1 Parallel Proximal Algorithm
1.3.3.2 M+SFBF algorithm
1.4 Manuscript organization
2 Combinatorial Continuous Maximum Flow
2.1 Introduction
2.2 Method
2.2.1 The continuous max-flow (CMF) problem
2.2.2 A discrete calculus formulation
2.2.3 The CCMF dual problem
2.2.4 Primal Dual Interior Point Method
2.3 Comparison between CCMF and existing related approaches
2.3.1 Min cut
2.3.2 Primal Dual Total variations
2.3.3 Combinatorial total variations
2.3.3.1 CCMF and CTV are not dual
2.4 Results
2.4.1 Metrication artifacts and minimal surfaces
2.4.2 Stability, convergence and speed
2.4.3 Segmentation quality
2.4.4 Extensions
2.4.4.1 Unary terms
2.4.4.2 Classification
2.4.4.3 3D segmentation
2.5 Conclusion
3 Dual Constrained TV-based regularization framework
3.1 Introduction
3.2 Graph extension of TV models
3.2.1 Considered class of constraint sets
3.3 Proposed algorithms
3.3.1 Parallel proximal algorithm (PPXA)
3.3.2 M+SFBF algorithm
3.4 Results
3.4.1 Image Denoising
3.4.1.1 Local denoising
3.4.1.2 Non local denoising
3.4.1.3 Comparison of applicability of PPXA and M+SFBF
3.4.2 Image deconvolution
3.4.3 Image fusion
3.4.4 Graph filtering
3.4.4.1 3D mesh filtering
3.4.4.2 Biologically sampled image filtering
3.5 Conclusion
4 A unifying graph-based optimization framework: Power watershed
4.1 Introduction
4.2 A short review of graph-based segmentation
4.3 A unifying energy minimization framework
4.3.1 A review of existing generalized segmentation framework
4.3.2 Broadening the framework to watershed
4.3.3 The case q finite, p → ∞ leading to watershed
4.4 Algorithm for optimizing the case q finite, p → ∞
4.4.1 Justification of the power watershed algorithm
4.4.2 Uniqueness of the solution
4.5 Results
4.5.1 Generality of the framework
4.5.1.1 Adding unary terms
4.5.1.2 Multilabel segmentation
4.5.2 Seeded segmentation
4.5.2.1 Quantitative assessment
4.5.2.2 Computation time
4.5.2.3 Qualitative assessment
4.6 Conclusion
5 Power watershed applied to filtering, stereovision and surface reconstruction
5.1 Anisotropic diffusion
5.1.1 Introduction
5.1.2 Formulation
5.1.2.1 Anisotropic diffusion and L0 norm
5.1.3 Results
5.1.4 Conclusion
5.2 Stereovision
5.3 Surface reconstruction
5.3.1 Introduction
5.3.2 Method
5.3.3 Results and comparative evaluation
5.3.3.1 Comparison with Graph cuts and Total Variation
5.3.3.2 Computation times and memory requirements
5.3.3.3 Comparison with some other approaches
5.3.4 Conclusion
6 Conclusion
6.1 Contributions
6.2 Future work
Appendix
A.1 Combinatorial continuous max flow
A.1.1 Proof of Property
A.1.2 Weak duality of CCMF and CTV
A.1.3 Algorithms for solving the CCMF problem
A.1.3.1 Parallel proximal method for solving the primal problem
A.1.3.2 First order method for solving the dual problem
A.2 Power watershed
A.2.1 The case p finite, q → ∞: Voronoi diagram
A.2.2 Illustration of Theorem 4.3.1
A.2.3 Proof of Property
A.2.4 Proof of Theorem 4.4.1
A.2.5 Interpretation as a Markov Random Field
A.2.6 Using mathematical morphology for an efficient preprocessing step
List of Figures
Index
References
