Comparaison de deux critères en classification ascendante hiérarchique sous contrainte de contiguïté. Application en imagerie numérique

Lerman, Israël-César; Bachar, Kaddour

Journal de la Société française de statistique & Revue de statistique appliquée, Tome 149 (2008) no. 2, pp. 45-74.

Nous analysons une algorithmique de classification ascendante hiérarchique sous contrainte de contiguïté par agrégation des voisins réciproques en la situant dans le contexte général des algorithmes rapides de classification ascendante hiérarchique. Surtout, nous la déclinons selon deux types de critères. Il s'agit d'une part, du critère de Ward de la variation de l'inertie expliquée et d'autre part, d'une famille paramétrée du critère VL de la vraisemblance du lien maximal. Le contexte applicatif est celui de la segmentation d'image. On souligne la nature linéaire de la complexité algorithmique que nous montrons expérimentalement. L'influence algorithmique de la notion de contiguïté retenue est mise en évidence. Une nouvelle stratégie mettant en oeuvre l'agrégation multiple dans la formation des classes montre tout son intérêt. On étudie aussi bien sur le plan théorique qu'expérimental la possibilité d'inversions compte tenu du type de critère utilisé. Nous terminons en proposant une analyse comparative des résultats sur des données réelles en imagerie satellitaire.

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.

Mot clés : classification hiérarchique, graphe de contiguïté, agrégation multiple, complexité, inversion, traitement d'image
Mots clés : hierarchical classification, contiguity graph, multiple aggregation, complexity, inversion, image processing

[1] K. Bachar. 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] K. Bachar and I.C. Lerman. 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. | MR | Zbl

[3] K. Bachar and I.C. Lerman. É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] K. Bachar and I.C. Lerman. 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. | MR

[5] J.P. Barthelemy and A. Guenoche. Trees and Proximity Representations. J. Wiley, 1991. | MR | Zbl

[6] J.P. Benzecri. 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. | Numdam | Zbl

[7] M. Bruynooghe. 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] M. Bruynooghe. 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] C. De Rahm. 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] A.D. Gordon. A survey of constrained classification. Computational Statistics and Data Analysis, (1) : 17-29, 1996. | MR | Zbl

[11] P. Hansen, B. Jaumard, C. Meyer, B. Simeone, and V. Doring. Maximum split clustering under connectivity constraints. Journal of Classification, (20) : 143-180, 2003. | MR | Zbl

[12] J. Juan. 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. | Numdam | Zbl

[13] G.N. Lance and W.T. Williams. A general theory of classification sorting strategies : clustering systems. Computer Journal, (10) : 271-277, 1967.

[14] L. Lebart. Programme d'agrégation avec contraintes. Les Cahiers de l'Analyse des Données, (III(3)) : 275-287, 1978.

[15] I.C. Lerman. 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. | Numdam | MR | Zbl

[16] I.C. Lerman. Classification et analyse ordinale des données. Dunod, 1981. | MR

[17] I.C. Lerman. Sur la signification des classes issues d'une classification automatique. In J. Felsenstein, editor, Numerical Taxonomy, pages 179-198. Springer-Verlag, 1983.

[18] I.C. Lerman. 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. | Numdam | MR | Zbl

[19] I.C. Lerman. Formules de réactualisation en cas d'agrégations multiples. RAIRO, série R.O., (vol 23, no 2) : 151-163, 1989. | Numdam | MR | Zbl

[20] I.C. Lerman. Foundations of the likelihood linkage analysis(lla) classification method. Applied Stochastic Models and Data Analysis, (vol 7,1) : 6376, march 1991. | MR | Zbl

[21] I.C. Lerman. 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. | Numdam | MR | Zbl

[22] I.C. Lerman. 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. | Numdam | MR | Zbl

[23] I.C. Lerman and K. Bachar. 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] I.C. Lerman and K. Bachar. 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] I.C. Lerman and Ph. Peter. Indice probabiliste de vraisemblance du lien entre objets quelconques ; analyse comparative entre deux approches. Revue de Statistique Appliquée, (LI(1)) : 5-35, 2003. | Numdam

[26] I.C. Lerman, Ph. Peter, and H. Leredde. 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] I.C. Lerman, J.F. Pinto Da Costa, and H. Silva. 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. | MR | Zbl

[28] P. Monestiez. Méthode de classification automatique sous contraintes spatiales. Statistique et Analyse des Données, (3) : 75-84, 1977.

[29] F. Murtagh. A survey of algorithms for contiguity-constrained clustering and related problems. The Computer Journal, (28) : 82-88, 1985.

[30] F.C. Nicolaü and H. Bacelar-Nicolaü. Some trends in the classification of variables. In Data Science, Classification and Related Methods, IFCS'96, pages 89-98. Springer-Verlag, 1996. | Zbl

[31] M. Ouali-Allah. 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] E.J. Pauwels and G. Frederix. Finding salient regions in images. Computer Vision and Image Understanding, (75) : 73-85, 1999.

[33] C. Perruchet. Constrained agglomerative hierarchical classification. Pattern Recognition, (16(2)) : 213-217, 1983.

[34] P. Peter, H. Leredde, and I.C. Lerman. 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] A. Prodhomme. 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] M. Tabb and N. Ahujia. Multiscale image segmentation by integrated edge and region detection. IEEE Trans. Image Processing, (6) : 642-655, 1997.

[37] J.H. Ward. Hierarchical grouping to optimise an objective function. Journal of the American Statistical Association, (58) : 238-244, 1963. | MR