# Transformée Mojette

La transformée Mojette est une application de la géométrie discrète. Plus précisément, c’est une version discrète exacte de la transformée de Radon (Théorème de Radon). Le premier travail de discrétisation de la transformée de Radon a été réalisé par Myron Katz en 1978. Depuis 1994, cette transformée a été développée par le laboratoire IRCCyN – UMR CNRS 6597 devenu LS2N à Nantes.
La première caractéristique de la transformée Mojette est de n’utiliser que des additions et des soustractions. De plus, celle-ci est redondante. La transformée utilise la géométrie discrète pour répartir l'information sur un support de géométrie discrète. Puis, sur ce support, on projette l'opérateur Mojette dans les directions discrètes partageant l'information sur les projections. Quand le nombre de projections est suffisant, l'information initiale peut être reconstruite. La transformée Mojette a déjà été utilisée dans de nombreux domaines d'application dans les problématiques du traitement du signal.
Les principaux domaines d’investigation sont :
* Le stockage distribué sur disques ou réseau
* L’envoi de paquets sur les réseaux
* La tomographie médicale
* Le tatouage d’images et le chiffrement d’images

## Historique

Après un an de recherche, la première communication introduisant la « Transformée Mojette » a eu lieu en mai 1995 dans la première édition du congrès national « CORESA » au CCETT de Rennes. Elle sera suivie par de nombreuses publications dans le monde entier. En 2011, le livre "The Mojette transform: theory and applications" chez ISTE-WILEY fut bien reçu par la communauté scientifique. Tout cela a encouragé les enseignants-chercheurs de l’IRCCyN à continuer le travail de recherche sur ce sujet.
Jean-Pierre Guédon, Professeur des Universités et concepteur de la transformée, la nomme la «Transformée Mojette ». Le mot « Mojette » vient du nom des haricots blancs en Vendée, écrit initialement « Moghette ou Mojhette». Dans de nombreux pays, le haricot sec est donc un outil pédagogique de base représentant une unité exacte qui permet d'apprendre l'addition simplement et visuellement. Le choix du nom « Mojette » permet donc de souligner le fait que la transformée n’use que d'addition ou soustraction entières. Il est intéressant de voir que depuis longtemps, les mojettes servent à compter.
Un dicton vendéen dit qu'il faut savoir "compter ses mojettes" c'est-à-dire son argent. Dans le monde anglo-saxon, on parle aussi de "bean counter" ce qui représente le petit fonctionnaire non zélé qui fait les additions. Une vieille expression anglaise dit "he knows how many beans make five ", ce qui veut dire : "il connait son affaire" et qui se réfère à une personne qui est férue de puzzles mathématiques. Cette expression provient des temps des abaques anglaises où les haricots servaient à noter les incréments dans les calculs.
L’objectif original de la « Transformée Mojette » était de créer un outil de mathématique discret qui permette de diviser le plan de Fourier en secteur angulaire et radial. La première tentative d’application fut l’encodage de l’image psychovisuelle reproduisant le canal de la vision humaine. Cependant, elle ne fut jamais réalisée.

## Mathématiques

La définition "brute" de la transformée Mojette est celle-ci :
$proj(b,p,q)=\sum _{k}^\sum _{l}^f(k,l)\Delta (b+kq-pl)$
| $\Delta (b)=1$ | $si\,\ b=0$ |
| $\Delta (b)=0$ | $sinon$ |
La figure 1 suivante permet d'expliciter en partie la transformée.
On part de la fonction f(k,l) représentée par les 16 pixels p1 à p16. Ces valeurs possibles de la fonction au point (k,l) différent selon les applications. Cela peut être une valeur binaire 0 ou 1 comme souvent utilisés pour différencier le fond et la forme. Cela peut être une valeur ternaire comme dans le jeu Mojette. Cela peut être également un ensemble fini de valeurs entières entre 0 et (n-1), ou souvent on prend un ensemble de cardinal égal à une puissance de 2 ou bien un nombre premier. Mais cela peut encore être les entiers ou les réels avec un nombre infini de possibilités, même si cette dernière idée ne sera quasiment jamais exploitée.
Avec les indices "k" comme "kolonne" et "l" comme "ligne", on définit un repère cartésien. Mais ici nous n'aurons besoin que des coordonnées entières. En rouge sur la figure 2, on voit que l'on a choisi arbitrairement le point bas gauche comme origine (position 0,0) et le sens des 2 axes. Dans chaque pixel est noté en rouge ses coordonnées.
Pour les projections, le système de coordonnées est donné par celui de la grille. En effet, on respecte 2 impératifs :
* le pixel (0,0) se projette toujours sur le point 0 de la projection (cela provient de la linéarité de l'opérateur Mojette)
* le sens de la projection est fixé "anti-horaire" comme en trigonométrie lorsque l'on va de 0° à 180°.
Cela donne donc nécessairement les positions des bins comme écrit en bleu sur la figure 2. La correspondance est avec la formule (1) : les points rouges correspondent à l'indice (k,l) et les points bleus à l'indice b. Donc il ne reste que les valeurs (p,q) à éclaircir pour avoir tous les éléments de la transformée.
Ces 2 valeurs (p,q) sont précisément celles qui caractérisent la transformée Mojette. Elles définissent l'angle de projection. La figure 3 montre des flèches de couleur correspondant chacune (par le code de couleur) à la projection indexée par (p,q). Pour l'angle 90°, la projection est représentée en dessous de la grille pour plus de commodités mais la direction est bien montante. Le tableau 1 fait la correspondance entre les angles en degrés et les valeurs de p et q.
| 0° | p=1 | q=0 | b-l=0 |
| 45° | p=1 | q=1 | b+k-l=0 |
| 90° | p=0 | q=1 | b+k=0 |
| 135° | p=-1 | q=1 | b+k+l=0 |
Tableau 1 : les correspondances d'angles de projections avec l'équation de direction b + qk - pl = 0
Les seuls angles valides en Mojette sont donnés par les règles suivantes :
1) un angle est donné par la direction de projection en ligne et colonne
2) une direction est composée de deux entiers (p,q) avec pgcd(p,q)=1
3) un angle est toujours compris entre 0 et 180° ce qui veut dire que q n'est jamais négatif
Ces règles permettent d'avoir une unicité dans la correspondance d'un angle. Par exemple, pour 45°, la règle 2 interdit de définir l'angle par les couples (2,2) ou (3,3) et la règle 3 interdit d'utiliser (-2,-2) ou (-1,-1). Seul l'angle (p=1,q=1) répond à la fois aux 3 règles.

## Applications & Réalisations
### Le stockage distribué sur disques ou réseau

Le domaine d’application le plus important utilisant la « Transformée Mojette » est le stockage distribué sur disques ou sur réseaux. Aujourd’hui, le stockage « Mojette » permet d’augmenter par 2 l’espace de stockage disponible (ou de façon équivalente, une réduction de 50 % des coûts d’équipements pour un volume donné à stocker), d’entretien et d’énergie par rapport aux technologies actuelles.
En 2010, Pierre Évenou, ingénieur de recherche de l’équipe IVC au laboratoire IRCCyN, décide de créer la start-up Fizians (aujourd'hui renommée Rozo Systems) qui développe le logiciel RozoFS. Il s'agit d'un logiciel libre qui offre un système de fichiers distribués. La distribution de ces données repose sur le transformée Mojette afin d'apporter de la protection aux données ainsi qu'aux applications qui y accèdent. Il s'agit d'utiliser les propriétés de la transformée Mojette comme code d'effacement. Plusieurs applications émanent de cette technique telles que le Cloud Computing et Cloud Storage, la virtualisation des serveurs de stockage ou encore l’archivage des données.

### L’envoi de paquet sur les réseaux

Grâce à la redondance de la transformée, l’envoi de paquet peut être fragmenté sans risque de perte. En parallèle, la propriété de n’utiliser que des additions et des soustractions permet d’augmenter la vitesse de transmission des informations. Enfin, l’information ne pouvant être reconstruite qu’en ayant l’angle original des projections, elle apporte aussi une sécurisation des données.
Cette application a été retenue par Thales Cholet pour ses réseaux ad hoc (sans fil et en utilisant les terminaux pour transmettre les messages entre eux) afin de le sécuriser et d'avoir plusieurs chemins entre la source et la destination. En 2002, la start-up PIBI a utilisé cette technologie pour proposer des services de paiement sécurisé sur Internet.

### La tomographie médicale

Dans le domaine de l’imagerie médicale, les propriétés de la « Transformée Mojette » permettent de créer un mapping direct et de résoudre le problème du calcul des angles. Cependant, l’acquisition de l’image utilisant la transformée Mojette n’a pas été encore développé. La problématique d’obtenir des valeurs exactes en utilisant des acquisitions de données qui ne sont qu’approximatifs a été étudiée mais doivent être continué. Par contre, le post-traitement des images médicales est opérationnel car l’acquisition des données est déjà faite.
Ces résultats sont utilisés par les sociétés Keosys en 2001 par Jérôme Fortineau et Qualiformed créée en 2006 par Stéphane Beaumont. Le Pr. Guédon et le laboratoire IRCCyN ont été fortement impliqués dans la création de ces entreprises. Ils ont permis de financer déjà plusieurs thèses et participé à des projets de recherche continuant à développer l’application en tomographie médicale. Les résultats ont permis de déposer des brevets et de les implémenter sur leurs équipements de traitement d’images.

### Le tatouage d’images et le chiffrement d’images

La cryptographie et le watermarking ont fait aussi partie des recherches effectuées au laboratoire IRCCyN pour développer les applications de la transformée. Elle apporte des solutions pour la sécurisation et l’authentification.
En cryptographie, l’instabilité de la transformée Mojette permet de sécuriser les données. Le fait que la transformée soit exacte permet de chiffrer les informations et ne permet aucun écart même minime. En tatouage d’image, la transformée est très efficace en fingerprinting. En insérant des marques « Transformée Mojette » sur image, on peut authentifier les documents en utilisant les mêmes propriétés qu’en cryptographie.