Resumé

Quadrilateral Distortion Algorithm

Cristian Merighi () 4.33

How to identify the starting coordinates of a point belonging to a quadrilateral, after a distortion process? Here's an answer.
This article is obsolete. Some functionalities might not work anymore. Comments are disabled.

In this article I describe, from a geometrical perspective, the algorithm I used to solve the problem of distorting an image by setting the 4 destination vertices.

distortion
original quadrilateral (rectangle) distorted quadrilateral

To retrieve te initial position of a point beloging to the quad - after a free distortion - the tasks are the following:

  1. retrieve the points (whether proper or improper) O and N visible in figure 1.
    You can find 'em respectively:
    • O » intersecting the lines through A' and B' and through D' and C';
    • N » intersecting the lines through A' and D' and thorugh B' and C'.
    find N and O
    figure 1
  2. retrieve the points L(P), M(P), J(P) e K(P) visible in figure 2.
    You can find 'em respectively:
    • L » intersecting the line through O and P and the line through A' and D';
    • M » intersecting the line through O and P and the line through B' and C';
    • J » intersecting the line through N and P and the line through A' and B';
    • K » intersecting the line through N and P and the line through C' and D';
    find L, M, J and K
    figure 2
  3. Now, to get the coordinates of P0 = (x0, y0) is necessary to apply the following proportion:

    nota bene: let us suppose that the stating rectangle is the bounding quadrilateral of the distorted one
    (the passages to bring the point P0 to the "effectively" starting status are trivial).

    In the Cartesian orthogonal monometric coordinate system Axy (see figure 3), we have:
    yP0 = yD * dJP / (dJP + dKP)
    xP0 = xB * dLP / (dLP + dMP)
                    
    dove,
    • dJP » distance between J and P
    • dKP » distance between K and P
    • dLP » distance between L and P
    • dMP » distance between M and P
    proportion
    figure 3

Take care. Bye.

Feedbacks

  • Re: Quadrilateral Distortion Algorithm

    Gilberto Carcano Monday, October 22, 2007 5.00

    Eccellente articolo! Veramente molto utile... Tramite l'algoritmo proposto, dato piano distorto individuato dalle rette A'B' e A'D', è possibile passare da un punto P di tale piano ad un punto P0 del piano non distorto individuato dalle rette AB e AD. Come si potrebbe fare per il contrario, e cioè per passare dalle coordinate di P0 a quelle di P ? E' un pò che ci provo ma non ho ancora trovato la soluzione... Mi serebbe molto utile poterlo fare per un'applicazione che stò realizzando nella scuola ove lavoro...

  • Re: Quadrilateral Distortion Algorithm

    Gilberto Carcano Monday, October 22, 2007 3.00

    C'è però un problema: se il quadrilatero distorto venisse visto come una trasformazione prospettica del rettangolo non distorto avente come punti di fuga O ed N, allora ci si aspetterebbe che la trasformazione del centro del quadrilatero (ovvero del punto P intersezione delle diagonali A'C' B'D') venisse mappata sul punto P0 centro del rettangolo non distorto! Mi pare che ciò non accade utilizzando l'algoritmo proposto. Da cui deduco che tale algoritmo non è utilizzabile per il mapping prospettico. :-(

  • Re: Quadrilateral Distortion Algorithm

    CMerighi Tuesday, October 23, 2007 0.00

    Ciao Gilberto, questo algoritmo di distorsione non è pensato per ottenere la conformazione di un quadrilatero data una rotazione tridimensionale (angoli euleriani, quaternioni etc...), anche se, individuata la conformazione finale risultante da una tale rotazione (quindi individuate le coordinate dei vertici del quadrilatero "distorto"), la corrispondenza biunivoca (<a href="http://it.wikipedia.org/wiki/Omologia_%28geometria%29" target="_blank">omologia</a>) tra i punti apparteneti alle due figure (iniziale e distorta) è rispettata. (Nota bene: i punti P e P0 in figura non sono i punti d'incontro delle diagonali e le figure stesse non sono in scala, per testarne il funzionamento fai riferimento a questo <a href="http://www.pacem.it/CMerighi/Posts/20,it-IT/Distorcere_Immagini_con_GDI%2b_(soluzione).aspx">articolo</a>).

  • Re: Quadrilateral Distortion Algorithm

    Gilberto Carcano Tuesday, October 23, 2007 5.00

    Ciao Cristian, premetto che non sono un grande esperto di matematica (per me gli angoli euleriani sono quelli da cui Eulero tirava formidabili calci d'angolo, i quaternioni sono quei grandi quaderni tanto comodi per prendere appunti e le rotazioni tridimensionali hanno a che fare con il kamasutra :-). Per quello che vale, sono d'accordissimo con quanto hai affermato. Vorrei però precisare di non aver detto che i punti P0 e P indicati in figura sono i centri del rettangolo e del parallelogramma rispettivamente, ma che calcolando "a mano" i centri C0 e C l'algoritmo applicato su C non fornisce C0. Spero di essere stato chiaro. Colgo l'occasione per segnalare a te e ai tuoi lettori <A href="http://pages.cs.wisc.edu/~dyer/cs766/readings/heckbert-proj.pdf">questo documento</A> che ritengo veramente interessante. Prendendo spunto ho scritto una classe C# che effettua la trasformazione e l'antitrasformazione (projective mappings) e, se mi dici come fare, posso inviartela per renderla disponibile ai tuoi lettori.

  • Re: Quadrilateral Distortion Algorithm

    CMerighi Wednesday, October 24, 2007 0.00

    Ciao Gilberto, ho ricontrollato l'algoritmo ieri ed effettivamente non da' una distorsione prospettica del quadrilatero iniziale. Non che fosse il suo scopo: questa procedura nasce dalla necessità di ottenere una ri-mappatura di un'immagine (rettangolare) su di un qualsivoglia quadrilatero. Grazie quindi dell'interesse e dell'entusiasmo dimostrato (btw, il documento che hai linkato è davvero interessante) e mi interessa molto leggere il codice della tua classe. Inviamelo pure via e-mail, lo pubblicherò volentieri! Grazie ancora!...

feedback
 

Syndicate

Author

Cristian Merighi facebook twitter google+ youtube

Latest articles

Top rated

Archive

Where am I?

Author

Cristian Merighi facebook twitter google+ youtube

I'm now reading

Feeds