# The tree of shapes of an image

• [1] CMLA, ENS Cachan, 61 avenue du Président Wilson, 94235 Cachan Cedex, France
• Volume: 9, page 1-18
• ISSN: 1292-8119

top

## Abstract

top
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.

## How to cite

top

Ballester, Coloma, Caselles, Vicent, and Monasse, P.. "The tree of shapes of an image." ESAIM: Control, Optimisation and Calculus of Variations 9 (2003): 1-18. <http://eudml.org/doc/244732>.

@article{Ballester2003,
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.},
affiliation = {CMLA, ENS Cachan, 61 avenue du Président Wilson, 94235 Cachan Cedex, France},
author = {Ballester, Coloma, Caselles, Vicent, Monasse, P.},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {image representation; mathematical morphology; tree structure; level sets},
language = {eng},
pages = {1-18},
publisher = {EDP-Sciences},
title = {The tree of shapes of an image},
url = {http://eudml.org/doc/244732},
volume = {9},
year = {2003},
}

TY - JOUR
AU - Ballester, Coloma
AU - Caselles, Vicent
AU - Monasse, P.
TI - The tree of shapes of an image
JO - ESAIM: Control, Optimisation and Calculus of Variations
PY - 2003
PB - EDP-Sciences
VL - 9
SP - 1
EP - 18
AB - 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.
LA - eng
KW - image representation; mathematical morphology; tree structure; level sets
UR - http://eudml.org/doc/244732
ER -

## References

top
1. [1] L. Alvarez, F. Guichard, P.L. Lions and J.M. Morel, Axioms and fundamental equations of image processing. Arch. Rational Mech. Anal. 16 (1993) 200-257. Zbl0788.68153MR1225209
2. [2] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems. Oxford Mathematical Monographs (2000). Zbl0957.49001MR1857292
3. [3] L. Ambrosio, V. Caselles, S. Masnou and J.M. Morel, The Connected Components of Sets of Finite Perimeter. Eur. J. Math. 3 (2001) 39-92. Zbl0981.49024MR1812124
4. [4] C. Ballester, E. Cubero–Castan, M. Gonzalez and J.M. Morel, Image intersection and applications to satellite imaging, Preprint. C.M.L.A., École Normale Supérieure de Cachan (1998).
5. [5] C. Ballester and V. Caselles, The $M$-components of level sets of continuous functions in WBV. Publ. Mat. 45 (2001) 477-527. Zbl0991.54013MR1876918
6. [6] V. Caselles and P. Monasse, Grain filters. J. Math. Imaging Vision (to appear). Zbl1028.68140MR1945474
7. [7] V. Caselles, B. Coll and J.M. Morel, Topographic Maps and Local Contrast Changes in Natural Images. Int. J. Comput. Vision 33 (1999) 5-27.
8. [8] V. Caselles, J.L. Lisani, J.M. Morel and G. Sapiro, Shape Preserving Histogram Modification. IEEE Trans. Image Process. 8 (1999).
9. [9] T. Chan, G. Golub and P. Mulet, A Nonlinear Primal-Dual Method for TV-Based Image Restoration, in ICAOS’96, 12th International Conference on Analysis and Optimization of Systems: Images, Wavelets and PDE’s, edited by M. Berger, R. Deriche, I. Herlin, J. Jaffre and J.M. Morel, Lecture Notes in Control and Inform. Sci. 219 (1996) 241-252. Zbl0852.68114
10. [10] J.L. Cox and D.B. Karron, Digital Morse Theory (1998), available at http://www.casi.net
11. [11] E. De Giorgi and L. Ambrosio, Un nuovo tipo di funzionale del Calcolo delle Variazioni. Atti Accad. Naz. Lincei 8 (1988) 199-210. Zbl0715.49014
12. [12] A. Desolneux, L. Moisan and J.M. Morel, Edge Detection by Helmholtz Principle. J. Math. Imaging Vision 14 (2001) 271-284. Zbl0988.68819
13. [13] F. Dibos and G. Koepfler, Total Variation Minimization by the Fast Level Sets Transform, in Proc. of IEEE Workshop on Variational and Level Sets Methods in Computer Vision (2001). Zbl0957.49002
14. [14] F. Dibos, G. Koepfler and P. Monasse, Total Variation Minimization: Application to Gray-scale, Color Images and Optical Flow Regularization, in Geometric Level Sets Methods in Imaging, Vision and Graphics, edited by S. Osher and N. Paragios (to appear).
15. [15] F. Dibos, G. Koepfler and P. Monasse, Image Registration, in Geometric Level Sets Methods in Imaging, Vision and Graphics, edited by S. Osher and N. Paragios (to appear). MR2071628
16. [16] S. Durand, F. Malgouyres and B. Rougé, Image Deblurring, Spectrum Interpolation and Application to Satellite Imaging. Math. Model. Numer. Anal. (to appear). Zbl0946.68150MR1789371
17. [17] L.C. Evans and R.F. Gariepy, Measure Theory and Fine Properties of Functions. Studies in Advanced Math., CRC Press (1992). Zbl0804.28001MR1158660
18. [18] J. Froment, A compact and multiscale image model based on level sets, in Proc. of the ${2}^{\text{nd}}$ Workshop on Scale-Space Theories in Computer Vision. Corfu, Greece (1999) 152-163.
19. [19] M. Golubitsky and V. Guillemin, Stable Mappings and Their Singularities. Springer-Verlag (1973). Zbl0294.58004MR341518
20. [20] L. Alvarez, Y. Gousseau and J.M. Morel, Scales in natural images and a consequence on their BV norm, in Proc. of the ${2}^{\text{nd}}$ Workshop on Scale-Space Theories in Computer Vision. Corfu, Greece (1999) 247-258.
21. [21] Y. Gousseau and J.M. Morel, Texture Synthesis through Level Sets. Preprint CMLA (2000).
22. [22] F. Guichard and J.M. Morel, Image iterative smoothing and P.D.E.’s (in preparation).
23. [23] C. Kuratowski, Topologie I, II. Editions J. Gabay (1992). Zbl0849.01044MR1296876
24. [24] J.-L. Lisani, L. Moisan, P. Monasse and J.M. Morel, Affine Invariant Mathematical Morphology Applied to a Generic Shape Recognition Algorithm. Comp. Imaging and Vision 18 (2000). Zbl1073.68774
25. [25] D. Marr, Vision. Freeman and Co. (1981).
26. [26] S. Masnou, Filtrage et désocclusion d’images par méthodes d’ensembles de niveau, Ph.D. Thesis. Ceremade, Université Paris-Dauphine (1998).
27. [27] F. Meyer and S. Beucher, Morphological Segmentation. J. Visual Commun. Image Representation 1 (1990) 21-46.
28. [28] J.M. Morel and S. Solimini, Variational methods in image processing. Birkhäuser (1994). Zbl0827.68111
29. [29] J. Milnor, Morse Theory. Princeton University Press, Annals Math. Studies 51 (1963). Zbl0108.10401MR163331
30. [30] A.S. Kronrod, On functions of two variables. Uspehi Mathematical Sciences (NS) 5 (1950) 24-134. Zbl0040.31603MR34826
31. [31] S. Mallat, A Wavelet Tour of Signal Processing. Academic Press, New York (1998). Zbl0937.94001MR1614527
32. [32] G. Matheron, Random Sets and Integral Geometry. John Wiley, NY (1975). Zbl0321.60009MR385969
33. [33] F. Meyer and P. Maragos, Morphological scale-space representation with levelings, in Proc. of the ${2}^{\text{nd}}$ Workshop on Scale-Space Theories in Computer Vision (1999) 187-198.
34. [34] P. Monasse, Contrast invariant image registration, in Proc. of International Conference on Acoustics. Speech and Signal Process. 6 (1999) 3221-3224.
35. [35] P. Monasse and F. Guichard, Fast computation of a contrast-invariant image representation. IEEE Trans. Image Process. 9 (2000) 860-872.
36. [36] P. Monasse and F. Guichard, Scale-space from a level lines tree. J. Visual Commun. Image Representation 11 (2000) 224-236.
37. [37] D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and variational problems. Comm. Pure Appl. Math. 42 (1988) 577-685. Zbl0691.49036MR997568
38. [38] M.H.A. Newman, Elements of the Topology of Plane Sets of Points. Dover Publications, New York (1992). Zbl0845.54002MR1160354
39. [39] L.I. Rudin, S. Osher and E. Fatemi, Nonlinear Total Variation Based Noise Removal Algorithms. Physica D 60 (1990) 259-269. Zbl0780.49028
40. [40] P. Salembier, Morphological multiscale segmentation for image coding. IEEE Trans. Signal Process. 38 (1994) 359-386.
41. [41] P. Salembier, Region-based filtering of images and video sequences: A morphological viewpoint. Preprint (2000).
42. [42] P. Salembier and J. Serra, Flat zones filtering, connected operators and filters by reconstruction. IEEE Trans. Image Process. 4 (1995) 1153-1160.
43. [43] P. Salembier, P. Brigger, J.R. Casas and M. Pardàs, Morphological Operators for Image and Video Compression. IEEE Trans. Image Process. 5 (1996) 881-897.
44. [44] P. Salembier and L. Garrido, Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. IEEE Trans. Image Process. 9 (2000).
45. [45] J. Serra, Image analysis and mathematical morphology. Academic Press (1982). Zbl0565.92001MR753649
46. [46] J. Serra, Image analysis and mathematical morphology. Volume 2: Theoretical Advances. Academic Press (1988). Zbl0565.92001MR949918
47. [47] J. Serra and P. Salembier, Connected operators and pyramids, in Proc. SPIE Image Algebra Math. Morphology. San Diego, CA, SPIE 2030 (1993) 65-76. MR1283596
48. [48] G. Sapiro and A. Tannenbaum, On affine plane curve evolution. J. Funct. Anal. 119 (1994) 79-120. Zbl0801.53008MR1255274
49. [49] G. Sapiro and A. Tannenbaum, Affine invariant scale space. Int. J. Comput. Vision 11 (1993) 24-44.
50. [50] C. Vachier, Valuation of image extrema using alterning filters by reconstruction, in Proc. SPIE, Image Algebra and Morphological Processing (1995).
51. [51] L. Vincent, Grayscale area openings and closings, their efficient implementation and applications, in Proc. of the ${1}^{st}$ Workshop on Mathematical Morphology and its Applications to Signal Processing, edited by J. Serra and Ph. Salembrier. Barcelona, Spain (1993) 22-27.
52. [52] L. Vincent, Morphological area openings and closings for grey-scale images, in Proc. of the Workshop Shape in Picture: Mathematical Description of Shape in Gray-Level Images. Driebergen, The Netherlands (1994) 197-208.
53. [53] L. Vincent and P. Soille, Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Trans. Pattern Anal. Machine Intell. 13 (1991) 583-598.
54. [54] C.R. Vogel and M.E. Oman, Iterative Methods for Total Variation Denoising. SIAM J. Sci. Comput. (to appear). Zbl0847.65083MR1375276
55. [55] M. Wertheimer, Untersuchungen zur Lehre der Gestalt, II. Psychologische Forschung 4 (1923) 301-350.
56. [56] L.P. Yaroslavsky and M. Eden, Fundamentals of digital optics. Birkhäuser, Boston (1996). Zbl0877.94006

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.