03 Roto-translation

Prima di proseguire con la ricerca dei numeri nelle caselle dello schema sudoku direi che è naturale far sì che il centro dello schema sia il centro dell'immagine e dare una raddrizzata alla griglia. Riferendosi all'ultima immagine del paragrafo precedente, vogliamo far sì che la croce tratteggiata verde si sovrapponga a quella tratteggiata blu.

Dobbiamo dunque roto-traslare i punti dell'immagine nonchè le rette che abbiamo ricavato. Le linee che formano la griglia sono rappresentate in forma esplicita in funzione delle ascisse (x) per le orizzontali ed in funzione delle ordinate (y) per le verticali; questo per essere certi di non ricadere nelle singolarità di queste rappresentazioni (ovvero, rispettivamente, le rette verticali ed orizzontali).

Le formule di rototraslazione per un punto e per le rette, nelle due rappresentazioni esplicite, sono facili da ricavare e sono date dalle seguenti equazioni.

Applicando le equazioni ai punti dell'immagine binaria e alle equazioni delle rette si ricava quanto visualizzato nella figura seguente.

A questo punto torna utile rototraslare la figura scansionata. La cosa sembra semplice visto quanto fatto in pochissimo tempo per l'immagine binaria, invece la rototraslazione di immagini non è banale in quanto ci sono una serie di effetti indesiderati dovuti al fatto che muoviamo un punto da una posizione che ha coordinate intere in una posizione di coordinate che, con probabilità elevatissima, non saranno intere. Ci sono due fastidiosissimi effetti indesiderati:

1. punti neri (buchi) all'interno dell'immagine;

2. linee seghettate (aliasing).

Un esempio di questi artefatti nelle immagini "fotografiche" ruotate è per l'appunto il nostro schema sudoku ruotato.

Per evitare di avere buchi all'interno dell'immagine ruotata si cambia semplicemente il punto di vista. Si scandiranno tutti i punti dell'immagine destinazione (che noi scegliamo avere stessa dimensione di quella di partenza, eventuali punti che sborderanno verranno eliminati) e mediante la funzione inversa andremo a prenderci il valore da associarvi nell'immagine sorgente (inverse mapping); da notare che per eseguire la funzione inversa basta prima traslare e poi ruotare i punti dell'immagine destinazione di quantità opposte rispetto ai valori di roto-traslazione della funzione diretta. Questo procedimento elimina i buchi ma non risolve il problema della discretizzazione delle coordinate, andremo a puntare quasi sicuramente ad un punto di coordinate non intere che nell'immagine sorgente non esiste.

Per ovviare a questo inconveniente, nonchè risolvere il punto 2 procediamo ad applicare per ogni punto l'interpolazione bilineare. Vi sono altri tipi di interpolazione più complessi, che danno risultati migliori a scapito però di semplicità e tempi/risorse di elaborazione. Per i nostri scopi questo tipo di interpolazione è più che buono.

Come spesso accade per questi algoritmi l'idea è semplice, quasi naturale e vincente, si osservi la figura che segue che è una sorta di ingrandimento della figura precedente nell'intorno del punto dell'immagine origine roto-traslato, con coordinate reali, ricavato mediante inverse mapping.

Il valore del punto incognito sarà calcolato semplicemente interpolando i valori dei punti che lo attorniano, si faranno prima due interpolazioni lungo le ascisse e poi una lungo le ordinate; l'interpolazione non è nient'altro che una media pesata basata sulla distanze:

NOTA: I pedici delle equazioni di cui sopra "u","d","l","r", "int" stanno rispettivamente per up,down,left e right ed interpolated mentre la notazione "c" indica il valore di colore del pixel. Le distanze h e v sono riportate nella figura sopra.

Il risultato finale della rotazione con interpolazione bilineare è nella figura sotto, decisamente meglio di prima.