Codes-barres et reconnaissance de forme

Des maths abstraites au service d’un problème concret.

Piste noire Le 15 juillet 2020  - Ecrit par  Vincent Humilière Voir les commentaires

On l’observe quotidiennement, les ordinateurs deviennent de plus en plus forts pour comprendre et interpréter le monde qui les entoure : reconnaissance de caractères, appareils photo détectant les visages, essais de voitures autonomes, etc. [1]. Ces progrès impressionnants s’expliquent par l’amélioration notoire de leurs capacités de calcul, mais également par l’inventivité brillante des humains qui les mettent au point !
Le but de cet article est d’expliquer une très belle idée mathématique (parmi de nombreuses !) utilisée à des fins de reconnaissance de forme par ordinateur.

Pour écrire cet article, je me suis appuyé principalement sur l’article [CCSGMO-09], paru en 2009, et qui a eu un fort impact. Je remercie l’un des auteurs, Steve Oudot, d’avoir répondu à mes questions et de m’avoir gentiment transmis certaines des images apparaissant dans l’article.

Voici le problème. On présente de manière aléatoire à notre ordinateur deux formes ou deux images, par exemple parmi celles apparaissant dans l’image ci-dessus. On voudrait que l’ordinateur soit capable de déterminer si ces deux formes représentent le même animal ou le même visage, éventuellement dans des positions différentes. Pour cela, nous allons associer à chaque forme un objet mathématique appelé code-barres. Expliquer (dans les grandes lignes) comment obtenir le code-barres à partir d’une forme occupera la plus grande partie de l’article.

Ce code-barres a l’avantage d’être à la fois relativement facile à calculer pour un ordinateur, mais en même temps, d’être suffisamment compliqué pour pouvoir bien discriminer nos formes. On verra en particulier, que deux formes représentant le même animal mais dans des positions différentes auront des codes-barres très ressemblants. C’est cette surprenante propriété qui sera la clé de la méthode présentée ici.

Codes-barres

Voici ce que les mathématiciens ont convenu d’appeler code-barres :

Définition. Un code-barres est une collection finie d’intervalles [2], éventuellement de longueur infinie, avec répétitions possibles. On ne tient pas compte de l’ordre dans lequel les intervalles apparaissent.

Voici un exemple de code-barres :

Cela ne ressemble pas tout à fait à un code-barres de supermarché, mais on voit tout de même qu’il y a des « barres ». La terminologie vient aussi du fait, que l’on va utiliser les codes-barres pour encoder d’autres objets a priori beaucoup plus compliqués. Nous verrons cela plus loin.

La distance « goulot de bouteille »

Nous allons voir que l’on peut donner un sens à la « distance » entre deux codes-barres. Intuitivement, on dira que deux codes-barres sont proches si leurs grandes barres sont à peu près les mêmes, peu importe ce que sont leurs petites barres. Si l’on veut définir cette distance rigoureusement, voici comment l’on procède.

On fixe un nombre réel strictement positif $c>0$. On dit que deux codes-barres $B_1$ et $B_2$ sont $c$-proches si l’on peut passer de $B_1$ à $B_2$ en modifiant les extrémités des barres de $B_1$ avec une amplitude plus petite que $c$. Éventuellement cette opération peut amener à faire disparaître ou apparaître certaines barres de longueur plus petites que $2c$. Enfin, rappelez-vous qu’on ne tient pas compte de l’ordre des barres.

Définition La distance goulot de bouteille [3] entre deux codes-barres est le plus petit $c$ tel que ces deux codes-barres soient $c$-proches.

Voici deux code-barres. Voyez-vous à quelle distance ils sont ?

Réponse

Ils sont à distance 1.
L’image ci-dessous montre quelles barres disparaissent et quelles barres sont identiques quitte à bouger leurs extrémités d’au plus 1.

Plus tard dans cet article, nous expliquerons comment associer un code-barres à certaines formes géométriques. Il se trouvera que deux formes géométriques proches auront des codes-barres proches pour la distance goulot de bouteille, d’où l’intérêt pour la reconnaissance automatique de forme. Mais avant d’en arriver là, il nous faut faire un petit détour par un concept mathématique appelé « homologie ».

Homologie d’un graphe

Nous allons commencer par expliquer ce qu’est l’homologie sur des formes géométriques simples : les graphes. C’est suffisamment simple pour que l’on comprenne ce qu’il s’y passe et suffisamment compliqué pour que des phénomènes intéressants apparaissent.

Un graphe est simplement un ensemble de points avec des courbes les reliant, comme sur le dessin ci-dessous. L’usage est d’appeler « sommets » les points et « arêtes » les courbes.

On peut décrire la forme d’un graphe à l’aide de plusieurs nombres. Le nombre de morceaux disjoints du graphe en est un exemple. Pour un graphe $G$, on notera $b_0(G)$ ce nombre. Autre exemple, le nombre de boucles dans le graphe que l’on notera $b_1(G)$. Par boucle on entend ici un chemin (c’est à dire une suite d’arêtes mises bout à bout) terminant à son point de départ [4]. Dans l’exemple représenté ci-dessus on voit que $b_0(G)=2$ et $b_1(G)=4$.

Le lecteur attentif/expérimenté/critique pourrait remarquer que le « nombre de boucles » dans un graphe est une notion un peu ambiguë. Par exemple sur le dessin ci-dessous, doit-on compter seulement la boucle $a$ et la boucle $b$, ou alors plutôt les trois boucles $a$, $b$ et $c$ ? En réalité, il y aurait plein d’autres boucles, comme par exemple celle qui consiste à faire 3 fois le tour de $a$ puis deux fois le tour de $c$.

Dans cet exemple, $b_1(G)=2$.
Alors, qu’entend-on vraiment par « nombre de boucles », lorsque l’on définit $b_1(G)$ ? Si le graphe est planaire, c’est-à-dire peut être dessiné dans le plan, sans que deux arêtes distinctes ne s’intersectent, il est facile de définir $b_1(G)$. En effet, dans ce cas, si l’on découpe le plan le long du graphe, on obtient un certain nombre de morceaux disjoints. Le nombre $b_1(G)$ est simplement ce nombre de morceaux auquel on soustrait $1$ (le vérifier sur les exemples précédents !).
Mais certains graphes ne peuvent pas être dessinés dans le plan (voir cet article de Wikipedia), définir rigoureusement le « nombre de boucles » demande alors un peu plus d’explications, que l’on peut lire en déroulant le bloc ci-dessous, bien que ce ne soit pas nécessaire à la poursuite de la lecture.

Qu’est-ce que le « nombre de boucles » vraiment ?

Donnons-nous un graphe $G$ et imaginons que l’on positionne une petite ampoule jaune sur chaque sommet de $G$ et un petit bouton poussoir sur chacune des arêtes de $G$. Chacune des ampoules peut être allumée ou éteinte. Chacun des boutons poussoir a l’effet suivant : lorsque l’on appuie sur le bouton d’une certaine arête, il change l’état des deux ampoules situées à l’extrémité de l’arête considérée ; celles qui étaient éteintes s’allument et celles qui étaient allumées s’éteignent.

En partant d’une situation où toutes les ampoules sont éteintes, et étant donné un ensemble d’arêtes, on peut appuyer successivement sur les différents boutons de cet ensemble d’arêtes et regarder le résultat. Un ensemble d’arêtes pour lequel les appuis successifs donnent une situation où toutes les ampoules sont éteintes s’appelle un cycle.

Par exemple, si l’on appuie sur les trois boutons comme ci-dessous, toutes les ampoules finissent éteintes.

On en déduit que l’ensemble d’arêtes en vert ci-dessous forme un cycle.

Il y a toujours un cycle un peu idiot qui est le cycle vide, constitué d’aucune arête. En effet, si l’on n’appuie sur les boutons d’aucune arête le résultat est que les ampoules restent toutes éteintes ! Vous pouvez vérifier que dans notre exemple, il y a exactement 8 cycles, représentés en vert ci-dessous.

Il se trouve que les cycles peuvent aussi être additionnés. C’est simple, si $C$ et $C'$ sont deux cycles, on regarde les arêtes qui sont soit dans $C$, soit dans $C'$, mais qui ne sont pas à la fois dans les $C$ et $C'$. Il se trouve que l’ensemble de ces arêtes forme un nouveau cycle (exercice !) que l’on note $C+C'$.

Le dessin ci-dessous montre (en vert), le résultat de l’addition de deux cycles (en vert également) :

Nous pouvons enfin définir notre « nombre de boucles » $b_1(G)$.

Définition On dit que des cycles $C_1, \dots, C_k$ non vides sont indépendants si aucun d’entre eux ne peut être obtenu comme somme de certains des autres. Le nombre de boucles $b_1(G)$ est le plus grand entier positif $k$ pour lequel on puisse trouver $k$ cycles non vides indépendants. [5]

Voici trois cycles indépendants en nombre maximal. En effet, on peut voir que tout autre cycle non vide peut s’écrire comme somme de ceux-ci.

Il y a plein d’autres nombres que l’on peut définir à partir d’un graphe : le nombre de sommets, le nombre d’arêtes, le nombre de sommets où une seule arête arrive, etc. Alors pourquoi s’intéresser à ces deux nombres $b_0(G)$ et $b_1(G)$ en particulier ? La raison est que ces deux nombres ont la propriété de rester invariants par déformation du graphe, c’est-à-dire par l’opération consistant à « étirer un point pour en faire une arête » comme dans le dessin ci-dessous

et son inverse qui consiste à contracter une arête à deux extrémités distinctes pour en faire un point.

Cette propriété d’invariance par déformation est cruciale pour la théorie des codes-barres, en particulier pour les théorèmes que nous verrons plus bas.
En langage technique, on dit que $b_0(G)$ et $b_1(G)$ sont des « invariants homologiques ».

Graphes généralisés

On peut généraliser ce qui précède à des objets plus compliqués que des graphes que nous appellerons ici graphes généralisés. [6]

Un graphe généralisé est une forme que l’on obtient de la manière suivante. On part d’un nombre fini de points, auquel on adjoint des arêtes. Cela commence donc comme pour un graphe, mais on ne s’arrête pas là. On colle ensuite des triangles à notre graphe, comme sur le dessin ci-dessous (les triangles collés sont en vert) :

Bien sûr les triangles peuvent être courbés, mais ils ont bien trois côtés, comme des vrais triangles, et on les colle de telle sorte que chacun des côtés soit l’une des arêtes du graphe que l’on avait avant. On obtient une forme géométrique que l’on appellera « graphe généralisé de dimension 2 ».

Il n’y a pas de raison de s’arrêter ici. On colle ensuite des tétraèdres (qui sont la généralisation des triangles en 3D), de telle sorte que les faces des tétraèdres que l’on recolle soient parmi les triangles que nous avions préalablement collés. Le résultat obtenu est appelé graphe généralisé de dimension 3. Voici un exemple.

Dans cet exemple, les triangles sont en vert, les tétraèdres en jaune, mais pour des raisons pratiques, on n’a pas colorié en vert les faces du tétraèdre jaune. Dans la partie droite du dessin, on n’a pas rempli le tétraèdre et seuls apparaissent les quatre triangles qui forment sa surface.

On peut encore continuer en collant successivement des objets de dimension supérieure. Les mathématiciens appellent « $n$-simplexe » la généralisation des triangles en dimension $n$. On recolle donc des 4-simplexes, puis des 5-simplexes... Bien sûr, à partir de la dimension 4, on ne peut plus faire de dessins, c’est une construction abstraite. Mais on verra plus loin que des graphes généralisés de dimension arbitrairement grande peuvent apparaître dans des problèmes bien concrets.

Comme pour les graphes, on peut décrire la forme d’un graphe généralisé $G$ à l’aide de nombres.

Comme avant, on appelle $b_0(G)$ le nombre de morceaux disjoints et $b_1(G)$ le nombre de boucles. Sauf qu’il faut préciser que l’on ne compte ici que des boucles « non-remplies ». Par exemple, dans l’exemple tri-dimensionnel ci-dessus, $b_1(G)=1$ car un seul triangle n’est pas rempli.
On peut continuer et appeler $b_2(G)$ le nombre de « cavités » non remplies. Toujours dans l’exemple tri-dimensionnel ci-dessus, on a $b_2(G)=1$ car il y a une seule cavité non-remplie, qui est le tétraèdre de la partie de droite.

On peut continuer ainsi et définir $b_3(G)$, $b_4(G)$... On pourrait même le faire rigoureusement avec des ampoules et des interrupteurs, comme dans le bloc déroulant plus haut, mais cela nous emmènerait trop loin. Ces nombres s’appellent nombres de Betti de $G$.

Tous ces nombres ont la propriété d’être invariants par déformation du graphe généralisé, c’est-à-dire que si l’on étire un sommet (ou une arête, ou un triangle, ou n’importe quel $n$-simplexe) en un simplexe de dimension supérieure, comme sur le dessin ci-dessous, ces nombres restent inchangés.

Bien sûr il en est de même pour l’opération inverse. A nouveau, on dit que ces nombres sont des invariants homologiques.

En réalité, il est possible de définir de tels nombres $b_0(G)$, $b_1(G)$, $b_2(G)$... de n’importe quelle forme (pas seulement pour des graphes généralisés). Ces nombres seront toujours invariants par déformation de notre forme. Beaucoup d’informations sur ce (très vaste) sujet qu’est l’homologie peuvent être trouvées ici.

Distance dans une forme

Imaginons une forme dans l’espace, par exemple un dromadaire. On supposera que cette forme est en un seul morceau. On dit que deux points de cette forme sont à distance $d$ si parmi tous les chemins qui les relient en restant dans la forme, le plus court est de longueur $d$. Par exemple les extrémités des deux pattes avant d’un dromadaire sont à distance environ 2 mètres dans le dromadaire. En effet, le plus court chemin pour relier ces deux points en restant dans le dromadaire, consiste à remonter la première patte puis descendre la seconde comme représenté en jaune ci-dessous.

Attention, cette manière de mesurer la distance est très différente de la distance usuelle « euclidienne » entre deux points de l’espace, pour laquelle les deux pieds avant sont très proches l’un de l’autre !

Il est intéressant de remarquer que cette distance dans le dromadaire change peu si le dromadaire change de position :

Lorsque l’on voudra faire de la reconnaissance de forme par ordinateur, on approximera notre forme par un nuage de points. Les données que l’on fournira à l’ordinateur seront simplement ce nuage de points que l’on appellera $X$ et les « distances dans la forme » calculées (de manière approchée) comme ci-dessus entre les points de $X$. On notera $d(x,y)$ la distance entre deux points $x$ et $y$ de $X$.

Pleins de graphes généralisés à partir d’un simple nuage de points

Imaginons que nous avons un nuage de points $X$ et fixons un nombre $s>0$. Par exemple, $X$ pourrait être formé de points pris dans le dromadaire ci-dessus et la distance entre ses points étant la « distance dans la forme » que nous venons de voir. Nous allons construire un graphe généralisé à partir de $X$, comme suit. On commence avec $X$ lui-même, il constitue l’ensemble des sommets du graphe que l’on va construire.

On relie ensuite certains points de $X$ par des arêtes suivant la règle : on met une arête entre $x$ et $y$ à chaque fois que la distance entre $x$ et $y$ est plus petite que $s$. On ajoute ensuite des triangles de sommets $x,y,z$ de $X$ à chaque fois que ces trois points sont deux à deux à distance plus petite que $s$. Bien sûr, on ajoute ces triangles de telle sorte que leur bord soit constitué des arêtes précédemment ajoutées.
On continue... on colle à ce qui précède un tétraèdre de sommets $x,y,z,t$ à chaque fois que ces quatre points sont deux à deux à distance plus petite que $s$.
Et on continue ainsi à coller des $n$-simplexes jusqu’à ce que le processus s’arrête (lorsque $n$ dépasse le nombre de points de $X$, on ne colle plus de $n$-simplexe).

Par cette construction, nommée complexe de Vietoris-Rips, on obtient à partir de $X$ et des distances entre les points de $X$, un graphe généralisé, ce pour chaque paramètre $s>0$.

Vous pouvez observer cette construction sur un nuage de 8 points du plan euclidien dans l’animation ci-dessus (réalisée avec le logiciel Geogebra). Pour plus de lisibilité, on y a fait apparaître les arêtes et les triangles, mais pas les tétraèdres et autres simplexes de dimension supérieure. Vous pouvez faire bouger le paramètre $s$, déplacer les points, zoomer, déplacer la figure. Pour revenir à la configuration initiale, cliquez sur le bouton en haut à droite.

Le code-barres d’une famille de graphes généralisés

Nous allons enfin voir apparaître le lien de tout ceci avec les codes-barres.
Mais d’abord, faisons le point : pour chaque valeur de $s>0$, on dispose d’un graphe généralisé, et donc de toute une collection de nombres $b_0$, $b_1$... ce pour chaque $s>0$. Ces nombres varient avec $s$. Le code-barres de $X$ va permettre de visualiser l’évolution de ces nombres lorsque $s$ évolue.

L’idée est la suivante. On fait croître le paramètre $s$ et l’on décide de faire commencer des barres à chaque valeur de $s$ où l’un des $b_i$ augmente, de telle sorte que le nombre de barres commencées correspondent au nombre d’unités dont $b_i$ augmente. De même, on termine des barres à chaque fois que l’un des $b_i$ diminue.

Voici un exemple de code-barres associé à un nuage de 8 points. On a représenté ici le code-barres obtenu en ne prenant en compte que les augmentations et les diminutions des nombres $b_0$ (le nombre de morceaux) et $b_1$ (le nombre de boucles, aussi appelées cycles) avec le paramètre $s$. Vous pouvez faire augmenter le paramètre $s$ en déplaçant le curseur (ou en cliquant sur le bouton lecture) et voir ainsi apparaître le code-barres. Vous pouvez aussi choisir de ne montrer que les barres liées à $b_0$ ou celles liées à $b_1$.

Lorsque $s>0$ est très petit, le graphe généralisé n’a aucune arête car tous les points sont à distance plus grande que $s$ les uns des autres. Alors $b_0$ est le nombre d’éléments de $X$ et les autres $b_i$ sont nuls. Notre code-barres commence donc avec autant de barres partant de $0$ qu’il y a de points dans $X$. Ensuite, si l’on fait grandir $s$, des arêtes, des triangles, etc. apparaissent. Le nombre $b_0$ diminue alors. Les autres nombres $b_1$, $b_2$ ... augmentent lorsque des boucles ou des cavités apparaissent, mais diminuent lorsque ces boucles ou cavités viennent à être « remplies » par de nouveaux triangles, tétraèdres...

Par construction, pour chaque valeur de $s$, le nombre de barres contenant $s$ est toujours égal à la somme $b_0+b_1+b_2+...$ du graphe généralisé obtenu à la valeur $s$. Par exemple, si le code-barres obtenu est comme ci-dessous, on voit que pour $s=5$, la somme $b_0+b_1+b_2+...$ vaut 3.

A priori, lorsqu’on souhaite terminer des barres, il y a le choix parmi toutes les barres possible. Mais un théorème du à Serguei Barannikov (cf [Ba-94]) [7] affirme que parmi tous les choix possibles, il y en a un qui est « naturel » et donc meilleur que les autres. En faisant à chaque fois ce « meilleur choix », on associe ainsi à tout nuage de points $X$ un code-barres $B(X)$.

Reconnaissance de forme

Voyons enfin comment tout ce qui précède peut être appliqué pour faire de la reconnaissance de forme à l’aide d’un ordinateur.

Le procédé va reposer sur deux remarques. La première est un peu empirique : elle postule que deux formes représentant le même animal ou type d’objet pris dans des positions différentes, donneront après échantillonnage, deux nuages de points finis $X$ avec des distances entre les points qui seront à peu près les mêmes. Nous avions déjà observé cela précédemment, pour la distance entre les pieds d’un dromadaire. Il y a une manière précise de dire ce que l’on entend ici par « à peu près les mêmes » qui a été définie par Mikhaïl Gromov en s’inspirant d’une autre définition due à Félix Hausdorff. Les mathématiciens expriment ceci en disant que les nuages de points sont proches « au sens de Gromov-Hausdorff ».

La deuxième remarque est quant à elle un vrai théorème de mathématiques prouvé en 2009, qui affirme que deux formes géométriquement proches auront des codes-barres proches. Sa démonstration est beaucoup trop compliquée pour qu’on l’aborde ici. Disons simplement que l’invariance par déformation des nombres que l’on considère, y joue un rôle crucial.

Théorème (Chazal, Cohen-Steiner, Guibas, Mémoli, Oudot [CCSGMO-09]) Si deux nuages de points munis de distances sont proches au sens de Gromov-Hausdorff, alors leurs codes-barres sont proches pour la distance « goulot de bouteille ».

Si l’on met ensemble ces deux remarques [8], on en déduit une méthode pour faire de la reconnaissance de forme, comme suit. Étant données deux formes, on choisit un échantillon représentatif de chacune d’elles sous la forme de deux nuages de points. Pour chacun des deux, on calcule (approximativement) les distances entre tous les points. On calcule ensuite les codes-barres respectifs des deux nuages et on estime leur distance goulot de bouteille. Si cette dernière est très petite, on en déduit que les deux formes dont nous étions partis représentent probablement le même animal ou objet. Si en revanche elle est grande, on en déduit que les formes ne représentent pas le même objet. Bien sûr, il y a une part expérimentale pour déterminer les bons paramètres, par exemple à partir de quel seuil de « petitesse », on décide que les formes sont probablement les mêmes.

Cette stratégie a été expérimentée par les auteurs du théorème ci-dessus, toujours dans l’article [CCSGMO-09], sur l’ensemble de formes montré en début d’article.
Détailler le protocole précis serait trop long [9], mais l’image ci-dessous permet de visualiser les distances « goulot de bouteille » entre les codes-barres des différentes formes, obtenues lors de l’une de leurs expériences.

Cette image confirme qu’un même animal mis dans des poses différentes donne des codes-barres proches. On voit aussi que des animaux différents auront des codes-barres éloignés. Cela permet donc à l’ordinateur de déterminer à partir d’une forme donnée à quel type d’animal elle correspond. Les auteurs affirment que le taux d’erreur de leur algorithme est réduit à 4%, mais que celui-ci tombe à 2% lorsqu’on exclut de l’expérience l’un des chameaux (celui correspondant au rond que l’on peut voir au milieu des triangles dans l’image ci-dessus). Du point de vue de l’ordinateur, ce chameau ressemble beaucoup à un cheval !

Conclusion

Cette histoire de code-barres est une belle illustration du caractère inattendu des applications des mathématiques ! Le concept d’homologie que nous avons simplement effleuré dans cet article, est très répandu en mathématiques et a toujours été considéré (à juste titre je crois) comme très éloigné des applications. Mais en quelques années, via la théorie des codes-barres et plus largement le domaine appelé « analyse topologique des données » (TDA), ce concept est brusquement entré dans le monde des maths appliquées.

A l’heure actuelle, la TDA commence a être utilisée par l’industrie, mais de manière encore limitée. En général, la résolution de problèmes concrets fait appel à de multiples méthodes (en particulier, statistique et apprentissage), la TDA ne venant qu’en complément.

Références

[Ba-94] S. Barannikov, Framed Morse complex and its invariants, Advances in Soviet Mathematics, 21 : 93–115, 1994.

[CB-15] W. Crawley-Boevey, Decomposition of pointwise finite-dimensional persistence modules, Journal of Algebra and Its Applications, Vol. 14, No. 05, 1550066 (2015).

[CCSGMO-09] F. Chazal, D. Cohen-Steiner, L. Guibas, F. Mémoli, S. Oudot, Gromov-Haussdorff signatures for shapes using persistence, Computer Graphics Forum (proc. SGP 2009) , 1393–1403, 2009.

Post-scriptum :

Un grand merci à Konrad Dierks, Gérard Grancher, Griforg et Pierre-Antoine Guihéneuf, pour leur relecture attentive et leurs remarques pertinentes.

Article édité par Pierre-Antoine Guihéneuf

Notes

[1Comme souvent, on peut imaginer de belles utilisations de ces avancées scientifiques, mais l’on peut aussi craindre qu’une utilisation éthiquement discutable en soit faite...

[2Peu importe que ces intervalles soient fermés ou ouverts, autrement dit peu importe s’ils contiennent leurs extrémités ou non.

[3En pratique, on utilise plutôt la terminologie anglaise : « bottleneck distance ».

[4Dans le langage de la théorie des graphes, le terme de boucle a en général une signification plus restrictive et désigne une arête ayant pour extrémités le même sommet

[5Le lecteur savant aura peut-être reconnu dans cette histoire que les cycles et leur addition forment un espace vectoriel sur le corps à deux éléments et que $b_1(G)$ n’est rien d’autre que la dimension de cet espace vectoriel.

[6Le terme technique utilisé par les mathématiciens est plutôt « complexe simplicial »

[7Une version plus générale due à William Crawley-Boevey (cf. [CB-15]) est souvent citée.

[8La première remarque seule ne suffit pas, car en pratique, calculer la distance de Gromov-Hausdorff demande énormément de temps à un ordinateur.

[9Un mot sur la manière de calculer les distances approchées dans cette expérimentation : les formes sont données sous forme triangulée, et sont donc données avec des points, des arêtes (qui forment un graphe) et des triangles. On peut calculer une bonne approximation de la distance dans la forme entre deux points en appliquant un algorithme de recherche du plus court chemin dans ce graphe. Il existe plusieurs tels algorithmes, mais les auteurs ont utilisé le plus célèbre d’entre eux, l’algorithme de Dijkstra qui était enseigné au lycée ces dernières années.

Partager cet article

Pour citer cet article :

Vincent Humilière — «Codes-barres et reconnaissance de forme» — Images des Mathématiques, CNRS, 2020

Crédits image :

Image à la une - Image tirée de l’article [CCSGMO-09].

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?