×

Level lines selection with variational models for segmentation and encoding. (English) Zbl 1478.94007

Summary: This paper discusses the interest of the Tree of Shapes of an image as a region oriented image representation. The Tree of Shapes offers a compact and structured representation of the family of level lines of an image. This representation has been used for many processing tasks such as filtering, registration, or shape analysis. In this paper we show how this representation can be used for segmentation, rate distortion optimization, and encoding. We address the problem of segmentation and rate distortion optimization using Guigues algorithm on a hierarchy of partitions constructed using the simplified Mumford-Shah multiscale energy. To segment an image, we minimize the simplified Mumford-Shah energy functional on the set of partitions represented in this hierarchy. The rate distortion problem is also solved in this hierarchy of partitions. In the case of encoding, we propose a variational model to select a family of level lines of a gray level image in order to obtain a minimal description of it. Our energy functional represents the cost in bits of encoding the selected level lines while controlling the maximum error of the reconstructed image. In this case, a greedy algorithm is used to minimize the corresponding functional. Some experiments are displayed.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
68U10 Computing methodologies for image processing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M.D. Adams, ”The jpeg-2000 still image compression standard.” Available at http://www.ece.ubc.ca/mdadams , 2001.
[2] C. Ballester, E. Cubero-Castan, M. Gonzalez, and J.M. Morel, ”Image intersection and applications to satellite imaging,” Preprint, C.M.L.A., Ecole Normale Supérieure de Cachan, 1998.
[3] C. Ballester, V. Caselles, and P. Monasse, ”The tree of shapes of an image,” ESAIM: Control, Opt. and Calc. of Variations, Vol. 9, pp. 1–18, 2003. · Zbl 1073.68094 · doi:10.1051/cocv:2002069
[4] T. Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice Hall, 1971. · Zbl 0200.00001
[5] L. Breiman, J.H. Friedman, R.A. Olsen, and C. J. Stone, Classification and Regression Trees. Wadsworth, Belmont, California, 1984. · Zbl 0541.62042
[6] F. Cao, P. Musé, and F. Sur, ”Extracting meaningful curves in images,” To appear in Journal of Mathematical Imaging and Vision, 2005.
[7] F. Cao, Y. Gousseau, J.M. Morel, P. Musé, and F. Sur, ”An a contrario decision method for shape element recognition,” Preprint CMLA, No. 16, 2004. · Zbl 1188.68249
[8] V. Caselles, B. Coll, and J.M. Morel, ”Topographic maps and local contrast changes in natural images,” Int. J. Comp. Vision, Vol. 33, pp. 5–27, 1999. · Zbl 05467140 · doi:10.1023/A:1008144113494
[9] V. Caselles, J.L. Lisani, J.M. Morel, and G. Sapiro, ”Shape preserving histogram modification,” IEEE Transactions on Image Processing, Vol. 8, No. 2, pp. 220–230, 1999. · doi:10.1109/83.743856
[10] V. Caselles, J.M. Morel, and C. Sbert, ”An axiomatic approach to image interpolation,” IEEE Transactions on Image Processing, Vol. 7, pp. 376–386, 1998. · Zbl 0993.94504 · doi:10.1109/83.661188
[11] V. Caselles, and P. Monasse, ”Morse theories of the Topographic map,” In preparation. · Zbl 1191.68759
[12] V. Caselles, G. Sapiro, A. Solé, and C. Ballester, ”Morse description and morphological encoding of continuous data,” SIAM Journal on Multiscale Modeling and Simulation, Vol. 2, pp. 179–209, 2004. · Zbl 1079.68103 · doi:10.1137/S1540345902416557
[13] R. Chiariglioni, ”MPEG and multimedia communitations,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 7, pp. 5–18, 1997. · doi:10.1109/76.554414
[14] P.A. Chou, T. Lookabaugh, and R.M. Gray, ”Optimal pruning with applications to tree-structured source coding and modeling,” IEEE Trans. Inform. Theory, Vol. 35, pp. 299–315, 1989. · doi:10.1109/18.32124
[15] A. Desolneux, L. Moisan, and J.M. Morel, ”Edge detection by Helmholtz principle,” Journal of Mathematical Imaging and Vision, Vol. 14, pp. 271–284, 2001. · Zbl 0988.68819 · doi:10.1023/A:1011290230196
[16] M. Eden and M. Kocher, ”On the performance of a contour coding algorithm in the context of image coding. Part I: Contour segment coding,” Signal Processing, Vol. 8, pp. 381–386, 1985. · doi:10.1016/0165-1684(85)90001-5
[17] J. Froment, ”A functional analysis model for natural images permitting structured compression,” ESAIM: Control, Optimization and Calculus of Variation, Vol. 4, pp. 473–495, 1999. · Zbl 0924.68201 · doi:10.1051/cocv:1999118
[18] L. Garrido, ”Hierarchical region based processing of images and video sequences: Application to filtering, sementation and information retrieval,” PhD thesis, Universitat Politécnica de Catalunya, 2002.
[19] F. Guichard and J.M. Morel, Image Iterative Smoothing and P.D.E.’s’. Book in preparation, 2000.
[20] L. Guigues, ”Modèles Multi-Échelles pour la Segmentation d’Images,” PhD thesis, Université de Cergy-Pontoise, 2003.
[21] A. Gersho and R.M. Gray, Vector Quantization and Signal Compression, Kluwer Academic Publishers, 1992. · Zbl 0782.94001
[22] J.M. Hyman, ”Accurate monotonicity preserving cubic interpolation.” SIAM J. Sci. Stat. Comp, Vol. 4, pp. 645–654, 1983. · Zbl 0533.65004 · doi:10.1137/0904045
[23] L. Igual, L. Garrido, and V. Caselles, ”A contrast invariant approach to motion estimation, validation and motion segmentation,” · Zbl 1308.94014
[24] G. Koepfler, C. Lopez, and J.M. Morel, ”A multiscale algorithm for image segmentation by variational method,” SIAM J. Numer. Anal, Vol. 31, pp. 282–299, 1994. · Zbl 0804.68053 · doi:10.1137/0731015
[25] C. Kuratowski, Topologie I, II. Editions J. Gabay: Paris, 1992.
[26] Y. G. Leclerc, ”Constructing simple stable descriptions for image partitioning,” International Journal of Computer Vision, Vol. 3, pp. 73–102, 1989. · doi:10.1007/BF00054839
[27] F. Meyer, ”The dynamics of minima and contours,” in Methematical Morphology and Its Applications to Image Processing, Atlanta (GA), USA, pp. 329–336, 1996. · Zbl 0918.68154
[28] F. Meyer and S. Beucher, ”Morphological segmentation,” J. of Visual Communication and Image Representation, Vol. 1, pp. 21–46, 1990. · doi:10.1016/1047-3203(90)90014-M
[29] P. Monasse, ”Représentation morphologique d’images numériques et application au recalage,” PhD thesis, Université de Paris-Dauphine, 2000.
[30] P. Monasse, ”Contrast invariant image registration,” in: Proc. of International Conference on Acoustics, Speech and Signal Processing, Vol. 6, pp. 3221–3224, 1999.
[31] P. Monasse and F. Guichard, ”Fast computation of a contrast invariant image representation,” IEEE Transactions on Image Processing, Vol. 9, pp. 860–872, 2000. · doi:10.1109/83.841532
[32] J.M. Morel and S. Solimini, Variational Methods in Image Processing. Birkhäuser Verlag: Basel, 1994. · Zbl 0827.68111
[33] D. Mumford and J. Shah, ”Optimal approximations by piecewise smooth functions and variational problems,” Communications on Pure and Applied Mathematics, Vol. 42, No. 5, pp. 577–685, 1988. · Zbl 0691.49036 · doi:10.1002/cpa.3160420503
[34] J. Rissanen, ”Minimum-Description-Length principle,” in Encyclopedia of Statistical Sciences. John Wiley: New York, 1987, Vol. 5, pp. 523–527.
[35] P. Salembier, ”Morphological multiscale segmentation for image coding,” IEEE Transactions on Signal Processing, Vol. 38, No. 3, pp. 359–386, 1994.
[36] P. Salembier, P. Brigger, J. R. Casas, and M. Pardàs, ”Morphological operators for image and video compression,” IEEE Transactions on Image Processing, Vol. 5, pp. 881–897, 1996. · doi:10.1109/83.503906
[37] P. Salembier and L. Garrido, ”Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval,” IEEE Transactions on Image Processing, Vol. 9, No. 4, pp. 561–576, 2000. · doi:10.1109/83.841934
[38] P. Salembier, F. Marqués, M. Pardás, R. Morros, I. Corset, S. Jeannin, L. Bouchard, F. Meyer, and B. Marcotegui, ”Segmentation-based video coding system allowing the manipulation of objects,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 7, pp. 60–73, 1997. · doi:10.1109/76.554418
[39] P. Salembier and J. Serra, ”Flat zones filtering, connected operators and filters by reconstruction,” IEEE Transactions Image Processing, Vol. 4, No. 8, pp. 1153–1160, 1995. · doi:10.1109/83.403422
[40] G.M. Schuster and A.K. Katsaggelos, Rate-Distortion Based Video Compression. Kluwer Academic Publishers, 1997.
[41] Y. Shoham and A. Gersho, ”Efficient bit allocation for an arbitrary set of quantizers.” IEEE Trans. on Acoust., Speech, Signal Processing, Vol. 36, No. 9, pp. 1445–1453, 1988. · Zbl 0709.94610 · doi:10.1109/29.90373
[42] J. Serra, Image Analysis and Mathematical Morphology, Academic Press: New York, 1982. · Zbl 0565.92001
[43] T. Sikora, ”The MPEG-7 visual standard for content description - an overview.” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 11, pp. 696–702, 2001. · Zbl 05451404 · doi:10.1109/76.927422
[44] P. Soille, Morphological Image Analysis. Springer Verlag, 2003. · Zbl 1012.68212
[45] A. Solé, ”Geometric image coding, filtering and restoration,” PhD thesis, Universitat Pompeu Fabra, 2002.
[46] L. Vincent, ”Morphological area openings and closings for grey-scale images,” in Proceedings of the Workshop Shape in Picture: Mathematical Description of Shape in Gray-Level Images. Driebergen, The Netherlands, pp. 197–208, 1994.
[47] L. Vincent and P. Soille, ”Watersheds in digital spaces: An efficient algorithm based on Immersion simulations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 6, pp. 583–598, 1991. · Zbl 05111651 · doi:10.1109/34.87344
[48] M.J. Weinberger, G. Seroussi, and G. Sapiro, ”The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS,” IEEE Transactions on Image Processing Vol. 9, No. 8, pp. 1309–1324, 2000. · doi:10.1109/83.855427
[49] M. Wertheimer, ”Untersuchungen zur Lehre der Gestalt, II,” Psychologische Forschung, Vol. 4, pp. 301–350, 1923. · doi:10.1007/BF00410640
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.