Brevet FR3153442A1 — publié le 20250328

Procédé d’encodage dans un graphe et objet matériel encodant L’invention concerne un procédé d’encodage d’un message dans un graphe et un objet matériel encodant le message, comprenant : - un choix (E0) d’une racine pour un arbre dans le graphe, - puis, le message étant considéré comme une succession d’unités d’information, une succession d’ajouts dans ledit arbre à chaque fois d’une nouvelle arête du graphe reliant l’arbre à un nouveau nœud, le nouveau nœud faisant l’objet d’un choix (E1), dit premier choix, parmi les nœuds du graphe dits nœuds candidats qui, au moment de l’ajout, sont extérieurs à l’arbre et voisins de l’arbre car distants de l’arbre d’une unique arête, ces arêtes uniques constituant des arêtes candidates, la nouvelle arête faisant quant à elle l’objet d’un choix (E2), dit second choix, parmi les arêtes candidates, un des choix encodant une ou des unités d’information successives de la succession d’unités d’information. Figure d’abrégé : figure 1A Procédé d’encodage dans un graphe et objet matériel encodant L’invention s’inscrit dans le domaine des codes graphiques analysables par ordinateur. Les codes-barres et les QR-codes (codes à réponse rapide) sont bien connus. Ces codes sont fondés sur le repérage, par un système de lecture optique par ordinateur, de deux aspects contrastés. Ceux-ci peuvent former une séquence dans les codes-barres à une dimension, ou peuvent être, dans les QR-code notamment, entrelacés dans des motifs complexes. Le contraste entre deux aspects permet un décodage simple, les 'blancs' et 'noirs' représentant un code binaire. A la place du blanc et du noir, d’autres couleurs peuvent être utilisées, sous réserve d’un contraste suffisant. Certaines applications industrielles et commerciales nécessitent que les codes soient physiquement robustes (résistants) et intrinsèquement liés à l'objet qui doit porter le code, et donc fabriqués dans la masse de l'objet ou bien fixés définitivement par tout procédé. Dans de nombreux cas, il est de plus important que les codes soient fabriqués à faible coût tout en étant uniques. On souhaite pouvoir les fabriquer dans des matériaux divers, comme le métal ou le plastique, et par des techniques versatiles et accessibles, comme le moulage, ou récemment, la fabrication additive – ou impression en trois dimensions. La nécessité d'avoir des aspects contrastés dans des arrangements spatiaux complexes rend délicate la fabrication. En effet, il devient nécessaire de combiner deux matériaux positionnés côte à côte avec des entrelacements précis et de faible taille, ce qui entraine une production complexe, et donc des coûts élevés et une robustesse difficile à obtenir. En fabrication additive à filaments, lorsque de petites tailles sont visées, les nombreux arrêts et reprises du dépôt rend le processus difficile à maîtriser et à répéter à l’identique. L'invention porte dans ce contexte sur une nouvelle forme de codes, qui permet non seulement une fabrication physique simple et robuste avec différents procédés de fabrication, mais également un décodage simple et robuste via un algorithme de capture d’image et analyse par ordinateur. L'invention prévoit donc, à partir d'un message, la fabrication d’un objet physique, ou objet matériel, incorporant le code, qui est mis en circulation au profit d’un récepteur connaissant un éventuel secret de codage et à même de mettre en œuvre la méthode de décodage. L'invention porte donc également sur le processus de décodage du message via un algorithme de capture d’image et analyse par processeur mis en œuvre sur - par exemple - un smartphone. Définition de l’invention et avantages associés Le procédé de génération du code graphique est basé sur une sélection d’arêtes dans un graphe. On rappelle qu’un graphe est un ensemble de sommets et d’arêtes entre des sommets du graphe. Il consiste en un procédé d’encodage d’un message ou d’une phrase secrète dans un graphe éventuellement à l’aide d’un secret préétabli, comprenant - un choix d’une racine pour un arbre dans le graphe, - puis, le message ou la phrase secrète étant considéré comme une succession d’unités d’information (en général des unités élémentaires ou bits), une succession d’ajouts dans ledit arbre à chaque fois d’une nouvelle arête du graphe reliant l’arbre à un nouveau nœud, le nouveau nœud faisant d’abord l’objet d’un choix, dit premier choix, parmi les nœuds du graphe dits nœuds candidats qui, au moment de l’ajout, sont extérieurs à l’arbre et voisins de l’arbre car distants de l’arbre d’une unique arête, de telles arêtes uniques constituant des arêtes candidates, la nouvelle arête faisant quant à elle ensuite l’objet d’un choix, dit second choix, parmi les arêtes candidates, la succession d’ajouts encodant, dans le premier ou le deuxième choix, une unité d’information successive de, respectivement la succession d’unités d’information de la phrase secrète ou de la succession d’unités d’information du message, les ajouts étant de plus menés, le cas échéant, selon une règle tenant compte du secret. Grâce à cette méthode, un code graphique bicolore ou bi-aspect dont l’un des aspects est construit d’un seul tenant est généré, et peut donc être manié de multiples manières très avantageuses. Selon des caractéristiques avantageuses et optionnelles le premier choix peut être effectué en défavorisant aux fins dudit premier choix des nœuds voisins qui possèdent un plus faible nombre de possibilités différentes de connexion à l’arbre par une telle arête unique que d’autres nœuds voisins, y compris en excluant du premier choix les nœuds voisins qui possèdent un nombre de possibilités de connexion à l’arbre par une arête unique qui est inférieur au maximal dans le groupe des nœuds candidats ; les ajouts peuvent être effectués en considérant une suite pseudoaléatoire du secret (une suite pseudoaléatoire secrète), qui est passée en revue progressivement au cours des ajouts de la succession d’ajouts ; la suite pseudoaléatoire secrète peut être utilisée à la fois pour le premier choix et le second choix ; le premier et le deuxième choix peuvent être menés en considérant un ordre prédéterminé des nœuds dans le graphe du nœud – en particulier, pour le premier choix, il est possible de simplement suivre l’ordre prédéterminé des nœuds ; la succession d’ajouts peut être poursuivie après un épuisement de la succession d’unités d’information, jusqu’à couverture complète du graphe par l’arbre, en ajoutant à la fin du message ou de la phrase secrète tout type de valeur, y compris une valeur constante ; le graphe peut être une grille plane rectangulaire (voire carrée), triangulaire, hexagonale ou radiale, ou peut être un graphe non plan, se développant dans l’espace, et constituer ainsi un réseau de points reliés entre eux dans l’espace, de maille éventuellement cubique ; Dans un mode de réalisation, un message est encodé dans les seconds choix, une phrase secrète étant de plus encodée dans les premiers choix, cette phrase secrète apportant une protection supplémentaire à l’encodage du message dans le graphe ; l’arbre peut être matérialisé par une fabrication d’un objet en métal ou en polymère synthétique, par synthèse additive ou découpe ou emboutissage de plaque, l’objet étant conservé visible ou à l’inverse intégré caché à l’intérieur d’un objet opaque à la lumière visible. Pour la fabrication de l’objet, on utilise l’arbre pour définir des trajectoires de fabrication, ou plus généralement un plan de fabrication, qui est communiqué à la machine de fabrication. Dans un mode de réalisation, on utilise un graphe de type grille, dont les points sont régulièrement espacés dans un plan et forment une grille à maille en général carrée régulière, avec des arêtes entre points voisins uniquement, dans les deux dimensions perpendiculaires. Mais on peut aussi utiliser un graphe en 3 dimensions. L'algorithme produit une sélection d'arêtes telle que jusqu’à tous les points du graphe sont connectés à l’arbre, et surtout la sélection d'arêtes ne forme aucun cycle. La sélection d'arêtes forme ainsi un arbre couvrant du graphe. Le procédé de génération inclut des choix à effectuer. Certains de ces choix se basent sur un secret nécessaire au codage et au décodage. L'un de ces choix est le point de départ, appelé couramment la racine, de l'arbre, qui est un point du graphe. Dans un mode de réalisation, le graphe est une grille carrée et la racine est un des quatre coins de la grille, sans qu’il soit trivial de déterminer lequel de ces quatre coins constitue la racine. D'autres choix sont effectués durant la génération du code graphique. Ces choix permettent d'encoder le message. Ces choix successifs consistent en la connexion d’un point à un autre, incluant par conséquent une des arêtes du graphe dans l’arbre. Ainsi, l’invention consiste aussi en un système de décryptage d’un message crypté et fourniture dudit message sous sa forme décryptée. Le système de décryptage et fourniture comprend un objet comprenant une continuité intégrale d’une matière solide formant un ensemble connexe non cyclique d’arêtes parcourant toute une surface ou tout un volume et un programme d’ordinateur pour extraire un message d’une image dudit objet, en analysant les choix des arêtes de l’objet à partir d’une racine dudit objet pour découvrir successivement des éléments d’information avec lesquels est formé le message décrypté. Ces éléments d’information découverts sont ceux d’un message encodé par un procédé d’encodage selon l’invention. Dans un mode de réalisation, l’ensemble d’arêtes est plan. Dans un mode de réalisation, l’ensemble d’arêtes étant plan, ou tridimensionnel, l’objet comprend une deuxième matière, la deuxième matière étant de teinte différente de la matière solide et occupant un espace séparant des arêtes de l’ensemble. Selon les réalisations l’objet est visible à l’œil (sous exposition aux ondes de la lumière visible, éventuellement par transparence grâce à une lumière visible suffisamment intense pour traverser une couche de matière solide ne l’absorbant pas totalement) l’objet est donc exposé à la lumière visible - ou à l’inverse est caché à l’intérieur d’un objet opaque à la lumière visible, auquel cas il peut être examiné par tomographie. Dans tous les cas, son image va être analysée par ordinateur. L’invention apporte aussi un système de vérification de l’authenticité d’un bien, caractérisé en ce que le système comprend un programme d’ordinateur pour encoder une phrase secrète dans un graphe et indiquer si le graphe obtenu est identique à un objet porté par le bien et comprenant une continuité intégrale d’une matière solide formant un ensemble connexe non cyclique d’arêtes parcourant toute une surface ou tout un volume. Liste des figures La FIG. 1 est un schéma de l’algorithme utilisé. La FIG. 1 est un exemple d’arbre couvrant dans un graphe simple, selon un exemple de mise en œuvre de l’invention. La FIG. 2 est un exemple de fabrication d’un objet physique, ou objet matériel, incorporant un code selon l’invention. Les figures 3 et 4 sont des vues d’un tel objet physique. Les figures 5 et 6 sont des vues d’une variante de l’objet physique incorporant l’invention. La FIG. 7 montre un exemple d’application de l’invention. La FIG. 8 montre une autre variante de l’objet matériel incorporant l’invention. Description détaillée d’un mode de réalisation – existence de variantes Encodage Eléments de départ Le graphe Le graphe peut être une grille carrée sans diagonales, c’est-à-dire un graphe carré ou équivalent, pour lequel on considère que les voisins d’un nœud sont ses quatre voisins selon les côtés de la maille élémentaire, une grille carrée avec diagonales c’est-à-dire un graphe carré ou équivalent, pour lequel on considère que les voisins d’un sommet sont ses quatre voisins selon les côtés de la maille et aussi les quatre nœuds reliés à deux des quatre voisins précédents, un graphe hexagonal, ou un graphe triangulaire. On dispose ainsi d’un graphe, et on a choisi dans ce graphe, un nœud qui va servir de racine pour l’arbre. On débute en incluant le nœud racine dans l’arbre S, jusque-là vide. Le graphe est noté G et ses M nœuds sont notés avec . Les nœuds ont des positions sur un réseau. Des arêtes connectent les nœuds. Une arête est notée avec ,, et chaque arête connecte une paire de nœuds. Il y a E arêtes dans le graphe. La séquence pseudo-aléatoire On se procure une séquence pseudo-aléatoire qui constitue un élément de secret. Une graine pour définir cette séquence pseudo-aléatoire crypte, à l’issue du procédé, le message. Changer la graine produit un code différent pour les mêmes données, et la connaissance de la graine est nécessaire pour décoder le message. Avec un algorithme de séquence pseudo-aléatoire adapté, tels que ceux utilisés en cryptographie, Il est virtuellement impossible de trouver la graine même en connaissant le code et les données du fait des propriétés des séquences pseudo-aléatoires robustes. La méthode proposée est donc robuste aux attaques, et permet par exemple de protéger les données du code avec un mot de passe, qui est utilisée comme graine d’encodage et de décodage. Certaines étapes de la méthode utilisent ainsi une séquence pseudo aléatoire R. La séquence génère une série de nombres aléatoires à partir d’une graine. Obtenir le nombre suivant est noté Cette fonction renvoie l’entier aléatoire , et avance la séquence à son membre suivant. Pour une même graine, la séquence des générée est toujours la même et donc parfaitement répétable, de façon déterministe. Les données à encoder Les données à encoder, appelées message, sont définies comme des octets en nombre D notés avec . On les code sous la forme d’un unique entier de grande taille N. Génération d’un arbre 4.1 Notions générales FIG. 1 L’algorithme calcule un arbre couvrant c’est à dire un graphe connexe sans cycle qui passe par tous les nœuds, sans pour autant bien sûr contenir toutes les arêtes. Au cours d’une étape E0, un nœud spécial, est désigné comme racine de l’arbre. Il peut s’agir par exemple du le coin inférieur gauche de la grille. Pendant l’algorithme l’arbre est représenté par l’ensemble des arêtes qui la compose, et noté S. On note N(S) les nœuds des arêtes de l’arbre. L’arbre est couvrant si tous les nœuds de G sont dans N(S). Pour un nœud on définit les choix d’arêtes possibles pour connecter c à S comme : L’ensemble est vide si le nœud c ne peut pas être connecté à S. On définit les nœuds candidats comme Où est le nombre d’éléments dans . est donc l’ensemble des nœuds qui ont au moins un choix d’arête possible pour être connecté à l’arbre S. 4.2 Itérations Tant que tous les nœuds du graphe ne sont pas dans l’arbre S, on effectue itérativement la série des étapes suivantes, cette série constituant une boucle : L’étape E1 comprend les actions suivantes : On définit, ou on redéfinit s’il avait été défini précédemment, l’ensemble C(S) comme l’ensemble des nœuds voisins des nœuds de l’arbre S tel qu’il existe au cours de cette occurrence de la boucle, c’est à dire pouvant à l’aide d’une arête de la grille, être reliés à un nœud de l’arbre S C(S) = {ensemble de nœuds voisins de l’arbre S} 4.2.1 Filtre de performance et choix du nœud à intégrer (1 er choix) On utilise une fonction . La fonction choisit un nœud parmi . Pour cela on extrait de C(S) l'ensemble plus restreint des nœuds qui offrent le plus de possibilités de connexion à l’arbre S tel qu’il existe au cours de l’occurrence courante de la boucle. Typiquement, pendant la construction, le plus grand nombre de possibilités de connexion dans une grille est 2, ce qui amène donc, pour constituer l’extrait d’intérêt de C(S), à exclure les nœuds de C(S) qui n’ont qu’une seule possibilité de connexion à l’arbre S. Ainsi, la fonction Select élimine les nœuds qui offrent un seul choix, s’ils existent et s’il existe des nœuds offrant plus de choix, pour augmenter la capacité d’encodage en évitant d’utiliser les nœuds n’offrant qu’un seul choix, de tels nœuds ne permettant pas d’encoder d’information. Il s’agit d’un filtre de performance, du point de vue de l’encodage. Les nœuds offrant le plus de choix de connexion possibles sont ordonnés dans un ensemble T1 à l’aide des positions sur la grille. La fonction Tri ordonne ainsi les nœuds suivant leur numéro global, i.e. sera devant dans T1 si k Parallèlement, on choisit pseudo aléatoirement un nœud c dans l’extrait d’intérêt de C(S), à l’aide de la séquence pseudo aléatoire définit préalablement. On prend le nombre pseudo-aléatoire r1 suivant dans la séquence R pour choisir un nœud particulier parmi les nœuds qui viennent d’être ordonnés: T1 Tri(Select( Retourne Fonction Noeudsuivant Ainsi, un des nœuds sélectionnés dans T est choisi en utilisant la fonction pseudo aléatoire pour le choix, en calculant le reste de la division euclidienne (le modulo, noté %) de r par l’effectif de T1. Ce choix aléatoire agit comme un outil de chiffrement, dont le secret est la graine initiale de R. Néanmoins, dans une variante, le choix n’est pas aléatoire, et on prend simplement le premier nœud dans l’ordre des positions de la grille, à l’aide du numéro global. Le nœud choisi, en tout état de cause, est noté c. L’étape E2 suit l’étape E1 et comprend les éléments suivants. 4.2.2 Choix de l’arête ou choix du nœud de l’arbre qui va être utilisé pour connecter le nouveau nœud (2 e choix) Si c a plus d'une possibilité de connexion (au moins deux arêtes disponibles pour connecter c), ce qui alors permet d’encoder une information d’au moins un bit (une unité élémentaire d’information), on choisit une des arêtes qui peuvent le connecter à S, ce qui revient à choisir un des nœuds de l’arbre tel qu’il existe à ce stade. On prend les bits du message à encoder les uns après les autres dans l’ordre. Si exactement deux arêtes sont disponibles, on encode un bit du message à l’occasion de cette occurrence de la boucle alors que si plus de deux arêtes sont possibles, on en choisit toujours une seule, mais ce choix dans cette circonstance favorable permet d’encoder plus d'un bit du message. S’il n’y a qu’une seule arête possible, aucun bit n'est encodé. C’est la fonction , qui va être décrite, qui choisit une arête parmi , en encodant donc un morceau d’information (de N et donc du message) dans ce choix. A nouveau, on travaille sur des nœuds triés sur la base de leur numéro global. Ce tri est appliqué aux quelques nœuds P(c) de l’arbre qui sont susceptibles de définir l’arête avec le nœud à inclure et définit un ensemble ordonné T2. Et parallèlement, on prend l’élément suivant r2 de la suite pseudoaléatoire et on extrait le reste k (c’est-à-dire le modulo, noté %) de la division euclidienne de N par l’effectif de P(c) (typiquement 0 ou 1 si la grille est carrée). On choisit alors le nœud dans l’ensemble T2 qui est défini par le reste de la division euclidienne (le modulo, noté %) de la somme r2+k par l’effectif de T2. T2 Tri( Retourne Fonction SelectionneArete Le calcul de k fait apparaitre l’encodage, qui dépend de et donc du nombre de choix possible pour relier c à S. L’utilisation de la séquence pseudo aléatoire R permet de ne pas avoir de biais dans l’arbre quel que soit N, en particulier si N = 0, et comme précédemment pour le 1 er choix, agit comme un outil de chiffrement au cours du 2 e choix qui est ainsi effectué. Alternativement, néanmoins, on n’utilise pas de suite pseudoaléatoire, et r2 est constant, par exemple égal à 0. On inclut l’arête choisie dans l’arbre. On passe à l’unité élémentaire d’information suivante (ou bit suivant) du nombre N, c’est-à-dire du message, en remplaçant N par le quotient de N par l’effectif de P(c). On passe alors à l’occurrence suivante de la boucle. On revient donc à l’étape E1. 4.3 Fin du codage En général, les informations à coder s’épuisent avant que tous les nœuds du graphe soient inclus dans l’arbre, et N devient 0 à l’issue d’une des itérations, lors du calcul du quotient évoqué ci-dessus. Il est cependant avantageux de couvrir physiquement tout le graphe, afin que tous les codes se ressemblent, et qu’il ne soit pas possible de deviner la longueur des données encodées. On poursuit donc l’inclusion des nœuds, de préférence à l’aide de la suite pseudo-aléatoire ou avec un autre élément de secret, ou éventuellement sans élément de secret, jusqu’à ce que tous les nœuds soient inclus dans l’arbre, en effectuant des occurrences de la boucle jusqu’à épuisement des nœuds à ajouter, et en codant une information quelconque, par exemple constante. On passe alors à l’étape E3 : l’arbre est terminé. FIG. 1 On interrompt alors les occurrences de la boucle. Le résultat de l’algorithme est un arbre couvrant comme celui représenté en FIG. 1 , dans un cas d’un graphe qui est une grille plane carrée 11 nœuds sur 11 nœuds (soit 121 nœuds). Fabrication FIG. 2 On fabrique ensuite un objet matériel à l’aide de l’arbre. Un squelette 10 a été déterminé préalablement à l’aide de l’arbre. Il s’agit d’une courbe virtuelle en arêtes reproduisant l’arbre aux dimensions qui sont prévues pour l’objet. Selon un mode de réalisation on construit autour du squelette 10 un corps de l’objet matériel en déposant par fabrication additive, un fil épais extrudé d’une première matière (solide) de remplissage 20 sur chacun des côtés des arêtes du squelette, comme cela est visible en FIG. 2 , en commençant par un côté, en longeant le squelette sur ce côté, en atteignant une extrémité du squelette autour de laquelle le fil épais extrudé est placé pour contourner l’extrémité, et en suivant ensuite le deuxième côté. Ainsi, une trajectoire cyclique faisant le tour du squelette et ayant exactement une épaisseur donnée dite épaisseur de solidification, est produite, produisant une epaisseur totale autour du squelette égale au double de l’épaisseur du fil épais extrudé. Ceci permet un dépôt constant et régulier, sans interruptions. La flèche en pointillés sur la figure montre le sens de dépôt du matériau épais. La matière solide déposée reste en place de manière pérenne. Aux angles dans l’arbre, correspondant à des sommets entre deux arêtes, des lumières peuvent être présentes entre les deux épaisseurs de la matière de remplissage 20 du fait de la courbure à accommoder. Ces lumières sont une conséquence de la méthode de fabrication, et n’ont pas de conséquences sur le décodage. Dans le mode de réalisation qui est présenté, l’épaisseur du fil épais extrudé est un quart de l’écartement entre les arêtes parallèles du graphe, de telle sorte qu’il y a entre la matière de remplissage de deux arêtes parallèles incluses dans l’arbre une distance sensiblement égale à la largeur de la matière de remplissage d’une arête (qui est de deux largeurs de fil extrudé). FIG. 3 La FIG. 3 montre en perspective une vue en gros plan de l’objet matériel ainsi fabriqué. Il peut être placé sur une surface qui a une couleur différente vis-à-vis de laquelle il se distinguera aisément, pour le traitement informatique ultérieur, lors du décodage. FIG. 4 La FIG. 4 montre toujours en perspective une vue complète d’un tel objet matériel, encodant jusqu’à 270 bits. On précise que la surface sur laquelle il est placé peut être la surface sur laquelle la fabrication additive a été menée et à laquelle il est collé du fait du processus de fabrication, ou une autre surface sur laquelle l’objet matériel a été collé ultérieurement, par exemple avec une colle liquide qui a été apposée entre les deux éléments. FIG. 5 La FIG. 5 montre une variante dans laquelle l’arbre est de couleur sombre et les espaces entre les arêtes de l’arbre ont été remplis d’une deuxième matière de remplissage, qui est claire, et qui a été déposée par extrusion d’un fil épais également déposé en deux parties, comme cela a été présenté pour la matière précédente déposée autour du squelette. La deuxième matière de remplissage a été déposée par exemple autour de la première matière de remplissage, le long des surfaces libres de celle-ci, à savoir ses flancs. Aux angles dans la matière remplissant l’espace entourant l’arbre, des lumières peuvent à nouveau être présentes entre les deux épaisseurs de la deuxième matière de remplissage du fait de la courbure à accommoder (ces lumières sont surtout visibles sur la FIG. 6 ). FIG. 6 La FIG. 6 montre une autre variante de la réalisation bicolore de la FIG. 5 , dans laquelle l’arbre est en couleur claire, qui est la couleur de la première matière de remplissage, et l’espace autour de lui, rempli de la deuxième matière de remplissage, de couleur sombre. Une couleur claire et une couleur sombre dans le cas d’une observation par exposition à la lumière visible peuvent être remplacées par l’équivalent d’une teinte claire et d’une teinte sombre dans le cas d’une observation par un ordinateur utilisant une exposition à des ondes qui ne sont pas des ondes lumineuses, notamment en cas d’examen de l’objet par tomographie. Différentes matières solides donnent différentes réactions aux ondes utilisées, produisant différents équivalents de teintes à l’analyse. FIG. 7 Comme cela est montré en FIG. 7 , les objets physiques des figures 2 à 6 peuvent être fabriqués sur une première couche continue, éventuellement imprimée par fabrication additive, et ensuite recouverts d’une autre couche imprimée par fabrication additive. Cela est rendu possible, tant que les dimensions choisies pour l’objet physique ne sont pas trop grandes au vu du procédé de fabrication additive (notamment le choix de matière) par la propriété de portance de l’objet physique matérialisant l’arbre, puisque l’arbre parcourt toute la surface et constitue donc un support satisfaisant pour des ajouts de matière en surplomb par fabrication additive. En effet, de par le fait que les codes couvrent densément une zone d’une surface, en général plane, ils offrent une portance et constituent donc un support permettant le dépôt fiable de couches au-dessus, en particulier pour le cas des dépôts par extrusion - à l’aide d’un filament. La matière pour plastiques translucides offrant la possibilité d’observer l’ombre de la matière sombre par transmission et occultation de la lumière, tout en formant un objet léger et plan. On peut aussi imprimer plusieurs étages d’objet physique encodant chacun un code, les uns sur les autres, du fait de cette propriété de portance. Dans la version des figures 3 et 4, le code qui est d'un seul tenant et dont les flancs n’ont pas été comblés par une deuxième matière de remplissage, forme un canal dans lequel un élément liquide (un métal liquide, de l’encre, une poudre, etc) peut être introduit ou duquel un tel élément liquide peut être extrait par aspiration ou soufflage. Cela se prête éventuellement à une opération de moulage. Ainsi, l’invention permet la production du code graphique en tant qu’objet autonome en soi. Le code ou son complémentaire étant d’un seul tenant, il peut être fabriqué en tant qu’objet, par exemple à porter dans une poche de vêtements ou dans un porte-monnaie ou sac à main, et servant de clé, porte-clés, ou porte-badges. Les codes graphiques générés selon l’invention peuvent être fabriqués matériellement de manière robuste car ils sont d'un seul tenant. Le code peut être fabriqué d'un seul matériau et contrasté sur un fond quelconque, de préférence uni, lors du décodage. Il est donc possible de produire des codes sous forme de plaques métalliques (en plein ou en creux, à l’aide d’une découpe à l’eau, d’une découpe au laser ou d’un procédé d’emboutissage. Les codes selon l’invention peuvent aussi être déposés par projection de peinture sur un masque (stencil) d’un seul tenant, puisque le motif correspond à un unique trou dans le masque. Les codes selon l’invention peuvent être produits par fabrication additive, la faible taille de codes permettant d'en produire des centaines lors d'une seule production d'une machine de frittage sélectif par laser, par exemple. Les trajectoires de fabrication sont obtenues en contourant (tournant autour de) l’arbre couvrant, ce qui produit un unique cycle, idéal pour la fabrication. Les codes selon l’invention peuvent également être fabriqués sur des machines de fabrication additive par extrusion de filament (dépôt de fil fondu), avec de l’ABS -acrylonitrile butadiène styrène – de l’acide polylactique PLA ou du polyuréthane thermoplastique TPU ou tout autre type de matériau compatible. Ils peuvent aussi être fabriqués par stéréolithographie à l’aide d’une résine thermodurcissable. L’objet peut être fabriqué à l’aide d’une machine de fabrication additive à filament : la fabrication est très robuste, rapide et fiable, grâce à l’extrusion le long d‘une unique trajectoire. Le mode ‘spirale’ (ou mode ‘vase’) est possible dans ce mode de fabrication. L’objet peut être fabriqué à l’aide machine de fabrication additive SLS (frittage sélectif par laser). La fabrication d’un très grand nombre de codes, tous uniques, est possible dans un même bac de production, réduisant très grandement le coût de revient par code. Sur machine de fabrication additive de stéréo lithographie SLA, la fabrication est aussi possible, robuste et peu couteuse. Sur machine de fabrication additive à filament multi-matériaux et multi-buses, un code bi-matière peut être fabriqué avec un matériau pour le code et un autre pour son complémentaire. Sur machine fabrication additive filament à fibre, le code étant composé d’une seule trajectoire, une fibre peut être co-extrudée dans sa longueur pour lui donner une résistance accrue. Dans un mode de réalisation, un code double-face est imprimé, suivi d’un second code situé au-dessus. En changeant le matériau (filament) entre la dernière couche du premier code et la première du second, les deux codes peuvent avoir des couleurs différentes, facilitant leur décodage. Grace à la propriété de portance, les deux codes sont imprimés avec une qualité optimale. Dans un mode de réalisation, les codes sont intégrés sur la surface d’une pièce fabriquée par impression 3D, par exemple sur la partie inférieure de la pièce qui est en contact avec le plateau dans une impression par filament. L’algorithme de génération est peu couteux et peut s’exécuter sur un simple microcontrôleur, un FPGA ou un processeur dédié. Le code peut être généré directement dans la machine de fabrication, en remplaçant les trajectoires de la pièce dans une zone par celles du code. Il est possible de marquer les pièces fabriquées, de manière unique et robuste. Grace à la propriété de portance les couches au-dessus du code sont fabriquées de manière fiable. Dans un mode de réalisation, le code est intégré dans le volume d’un objet et caché à la vue, en mettant à profit une zone suffisamment large et portante. Le décodage ne peut alors se faire que de manière destructive (découpe de la pièce), ou par un procède optique avancé tel que l’utilisation de la transparence d’un matériau sous un fort éclairage, l’utilisation de rayons X dans un plan unique, ou encore d’une technique de scanner CT-scan- computed tomography scanner visant une reconstitution en trois dimensions. Des matériaux sensibles à la température peuvent également permettre de rendre visible le code même quand il est intégré dans le volume d’un objet, le vide ou l’air qui entoure l’arbre ayant une conductivité thermique moindre que de tels matériaux sensibles à la température. Dans un mode de réalisation, les codes fabriqués sont dimensionnés pour être insérés. Leur épaisseur est facilement ajustable, et il est possible de créer des codes prévus pour être insérés et fixés sur, ou dans un objet. Cela peut se combiner à la fabrication additive : par exemple des codes sont pré-imprimés, livrés et insérés dans la pièce en cours de fabrication – un avantage par rapport à un procédé d’extrusion est que le code est naturellement fusionné à la pièce en cours de fabrication. FIG. 8 Les trajectoires complémentaires, c’est à dire la partie autour de l’arbre matérialisant le code, peuvent également être facilement produites, en extrayant la partie du graphe complémentaire à l’arbre et en la fabriquant par impression à trois dimensions sur une surface de support. La FIG. 8 montre un tel objet. Les branches ne sont pas toutes nécessairement d’un même tenant, mais elles sont maintenues solidaires par la couche continue de matière sur laquelle elles sont déposées, et, sur la vue représentée, également par un cadre périphérique imprimé. L’objet matériel est ensuite mis en circulation, et obtenu par une personne qui n’a pas été impliquée dans sa fabrication. Décodage On décode ensuite l’information contenue dans l’objet matériel. Pour cela on capture une image, en général une image numérique, et celle-ci est analysée par un processeur exécutant un algorithme. L'algorithme cherche dans l'image le plus long contour fermé, qui est sauf exception le contour du code lui-même, étant donne sa forme particulière : il est extrêmement improbable qu’une image naturelle contienne un contour d’une telle longueur. De plus, si l’on connait la forme globale du domaine de G (par exemple, un rectangle ou un disque), il est possible d’utiliser l’enveloppe convexe du contour pour définir une homographie et redresser l’image du code. Plus en détail, à partir du contour, le procédé de décodage exploite le fait que l'orientation des bords suit celle du graphe utilisé pour l'encodage. Dans le cas d'une grille, cela permet de redresser par homographie le contour dans l'image, en retrouvant la forme de la grille. On trouve alors la rotation qui positionne la racine n_root dans le bon coin de la grille, si celle-ci est rectangulaire. Les bords du contour sont redressés selon leur direction la plus probable, la connaissance de la grille et de sa connectivité permettant une approche robuste au bruit d'acquisition. L'arbre est le squelette du contour redressé, et il est reconstruit par un algorithme d’amincissement (algorithme de 'thinning'). Une fois le redressement effectué, il est possible de reconstruire l’arbre couvrant qui correspond au code. Cet arbre couvrant reconstruit est noté A. Une variante spécialisée pour le cas d’un graphe 2D dans une grille régulière à quatre voisins consiste à reconstruire l’arbre à partir d’une grille positionnée sur l’image redressée, en déterminant à partir de la moyenne des valeurs de pixels dans chaque case si elle correspond à l’arbre épaissi ou au vide l’entourant. Une fois l'arbre reconstruit, le processus de décodage est relancé. Il débute à la racine, qui est connu de la personne effectuant le décodage, et est similaire à l’algorithme de codage, à ceci près qu’à chaque étape, au lieu d'effectuer un choix en fonction du message, dont on ne dispose pas, le choix effectué durant l'encodage est observé sur la structure, permettant de progressivement décoder les bits du message. Ainsi, on reconstruit N, l’entier représentant le message, à partir de l’arbre couvrant reconstruit A. L’algorithme est le même que l’encodeur à ceci près qu’au lieu de choisir une arête on observe le choix dans l’arbre couvrant reconstruit A. On obtient donc la valeur de k, avec laquelle on met N à jour en prenant le modulo positif. De plus la division de N à chaque itération et le test N = 0 sont enlevés, puisqu’ils n’ont pas de sens lors du décodage. A tout moment, il est possible de vérifier que l’arbre S en cours de construction est bien un sous ensemble strict de A l’arbre observé dans l’image. Si ce n’est pas le cas, une erreur est survenue lors de l’extraction de A de l’image, ou bien les éléments fournis à titre de secret par l’utilisateur pour le décodage sont incorrects. Alternative dans laquelle les unités élémentaires d’information sont encodées lors du premier choix Codage Dans un autre mode de réalisation, les données à encoder, ou phrase secrète (passphrase), sont présentées sous la forme d’un unique entier de grande taille M. On définit encore C(S) = {ensemble de nœuds voisins de l’arbre S} et on utilise la fonction qui choisit un nœud parmi . Pour cela on extrait à nouveau de C(S), avec une fonction Select l'ensemble des nœuds qui offrent le plus de possibilités de connexion à l’arbre S tel qu’il existe au cours de l’occurrence courante de la boucle. Les nœuds offrant le plus de choix de connexion possibles sont ordonnés dans un ensemble T’1 à l’aide des positions sur la grille. Une fonction choisit un noeud parmi les nœuds extraits ci-dessus de C(S) en encodant un morceau d’information (de M) dans ce choix. Elle effectue cet encodage en tenant compte, sauf à choisir de s’en passer, du secret offert par la suite pseudoaléatoire R. T’1 Tri(Select( Retourne fonction Le nœud choisi est noté c’. On passe à l’unité élémentaire d’information suivante (ou bit suivant) du nombre M, en remplaçant M par le quotient de M par l’effectif de T’1 On inclut une arête choisie dans l’arbre pour relier le nœud choisi. L’arête choisie peut être choisie en encodant ou non une partie de la phrase secrète, et en tenant compte ou non de la suite pseudoaléatoire. On passe alors à l’occurrence suivante de la boucle. Utilisation Cette manière de faire, lorsqu’utilisée seule, permet de savoir si l’objet matériel qui est présenté lors d’une situation de contrôle est un objet authentique, qui a été fabriqué par une personne connaissant la phrase secrète M. Cela peut servir à authentifier un bien, notamment un bien de valeur, qui porte le code, l’objet matériel réalisé par impression tridimensionnelle ayant été apposé sur, incorporé dans ou fabriqué de manière indissociable avec le bien. Pour vérifier que l’objet présenté est ainsi authentique, on le compare à un objet généré selon la même méthode, à partir de la même phrase secrète M connue par la personne souhaitant savoir si l’objet est authentique. Alternative dans laquelle des unités élémentaires d’information d’une phrase secrète sont encodées lors du premier choix et des unités élémentaires d’information d’un message sont encodées lors du 2 e choix. Combinée à un message N encodé dans les seconds choix, le fait d’encoder une phrase secrète dans les premiers choix permet de protéger le décodage de N par la nécessité de fournir une phrase secrète M au moment du décodage, agissant comme un mot de passe. Le message N et la phrase secrète M sont des éléments distincts, et le message est encodé, progressivement, lors des seconds choix, alors que la phrase secrète est encodée, progressivement aussi, dans les premiers choix. La phrase secrète et le message s’épuisent au cours de la construction de l’arbre, à des rythmes qui peuvent être identiques ou distincts. Procédé d’encodage d’un message ou d’une phrase secrète dans un graphe, comprenant : - un choix (E0) d’une racine pour un arbre dans le graphe, - puis, le message (N) ou la phrase secrète (M) étant considéré comme une succession d’unités d’information, une succession d’ajouts dans ledit arbre à chaque fois d’une nouvelle arête du graphe reliant l’arbre à un nouveau nœud, le nouveau nœud faisant d’abord l’objet d’un choix (E1), dit premier choix, parmi les nœuds du graphe dits nœuds candidats qui, au moment de l’ajout, sont extérieurs à l’arbre et voisins de l’arbre car distants de l’arbre d’une unique arête, de telles arêtes uniques constituant des arêtes candidates, la nouvelle arête faisant quant à elle ensuite l’objet d’un choix (E2), dit second choix, parmi les arêtes candidates, la succession d’ajouts encodant au fil desdits ajouts, dans le premier choix (E1) ou le deuxième choix (E2), des informations successives de, respectivement la succession d’unités d’information de la phrase secrète (M), ou de la succession d’unités d’information du message (N). Procédé d’encodage dans un graphe selon la revendication 1, caractérisé en ce que le premier choix (E1) est effectué en défavorisant aux fins dudit premier choix des nœuds voisins qui possèdent un plus faible nombre de possibilités différentes de connexion à l’arbre par une telle arête unique que d’autres nœuds voisins, y compris en excluant du premier choix les nœuds voisins qui possèdent un nombre de possibilités de connexion à l’arbre par une arête unique qui est inférieur au maximal dans le groupe des nœuds candidats. Procédé d’encodage dans un graphe selon la revendication 1 ou la revendication 2, caractérisé en ce que les ajouts sont effectués en considérant une suite pseudoaléatoire secrète (R), qui est passée en revue progressivement au cours des ajouts de la succession d’ajouts. Procédé d’encodage dans un graphe selon la revendication 3, caractérisé en ce que la suite pseudoaléatoire secrète (R) est utilisée à la fois pour le premier choix et le second choix. Procédé d’encodage dans un graphe selon l’une des revendications 1 à 4, caractérisé en ce que le premier choix (E1) et le deuxième choix (E2) sont menés en considérant un ordre prédéterminé des nœuds dans le graphe. Procédé d’encodage dans un graphe selon l’une des revendications 1 à 5, caractérisé en ce que la succession d’ajouts est poursuivie après un épuisement de la succession d’unités d’information, jusqu’à couverture complète du graphe par l’arbre, en ajoutant à la fin du message (N) ou de la phrase secrète (M) tout type de valeur, y compris une valeur constante. Procédé d’encodage dans un graphe selon l’une des revendications 1 à 6, caractérisé en ce que le graphe peut être une grille plane rectangulaire, triangulaire, hexagonale ou radiale, ou être un réseau tridimensionnel. Procédé d’encodage dans un graphe selon l’une des revendications 1 à 7, caractérisé en ce que l’arbre est utilisé pour la fabrication d’un objet en métal ou en polymère synthétique, par synthèse additive ou découpe ou emboutissage de plaque, ledit objet étant conservé exposé à la lumière visible ou à l’inverse intégré caché à l’intérieur d’un objet opaque à la lumière visible. Procédé d’encodage dans un graphe selon l’une des revendications 1 à 8, caractérisé en ce qu’un message est encodé dans les seconds choix (E2), une phrase secrète étant de plus encodée dans les premiers choix (E1). Système de décryptage d’un message crypté et fourniture dudit message sous sa forme décryptée caractérisé en ce que le système comprend un objet comprenant une continuité intégrale d’une matière solide formant un ensemble connexe non cyclique d’arêtes parcourant toute une surface ou tout un volume et un programme d’ordinateur pour extraire un message d’une image dudit objet, en analysant les choix des arêtes de l’objet à partir d’une racine dudit objet pour découvrir successivement des éléments d’information d’un message encodé par un procédé d’encodage selon l’une des revendications 1 à 9, avec lesquels est formé le message décrypté. Système de décryptage d’un message crypté selon la revendication 10, caractérisé en ce que l’objet comprend de plus une deuxième matière, la deuxième matière étant de teinte différente de la matière solide et occupant un espace séparant des arêtes de l’ensemble. Système de décryptage d’un message crypté selon la revendication 10 ou la revendication 11, caractérisé en ce qu’il est exposé à la lumière visible ou à l’inverse est caché à l’intérieur d’un objet opaque à la lumière visible. Système de vérification de l’authenticité d’un bien, caractérisé en ce que le système comprend un programme d’ordinateur pour encoder une phrase secrète dans un graphe selon un procédé de l’une des revendications 1 à 9 et indiquer si le graphe obtenu est identique à un objet porté par le bien et comprenant une continuité intégrale d’une matière solide formant un ensemble connexe non cyclique d’arêtes parcourant toute une surface ou tout un volume.