Come disegnare una griglia con correzione prospettica in 2D
https://stackoverflow.com/questions/530396
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho un'applicazione che definisce un rettangolo del mondo reale sopra un'immagine/fotografia, ovviamente in 2D potrebbe non essere un rettangolo perché lo guardi da un angolo.
Il problema è, diciamo che sul rettangolo devono essere disegnate delle linee della griglia, ad esempio se è 3x5 quindi devo disegnare 2 linee dal lato 1 al lato 3 e 4 linee dal lato 2 al lato 4.
A partire da ora sto suddividendo ogni linea in parti equidistanti, per ottenere il punto iniziale e finale di tutte le linee della griglia.Tuttavia, maggiore è l'angolo del rettangolo, più "errate" diventano queste linee, poiché le linee orizzontali più lontane da te dovrebbero essere più vicine tra loro.
Qualcuno conosce il nome dell'algoritmo che dovrei cercare?
Sì, lo so, puoi farlo in 3D, tuttavia sono limitato al 2D per questa particolare applicazione.
Soluzione
Ecco la soluzione.
L'idea di base è che si può trovare la giusta prospettiva "centro" del rettangolo collegando gli angoli diagonalmente. L'intersezione delle due linee risultanti è la prospettiva centrale corretta. Da lì si suddividere il vostro rettangolo in quattro rettangoli più piccoli, e si ripete il processo. Il numero di volte dipende da come precisa lo vuoi. È possibile suddividere appena al di sotto della dimensione di un pixel per prospettiva efficace perfetto.
Poi, nel tuo sottorettangoli basta applicare le normali triangoli non corretti "strutturato", o rettangoli o qualsiasi altra cosa.
È possibile eseguire questa procedura senza andare al complesso problema della costruzione di una 'vera' del mondo 3d. E 'anche un bene per se fa avere un vero e proprio mondo 3D modellato, ma i tuoi textriangles non vengono prospettiva corretta in hardware, o avete bisogno di un modo performante per ottenere prospettiva aerei corrette, senza per il rendering pixel inganno.
Altri suggerimenti
Immagine:Esempio di trasformazione bilineare e prospettica (Nota:L'altezza delle linee orizzontali della griglia superiore e inferiore è in realtà la metà dell'altezza delle linee rimanenti, su entrambi i disegni)
========================================
So che è una vecchia domanda, ma ho una soluzione generica quindi ho deciso di pubblicarla sperando che possa essere utile ai futuri lettori.Il codice seguente può disegnare una griglia prospettica arbitraria senza la necessità di calcoli ripetitivi.
In realtà inizio con un problema simile:per disegnare una Griglia prospettica 2D e quindi trasformare l'immagine sottolineata per ripristinare la prospettiva.
Ho iniziato a leggere qui:http://www.imagemagick.org/Usage/distorts/#bilinear_forward
e poi qui (Biblioteca Leptonica):http://www.leptonica.com/affine.html
dove ho trovato questo:
Quando guardi un oggetto su un piano da una direzione arbitraria a una distanza finita, si ottiene un'ulteriore distorsione "chiave di volta" nell'immagine.Questa è una trasformazione proiettiva, che mantiene le linee rette dritte ma non conserva gli angoli tra le linee.Questo deformazione non può essere descritto da una trasformazione affine lineare e in effetti differisce per termini dipendenti da X e Y nel denominatore.
La trasformazione non è lineare, come molte persone hanno già sottolineato in questo thread.Implica la risoluzione di un sistema lineare di 8 equazioni (una volta) per calcolare gli 8 coefficienti richiesti e quindi puoi usarli per trasformare tutti i punti che desideri.
Per evitare di includere tutta la libreria Leptonica nel mio progetto, ne ho preso alcuni pezzi di codice, ho rimosso tutti i tipi di dati e le macro speciali di Leptonica, ho corretto alcune perdite di memoria e l'ho convertito in una classe C++ (principalmente per ragioni di incapsulamento) che fa solo una cosa:Mappa una coordinata (Qt) QPointF float (x,y) alla corrispondente coordinata prospettica.
Se vuoi adattare il codice ad un'altra libreria C++, l'unica cosa da ridefinire/sostituire è la classe di coordinate QPointF.
Spero che qualche futuro lettore lo trovi utile.Il codice seguente è diviso in 3 parti:
UN.Un esempio su come utilizzare la classe C++ genImageProjective per disegnare una griglia prospettica 2D
B.file genImageProjective.h
C.file 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
}
}
//========================================
Mentre il mio google-fu non è riuscita a produrre alcuna solida roccia soluzione matematica, forse questo disegno che ho trovato potrebbe aiutare un po '.
http://studiochalkboard.evansville.edu/lp-diminish.html
Penso che potrebbe in realtà essere piuttosto difficile da trovare con la matematica corretta da soli, è probabilmente una sorta di espressione logaritmica o di sommatoria. Speriamo che il disegno e le condizioni in quel link potrebbe fornire qualcosa di un po 'più ricercabile per voi.
Usando il metodo di suddivisione di Breton (che è legato al metodo di estensione di Mongo), si arriva precise divisioni arbitrarie potenze di due. Per dividere in divisioni non-potere-su-due utilizzando questi metodi si dovrà suddividere a distanza sub-pixel, che può essere computazionalmente costoso.
Tuttavia, credo che si può essere in grado di applicare una variazione di Teorema di Haga (che viene utilizzato in origami per dividere un lato in Nths dato un lato diviso in (N-1) tHS) alle suddivisioni prospettiche quadrati per produrre divisioni arbitrarie dalla potenza più vicina 2 senza dover per continuare a suddivisione.
La soluzione più elegante e più veloce sarebbe quella di trovare la matrice omografia, che mappa rettangolo di coordinate coordinate foto.
Con una libreria di matrice decente non dovrebbe essere un compito difficile, a patto che si conosce la matematica.
Parole chiave: collineation, omografia, trasformazione diretta lineare
Tuttavia, l'algoritmo ricorsivo sopra dovrebbe funzionare, ma probabilmente se le risorse sono limitate, la geometria proiettiva è l'unico modo per andare.
Nel caso particolare quando si guarda perpendicolarmente ai lati 1 e 3, si può dividere quei lati in parti uguali. Quindi disegnare una diagonale, e disegnare paralleli lato 1 attraverso ciascuna intersezione della diagonale e le linee di divisione disegnate in precedenza.
Questa soluzione geometrica ho pensato fuori. Non so se il 'algoritmo' ha un nome.
Dire che si desidera avviare dividendo il 'rettangolo' in n pezzi con linee verticali primi.
L'obiettivo è quello di posizionare i punti P1..Pn-1 sulla riga superiore, che possiamo usare per disegnare linee attraverso di loro per i punti in cui la sinistra e la linea a destra si incontrano o in parallelo ad essi quando tale punto non esiste.
Se la linea superiore e inferiore sono paralleli l'uno all'altro solo inserire thoose punti per dividere la linea superiore tra gli angoli equidistanti.
altro posto n punti Q1..Qn sulla linea di sinistra in modo che theese e l'angolo in alto a sinistra sono equidistanti e i
Fare questo analogico per le linee orizzontali.
Dato una rotazione intorno all'asse y, soprattutto se le superfici di rotazione sono piane, la prospettiva è generato dai gradienti verticali. Questi diventano progressivamente più vicino in prospettiva. Invece di usare diagonali per definire quattro rettangoli, che può funzionare dato poteri di due ... definire due rettangoli, a destra ea sinistra. Saranno superiore ampia, eventualmente, se si continua a dividere la superficie in segmenti verticali strette. Ciò può ospitare superfici che non sono quadrati. Se una rotazione è intorno all'asse x, sono necessari gradienti quindi orizzontali.
Credo che la risposta selezionata non è la migliore soluzione disponibile. Una soluzione migliore è quella di applicare la prospettiva (proiettiva) trasformazione di un rettangolo di semplice griglia come seguente script Matlab e mostra immagine. È possibile implementare questo algoritmo con C ++ e OpenCV pure.
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;
Il problema è che è la trasformazione da 3D a 2D che si sta facendo.
Qui 'un tutorial su come è fatto.
Quello che dovete fare è rappresentare in 3D (mondo) e poi proiettare verso il basso per 2D (schermo).
Questo richiede di utilizzare una matrice di trasformazione 4D che fa la proiezione su un 4D omogenea fino a un vettore omogeneo 3D, che è quindi possibile convertire fino a un 2D spazio screen vettoriale.
non ho potuto trovare in Google sia, ma un buon libro di computer grafica avrò i dettagli.
chiave sono matrice di proiezione, trasformazione proiezione, affine trasformazione, vettore omogeneo, mondo spazio, lo spazio dello schermo, trasformazione prospettica, trasformazione 3D
E, a proposito, questo richiede di solito un paio di lezioni per spiegare tutto questo. Quindi buona fortuna.
