Images et transformations - Page 1

Bon, voilà un petit tutorial sur comment faire des transformations, principalement rotation et scaling, et quelques petits détails insignifiants avec ça. Il est très probable que vous connaissiez déjà tout ce que j'expliquerai ici donc ne vous étonnez pas si c'est le cas
J'ai décidé de réaliser ce mini-tutorial quand en codant une rotation toute bête, je me suis aperçu, que bah, il y avait une (vraiment) minuscule subtilité. J'ai donc cherché sur un bout de papier le pourquoi du comment et j'ai pensé que ça pourrait être utile à quelques uns. Et quitte a expliquer quelque chose, autant faire un truc qui soit plus consistant qu'une simple explication des rotations... (d'autant plus qu'on peut les combiner a un scaling en même temps )

A ) Représentation des images (Pixels, toussa....)

Bon, je suppose que tout le monde sait ce qu'est un pixel donc je ne vais pas m'attarder sur cette partie...
Pour faire simple, une image est une matrice de pixels, chaque pixel étant un point de l'image, qu'on peut assimiler à un petit carré de dimensions 1x1, avec sa position et sa couleur propre... Il y aurait certainement plus a dire que ça, mais je ne pense pas que ça soit si important. J'améliorerais ça si jamais ce n'est pas assez clair

Bon je ne pense pas qu'il y ait quelque chose a ajouter à celà, peut être les formats de pixels les plus courants si ça intéresse du monde...

B ) Dimensions et coordonnées en pixels

Tout d'abord un pixel... Il a deux coordonnées (On travaille en 2d... En 3d, avec des textures volumiques par exemple, il en aurait 3) et une couleur (j'ai un peu de mal à imaginer un pixel avec plus d'une couleur ), et chose très importante, ses dimensions sont 1x1. Habituellement on nomme les deux coordonnées x et y... x pour les abscisses et y pour les ordonnées

Il nous faut aussi un moyen pour bien repérer les pixels, alors utilisons une grille (en rouge ici) pour laquelle chaque intersection correspond à un pixel (en jaune)


Maintenant prenons une image plus grande, et prenons deux pixels A(x_a, y_a) et B(x_b, y_b). Si tout va bien ces deux pixels forment un rectangle... ou au moins une ligne... ou au pire un point. On trouve donc

largeur = |x_b - x_a| + 1
hauteur = |y_b - y_a| + 1

Attaquons nous au calcul des coordonnées du centre d'un rectangle. Le centre pouvant être vu comme l'isobarycentre des quatre points du rectangle, nous en déduisons ces formules:

x = (gauche + droite) / 2
y = (haut + bas) / 2

Ou encore

x = gauche + (largeur - 1) / 2
y = haut + (hauteur - 1) / 2

C ) Translations

Ici aucun problème, c'est tout bête D'ailleurs cette partie n'est absolument pas nécéssaire, mais histoire de faire un truc complet... ^^
Imaginons que vous avez un pixel au point M(x, y) que vous voulez déplacer d'un vecteur u(x_u, y_u), vous ajoutez simplement les coordonnées du vecteur à celles de votre pixel et c'est bon.

x = x + x_u
y = y + y_u

Evidemment, les translations d'images fonctionnent de manière semblable, les images étant elle-mêmes composées de pixels

D ) Clipping

Bon, petit bonus qui n'a pas énormément à voir, mais qui se combine généralement très bien avec tout ce qui est rotation/scaling, et qui plus est, qui va de paire avec la translation.

Le clipping (le découpage quoi) ça consiste à réduite le dessin d'une image, un sprite généralement, à un rectangle donné, qui est généralement au maximum égal à celui de l'imge dans laquelle vous dessinez.
C'est simple, vous testez les coordonnées de chaque pixel. Si le pixel est dans le rectangle, vous continuez à dessiner, sinon vous passez au suivant ou vous arrêtez (a voir en fonction des cas). Rapellez vous les calculs de largeur et hauteur et tout ira bien.
Il est généralement utile de définir une fonction qui s'occupera de tester tout cela pour vous dans vos programme afin de diminuer la redondance du code.

E ) Le redimensionnement (scaling)

Etirer/Compresser une image... idée étrange... ça va certainement être super moche ! Bah oui peut être un peu, mais c'est très pratique, principalement pour les jeux vidéos.
Le principe, vous le connaissez, on dessine une image (ou une partie) dans un rectangle plus petit ou plus grand, en l'étirant ou en la compressant de manière à ce qu'elle rentre dans le rectangle.

Maintenant, comment faire ça ? encore une fois ça n'est pas très difficile.
A priori deux méthodes s'offrent à vous: (On considère une partie d'image comme une image)
1 - Pour chaque pixel de l'image source, trouver le pixel correspondant de l'image de destination et en changer la couleur
2 - La même chose, mais en sens inverse, c'est à dire qu'on prend chaque pixel de la destination et on regarde quel pixel de la source on doit utiliser afin de connaître sa couleur
Pour des raisons logiques on préfèrera la deuxième méthode. La première méthode, si on y regarde de plus près, se contente de dessiner un pixel de destination pour un pixel source, donc si l'image de destination est plus grade, on verra du 'vide' entre les pixels, et pour une image plus petite, il y aura du chevauchement de 'pixels'

Voilà le pseudo-code pour la méthode 2:

EtirerImage(Source, Destination)
	Pour Chaque Pixel de Destination
		X = Pixel.X * Source.Largeur / Destination.Largeur
		Y = Pixel.Y * Source.Hauteur / Destination.Hauteur
		Pixel.Couleur = Source.Pixel(X, Y).Couleur
	Fin
Fin

Pour finir, notez que certaines filtres tels que entre autres bilinear, trilinear et bicubic, permettent d'avoir un redimensionnement plus lisse en utilisant les couleurs des pixels adjacents dans l'image source pour la détermination de la couleur de chaque pixel de l'image de destination. La technique de redimensionnement exposée ici quand a elle se nomme "pixel resize" du fait qu'en quelque sorte on agrandit les pixels.
F ) La rotation

La rotation... Souvenez vous de vos cours de mathématiques si lointains (ou pas)... Pour une rotation nous avons besoin d'un centre de rotation et d'un angle de rotation. Pas bien compliqué jusqu'ici.

Maintenant, le choix du centre de rotation. C'est à vous de voir, ça peut être le centre de l'image, le centre d'un rectangle, un point quelconque, ou tout autre chose, cela dépend vraiment de l'image et de ce que vous voulez faire.
Attention toutefois a bien choisir votre centre de rotation si vous ne voulez pas obtenir un résultat erroné ^^
A présent, concentrons nous sur le problème de la rotation en elle même. Nous avons ici aussi le choix entre deux méthodes, qui sont les mêmes que précédement, et pour les mêmes raisons la première est éliminée.
Lors de la rotation, nous avons juste a appliquer nos formules de rotation, en tenant compte du recentrage. Attention toutefois, car nous travaillons de la destination vers la source, donc notre angle devrait être inversé... Mais étant donné que les ordonnées sont inversées par rapport à la trigonométrie classique, nous pouvons conserver notre angle

TournerImage(Source, Destination, Angle)
	Pour Chaque Pixel de Destination
		X = (Pixel.X - Destination.Centre.X) * Cos(Angle) - (Pixel.Y - Destination.Centre.Y) * Sin(Angle) + Source.Centre.X
		Y = (Pixel.Y - Destination.Centre.Y) * Cos(Angle) + (Pixel.X - Destination.Centre.X) * Sin(Angle) + Source.Centre.Y
		Pixel.Couleur = Source.Pixel(X, Y).Couleur
	Fin
Fin

G ) Remerciements
- Ethaniel (voir les posts en dessous)

Bon, voilà un petit truc que je viens d'écrire, si vous avez des suggestions ou des critiques n'hésitez pas.
Je n'ai pas le temps d'améliorer ça pour le moment, je verrais ça bientôt

Personellement, je trouve un peu bizarre de graduer le bord d'un rectangle avec les valeurs entieres au coin superieur gauche des pixels, et en fait, j'utilise toujours la notation de la grille rouge.

Avec la grille rouge, on a donc les pixels (0,0), (0,1), (1,0) et (1,1), et on trouve bien largeur = (droite - gauche) +1 = (1-0)+1 = 2 et hauteur=2, donc contrairement a ce que tu dis, avec la grille rouge, l'image fait bien deux pixels de large ...
Donc centre_x = (gauche + droite) /2 = (0+1)/2 = 0.5 et centre_y=0.5, ce qui est le bon centre.
De plus, il faudrait que tu expliques clairement le systeme de notation utilise (coin superieur gauche ou centre du pixel) des le paragraphe B.

Pour le scaling, tu pourrais preciser que c'est la methode basique que tu decris en selectionnant sans transformation la couleur des pixels d'origine, puisque si tu reduis d'un facteur 2 un damier N&B, tu obtiens soit une image toute noire, soit une image toute blanche, au lieu d'une image toute grise (puisque le gris n'existe pas dans l'image d'origine).
Ainsi, sans entrer dans les details, tu pourrais juste mentionner les interpolations bilineaire (pour la reduction) et bicubique (pour l'etirement), a charge pour les personnes interessees de faire ensuite une recherche avec ces mots-cles.

Mais sinon, c'est une bonne introduction , vivement la suite !

@++

Bah de toute façons les grilles ça ne change rien aux calculs, juste que ce sont deux façons de voir les pixels, qui sont toutes les deux justes. Perso je préfère la grille bleue, parce qu'on y voit plus clairement la largeur, mais peut être que je suis bizarre

Avec la grille rouge, on a donc les pixels (0,0), (0,1), (1,0) et (1,1), et on trouve bien largeur = (droite - gauche) +1 = (1-0)+1 = 2 et hauteur=2, donc contrairement a ce que tu dis, avec la grille rouge, l'image fait bien deux pixels de large ...

Ben euh... Pour mesurer la largeur je considère qu'un segment entre deux points jaunes ça fait un pixel... Donc le petit carré au milieu, bah pour moi c'est l'image, donc 1x1 Evidemment par le calcul les deux grilles reviennent au même (encore heureux). Enifn... a voir, mais du coup j'explique comment que le centre c'est 0,5 et pas 1 ?

Pour le scaling, tu pourrais preciser que c'est la methode basique que tu decris en selectionnant sans transformation la couleur des pixels d'origine, puisque si tu reduis d'un facteur 2 un damier N&B, tu obtiens soit une image toute noire, soit une image toute blanche, au lieu d'une image toute grise (puisque le gris n'existe pas dans l'image d'origine). Ainsi, sans entrer dans les details, tu pourrais juste mentionner les interpolations bilineaire (pour la reduction) et bicubique (pour l'etirement), a charge pour les personnes interessees de faire ensuite une recherche avec ces mots-cles.

Euh ué, c'était implicite pour moi ça Je corrigerai ça avec tout le reste, quand j'aurais le temps et l'accès à internet (les deux étant faciles à obtenir, mais séparément ). En fait les filtres bilinéaires & co j'y ai pensé, mais n'en ayant jamais fait, je vais éviter d'expliquer un truc auquel j'ai réfléchi sans le réaliser (D'ailleurs je vais faire un prog dès ce soir, comme ça... )

En fait, petit truc que j'ai pas posté, parce que j'ai posté ça hier soir 2 secs avant de partir, voilà la liste de ce que je pourrais rajouter: (Enfin les trucs auquels j'ai pensé avant ou pendant l'écriture)
- Quelques trucs sur les formats de pixels les plus répandus (32 bits ARGB & RGB, 24 bits RGB, 16 bits RGB, 8 bits Palette & grayscale, 4 bits, 2 bits, 1 bit, ...)
- Les masques
- L'alphablending
- Les filtres de redimensionnement
- Les opérations sur les rectangles (addition, inflation, déflation, ...)
Peut-être quelques autres trucs encore, mais là ça s'éloigne déjà pas mal du but visé à l'orgine :]

Enfin, plus tard de toute façon, peut être ce soir si j'arrive à chopper un PC avant 17h

GoldenCrystal a écrit :
[...] Enifn... a voir, mais du coup j'explique comment que le centre c'est 0,5 et pas 1 ? [...]

Avec la grille rouge, le pixel gauche est a x_gauche=0, le pixel droit a x_droite=1, donc le centre est a x_centre = (x_gauche + x_droite) /2 , tout simplement, formule deja donnee en ./2 et bien plus simple a comprendre que x_centre = x_gauche + (largeur - 1) /2 , bien que ce soit strictement la meme chose, en vertu de la relation largeur = (x_droite - x_gauche) +1.

Sinon, si tu veux des trucs sur les operations sur les contours (accentuation (sharpening), adoucissement(softening), erosion, dilatation, ...), j'ai fait un compte-rendu de TP que je peux t'envoyer, si tu veux.
Mais comme je ne l'ai pas sur moi, ce ne sera pas avant demain ...
A moins que squalyl^2, qui normalement l'a sur son serveur, te l'envoie.

@++

cf ma signature, mon serveur http est down vu que le port 80 me sert de ssh depuis mon lieu de stage

http://www.galaxoft.org >

SSH-1.99-OpenSSH_3.9p1

Perso je préfère la grille bleue, parce qu'on y voit plus clairement la largeur, mais peut être que je suis bizarre

C'est parce que tu n'as pas les bonnes notions pour calculer largeur et hauteur en utilisant des éléments discrets.

Je le sais bien, que ton serveur est down !
Mais tu dois bien pouvoir recuperer le CR par FTP, SSH ou je ne sais quoi, non ?
Apres, par exemple, tu me le mailes et je le mets sur mon site Free (apres une eventuelle anonymisation si OpenOffice ne fait pas son boulet ... ou alors tu le fais) ...

@++

Ethaniel
:

GoldenCrystal a écrit :
[...] Enifn... a voir, mais du coup j'explique comment que le centre c'est 0,5 et pas 1 ? [...]

Avec la grille rouge, le pixel gauche est a x_gauche=0, le pixel droit a x_droite=1, donc le centre est a x_centre = (x_gauche + x_droite) /2 , tout simplement, formule deja donnee en ./2 et bien plus simple a comprendre que x_centre = x_gauche + (largeur - 1) /2 , bien que ce soit strictement la meme chose, en vertu de la relation largeur = (x_droite - x_gauche) +1.

Hmm mwé...

Sinon, si tu veux des trucs sur les operations sur les contours (accentuation (sharpening), adoucissement(softening), erosion, dilatation, ...), j'ai fait un compte-rendu de TP que je peux t'envoyer, si tu veux.
Mais comme je ne l'ai pas sur moi, ce ne sera pas avant demain ...A moins que squalyl^2, qui normalement l'a sur son serveur, te l'envoie.

Hmm ça peut-être intéressant, mais je vais déjà voir les trucs simples avant ça

squalyl^2
:

Perso je préfère la grille bleue, parce qu'on y voit plus clairement la largeur, mais peut être que je suis bizarre

C'est parce que tu n'as pas les bonnes notions pour calculer largeur et hauteur en utilisant des éléments discrets.

Bah explique C'est quoi les bonnes notions ?

GoldenCrystal
:

squalyl^2
:

Perso je préfère la grille bleue, parce qu'on y voit plus clairement la largeur, mais peut être que je suis bizarre

C'est parce que tu n'as pas les bonnes notions pour calculer largeur et hauteur en utilisant des éléments discrets.

Bah explique C'est quoi les bonnes notions ?

La notion, c'est qu'en continu, on a largeur = (droite - gauche), et en discret, largeur = (droite - gauche) +1, toujours ...
C'est bien ce a quoi tu arrives, mais plus en le sortant d'un chapeau qu'autre chose, et en donnant l'impression que tu ne sais pas toi-meme d'ou ca sort ...
D'ailleurs, tu dis que la logique donne largeur = (droite - gauche) mais qu'en fait ce n'est pas ca, sous-entendant ainsi que la bonne formule n'est pas logique .
De ce que je sais des maths, ce qui est logique est juste, et reciproquement (excepte pour les enonces auto-referents ).
Si tu en arrives a ca, c'est bien parce que tu melanges la logique du continu a laquelle tu t'accroches et celle du discret qui doit s'appliquer ici.
D'ou l'utilisation de la grille bleue qui donne un resultat faux pour la rotation ...

En plus, tu n'as meme pas verifie la formule sur le premier dessin sur lequel les chiffres '2' ne devraient pas apparaitre, si tu veux etre coherent ...

@++

voila Merci Ethaniel.

Ethaniel :
La notion, c'est qu'en continu, on a largeur = (droite - gauche), et en discret, largeur = (droite - gauche) +1, toujours ... C'est bien ce a quoi tu arrives, mais plus en le sortant d'un chapeau qu'autre chose, et en donnant l'impression que tu ne sais pas toi-meme d'ou ca sort ...

Bah si, ça sort de ma la logique bizarre, stou Pis ça s'esplique très bien en partant du fait qu'un pixel mesure 1x1

En plus, tu n'as meme pas verifie la formule sur le premier dessin sur lequel les chiffres '2' ne devraient pas apparaitre, si tu veux etre coherent ...

Bah si ils devaient apparaître parce que 2x2 c'est la taille de l'image C'est pour ça que je les ai mis c tout

oui mais non comme tes pixels sont numérotés à partir de zéro dans une image 2x2 les pixels de droite ont pour coordonnées 1,1 ce qui prouve que c'est le modèle de la coordonnée centrale qui fonctionne et pas le modèle de la coordonnée du coin d'un rectangle.

D'autant plus que dans ta convention rien ne m'empêche de choisir le coin inférieur droit ou tout autre comme référence; tandis que dans le cas des coordonnées du centre du pixel il n'y a pas besoin de se poser la question.

D'autant plus qu'un pixel est un point, pas un rectangle.

GoldenCrystal a écrit :

En plus, tu n'as meme pas verifie la formule sur le premier dessin sur lequel les chiffres '2' ne devraient pas apparaitre, si tu veux etre coherent ...

Bah si ils devaient apparaître parce que 2x2 c'est la taille de l'image C'est pour ça que je les ai mis c tout

Justement, non : au-dessus des pixels, je vois 0 - 1 - 2, ce qui fait 3 nombres, alors qu'il n'y a que 2 pixels en largeur.
Si tu gradues tes pixels a leur coin superieur gauche, n'indique que les coordonnees des pixels presents : le pixel (2,0) est blanc, donc le 2 ne devrait pas apparaitre.
Si tu te sens oblige de marquer les nombres 0 - 1 - 2 pour seulement 2 pixels, c'est bien parce que tu es dans la logique du continu, non du discret ...
C'est a cause de ceci que la determination des bonnes formules n'est pas immediate ...

@++

-

heu comme ça ce sera dur à répondre

déja:

-quel angle?
-comment utilises tu tes tables?

parce que normalement 4 multiplications et deux sommes ca prend le même temps pour tous les angles ... en RISC!

L'arm a t il un opcode de multiplication ? dans ce cas c'est peut être ca qui bug, cf la doc pour le nombre de cycles que prend la multiplication, c'est variable généralement. donc si tu fais plein de multiplications ca peut ramer si tu passes dans un coin ou l'ALU prend du temps pour multiplier

edit: oups je viens de voir que l'arm est un RISC
alors
- soit la mult hardware est dédié à un bloc math interne qui est pas risc (déja vu chez dallas pour un autre proc)
- soit je pige pas

Hmm, monstrueux comment les ralentissements ? genre perte de 1 fps ou bien perte de 10x plus ?
Tu as fait des benchs là dessus pour savoir si c'était uniquement ton programme ou si c'était partout ?

Les multiplications sont lourdes, non ?
Je pense qu'on peut se débrouiller avec simplement des additions.

Les ARM récents pas trop basiques ne sont pas trop RISC. Voir leur jeu d'instructions, et un autre topic dans cette même section.

Hmm bon, j'ai mis a jour cet article comme me l'avait demandé ethaniel (ça aura pris a peine plus d'un mois ) Si il y a encore des erreurs prévenez moi histoire que je corrige.
Bon et sinon faut aussi que j'ajoute la deuxième partie sur les couleurs, et la troisième sur je sais plus quoi (ué depuis le temps j'ai oublié ce que je voulais mettre après), si jamais dans 1 mois c'est pas encore fait (au moins la deuxième partie), pensez à me slapper ^^

GoldenCrystal :
Si il y a encore des erreurs prévenez moi histoire que je corrige.

Tiens, ca me donne une idée : pkoi ne pas le mettre sur Ti-Wiki ?

Parce que ça a rien à voir avec les TIs ?

ah oui, tiens mais bon le post est dans "Forum Ti 68k - Ti 89/92/92+/V200"

le forum algo et optimisation est aussi rattaché au forum PC, même si, pour des raisons historiques, c'est une rubrique du forum TI.
(la plupart des algos pouvant être appliqués aussi bien sur TI que sur PC, je suppose)