Dans cet article, je vais parler d'une formule inhabituelle qui vous permet de regarder sous un nouvel angle sur les transformations affines, et en particulier sur les problèmes inverses qui se posent en relation avec ces transformations. J'appellerai des problèmes inverses qui nécessitent de calculer la matrice inverse: trouver la transformation par points, résoudre un système d'équations linéaires, transformer des coordonnées lors du changement de base, etc. Je réserve tout de suite qu'il n'y aura pas de découvertes fondamentales dans l'article, ni de réduction de la complexité algorithmique - je vais simplement montrer une formule symétrique et facile à retenir avec laquelle vous pouvez résoudre de manière inattendue de nombreux problèmes de fonctionnement. Pour les amateurs de rigueur mathématique, il y a une présentation plus formalisée ici [1] (orientée vers les étudiants) et un petit livre de problèmes ici [2] .

La transformation affine est généralement définie par la matrice $$$A$ et vecteur de traduction et agit sur l'argument vecteur par la formule

$$

$$\ mathcal {A} (\ vec {x}) = \ hat {A} \ vec {x} + \ vec {t}.$$

Cependant, vous pouvez vous passer de $$$\ vec {t}$ si vous utilisez la matrice augmentée et les coordonnées uniformes pour l'argument (comme cela est bien connu des utilisateurs d'OpenGL). Cependant, il s'avère que, outre ces formes d'écriture, vous pouvez également utiliser le déterminant d'une matrice spéciale, qui contient à la fois les coordonnées de l'argument et les paramètres qui déterminent la transformation. Le fait est que le déterminant a la propriété de linéarité sur les éléments de n'importe quelle ligne ou colonne, ce qui lui permet d'être utilisé pour représenter des transformations affines. Ici, en fait, comment exprimer l'action de la transformation affine sur un vecteur arbitraire $$$\ vec {x}$ :


Ne vous précipitez pas pour vous enfuir avec horreur - premièrement, une transformation est écrite ici qui agit sur des espaces de dimension arbitraire (il y a tellement de choses d'ici), et deuxièmement, bien que la formule semble lourde, elle est simplement mémorisée et utilisée. Pour commencer, je vais mettre en évidence les éléments logiquement liés avec des cadres et des couleurs


Nous voyons donc que l'action de toute transformation affine $$$\ mathcal {A}$ par vecteur peut être représenté comme le rapport de deux déterminants, l'argument vecteur ne saisissant que le haut, et le bas n'est qu'une constante qui ne dépend que des paramètres.

Vecteur en surbrillance bleu $$$\ vec {x}$ Est un argument, le vecteur sur lequel agit la transformation affine $$$\ mathcal {A}$ . Ci-après, les indices désignent la composante du vecteur. Dans la matrice supérieure des composants $$$\ vec {x}$ occupent presque toute la première colonne, sauf pour eux dans cette colonne seulement zéro (haut) et un (bas). Tous les autres éléments de la matrice sont des vecteurs de paramètres (ils sont numérotés en exposant, pris entre parenthèses pour ne pas confondre avec le degré) et les unités de la dernière ligne. Parmi l'ensemble de toutes les transformations affines, les paramètres distinguent ce dont nous avons besoin. La commodité et la beauté de la formule est que la signification de ces paramètres est très simple: ils définissent une transformation affine qui traduit les vecteurs $$$\ vec {x} ^ {\, (i)}$ dans $$$\ vec {X} ^ {(i)}$ . Par conséquent, les vecteurs $$$\ vec {x} ^ {\, (1)}, \ dots, \ vec {x} ^ {\, (n + 1)}$ , nous appellerons «entrée» (ils sont entourés de rectangles dans la matrice) - chacun d'eux est écrit par composant dans sa propre colonne, une unité est ajoutée ci-dessous. Les paramètres de «sortie» sont écrits d'en haut (surlignés en rouge) $$$\ vec {X} ^ {(1)}, \ dots, \ vec {X} ^ {(n + 1)}$ , mais maintenant pas par composant, mais comme une entité entière.

Si quelqu'un est surpris par un tel record, souvenez-vous du produit vectoriel

$$$$ afficher $$ [\ vec {a} \ times \ vec {b}] = \ det \ begin {pmatrix} \ vec {e} _1 & \ vec {e} _2 & \ vec {e} _3 \\ a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ \ end {pmatrix}, $$ display $$

où il y avait une structure très similaire et la première ligne de la même manière était occupée par des vecteurs. De plus, il n'est pas nécessaire que les dimensions des vecteurs $$$\ vec {X} ^ {(i)}$ et $$$\ vec {x} ^ {(i)}$ coïncidé. Tous les déterminants sont considérés comme habituels et permettent les "astuces" habituelles, par exemple, vous pouvez ajouter une autre colonne à n'importe quelle colonne.

Avec la matrice du bas, tout est extrêmement simple - on l'obtient par le haut en supprimant la première ligne et la première colonne. L'inconvénient de (1) est que vous devez prendre les déterminants, cependant, si vous transférez cette tâche de routine sur un ordinateur, il s'avère que la personne n'aura qu'à remplir correctement les matrices avec les nombres de sa tâche. En même temps, en utilisant une formule, vous pouvez résoudre un certain nombre de problèmes pratiques courants:

• trouver une transformation affine par points;
• calcul des coordonnées barycentriques;
• interpolation multilinéaire;
• problèmes de transformation linéaire (sans traduction):
  
  • inversion de matrice;
  • La règle de Cramer dans une formule (non, ce que vous avez vu n'est pas dans une formule);
  • recalcul des coordonnées du vecteur lorsque la base change;
  • interpolation par polynômes de Lagrange.

Transformation affine à trois points sur un plan

Sous l'influence d'une transformation affine inconnue, trois points de l'avion sont passés aux trois autres points. Trouvez cette transformation affine.
Pour être précis, laissez nos points d'entrée


et le résultat de la transformation

Trouvez la transformation affine $$$\ mathcal {A}$ .

En fait, ce problème peut être résolu de différentes manières: en utilisant un système d'équations linéaires, de coordonnées barycentriques ... mais nous suivrons notre propre chemin. Je pense que par la notation utilisée, vous pouvez deviner où je veux en venir: nous prenons l'équation (1) pour la dimension $$$n = 2$ et substitut $$$\ vec {x} ^ {\, (i)}$ comme paramètres d'entrée, et $$$\ vec {X} ^ {\, (i)}$ - comme un week-end


puis il ne reste plus qu'à calculer les déterminants


Un œil entraîné détectera facilement un allumage $$ et diffusé sur $$$((3 + \ sqrt {3}) / 2, 2) ^ {\ mathsf {T}}$ .

Quand la formule est-elle applicable?

Les vecteurs d'entrée et de sortie peuvent avoir des dimensions différentes - la formule s'applique aux transformations affines agissant sur des espaces de n'importe quelle dimension. Cependant, il devrait y avoir suffisamment de points d'entrée et ils ne devraient pas «coller ensemble»: si la transformation affine agit à partir de $$$n$ multidimensionnel - les points doivent former un simplexe non dégénéré $$$n + 1$ des points. Si cette condition n'est pas remplie, il est impossible de restaurer sans ambiguïté la transformation (par n'importe quelle méthode, pas seulement celle-ci) - la formule en avertira par zéro dans le dénominateur.

Pourquoi restaurer une transformation affine à un programmeur?

Souvent, vous devez trouver une transformation entre deux images (pour calculer la position de la caméra, par exemple). Si nous avons des points spéciaux (fonctionnalités) fiables dans ces images, ou si vous n'avez tout simplement pas envie de commencer tout de suite avec des ranzaks et de vous battre avec des débardeurs, alors cette formule peut être utilisée.

Un autre exemple est la texturation . Couper un triangle à partir d'une texture et le tirer sur un triangle quelque part dans un plan ou dans l'espace est une tâche typique pour appliquer la transformation affine aux points d'un espace de texture, en les traduisant dans l'espace où vivent les modèles. Et bien souvent, il nous est facile d’indiquer quels points de la texture correspondent aux sommets du triangle du modèle, mais pour déterminer où vont les points autres que les coins, il faudra peut-être réfléchir. Avec la même formule, il suffit d'insérer simplement les chiffres dans les bonnes cellules et il y aura une telle beauté.

D'après ce que j'ai dû affronter personnellement: le réseau neuronal donne les coordonnées des coins du marqueur et nous voulons «compléter la réalité» avec un objet virtuel situé sur le marqueur.
Évidemment, lors du déplacement du marqueur, l'objet doit répéter tous ses mouvements. Et ici, la formule (1) est très utile - elle nous aidera à déplacer l'objet après le marqueur.

Ou un autre exemple: vous devez programmer la rotation de divers objets sur la scène à l'aide de l'outil gizmo. Pour ce faire, nous devons pouvoir faire pivoter le modèle sélectionné autour de trois axes parallèles aux axes de coordonnées et passant par le centre de l'objet. La photo montre le cas de rotation du modèle autour d'un axe parallèle à $$$Oz$ .

En fin de compte, tout se résume au problème bidimensionnel de la rotation autour d'un point arbitraire. Résolvons-le même pour un cas simple, disons, allumer $$ dans le sens antihoraire autour $$$(a; b)$ (le cas général est résolu de la même manière, je ne veux pas encombrer les calculs avec des sinus et des cosinus). Bien sûr, vous pouvez suivre le chemin des samouraïs et multiplier trois matrices (traduction du point de rotation à zéro, en fait rotation et translation de retour), ou vous pouvez également trouver les coordonnées de trois points avant et après la rotation et utiliser la formule. Le premier point est simple - nous savons déjà que $$$(a; b)$ va en soi. Regardons le point un à droite, car c'est vrai $$$(a + 1; b) \ mapsto (a; b + 1)$ . Eh bien, et encore un ci-dessous, il est évident que $$$(a; b-1) \ mapsto (a + 1; b)$ . Alors tout est simple

Coordonnées barycentriques

Nous décomposons le déterminant supérieur (1) le long de la première ligne selon la règle de Laplace. Il est clair qu'en conséquence, nous obtenons une somme pondérée de vecteurs $$$\ vec {X} ^ {(i)}$ . Il s'avère que les coefficients de cette somme sont les coordonnées barycentriques de l' argument $$$\ vec {x}$ par rapport au simplex donné $$$\ vec {x} ^ {\, (i)}$ (pour les preuves voir [1] ). Si nous ne sommes intéressés que par les coordonnées barycentriques d'un point, nous pouvons tricher et remplir la première ligne avec les orts unitaires - après avoir calculé les déterminants, nous obtenons un vecteur dont les composantes coïncident avec les coordonnées barycentriques $$$\ vec {x}$ . Graphiquement, une telle conversion $$$\ mathcal {B}$ traduire un point dans l'espace de ses coordonnées barycentriques se présentera comme suit


Essayons cette "recette" en pratique. Tâche: trouver les coordonnées barycentriques d'un point par rapport à un triangle donné. Que ce soit un point de définition $$$(2,2) ^ \ mathsf {T}$ , et prenez les sommets d'un triangle


Le point est petit - prenez (1) pour $$$n = 2$ , placez-y correctement les données de tâche et calculez les déterminants


Voici la solution: coordonnées barycentriques $$$(2,2) ^ \ mathsf {T}$ par rapport à un triangle donné, il y a $$ , $$ et $$ . En programmation, le calcul des coordonnées barycentriques se pose souvent dans le cadre de la vérification si un point se trouve à l'intérieur d'un simplexe (alors toutes les coordonnées barycentriques sont supérieures à zéro et inférieures à l'unité), ainsi que pour diverses interpolations, dont nous parlerons maintenant.

Notez que la formule (1) a une dualité agréable: si nous développons le déterminant dans la première colonne, nous obtenons la notation standard pour la fonction affine, et si sur la première ligne nous obtenons la combinaison affine des vecteurs de sortie.

Interpolation multilinéaire

Nous avons donc constaté que la transformation affine pondère les vecteurs de sortie avec des coefficients égaux aux coordonnées barycentriques de l'argument. Il est naturel d'utiliser cette propriété pour une interpolation multilinéaire.

Interpolation des couleurs

Par exemple, calculons le GL standard - le «monde bonjour» - un triangle coloré. Bien sûr, OpenGL sait parfaitement interpoler les couleurs et le fait également en utilisant des coordonnées barycentriques , mais aujourd'hui, nous le ferons nous-mêmes.

Tâche: aux sommets du triangle, les couleurs sont définies, pour interpoler les couleurs à l'intérieur du triangle. Pour être précis, laissez les sommets de notre triangle avoir des coordonnées


Nous leur attribuons des couleurs: jaune, cyan et magenta


Les triplets numériques sont les composants RVB d'une couleur. Prendre (1) et organiser correctement les données d'entrée


Voici les composants $$$\ mathcal {C} (x; y)$ indiquer comment peindre un point $$$(x, y)$ en termes de RVB. Voyons ce qui s'est passé.

Nous pouvons dire que nous venons de faire une transformation affine de l'espace bidimensionnel d'une image en espace tridimensionnel de couleurs (RVB).

Interpolation normale (ombrage Phong)

Nous pouvons mettre une variété de significations dans les vecteurs que nous interpolons, y compris ceux qui peuvent être des vecteurs normaux. De plus, c'est exactement ce que fait l'ombrage de Phong, ce n'est qu'après interpolation que les vecteurs doivent être normalisés. La raison pour laquelle une telle interpolation est nécessaire est bien illustrée par l'image suivante (tirée de Wikipedia commons.wikimedia.org/w/index.php?curid=1556366 ).

Je ne pense plus que cela vaut la peine de faire des calculs - tous les détails sont discutés dans [2] , mais je vais montrer une image avec le résultat.

Les vecteurs sur celui-ci ne sont pas uniques, et pour une utilisation dans l'ombrage Phong, ils doivent d'abord être normalisés, et, pour plus de clarté, ils sont dirigés dans des directions très différentes, ce qui est rarement le cas en pratique.

Trouver un avion $$$z = z (x, y)$ en trois points

Prenons un autre exemple inhabituel de l'application de la transformation affine.
Trois points sont accordés

On retrouve l'équation de l'avion qui les traverse sous la forme $$$z = z (x, y)$ . Et nous le ferons à l'aide de transformations affines: après tout, on sait qu'elles traduisent les plans en plans. Pour commencer, nous concevons tous les points de l'avion $$$Xy$ c'est facile. Et maintenant, nous allons établir une transformation affine qui traduit les projections de points aux points tridimensionnels originaux


et qui "ramasse" avec les points et tout le plan $$$Xy$ à tel point qu'après la transformation, elle passera par les points d'intérêt pour nous.

Comme d'habitude, il suffit de répartir les nombres entre les éléments des matrices


Réécrivez la dernière expression sous la forme habituelle


et dessinez ce qui s'est passé.

Transformations linéaires

Malgré l'importance pratique des transformations affines, il faut souvent faire face à des transformations linéaires. Bien sûr, les transformations linéaires sont un cas particulier des transformations affines, laissant un point en place $$$\ vec {0}$ . Cela nous permet de simplifier un peu la formule (après tout, l'une des colonnes sera composée de presque uniquement des zéros et vous pouvez développer le déterminant par elle)


Comme vous pouvez le voir, la dernière ligne avec des unités et une colonne est manquante dans la formule. Ce résultat est tout à fait cohérent avec nos idées que pour spécifier une transformation linéaire, il suffit d'indiquer son effet sur $$$n$ éléments linéairement indépendants.

Transformation linéaire en trois points

Résolvons le problème pour voir comment tout fonctionne. Problème: on sait que sous l'action d'une transformation linéaire


On retrouve cette transformation linéaire.

Nous prenons une formule simplifiée et mettons les bons nombres aux bons endroits:


C'est fait!

Trouver la transformée inverse

Rappelons que la matrice de transformation linéaire


contient des images de vecteurs unitaires dans ses colonnes:


Donc, agissant comme une matrice sur les vecteurs unitaires, nous obtenons ses colonnes. Et qu'en est-il de la transformation inverse (disons qu'elle existe)? Il fait tout "vice versa":


Attendez une minute, car nous venons de trouver les images de trois points sous l'influence d'une transformation linéaire - assez pour restaurer la transformation elle-même!


où $$$\ vec {e} _1 = (1; 0; 0) ^ \ mathsf {T}$ , $$$\ vec {e} _2 = (0; 1; 0) ^ \ mathsf {T}$ et $$$\ vec {e} _3 = (0; 0; 1) ^ \ mathsf {T}$ .

Nous ne nous limiterons pas à l'espace tridimensionnel et réécrirons la formule précédente sous une forme plus générale

Comme vous pouvez le voir, nous devons attribuer à la matrice de gauche une colonne avec les composants de l'argument vecteur, en haut - une ligne avec des vecteurs de coordonnées, puis ce n'est que la capacité de prendre des déterminants.

Problème de transformation inverse

Essayons la méthode donnée en pratique. Tâche: inverser la matrice


Nous utilisons (2) pour $$$n = 3$


Il est immédiatement clair que

Règle de Cramer dans une formule

Depuis l'école, nous sommes confrontés à des équations de la forme


Si la matrice $$$\ chapeau {A}$ non dégénéré, alors la solution peut être écrite comme


Hmm ... n'est-ce pas dans la section précédente que j'ai vu la même expression, mais à la place $$$b$ était une autre lettre? Nous allons l'utiliser.

Ce n'est autre que la règle de Cramer . Cela peut être facilement vérifié en développant le déterminant sur la première ligne: calcul $$$x_i$ suppose simplement que nous barrons la colonne avec $$$\ vec {e} _i$ et avec $$$i$ Colonne de matrice $$$\ chapeau {A}$ . Maintenant, si vous réorganisez la colonne $$$b$ au lieu de la télécommande, nous obtenons simplement la règle "insérer une colonne $$$b$ en place $$$i$ Th colonne et trouver le déterminant. " Et oui, avec les signes, tout va bien: seul $$$\ pm$ nous générons lors de l'expansion le long de la ligne, tandis que d'autres lors de la réorganisation - en conséquence, ils s'annulent.

En regardant de plus près l'équation obtenue, on peut remarquer sa similitude avec l'équation pour trouver des coordonnées barycentriques: résoudre un système d'équations linéaires, c'est trouver les coordonnées barycentriques d'un point $$$\ vec {b}$ par rapport à un simplex, dont l'un des sommets $$$\ vec {0}$ , et le reste est défini par les colonnes de la matrice $$$\ chapeau {A}$ .

Solution d'un système d'équations linéaires

Nous résolvons le système d'équations linéaires


Sous forme matricielle, cela ressemble à ceci


Nous utilisons la formule résultante


d'où vient la réponse $$$x = 1/25$ , $$$y = 14/25$ et $$$z = 2/5$ .

Transformation des coordonnées vectorielles lors du changement de base

Supposons que nous ayons choisi une nouvelle base (nous sommes passés à un système de coordonnées différent). On sait que les nouvelles coordonnées des vecteurs s'expriment linéairement à travers les anciennes. Il n'est donc pas surprenant que nous puissions utiliser nos outils pour changer la base. Comment faire cela, je vais montrer avec un exemple.

Alors, passons de la base standard $$$\ {\ vec {e} _x, \ vec {e} _y \}$ à une base composée de vecteurs


Dans l'ancienne base, un vecteur est spécifié $$$\ vec {x} = (3,4) ^ \ mathsf {T}$ . Trouvez les coordonnées de ce vecteur dans une nouvelle base. Dans le nouveau système de coordonnées, les vecteurs de la nouvelle base deviendront des orts et auront des coordonnées


ci-après, les traits près des colonnes signifient que les coordonnées en eux se réfèrent à une nouvelle base. Il est facile de deviner qu'une transformation linéaire qui se traduit


convertit également les coordonnées de notre vecteur selon les besoins. Il ne reste plus qu'à appliquer la formule


La solution du problème de la manière habituelle nécessite une inversion de matrice (qui, cependant, consiste également principalement à calculer des déterminants) et une multiplication


Nous venons de regrouper ces étapes dans une seule formule.

Pourquoi la formule fonctionne-t-elle pour les problèmes inverses?

L'efficacité de la formule dans la résolution de problèmes inverses s'explique par l'égalité suivante (la preuve est en [1] )


Ainsi, la formule cache en elle-même la matrice inverse et la multiplication par une autre matrice en plus. Cette expression est la solution standard au problème de la recherche d'une transformation linéaire par points. Notez qu'en faisant la deuxième matrice dans l'identité du produit, nous obtenons juste la matrice inverse. Avec son aide, un système d'équations linéaires et les problèmes qui peuvent y être résolus sont résolus: recherche de coordonnées barycentriques, interpolation par polynômes de Lagrange, etc. Cependant, la représentation sous la forme d'un produit de deux matrices ne permet pas d'obtenir les «deux regards» associés à l'expansion sur la première ligne et sur la première colonne.

L'interpolation de Lagrange et ses propriétés

Permettez-moi de vous rappeler que l' interpolation de Lagrange trouve le moins de polynômes passant par des points $$$(a_0; b_0)$ , $$$(a_1; b_1)$ , $$$\ points$ , $$$(a_n; b_n)$ . Non pas que c'était une tâche courante dans la pratique du programmeur, mais regardons-la quand même.

Comment les polynômes et les transformations linéaires sont-ils liés?

Le fait est que le polynôme


peut être considéré comme une transformation linéaire qui affiche le vecteur $$$(x ^ n; x ^ {n-1}; \ dots; 1) ^ T$ dans $$$\ mathbb {R}$ . Donc, le problème d'interpolation ponctuelle $$$(a_0; b_0)$ , $$$(a_1; b_1)$ , $$$\ points$ , $$$(a_n; b_n)$ se réduit à trouver une telle transformation linéaire


et nous pouvons le faire. Remplacez les bonnes lettres dans les bonnes cellules et obtenez la formule


La preuve que ce sera le polynôme de Lagrange (et pas quelqu'un d'autre) peut être trouvée dans [1] . Soit dit en passant, l'expression au dénominateur est l'identifiant de Vandermonde. Sachant cela et élargissant le déterminant du numérateur le long de la première ligne, nous arrivons à une formule plus familière pour le polynôme de Lagrange.

Problème sur le polynôme de Lagrange

Est-ce difficile à utiliser? Essayons les forces sur le problème: trouver le polynôme de Lagrange passant par les points $$$(- 1; 2)$ , $$$(3; 4)$ et $$$(2; 7)$ .

Remplacez ces points dans la formule


Sur le graphique, tout ressemblera à ceci.

Propriétés du polynôme de Lagrange

Après avoir disposé le déterminant supérieur dans la première ligne et la première colonne, nous regardons le polynôme de Lagrange de deux côtés différents. Dans le premier cas, nous obtenons la formule classique de Wikipedia, et dans le second, nous écrivons le polynôme sous la forme de la somme des monômes $$$\ alpha_i x ^ i$ où


Et maintenant, nous pouvons relativement facilement prouver des déclarations assez complexes. Par exemple, dans [2], il a été prouvé sur une ligne que la somme des polynômes de Lagrange de base est égale à un et que le polynôme de Lagrange interpolant $$$(a_0; a_0 ^ {n + 1})$ , $$$\ points$ , $$$(a_n; a_n ^ {n + 1})$ a une valeur nulle $$$(- 1) ^ {n} a_0 \ cdot \ cdots \ cdot a_n$ . Eh bien, pas un seul Lagrange - une approche similaire peut être appliquée à l'interpolation par des sinus-cosinus ou d'autres fonctions.

Conclusion

Merci à tous ceux qui ont lu jusqu'à la fin. Dans cet article, nous avons résolu des problèmes standard en utilisant une formule non standard. Je l'ai aimé parce que, tout d'abord, cela montre que les transformations affines (linéaires), les coordonnées barycentriques, l'interpolation et même les polynômes de Lagrange sont étroitement liés. Après tout, lorsque les solutions aux problèmes sont écrites de la même manière, la pensée de leur affinité se pose d'elle-même. Deuxièmement, la plupart du temps, nous avons simplement organisé les données d'entrée dans les cellules correctes sans transformations supplémentaires.

Les tâches que nous avons envisagées peuvent également être résolues par des méthodes assez familières. Cependant, pour des problèmes de petite dimension ou des tâches éducatives, la formule peut être utile. De plus, elle me semble belle.

Les références

[ 1] Guide du débutant pour cartographier affinement les simplexes

[ 2] Cahier d'exercices sur la cartographie affinée des simplexes