Rotation de matrice (tableaux)

[Aure7780]

Bonjour,

Je cherche à faire une rotation d'un tableau à plusieurs dimensions (matrice) en fonction d'un angle.
Je n'arrive pas à trouver la formule mathématique.

Voici ce que je cherche à faire :
|1,2,3|
|4,5,6|
représenté par à tableau à 2 dimensions :
tab[0][0] = 1
tab[0][1] = 2
tab[0][2] = 3
tab[1][0] = 4
tab[1][1] = 5
tab[1][2] = 6

Je cherche par exemple à avoir une rotation à +90 degrès :
|4,1|
|5,2|
|6,3|
donc
tab[0][0] = 4
tab[0][1] = 1
tab[1][0] = 5
tab[1][1] = 2
tab[2][0] = 6
tab[2][1] = 3


Comme vous pouvez le voir, les dimensions du tableau changent...(matrice non carrée)
De plus comment faire pour les autres angles (45°, ...).
Merci pour votre aide.

[Aleph69]

Bonjour,

il y a quelque chose qui n'est pas clair...
Il existe bien des matrices de rotation mais cela n'a absolument rien à voir avec ce que tu souhaites faire. Es-tu sûre d'avoir bien compris ta problématique? Dans quel cadre souhaites-tu faire tes "rotations".

[Aure7780]

Si mon tableau représente chaque pixel d'une image, je cherche à faire une rotation de mon image...

[Aleph69]

Bonjour,

franchement, je ne vois pas ce que tu veux faire, mais en ce qui concerne les rotations de figures, il suffit de passer par des matrices de rotation. Tout est expliqué ici :
http://fr.wikipedia.org/wiki/Matrice_de_rotation
Si tu as des questions n'hésite pas.

[Aure7780]

Dans le wiki, il est dit :

La matrice 4×3 n'est pas carrée et ne peut donc pas être une matrice de rotation

Or je cherche à faire des rotations de toutes matrices (carrée ou non).

C'est simple, une image est un ensemble de pixel.
Une image contient une largeur et une hauteur (en nombre de pixels).
Je définis donc un tableau à 2 dimensions (une pour les lignes et l'autre pour les colonnes). Et chaque case de ce tableau, contient la valeur du pixel en RGB (simplifié par un entier dans mon exemple).

Lorsqu'on fait une rotation à +90° d'une image, on déplace les pixels pour modifier l'image. Par exemple le pixel en haut à gauche se retrouve en haut à droite et celui en haut à droite se retrouve en bas à droite, ....

Moi je cherche la formule mathématique/algo qui permet de faire une rotation de ce tableau à 2 dimensions quelque soit l'angle de rotation !

[Aleph69]

Bonjour,

je ne vois pas la contradiction. Une matrice de rotation est nécessairement carrée mais tu peux l'appliquer à une matrice rectangulaire sous réserve que le nombre de lignes de cette dernière soit égal à la taille de la matrice de rotation bien sûr.

Je reviens un peu sur ton histoire de pixels. Je ne m'y connais pas spécialement mais j'aurais tendance à dire que tes pixels représentent finalement des coordonnées. Ce qui pose problème dans ton exemple de rotation à 90 degrés, c'est que les valeurs de tes pixels sont les mêmes avant et après rotation. En gros, tu as fait "tourner" ton tableau un peu à la manière de ce que l'on fait pour transposer une matrice. Or, ce qui est très bizarre, c'est que tu demandes une formule pour tous les angles : mais une formule pour calculer quoi vu que rien ne change???

[Aure7780]

Envoyé par Aleph69

Ce qui pose problème dans ton exemple de rotation à 90 degrés, c'est que les valeurs de tes pixels sont les mêmes avant et après rotation. En gros, tu as fait "tourner" ton tableau un peu à la manière de ce que l'on fait pour transposer une matrice. Or, ce qui est très bizarre, c'est que tu demandes une formule pour tous les angles : mais une formule pour calculer quoi vu que rien ne change???

Le valeur des pixels de doivent pas changer, mais c'est leur position dans le tableau à 2 dimensions qui change !
Ex:
tab[0][0] = 1 -> tab[0][1] = 1
tab[0][1] = 2 -> tab[1][1] = 2
tab[0][2] = 3 -> tab[2][1] = 3
tab[1][0] = 4 -> tab[0][0] = 4
tab[1][1] = 5 -> tab[1][0] = 5
tab[1][2] = 6 -> tab[2][0] = 6

Le premier tableau est un 2x3, alors qu'après la rotation c'est un 3x2.
Mais comment définir ce changement mathématiquement ? Avec une matrice de rotation ? (si oui, comment ?)

[Aleph69]

Pour commencer, ce n'est pas possible de passer d'une matrice 2x3 à une matrice 3x2 en appliquant une matrice de rotation.

Bon, j'ai autre chose à te proposer puisque c'est ce que tu sembles vouloir faire... On va identifier les coins de ton tableau à l'aide d'un système de coordonnées. Disons que tes coins sont les points (0,0), (1,0), (0,1) et (1,1). Pour faire "tourner" ton tableau, il suffit de calculer les nouvelles coordonnées de tes coins après rotation d'angle theta et de tracer les arêtes qui les relient (les côtés de ton tableau si tu préfères). Dans ce cas, il suffit de suivre l'explication de wilkipedia. On pose c=cos(theta), s=sin(theta) et on définit la matrice de rotation R(theta) par
|c s|
|-s c|
Pour calculer les nouvelles coordonnées de tes coins, il suffit d'appliquer ta matrice à chaque point. Par exemple, pour le point (1,0) on trouve
|c s| * |1| = |c|
|-s c| |0| |-s|
c'est-à-dire que le point (1,0) se trouve en (c,-s) après rotation.

Deux remarques :
1. tes pixels ne servent à rien dans l'histoire...
2. la rotation se fait dans le sens inverse des aiguilles d'une montre. Il faudra donc peut-être mettre un signe "moins" devant tous tes angles car j'ai l'impression que tu as choisi l'autre convention (sens des aiguilles d'une montre).

[Aure7780]

En appliquant le produit matricielle sur mes cases :

Code :

1
2
3
4
5
6
7
8
9
tsin = sin(90);
tcos = cos(90);
pour(i=0; i < 2; i++) {
	pour(j=0; j< 3; j++) {
		x = arrondir( tcos * i + tsin * j );
		y = arrondir( -tsin * i + tcos * j );
		affiche( "tab["+i+"]["+j+"] => tab["+x+"]["+y+"]" );
	}
}

j'obtiens :
tab[0][0] => tab[0][0]
tab[0][1] => tab[-1][0]
tab[0][2] => tab[-2][-1]
tab[1][0] => tab[0][1]
tab[1][1] => tab[-1][0]
tab[1][2] => tab[-2][0]

J'ai fais une erreur dans mon algo ? (certains indices sont négatifs )

[Aleph69]

Affiche la valeur de tcos et tsin à chaque fois pour voir.

[pseudocode]

Envoyé par Aure7780

Le valeur des pixels de doivent pas changer, mais c'est leur position dans le tableau à 2 dimensions qui change !

Le premier tableau est un 2x3, alors qu'après la rotation c'est un 3x2.
Mais comment définir ce changement mathématiquement ?

Mathématiquement, c'est une permutation.

[Aleph69]

Ben non justement!

[pseudocode]

Envoyé par Aleph69

Ben non justement!

Oui, je me suis trompé (lu trop vite). J'ai corrigé.

[Aleph69]

En fait c'est la composée d'une permutation par ligne et d'une transposition pour être tout à fait précis.
EDIT : la permutation peut aussi être par colonne, cela dépend de l'ordre de composition.

[pseudocode]

Envoyé par Aleph69

En fait c'est la composée d'une permutation par ligne et d'une transposition pour être tout à fait précis.
EDIT : la permutation peut aussi être par colonne, cela dépend de l'ordre de composition.

Exact. Ca revient a transposer et faire une symétrie par ligne ou colonne.

Pour un tableau Tab de taille W*H

Rot 0° : Tab[i][j] --> Tab[i][j]
Rot 90° : Tab[i][j] --> Tab[H-1-j][i]
Rot 180° : Tab[i][j] --> Tab[W-1-i][H-1-j]
Rot 270° : Tab[i][j] --> Tab[j][W-1-i]

(sauf erreur)

[souviron34]

Envoyé par Aure7780

Moi je cherche la formule mathématique/algo qui permet de faire une rotation de ce tableau à 2 dimensions quelque soit l'angle de rotation !

Je crois (si j'ai bien compris) que tu mélanges 2 choses :

• une image est stockée comme une matrice rectangulaire
  
  
• tu veux faire la rotation d'une image

La formule générale est, pour tout pixel

x' = x cos(a) + y sin(a)
y' = x sin(a) - y cos(a)


Maintenant, suivant l'angle, cela va te donner un ensemble de points englobés par un rectangle... Dont on peut calculer les dimensions en appliquant cet algo aux 4 coins.

Mais on ne transformera pas un rectangle (image initiale) en un autre (image finale) parfaitement rempli... (sauf si la rotation est modulo 90 degrés)

Le rectangle final, dans le cas général, aura du noir... Dans des "coins" plus ou moins grands suivant l'angle. Donc on obtiendra plutôt une sorte de losange, inclus dans un rectangle noir.

Enfin, en général, pour éviter les effets de moiré, on fait en sens inverse : on part du pixel destination et on cherche le pixel d'origine..

[math_lab]

Pour les rotations non multiples de 90 degrés, il faut penser a plusieurs choses: la taille de l'image finale n'aura pas grand chose a voir avec la taille de l'image originale (en gros, ce sera une image plus grande qui contiendra la version tournée de l'image de base au milieu, et du vide dans les coins).
Ensuite, il faut une interpolation des valeurs de ton image, sinon tu vas te retrouver un truc tout pixelisé pas beau: en gros, a cause des arrondis que tu dois faire, tu vas te retrouver avec plusieurs pixels de l'image finale qui 'pointent' vers les mêmes pixels de l'image de base (alors qu'en réalité ils devraient avoir un nième de pixel d’écart). Pour gérer ça, il faut se débrouiller pour deviner la valeur que tu as entre les pixels (l'interpolation linéaire devrait être plus que suffisante).
Et aussi, il faut éviter de partir de l'image de base pour transformer la position de pixels et les coller dans l'image résultat: tu te retrouverais avec des trous un peu partout. Il faire l'inverse en partant de l'image résultat et en cherchant quel pixel correspondrait dans l'image de base.
Un dernier truc, il faut que tu mettes une translation dans ta transformation parce que la, je pense que ça va faire une rotation de centre (0,0) alors que je suppose que tu veux une rotation de centre (milieux, milieuy).

[FR119492]

Salut!

je cherche à faire une rotation de mon image...

Intuitivement, je pense que le plus simple serait de passer par les valeurs singulières.
Jean-Marc Blanc

[Aure7780]

Envoyé par pseudocode

Exact. Ca revient a transposer et faire une symétrie par ligne ou colonne.

Pour un tableau Tab de taille W*H

Rot 0° : Tab[i][j] --> Tab[i][j]
Rot 90° : Tab[i][j] --> Tab[H-1-j][i]
Rot 180° : Tab[i][j] --> Tab[W-1-i][H-1-j]
Rot 270° : Tab[i][j] --> Tab[j][W-1-i]

(sauf erreur)

Ok merci pour ces infos, je vais d'abord me baser sur les multiples de 90° pour la rotation, ça sera plus simple.

Si j'ai des soucis avec l'algo ci-dessus, je reviendrais vers vous.
Peut-être plus tard, j'essaierais la version "toutes angles".

[souviron34]

Envoyé par Aure7780

Peut-être plus tard, j'essaierais la version "toutes angles".

Relis attentivement mon post.

Tu n'auras pas, dans le cas général, de "matrice de rotation" permettant de passer d'un rectangle à un un autre par permutation correspondant à

Je cherche à faire une rotation d'un tableau à plusieurs dimensions (matrice) en fonction d'un angle.

Il te faudra un algo faisant une rotation des pixels, en ayant calculé auparavant avec la rotation des coins la dimension de l'image finale...

Le seul cas où c'est possible est quand les angles sont modulo 90 degrés.