Trasformazioni 2D e image stitching

1. Coordinate omogenee: un punto è un raggio

Le trasformazioni 2D si scrivono in modo compatto usando le coordinate omogenee, la cui intuizione geometrica è: un punto nell'immagine è un raggio nello spazio proiettivo. Un punto (x, y) sul piano z = 1 è rappresentato dal raggio (sx, sy, s): tutti i punti del raggio sono equivalenti, perché vengono proiettati nello stesso punto sul piano dell'immagine:

(x, y, 1) ≅ (sx, sy, s)

La conversione da coordinate omogenee a coordinate non omogenee è immediata: si divide per la coordinata w:

(x, y, w)  ⇒  (x/w, y/w)

Da qui una proprietà centrale: le coordinate omogenee sono invarianti per cambiamenti di scala — moltiplicare tutte le coordinate per una costante non cambia il punto rappresentato.

2. Image reprojection: allineare immagini come trasformazione 2D

L'image stitching (o costruzione di panorami) parte da una domanda: come mettere in relazione due immagini acquisite dalla stessa camera? Dato il punto di osservazione (la camera) e il punto proiettato nel piano P₁ è possibile identificare il raggio; per sapere dove quello stesso raggio viene proiettato nel piano P₂ non è necessario avere informazioni sulla posizione del raggio nel «mondo».

Il mapping tra le due immagini non richiede quindi informazioni 3D: può essere rappresentato semplicemente come trasformazione 2D (warping). L'idea è proiettare le immagini acquisite da diverse angolazioni su un unico piano: l'immagine panoramica.

I problemi da affrontare sono due: l'allineamento delle diverse immagini e il blending, con attenzione alle variazioni che possono interessare le immagini (per esempio la luce).

3. La gerarchia delle trasformazioni

Le possibili trasformazioni tra immagini formano una gerarchia: ogni livello è un caso particolare del successivo, e ogni livello preserva un sottoinsieme diverso di proprietà. Le cinque famiglie, in ordine di generalità crescente:

Leggere la tabella dal basso verso l'alto è il modo migliore per fissarla: la proiettiva preserva solo le linee; l'affine in più il parallelismo e i rapporti di area; l'euclidea le lunghezze e gli angoli; la traslazione perfino le orientazioni. La scala è un caso particolare di affine (matrice diagonale).

4. Traslazione e cambiamento di scala

Traslazione

La traslazione sposta il punto di t_x, t_y. Preserva lunghezze/aree, angoli, orientazioni e linee:

⎡x′⎤   ⎡1  0  t_x⎤ ⎡x⎤          x′ = x + t_x
⎢y′⎥ = ⎢0  1  t_y⎥ ⎢y⎥          y′ = y + t_y
⎣1 ⎦   ⎣0  0   1 ⎦ ⎣1⎦

Cambiamento di scala

La scala moltiplica le coordinate per s_x e s_y. Preserva il rapporto tra lunghezze/aree (non le lunghezze assolute), gli angoli, le orientazioni e le linee:

⎡x′⎤   ⎡s_x  0   0⎤ ⎡x⎤          x′ = s_x · x
⎢y′⎥ = ⎢0    s_y 0⎥ ⎢y⎥          y′ = s_y · y
⎣1 ⎦   ⎣0    0   1⎦ ⎣1⎦

5. Trasformazione euclidea e affine

Trasformazione euclidea (rigid body)

Combina rotazione (angolo θ) e traslazione. Preserva lunghezze/aree, angoli e linee; perde l'invarianza delle orientazioni (l'oggetto ruota con la scena):

⎡x′⎤   ⎡ cosθ  −sinθ  t_x⎤ ⎡x⎤     x′ = x·cosθ − y·sinθ + t_x
⎢y′⎥ = ⎢ sinθ   cosθ  t_y⎥ ⎢y⎥     y′ = x·sinθ + y·cosθ + t_y
⎣1 ⎦   ⎣  0      0     1 ⎦ ⎣1⎦

Trasformazione affine

Generalizza le precedenti con sei parametri a, b, c, d, e, f. Preserva il rapporto tra aree, le linee parallele e il rapporto tra linee — il parallelismo è la proprietà che la distingue dalla proiettiva:

⎡x′⎤   ⎡a  b  c⎤ ⎡x⎤          x′ = a·x + b·y + c
⎢y′⎥ = ⎢d  e  f⎥ ⎢y⎥          y′ = d·x + e·y + f
⎣1 ⎦   ⎣0  0  1⎦ ⎣1⎦

Con la scomposizione a = s·cosθ, b = −s·sinθ, c = t_x, d = s·sinθ, e = s·cosθ, f = t_y si ottiene il caso particolare «scala uniforme + rotazione + traslazione».

6. La trasformazione proiettiva: l'omografia

La trasformazione proiettiva (o omografia) è la più generale tra quelle studiate e preserva soltanto le linee. Nella terza riga compaiono i parametri g e h, che introducono la prospettiva:

⎡x′⎤   ⎡a  b  c⎤ ⎡x⎤
⎢y′⎥ = ⎢d  e  f⎥ ⎢y⎥        p′ = H·p
⎣w′⎦   ⎣g  h  1⎦ ⎣1⎦

Notare la terza coordinata w′: per tornare alle coordinate dell'immagine si divide per w′, esattamente come nella sezione 1. È la divisione per w′ a rompere il parallelismo: due rette parallele possono convergere in un punto di fuga.

7. Stimare l'omografia e costruire il panorama

Per determinare l'omografia che rappresenta la trasformazione tra due immagini servono (almeno) 4 coppie di punti corrispondenti. Date le corrispondenze è possibile risalire alla matrice H attraverso SVD o il metodo dei minimi quadrati.

L'immagine panoramica si ottiene allineando progressivamente le immagini due a due: prima si stimano le omografie tra coppie consecutive, poi si applicano le trasformazioni e si fondono i risultati. Uno step finale di «normalizzazione» è spesso necessario per rendere invisibile la transizione tra immagini diverse (il blending della sezione 2).

Ma da dove arrivano le corrispondenze? Questo è il ponte verso il prossimo capitolo: i keypoint e i descrittori locali servono proprio a trovare in modo automatico i punti corrispondenti tra due immagini.

8. Image warping: mapping diretto e inverso

Sia f la funzione che rappresenta la trasformazione da applicare. Eseguendo la trasformazione a partire da una scansione dell'immagine di partenza (mapping diretto), si incontrano tre problemi:

• i valori dei nuovi pixel non sono necessariamente interi (serve un'approssimazione);
• alcuni pixel vengono mappati al di fuori della nuova immagine;
• alcuni pixel della nuova immagine non vengono colpiti: restano i cosiddetti buchi.

Un modo efficace di risolvere questi problemi è il mapping inverso: si scandisce la nuova immagine e, per ogni pixel [x_new, y_new], si determina il punto di riferimento [x_old, y_old] sulla vecchia immagine attraverso la funzione inversa f⁻¹. Per una trasformazione affine:

⎡x_old⎤   ⎡1/s  0   ⎤ ⎡ cos(−θ)  −sin(−θ) ⎤ ⎛ ⎡x_new⎤   ⎡t_x⎤ ⎞
⎢y_old⎥ = ⎢ 0   1/s  ⎥ ⎢ sin(−θ)   cos(−θ) ⎥ · ⎜ ⎢y_new⎥ − ⎢t_y⎥ ⎟
⎣ 1   ⎦   ⎣ 0    0   ⎦ ⎣   0         0     ⎦ ⎝ ⎣  1  ⎦   ⎣ 1 ⎦ ⎠

Il punto di riferimento [x_old, y_old], in coordinate continue (floating point), può cadere:

• fuori dalla vecchia immagine: si imposta un valore di base (es. nero);
• su un pixel della vecchia immagine: si copia l'intensità;
• a metà strada tra 4 pixel: si interpola (sezione successiva).

9. Interpolazione: quando il punto cade tra i pixel

Se [x_old, y_old] cade a metà strada tra quattro pixel A, B, C, D, il valore di intensità del nuovo pixel si calcola interpolando i valori di intensità dei 4 pixel circostanti. L'interpolazione di Lagrange cerca il piano che meglio approssima i 4 punti (ai minimi quadrati):

New I(x_new, y_new) = ( Old I(A)·w_A + Old I(B)·w_B + Old I(C)·w_C + Old I(D)·w_D ) / ( w_A + w_B + w_C + w_D )

con i pesi (indicando con x_old, y_old le coordinate frazionarie dentro la cella, e con x_i, y_j il vertice in basso a sinistra):

w_A = (x_i+1 − x_old)·(y_j+1 − y_old)        w_C = (x_old − x_i)·(y_old − y_j)
w_B = (x_old − x_i)·(y_j+1 − y_old)           w_D = (x_i+1 − x_old)·(y_old − y_j)

La lettura è semplice: ogni peso è il prodotto delle distanze dal vertice opposto — un vertice vicino al punto riceve un peso grande, uno lontano un peso piccolo.

Verifica le tue conoscenze