ift04

Prévia do material em texto

Image Foresting Transform
A graph-based approach to image processing
Alexandre Xavier Falcão
afalcao@ic.unicamp.br
www.ic.unicamp.br/˜afalcao/ift.html.
Institute of Computing
State University of Campinas
Campinas - SP - Brazil
A.X. Falcão – p.1/122
Contributors
Jorge Stolfi, Institute of Computing, State University of
Campinas, Campinas, SP, Brazil.
Roberto Lotufo, Faculty of Electrical and Computer
Engineering, State University of Campinas, Campinas,
SP, Brazil.
Luciano Costa, Institute of Physics, University of Sao
Paulo, Sao Carlos, SP, Brazil.
Fernando Cendes, Dept. of Neurology, Faculty of
Medical Sciences, University of Campinas, Campinas,
SP, Brazil.
Bruno Cunha, Ricardo Torres, Felipe Bergo, Gabriela
Castellano, Romaric Audigier, Celso Suzuki, Eduardo
Picado, and Carlos Camolesi.
A.X. Falcão – p.2/122
Goals of research
The design, efficient implementation, and evaluation of ef-
fective image processing operators based on connectivity.
A.X. Falcão – p.3/122
Motivation
Unification
Image operators can be derived from a single algorithm,
favoring hardware-based implementations and the
understanding of how operators relate to each other.
Efficiency
The IFT algorithm usually runs in linear time. Further
optimizations are possible for specific applications.
Simplicity
An image operator requires a simple choice of parameters of
the IFT algorithm and a local processing of its output.
A.X. Falcão – p.4/122
Purpose of the lecture
What may you expect from this lecture?
Get a different way of looking at image processing
problems.
Understand the IFT and how it works for several
applications.
Make it easier to use the C source code of the IFT
algorithm, which is available for download at
www.ic.unicamp.br/˜afalcao/ift.html.
A.X. Falcão – p.5/122
What is it all about?
Many image operators can be directly/indirectly related to a partition
of the image into influence zones associated with root pixels, where
the zone of each root consists of the pixels that are more closely
connected to that root than to any other, in some appropriate sense.
r
r
1
2
3
t
r
Pixel
�
is more closely connected to root �� .
A.X. Falcão – p.6/122
What is it all about?
The IFT unifies these image operators by computing an
optimum-path forest in a directed graph derived from the image.
The roots of the forest are drawn from a given set of seed
pixels, which may also consist of all image pixels.
The influence zone of a root � consists of the pixels reached
from � by a path of minimum cost, considering the cost of all
paths in the graph from the seed set to that pixels.
The IFT algorithm outputs three attributes for each image pixel:
an optimum path from the root set, the cost of that path, and its
corresponding root.
An image operator is reduced to a simple local processing of
these attributes.
A.X. Falcão – p.7/122
Region-based image segmentation
An object can be defined by pixels whose root belongs to a
given set of internal pixels.
A.X. Falcão – p.8/122
Image filtering
A filtered image can be obtained from the cost attribute.
A.X. Falcão – p.9/122
Optimum boundary tracking
The path attribute can be used to find an optimum curve that
is constrained to pass through a given sequence of land-
marks (pixel sets) on the object’s boundary.
A.X. Falcão – p.10/122
Euclidean distance transform (EDT)
The EDT of a given shape and its exact dilations/erosions
can be obtained from the cost attribute.
A.X. Falcão – p.11/122
Multiscale skeletonization
MS-skeletons can be obtained from the root attribute and
thresholded into one-pixel-wide and connected skeletons.
A.X. Falcão – p.12/122
Multiscale fractal dimension
0.8
0.85
0.9
0.95
1
1.05
1.1
1.15
1.2
1.25
1.3
1 1.5 2 2.5 3 3.5 4 4.5 5 5.5
Fr
ac
ta
l D
im
en
si
on
 (
F)
Log(r)
The self-similarity of a shape can be expressed in various
scales from the cost attribute.
A.X. Falcão – p.13/122
Salience points of a shape
Higher curvature points of a shape can be located from the
root attribute.
A.X. Falcão – p.14/122
Outline
Graph concepts
Images as graphs
Image Foresting Transform
The IFT algorithm
Applications
Current work
A.X. Falcão – p.15/122
Directed graphs
A directed graph is a pair
� ��� � , where � is a set of nodes
and is a set of ordered pairs of nodes.
b
i
e
a
c
dj
f
g
h
A.X. Falcão – p.16/122
Paths
A path is a sequence
�
	�� � 	�
 �� � � � 	�� � of distinct nodes in
the graph, such that
�
	�� � 	� �� � � for � � � � � � �.
A path is trivial if
� � �.
Path �
� � denotes the concatenation of two paths, � and�, where � ends at 	 and � begins at 	 .
t
τπ
Path � � � � ��� � 	 � denotes the concatenation of the
longest prefix � of � and the last arc ��� � 	 � .
A.X. Falcão – p.17/122
Path-cost functions
A path-cost function is a mapping that assigns to each
path � a cost � � � , in some ordered set ! of cost values.
A function
 
is said monotonic-incremental (MI) when
 � �
	 � � � " �
	 � � � � � ��� � 	 � � � � � � # ��� � 	 � �
where
" �
	 �
is a handicap cost value and # satisfies:$ % & $ ' $ % # �� � 	 � & $ # ��� � 	 � and $ # ��� � 	 � & $, for$ � $ % � ! and ��� � 	 � � .
A.X. Falcão – p.18/122
Examples of MI cost functions
Additive cost function
 )(* + � �
	 � � � " �
	 � � )(* + � � � ��� � 	 � � � )(* + � � �-, . ��� � 	 � �
where . ��� � 	 � is a fixed non-negative arc weight.
Max-arc cost function
 +/0 � �
	 � � � " �
	 � � +/0 � � � ��� � 	 � � � 1 23 4 +/0 � � � � . ��� � 	 �5 �
where . ��� � 	 � is a fixed arc weight.
A.X. Falcão – p.19/122
Examples of MI cost functions
b
f
e
a
c
2 1
2
3
7
64
3 0
g 3
4
5
d
1.
" ��6 � � �, +/0 � ��6 � 7 � 8 � 9 � � � : and )(* + � ��6 � 7 � 8 � 9 � � � �; .
2.
" ��6 � � <, +/0 � ��6 � 7 � 8 � 9 � � � < and )(* + � ��6 � 7 � 8 � 9 � � � � :.
A.X. Falcão – p.20/122
Predecessor map and spanning forest
A predecessor map is a function
=
that assigns to each
node
	 � � either some other node in �, or a distinctive
marker > � ? @� �— in which case 	 is the root of the map.
A spanning forest is a predecessor map which takes
every node to > � ? in a finite number of iterations (i.e. it
contains no cycles).
b
a
c
dj
i
e
f
g
h
A.X. Falcão – p.21/122
Paths of the forest
For any node
	 � �, there is a path = A �	 � which is obtained
in backward by following the predecessor nodes along the
path.
b
a
c
dj
i
e
f
g
h
For example, path
= A � 8 � � ��6 � 7 � 8 � , where = � 8 � � 7, = � 7 � � 6 ,
and
= ��6 � � > � ?; and path = A � � � � � � � , where = � � � � > � ?.
A.X. Falcão – p.22/122
Optimum-path forest
An optimum-path forest is a spanning forest
=
, where � = A �
	 � �
is minimum for all nodes
	 � �. Consider cost
function
 )(* + in the example below.
2 2
00
0
0
0
a
f d
g
e
b c
0
1
2
0
2
0
3
1
3
00
1
2
0 4
3 4
0
4
a
3b c
d
e
f
g
A.X. Falcão – p.23/122
Dijkstra’s algorithm
Dijkstra’s algorithm can be slightly modified to compute
optimum-path forests for MI cost functions.
Dijkstra’s algorithm also works for non-MI cost functions
under weaker conditions which are applied to only
optimum paths.
A.X. Falcão – p.24/122
Smooth path-cost functions
A cost function
 
is smooth if for any node
	 � �, there is an
optimum path � ending at 	 which either is trivial, or has the
form � � ��� � 	 � where
1.
 � � � � � � � ,
2. � is optimum,
3. for any optimum path � % ending at � , � � % � ��� � 	 � � � � � � .
s
t
τ
τ ’
These conditions apply to only optimum paths.
A.X. Falcão – p.25/122
An image as a directed graph
A grayscale image
B
is a pair
� ��� C � , where � is a finite
set of pixels (points in
D
) and
C
assigns to each pixel	 � � a value C �	 � in some arbitrary value space.
An adjacency relation is a binary relation between
pixels of
�
, which is usually translation-invariant.
Once has been fixed, image
B
can be interpreted as a
directedgraph, whose nodes are the image pixels in
�
and whose arcs are defined by .
A.X. Falcão – p.26/122
Examples of adjacency relations
Euclidean relation: A pixel
	 � � $
E � FE � is adjacent to a pixel� � � $ ( � F ( � (i.e. arc ��� � 	 � � ) if � $ E � $ ( �
 , � FE � F ( �
 �HG .
(A) (B)
(A) IJ K and (B) IJ LM .
A.X. Falcão – p.27/122
Examples of adjacency relations
Box-shaped relation.
Arc
�� � 	 � � if N $OE � $ ( N � /
 and N FE � F ( N � P
 .
Set-based relation.
Arc
�� � 	 � � if 	 � � � 4 � � � � � � � � � � � � � �5 .
x
y
s
(C)
A.X. Falcão – p.28/122
Connectivity relation
A pixel
	
is said connected to a pixel � if there is a path
from � to 	 in the graph.
The cost of a path in the graph is determined by an
application-specific smooth path-cost function which
usually depends on local image properties along the
path, such as brightness, gradient, and pixel position.
This notion of connectivity can be exploited in many different ways.
For example, consider the labeling of components using symmetric
connectivity relations...
A.X. Falcão – p.29/122
Labeling of components
A.X. Falcão – p.30/122
Labeling of components
For example, consider Euclidean adjacency relation withG � Q for labeling letters of a binary text;
A.X. Falcão – p.31/122
Labeling of components
Euclidean adjacency relation withG � Q < for labeling words
of a text; and
A.X. Falcão – p.32/122
Labeling of components
box-shaped adjacency relation with 6 � R; and 7 � < for
labeling lines of a text.
A.X. Falcão – p.33/122
Labeling of components
Consider now
��� � 	 � � if � $ E � $ ( �
 , � FE � F ( �
 � �; ; andN C �
	 � � C �S ��� � � N � �; ; , where S ��� � is the initial pixel of the
first path that reached � .
A.X. Falcão – p.34/122
Labeling algorithm
Input: Image
B � � � � C � and adjacency relation .
Output: Labeled image
T � � � � U � , where U �
	 � � ; initially.
Auxiliary: FIFO
V
and variable
? � � initially.
1. For all W � �, such that U � W � � ; , do
2. Set
U � W � X ? and insert W in V.
3. While
V @ � Y do
4. Remove � from V.
5. For all
	
, such that
��� � 	 � � and U �	 � � ; , do
6. Set
U �
	 � X U ��� � and insert 	 in V.
7. Set
? X ?, � .
A.X. Falcão – p.35/122
Image Foresting Transform
The IFT takes an image
Z
, a smooth path-cost function
[
and an
adjacency relation
\
; and returns an optimum-path forest
]
.
2222222222 1111111111 2222222222 5555555555 8888888888 5555555555 4444444444 5555555555
1111111111 0000000000 1111111111 4444444444 5555555555 2222222222 1111111111 2222222222
2222222222 1111111111 2222222222 5555555555 4444444444 1111111111 0000000000 1111111111
5555555555 2222222222 5555555555 8888888888 4444444444 1111111111 0000000000 1111111111
2222222222 1111111111 2222222222 5555555555 5555555555 2222222222 1111111111 2222222222
1111111111 0000000000 1111111111 4444444444 8888888888 5555555555 4444444444 5555555555
1111111111 1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 3333333333
1111111111 1111111111 1111111111 3333333333 3333333333 1111111111 1111111111 1111111111
1111111111 1111111111 1111111111 3333333333 3333333333 1111111111 1111111111 1111111111
3333333333 1111111111 3333333333 3333333333 3333333333 1111111111 1111111111 1111111111
1111111111 1111111111 1111111111 3333333333 3333333333 1111111111 1111111111 1111111111
1111111111 1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 3333333333
A
^
-connected image graph and the optimum forest for max-arc func-
tion
[`_a b with c d � e J f d � ehg K and i dkj�l � e J m f d � eon f dkj e m .
A.X. Falcão – p.36/122
Tie-breaking
The optimum-path forest
=
may not be unique, because a
pixel may be reached from two or more roots at the same
minimum cost. This ambiguity requires tie-breaking policies.
FIFO policy
Any connected set
p
of pixels with minimum cost with
respect to two or more roots tends to be equally
partitioned among the respective trees.
LIFO policy
The pixels in
p
will all get assigned to a single tree.
A.X. Falcão – p.37/122
IFT algorithm
The algorithm first identifies a root set and then
computes optimum paths within wavefronts that grow
from each root pixel.
During this process, the algorithm propagates for each
pixel
	
its predecessor
= �
	 �
in the optimum path with
terminus
	
, the cost
q �	 �
of that path, and its
corresponding root
S �	 �
.
The process stops when the wavefronts encounter each
other.
A priority queue
V
stores the pixels of the wavefronts
and controls their shapes, by favoring growth toward
directions of minimum-cost paths or according to
FIFO/LIFO policy in the case of ties.
A.X. Falcão – p.38/122
FIFO tie-breaking
Consider the max-arc function
 +/0 with " �
	 � � C �
	 � ,. ��� � 	 � � N C �
	 � � C �� � N , and a :-connected image graph.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
A.X. Falcão – p.39/122
FIFO tie-breaking
After the first iteration of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 1111111111 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
A.X. Falcão – p.40/122
FIFO tie-breaking
After the second iteration of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
1111111111 1111111111 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
A.X. Falcão – p.41/122
FIFO tie-breaking
After the third iteration of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 1111111111 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
1111111111 1111111111 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
A.X. Falcão – p.42/122
FIFO tie-breaking
After 15 iterations of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
1111111111 1111111111 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
1111111111 1111111111 3333333333 5555555555 5555555555 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 5555555555 5555555555 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 5555555555 5555555555 3333333333 1111111111 1111111111
A.X. Falcão – p.43/122
FIFO tie-breaking
The resulting optimum-path forest.
1111111111 1111111111 3333333333 3333333333 33333333333333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
A.X. Falcão – p.44/122
LIFO tie-breaking
Consider the same max-arc function
 +/0 with " �
	 � � C �
	 � ,. ��� � 	 � � N C �
	 � � C �� � N , and :-connected image graph.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
A.X. Falcão – p.45/122
LIFO tie-breaking
After the first iteration of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
A.X. Falcão – p.46/122
LIFO tie-breaking
After the second iteration of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
A.X. Falcão – p.47/122
LIFO tie-breaking
After the third iteration of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 2222222222
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 2222222222 1111111111
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
2222222222 2222222222 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
1111111111 2222222222 5555555555 5555555555 5555555555 5555555555 1111111111 1111111111
A.X. Falcão – p.48/122
LIFO tie-breaking
After 15 iterations of the algorithm.
2222222222 2222222222 5555555555 5555555555 5555555555 3333333333 1111111111 1111111111
2222222222 2222222222 5555555555 5555555555 5555555555 3333333333 1111111111 1111111111
2222222222 2222222222 5555555555 5555555555 5555555555 3333333333 1111111111 1111111111
2222222222 2222222222 5555555555 5555555555 5555555555 3333333333 1111111111 1111111111
1111111111 1111111111 5555555555 5555555555 5555555555 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 5555555555 5555555555 3333333333 1111111111 1111111111
A.X. Falcão – p.49/122
LIFO tie-breaking
The resulting optimum-path forest.
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
1111111111 1111111111 3333333333 3333333333 3333333333 3333333333 1111111111 1111111111
A.X. Falcão – p.50/122
IFT algorithm with FIFO policy
1. For all pixels
	 � � do
2.
q �
	 � X � �
	 � � , = �
	 � X > � ?, S �
	 � X 	 .
3. If
q �
	 �sr , t, insert 	 in V.
4. While
V @ � Y do
5. Remove a pixel � from V such that q ��� � is minimum.
6. For all
	
, such that
��� � 	 � � and q �	 �su q ��� � , do
7. 8 X � = A ��� � � ��� � 	 � � .
8. If 8r q �
	 � then
9. If
q �
	 � @ � , t, remove 	 from V.
10.
q �
	 � X 8, = �
	 � X � , S �
	 � X S �� � , insert 	 in V.
A.X. Falcão – p.51/122
IFT algorithm with LIFO policy
1. For all pixels
	 � � do
2.
q �
	 � X � �
	 � � , = �
	 � X > � ?, S �
	 � X 	 , insert 	 in V.
3. While
V @ � Y do
4. Remove a pixel � from V such that q ��� � is minimum.
5. For all
	
, such that
��� � 	 � � and 	 � V, do
6. 8 X � = A ��� � � ��� � 	 � � .
7. If 8 � q �
	 � then
8. Remove
	
from
V
,
q �
	 � X 8, = �
	 � X � ,S �
	 � X S ��� � , insert 	 in V.
A.X. Falcão – p.52/122
Unfair partitions with FIFO
Function
 +/0 with " �	 � � C �
	 � and . ��� � 	 � � N C �
	 � � C ��� � N .
5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555
5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555
5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555
5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555
5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555
1111111111 5555555555 5555555555 5555555555 5555555555 5555555555 5555555555 1111111111
4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444
4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444
4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444
4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444
4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444
1111111111 4444444444 4444444444 4444444444 4444444444 4444444444 4444444444 1111111111
(a) Image graph (b) Optimum forest
Other tie-breaking policies may be incorporated to the cost function.
A.X. Falcão – p.53/122
Priority queue
If
V
is a binary heap, the algorithm will run inv ��w , > xzy { > � time and v � > � storage, where w � N N
and > � N � N .
In most applications, we can find a small integer
|
such
that
 � � � ��� � 	 � � � � � � � | and � �
	 � � � � �
	 % � � � |
(excluding, t values). The cost of pixels in V will be
integers in the range
} q� � q, | ~ , for some cost q that
varies during the algorithm. Then
V
can be a circular
queue of
|, � entries; and the algorithm will run inv ��w , >, | � time and v � >, | � storage.
For small adjacency relations (sparse graphs), w >, the
algorithm will run in linear time
v � > � .
A.X. Falcão – p.54/122
Circular priority queue
C max
min
C
Q A
012
3
4
K−4
K−3
K−2
K−1
K
A.X. Falcão – p.55/122
Detection of regional minima
A regional minimum is a maximal connected set
p� �
of
same gray value, such that
C ��� � r C �
	 � for any arc ��� � 	 � �
where � � p and 	 @� p.
9999999999 9999999999 4444444444 8888888888 9999999999 2222222222 2222222222 3333333333
2222222222 2222222222 4444444444 5555555555 9999999999 0000000000 0000000000 8888888888
3333333333 3333333333 6666666666 5555555555 9999999999 3333333333 0000000000 7777777777
4444444444 4444444444 8888888888 5555555555 9999999999 9999999999 9999999999 8888888888
5555555555 5555555555 6666666666 9999999999 9999999999 9999999999 9999999999 8888888888
5555555555 5555555555 5555555555 6666666666 9999999999 9999999999 9999999999 4444444444A.X. Falcão – p.56/122
Cost function for regional minima
 � �� � �
	 � � � C �
	 � � for all 	 � �,
 � �� � � � ��� � 	 � � �
 � �� � � � � if C �� � � C �
	 � ,, t otherwise.
All image pixels are root candidates.
Any optimum path starts at a regional minimum and
never goes downhill.
A.X. Falcão – p.57/122
Regional minima with FIFO
9999999999 9999999999 4444444444 8888888888 9999999999 2222222222 2222222222 3333333333
2222222222 2222222222 4444444444 5555555555 9999999999 0000000000 0000000000 8888888888
3333333333 3333333333 6666666666 5555555555 9999999999 3333333333 0000000000 7777777777
4444444444 4444444444 8888888888 5555555555 9999999999 9999999999 9999999999 8888888888
5555555555 5555555555 6666666666 9999999999 9999999999 9999999999 9999999999 8888888888
5555555555 5555555555 5555555555 6666666666 9999999999 9999999999 9999999999 4444444444
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 4444444444
(a) Image graph (b) Optimum forest
The regional minima form the root set of the forest and each
minimum
p
is a connected component of this set.
A.X. Falcão – p.58/122
Regional minima with LIFO
9999999999 9999999999 4444444444 8888888888 9999999999 2222222222 2222222222 3333333333
2222222222 2222222222 4444444444 5555555555 9999999999 0000000000 0000000000 8888888888
3333333333 3333333333 6666666666 5555555555 9999999999 3333333333 0000000000 7777777777
4444444444 4444444444 8888888888 5555555555 9999999999 9999999999 9999999999 8888888888
5555555555 5555555555 6666666666 9999999999 9999999999 9999999999 9999999999 8888888888
5555555555 5555555555 5555555555 6666666666 9999999999 9999999999 9999999999 4444444444
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 0000000000 0000000000
2222222222 2222222222 2222222222 2222222222 0000000000 0000000000 0000000000 4444444444
(a) Image graph (b) Optimum forest
The number of minima is the number of roots, and their ex-
tent is detected by selecting the pixels
	
where
C �
	 � � C �S �
	 � � .
A.X. Falcão – p.59/122
Seed pixels
In some applications, we would like to use a smooth cost
function
 
but constrain the search to paths that start in a
given set
�� �
of seed pixels. This constraint can be
modeled by defining
 � � � � � � � � � if � starts in � �, t otherwise.
It is valid for any MI function, but not for all smooth cost
functions— in which case the IFT algorithm outputs a
non-optimum spanning forest.
A seed
	
may not become root, because there may be
another path from
�
cheaper than
�
	 �
.
A.X. Falcão – p.60/122
Region-based image segmentation
Consider an MR image
B � � � � C � of a brain, where the
object of interest is the left caudate nucleus.
A.X. Falcão – p.61/122
The IFT-watershed approach
A gradient image
� � � ��� � � obtained from B with the seeds
selected inside and outside the left caudate nucleus.
A.X. Falcão – p.62/122
Cost function for the caudate nucleus
The path-cost function can be the maximum pixel intensity
along the path.
 ��� / � � �
	 � � � C �
	 � � if 	 � �, and, t otherwise. ��� / � � � � ��� � 	 � � � 1 23 4 ��� / � � � � � C �
	 �5 �
36
4
9
0
0
0
0
0
4
3
9
6
A.X. Falcão – p.63/122
Left caudate nucleus
Result of the IFT with FIFO policy and
�
-neighborhood,
where the object was obtained from the root map
S
.
A.X. Falcão – p.64/122
Left caudate nucleus
Result of the IFT with LIFO policy and
�
-neighborhood,
where the object was obtained from the root map
S
.
A.X. Falcão – p.65/122
Differential IFT
The differential IFT (DIFT) allows to compute
sequences of IFTs in a differential way.
At each iteration, trees may be marked for deletion and
seeds added for a new dispute among the remaining
roots.
The optimum forest, costs, and roots are updated,
without running the algorithm from the beginning.
The DIFT algorithm takes time proportional to the number
of pixels whose optimum values need to be updated.
A.X. Falcão – p.66/122
Differential IFT
Tb
Tc
Tb
Tc
Td
Tb
Ta
Tc c
b
a
c d
b
c d
b
An optimum forest with trees
�a , ��� , and ��� rooted at pixels �, �, and
� (left). �a is marked for removal and � is added as seed (center).
The dispute involves
�
, �, and �, where � and � are represented by
pixels of
� � and �� along the bold and dashed lines (i.e. frontier
pixels between
�a and these trees). The new optimum forest (right).
A.X. Falcão – p.67/122
3D interactive segmentation
The DIFT algorithm has been used for multiple-object
interactive 3D segmentation of MR-brain images using
the watershed and fuzzy-connected approaches.
It has provided efficiency gains from 10 to 17 with
respect to our IFT implementations of these techniques.
It has reduced the user’s waiting time from 19–36
seconds to 2–3 seconds to visualize in 3D the results of
each iteration, using data sets of sizes 5-9Mvoxels and
an 1.1GHz Athlon PC with 384MB RAM.
A.X. Falcão – p.68/122
2D example of DIFT-watershed
Seed selection for ventricles and caudate nuclei (left). First result
shows part of the ventricles missing and part of the background as
caudate nuclei (right).
A.X. Falcão – p.69/122
2D example of DIFT-watershed
Seed selection for correction. The green region shows a single tree
marked for removal (left). Corrected segmentation (right).
A.X. Falcão – p.70/122
Segmentation from the cost map
In some situations, objects are darker/brighter than their
nearby background.
An MR image of a wrist where the bigger bone is the object of inter-
est for segmentation.
A.X. Falcão – p.71/122
Cost function for the wrist
First, suppose that the object was darker than its nearby
background. ��� / � � � � assigns to � the maximum pixel intensity along
it (i.e. once � starts in a certain gray level, its cost can
never go down).
If a single seed was selected inside the object, the
resulting cost map using
 �� / � would be darker inside
and brighter outside it.
Then, the object could be segmented by simple
thresholding.
A.X. Falcão – p.72/122
Cost function for the wrist
The dual operation applies to the case of the wrist bone
and results from the complement of the cost map obtained
by using a cost function
� ��� / � � �
	 � � � | � C �
	 � � if 	 � �, and, t otherwise.� ��� / � � � � ��� � 	 � � � 1 23 4 � ��� / � � � � � | � C �
	 �5 �
where
|
is the maximum of
C
.
A.X. Falcão – p.73/122
Bone of the wrist
Seed selection (left) and the complement of the cost map obtained
by using
�[��� a � cost function (right).
A.X. Falcão – p.74/122
Bone of the wrist
The holes within the bone (left) can be closed if we apply
the same strategy using
 �� / � cost function and one pixel of
the image border as seed (right).
A.X. Falcão – p.75/122
Bone of the wrist
The bone is segmented by thresholding the last image.
A.X. Falcão – p.76/122
Filtering by reconstruction
It is known that holes may appear in 3D renditions
whenever we use one-voxel to one-pixel projection.
A.X. Falcão – p.77/122
Filtering by reconstruction
A simple morphological closing operation using a disk of
radius
Q
(Euclidean adjacency) as structuring element
closes theholes, but also looses details.
A.X. Falcão – p.78/122
Cost function for the skull
(A) (B)
(A) The original image in blue and the closed image in (red). The
closed image is taken as a handicap cost image in the
[ �� a � function.
(B) The resulting cost map is shown in red.
A.X. Falcão – p.79/122
Cost function for the skull
The cost function becomes a simple variation of
 �� / � .
 )(� �� � �
	 � � � " �
	 � � )( � � � � � � ��� � 	 � � � 1 2 3 4 )(� �� � � � � C �
	 �5 �
where
" �	 � & C �
	 �
, for all
	 � �. The cost map q is the result
of the morphological superior reconstruction of
C
from
"
.
A.X. Falcão – p.80/122
Filtering by reconstruction
The operation is called closing by reconstruction.
A.X. Falcão – p.81/122
Filtering by reconstruction
Function
 (� �� has also a dual function, which provides
in
q
the inferior reconstruction of
C
from
"
, when" �
	 � � C �
	 �
for all
	 � �.
Together they provide many other image operators,
such as area closing/opening,leveling, closing of
basins, opening of domes, h-basins, h-domes, etc.
The root map
S
obtained from
 (� �� function is the
catchment basins of the watershed transform of
q
from
a grayscale marker
"
, when
C �	 � r " �
	 � for all 	 � �.
If we use seed pixels, the root map
S
is the catchment
basins of the watershed from markers, and marker
imposition is obtained whenever
" �
	 � r C �	 � for LIFO
policy and
" �	 � � C �
	 �
for FIFO policy.
A.X. Falcão – p.82/122
Segmentation by local reconstruction
A CT image of a knee where one seed
�
is selected inside the femur
with handicap
c d � e�� f d � e , but less than the brightness of the femur’s
border (left). The interior of the bone can be extracted from the root
map
�
(right).
A.X. Falcão – p.83/122
Local superior reconstruction
The local superior reconstruction is a variant which fills up
one or more basins, selected by a seed set
�
, up to levels
specified by given handicaps
" �
	 �su C �
	 � for 	 � �. Its cost
function is
 �� ( � � � � �
	 � � � " �
	 � , if 	 � �, and, t otherwise,
 �� (� �� � � � ��� � 	 � � �
 ��� � � � � � � if �� � � � � � u C �	 � ,, t � otherwise.
It has been used for image filtering by area closing and im-
age segmentation.
A.X. Falcão – p.84/122
Boundary tracking
Consider the problem of finding an optimum curve that is
constrained to pass through a given sequence� � � 
 �� � � � � � of � landmarks (pixel sets) on the object’s
boundary, in that order, starting in � and ending in � .
MR-image where the talus is the object of interest.
A.X. Falcão – p.85/122
Boundary tracking
If
 
is MI, the curve consists of
� � � segments�� � �
 �� � � � ��  � , where �� is an -optimum path
connecting � to � �� .
The problem can be solved by
� � � executions of the
IFT, where each stage can be terminated as soon as
the last pixel of the target set � �� is removed from the
queue.
The curve is obtained from the predecessor maps=�  � � =�  
 �� � � � =� .
The curve can be closed by making
¡� � ¡� and
computing an extra path from the last to the first pixel of
the opened curve.
A.X. Falcão – p.86/122
Cost function for the talus
 PE � /� � � �
	 � � �
¢£
£¥¤
; � if � � � and 	 � ¡� ,q� �	 � � if �u � and 	 � ¡� ,, t � otherwise. PE � /� � � � � ��� � 	 � � � PE � /� � � � �, . ��� � 	 � �
where . ��� � 	 � � | � 1 23 4 � ��� � 	 � � ¦ ��� � 	 � � ; 5 , where � ��� � 	 � is a
gradient vector estimated at the midpoint of arc
��� � 	 � ; 6 �� � 	 �
is the arc
��� � 	 � rotated 90 degrees counter-clockwise; and |
is an upper bound for
N � ��� � 	 � � 6 ��� � 	 � N .
A.X. Falcão – p.87/122
Boundary orientation
t s
G(s,t)
t s
G(s,t)
a(s,t)
a(s,t)
Figure on the left shows when the cost assignment will not favor
dkj l � e
orientation and the other way around is shown on the right.
A.X. Falcão – p.88/122
Optimum boundary of the talus
Result of the IFTs with FIFO policy and
§
-neighborhood.
A.X. Falcão – p.89/122
Live wire
Live wire becomes a particular case of this optimum
formulation for boundary tracking, where the sets
¡� are
chosen by the user during image segmentation.
A.X. Falcão – p.90/122
Live wire
A.X. Falcão – p.91/122
Live-wire-on-the-fly
Note that its most recent variant, called live-wire-on-the-fly,
is another example of IFT being computed in a differential
way.
A.X. Falcão – p.92/122
Euclidean distance transform (EDT)
The EDT of a given seed set
� � � assigns to each image
pixel
	 � � a value q �	 � , which is the minimum Euclidean
distance from
	
to
�
.
A fish contour (left) and its EDT (right).
A.X. Falcão – p.93/122
Cost function for the EDT
 �� * � � �
	 � � � ; � if 	 � �, and, t otherwise. �� * � � � � ��� � 	 � � � � $OE � $� �
 , � FE � F� �
 �
where ¨ is the initial pixel of � (or better, S ��� � during the
execution of the algorithm). The EDT can be obtained by
computing the IFT with FIFO policy and the squared root of
its resulting cost map
q
.
A.X. Falcão – p.94/122
Example of the EDT
Consider a directed graph whose nodes are the image
pixels of a binary image
B
and whose arcs are defined by an�
-neighborhood relation. The seed set
�
is composed by
contour pixels.
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
A.X. Falcão – p.95/122
The Euclidean distance map
2222222222 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 2222222222
1111111111 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 1111111111
1111111111 0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000 1111111111
1111111111 0000000000 1111111111 4444444444 4444444444 4444444444 4444444444 1111111111 0000000000 1111111111
1111111111 0000000000 1111111111 4444444444 4444444444 4444444444 4444444444 1111111111 0000000000 1111111111
1111111111 0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000 1111111111
1111111111 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 1111111111
2222222222 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 2222222222
The cost map
©
shows the squared Euclidean distance values.
©
can be used to compute the multiscale fractal dimension of
ª
.
A.X. Falcão – p.96/122
Discrete Voronoi regions
The influence zones of the contour pixels define
discrete Voronoi regions in the root map
S
.
Each contour pixel
	 � � can be associated with a
subsequent integer number
U �
	 �
from
�
to
«
, while
circumscribing the contour.
A label map
U
may be created from the root map
S
by
setting
U �	 � X U �S �
	 � � , or the labels may be propagated
during the algorithm.
The label map
U
can be used to compute multiscale skele-
tons and salience points along the contour.
A.X. Falcão – p.97/122
Discrete Voronoi regions
24242424242424242424 24242424242424242424 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 7777777777 7777777777
24242424242424242424 24242424242424242424 1111111111 2222222222 3333333333 44444444445555555555 6666666666 7777777777 7777777777
23232323232323232323 23232323232323232323 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 8888888888 8888888888
22222222222222222222 22222222222222222222 22222222222222222222 2222222222 3333333333 4444444444 5555555555 9999999999 9999999999 9999999999
21212121212121212121 21212121212121212121 21212121212121212121 21212121212121212121 16161616161616161616 15151515151515151515 10101010101010101010 10101010101010101010 10101010101010101010 10101010101010101010
20202020202020202020 20202020202020202020 20202020202020202020 17171717171717171717 16161616161616161616 15151515151515151515 14141414141414141414 11111111111111111111 11111111111111111111 11111111111111111111
19191919191919191919 19191919191919191919 18181818181818181818 17171717171717171717 16161616161616161616 15151515151515151515 14141414141414141414 13131313131313131313 12121212121212121212 12121212121212121212
19191919191919191919 19191919191919191919 18181818181818181818 17171717171717171717 16161616161616161616 15151515151515151515 14141414141414141414 13131313131313131313 12121212121212121212 12121212121212121212
The label map
U
shows the influence zone of each contour
pixel.
A.X. Falcão – p.98/122
Some observations
Although
 �� * � is not smooth for some combinations of �
and ,
�
-neighborhood seems to be enough for most
practical situations.
Even when
 �� * � is not smooth, and the IFT can not
output exact distance values,
�
-connected regions are
essential to obtain one-pixel-wide and connected
skeletons.
A.X. Falcão – p.99/122
Multiscale skeletons
Internal and external multiscale skeletons of a close curve�­¬ � can be obtained from the label map U by assigning to
each pixel � � � a difference value
® �� � � 1 23¯ ° (²± E ³µ´ ¶
4 1 ·¹¸ 4 U �
	 � � U ��� � � « � � U �	 � � U �� � �5 5 �
where
«
is the number of contour pixels and is the
:
-
neighborhood relation.
A.X. Falcão – p.100/122
Example of MS-skeletons
24242424242424242424 24242424242424242424 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 7777777777 7777777777
24242424242424242424 24242424242424242424 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 7777777777 7777777777
23232323232323232323 23232323232323232323 1111111111 2222222222 3333333333 4444444444 5555555555 6666666666 8888888888 8888888888
22222222222222222222 22222222222222222222 22222222222222222222 2222222222 3333333333 4444444444 5555555555 9999999999 9999999999 9999999999
21212121212121212121 21212121212121212121 21212121212121212121 21212121212121212121 16161616161616161616 15151515151515151515 10101010101010101010 10101010101010101010 10101010101010101010 10101010101010101010
20202020202020202020 20202020202020202020 20202020202020202020 17171717171717171717 16161616161616161616 15151515151515151515 14141414141414141414 11111111111111111111 11111111111111111111 11111111111111111111
19191919191919191919 19191919191919191919 18181818181818181818 17171717171717171717 16161616161616161616 15151515151515151515 14141414141414141414 13131313131313131313 12121212121212121212 12121212121212121212
19191919191919191919 19191919191919191919 18181818181818181818 17171717171717171717 16161616161616161616 15151515151515151515 14141414141414141414 13131313131313131313 12121212121212121212 12121212121212121212
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 2222222222 1111111111 1111111111 1111111111 1111111111 3333333333 1111111111 0000000000
0000000000 1111111111 0000000000 4444444444 10101010101010101010 11111111111111111111 5555555555 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 0000000000 5555555555 1111111111 5555555555 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 4444444444 1111111111 1111111111 1111111111 3333333333 1111111111 0000000000
0000000000 1111111111 2222222222 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
The label map
º
(left) and the skeleton scale map
»
inside the object
only (right).
A.X. Falcão – p.101/122
Example of MS-skeletons
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 1111111111 2222222222 1111111111 1111111111 1111111111 1111111111 3333333333 1111111111 0000000000
0000000000 1111111111 0000000000 4444444444 10101010101010101010 11111111111111111111 5555555555 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 0000000000 5555555555 1111111111 5555555555 1111111111 1111111111 0000000000
0000000000 1111111111 1111111111 4444444444 1111111111 1111111111 1111111111 3333333333 1111111111 0000000000
0000000000 1111111111 2222222222 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 1111111111 0000000000 0000000000 0000000000 0000000000 1111111111 0000000000 0000000000
0000000000 0000000000 0000000000 1111111111 1111111111 1111111111 1111111111 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 1111111111 0000000000 1111111111 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 1111111111 0000000000 0000000000 0000000000 1111111111 0000000000 0000000000
0000000000 0000000000 1111111111 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
One-pixel wide and connected skeletons (right) can be obtained by
thresholding
»
(left) at various scales.
A.X. Falcão – p.102/122
MS-skeletons for the fish contour
Labeled contour (left) and label map
º
(right).
A.X. Falcão – p.103/122
Multiscale skeletons
MS-skeletons (left) and a skeleton obtained by thresholding (right).
A.X. Falcão – p.104/122
Multiscale skeletons
The skeletons become more simplified as the threshold increases.
A.X. Falcão – p.105/122
Salience points
The salience points of a curve can be informally defined as
its higher curvature points.
Convex points are shown in blue and concave points in red.
A.X. Falcão – p.106/122
Salience values
Consider a small radius � forming a narrow band ¼ of size L �
around a curve
ª
.
Each salience point has two influence areas within
¼
, one
outside and one inside
ª
.
Convex points have higher influence areas outside than inside,
and the other way around is true for concave points.
½ ½ ½ ½ ½½ ½ ½ ½ ½½ ½ ½ ½ ½½ ½ ½ ½ ½½ ½ ½ ½ ½¾ ¾ ¾ ¾ ¾¾ ¾ ¾ ¾ ¾¾ ¾ ¾ ¾ ¾¾ ¾ ¾ ¾ ¾
¿ ¿ ¿¿ ¿ ¿¿ ¿ ¿¿ ¿ ¿¿ ¿ ¿ À ÀÀ ÀÀ ÀÀ À
Á Á ÁÁ Á Á Â ÂÂ Â
à à à Ãà à à Ãà à à ÃÄ Ä Ä ÄÄ Ä Ä ÄÄ Ä Ä Ä
A
B
The salience value of a point is its highest influence area.
A.X. Falcão – p.107/122
Detection of salience points
The salience value
Å
of a point relates to the aperture
angle
Æ
by the formula
Å � Ç� È
 .Å
can be coomputed from the histogram of the label
map
U
.
Salience points can be detected by thresholding
Æ
.
Small values of ¨ reduce cross-influence in this method
from opposite parts of the contour which come close to
each other.
The method works fine for skeletons, but not for contours
which are usually more intricate shapes.
A.X. Falcão – p.108/122
Detection of salience points on contoursSalience points of the contour can be related to salience points of
its internal and external skeletons by means of the skeleton scale
map
»
and root map
�
.
b a
dc
c
ba
d
For a clockwise labeled contour: if
� d � e J �, � is reached by skippingÉ Ê � Ë Ì pixels in anti-clockwise from � (left); and if � d � e J �, � is reached
from
�
by skipping
É Ê � Ë Ì pixels in clockwise (right). But, how do we
know if the root of � is � or �?
A.X. Falcão – p.109/122
Detection of salience points on contours
The skeleton scale value at a pixel j Í Î is
» dkj e J Ï ÐÑÒ ÊÔÓÔÕ Ö ËØ× Ù
Ú Ï ÛÝÜ Ú º d � eon º dj el Þn d º d � eon º dkj e eß ß l
where
Þ
is the number of contour pixels and
\
is the^
-neighborhood relation.
The root of � will be � wheneverº d � eon º dkj e � Þn d º d � e n º dkj e e , where º d � e J º d � e andº dj e J º d � e .
The root of � will be � wheneverº d � eon º dkj eáà Þn d º d � e n º dkj e e , where º d � e J º d � e andº dj e J º d � e .
A.X. Falcão – p.110/122
Signed ms-skeletons
The solution is to sign the ms-skeletons
®
.
1. For all pixels � � �, do
2. Set
â +/0 X � t.
3. For all pixels
	
, such that
�� � 	 � � Å, do
4. Set
â X 1 ·¸ 4 U �
	 � � U ��� � � « � � U �
	 � � U ��� � �5 and
ã X , �.
5. If
â � } « � � U �
	 � � U ��� � � ~ , then set ã X � �.
6. If
âu â +/0 , then set â +/0 X â and � �sä > X ã.
7. Set
® ��� � X � � ä > å â +/0 .
A.X. Falcão – p.111/122
Salience points of a contour
Salience points on the internal (left) and external (center) skeletons.
Salience points on the contour (right).
A.X. Falcão – p.112/122
Contour salience descriptor
The contour salience descriptor consists of the relative
position of each salience point along the contour with
respect to a starting point, the salience values for these
points, and a matching algorithm.
-0.3
-0.25
-0.2
-0.15
-0.1
-0.05
0
0.05
0.1
0.15
0.2
0 0.2 0.4 0.6 0.8 1
In
fl
ue
nc
e 
A
re
a
Contour point
A B
C
D E
F
G
H I
J
K
A.X. Falcão – p.113/122
Fractal dimension
The Fractal dimension of a set
�
by Minkowski-Bouligand is
a number
æ
within
}; � Q ~ .
æ � Q � x · 1� ç è
x¸ � Å � ¨ � �
x¸ � ¨ � �
where
Å � ¨ � is the area of � dilated by a radius ¨. It represents
the self-similarity of
�
for ¨ close to ; . Note that, Å is simply
the cummulative histogram of the Euclidean distance map
which can be obtained from the cost map
q
.
A.X. Falcão – p.114/122
Euclidean distance map
A.X. Falcão – p.115/122
Standard approach for computing
8.5
9
9.5
10
10.5
11
11.5
12
12.5
13
1 2 3 4 5 6
L
og
(A
)
Log(r)
observed values
fitted straight line
A shape similar to the Koch star, which has
æêé �� Që (left). A
line is fitted to the curve (right), and its first derivative is used
to estimate
æ
(
æ é �� Q R).
A.X. Falcão – p.116/122
Multiscale fractal dimension
We use polynomial regression for fitting (left) and
ì
becomes a
polynomial curve, called multiscale fractal dimension (right).
8.5
9
9.5
10
10.5
11
11.5
12
12.5
13
1 2 3 4 5 6
L
og
(A
)
Log(r)
observed values
polynomial regression
0.8
0.85
0.9
0.95
1
1.05
1.1
1.15
1.2
1.25
1.3
1 1.5 2 2.5 3 3.5 4 4.5 5 5.5
Fr
ac
ta
l D
im
en
si
on
 (
F)
Log(r)
Note that, the maximum value of the curve is close to 1.26, providing
much richer description of the self-similarity of
ª
.
A.X. Falcão – p.117/122
Shape analysis
Multiscale Fractal Dimention (MFD) and Contour
Salience Descriptor (CSD) have been compared to
Curvature Scale Space (CSS), Bean Angle Statistics
(BAS), Moment Invariants (MIV), Fourier Descriptors
(FD), and Simple Fractal Dimension (SFD) for shape
classification using a database of 11,000 fish contours
and 1,100 classes.
CSD was the most effective among them, for this
particular application, and MFD was competitive with
FD and BAS, and superior to SFD and MIV.
A.X. Falcão – p.118/122
Combining image operators
Image of blood cells (left). Area opening by IFT (center). Threshold-
ing and morphological opening (right).
A.X. Falcão – p.119/122
Combining image operators
Distance transform by IFT (left). Regional maxima by IFT (center).
Local reconstruction by IFT (right).
A.X. Falcão – p.120/122
Current work
Procedures for automatic seed selection during
interactive 3D segmentation.
More effective path-cost functions for 3D segmentation
of MR-images of the brain and the evaluation of the
methods.
Methods that combine boundary tracking and active
contours for image segmentation.
Automatic image operators based on the DIFT.
3D multiscale skeletonization.
Further improvements on multiscale fractal dimension
and contour salience descriptor.
A.X. Falcão – p.121/122
Conclusion
The IFT provides a different way to look at image
processing operations.
To develop an image operator based on the IFT, one
needs to
relate the operator to an optimum image partition
problem with connectivity restriction,
find suitable adjacency relation and smooth
path-cost function, and
apply some local processing to the output of the IFT
algorithm.
A.X. Falcão – p.122/122
	Contributors
	Goals of research
	Motivation
	Purpose of the lecture
	What is it all about?
	What is it all about?
	Region-based image segmentation
	Image filtering
	Optimum boundary tracking
	Euclidean distance transform (EDT)
	Multiscale skeletonization
	Multiscale fractal dimension
	Salience points of a shape
	Outline
	Directed graphs
	Paths
	Path-cost functions
	Examples of MI cost functions
	Examples of MI cost functions
	Predecessor map and spanning forest
	Paths of the forest $P$
	Optimum-path forest
	Dijkstra's algorithm
	Smooth path-cost functions
	An image as a directed graph
	Examples of adjacency relations
	Examples of adjacency relations
	Connectivity relation
	Labeling of components
	Labeling of components
	Labeling of components
	Labeling of components
	Labeling of components
	Labeling algorithm
	Image Foresting Transform
	Tie-breaking
	IFT algorithm
		extcolor {red}{FIFO} tie-breaking
		extcolor {red}{FIFO} tie-breaking
		extcolor {red}{FIFO} tie-breaking
		extcolor {red}{FIFO} tie-breaking
		extcolor {red}{FIFO} tie-breaking
		extcolor {red}{FIFO} tie-breaking
		extcolor {red}{LIFO} tie-breaking
		extcolor {red}{LIFO} tie-breaking
		extcolor {red}{LIFO} tie-breaking
		extcolor {red}{LIFO} tie-breaking
		extcolor {red}{LIFO} tie-breaking
		extcolor {red}{LIFO} tie-breaking
	IFT algorithm with 	extcolor {red}{FIFO} policy
	IFT algorithm with 	extcolor {red}{LIFO} policy
	Unfair partitions with 	extcolor {red}{FIFO}
	Priority queue $Q$
	Circular priority queue
	Detection of regional minima
	Cost function for regional minima
	Regional minima with 	extcolor {red}{FIFO}
	Regional minima with 	extcolor {red}{LIFO}
	Seed pixels
	Region-based image segmentation
	The IFT-watershed approach
	Cost function for the caudate nucleus
	Left caudate nucleus
	Left caudate nucleus
	Differential IFT
	Differential IFT
	3D interactive segmentation
	2D example of DIFT-watershed
	2D example of DIFT-watershed
	Segmentation from the 	extcolor {red}{cost map $C$}
	Cost function for the wrist
	Cost function for the wrist
	Bone of the wrist
	Bone of the wrist
	Bone of the wrist
	Filtering by reconstruction
	Filtering by reconstruction
	Cost function for the skull
	Cost function for the skull
	Filtering by reconstruction
	Filtering by reconstruction
	Segmentation by local reconstruction
	Local superior reconstruction
	Boundary tracking
	Boundary tracking
	Cost function for the talus
	Boundary orientation
	Optimum boundary of the talus
	Live wire
	Live wire
	Live-wire-on-the-fly
	Euclidean distance transform (EDT)
	Cost function for the EDT
	Example of the EDT
	The Euclidean distance map
	Discrete Voronoi regions
	Discrete Voronoi regions
	Some observations
	Multiscale skeletons
	Example of MS-skeletons
	Example of MS-skeletons
	MS-skeletons for the fish contour
	Multiscale skeletons
	Multiscale skeletons
	Salience points
	Salience values
	Detection of salience pointsDetection of salience points on contours
	Detection of salience points on contours
	Signed ms-skeletons
	Salience points of a contour
	Contour salience descriptor
	Fractal dimension
	Euclidean distance map
	Standard approach for computing $F$
	Multiscale fractal dimension
	Shape analysis
	Combining image operators
	Combining image operators
	Current work
	Conclusion