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.
Mots-clés : image representation, mathematical morphology, tree structure, level sets
@article{COCV_2003__9__1_0,
author = {Ballester, Coloma and Caselles, Vicent and Monasse, P.},
title = {The tree of shapes of an image},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
pages = {1--18},
publisher = {EDP-Sciences},
volume = {9},
year = {2003},
doi = {10.1051/cocv:2002069},
mrnumber = {1957088},
zbl = {1073.68094},
language = {en},
url = {http://www.numdam.org/articles/10.1051/cocv:2002069/}
}
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 SP - 1 EP - 18 VL - 9 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv:2002069/ DO - 10.1051/cocv:2002069 LA - en ID - COCV_2003__9__1_0 ER -
%0 Journal Article %A Ballester, Coloma %A Caselles, Vicent %A Monasse, P. %T The tree of shapes of an image %J ESAIM: Control, Optimisation and Calculus of Variations %D 2003 %P 1-18 %V 9 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv:2002069/ %R 10.1051/cocv:2002069 %G en %F COCV_2003__9__1_0
Ballester, Coloma; Caselles, Vicent; Monasse, P. The tree of shapes of an image. ESAIM: Control, Optimisation and Calculus of Variations, Tome 9 (2003), pp. 1-18. doi : 10.1051/cocv:2002069. http://www.numdam.org/articles/10.1051/cocv:2002069/
[1] ,, and, Axioms and fundamental equations of image processing. Arch. Rational Mech. Anal. 16 (1993) 200-257. | MR | Zbl
[2] , and, Functions of Bounded Variation and Free Discontinuity Problems. Oxford Mathematical Monographs (2000). | MR | Zbl
[3] ,, and, The Connected Components of Sets of Finite Perimeter. Eur. J. Math. 3 (2001) 39-92. | MR | Zbl
[4] ,, and, Image intersection and applications to satellite imaging, Preprint. C.M.L.A., École Normale Supérieure de Cachan (1998).
[5] and, The -components of level sets of continuous functions in WBV. Publ. Mat. 45 (2001) 477-527. | MR | Zbl
[6] and, Grain filters. J. Math. Imaging Vision (to appear). | MR | Zbl
[7] , and, Topographic Maps and Local Contrast Changes in Natural Images. Int. J. Comput. Vision 33 (1999) 5-27.
[8] ,, and, Shape Preserving Histogram Modification. IEEE Trans. Image Process. 8 (1999).
[9] , and, 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. | Zbl
[10] and, Digital Morse Theory (1998), available at http://www.casi.net
[11] and, Un nuovo tipo di funzionale del Calcolo delle Variazioni. Atti Accad. Naz. Lincei 8 (1988) 199-210. | EuDML | Zbl
[12] , and, Edge Detection by Helmholtz Principle. J. Math. Imaging Vision 14 (2001) 271-284. | Zbl
[13] and, Total Variation Minimization by the Fast Level Sets Transform, in Proc. of IEEE Workshop on Variational and Level Sets Methods in Computer Vision (2001).
[14] , and, 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] , and, Image Registration, in Geometric Level Sets Methods in Imaging, Vision and Graphics, edited by S. Osher and N. Paragios (to appear). | MR
[16] , and, Image Deblurring, Spectrum Interpolation and Application to Satellite Imaging. Math. Model. Numer. Anal. (to appear). | Numdam | MR | Zbl
[17] and, Measure Theory and Fine Properties of Functions. Studies in Advanced Math., CRC Press (1992). | MR | Zbl
[18] , A compact and multiscale image model based on level sets1999) 152-163.
[19] and, Stable Mappings and Their Singularities. Springer-Verlag (1973). | MR | Zbl
[20] , and, Scales in natural images and a consequence on their BV norm1999) 247-258.
[21] and, Texture Synthesis through Level Sets. Preprint CMLA (2000).
[22] and, Image iterative smoothing and P.D.E.'s (in preparation).
[23] ,, II. Editions J. Gabay (1992). | MR | Zbl
[24] ,, and, Affine Invariant Mathematical Morphology Applied to a Generic Shape Recognition Algorithm. Comp. Imaging and Vision 18 (2000). | Zbl
[25] , Vision. Freeman and Co. (1981).
[26] , Filtrage et désocclusion d'images par méthodes d'ensembles de niveau, Ph.D. Thesis. Ceremade, Université Paris-Dauphine (1998).
[27] and, Morphological Segmentation. J. Visual Commun. Image Representation 1 (1990) 21-46.
[28] and, Variational methods in image processing. Birkhäuser (1994). | Zbl
[29] , Morse Theory. Princeton University Press, Annals Math. Studies 51 (1963). | MR | Zbl
[30] , On functions of two variables. Uspehi Mathematical Sciences (NS) 5 (1950) 24-134. | MR | Zbl
[31] , A Wavelet Tour of Signal Processing. Academic Press, New York (1998). | MR | Zbl
[32] , Random Sets and Integral Geometry. John Wiley, NY (1975). | MR | Zbl
[33] and, Morphological scale-space representation with levelings1999) 187-198.
[34] , Contrast invariant image registration, in Proc. of International Conference on Acoustics. Speech and Signal Process. 6 (1999) 3221-3224.
[35] and, Fast computation of a contrast-invariant image representation. IEEE Trans. Image Process. 9 (2000) 860-872.
[36] and, Scale-space from a level lines tree. J. Visual Commun. Image Representation 11 (2000) 224-236.
[37] and, Optimal approximations by piecewise smooth functions and variational problems. Comm. Pure Appl. Math. 42 (1988) 577-685. | MR | Zbl
[38] , Elements of the Topology of Plane Sets of Points. Dover Publications, New York (1992). | MR | Zbl
[39] , and, Nonlinear Total Variation Based Noise Removal Algorithms. Physica D 60 (1990) 259-269. | Zbl
[40] , Morphological multiscale segmentation for image coding. IEEE Trans. Signal Process. 38 (1994) 359-386.
[41] , Region-based filtering of images and video sequences: A morphological viewpoint. Preprint (2000).
[42] and, Flat zones filtering, connected operators and filters by reconstruction. IEEE Trans. Image Process. 4 (1995) 1153-1160.
[43] ,, and, Morphological Operators for Image and Video Compression. IEEE Trans. Image Process. 5 (1996) 881-897.
[44] and, Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. IEEE Trans. Image Process. 9 (2000).
[45] , Image analysis and mathematical morphology. Academic Press (1982). | MR | Zbl
[46] , Image analysis and mathematical morphology. Volume 2: Theoretical Advances. Academic Press (1988). | MR | Zbl
[47] and, Connected operators and pyramids, in Proc. SPIE Image Algebra Math. Morphology. San Diego, CA, SPIE 2030 (1993) 65-76. | MR
[48] and, On affine plane curve evolution. J. Funct. Anal. 119 (1994) 79-120. | MR | Zbl
[49] and, Affine invariant scale space. Int. J. Comput. Vision 11 (1993) 24-44.
[50] , Valuation of image extrema using alterning filters by reconstruction, in Proc. SPIE, Image Algebra and Morphological Processing (1995).
[51] , Grayscale area openings and closings, their efficient implementation and applications1993) 22-27.
[52] , 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] and, Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Trans. Pattern Anal. Machine Intell. 13 (1991) 583-598.
[54] and, Iterative Methods for Total Variation Denoising. SIAM J. Sci. Comput. (to appear). | MR | Zbl
[55] , Untersuchungen zur Lehre der Gestalt, II. Psychologische Forschung 4 (1923) 301-350.
[56] and, Fundamentals of digital optics. Birkhäuser, Boston (1996). | Zbl
Cité par Sources :
