# MatchPoint

## Introduzione

MatchPoint è un individuatore di punti di controllo di nuova generazione: è il risultato del GSoC2007. Attualmente permette l'individuazione dei soli punti chiave ma non della corrispondenza (questa faceva parte del progetto GSoC 07 ma non è stata sviluppata) e può essere utilizzato solamente come sostituto per le chiavi generate da autopano-sift o autopano-sift-C.

La versione corrente di Matchpoint può essere reperita attraverso il progetto hugin.

Lo scopo di MatchPoint è quello di creare una serie completa di applicativi per i punti di controllo che verrà poi utilizzata da hugin come sostituto (o almeno come alternativa) dell'applicativo utilizzato attualmente e cioè autopano.

Se si desidera utilizzare fin d'ora MatchPoint nel processo di creazione delle immagini panoramiche (anche se tutte le funzioni non sono ancora state implementate) sarà necessario utilizzare anche autopano-sift.

Utilizzo:
// estrarre gli elementi dalla prima immagine e salvarli nel file image1.key:
MatchPoint imamagine1.jpg immagine1.key

// per la seconda immagine:
MatchPoint immagine2.jpg immagine2.key

// fare ricercare da autopano le corrispondenze tra i due file appena generati:
autopano project.pto immagine1.key immagine2.key

// aprire poi il file di progetto in hugin:
hugin project.pto

## Utilizzo da linea di comando

Utilizzo:

MatchPoint [opzioni] immagine1.jpg output.key

Parametri:

-v
  output prolisso
-t
  genera i file dei punti chiave (keypoint) per la suite di test di matlab (il nome del file è generato in questo modo: immagine1.jpg.key)

Argomenti:

immagine1.jpg
  percorso dell'immagine da analizzare.
output.key
  file dei punti chiave di output.

## Descrizione dell'algoritmo

### Integrali delle immagini

Prima del processo di identificazione delle corrispondenze, le immagini vengono integrate. Ogni elemento pixel (x,y) dell'immagine integrata, rappresenta la somma dei pixel da (0,0) a (x,y) dell'immagine di partenza. Questo processo rende più veloce il calcolo della somma di una regione. Inoltre, la convoluzione a qualsiasi scala ha la stessa complessità temporale. Questa parte è necessaria solamente quando si utilizzano dei riquadri come filtri per l'individuazione delle corrispondenze.

### Individuazione degli elementi

I punti vengono identificati avvalendosi dell'Hessian Detector e utilizzando dei filtri a riquadro. Di seguito è riportata una descrizione cronologica del processo di individuazione delle corrispondenze. Probabilmente non è completamente identica al processo effettuato dal codice di calcolo dato che alcune parti avvengono simultaneamente (per esempio i primi due passi).

Convoluzione dei pixel
La convoluzione di un pixel a una certa scala è effettuata tramite l'approssimazione della funzione Gaussiana bidimensionale; questo processo prende il nome di individuazione con filtro a riquadro (box filter detection). Ogni nucleo ha 4 filtri di convoluzione (3 di essi sono unici - i filtri xy e yx sono gli stessi). Il valore risultante è poi determinante per la matrice Hessiana in cui gli elementi rappresentano i valori dei 4 filtri.

Le dimensioni del nucleo per la convoluzione sono:
9,15,21,27, (1^ ottava)
15,27,39,51, (2^ ottava)
21,45,69,93 (3^ ottava)

MatchPoint è in grado di effettuare la convoluzione in due modi:

- box filter: più veloce ed è il metodo preferibile
- sliding window (implementata perché conveniente ma necessita di prove): più lenta, più accurata ma più sensibile al rumore

Ricerca del massimo
Per ottenere l'invarianza di scala, l'individuazione deve trovare il massimo del determinante dell' Hessiana tra le varie scale. Per farlo, sono state introdotte le ottave. Le ottave sono interpolazioni di determinanti a varie scale (generalmente due). MatchPoint offre l'individuazione con un massimo di 3 ottave (impostando un parametro). Per esempio, la prima ottava può essere individuata alla scala 1,6 (=((9+15/2)*1,2)/9 dove 1,2 è la scala iniziale e 9 è la dimensione iniziale del nucleo) o 3,2 (=((21+27/2)*1,2)/9. La scala principale dei punti chiave è poi selezionata in accordo al valore maggiore del determinante dell'Hessiana.

Selezione dei punti

Il passo successivo consiste nel selezionare i punti con elevati valori del determinante (senza tener conto della scala con cui i punti sono stati individuati) che rappresentano i punti chiave invarianti e che saranno utilizzati per le successive elaborazioni. Questo si ottiene utilizzando una soglia fissa che dovrebbe essere impostata bassa (diversamente potrebbe capitare che non venga individuato alcun punto).

Poi viene applicata la soppressione dei non massimi (sono selezionati solo i punti con un massimo locale dei determinanti).

A questo punto si è ottenuta una lista di punti di lunghezza variabile, dato che la soglia del passo precedente è fissata nel codice. In questo modo si possono avere anche più di 200.000 punti, per le immagini più grandi, che sono chiaramente troppi (indipendentemente dalla dimensione dell'immagine, è necessario lo stesso numero di punti di controllo per tutte le immagini; almeno 3 punti di controllo per ogni sovrapposizione), quindi la lista deve essere ridotta al di sotto di 10.000 punti (questo numero è scelto intuitivamente ed è basato sul tempo impiegato). (Nota: si tratta ancora di un progetto in lavorazione).

### Descrizione dell'elemento

Assegnazione dell'orientamento
L'invarianza di scala è ottenuta assegnando assegnando l'orientamento principale del punto di interesse utilizzando un algoritmo speciale proposto da Herbert Bay. L'efficienza di questo algoritmo non è ancora stata testata, quindi l'eseguibile di MatchPoint non utilizza alcuna assegnazione dell'orientamento.

Shape Context descriptors
Un descrittore a 36 elementi è assegnato a ogni punto di interesse. Gli elementi di questi descrittori sono organizzati in accordo al "Shape Context descriptor" proposto da S. Belongie, J. Malik and J. Puzicha e adattato da K. Mikolajczyk allo scopo dell'individuazione dei punti di controllo.

Passi nella creazione dei descrittori:

1. individuazione degli spigoli nell'intorno del punto di interesse (la dimensione della regione dipende dalla scala a cui il punto è stato individuato). MatchPoint utilizza le API di vigra (individuazione degli spigoli Canny) per questo scopo;
2. sulla base delle posizioni relative degli elementi di spigolo viene creato un istogramma con 36 valori. Usare i valori log-polar. Il contributo del punto di spigolo all'istogramma è basato sulla sua magnitudine e orientamento.

Consultare gli articoli di riferimento per maggiori dettagli.

## Riferimenti

- Speeded Up Robust Features - SURF
- Matlab suite per le prove, articoli per l'individuazione, descrizione e valutazione di K. Mikolajczyk
- Shape Context descriptors

Tratto e tradotto da "http://wiki.panotools.org/MatchPoint"