Image Processing Reference
In-Depth Information
27.3 Sample Feature Hierarchies
Merge Trees
As shown in [
3
,
12
]the
merge tree
is ideally suited to hierarchically
encode regions of locally varying isovalues. Given a simply connected domain
M
and
a function
g
: M → R
the
level set L
(
s
)
of
g
at isovalue
s
is defined as the collection
of all points on
.A
connected component of a level set is called a
contour
.Themergetreeof
g
represents
the merging of contours as the isovalue
s
is swept top-to-bottom through the range
of
g
, see Fig.
27.1
a. Each branch of the tree represents a family of contours that
continuously evolve without merging as
s
is lowered. These contours sweep out a
subset of
R
with function value equal to
s
:
L
(
s
)
={
p
∈ M|
g
(
p
)
=
s
}
, see Fig.
27.1
a.
To increase the resolution in parameter space we refine the merge tree by splitting
long branches and refining the segmentation accordingly, see Fig.
27.1
b.
In a simple threshold-based segmentation, each branch of the tree is an ele-
ment with a lifetime given by the function values of the branch's top and bottom
nodes. Given a particular threshold, each branch acts as the representative of its sub-
tree/feature and, by construction, each subtree represents a simply connected region
of high threshold, see Fig.
27.1
c. However, when
g
spans multiple orders of mag-
nitude
relevance
[
12
] is an alternate metric that scales
g
at each node by its local
maximum—the highest maximum in its corresponding subtree. The relevance life-
time of a branch is thus given by the relevance interval between its top and bottom
node and ranges between 0 and 1, see Fig.
27.1
d. Typical examples of merge tree hier-
archies are shown in Fig.
27.2
. Figure
27.2
a shows the burning cells in a simulation
of low-swirl pre-fixed combustion [
5
]. In this applications burning cells are defined
as regions of high fuel consumption and thus the merge tree of fuel consumption
provides the appropriate segmentation. Figure
27.2
b shows extinction regions in a
turbulent simulation of non-premixed combustion. These regions are indicated by a
high scalar dissipation rate [
12
]. Since the dissipation rates spans multiple orders of
magnitude these structures are extracted using relevance as metric. Finally, Fig.
27.2
c
shows eddies in the north Atlantic ocean extracted using a split tree (the merge tree
of the negative function) of the Okubo-Weiss scalar field [
15
].
M
and thus the branches correspond to a segmentation of
M
Morse Complexes
Merge trees or in general level set based hierarchies are well
suited to encode threshold based regions. However, there exist a second, in some
sense dual, class of feature descriptions based on the gradient flow. Given a point
x
∈ M
we call a line
γ(
t
)
: R → M
, with
γ(
0
)
=
x
,the
integral line
of
x
with respect
if
∂
dt
to
g
. For each maximum
m
of
g
its
stable manifold
is defined as the set
of points whose integral lines converge to
m
[
6
]. The set of all stable manifolds forms
a segmentation of
γ
=∇
, see Fig.
27.3
. Similar to merge trees Morse complexes have
a natural hierarchical structure induced by merging neighboring stable manifolds.
However, instead of using the thresholds this hierarchy typically employs
persistence
,
the difference in function value between the lower of the two maxima and the saddle
separating them [
6
]. In this case, the life time of features always starts at 0 (since all
maxima/stable manifolds exists for 0 persistence) and ends at the persistence level
at which a stable manifolds merges with one of its neighbors. An application where
M
Search WWH ::
Custom Search