Implementazione di tecniche di calibrazione basate sugli algoritmi genetic

Anche per l‟implementazione di tecniche di calibrazione basate su algoritmi genetici è stato deciso di utilizzare MatLab, date la sua potenza di calcolo, il linguaggio di programmazione ad alto livello non complesso e le capacità grafiche semplici e potenti. Grazie a queste caratteristiche MatLab risulta essere un comodo strumento per la ricerca scientifica e un potente metodo di prototipazione. Come descritto nel capitolo 2.2.4, anche l‟algoritmo di Zhang e quello di Levenberg-Marquardt sono stati implementati in MatLab, e l‟utilizzo dello stesso software sicuramente semplifica le procedure di scrittura dell‟algoritmo e rende immediato il confronto tra le due tecniche. Inoltre MatLab contiene un‟ottima libreria dedicata agli algoritmi genetici, oltre che un tool dedicato all‟ottimizzazione (“MatLab Optimization Tool”) in cui è possibile risolvere problemi di minimizzazione anche usando i GA. Il software di calibrazione descritto nel capitolo 2.2.4 è stato quindi ampliato. Oltre all‟algoritmo di Zhang- LM, viene risolto il problema di calibrazione con l‟utilizzo di diverse tecniche, descritte in seguito, basate sugli algoritmi genetici. Il software permette anche di confrontare i risultati tra i vari metodi. Anche in questo caso viene data la possibilità all‟utente di scegliere quale modello di telecamera utilizzare e i dati sono creati ancora una volta grazie al programma “FeatureLinker” del VBLab.

L‟algoritmo genetico implementato prende in ingresso una serie di parametri di configurazione. Prima di tutto bisogna stabilire la dimensione della popolazione, ovvero quanti individui sono contenuti in ogni generazione. Più è ampia la popolazione e minore sarà la possibilità di convergere in un minimo locale, in quanto il GA andrà a esplorare tutto lo spazio delle variabili. Ciò però ridurrà considerevolmente la velocità di esecuzione. È necessario poi passare in ingresso all‟algoritmo un individuo iniziale, che verrà utilizzato per la creazione della prima generazione. L‟individuo iniziale può essere costituito da una stima delle variabili di minimizzazione, oppure creato in maniera del tutto casuale. Chiaramente un set di variabili iniziali sensato può diminuire considerevolmente la velocità con la quale l‟algoritmo converge al minimo globale. Per ogni cromosoma che compone l‟individuo, quindi per ogni variabile, si può configurare un range in cui vengono scelti i valori di quel dato cromosoma per la creazione della popolazione iniziale. Non è necessario che tale range contenga la soluzione ottima del problema, poiché l‟algoritmo genetico evolve esplorando soluzioni all‟infuori di esso. Chiaramente, se la soluzione è compresa in esso, più il limite superiore e inferiore si avvicinano ad essa e più l‟algoritmo ha possibilità di convergere in fretta alla soluzione ottima. Bisogna inoltre definire i criteri d‟arresto dell‟algoritmo; in particolare è stato deciso di terminare l‟esecuzione del GA quando viene raggiunto un certo numero di generazioni massimo, che assume valori differenti a seconda delle tecniche utilizzate. Altro parametro è il crossover

fraction, definito nel capitolo 2.3.2, che in tutte le simulazioni è stato posto a 0.8.

Questo valore, come spesso accade nella scelta dei parametri degli algoritmi genetici, è frutto di sperimentazioni e tentativi. Essendo i GA algoritmi che progrediscono in maniera casuale, non è sempre facile capire quale sia la configurazione dei parametri migliore per far sì che converga più velocemente possibile alla soluzione ottima. Spesso l‟unico metodo valido per capire quale sia

parametri fissi e variando solamente il crossover fraction tra esse. I GA evolvono in maniera casuale e spesso non si ottengono gli stessi valori lanciando due volte lo stesso GA. Per questo sono state fatte più prove di questo tipo, anche con differenti sottoinsiemi di immagini, e i risultati sono stati mediati per ogni valore di crossover fraction. Ad esempio in figura 2.15 sono stati rappresentati i risultati trovati durante una di queste analisi. Dal grafico si nota che un valore pari a 0.8 del parametro crossover fraction porta a risultati migliori in termini di errore di retroproiezione finale. Questo valore è stato verificato essere il migliore per tutti i metodi implementati.

Figura 2.15: Risultati degli esperimenti per l’individuazione del miglior valore da assegnare al

parametro crossover fraction.

Lo stesso tipo di esperimento è stato svolto per verificare quale tipo di crossover fosse il migliore. Non è stata però trovata alcuna differenza tra i risultati ricavati utilizzando un crossover a single-point e a two-point (tabella 2.1). Si è dunque deciso di utilizzare il primo.

CROSSOVER TYPE Reprojection Error Mean

Single-point 0.117947538

Two-point 0.118354563

Il parametro elite count, ovvero il numero degli individui che vengono duplicati nella generazione seguente senza essere modificati, è stato impostato a 2 in tutte le simulazioni, poiché analisi simili a quelle effettuate per trovare il miglior valore di

crossover fraction hanno mostrato che valori tra 2 e 8 portano nella maggior parte

dei casi a risultati migliori (figura 2.16).

Figura 2.16: Risultati degli esperimenti per l’individuazione del miglior valore di elite count.

Infine le mutazioni sono state eseguite selezionando in modo casuale un valore per ogni cromosoma, scelto in una distribuzione gaussiana che ha come valore medio il valore della variabile nella generazione precedente e deviazione standard definita da un parametro chiamato Scale. Inoltre l‟ampiezza delle mutazioni in ogni generazione è definito dal parametro Shrink. Infatti la deviazione standard della distribuzione gaussiana diminuisce linearmente in ogni generazione in modo tale da avere alla fine della simulazione un valore pari a 1-Shrink. Quindi, se per esempio il valore di Shrink è settato pari a 1, l‟ammontare delle mutazioni

quindi inutile compiere mutazioni eccessive che creerebbero individui con fitness più alto. Al contrario se non si eseguissero mutazioni l‟algoritmo non esplorerebbe tutto lo spazio dei parametri e quindi rischierebbe di convergere in un minimo locale. Anche in questo caso per ogni tecnica implementata sono stati eseguiti numerosi esperimenti e tentativi per stabilire quale fosse il miglior valore da assegnare ai parametri scale e shrink. In tutte queste prove si è evidenziato che mutazioni con una distribuzione gaussiana di deviazione standard 0.005 (scale) e

shrink 1 portano ai risultati migliori. A testimonianza di ciò si riportano nella

figura 2.17 alcuni dei risultati trovati dagli esperimenti per trovare il miglior valore di deviazione standard, con il parametro di shrink fisso a 1. Con errore di retroproiezione medio si intende il valore medio risultante da differenti prove con diversi set di immagini. Si nota che si hanno valori più bassi di errore di retroproiezione medio con scale intorno a 0.05.

Figura 2.17: Risultati degli esperimenti per l’individuazione del miglior valore di scale, con