💻 computer science

Mathematical Morphology in Machine Learning

Cet article introduit la morphologie mathématique dans l'apprentissage automatique en proposant un algorithme de partitionnement par reconstruction morphologique rapide, une nouvelle métrique de distance hybride qui surpasse considérablement les distances standards en termes de vitesse et de précision, ainsi que de nouveaux classifieurs qui modélisent de manière unique la forme, la densité et l'information fractale.

Auteurs originaux : Erick Oliveira Rodrigues, Aura Conci

Publié 2026-06-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Erick Oliveira Rodrigues, Aura Conci

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous ayez une chambre en désordre remplie de jouets éparpillés sur le sol. Votre objectif est de les trier en tas. La plupart des programmes informatiques qui effectuent ce genre de tâche (appelée « apprentissage automatique » ou machine learning) observent les jouets et essaient de les regrouper en fonction de leur distance. Ils pourraient dire : « Ces deux blocs rouges sont proches, donc ils vont dans un tas », ou « Ces voitures bleues sont loin, donc elles vont dans un autre ».

Cependant, les auteurs de cet article, Erick Oliveira Rodrigues et Aura Conci, soutiennent que cette approche néglige un détail crucial : la forme et la densité. Parfois, deux jouets sont proches mais appartiennent à des groupes différents parce qu'ils font partie d'un amas dense et serré, tandis que d'autres jouets sont loin mais font partie du même groupe lâche.

Cet article présente une nouvelle façon de penser le tri de données en utilisant un domaine appelé morphologie mathématique. Ne voyez pas cela comme un problème de mathématiques, mais plutôt comme un jeu de bulles qui s'étendent.

L'approche par « Bulles » pour le tri (Clustering)

Au lieu de simplement mesurer la distance, les auteurs proposent un algorithme appelé ensembles k-morphologiques (k-MS).

Imaginez que vous déposiez une goutte d'eau sur une éponge. L'eau se répand, remplissant chaque recoin qu'elle peut atteindre. Si l'éponge possède deux îles de zones sèches séparées, l'eau remplira la première île, s'arrêtera, puis finira par remplir la seconde.

L'ancienne méthode : La plupart des algorithmes essaient de deviner où se trouvent les îles en traçant des lignes entre les points.
La nouvelle méthode (k-MS) : L'algorithme agit comme cette eau. Il commence avec un petit « élément structurant » (comme une petite éponge) et l'étend. Il remplit d'abord les zones denses. Si l'eau rencontre un mur (un vide dans les données), elle s'arrête.
Le résultat : Cette méthode sépare naturellement les groupes de données « denses » du « bruit » épars. C'est comme être capable de faire la différence entre une foule de gens très serrés et quelques individus isolés, même s'ils se tiennent les uns à côté des autres.

Pourquoi est-ce génial ?

Cela nettoie le désordre : S'il y a quelques jouets égarés (bruit) sur le sol, cette méthode les ignore naturellement ou les regroupe dans leur propre petit tas inutile, plutôt que de les forcer dans un vrai groupe.
C'est rapide : Parce qu'elle fonctionne comme un simple processus d'expansion, cela peut être fait très rapidement, surtout sur les puces modernes (GPU) qui sont conçues pour effectuer de nombreuses petites tâches à la fois.
Elle sait quand s'arrêter : L'algorithme possède un « sens intrinsèque » du nombre de groupes qu'il peut réellement créer en fonction de la forme des données, plutôt que de simplement forcer aveuglément un nombre spécifique de groupes.

Le raccourci de l'« Octogone » (Nouvelle métrique de distance)

La deuxième contribution majeure est une nouvelle façon de mesurer la distance entre deux points.

Dans le monde de l'informatique, la distance entre deux points est généralement calculée de deux manières :

Le « Bloc de ville » (Manhattan/Chebyshev) : Imaginez que vous marchez dans une ville avec un quadrillage de rues. Vous ne pouvez marcher que vers le Nord, le Sud, l'Est ou l'Ouest. La distance est le nombre de pâtés de maisons parcourus. C'est rapide à calculer, mais c'est un peu trop « carré » et cela ne ressemble pas à une ligne droite.
La « Ligne droite » (Euclidienne) : Imaginez voler comme un oiseau en ligne droite. C'est la distance la plus précise, mais elle est très difficile et lente à calculer pour les ordinateurs, surtout quand on doit le faire des millions de fois.

Les auteurs ont inventé une distance hybride qui ressemble à un octogone (une forme à 8 côtés).

Si vous regardez la distance du « Bloc de ville », elle ressemble à un carré.
Si vous regardez la distance de l'« Œil de l'oiseau », elle ressemble à un cercle.
La nouvelle distance des auteurs ressemble à un octogone.

Pourquoi est-ce important ?
Un octogone est beaucoup plus proche d'un cercle qu'un carré ne l'est, ce qui donne une sensation de « ligne droite » plus précise. Mais parce qu'il est construit à partir de règles mathématiques simples, il se calcule presque aussi vite que la méthode du « Bloc de ville ».

L'article affirme que cette règle « octogone » est :

329 fois plus rapide que la méthode standard de l'« Œil de l'oiseau » (Euclidienne).
1,3 fois plus rapide que la méthode du « Bloc de ville » (Manhattan).
Plus précise : Lors de tests sur 33 ensembles de données différents (comme le tri d'e-mails ou l'identification d'images), cette nouvelle règle a aidé un classificateur (un programme qui devine ce qu'est un objet) à obtenir la bonne réponse plus souvent que les 14 autres règles testées.

La vue d'ensemble

Les auteurs disent essentiellement : « Nous avons pris un outil visuel utilisé pour analyser les formes (la morphologie mathématique) et nous l'avons appliqué à l'apprentissage automatique. Nous avons construit un trieur par « expansion de bulles » qui respecte la forme et la densité des données, et nous avons inventé une nouvelle « règle octogonale » qui est incroyablement rapide et précise pour les ordinateurs. »

Ils ont testé ces idées sur des données réelles et ont constaté que leurs méthodes sont plus rapides et souvent plus précises que les meilleures techniques actuelles, tout en étant capables de gérer le « bruit » (données désordonnées) sans nécessiter d'étapes supplémentaires pour les nettoyer au préalable.

Résumé Technique : Morphologie Mathématique en Apprentissage Automatique

Énoncé du Problème
Bien que la morphologie mathématique (MM) soit une théorie établie en informatique visuelle pour l'analyse d'objets graphiques basés sur la forme, la taille et la convexité, son application en apprentissage automatique reste sous-utilisée. Les techniques d'apprentissage automatique existantes échouent souvent à exploiter suffisamment les informations de forme et de densité. De plus, les méthodes actuelles de partitionnement (clustering) et de classification reposent soit sur des heuristiques qui ne respectent pas pleinement les principes de la MM, soit manquent de la capacité de modéliser simultanément l'information fractale, la forme et la densité. De plus, dans les environnements discrets (tels que le traitement sur GPU), les métriques de distance standard présentent des compromis : la distance euclidienne est coûteuse en calcul et nécessite une quantification, tandis que les distances de Chebyshev et de Manhattan sont rapides mais de nature « carrée », échouant à approximer efficacement l'itération circulaire de la distance euclidienne.

Méthodologie
Le document propose un cadre intégrant la morphologie mathématique dans l'apprentissage automatique à travers trois composantes principales :

Algorithme de Partitionnement par Ensembles Morphologiques k (k-MS) :
- Cet algorithme utilise la reconstruction morphologique plutôt que des opérations binaires (contrairement aux précédents algorithmes de partitionnement par morphologie binaire).
- Il opère sur une grille où les instances de données sont cartographiées. Un élément structurant $B$ (contenant initialement des zéros) et un masque $M$ sont utilisés pour effectuer la reconstruction.
- L'algorithme emploie une variable interne $\delta$ pour contrôler la taille de l'élément structurant. Il augmente de manière itérative $\delta$ pour faire croître les clusters jusqu'à ce qu'un état idempotent soit atteint ou qu'un nombre prédéfini de clusters ( $k$ ) soit approché.
- Si le nombre d'indices de clusters uniques dépasse $k$ , $\delta$ est incrémenté ; si la reconstruction devient non-idempotente (fusion de clusters), $\delta$ est réinitialisé à 1, et le processus se répète.
- La méthode segmente intrinsèquement le bruit en petits clusters indépendants sans coûts de traitement supplémentaires.
Nouvelle Métrique de Distance :
- Pour optimiser l'itération de voisinage dans les espaces discrets (spécifiquement pour l'implémentation sur GPU), une nouvelle métrique de distance est proposée.
- Cette métrique est une combinaison pondérée de la distance de Chebyshev et de la distance de Minkowski (Équation 1 : $d_{R^p}(x,y) = w_1 \sum |x_i - y_i|^p + w_2 \max |x_i - y_i|$ ).
- En ajustant les poids $w_1$ et $w_2$ ainsi que le paramètre $p$ , la métrique peut converger vers des comportements de type Chebyshev ou Minkowski.
- En 2D ( $R^2$ ), cette distance produit une forme octogonale, ce qui est géométriquement plus proche de la distance euclidienne circulaire que les formes carrées produites par les distances de Manhattan ou de Chebyshev.
Classificateurs Morphologiques :
- Les auteurs proposent des classificateurs qui font croître les instances d'entraînement par des dilatations afin de couvrir l'espace non étiqueté.
- Ces classificateurs sont implémentés sur des processeurs graphiques (GPU) pour exploiter le traitement parallèle, où les cellules de la grille croissent simultanément.
- Lorsque des intersections se produisent lors de la croissance, un schéma de vote détermine l'étiquette.

Contributions Clés

Algorithme k-MS : Une technique de partitionnement qui préserve la forme et la densité, offre une notion intrinsèque du nombre maximal de clusters créables (indépendamment de $k$ ), et élimine le bruit sans surcharge de calcul supplémentaire.
Métrique de Distance Hybride : Une nouvelle métrique combinant les distances de Chebyshev et de Minkowski qui offre un équilibre entre l'efficacité de calcul des distances « carrées » et la fidélité géométrique de la distance euclidienne.
Implémentation Optimisée pour GPU : Le développement de classificateurs morphologiques et de calculs de distance spécifiquement adaptés aux environnements GPU de bas niveau, évitant les accès lents aux noyaux (kernels) et les tailles de noyaux indéfinies.
Évaluation Complète : Tests approfondis de la métrique de distance proposée à l'aide du classificateur k-plus proches voisins (k-NN) sur 33 jeux de données UCI.

Résultats

Efficacité du Partitionnement : L'algorithme k-MS s'est avéré plus rapide que les techniques de partitionnement basées sur la densité de pointe, tout en offrant des caractéristiques uniques comme l'élimination du bruit et la préservation de la forme. Dans les analyses de temps par rapport au k-Means parallèle (CPU), le k-MS a démontré des performances compétitives ou supérieures, particulièrement à mesure que le nombre de clusters augmentait grâce aux optimisations d'arrêt précoce.
Performance de la Métrique de Distance :
- Vitesse : Dans les tâches d'itération de voisinage discret dans $Z^2$ , la distance proposée était environ 1,3 fois plus rapide que la distance de Manhattan et 329,5 fois plus rapide que la distance euclidienne.
- Précision : Évaluée avec k-NN sur 33 jeux de données UCI, la distance proposée a atteint des précisions supérieures à la moyenne de 14 autres distances dans 26 cas sur 33. Elle a obtenu la meilleure précision unique dans 9 cas sur 33.
Partitionnement Visuel : Dans les jeux de données bruités, k-MS a réussi à séparer les clusters authentiques et les valeurs aberrantes (outliers), alors que d'autres algorithmes (comme Chameleon) ont parfois regroupé les valeurs aberrantes avec les clusters authentiques, et d'autres (comme Mitosis) ont échoué à séparer le bruit.

Signification et Revendications
Les auteurs affirment que ce travail représente la première proposition de techniques de classification et de partitionnement reposant entièrement sur des techniques de morphologie mathématique, allant au-delà des connexions heuristiques. Le document soutient qu'aucun autre classificateur dans la littérature actuelle ne peut modéliser correctement la forme, la densité et l'information fractale simultanément.

La signification de ce travail réside dans le pont jeté entre la théorie de l'informatique visuelle et l'apprentissage automatique, fournissant des outils qui sont non seulement théoriquement solides concernant la forme et la densité, mais aussi informatiquement efficaces pour le matériel moderne (GPU). La métrique de distance proposée est mise en avant comme une solution pratique pour les environnements de calcul haute performance où la distance euclidienne est trop lente et où les distances de Manhattan/Chebyshev manquent de fidélité géométrique suffisante. Les auteurs notent que ces contributions ont déjà donné lieu à plusieurs publications dans des revues réputées telles que Pattern Recognition et Pattern Recognition Letters.

L'approche par « Bulles » pour le tri (Clustering)

Le raccourci de l'« Octogone » (Nouvelle métrique de distance)

La vue d'ensemble

Résumé Technique : Morphologie Mathématique en Apprentissage Automatique

Articles similaires