Mathematical notions

ρ (E):	the family of subsets of a set ε
	the upper bounds of the set A
	the lower bounds of the set A
∨A:	the supremum of A = the lowest upper bound of A = the smallest element of
∧A:	the infimum of A = the greatest lower bound of A = the greatest element of
Idv,Idw:	the identity operator respectively in V and W
:	the complementation operator respectively in V and W
Inv(ψ):	the family of invariants of the operator ψ, i.e. the elements a such that ψ(a) = a
Fun():	the family of functions from the domain D into the completely ordered set T
	the infimum of a family of functions
	the supremum of a family of functions

Weighted graphs

Graphs

	a graph containing a set N of nodes and a set ε of edges
p, q, r…:	nodes of the graph, elements of N
epq or (p − q)	an edge connecting p and q belonging to ε
	a directed graph containing a set N of nodes and a set of arcs
(p → q):	an arrow or arc from p to q belonging to
:	a bidirectional arrow: an arc from p to q and an arc from q to p

Subgraphs

For a graph G:
	the family of edges linking two nodes of A ⊂ N
GA = [A, EA]:	a subgraph spanned by εA
For a directed graph
	a subgraph spanned by

Partial graphs

For a graph G:	For and , a partial graph associated to a subset of edges.
For a digraph :	For a digraph or (q → p) or and a partial digraph associated with a subset of arcs.

Paths

For a graph G: For a digraph :	an undirected path from p to q
	an undirected path of origin p number of edges of the path πpq.concatenation of the two paths and
	a directed path from p to q
	a bidirectional path between p and q
	a directed path starting at p number of edges of the path concatenation of two directed paths and

Cocycles and neighborhoods

For a graph G:
−→	the cocycle of a set Y the cocycle of the node p
For a digraph	the cocycle of a set Y the cocycle of the node p

Weight distributions on the nodes or edges of a graph

Fn = Fun(N,T):	the functions defined on the nodes N for a value of T .
Fe = Fun(E,T):	the functions defined on the edges ε for a value of T .
ηpq =	the value taken by the function η ∈ Fe on the edge epq of the graph G or on the arc in
νp =	the value taken by the function ν ∈ Fn on the node p in
G(ν, η):	a node- and edge-weighted graph
G(ν, nil):	a node-weighted graph, with unweighted edges
G(nil, η):	an edge-weighted graph, with unweighted nodes
G(nil, nil):	an unweighted graph

Erosions and dilations between node and edge weights

	the weight taken by the edge eij after the erosion εen
	the weight taken by the edge eij after the dilation δen
	the weight taken by the node i afte the erosion εne
	the weight taken by the node i afte the dilation δne

Composition of operators

Gradient operators

Subtracting an erosion from a dilation produces various gradient operators:

Binary and equivalence relations

Creations of node flat zones on	equivalence relation = transitive closure of the binary relation p ∗ q the equivalence classes are the node flat zones
Creations of edge flat zones on G(nil, η):	equivalence relation = transitive closure of the binary relation epq ∼ εqr
	the equivalence classes are the edgeflat zones
Creations of even zones on G(nil, η):
	epq is a flowing edge for p and q
	equivalence relation = transitive closure of the binary relation
	the equivalence classes are the even zones

Flowing graphs

	a flowing graph obtained by cutting the non-flowing edges of G(nil, η)
	a flowing graph obtained by adding a self-loop connecting each isolated regional minimum with itself

The topography of digraphs

and have the same flowing edges and flowing paths.

	the associated flow digraphan equivalence relation
smooth zones:	the equivalence classes of
dead-end:	a smooth zone without outgoing arc
	a bidirectional path exists between p and q
flatzones:	the equivalence classes of
black hole:	the equivalence classes ofa flatzone without outgoing arc
	characterizes gravitational graphs 1 step upstream propagation of labels
	k step upstream propagation of labels
	upstream propagation of labels unti stability
	1 step downstream propagation of labels
	k step downstream propagation of labels
	downstream propagation of labels untill stability p → u and

Measuring the steepness of flowing paths

	the lexicographic order relation of length k
exists such that
	the lexicographic order relation of length ∞
	(π1,π2, …πk,πk,πk..): the series of weights of the nodes of a flowing path π
	the weights of the k first nodes of the flowing path π
	the infinite list of node weights
	the lexicographic weight of the flowing path π
	the weights of the nodes k +1 to ∞
	concatenation of lists of weights o lists of nodes
=	example of concatenation
θ(p):	steepness measure of the node p
θ(p):	the lexicographic weight of an ∞− steep path starting at p
	the k first nodes of ∞− steep path starting at p
k − steep:	a flowing path π starting at p is k −steep if
∞− steep:	a flowing path π starting at p is ∞−steep if
k − steep:	a graph is k−steep if all its flowing paths are k − steep
∞− steep:	a graph is ∞ − steep if all its flowing paths are ∞− steep

Pruning a flow digraph

	scissor operator directed erosion
	pruning of intensity n +2 decomposition of a pruning as the composition of two prunings
	the operator assigning the weight o to the black holes
	pruning propagating the value o starting from the black holes:
	the union of the directed paths tha have their origin within the set X and reduced to their first n nodes
	the union of the directed paths tha have their origin within the set X and ending in a black hole

Constructing an ∞− steep digraph by flooding

	a digraph constructed by the core expanding algorithm
	the weight νp followed by an infinite list of 0
	the infinite list of
	first-in first-out queue to contain nodes verifying
Λ:	the minimum lexicographic weighof the nodes that has neighbors
lexdist:	the lexicographic distance

Creating steep watershed partitions

	first-in first-out queue to contain nodes verifying θ1 = λi
	first-in first-out queue to contain θ1 = λi
	hierarchical queue = collection of prioritized first-in first-out queues
	a digraph for which the nodes hold the weight ν and the label

An historical intermezzo

	the geodesic distance between two pixels x and y in a domain Z
skiz(X, Z):	the skeleton by zone of influence o the family X = (Xi)i∈I of sets within the domain Z
Q:	the first-in first-out queue
(εN ν)p:	the weight of the lowest neighboring node of p

Encoding the digraph associated with an image

	the operator inverting the arcs in a digraph
	an arc exists from p to q but no arc in the other direction
S = {p | p, q ∈ N : (p → q) and	overlapping seeds=nodes with a given label, the origin of an arc towards a node with another label
	the interleaving pruning and upstream propagation of labels

Volume 2

Modeling flooding

	the function τ is an n-flooding of the graph G[ν, nil]
	the function τ is an e-flooding of the graph G[nil, η]

Lakes and regional minima

Λ_λ(nil, η): a partial subgraph of G[nil, η] defined as follows:

• – a node p belongs to Λ_λ(nil, η) if τ_p = λ;
• – an edge e_pq belongs to Λ_λ(nil, η) iff τ_p = τ_q = λ and

Creations of node flat zones on G(ν, nil):

	equivalence relation = transitive closure of the binary relation p ∗ q
	the equivalence classes are the node flat zones, an edge epq belongs to Λλ(ν, nil) iff τp = τq = λ

Among all flooding, choosing one

	the ceiling function defined on the nodes of a node- or edge-weighted graph
	the highest flooding of G[ν, nil]under the ceiling function
	the operator assigning to the function ω the dominated flooding τω of G
	the pulse function at node p, equa to ωp at node p and equal to∞ on all other nodes
τleft:	in an ordered exploration of the nodes in a graph, all nodes me before a node p
τright:	in an ordered exploration of the nodes in a graph, all nodes met afte a node

Flooding and flooding distances

χ(p, q):	the flooding distance between two nodes p and q
	the highest edge weight on the path πpq, called the section or sup section of the path in G(nil, η)
Πpq:	the family of paths linking p and qthe flooding distance in G(nil, η)
	the highest weight of the nodes belonging to πpq in G(ν, nil)
	the flooding distance in the graph G(ν, nil)

Augmented graph in G(nil, η)

Augmented graph in G(nil, η)

	the twin node of p, created if the ceiling function ω verifies that ωp < ∞, and linked with the node p by an unweighted edge
	a set of twin nodes of the set A of nodes with a finite ceiling value
	the ground level of the twin node the structure of the augmented graph

Shortest path algorithms

S:	the set of nodes whose shortes distance to Ω has been computed
	estimation is the length of theshortest path whose nodes are all included in S, with the exception of the node p
	a funnel structure
	the subset of nodes of ∂S with minimum weight

Graph flooding via dendrograms

Dendrogram structure

Ultrametric distances

χ:	partial ultrametric distance
Ball(p, ρ) = {q ∈ E | χ(p, q) ≤ ρ}:◦	a closed ball of center p and radiu ρ
◦Ball(p, ρ) = {q ∈ E | χ(p, q) < ρ}:	an open ball of center p and radiu ρ
ρB:	the radius of B
θB:	the diameter of B, i.e. the weight o the largest internal edge, connecting two nodes of B
ζB:	the weight of the edge with lowes weight in the cocycle of B, i.e. the edges with an extremity in B and the other outside
	a node of the dendrogram, i.e. a closed ball centered at a leave p
successor of ):	the lowest value of the ceiling function ω inside the closed ball p

Minimum spanning forests and watershed partitions

T (nil, η):	a minimum spanning tree of the graph G(nil, η)
Ts and Tt:	subtrees created by cutting the edge epq in T
F = Φ(G, M):	a minimum spanning forest, with trees rooted in the family M o markers (mi)
	the retraction of the graph G around the minimum spanning forest F
	a minimum spanning tree of
	a hierarchical queue structure, with Φi being a FIFO queue with priority i

Marker-based segmentation

	a flood-pruned graph obtained by suppressing the edges epq verifying τω(p) ∨ τω(q) < ηpq
	a digraph of