Segmentation d'images couleur par partitions de Voronoï
Color Image Segmentation by Voronoi Partitions
OPEN ACCESS
We address the issue of low-level segmentation of color images. The proposed approach is based on the formulation of the problem as a generalized Voronoi partition of the image domain. In this context, a segmentation is determined by the definition of a distance between points of the image and the selection of a set of sites. The distance is defined by considering the low-level attributes of the image and, particularly, the color information. We divide the segmentation task in three successive sub-tasks, treated in the framework of Voronoi partitions: pre-segmentation, hierarchical representation and contour extraction.
Résumé
Nous étudions le problème de la segmentation de bas niveau pour les images couleur. L'approche proposée consiste à modéliser la segmentation d'une image comme une partition de Voronoï généralisée de son domaine. Dans ce contexte, segmenter une image couleur revient à définir une distance appropriée entre points de l'image et à choisir un ensemble de sites. La distance est définie en considérant les attributs de bas niveau de l'image et, en particulier, l'information fournie par la couleur. La démarche adoptée repose sur la division du problème de la segmentation en trois sous-tâches successives, traitées dans le cadre des partitions de Voronoï: la pré-segmentation, la représentation hiérarchique et l'extraction de contours.
Image processing, image modelling, color segmentation, contour extraction, Voronoi partition and diagram, ultrametrics, mathematical morphology
Mots clés
Traitement d'images, modélisation des images, segmentation couleur, extraction de contours, partition et diagramme de Voronoï, ultramétriques, morphologie mathématique
[1] N.AHUJA, B.AN, B.SCHACHTER, Image representation using Voronoi tessellation, CVGIP, 29(3):286-295, March 1985.
[2] J.ANGULO, J.SERRA, Color segmentation by ordered mergings, In Proc. of IEEE International Conference on Image Processing (ICIP'03), 125-128, Barcelona, Spain, Sept. 2003.
[3] P.A. ARBELÁEZ, L.D. COHEN, Path variation and image segmentation, In Proc. EMMCVPR'03, 246-260, Lisbon, Portugal, July 2003.
[4] P.A. ARBELÁEZ, L.D. COHEN, Energy partitions and image segmentation, Journal of Mathematical Imaging and Vision, 20(1-2):43-57, 2004.
[5] F. AURENHAMMER, R. KLEIN, Handbook of Computational Geometry, chapter 5: Voronoi Diagrams, 201-290, Elsevier Science Publishing, 2000.
[6] J.M. BEAULIEU, M. GOLDBERG, Hierarchy in picture segmentation: a stepwise optimization approach, IEEE Trans. on PAMI, 11(2):150-163, February 1989.
[7] J.P. BENZÉCRI, L'Analyse des Données. Tome I: La Taxinomie, Dunod, Paris, 4ème édition, 1984.
[8] S. BEUCHER, F. MEYER, Mathematical Morphology in Image Processing, chapter 12 : The Morphological Approach to Segmentation : The Watershed Transformation, 433-481, Marcel Dekker, 1992.
[9] L.D. COHEN, R.KIMMEL, Global minimum for active contour models : A minimal path approach, International Journal of Computer Vision, 24(1):57-78, August 1997.
[10] L.D. COHEN, Multiple contour finding and perceptual grouping using minimal paths, Journal of Mathematical Imaging and Vision, 14(3):225-236, 2001.
[11] A.COLANTONI, P.TREMEAU, Regions adjacency graph applied to color image segmentation, IEEE Trans. on Image Processing, 9(4):735-744, 2000.
[12] T.DESCHAMPS, L.D. COHEN, Fast extraction of minimal paths in 3D images and applications to virtual endoscopy, Medical Image Analysis, 5(4):281-299, 2001.
[13] F. DIBOS, G. KOEPFLER, Segmentation d'images couleur par méthode variationnelle, In Actes du 16ème Colloque GRETSI, 367-370, 1997.
[14] E.W. DIJKSTRA, A note on two problems in connection with graphs, Numerische Mathemetic, 1:269-271, 1959.
[15] P.G.L. DIRICHLET, Uber die reduction der positiven quadratischen formen mit drei unbestimmten ganzen zalhen, J. Reine Angew. Mathematik, 40:209-227, 1850.
[16] C.FOWLKES, D.MARTIN, J.MALIK, Learning affinity functions for image segmentation: Combining patch-based and gradient-based approaches, In Proc. CVPR, 54-61, Madison, WI, USA, 2003.
[17] L.GARRIDO, P.SALEMBIER, D.GARCIA, Extensive operators in partition lattices for image sequence analysis, IEEE Trans. on Signal Processing, 66(2):157-180, April 1998, Special Issue on Video Sequence Segmentation.
[18] M.GRIMAUD, New measure of contrast : Dynamics, In Image Algebra and Morphological Processing III, SPIE, San Diego, USA, 1992.
[19] M. GROMOV, Metric Structures for Riemannian and NonRiemannian Spaces, Birkhauser, Boston, 1999.
[20] C.JORDAN, Sur la série de fourier, Comptes Rendus de l'Académie des Sciences. Série Mathématique., 92(5) :228-230, 1881.
[21] J.L. KELLEY, General Topology, Springer, 1975.
[22] R.KIMMEL, A.M. BRUCKSTEIN, Global shape from shading, Computer Vision and Image Understanding, 62(3): 360-369, 1995.
[23] R.KIMMEL, N.KIRYATI, A.M. BRUCKSTEIN, Distance maps and weighted distance transforms, Journal of Mathematical Imaging and Vision, 6 : 223-233, May 1996, Special Issue on Topology and Geometry in Computer Vision.
[24] R.KRUSE, A.RYBA, Data structures and program design in C++, Prentice Hall, New York, 1999.
[25] K.KURATOWSKI, Topology, volumeI, Academic Press, 1966.
[26] Ch. LANTUEJOUL, La Squelettisation et son Application aux Mesures Topologiques des Mosaïques Polycristallines, PhD thesis, École des Mines de Paris, 1978.
[27] R.MALLADI, J.A. SETHIAN, A unified approach to noise removal, image-enhancement, and shape recovery, IEEE Trans. on Image Processing, 5(11):1554-1568, November 1996.
[28] P.MARAGOS, M.A. BUTT, Curve evolution, differential morphology and distance transforms applied to multiscale and eikonal problems, Fundamenta Informaticae, 41:91-129, 2000.
[29] D. MARTIN, C. FOWLKES, D. TAL, J. MALIK, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, In Proc. ICCV'01, volumeII, 416-423, Vancouver, Canada, 2001.
[30] D.MARTIN, C.FOWLKES, D.TAL, J.MALIK, Learning to detect natural image boundaries using local brightness, color and texture cues, IEEE Trans. on PAMI, 26(5):530-549, 2004.
[31] N.MAYYA, V.T. RAJAN, Voronoi diagrams of polygons: A framework for shape representation, Journal of Mathematical Imaging and Vision, 6(4):355-378, December 1996.
[32] F. MEYER, A. OLIVERAS, P. SALEMBIER, C. VACHIER, Morphological tools for segmentation: Connected filters and watersheds, Annals of Telecommunications, 52(7-8):367-379, 1997.
[33] F.MEYER, Hierarchies of partitions and morphological segmentation, In Michael Kerckhove, editor, Scale Space and Morphology in Computer Vision, 161-182, 2001.
[34] F. MEYER, An overview of morphological segmentation, International Journal of Pattern Recognition and Artificial Intelligence, 15(7):1089-1118, 2001.
[35] P.F.M. NACKEN, Image segmentation by connectivity preserving relinking in hierarchical graph structures, PR, 28(6):907-920, June 1995.
[36] L. NAJMAN, M. SCHMITT, Geodesic saliency of watershed contours and hierarchical segmentation, IEEE Trans. on PAMI, 18(12):1163-1173, 1996.
[37] A. OKABE, B. BOOTS, K. SUGIHARA, S. N. CHIU, Spatial Tessellations : Concepts and Applications of Voronoi Diagrams, Wiley, 2 édition, 2002.
[38] X.REN, J. MALIK, Learning a classification model for segmentation, In Proc. ICCV'03, 10-17, 2003.
[39] L.I. RUDIN, S.OSHER, E.FATEMI, Nonlinear total variation based noise removal algorithms, Physica D, 60:259-268, 1992.
[40] J.SERRA, P.SALEMBIER, Connected operators and pyramids, In SPIE, editor, Image Algebra and Mathematical Morphology, volume 2030, 65-76, San Diego, CA, July 1993.
[41] J.SERRA, A lattice approach to segmentation, Rapport Technique CMM - École des Mines de Paris, N-02/04/MM, 2004.
[42] M.TUCERYAN, A.K. JAIN, Texture segmentation using Voronoi polygons, IEEE Trans. on PAMI, 12(2):211-216, February 1990.
[43] Z.TU, S.C. ZHU, Image segmentation by data driven markov chain monte carlo, IEEE Trans. on PAMI, 24(5):657-673, 2002.
[44] I. VANHAMEL, I. PRATIKAKIS, H. SAHLI, Multiscale gradient watersheds of color images, IEEE Trans. on Image Processing, 12(6), 2003.
[45] G.M. VORONOI, Nouvelles applications des paramètres continus à la théorie des formes quadratiques. premier mémoire: Sur quelques proprietés des formes quadratiques positives parfaites, Journal für die Reine und Angewandte Mathematik, 133:97-178, 1907.
[46] G. WYSZECKI, W. S. STILES, Color Science : Concepts and Methods, Quantitative Data and Formulas, J. Wiley and Sons, 1982.
[47] W.YU, J.FRITTS, F.SUN, A hierarchical image segmentation algorithm, In Proc. ICME'02, 221-224, August 2002.