Algorithme: la transformation du boulanger
Bonjour à tous,
Chaque matin lorsque vous émergez de votre sommeil, d’autres s’affairent à terminer pains, croissants et autre mets délicieux, j’ai nommé: les boulangers. Ces artisans à l’origine de notre contentement matinal ont un véritable coup de main pour transformer les différents ingrédients en une pâte généreuse qui donnera naissance tantôt à un pain de campagne, tantôt à une baguette. Ce coup de main étant tellement extraordinaire qu’il a donné son nom à une transformation d’images au déroulement similaire.
L’idée
Créer une fonction intégrée à ma class image qui applique la transformation du boulanger à mon image courante
Le principe
Tel le boulanger ayant sa pâte devant lui, nous allons prendre notre image et l’aplatir de telle sorte que la hauteur diminue de moitié laissant place à une largeur double.
Voyez plutôt:
Attention toutefois… Contrairement à ce que l’on croit, la pâte ainsi pétrie n’est pas pressée n’importe comment. Il y a donc une méthode spécifique pour notre image: On écarte les pixels et on remplit les trous créés dans la première ligne par les pixels de la seconde ligne. On réitère jusqu’à la dernière ligne.
Schématiquement, cela donne ceci:
Vous l’aurez certainement remarqué, il faut donc que mon nombre de lignes soit un multiple de 2. Sinon, il reste une dernière ligne qui ne peut être comblée.
Une fois sa pâte aplatie, le boulanger la plie en deux afin de revenir à une boule similaire à celle de départ et ainsi recommencer s’il le désir afin d’obtenir l’onctuosité désirée.
Nous allons donc également couper notre image en deux et rabattre la partie (de droite) coupé en dessous en faisant un belle rotation comme indiqué sur le dessin ci-dessous.
Nous voici désormais en possession d’une image similaire à celle de départ puisqu’elle est aux mêmes dimensions. Cette transformation est bien bijective puisque tous les pixels de notre image de départ se trouvent toujours dans celle d’arrivée.
La curiosité de cette transformation
Cette transformation est bijective pour peu que notre nombre de ligne soit pair. Cela veut donc dire que même après plusieurs applications de cette transformation à une même image, tous les pixels de l’image d’origine sont toujours là mais disposés de plus en plus différemment sauf… qu’à un certain moment les pixels retrouvent leur place d’origine! Pour les images carrés dont le côté vaut une puissance de 2, il ne faut que quelques applications pour retrouver l’image d’origine. Pour une image de hauteur/largeur 2^7(=128) pixels, il faut 2*7+1 applications pour retrouver l’image. Jugez plutôt:
La généralisation
Lorsque je pense généralisation d’habitude, je pense à la création de mon algorithme pour appliquer une transformation comme celle-ci à toute image. Mais ici, j’ai pensé également à une généralisation dans le sens d’extension de l’idée de base. Ainsi, pourquoi se satisfaire de presser et couper notre pâte en deux alors qu’on pourrait le faire en trois, quatre ou vingt?
Il faut donc juste faire attention que notre nombre de ligne de départ soit adéquat avec le nombre de découpes que l’on désire faire. On élaguera donc le nombre superflu de lignes de l’image courante dès le départ.
Le petit « + »
Puisqu’il s’agit d’une transformation bijective, j’ai également donner la possibilité de retrouver l’image dont est issue l’image courante par la transformation du boulanger
Le code
-
-
/* Applique la transformation du boulanger à l’image actuelle avec un nombre de morceaux à couper réglable */‘do’‘do’
Notez que ce code fait partie du module algorithmes de ma class image.
Un exemple
Et pour terminer, voici une photographie sur laquelle j’ai appliqué une transformation du boulanger avec les paramètres 3 et ‘undo’. Le résultat est donc l’image telle que si j’applique une transformation du boulanger à ‘3’ découpe, je retrouve l’originale.
load('tailles')->recadrer(400, 300); $image->load('algorithmes')->boulanger(3, 'undo'); $image->afficher(); ?>
Alors, pour vous ce sera croissant ou pain de campagne?