Title:  Image Segmentation as a Discrete Mathematics Problem
Author: Prof. Alexandre Xavier Falcão
Affiliation: State University of Campinas, Institute of Computing
E-mail: afalcao@ic.unicamp.br

Discrete Mathematics provides an elegant framework for image
processing and analysis, which is rich of efficient algorithms with
proofs of correctness. The image foresting transform (IFT) is an
example that reduces several image processing problems into a
minimum-cost path forest problem in a graph derived from the
image. Morphological reconstructions, watershed transforms, multiscale
skeletonization, contour tracking, shape salience, and distance
transforms are some instances of these applications. In this talk, I
will concentrate on approaches for region-based image segmentation
using a particular graph model and two algorithms: the minimum-cost
path forest algorithm and the maximum-flow algorithm.

The discrete mathematical model consists of interpreting the image as
a sparse graph, whose nodes are the image pixels and whose arcs are
defined by a small adjacency relation between pixels (e.g., an
8-connected relation in the 2D case). The basic idea is to enhance the
differences between object and background by assigning weights to the
arcs. Four distinct approaches will be discussed: (a) differential
watershed transform, (b) tree-pruning segmentation, (c) watershed
transform with graph-cut measures, and (d) min-cut/max-flow image
segmentation. In the later, each pixel is also connected to two
terminal nodes, source and sink, by weighted arcs.

Approaches (a)--(c) exploit the IFT algorithm and variants, while
approach (d) uses a maximum-flow algorithm. The IFT algorithm runs in
O(n) and maximum flow algorithms usually take O(n^3), for sparse
graphs with n nodes. When the segmentation fails, seed pixels may be
added/removed in all approaches for correction. Approach (a) is based
on internal (object) and external (background) seed competition, where
each seed is root of a tree in the forest. The corrections can be done
in sublinear time by adding/removing trees of the forest in a
differential way. It has been successfully used for interactive 3D
segmentation. Approaches (b) and (c) aim at eliminating/reducing
external seeds by exploiting other segmentation criteria rather than
seed competition. In approach (b), an optimum path forest rooted
inside the object connects it with the background by a few optimum
paths (leaking paths). The leaking paths cross the object's boundary
through its ``most weakly connected'' parts (leaking pixels). The
leaking pixels are automatically identified and their subtrees are
eliminated, such that the remaining forest defines the object. This
approach has been successfully used in some automatic segmentation
tasks, where object properties can be exploited for seed
computation. Approaches (c) and (d) define the object as resulting
from a minimum cut in the image graph, according to some graph-cut
measure. In approach (c), the main idea is to reduce the search space
of possible cuts, as compared to approach (d), by exploiting the IFT
algorithm and the seed competition paradigm. Approach (d) has been
actively pursued. It can also use seed pixels to force arc-weight
assignment between seeds and terminal nodes, and correct segmentation.

Apart from their differences in efficiency, the effectiveness of these
approaches strongly depends on the arc-weight assignment, which is an
application-dependent task. I will describe these approaches with
robustness conditions, present some results, and discuss the main
differences among them.


Biographical Sketch

Alexandre Falcão received a B.Sc. in Electrical Engineering from the
Federal University of Pernambuco, Recife, PE, Brazil, in 1988. He has
worked in medical image processing, visualization and analysis since
1991. In 1993, he received a M.Sc. in Electrical Engineering from the
State University of Campinas, Campinas, SP, Brazil. During 1994-1996,
he worked with the Medical Image Processing Group at the Department of
Radiology, University of Pennsylvania, PA, USA, on interactive image
segmentation for his doctorate. He got his doctorate in Electrical
Engineering from the State University of Campinas in 1996. In 1997, he
worked in a research center (CPqD-TELEBRAS, Campinas) developing
methods for video quality assessment with financial support from Globo
TV, Rio de Janeiro, RJ, Brazil. His experience as professor of
Computer Science and Engineering started in 1998 at the State
University of Campinas, where he is currently an Associate Professor
(since 2003). He is also an Associate Researcher with CNPq. His main
contributions in image processing are the segmentation methods based
on live-wire and, more recently, the image foresting transform (a
unified approach for the design of image processing operators). He has
published several papers in the main journals and conferences of image
processing and analysis, and served as reviewer to some of them. He
has also been in the program committee of SIBGRAPI (the Brazilian
Symposium on Computer Graphics and Image Processing) for several years
now. His main research interests include image segmentation and
analysis, volume visualization, content-based image retrieval,
mathematical morphology, digital video processing and biomedical
imaging applications.