De l'appariement de graphes symboliques à l'appariement de graphes numériques : Application à la reconnaissance de symboles

Les représentations sous forme de graphes structurels ont été appliquées dans un grand nombre de problèmes en vision par ordinateur et en reconnaissance de formes. Néanmoins, lors de l'étape d'appariement de graphes, les algorithmes classiques d'isomorphisme de graphes sont peu performants quand l'image est dégradée par du bruit ou des distorsions vectorielles. Cet article traite de la reconnaissance de symboles graphiques grâce à la formulation d'une nouvelle mesure de similarité entre leur représentation sous forme de graphes étiquetés. Dans l'approche proposée, les symboles sont d'abord décomposés en primitives structurelles et un graphe attribué est alors généré pour décrire chaque symbole. Les nœuds du graphe représentent les primitives structurelles tandis que les arcs décrivent les relations topologiques entre les primitives. L'utilisation d'attributs numériques pour caractériser les primitives et leurs relations permet d'allier précision et, invariance à la rotation et au changement d'échelle. Nous proposons également une nouvelle technique d'appariement de graphes basée sur notre fonction de similarité qui utilise les valeurs numériques des attributs pour produire un score de similarité. Cette mesure de similarité a de nombreuses propriétés intéressantes comme un fort pouvoir de discrimination, une invariance aux transformations affines et une faible sensibilité au bruit