Comment inverser le projet 2D en 3D?

J’ai 4 points 2D dans l’espace écran et je dois les renverser dans l’espace 3D. Je sais que chacun des 4 points est un coin d’un rectangle rigide en rotation 3D, et je connais la taille du rectangle. Comment puis-je obtenir des coordonnées 3D à partir de cela?

Je n’utilise pas d’API particulière et je n’ai pas de masortingce de projection existante. Je cherche juste des mathématiques de base pour le faire. Bien sûr, il n’y a pas assez de données pour convertir un seul point 2D en 3D sans autre référence, mais j’imagine que si vous avez 4 points, vous savez qu’ils sont tous perpendiculaires sur le même plan. et vous connaissez la distance entre eux, vous devriez être capable de le comprendre à partir de là. Malheureusement, je ne peux pas vraiment savoir comment.

Cela pourrait tomber sous le parapluie de la photogrammésortinge, mais les recherches sur Google ne m’ont pas conduit à des informations utiles.

Bon, je suis venu ici pour chercher une réponse et n’ai pas trouvé quelque chose de simple et direct, alors je suis allé de l’avant et j’ai fait la chose stupide mais efficace (et relativement simple): l’optimisation de Monte Carlo.

En termes simples, l’algorithme est le suivant: Perturbation aléatoire de votre masortingce de projection jusqu’à ce qu’elle projette vos coordonnées 3D connues sur vos coordonnées 2D connues.

Voici une photo de Thomas the Tank Engine:

Thomas le moteur du réservoir

Disons que nous utilisons GIMP pour trouver les coordonnées 2D de ce que nous pensons être un carré sur le plan de masse (que ce soit ou non un carré dépend de votre jugement de la profondeur):

Avec un contour du carré

Je reçois quatre points dans l’image 2D: (318, 247) , (326, 312) , (418, 241) et (452, 303) .

Par convention, on dit que ces points doivent correspondre aux points 3D: (0, 0, 0) , (0, 0, 1) , (1, 0, 0) et (1, 0, 1) . En d’autres termes, une unité carrée dans le plan y = 0.

La projection de chacune de ces coordonnées 3D en 2D se fait en multipliant le vecteur 4D [x, y, z, 1] par une masortingce de projection 4×4, puis en divisant les composantes x et y par z pour obtenir la correction de perspective. C’est plus ou moins ce que gluProject () fait, sauf que gluProject() prend également en compte la fenêtre d’ gluProject() actuelle et prend en compte une masortingce de vue modèle (nous pouvons simplement supposer que la masortingce modelview est la masortingce d’identité). Il est très pratique de regarder la documentation de gluProject() car je souhaite en fait une solution qui fonctionne pour OpenGL, mais attention, la division ne contient pas la division par z dans la formule.

Rappelez-vous que l’algorithme doit commencer par une masortingce de projection et le perturber de manière aléatoire jusqu’à ce qu’il donne la projection souhaitée. Nous allons donc projeter chacun des quatre points 3D et voir à quel point nous atteignons les points 2D que nous voulions. Si nos perturbations aléatoires rapprochent les points 2D projetés de ceux que nous avons indiqués ci-dessus, nous conservons cette masortingce comme une amélioration par rapport à notre estimation initiale (ou précédente).

Définissons nos points:

 # Known 2D coordinates of our rectangle i0 = Point2(318, 247) i1 = Point2(326, 312) i2 = Point2(418, 241) i3 = Point2(452, 303) # 3D coordinates corresponding to i0, i1, i2, i3 r0 = Point3(0, 0, 0) r1 = Point3(0, 0, 1) r2 = Point3(1, 0, 0) r3 = Point3(1, 0, 1) 

Il faut commencer par une masortingce, la masortingce d’identité semble un choix naturel:

 mat = [ [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], ] 

Nous devons réellement mettre en œuvre la projection (qui est essentiellement une multiplication masortingcielle):

 def project(p, mat): x = mat[0][0] * px + mat[0][1] * py + mat[0][2] * pz + mat[0][3] * 1 y = mat[1][0] * px + mat[1][1] * py + mat[1][2] * pz + mat[1][3] * 1 w = mat[3][0] * px + mat[3][1] * py + mat[3][2] * pz + mat[3][3] * 1 return Point(720 * (x / w + 1) / 2., 576 - 576 * (y / w + 1) / 2.) 

C’est fondamentalement ce que fait gluProject() , 720 et 576 sont la largeur et la hauteur de l’image, respectivement (c.-à-d. La fenêtre d’affichage), et nous soustrayons de 576 pour le fait que nous avons compté y eux du fond. Vous remarquerez que nous ne calculons pas z, car nous n’en avons pas vraiment besoin ici (bien que cela puisse être pratique pour vous assurer qu’il se situe dans la plage utilisée par OpenGL pour le tampon de profondeur).

Maintenant, nous avons besoin d’une fonction pour évaluer la proximité de la solution. La valeur renvoyée par cette fonction est ce que nous allons utiliser pour vérifier si une masortingce est meilleure qu’une autre. J’ai choisi de passer par la sum des distances au carré, c’est-à-dire:

 # The squared distance between two points a and b def norm2(a, b): dx = bx - ax dy = by - ay return dx * dx + dy * dy def evaluate(mat): c0 = project(r0, mat) c1 = project(r1, mat) c2 = project(r2, mat) c3 = project(r3, mat) return norm2(i0, c0) + norm2(i1, c1) + norm2(i2, c2) + norm2(i3, c3) 

Pour perturber la masortingce, il suffit de choisir un élément à perturber d’une quantité aléatoire dans une certaine plage:

 def perturb(amount): from copy import deepcopy from random import randrange, uniform mat2 = deepcopy(mat) mat2[randrange(4)][randrange(4)] += uniform(-amount, amount) 

(Il est intéressant de noter que notre fonction project() n’utilise pas du tout mat[2] , puisque nous ne calculons pas z et que toutes nos coordonnées y sont égales à 0, les valeurs de mat[*][1] sont sans importance. Nous pourrions utiliser ce fait et ne jamais essayer de perturber ces valeurs, ce qui donnerait une petite accélération, mais cela rest comme un exercice …)

Pour plus de commodité, ajoutons une fonction qui effectue le gros de l’approximation en appelant perturb() encore et encore sur la meilleure masortingce que nous ayons trouvée jusqu’à présent:

 def approximate(mat, amount, n=100000): est = evaluate(mat) for i in xrange(n): mat2 = perturb(mat, amount) est2 = evaluate(mat2) if est2 < est: mat = mat2 est = est2 return mat, est 

Maintenant, tout ce qui rest à faire est de l'exécuter ...:

 for i in xrange(100): mat = approximate(mat, 1) mat = approximate(mat, .1) 

Je trouve que cela donne déjà une réponse assez précise. Après avoir fonctionné pendant un moment, la masortingce que j'ai trouvée était:

 [ [1.0836000765696232, 0, 0.16272110011060575, -0.44811064935115597], [0.09339193527789781, 1, -0.7990570384334473, 0.539087345090207 ], [0, 0, 1, 0 ], [0.06700844759602216, 0, -0.8333379578853196, 3.875290562060915 ], ] 

avec une erreur d'environ 2.6e-5 . (Remarquez que les éléments que nous avons dit n’ont pas été utilisés dans le calcul n’ont pas été modifiés par rapport à notre masortingce initiale, car la modification de ces entrées ne changerait pas le résultat de l’évaluation et le changement ne serait donc jamais effectué.)

Nous pouvons passer la masortingce dans OpenGL en utilisant glLoadMasortingx() (mais n'oubliez pas de la transposer d'abord, et n'oubliez pas de charger votre masortingce modelview avec la masortingce d'identité):

 def transpose(m): return [ [m[0][0], m[1][0], m[2][0], m[3][0]], [m[0][1], m[1][1], m[2][1], m[3][1]], [m[0][2], m[1][2], m[2][2], m[3][2]], [m[0][3], m[1][3], m[2][3], m[3][3]], ] glLoadMasortingxf(transpose(mat)) 

Maintenant, nous pouvons par exemple traduire le long de l'axe z pour obtenir différentes positions le long des pistes:

 glTranslate(0, 0, frame) frame = frame + 1 glBegin(GL_QUADS) glVertex3f(0, 0, 0) glVertex3f(0, 0, 1) glVertex3f(1, 0, 1) glVertex3f(1, 0, 0) glEnd() 

Avec la traduction 3D

Pour sûr, ce n'est pas très élégant d'un sharepoint vue mathématique; vous n'obtenez pas une équation de forme fermée que vous pouvez simplement twigr sur vos chiffres et obtenir une réponse directe (et précise). Cependant, cela vous permet d'append des contraintes supplémentaires sans avoir à vous soucier de compliquer vos équations; Par exemple, si nous voulions également incorporer de la hauteur, nous pourrions utiliser ce coin de la maison et dire (dans notre fonction d'évaluation) que la distance entre le sol et le toit devrait être telle et exécuter à nouveau l'algorithme. Donc oui, c'est une sorte de force brute, mais ça marche et ça marche bien.

Choo choo!

C’est le problème classique de la réalité augmentée basée sur les marqueurs.

Vous avez un marqueur carré (2D Barcode), et vous voulez trouver sa pose (translation et rotation par rapport à la caméra), après avoir trouvé les quatre bords du marqueur. Vue d’ensemble

Je ne suis pas au courant des dernières consortingbutions sur le terrain, mais au moins jusqu’à un certain point (2009) RPP était censé surpasser POSIT mentionné ci-dessus (et est en effet une approche classique pour cela). fournir la source.

(PS – Je sais que c’est un sujet un peu ancien, mais de toute façon, le post pourrait être utile à quelqu’un)

D. DeMenthon a mis au point un algorithme pour calculer la pose d’un object (sa position et son orientation dans l’espace) à partir de points caractéristiques d’une image 2D lorsqu’il connaît le modèle de l’object – c’est votre problème exact :

Nous décrivons une méthode pour trouver la pose d’un object à partir d’une image unique. Nous supposons que nous pouvons détecter et faire correspondre dans l’image quatre points caractéristiques non-coplanaires ou plus de l’object, et que nous connaissons leur géomésortinge relative sur l’object.

L’algorithme est connu sous le nom de Posit et est décrit dans son article classique “Pose d’object basée sur un modèle dans 25 lignes de code” (disponible sur son site Web , section 4).

Lien direct vers l’article: http://www.cfar.umd.edu/~daniel/daniel_papersfordownload/Pose25Lines.pdf Implémentation d’OpenCV: http://opencv.willowgarage.com/wiki/Posit

L’idée est de faire une approximation répétée de la projection en perspective par une projection orthographique mise à l’échelle jusqu’à ce qu’elle converge vers une pose précise.

Pour mon moteur OpenGL, le snip suivant convertira les coordonnées souris / écran en coordonnées 3D. Lisez les commentaires pour une description réelle de ce qui se passe.

 / * FONCTION: YCamera :: CalculateWorldCoordinates
      ARGUMENTS: x souris x coordonnées
                       y souris y coordonne
                       vec où stocker les coordonnées
      RETOUR: so
      DESCRIPTION: Convertir les coordonnées de la souris en coordonnées du monde
 * /

void YCamera :: CalculateWorldCoordinates(float x, float y, YVector3 *vec) { // START GLint viewport[4]; GLdouble mvmasortingx[16], projmasortingx[16];

 GLint real_y; GLdouble mx, my, mz; glGetIntegerv(GL_VIEWPORT, viewport); glGetDoublev(GL_MODELVIEW_MATRIX, mvmasortingx); glGetDoublev(GL_PROJECTION_MATRIX, projmasortingx); real_y = viewport[3] - (GLint) y - 1; // viewport[3] is height of window in pixels gluUnProject((GLdouble) x, (GLdouble) real_y, 1.0, mvmasortingx, projmasortingx, viewport, &mx, &my, &mz); /* 'mouse' is the point where mouse projection reaches FAR_PLANE. World coordinates is intersection of line(camera->mouse) with plane(z=0) (see LaMothe 306) Equation of line in 3D: (x-x0)/a = (y-y0)/b = (z-z0)/c Intersection of line with plane: z = 0 x-x0 = a(z-z0)/c <=> x = x0+a(0-z0)/c <=> x = x0 -a*z0/c y = y0 - b*z0/c */ double lx = fPosition.x - mx; double ly = fPosition.y - my; double lz = fPosition.z - mz; double sum = lx*lx + ly*ly + lz*lz; double normal = sqrt(sum); double z0_c = fPosition.z / (lz/normal); vec->x = (float) (fPosition.x - (lx/normal)*z0_c); vec->y = (float) (fPosition.y - (ly/normal)*z0_c); vec->z = 0.0f; 

}

À partir de l’espace 2D, deux rectangles valides peuvent être créés. Sans connaître la projection de la masortingce d’origine, vous ne saurez pas laquelle est correcte. C’est la même chose que le problème “box”: vous voyez deux carrés, l’un dans l’autre, avec les 4 sumts internes connectés aux 4 sumts extérieurs respectifs. Regardez-vous une boîte de haut en bas ou de bas en haut?

Cela étant dit, vous recherchez une masortingce de transformation T où …

{{x1, y1, z1}, {x2, y2, z2}, {x3, y3, z3}, {x4, y4, z4}} x T = {{x1, y1}, {x2, y2}, { x3, y3}, {x4, y4}}

(4 x 3) x T = (4 x 2)

Donc, T doit être une masortingce (3 x 2). Nous avons donc 6 inconnues.

Maintenant, construisez un système de contraintes sur T et résolvez avec Simplex. Pour construire les contraintes, vous savez qu’une ligne passant par les deux premiers points doit être parallèle à la ligne passant aux deux autres points. Vous savez qu’une ligne passant par les points 1 et 3 doit être parallèle aux lignes passant par les points 2 et 4. Vous savez qu’une ligne passant par 1 et 2 doit être orthogonale à une ligne passant par les points 2 et 3. Vous savez que la longueur de la ligne de 1 et 2 doit être égale à la longueur de la ligne de 3 et 4. Vous savez que la longueur de la ligne de 1 et 3 doit être égale à la longueur de la ligne de 2 et 4.

Pour rendre cela encore plus facile, vous connaissez le rectangle, de sorte que vous connaissez la longueur de tous les côtés.

Cela devrait vous donner beaucoup de contraintes pour résoudre ce problème.

Bien sûr, pour revenir, vous pouvez trouver l’inverse de T.

@Rob: Oui, il existe un nombre infini de projections, mais pas un nombre infini de projets où les points doivent satisfaire aux exigences d’un rectangle.

@nlucaroni: Oui, cela ne peut être résolu que si vous avez quatre points dans la projection. Si le rectangle ne dépasse pas 2 points (c’est-à-dire que le plan du rectangle est orthogonal à la surface de projection), cela ne peut pas être résolu.

Hmmm … je devrais rentrer chez moi et écrire ce petit bijou. Cela semble amusant.

Mises à jour:

  1. Il y a un nombre infini de projections à moins que vous ne fixiez l’un des points. Si vous fixez des points du rectangle d’origine, il existe deux rectangles originaux possibles.

En supposant que les points font effectivement partie d’un rectangle, je donne une idée générique:

Trouver deux points avec inter-distance max: ceux-ci définissent le plus probablement une diagonale (exception: cas particulier où le rectangle est presque parallèle au plan YZ, laissé à l’élève). Appelez-les A, C. Calculez les angles BAD, BCD. Celles-ci, comparées aux angles droits, vous donnent une orientation dans l’espace 3D. Pour en savoir plus sur la distance z, vous devez corréler les côtés projetés aux côtés connus, puis, selon la méthode de projection 3D (est-ce 1 / z?), Vous êtes sur la bonne voie pour connaître les distances.

Pour suivre l’approche Rons: Vous pouvez trouver vos valeurs Z si vous savez comment vous avez fait pivoter votre rectangle.

L’astuce consiste à trouver la masortingce projective qui a fait la projection. Heureusement, c’est possible et même pas cher à faire. Les mathématiques pertinentes se trouvent dans l’étude intitulée «Projective Mappings for Image Warping» de Paul Heckbert.

http://pages.cs.wisc.edu/~dyer/cs766/readings/heckbert-proj.pdf

De cette façon, vous pouvez récupérer la partie homogène de chaque sumt qui a été perdu lors de la projection.

Maintenant, il vous rest quatre lignes au lieu de points (comme Ron l’expliquait). Comme vous connaissez la taille de votre rectangle d’origine, rien n’est perdu. Vous pouvez maintenant twigr les données de la méthode de Ron et de l’approche 2D dans un résolveur d’équations linéaires et résoudre z. Vous obtenez les valeurs z exactes de chaque sumt de cette façon.

Note: Cela fonctionne simplement parce que:

  1. La forme originale était un rectangle
  2. Vous connaissez la taille exacte du rectangle dans l’espace 3D.

C’est vraiment un cas particulier.

J’espère que ça aide, Nils

La projection que vous avez sur la surface 2D contient une infinité de rectangles 3D qui vont se projeter sur la même forme 2D.

Pensez-y de cette façon: vous avez quatre points 3D qui composent le rectangle 3D. Appelez-les (x0, y0, z0), (x1, y1, z1), (x2, y2, z2) et (x3, y3, z3). Lorsque vous projetez ces points sur le plan xy, vous déposez les coordonnées z: (x0, y0), (x1, y1), (x2, y2), (x3, y3).

Maintenant, vous souhaitez projeter dans l’espace 3D, vous devez procéder au reverse engineering de ce que sont z0, .., z3. Mais tout ensemble de coordonnées z qui a) garde la même distance xy entre les points et b) garde la forme qu’un rectangle fonctionnera. Ainsi, tout membre de cet ensemble (infini) fera: {(z0 + i, z1 + i, z2 + i, z3 + i) | i <- R}.

Modifier @Jarrett: Imaginez que vous ayez résolu ce problème et que vous vous retrouviez avec un rectangle dans un espace 3D. Maintenant, imaginez glisser ce rectangle de haut en bas sur l’axe des z. Ces infinis de rectangles traduits ont tous la même projection xy. Comment savez-vous que vous avez trouvé le “bon”?

Edit # 2: D’accord, c’est à partir d’un commentaire que j’ai fait sur cette question – une approche plus intuitive pour raisonner à ce sujet.

Imaginez que vous teniez un morceau de papier au-dessus de votre bureau. Imaginez que chaque coin du papier est relié à un pointeur laser léger qui pointe vers le bureau. Le papier est l’object 3D, et les points du pointeur laser sur le bureau sont la projection 2D.

Maintenant, comment pouvez-vous dire à quel point le papier est haut sur le bureau en ne regardant que les points du pointeur laser?

Vous ne pouvez pas Déplacez le papier de haut en bas. Les pointeurs laser brillent toujours aux mêmes endroits sur le bureau, quelle que soit la hauteur du papier.

Trouver les coordonnées z dans la projection inversée, c’est comme essayer de trouver la hauteur du papier en fonction des points du pointeur laser sur le seul bureau.

Lorsque vous projetez de la 3D vers la 2D, vous perdez des informations.

Dans le cas simple d’un seul point, la projection inverse vous donnerait un rayon infini à travers l’espace 3d.

La reconstruction stéréoscopique commence généralement par deux images 2D et se projette sur la 3D. Recherchez ensuite une intersection des deux rayons 3D produits.

La projection peut prendre différentes formes. Orthogonal ou perspective. Je suppose que vous supposez une projection orthogonale?

Dans votre cas, en supposant que vous ayez la masortingce d’origine, vous auriez 4 rayons dans l’espace 3D. Vous pourrez alors limiter le problème en fonction des dimensions de votre rectangle 3D et tenter de le résoudre.

La solution ne sera pas unique car une rotation autour de l’un des axes parallèles au plan de projection 2D sera ambiguë. En d’autres termes, si l’image 2D est perpendiculaire à l’axe z, la rotation du rectangle 3D dans le sens des aiguilles d’une montre ou dans le sens inverse autour de l’axe x produirait la même image. De même pour l’axe des y.

Dans le cas où le plan rectangle est parallèle à l’axe z, vous avez encore plus de solutions.

Comme vous n’avez pas la masortingce de projection d’origine, une ambiguïté supplémentaire est introduite par un facteur d’échelle arbitraire qui existe dans toute projection. Vous ne pouvez pas distinguer une mise à l’échelle dans la projection et une translation en 3D dans la direction de l’axe z. Cela ne pose pas de problème si vous ne vous intéressez qu’aux positions relatives des 4 points dans un espace 3d lorsqu’ils sont liés les uns aux autres et non au plan de la projection 2D.

Dans une projection en perspective, les choses deviennent plus difficiles …

Si vous savez que la forme est un rectangle dans un plan, vous pouvez considérablement limiter le problème. Vous ne pouvez certainement pas déterminer “quel” plan, vous pouvez donc choisir qu’il soit situé sur le plan où z = 0 et l’un des coins est à x = y = 0, et les bords sont parallèles à l’axe x / y.

Les points en 3d sont donc {0,0,0}, {w, 0,0}, {w, h, 0} et {0, h, 0}. Je suis quasiment certain que la taille absolue ne sera pas trouvée, donc seul le rapport w / h est relatif, donc c’est un inconnu.

Relativement à ce plan, la caméra doit être à un certain point cx, cy, cz dans l’espace, doit pointer dans une direction nx, ny, nz (un vecteur de longueur un, l’un d’eux est redondant) et avoir foc_length / image_width facteur de w. Ces nombres se transforment en une masortingce de projection 3×3.

Cela donne un total de 7 inconnues: w / h, cx, cy, cz, nx, ny et w.

Vous avez un total de 8 connus: les 4 paires x + y.

Donc, cela peut être résolu.

La prochaine étape consiste à utiliser Matlab ou Mathmatica.