Comment dessiner une perspective correcte Grille en 2D
https://stackoverflow.com/questions/530396
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une application qui définit un vrai rectangle mondial sur le dessus d'une image / photo, bien sûr en 2D, il ne peut pas être un rectangle parce que vous le regardez d'un angle.
Le problème est, disons que le rectangle a besoin d'avoir des lignes de grille dessinée sur elle, par exemple si elle est 3x5 si je besoin de tirer 2 lignes de côté une à l'autre 3, et 4 lignes de côté 2 à côté 4.
En ce moment je suis la rupture de chaque ligne en parties à égale distance, pour obtenir le point de départ et à la fin de toutes les lignes de la grille. Cependant plus d'un angle du rectangle est, plus ces lignes « incorrectes » deviennent, sous forme de lignes horizontales plus loin, vous devriez être plus ensemble.
Quelqu'un sait-il le nom de l'algorithme que je être à la recherche?
Oui, je sais que vous pouvez le faire en 3D, mais je suis limité à 2D pour cette application particulière.
La solution
Voilà la solution.
L'idée de base est que vous pouvez trouver la bonne perspective « centre » de votre rectangle en reliant les coins en diagonale. L'intersection des deux lignes résultantes est votre point de vue centre correct. De là, vous subdivisez votre rectangle en quatre rectangles plus petits, et vous répétez le processus. Le nombre de fois dépend de la façon dont vous voulez précis, il. Vous pouvez diviser juste en dessous de la taille d'un pixel pour perspective efficacement parfaite.
Ensuite, dans votre sous-rectangles vous suffit d'appliquer vos standards triangles « texture non corrigées », ou rectangles ou autre.
Vous pouvez effectuer cet algorithme sans se donner la peine complexe de la construction d'un « vrai » monde 3D. il est également bon pour si vous faire un monde réel 3D modélisé, mais vos textriangles ne sont pas perspective corrigées dans le matériel, ou vous avez besoin d'une manière performante pour obtenir la perspective des plans corrects sans par pixel rendu supercherie.
Autres conseils
Image: Exemple de bilinéaire et Perspective Transform (Note: La hauteur du dessus et les lignes horizontales de la grille du bas est en fait la moitié des lignes de repos hauteur, sur les dessins)
========================================
Je sais que c'est une vieille question, mais j'ai une solution générique alors j'ai décidé de le publier hopping il sera utile aux futurs lecteurs. Le soufflet de code peut dessiner une grille en perspective arbitraire sans nécessiter de calculs répétitifs.
Je commence en fait avec un problème similaire: pour dessiner une grille en perspective 2D et transformer l'image soulignement pour restaurer la perspective
.J'ai commencé à lire ici: http://www.imagemagick.org/Usage/distorts/#bilinear_forward
puis ici (la Bibliothèque Leptonica): http://www.leptonica.com/affine.html
étaient je trouve ceci:
Quand vous regardez un objet dans un plan de quelque direction arbitraire à une distance finie, vous obtenez une distorsion « clef de voûte » supplémentaire dans la image. Ceci est une transformation projective, qui maintient les lignes droites ne conserve pas droit, mais les angles entre les lignes. ce gauchissement ne peut pas être décrite par une transformation affine linéaire, et en fait diffère en termes x et y-dépendantes dans le dénominateur.
La transformation n'est pas linéaire, comme beaucoup de gens déjà fait remarquer dans ce fil. Il implique la résolution d'un système linéaire de 8 équations (une fois) pour calculer les 8 coefficients nécessaires et vous pouvez les utiliser pour transformer autant de points que vous voulez.
Pour éviter d'inclure toute bibliothèque Leptonica dans mon projet, je pris quelques morceaux de code de celui-ci, je l'ai enlevé toutes Leptonica spéciales données-types et macros, je fixe des fuites de mémoire et je me suis converti à une classe C ++ (la plupart du temps pour l'encapsulation raisons) qui ne fait qu'une chose: Il associe un (Qt) float QPointF (x, y) coordonner la perspective coordonnée correspondante.
Si vous voulez adapter le code à une autre bibliothèque C ++, la seule chose à redéfinir / remplacer est la QPointF de coordonnées classe.
J'espère que certains futurs lecteurs trouveront utile. Le soufflet de code est divisé en 3 parties:
A. Un exemple sur la manière d'utiliser la genImageProjective classe C ++ pour dessiner une perspective 2D Grille
B. fichier genImageProjective.h
C. fichier genImageProjective.cpp
//============================================================
// C++ Code Example on how to use the
// genImageProjective class to draw a perspective 2D Grid
//============================================================
#include "genImageProjective.h"
// Input: 4 Perspective-Tranformed points:
// perspPoints[0] = top-left
// perspPoints[1] = top-right
// perspPoints[2] = bottom-right
// perspPoints[3] = bottom-left
void drawGrid(QPointF *perspPoints)
{
(...)
// Setup a non-transformed area rectangle
// I use a simple square rectangle here because in this case we are not interested in the source-rectangle,
// (we want to just draw a grid on the perspPoints[] area)
// but you can use any arbitrary rectangle to perform a real mapping to the perspPoints[] area
QPointF topLeft = QPointF(0,0);
QPointF topRight = QPointF(1000,0);
QPointF bottomRight = QPointF(1000,1000);
QPointF bottomLeft = QPointF(0,1000);
float width = topRight.x() - topLeft.x();
float height = bottomLeft.y() - topLeft.y();
// Setup Projective trasform object
genImageProjective imageProjective;
imageProjective.sourceArea[0] = topLeft;
imageProjective.sourceArea[1] = topRight;
imageProjective.sourceArea[2] = bottomRight;
imageProjective.sourceArea[3] = bottomLeft;
imageProjective.destArea[0] = perspPoints[0];
imageProjective.destArea[1] = perspPoints[1];
imageProjective.destArea[2] = perspPoints[2];
imageProjective.destArea[3] = perspPoints[3];
// Compute projective transform coefficients
if (imageProjective.computeCoeefficients() != 0)
return; // This can actually fail if any 3 points of Source or Dest are colinear
// Initialize Grid parameters (without transform)
float gridFirstLine = 0.1f; // The normalized position of first Grid Line (0.0 to 1.0)
float gridStep = 0.1f; // The normalized Grd size (=distance between grid lines: 0.0 to 1.0)
// Draw Horizonal Grid lines
QPointF lineStart, lineEnd, tempPnt;
for (float pos = gridFirstLine; pos <= 1.0f; pos += gridStep)
{
// Compute Grid Line Start
tempPnt = QPointF(topLeft.x(), topLeft.y() + pos*width);
imageProjective.mapSourceToDestPoint(tempPnt, lineStart);
// Compute Grid Line End
tempPnt = QPointF(topRight.x(), topLeft.y() + pos*width);
imageProjective.mapSourceToDestPoint(tempPnt, lineEnd);
// Draw Horizontal Line (use your prefered method to draw the line)
(...)
}
// Draw Vertical Grid lines
for (float pos = gridFirstLine; pos <= 1.0f; pos += gridStep)
{
// Compute Grid Line Start
tempPnt = QPointF(topLeft.x() + pos*height, topLeft.y());
imageProjective.mapSourceToDestPoint(tempPnt, lineStart);
// Compute Grid Line End
tempPnt = QPointF(topLeft.x() + pos*height, bottomLeft.y());
imageProjective.mapSourceToDestPoint(tempPnt, lineEnd);
// Draw Vertical Line (use your prefered method to draw the line)
(...)
}
(...)
}
==========================================
//========================================
//C++ Header File: genImageProjective.h
//========================================
#ifndef GENIMAGE_H
#define GENIMAGE_H
#include <QPointF>
// Class to transform an Image Point using Perspective transformation
class genImageProjective
{
public:
genImageProjective();
int computeCoeefficients(void);
int mapSourceToDestPoint(QPointF& sourcePoint, QPointF& destPoint);
public:
QPointF sourceArea[4]; // Source Image area limits (Rectangular)
QPointF destArea[4]; // Destination Image area limits (Perspectivelly Transformed)
private:
static int gaussjordan(float **a, float *b, int n);
bool coefficientsComputed;
float vc[8]; // Vector of Transform Coefficients
};
#endif // GENIMAGE_H
//========================================
//========================================
//C++ CPP File: genImageProjective.cpp
//========================================
#include <math.h>
#include "genImageProjective.h"
// ----------------------------------------------------
// class genImageProjective
// ----------------------------------------------------
genImageProjective::genImageProjective()
{
sourceArea[0] = sourceArea[1] = sourceArea[2] = sourceArea[3] = QPointF(0,0);
destArea[0] = destArea[1] = destArea[2] = destArea[3] = QPointF(0,0);
coefficientsComputed = false;
}
// --------------------------------------------------------------
// Compute projective transform coeeeficients
// RetValue: 0: Success, !=0: Error
/*-------------------------------------------------------------*
* Projective coordinate transformation *
*-------------------------------------------------------------*/
/*!
* computeCoeefficients()
*
* Input: this->sourceArea[4]: (source 4 points; unprimed)
* this->destArea[4]: (transformed 4 points; primed)
* this->vc (computed vector of transform coefficients)
* Return: 0 if OK; <0 on error
*
* We have a set of 8 equations, describing the projective
* transformation that takes 4 points (sourceArea) into 4 other
* points (destArea). These equations are:
*
* x1' = (c[0]*x1 + c[1]*y1 + c[2]) / (c[6]*x1 + c[7]*y1 + 1)
* y1' = (c[3]*x1 + c[4]*y1 + c[5]) / (c[6]*x1 + c[7]*y1 + 1)
* x2' = (c[0]*x2 + c[1]*y2 + c[2]) / (c[6]*x2 + c[7]*y2 + 1)
* y2' = (c[3]*x2 + c[4]*y2 + c[5]) / (c[6]*x2 + c[7]*y2 + 1)
* x3' = (c[0]*x3 + c[1]*y3 + c[2]) / (c[6]*x3 + c[7]*y3 + 1)
* y3' = (c[3]*x3 + c[4]*y3 + c[5]) / (c[6]*x3 + c[7]*y3 + 1)
* x4' = (c[0]*x4 + c[1]*y4 + c[2]) / (c[6]*x4 + c[7]*y4 + 1)
* y4' = (c[3]*x4 + c[4]*y4 + c[5]) / (c[6]*x4 + c[7]*y4 + 1)
*
* Multiplying both sides of each eqn by the denominator, we get
*
* AC = B
*
* where B and C are column vectors
*
* B = [ x1' y1' x2' y2' x3' y3' x4' y4' ]
* C = [ c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] ]
*
* and A is the 8x8 matrix
*
* x1 y1 1 0 0 0 -x1*x1' -y1*x1'
* 0 0 0 x1 y1 1 -x1*y1' -y1*y1'
* x2 y2 1 0 0 0 -x2*x2' -y2*x2'
* 0 0 0 x2 y2 1 -x2*y2' -y2*y2'
* x3 y3 1 0 0 0 -x3*x3' -y3*x3'
* 0 0 0 x3 y3 1 -x3*y3' -y3*y3'
* x4 y4 1 0 0 0 -x4*x4' -y4*x4'
* 0 0 0 x4 y4 1 -x4*y4' -y4*y4'
*
* These eight equations are solved here for the coefficients C.
*
* These eight coefficients can then be used to find the mapping
* (x,y) --> (x',y'):
*
* x' = (c[0]x + c[1]y + c[2]) / (c[6]x + c[7]y + 1)
* y' = (c[3]x + c[4]y + c[5]) / (c[6]x + c[7]y + 1)
*
*/
int genImageProjective::computeCoeefficients(void)
{
int retValue = 0;
int i;
float *a[8]; /* 8x8 matrix A */
float *b = this->vc; /* rhs vector of primed coords X'; coeffs returned in vc[] */
b[0] = destArea[0].x();
b[1] = destArea[0].y();
b[2] = destArea[1].x();
b[3] = destArea[1].y();
b[4] = destArea[2].x();
b[5] = destArea[2].y();
b[6] = destArea[3].x();
b[7] = destArea[3].y();
for (i = 0; i < 8; i++)
a[i] = NULL;
for (i = 0; i < 8; i++)
{
if ((a[i] = (float *)calloc(8, sizeof(float))) == NULL)
{
retValue = -100; // ERROR_INT("a[i] not made", procName, 1);
goto Terminate;
}
}
a[0][0] = sourceArea[0].x();
a[0][1] = sourceArea[0].y();
a[0][2] = 1.;
a[0][6] = -sourceArea[0].x() * b[0];
a[0][7] = -sourceArea[0].y() * b[0];
a[1][3] = sourceArea[0].x();
a[1][4] = sourceArea[0].y();
a[1][5] = 1;
a[1][6] = -sourceArea[0].x() * b[1];
a[1][7] = -sourceArea[0].y() * b[1];
a[2][0] = sourceArea[1].x();
a[2][1] = sourceArea[1].y();
a[2][2] = 1.;
a[2][6] = -sourceArea[1].x() * b[2];
a[2][7] = -sourceArea[1].y() * b[2];
a[3][3] = sourceArea[1].x();
a[3][4] = sourceArea[1].y();
a[3][5] = 1;
a[3][6] = -sourceArea[1].x() * b[3];
a[3][7] = -sourceArea[1].y() * b[3];
a[4][0] = sourceArea[2].x();
a[4][1] = sourceArea[2].y();
a[4][2] = 1.;
a[4][6] = -sourceArea[2].x() * b[4];
a[4][7] = -sourceArea[2].y() * b[4];
a[5][3] = sourceArea[2].x();
a[5][4] = sourceArea[2].y();
a[5][5] = 1;
a[5][6] = -sourceArea[2].x() * b[5];
a[5][7] = -sourceArea[2].y() * b[5];
a[6][0] = sourceArea[3].x();
a[6][1] = sourceArea[3].y();
a[6][2] = 1.;
a[6][6] = -sourceArea[3].x() * b[6];
a[6][7] = -sourceArea[3].y() * b[6];
a[7][3] = sourceArea[3].x();
a[7][4] = sourceArea[3].y();
a[7][5] = 1;
a[7][6] = -sourceArea[3].x() * b[7];
a[7][7] = -sourceArea[3].y() * b[7];
retValue = gaussjordan(a, b, 8);
Terminate:
// Clean up
for (i = 0; i < 8; i++)
{
if (a[i])
free(a[i]);
}
this->coefficientsComputed = (retValue == 0);
return retValue;
}
/*-------------------------------------------------------------*
* Gauss-jordan linear equation solver *
*-------------------------------------------------------------*/
/*
* gaussjordan()
*
* Input: a (n x n matrix)
* b (rhs column vector)
* n (dimension)
* Return: 0 if ok, 1 on error
*
* Note side effects:
* (1) the matrix a is transformed to its inverse
* (2) the vector b is transformed to the solution X to the
* linear equation AX = B
*
* Adapted from "Numerical Recipes in C, Second Edition", 1992
* pp. 36-41 (gauss-jordan elimination)
*/
#define SWAP(a,b) {temp = (a); (a) = (b); (b) = temp;}
int genImageProjective::gaussjordan(float **a, float *b, int n)
{
int retValue = 0;
int i, icol=0, irow=0, j, k, l, ll;
int *indexc = NULL, *indexr = NULL, *ipiv = NULL;
float big, dum, pivinv, temp;
if (!a)
{
retValue = -1; // ERROR_INT("a not defined", procName, 1);
goto Terminate;
}
if (!b)
{
retValue = -2; // ERROR_INT("b not defined", procName, 1);
goto Terminate;
}
if ((indexc = (int *)calloc(n, sizeof(int))) == NULL)
{
retValue = -3; // ERROR_INT("indexc not made", procName, 1);
goto Terminate;
}
if ((indexr = (int *)calloc(n, sizeof(int))) == NULL)
{
retValue = -4; // ERROR_INT("indexr not made", procName, 1);
goto Terminate;
}
if ((ipiv = (int *)calloc(n, sizeof(int))) == NULL)
{
retValue = -5; // ERROR_INT("ipiv not made", procName, 1);
goto Terminate;
}
for (i = 0; i < n; i++)
{
big = 0.0;
for (j = 0; j < n; j++)
{
if (ipiv[j] != 1)
{
for (k = 0; k < n; k++)
{
if (ipiv[k] == 0)
{
if (fabs(a[j][k]) >= big)
{
big = fabs(a[j][k]);
irow = j;
icol = k;
}
}
else if (ipiv[k] > 1)
{
retValue = -6; // ERROR_INT("singular matrix", procName, 1);
goto Terminate;
}
}
}
}
++(ipiv[icol]);
if (irow != icol)
{
for (l = 0; l < n; l++)
SWAP(a[irow][l], a[icol][l]);
SWAP(b[irow], b[icol]);
}
indexr[i] = irow;
indexc[i] = icol;
if (a[icol][icol] == 0.0)
{
retValue = -7; // ERROR_INT("singular matrix", procName, 1);
goto Terminate;
}
pivinv = 1.0 / a[icol][icol];
a[icol][icol] = 1.0;
for (l = 0; l < n; l++)
a[icol][l] *= pivinv;
b[icol] *= pivinv;
for (ll = 0; ll < n; ll++)
{
if (ll != icol)
{
dum = a[ll][icol];
a[ll][icol] = 0.0;
for (l = 0; l < n; l++)
a[ll][l] -= a[icol][l] * dum;
b[ll] -= b[icol] * dum;
}
}
}
for (l = n - 1; l >= 0; l--)
{
if (indexr[l] != indexc[l])
{
for (k = 0; k < n; k++)
SWAP(a[k][indexr[l]], a[k][indexc[l]]);
}
}
Terminate:
if (indexr)
free(indexr);
if (indexc)
free(indexc);
if (ipiv)
free(ipiv);
return retValue;
}
// --------------------------------------------------------------
// Map a source point to destination using projective transform
// --------------------------------------------------------------
// Params:
// sourcePoint: initial point
// destPoint: transformed point
// RetValue: 0: Success, !=0: Error
// --------------------------------------------------------------
// Notes:
// 1. You must call once computeCoeefficients() to compute
// the this->vc[] vector of 8 coefficients, before you call
// mapSourceToDestPoint().
// 2. If there was an error or the 8 coefficients were not computed,
// a -1 is returned and destPoint is just set to sourcePoint value.
// --------------------------------------------------------------
int genImageProjective::mapSourceToDestPoint(QPointF& sourcePoint, QPointF& destPoint)
{
if (coefficientsComputed)
{
float factor = 1.0f / (vc[6] * sourcePoint.x() + vc[7] * sourcePoint.y() + 1.);
destPoint.setX( factor * (vc[0] * sourcePoint.x() + vc[1] * sourcePoint.y() + vc[2]) );
destPoint.setY( factor * (vc[3] * sourcePoint.x() + vc[4] * sourcePoint.y() + vc[5]) );
return 0;
}
else // There was an error while computing coefficients
{
destPoint = sourcePoint; // just copy the source to destination...
return -1; // ...and return an error
}
}
//========================================
Alors que mon google-fu n'a pas réussi à produire une solution mathématique solide de roche, peut-être ce dessin que j'ai trouvé pourrait aider un peu.
http://studiochalkboard.evansville.edu/lp-diminish.html
Je pense qu'il pourrait effectivement être assez difficile de trouver le calcul correct sur votre propre, il est probablement une sorte d'expression logarithmique ou sommation. Si tout va bien le dessin et les conditions à ce lien pourrait fournir quelque chose d'un peu plus des recherches pour vous.
En utilisant la méthode de subdivision de Breton (qui est liée à la méthode d'extension de Mongo), vous obtiendrez arbitraires précises puissance de-deux divisions. Pour diviser en non-puissance de-deux divisions en utilisant ces méthodes, vous devrez diviser l'espacement sous-pixel, ce qui peut être informatiquement cher.
Cependant, je crois que vous pourriez être en mesure d'appliquer une variation de
La plus élégante et la plus rapide solution serait de trouver la matrice homographie, qui mappe rectangle vers les coordonnées photo. Avec une bibliothèque de matrice décent, il ne devrait pas être une tâche difficile, aussi longtemps que vous savez que votre mathématiques. Mots-clés: collinéation, homographie, transformation linéaire directe Cependant, l'algorithme récursif devrait fonctionner au-dessus, mais probablement si vos ressources sont limitées, la géométrie projective est la seule façon d'aller.
Dans le cas particulier quand on regarde perpendiculairement à côtés 1 et 3, vous pouvez diviser les côtés en parties égales. Ensuite, tracer une diagonale, et tracer des parallèles à côté de 1 à chaque intersection de la diagonale et les lignes de séparation établis précédemment.
Cette solution géométrique je pensé. Je ne sais pas si le « algorithme » a un nom.
Dites que vous voulez commencer en divisant le « rectangle » en morceaux n avec des lignes verticales premières.
Le but est de placer des points P1..Pn-1 sur la première ligne que nous pouvons utiliser pour tracer des lignes à travers eux aux points où la gauche et la ligne droite se rencontrent ou parallèlement à eux quand tel point n'existe pas.
Si la ligne supérieure et inférieure sont parallèles les uns aux autres il suffit de placer thoose points de division de la ligne supérieure entre les coins équidistante.
Place Else n points de Q1..Qn sur la ligne gauche de sorte que theese et le coin supérieur gauche sont à égale distance et i
Pour ce faire, analogique pour les lignes horizontales.
Etant donné une rotation autour de l'axe y, en particulier si les surfaces de rotation sont planes, la perspective est générée par des gradients verticaux. Ceux-ci deviennent progressivement plus en perspective. Au lieu d'utiliser pour définir quatre diagonales rectangles, qui peut travailler de deux pouvoirs conférés ... définir deux rectangles, à gauche et à droite. Ils seront plus hauts que larges, éventuellement, si l'on continue de diviser la surface en segments verticaux plus étroits. Cela peut accueillir des surfaces qui ne sont pas carrés. Si une rotation est autour de l'axe x, puis gradients horizontaux sont nécessaires.
Je pense que la réponse choisie est pas la meilleure solution disponible. Une meilleure solution consiste à appliquer une perspective (projective) la transformation d'un rectangle à grille simple script suivant Matlab et show image. Vous pouvez implémenter cet algorithme avec C ++ et OpenCV ainsi.
function drawpersgrid
sz = [ 24, 16 ]; % [x y]
srcpt = [ 0 0; sz(1) 0; 0 sz(2); sz(1) sz(2)];
destpt = [ 20 50; 100 60; 0 150; 200 200;];
% make rectangular grid
[X,Y] = meshgrid(0:sz(1),0:sz(2));
% find projective transform matching corner points
tform = maketform('projective',srcpt,destpt);
% apply the projective transform to the grid
[X1,Y1] = tformfwd(tform,X,Y);
hold on;
%% find grid
for i=1:sz(2)
for j=1:sz(1)
x = [ X1(i,j);X1(i,j+1);X1(i+1,j+1);X1(i+1,j);X1(i,j)];
y = [ Y1(i,j);Y1(i,j+1);Y1(i+1,j+1);Y1(i+1,j);Y1(i,j)];
plot(x,y,'b');
end
end
hold off;
Ce que vous devez faire est de le représenter en 3D (monde) et projeter ensuite vers 2D (écran).
Cela vous obligera à utiliser une matrice de transformation 4D qui fait la projection sur un 4D homogène jusqu'à un vecteur homogène 3D, que vous pouvez ensuite convertir vers le bas à un vecteur d'espace d'écran 2D.
Je ne pouvais pas le trouver dans Google non plus, mais un bon livres graphiques ordinateur ont les détails.
Les mots clés sont matrice de projection, la transformation de projection, transformation affine, vecteur homogène, l'espace du monde, l'espace d'écran, la transformation en perspective, la transformation 3D
Et par ailleurs, cela prend généralement quelques conférences pour expliquer tout cela. Alors bonne chance.
