Analisi comparativa degli operatori di interesse

Pur senza la completezza e il grado di approfondimento presente in [Schmid 2000b] e in [Mikolajczyk 2003] si è voluto analizzare le effettive prestazioni degli algoritmi implementati in relazione ad una serie di casi differenti e la corretta implementazione.

Sono state considerate 5 diverse immagini (reali o realizzate artificialmente con un software di model-lazione) che possano fornire un quadro di situazioni sufficientemente ampio. Per ciascuna di tali immagini si è testato ciascun algoritmo andando a imporre trasformazioni note (rotazione, variazione di scala, tra-sformazione affine, variazioni di luminosità e contrasto) e nel caso delle immagini sintetiche si è anche

a.

d.

b.

e.

c.

Figura 1.3: Immagini utilizzate per i test comparativi degli operatori di interesse implementati. Ognuna vie-ne utilizzata per mostrare una delle trasformazioni applicate vie-nella prova: a. trasformaziovie-ne di rotaziovie-ne; b.

trasformazione di scala; c. trasformazione affine; d. cambiamento del punto di vista (omografia) utilizzata solo per i due casi generati artificialmente (a. e d.); e. trasformazione complessa di luminosità, contrasto e correzione gamma.

CAPITOLO 1. Structure and Motion 21

provveduto a considerare cambiamenti nel punto di vista. Si sono così ottenuti 22 differenti test in cui si sono analizzate le prestazioni di ciascuno dei 3 operatori al momento implementati, variando i parametri di trasformazione.

Di seguito vengono presentati i grafici riepilogativi dei risultati emersi: si è ritenuto corretto conside-rare come parametro più significativo per valutare l’efficienza degli operatori il grado di ripetibilità che, lo ricordiamo, è definito come la percentuale di features corrispondenti estratte dall’operatore su entrambi i fotogrammi. Tale valore dipende strettamente dall’errore di localizzazione, definito come la distanza di accettazione massima a cui devono trovarsi le features dalla loro posizione corretta valutata a partire dalle posizioni sul fotogramma di riferimento e dai parametri della trasformazione imposta: l’errore di localizza-zione, in tutte le prove, è stato posto a 1.5 pixel. E’ importante osservare a questo riguardo che in molti casi pratici non è richiesta in operazioni di feature matching una precisione troppo elevata, in quanto, una volta identificati i punti corrispondenti, per mezzo di algoritmi di matching Area Based è possibile migliorare il posizionamento.

Si cominci con l’analizzare il test relativo alla trasformazione di rotazione: come possibile vedere in figura 1.3.a, in cui sono mostrate alcune delle immagini trasformate utilizzate relative ad una delle imma-gini utilizzate per la prova, si è realizzata una cornice monocromatica attorno al fotogramma originale in modo da garantire che l’area analizzata dall’operatore fosse sempre uguale per tutte le rotazioni imposte. I risultati sono presentati nel grafico di figura 1.4, in cui, come in tutti gli altri casi presi in considerazione, vengono visualizzati solamente i valori medi di ripetibilità ottenuti su tutte le immagini: è possibile notare che tutti gli operatori, visti i criteri sui quali sono basati, si comportano abbastanza bene di fronte a questo tipo di trasformazione; fa in parte eccezione l’operatore di Foerstner che presenta valori di ripetibilità più bassi del 10% ÷ 15% rispetto agli altri; tale comportamento è però identico in tutte le altre prove e non sembra quindi essere relativo solamente al caso

della rotazione. E’ poi possibile osservare che l’andamento della curva tende a decrescere per i primi 45° per poi aumentare fino a 90°, dimi-nuire nuovamente fino a 135° e infine aumen-tare di nuovo fino a 180°; tale comportamento può essere dovuto principalmente al fatto che nel caso delle rotazioni per 90° e 180° il ricam-pionamento dell’immagine è esatto, mentre per tutte le altre l’interpolazione (bilineare) utiliz-zata per calcolare la trasformazione dei toni di grigio può indurre cambiamenti in termini di contrasto in una certa percentuale di punti estratti con l’operatore.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 15 30 45 60 75 90 105 120 135 150 165 180 Harris Föerstner Lowe

Figura 1.4: Grado di ripetibilità medio per le 5 immagini relativamente alla rotazione del piano immagine.

Nel caso delle variazioni di scala (figura 1.3.b) è immediato verificare, osservando i ri-sultati del grafico di figura 1.5, che solo l’ope-ratore di Lowe permette di ottenere gradi di ripetibilità elevati quando la variazione di scala supera il 25%: con solo il 50% di variazione l’operatore di Harris presenta coefficienti infe-riori a 0.5, attestandosi rapidamente, per fatto-ri più alti, su valofatto-ri prossimi a 0.2; viceversa l’operatore di Lowe per riduzioni fino ad un ter-zo della dimensione originale presenta valori di ripetibilità approssimativamente pari a 0.÷0.6, valori solitamente accettabili per le procedure di feature matching di cui si parlerà nel prossi-mo paragrafo.

Per la trasformazione affine (figura 1.3.c) valgono sostanzialmente le stesse considerazioni per l’opera-tore di Lowe; al contrario gli altri operatori, si veda figura 1.6, presentano valori di ripetibilità lievemente superiori al caso precedente: la nostra interpretazione del fenomeno è che il tipo di trasformazione tenda ad sfavorire il riconoscimento di alcuni punti che presentano gradienti principali in direzione della variazione di scala, mentre influenza in grado minore quelli ortogonali.

Per considerare la variazione del punto di vista si è proceduto come segue: per mezzo di un programma di modellazione si sono generati due differenti immagini sintetiche (rappresen-tate in figura 1.3.c e 1.3.d); tali immagini sono state applicate ad una superficie piana alla qua-le sono stati solidarizzati sei target circolari: la scelta di considerare un oggetto piano deriva dalla necessità di poter stimare facilmente una trasformazione fra i punti dei vari fotogrammi per riportarli in un sistema di riferimento comu-ne; al tempo stesso con tale geometria non si ha il problema di poter riscontrare occlusioni che possono drasticamente ridurre il grado di

ripeti-Figura 1.6: Grado di ripetibilità medio per le 5 immagi-ni relativamente ad una trasformazione affine del piano immagine.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0.75 1 1.25 1.5 1.75 2 2.25 2.5

Harris Föerstner Lowe

Figura 1.5: Grado di ripetibilità medio per le 5 immagini relativamente alla variazione di scala del piano immagi-ne.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0.5 1 1.5 2 2.5 3 3.5 4

Harris Föerstner Lowe

CAPITOLO 1. Structure and Motion 23 bilità, in quanto l’operatore va ad estrarre punti

in zone differenti dell’oggetto. Si è poi provve-duto a variare il punto di vista muovendo una camera virtuale su una circonferenza, variando l’angolo d’incidenza dell’asse principale con la normale al piano da 0° a 0° con passi costanti di 5°; una volta estratti i punti con i vari opera-tori si sono determinate con LSM le posizioni dei centri dei vari target e si è stimata la trasfor-mazione omografica con il piano immagine ini-ziale (cioè quello corrispondente a 0°); infine si sono trasformati, grazie all’omografia stimata, le posizioni corrispondenti di tutti i punti estrat-ti. Per tenere in conto i possibili errori di centra-mento dei target e della conseguente stima della

trasformazione si è stimato mediamente di dover incrementare di 0.2 pixel la soglia di accettazione per il calcolo del grado di ripetibilità.

Come è possibile vedere in figura 1.7, e come del resto era prevedibile, tutti gli operatori non fornisco-no prestazioni accettabili superati i 35°÷45°; sia l’operatore di Harris che quello di Foerstner consento di ottenere una buona ripetibilità fino a 15°÷20°, mentre quello di Lowe, che come di consueto si dimostra più robusto quando intervengono variazioni di scala, si può pensare di ottenere risultati accettabili fino a 45°. Ciononostante, per quanto osservato precedentemente sulle occlusioni e sulle altre possibili cause di disturbo bisogna considerare che, in casi reali

non ottimali, il grado di ripetibilità può essere nettamente inferiore.

Infine si è considerato il caso di variazioni complesse delle caratteristiche illuminometri-che del fotogramma: sono state considerate 15 repliche dei fotogrammi originali, per ognuna delle quali è stata applicata una trasformazione casuale di luminosità e contrasto oltre ad una correzione gamma (vd. § 2.4.2) sempre casua-le; come si vede in figura 1.3.e tali variazioni sono comunque contenute in modo da non ave-re effetti di clipping dei toni di grigio. Il grafico

Figura 1.8: Grado di ripetibilità medio per le 5 immagini relativamente ad una variazione complessa delle caratte-ristiche di luminosità dell’immagine.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Harris Föerstner Lowe

Figura 1.7: Grado di ripetibilità medio per le 2 immagini sintetiche relativamente alla variazione del punto di vista da cui è generata l’immagine.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 Harris Föerstner Lowe

di figura 1.8 riporta i risultati di ripetibilità ottenuti nei vari casi: si può osservare come il comportamento dei vari operatori sia approssimativamente costante, ad eccezione dell’operatore di Foerstner che presenta oscillazioni un po’ più pronunciate. Il grado di ripetibilità medio complessivo per l’operatore di Harris è stato dell’84. %, per Foerstner del 64.5 % e del 9.2 % per l’operatore di Lowe.

Cercando di riassumere i risultati emersi, possiamo dire che solitamente, quando intervengono varia-zioni fra le immagini limitate, è preferibile utilizzare l’operatore di Harris, in quanto è quello che fornisce (seppur lievemente) i risultati migliori e garantisce soprattutto uno sforzo computazionale minore; in parte esso, come del resto l’operatore di Foerstner è in grado di fornire risultati accettabili, se non ottimali, anche per variazioni del punto di vista, purché relativamente contenute (15°÷20°); ciononostante in tali frangenti è sempre preferibile utilizzare l’operatore di Lowe, o comunque altri approcci invarianti rispetto alle tra-sformazioni di scala, in quanto forniscono prestazioni decisamente maggiori.