The tree of shapes of an image

Free access article

Issue		ESAIM: COCV Volume 9, 2003


Page(s)		1 - 18
DOI		10.1051/cocv:2002069

ESAIM: COCV, January 2003, Vol. 9, pp. 1-18
DOI: 10.1051/cocv:2002069

The tree of shapes of an image

Coloma Ballester¹, Vicent Caselles¹ and P. Monasse²

¹ Univ. Pompeu-Fabra, Passeig de Circumvalació 8, 08003 Barcelona, Spain; coloma.ballester@tecn.upf.es. vicent.caselles@tecn.upf.es.
² CMLA, ENS Cachan, 61 avenue du Président Wilson, 94235 Cachan Cedex, France; monasse@cmla.ens-cachan.fr.

(Received February 1, 2002.)

Abstract
In [30], Kronrod proves that the connected components of isolevel sets of a continuous function can be endowed with a tree structure. Obviously, the connected components of upper level sets are an inclusion tree, and the same is true for connected components of lower level sets. We prove that in the case of semicontinuous functions, those trees can be merged into a single one, which, following its use in image processing, we call "tree of shapes". This permits us to solve a classical representation problem in mathematical morphology: to represent an image in such a way that maxima and minima can be computationally dealt with simultaneously. We prove the finiteness of the tree when the image is the result of applying any extrema killer (a classical denoising filter in image processing). The shape tree also yields an easy mathematical definition of adaptive image quantization.

Mathematics Subject Classification. 68U10, O5C05

Key words: Image representation, mathematical morphology, tree structure, level sets.

© EDP Sciences, SMAI 2003

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.