Algoritmo Distorsione Quadrilatero

In questo articolo illustro, dal punto di vista geometrico, l'algoritmo utilizzato nella risoluzione del problema della distorsione di un'immagine dati i 4 vertici di destinazione.


quadrilatero originale (rettangolo per comodità)	quadrilatero distorto

Per individuare la posizione iniziale di un punto appartenente ad un quadrilatero - successivamente ad una distorsione apportata al quadrilatero stesso - i passaggi sono i seguenti:

individuare i punti (propri o impropri) O e N visibili in figura 1.
Tali punti si trovano rispettivamente:

O » sull'intersezione delle direttrici dei lati A'B' e D'C';
N » sull'intersezione delle direttrici dei lati A'D' e B'C'.

figura 1

individuare i punti L(P), M(P), J(P) e K(P) visibili in figura 2.
Tali punti si trovano rispettivamente:

L » sull'intersezione tra la congiungente i punti O e P e la retta per A' e D';
M » sull'intersezione tra la congiungente i punti O e P e la retta per B' e C';
J » sull'intersezione tra la congiungente i punti N e P e la retta per A' e B';
K » sull'intersezione tra la congiungente i punti N e P e la retta per C' e D';

figura 2

Ora per recuperare le coordinate del punto iniziale P₀ = (x₀, y₀) è necessario applicare la seguente proporzione.

nota bene: supponiamo che il rettangolo di partenza circoscriva esattamente il quadrilatero distorto
(i passaggi necessari per riportare le coordinate del punto P₀ alla situazione "effettivamente" iniziale sono banali).

Nel sistema di riferimento cartesiano ortogonale monometrico Axy (vedi figura 3), si ha che:

yP₀ = yD * dJP / (dJP + dKP)
xP₀ = xB * dLP / (dLP + dMP)

dove,

dJP » distanza tra J e P
dKP » distanza tra K e P
dLP » distanza tra L e P
dMP » distanza tra M e P

figura 3

Take care. Bye.

Feedbacks

Re: Quadrilateral Distortion Algorithm

Gilberto Carcano (lunedì 22 ottobre 2007 3.11)

“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 (lunedì 22 ottobre 2007 18.31)

“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 (martedì 23 ottobre 2007 3.30)

“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 (omologia) 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 articolo).”
Re: Quadrilateral Distortion Algorithm

Gilberto Carcano (martedì 23 ottobre 2007 16.38)

“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 questo documento 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 (mercoledì 24 ottobre 2007 2.13)

“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!...”