En 2012, j’ai créé une application d’appareil photo simple pour Android qui annule la projection naturelle d’une image.
Bien sûr, nous avons maintenant toutes sortes d’applications de numérisation sur chaque téléphone, mais à l’époque, c’était une nouveauté. Décortiquons l’application et voyons de quoi elle est faite.
Mais d’abord, un petit récapitulatif de la transformation projective. La formule de la transformation projective est indiquée ci-dessous.
Xp = (hacheje + parje + c) / (gxje + hyje + je)
etp = (dxje + ehje + f) / (gxje + hyje + je)
En coordonnées homogènes, tous les composants polynomiaux deviendront également homogènes et le dénominateur pourrait être 1.
Xp = (hacheje + parje + sensje) / (gxje + hyje + et dansje)
etp = (dxje + ehje + fwje) / (gxje + hyje + et dansje)
wp = 1
À moins que le dénominateur ne soit 0, et dans les transformations projectives réelles, ce n’est pas le cas, nous pouvons multiplier toutes les coordonnées par le dénominateur. Rappelez-vous, (1, 0, 1) et (2, 0, 2) est le même point.
Xp = hacheje + parje + sensje
etp = dxje + ehje + fwje
wp = gxje + hyje + et dansje
Si vous connaissez la règle ligne sur colonne, vous voyez probablement déjà la ressemblance avec la multiplication matricielle. En effet, en coordonnées homogènes, nous pouvons réécrire notre transformation projective en multiplication matricielle.
Le projectif est une transformation en quatre points, donc toute l’entrée dont nous avons besoin est une image, que l’API de la caméra nous fournit, et quatre points d’angle d’un rectangle que nous demanderons à l’utilisateur de sélectionner.
Les applications de numérisation modernes sélectionnent automatiquement les points, mais pas toujours avec un grand succès. Cette sélection automatique est un problème intéressant en soi, mais elle a peu à voir avec les transformations projectives, nous la laisserons donc de côté pour l’instant.
Résoudre symboliquement un système pour une transformation arbitraire en 4 points est un peu problématique. Cela prend une éternité dans SymPy, et la solution elle-même semble également être déraisonnablement énorme.
Bien sûr, nous avons toujours la possibilité de le résoudre numériquement, mais il est généralement plus rapide de calculer les choses en exécutant simplement une formule toute faite qu’avec un solveur numérique. Laissez-moi vous montrer comment obtenir les formules que vous voulez.
Ainsi, le problème de numérisation est le suivant. Pour chaque pixel d’une image rectangulaire cible, trouvez la couleur de pixel d’origine à partir d’une photographie, étant donné que les quatre points d’angle de l’image rectangulaire ont leurs points correspondants dans l’image de l’appareil photo.
Cela peut sembler quelque chose qui implique un quadrilatère convexe à une transformation rectangulaire, mais en fait, c’est le contraire. Pour chaque pixel de l’image plate, nous voulons trouver d’où il vient. La transformation est rectangulaire au quadrilatère, et non l’inverse.
Maintenant, pourquoi est-ce soudain important ? Parce que nous pouvons maintenant appeler le cube standard pour obtenir de l’aide.
Une transformation de cube rectangulaire en cube standard n’est qu’une mise à l’échelle. Disons que notre rectangle a une largeur « w » et une hauteur « h ». La matrice de transformation qui transforme ses pixels en cube standard est la suivante.
Maintenant, la deuxième transformation – du cube standard à l’image source est un peu plus délicate. Écrivons le système que SymPy doit résoudre. Dans notre entrée, x1, y1 … x4, y4 sont les points initiaux, xt1, yt1 … xt4, yt4 sont les points transformés, et a, b, c, d, e, f, g, h, i sont les éléments de la matrice de transformation.
Une transformation en quatre points ne nous donne que 8 équations : deux pour chacun des quatre points. Heureusement, si nous multiplions une matrice par un nombre, elle portera toujours la même transformation. C’est à l’épreuve de l’entartrage. Alors choisissons simplement une matrice avec i == 1, et le reste se redimensionnera automatiquement pour former la transformation que nous voulons.
[
xt1 * x1 * g + xt1 * y1 * h + xt1 * i – x1 * a – y1 * b – c,
yt1 * x1 * g + yt1 * y1 * h + yt1 * i – x1 * d – y1 * e – f,
xt2 * x2 * g + xt2 * y2 * h + xt2 * i – x2 * a – y2 * b – c,
yt2 * x2 * g + yt2 * y2 * h + yt2 * i – x2 * d – y2 * e – f,
xt3 * x3 * g + xt3 * y3 * h + xt3 * i – x3 * a – y3 * b – c,
yt3 * x3 * g + yt3 * y3 * h + yt3 * i – x3 * d – y3 * e – f,
xt4 * x4 * g + xt4 * y4 * h + xt4 * i – x4 * a – y4 * b – c,
yt4 * x4 * g + yt4 * y4 * h + yt4 * i – x4 * d – y4 * e – f,
i – 1
], (a, b, c, d, e, f, g, h, i))
Le système est grand, bien sûr, mais appliquons-y nos coordonnées cubiques standard et voyons ce qui se passera.
L’ordre exact dans lequel nous choisissons nos coordonnées n’a pas d’importance, donc cela fera l’affaire.
(x1, y1) = (0, 0)
(x2, y2) = (1, 0)
(x3, y3) = (1, 1)
(x4, y4) = (0, 1)
En appliquant ces nombres spécifiques aux équations, nous les rendons plus petites et plus simples.
[
xt1 * i – c,
yt1 * i – f,
xt2 * g + xt2 * i – a – c,
yt2 * g + yt2 * i – d – f,
xt3 * g + xt3 * h + xt3 * i – a – b – c,
yt3 * g + yt3 * h + yt3 * i – d – e – f,
xt4 * h + xt4 * i – b – c,
yt4 * h + yt4 * i – e – f,
i – 1
], (a, b, c, d, e, f, g, h, i))
Il s’agit d’une version allégée du même système mais, plus important encore, il ne doit plus s’agir d’un seul système ! Il y a maintenant 4 pièces que nous pouvons résoudre une par une. Beaucoup plus rapide et avec des solutions plus compactes également.
Il y a le « je » évident.
[i – 1 ], (je)
Puis, avec le « i » connu, les deux premières équations deviennent indépendantes.
[xt1 * i – c] , (c)
et
[yt1 * i – f,], (F)
Ensuite, connaissant le « c » et le « f », nous pouvons résoudre les deux équations suivantes ainsi que les deux à la fin en termes de « g » et « h ».
c = xt1
f = yt1
je = 1
[xt2 * g + xt2 * i – a – c,
yt2 * g + yt2 * i – d – f,
xt4 * h + xt4 * i – b – c,
yt4 * h + yt4 * i – e – f] , (a, b, d, e)
Le résultat sera plutôt compact :
{a : g*xt2 – xt1 + xt2, d : g*yt2 – yt1 + yt2, b : h*xt4 – xt1 + xt4, e : h*yt4 – yt1 + yt4}
Et réutilisable ! Finissons tout le système avec ces équations.
a = g*xt2 – xt1 + xt2
d = g*yt2 – yt1 + yt2
b = h*xt4 – xt1 + xt4
e = h*yt4 – yt1 + yt4
solution_3 = résoudre([
xt3 * g + xt3 * h + xt3 * i – a – b – c,
yt3 * g + yt3 * h + yt3 * i – d – e – f,
], (g, h))
La solution pour cela sera dans les « x » et « y » seulement. Aucune autre variable.
g : (xt1*yt3 – xt1*yt4 – xt2*yt3 + xt2*yt4 – xt3*yt1 + xt3*yt2 + xt4*yt1 – xt4*yt2)/(xt2*yt3 – xt2*yt4 – xt3*yt2 + xt3 *yt4 + xt4*yt2 – xt4*yt3),
h : (xt1*yt2 – xt1*yt3 – xt2*yt1 + xt2*yt4 + xt3*yt1 – xt3*yt4 – xt4*yt2 + xt4*yt3)/(xt2*yt3 – xt2*yt4 – xt3*yt2 + xt3 *yt4 + xt4*yt2 – xt4*yt3)
Avec ces formules, nous pouvons calculer « g » et « h » numériquement pour tous les quatre points de la transformation de cube standard, et l’utiliser pour calculer « a », « b », « d » et « e ». Calculer « c » et « f » à partir de leurs formules simples, et mettre « i » comme 1 complétera la solution.
Nous avons donc maintenant une transformation qui met les pixels à l’échelle aux points du cube standard et une transformation qui transforme les points du cube standard à l’image source. Nous pouvons les composer en une seule transformation, puis l’appliquer à chaque point de l’image rectangulaire cible pour savoir d’où elle doit prendre sa couleur.
Il reste encore quelques problèmes moins pertinents à résoudre.
Premièrement, comment connaît-on la taille de l’image rectangulaire ? Et la réponse est que non. Il y a une transformation projective pour chaque rectangle en chaque quadrilatère possible. Bien sûr, la plupart d’entre eux sont improbables en pratique, bien que je ne sois pas sûr qu’il soit même grammaticalement correct d’appliquer le mot « plus » à un continuum infini.
Alors résolvons cela de manière constructive. Nous ne voulons pas que notre image soit trop pixelisée, ce qui signifie que beaucoup de pixels sur les pixels cibles correspondraient à un seul pixel sur la source, mais nous ne voulons pas non plus perdre de données, ce qui signifie qu’il y aurait des pixels sur l’image source qui ne transmettrait sa couleur à aucun pixel de la cible.
La règle empirique que j’ai trouvée est la suivante : la hauteur de l’image cible doit être la moyenne des longueurs de segment du point 1 au point 4 et du point 2 au point 3. La largeur est alors la moyenne des longueurs de segment du point 1 à 2, et de 3 à 4.
Ce n’est pas des maths, c’est de l’ingénierie. Il n’est pas prouvé que ce soit optimal, c’est juste quelque chose qui fonctionne la plupart du temps. N’hésitez pas à proposer vos propres solutions.
Un autre problème est de savoir comment calculer les couleurs entre les pixels afin que l’image cible devienne agréable et lisse. C’est un problème complètement indépendant et il est abordé dans les derniers chapitres de mon livre, Géométrie pour les programmeurs.