×

zbMATH — the first resource for mathematics

Comparison to two ascendant hierarchical classification criteria under a contiguity constraint. Application to image processing. (Comparaison de deux critères en classification ascendante hiérarchique sous contrainte de contiguïté. Application en imagerie numérique.) (French. English summary) Zbl 1455.62126
Summary: We analyse an algorithm of ascendant hierarchical classification under contiguity constraint and using the aggregation principle of reciprocal nearest neighbors. This algorithm is situated in the general framework of quick ascendant hierarchical classification algorithms. Two cluster merging criteria are studied. The former is the classical inertia Ward criterion and the latter consists of the maximal likelihood linkage family criteria. A new contiguity version of this criterion proves its efficiency in image segmentation. One major feature of our algorithm is the linear nature of the computational complexity. New strategies concerning multiple aggregation in the class formation and contiguity notion are positively evaluated in terms of quality and efficiency. We establish mathematically and experimentally how the used criterion influences inversion possibility in the tree building. Finally, comparative results of both types of criteria in image segmentation on satellite pictures are discussed.
MSC:
62H30 Classification and discrimination; cluster analysis (statistical aspects)
62-08 Computational methods for problems pertaining to statistics
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
PDF BibTeX XML Cite
Full Text: Link
References:
[1] BACHAR, K.. Contributions en analyse factorielle et en classification ascendante hiérarchique sous contrainte de contiguïté. Applications à la segmentation d’images. PhD thesis, Université de Rennes 1, Décembre 1994.
[2] BACHAR, K. and LERMAN, I.C.. Statistical conditions for a linear complexity for an algorithm of hierarchical classification under constraint of contiguity. In Bock H.-H. Rizzi A., Vichi M., editor, Advances in Data Science and Classification/ IFCS’98, pages 131-136. Springer-Verlag, 1998. · Zbl 1052.62525
[3] BACHAR, K. and LERMAN, I.C.. Étude d’un comportement paramétré de CAHCVR sur des données réelles en imagerie numérique. In Melfi G. Dodge Y., editor, Méthodes et Perspectives en Classification, pages 63-66. Presses Académique Neuchâtel, 2003.
[4] BACHAR, K. and LERMAN, I.C.. Fixing parameters in the constrained hierarchical classification method : Application to digital image segmentation. In Banks D. et al., editor, Classification Clustering and Data Mining Applications, pages 85-94. Springer, 2004.
[5] BARTHELEMY, J.P. and GUENOCHE, A.. Trees and Proximity Representations. J. Wiley, 1991. · Zbl 0790.05021
[6] BENZECRI, J.P.. Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques. Les Cahiers de l’Analyse des Données, (VII) : 209-218, 1982. · Zbl 0492.62049
[7] BRUYNOOGHE, M.. Classification ascendante hiérarchique des grands ensembles de données ; un algorithme rapide fondé sur la construction des voisinages réductibles. Les Cahiers de l’Analyse des Données, (III) : 7-33, 1978.
[8] BRUYNOOGHE, M.. Nouveaux algorithmes en classification automatique applicables aux très grands ensembles de données, rencontrés en traitement d’images et en reconnaissance des formes. PhD thesis, Thèse d’État, Université de Paris 6, janvier 1989.
[9] DE RAHM, C.. La classification hiérarchique ascendante selon la méthode des voisins réciproques. Les Cahiers de l’Analyse des Données, (V, no 2) : 135-144, 1980.
[10] GORDON, A.D.. A survey of constrained classification. Computational Statistics and Data Analysis, (1) : 17-29, 1996. · Zbl 0900.62313
[11] HANSEN, P., JAUMARD, B., MEYER, C., SIMEONE, B., and DORING, V.. Maximum split clustering under connectivity constraints. Journal of Classification, (20) : 143-180, 2003. · Zbl 1083.91063
[12] JUAN, J.. Programme de classification hiérarchique par l’algorithme de recherche en chaîne des voisins réciproques. Les Cahiers de l’Analyse des Données, (VII) : 219-225, 1982. · Zbl 0505.62042
[13] LANCE, G.N. and WILLIAMS, W.T.. A general theory of classification sorting strategies : clustering systems. Computer Journal, (10) : 271-277, 1967.
[14] LEBART, L.. Programme d’agrégation avec contraintes. Les Cahiers de l’Analyse des Données, (III(3)) : 275-287, 1978.
[15] LERMAN, I.C.. Sur l’analyse des données préalable à une classification automatique. proposition d’une nouvelle mesure de similarité. Mathématiques et Sciences Humaines, (32) : 5-15, 1970. · Zbl 0221.62021
[16] LERMAN, I.C.. Classification et analyse ordinale des données. Dunod, 1981.
[17] LERMAN, I.C.. Sur la signification des classes issues d’une classification automatique. In J. Felsenstein, editor, Numerical Taxonomy, pages 179-198. Springer-Verlag, 1983.
[18] LERMAN, I.C.. Construction d’un indice de similarité entre objets décrits par des variables d’un type quelconque. application au problème du consensus en classification. Revue de Statistique Appliquée, (XXXV(2)) : 39-60, 1987. · Zbl 0615.62068
[19] LERMAN, I.C.. Formules de réactualisation en cas d’agrégations multiples. RAIRO, série R.O., (vol 23, no 2) : 151-163, 1989. · Zbl 0674.62042
[20] LERMAN, I.C.. Foundations of the likelihood linkage analysis(lla) classification method. Applied Stochastic Models and Data Analysis, (vol 7,1) : 6376, march 1991. · Zbl 0800.62320
[21] LERMAN, I.C.. Conception et analyse de la forme limite d’une famille de coefficients statistiques d’association entre variables relationnelles I. Revue Mathématiques Informatique et Sciences Humaines, (118) : 35-52, 1992. · Zbl 0851.62039
[22] LERMAN, I.C.. Conception et analyse de la forme limite d’une famille de coefficients statistiques d’association entre variables relationnelles II. Revue Mathématique Informatique et Sciences Humaines, (119) : 75-100, 1992. · Zbl 0851.62040
[23] LERMAN, I.C. and BACHAR, K.. Agrégations multiples et contraintes de contiguïté dans la classification ascendante hiérarchique utilisant les voisins réciproques et le critère de la vraisemblance des liens. In 8-èmes Rencontres de la Société Francophone de Classification, pages 232-237. Université Pointe-à-Pitre, 2001.
[24] LERMAN, I.C. and BACHAR, K.. Construction et justification d’une méthode de classification ascendante hiérarchique accélérée fondée sur le critère de la vraisemblance du lien maximal en cas de données de contiguïté. Application en imagerie numérique. Rapport de Recherche 1616, IRISA, avril 2004.
[25] LERMAN, I.C. and PETER, Ph.. Indice probabiliste de vraisemblance du lien entre objets quelconques ; analyse comparative entre deux approches. Revue de Statistique Appliquée, (LI(1)) : 5-35, 2003.
[26] LERMAN, I.C., PETER, Ph., and LEREDDE, H.. Principes et calculs de la méthode implantée dans le programme CHAVL 1-ère partie. La Revue de Modulad, (12) : 33-70, Décembre 1993.
[27] LERMAN, I.C., PINTO da COSTA, J.F., and SILVA, H.. Validation of very large data sets clustering by means of a nonparametric criterion. In A. Sokolowski K. Jajuga and H.-H. Bock, editors, Classification, Clustering and Data Analysis, Recent Advances and Applications, pages 147-157. Springer-Verlag, 2002. · Zbl 1032.62061
[28] MONESTIEZ, P.. Méthode de classification automatique sous contraintes spatiales. Statistique et Analyse des Données, (3) : 75-84, 1977.
[29] MURTAGH, F.. A survey of algorithms for contiguity-constrained clustering and related problems. The Computer Journal, (28) : 82-88, 1985.
[30] NICOLAÜ, F.C. and BACELAR-NICOLAÜ, H.. Some trends in the classification of variables. In Data Science, Classification and Related Methods, IFCS’96, pages 89-98. Springer-Verlag, 1996. · Zbl 0894.62075
[31] OUALI-ALLAH, M.. Analyse en préordonnance des données qualitatives. Application aux données numériques et symboliques. PhD thesis, Université de Rennes 1, Décembre 1991.
[32] PAUWELS, E.J. and FREDERIX, G.. Finding salient regions in images. Computer Vision and Image Understanding, (75) : 73-85, 1999.
[33] PERRUCHET, C.. Constrained agglomerative hierarchical classification. Pattern Recognition, (16(2)) : 213-217, 1983.
[34] PETER, P., LEREDDE, H., and LERMAN, I.C.. Notice du programme CHAVLH (Classification Hiérarchique par Analyse de la Vraisemblance des Liens en cas de variables Hétérogènes). Dépôt APP (Agence pour la Protection des Programmes) IDDN.FR.001.240016.000.S.P.2006.000.20700, Université de Rennes 1, Décembre 2005.
[35] PRODHOMME, A.. Indices d’explication des classes obtenues par une méthode de classification hiérarchique respectant la contrainte de contiguïté spatiale. Application à la viticulture Girondine et à la construction de logements dans les Bouches-du Rhône. PhD thesis, Université de Rennes 1, Décembre 1980.
[36] TABB, M. and AHUJIA, N.. Multiscale image segmentation by integrated edge and region detection. IEEE Trans. Image Processing, (6) : 642-655, 1997.
[37] WARD, J.H.. Hierarchical grouping to optimise an objective function. Journal of the American Statistical Association, (58) : 238-244, 1963.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.