Algoritmi per la stima del rumore nella ricostruzione di immagini

In questa tesi viene analizzato un metodo di regolarizzazione nel quale il problema di regolarizzazione è formulato come un problema di ottimizzazione vincolata. In questa formulazione è fondamentale il termine noto del vincolo, parametro per il quale dipende la bontà della ricostruzione, che corrisponde ad una stima della norma del rumore sul dato. Il contributo della tesi è l'analisi di un algoritmo proposto per stimare il rumore in applicazioni di image deblurring utilizzando la decomposizione in valori singolari dell'operatore che descrive il blur. Sono stati fatti numerosi test per valutare sia i parametri dell'algoritmo di stima che l'efficacia della stima ottenuta quando è inserita nel termine noto del vincolo del problema di ottimizzazione per la ricostruzione dell'immagine.

Firma digitale e algoritmo DSA

La firma digitale è uno degli sviluppi più importanti della crittografia a chiave pubblica, che permette di implementarne le funzionalità di sicurezza. La crittografia a chiave pubblica, introdotta nel 1976 da Diffie ed Hellman, è stata l'unica grande rivoluzione nella storia della crittografia. Si distacca in modo radicale da ciò che l'ha preceduta, sia perché i suoi algoritmi si basano su funzioni matematiche e non su operazioni di sostituzione e permutazione, ma sopratutto perché è asimmetrica: prevede l'uso di due chiavi distinte (mentre nelle crittografia simmetrica si usa una sola chiave condivisa tra le parti). In particolare, le funzioni matematiche su cui si basa tale crittografia sono funzioni ben note nella Teoria dei Numeri: ad esempio fattorizzazione, calcolo del logaritmo discreto. La loro importanza deriva dal fatto che si ritiene che siano 'computazionalmente intrattabili' da calcolare. Dei vari schemi per la firma digitale basati sulla crittografia a chiave pubblica, si è scelto di studiare quello proposto dal NIST (National Institute of Standard and Technology): il Digital Signature Standard (DSS), spesso indicato come DSA (Digital Signature Algorithm) dal nome dell'algoritmo che utilizza. Il presente lavoro è strutturato in tre capitoli. Nel Capitolo 1 viene introdotto il concetto di logaritmo discreto (centrale nell'algoritmo DSA) e vengono mostrati alcuni algoritmi per calcolarlo. Nel Capitolo 2, dopo una panoramica sulla crittografia a chiave pubblica, si dà una definizione di firma digitale e delle sue caratteristiche. Chiude il capitolo una spiegazione di un importante strumento utilizzato negli algoritmi di firma digitale: le funzioni hash. Nel Capitolo 3, infine, si analizza nel dettaglio il DSA nelle tre fasi che lo costituiscono (inizializzazione, generazione, verifica), mostrando come il suo funzionamento e la sua sicurezza derivino dai concetti precedentemente illustrati.

Studio di un algoritmo per confrontare documenti xml

Tesi sullo studio di algoritmi per il confronto di documenti XML, panoramica sui vari algoritmi. Focalizzazione sull'algoritmo NDiff e in particolare sulla gestione degli attributi.

Implementazione dell'algoritmo filtered back-projection (FBP) per architetture low-power di tipo systems-on-chip

Il presente lavoro di tesi, svolto presso i laboratori dell'X-ray Imaging Group del Dipartimento di Fisica e Astronomia dell'Università di Bologna e all'interno del progetto della V Commissione Scientifica Nazionale dell'INFN, COSA (Computing on SoC Architectures), ha come obiettivo il porting e l’analisi di un codice di ricostruzione tomografica su architetture GPU installate su System-On-Chip low-power, al fine di sviluppare un metodo portatile, economico e relativamente veloce. Dall'analisi computazionale sono state sviluppate tre diverse versioni del porting in CUDA C: nella prima ci si è limitati a trasporre la parte più onerosa del calcolo sulla scheda grafica, nella seconda si sfrutta la velocità del calcolo matriciale propria del coprocessore (facendo coincidere ogni pixel con una singola unità di calcolo parallelo), mentre la terza è un miglioramento della precedente versione ottimizzata ulteriormente. La terza versione è quella definitiva scelta perché è la più performante sia dal punto di vista del tempo di ricostruzione della singola slice sia a livello di risparmio energetico. Il porting sviluppato è stato confrontato con altre due parallelizzazioni in OpenMP ed MPI. Si è studiato quindi, sia su cluster HPC, sia su cluster SoC low-power (utilizzando in particolare la scheda quad-core Tegra K1), l’efficienza di ogni paradigma in funzione della velocità di calcolo e dell’energia impiegata. La soluzione da noi proposta prevede la combinazione del porting in OpenMP e di quello in CUDA C. Tre core CPU vengono riservati per l'esecuzione del codice in OpenMP, il quarto per gestire la GPU usando il porting in CUDA C. Questa doppia parallelizzazione ha la massima efficienza in funzione della potenza e dell’energia, mentre il cluster HPC ha la massima efficienza in velocità di calcolo. Il metodo proposto quindi permetterebbe di sfruttare quasi completamente le potenzialità della CPU e GPU con un costo molto contenuto. Una possibile ottimizzazione futura potrebbe prevedere la ricostruzione di due slice contemporaneamente sulla GPU, raddoppiando circa la velocità totale e sfruttando al meglio l’hardware. Questo studio ha dato risultati molto soddisfacenti, infatti, è possibile con solo tre schede TK1 eguagliare e forse a superare, in seguito, la potenza di calcolo di un server tradizionale con il vantaggio aggiunto di avere un sistema portatile, a basso consumo e costo. Questa ricerca si va a porre nell’ambito del computing come uno tra i primi studi effettivi su architetture SoC low-power e sul loro impiego in ambito scientifico, con risultati molto promettenti.

Studio ed implementazione di un algoritmo per la gestione dell'handover in ambiente Android

In questo elaborato di tesi, viene progettata ed implementata una soluzione per gestire il processo di handover in ambiente Android. Tale proposta, è costituita da un algoritmo in grado di gestire automaticamente le interfacce di connessione dei dispostivi, in relazione alle preferenze e agli spostamenti effettuati dall'utente. Le prove sperimentali effettuate, confermano che tale proposta è una buona base per risolvere il problema dell'handover e si presta bene a cooperare con altri protocolli quali ABPS (Always Best Packet Switching). Inoltre l'applicazione si presta bene ad un semplice utilizzo e può essere impiegata anche come servizio eseguito in background, non richiedendo frequenti interazioni da parte dell'utente. Oltre all'algoritmo citato in precedenza, sono stati proposti altri dettagli implementativi, non presenti in letteratura. In particolare, vengono modificate alcune impostazioni di sistema, accedendo agli opportuni file, in modo tale che Android gestisca correttamente le scansioni delle interfacce e la loro attivazione/disattivazione.

Un approccio per la disambiguazione di autori di articoli scientifici: algoritmo e implementazione

Dalla necessità di risolvere il problema della disambiguazione di un insieme di autori messo a disposizione dall'Università di Bologna, il Semantic Lancet, è nata l'idea di progettare un algoritmo di disambiguazione in grado di adattarsi, in caso di bisogno, a qualsiasi tipo di lista di autori. Per la fase di testing dell'algoritmo è stato utilizzato un dataset generato (11724 autori di cui 1295 coppie da disambiguare) dalle informazioni disponibili dal "database systems and logic programming" (DBLP), in modo da essere il più etereogeneo possibile, cioè da contenere il maggior numero di casi di disambiguazione possibile. Per i primi test di sbarramento è stato definito un algoritmo alternativo discusso nella sezione 4.3 ottenendo una misura di esattezza dell'1% ed una di completezza dell'81%. L'algoritmo proposto impostato con il modello di configurazione ha ottenuto invece una misura di esattezza dell'81% ed una di completezza del 70%, test discusso nella sezione 4.4. Successivamente l'algoritmo è stato testato anche su un altro dataset: Semantic Lancet (919 autori di cui 34 coppie da disambiguare), ottenendo, grazie alle dovute variazioni del file di configurazione, una misura di esattezza del 84% e una di completezza del 79%, discusso nella sezione 4.5.

Implementazione di un algoritmo SDF per la determinazione dello spessore di componenti meccanici

Implementazione di un algoritmo sdf per la determinazione dello spessore di componenti meccanici

Progetto e implementazione di un algoritmo per la navigazione a piedi su un dispositivo Windows Mobile

Presentazione di un'applicazione per Windows Phone in grado di contare il numero dei passi effettuati e stimare la distanza percorsa. Tale stima viene effettuata sulla base della lunghezza del passo calcolata istante per istante tramite un algoritmo in base all'altezza di una persona e alla frequenza di passo.

L'informazione di fase per la segmentazione volumetrica di dati ecocardiografici

L’imaging ad ultrasuoni è una tecnica di indagine utilizzata comunemente per molte applicazioni diagnostiche e terapeutiche. La tecnica ha numerosi vantaggi: non è invasiva, fornisce immagini in tempo reale e l’equipaggiamento necessario è facilmente trasportabile. Le immagini ottenute con questa tecnica hanno tuttavia basso rapporto segnale rumore a causa del basso contrasto e del rumore caratteristico delle immagini ad ultrasuoni, detto speckle noise. Una corretta segmentazione delle strutture anatomiche nelle immagini ad ultrasuoni è di fondamentale importanza in molte applicazioni mediche . Nella pratica clinica l’identificazione delle strutture anatomiche è in molti casi ancora ottenuta tramite tracciamento manuale dei contorni. Questo processo richiede molto tempo e produce risultati scarsamente riproducibili e legati all’esperienza del clinico che effettua l’operazione. In ambito cardiaco l’indagine ecocardiografica è alla base dello studio della morfologia e della funzione del miocardio. I sistemi ecocardiografici in grado di acquisire in tempo reale un dato volumetrico, da pochi anni disponibili per le applicazioni cliniche, hanno dimostrato la loro superiorità rispetto all’ecocardiografia bidimensionale e vengono considerati dalla comunità medica e scientifica, la tecnica di acquisizione che nel futuro prossimo sostituirà la risonanza magnetica cardiaca. Al fine di sfruttare appieno l’informazione volumetrica contenuta in questi dati, negli ultimi anni sono stati sviluppati numerosi metodi di segmentazione automatici o semiautomatici tesi alla valutazione della volumetria del ventricolo sinistro. La presente tesi descrive il progetto, lo sviluppo e la validazione di un metodo di segmentazione ventricolare quasi automatico 3D, ottenuto integrando la teoria dei modelli level-set e la teoria del segnale monogenico. Questo approccio permette di superare i limiti dovuti alla scarsa qualità delle immagini grazie alla sostituzione dell’informazione di intensità con l’informazione di fase, che contiene tutta l’informazione strutturale del segnale.

Analisi e processi di immagini astronomiche

Questa tesi riguarda l'analisi di immagini astronomiche. In particolare esamineremo tecniche che permettono l'elaborazione di immagini. Si parlerà di operazioni di base che comprendono le usuali operazioni matematiche e le trasformazioni geometriche fornendo alcuni esempi di applicazioni. Parleremo inoltre approfonditamente dell'operazione di convoluzione tra immagini e delle sue proprietà. Successivamente tratteremo in modo approfondito la teoria di Fourier, a partire dai suoi lavori sulle serie omonime fino allo sviluppo dell'algoritmo FFT. Vedremo inoltre svariate applicazioni della trasformata di Fourier all'analisi di immagini. Per concludere parleremo di deconvoluzione, analizzando in particolare due algoritmi deconvolutivi, l'algoritmo di Van Cittert e l'algoritmo di Richardson-Lucy.

The effect of diffusion gradient direction number on tractography of corticospinal tract in human brain: an along-tract analysis

Nel presente lavoro di tesi ho sviluppato un metodo di analisi di dati di DW-MRI (Diffusion-Weighted Magnetic Resonance Imaging)cerebrale, tramite un algoritmo di trattografia, per la ricostruzione del tratto corticospinale, in un campione di 25 volontari sani. Il diffusion tensor imaging (DTI) sfrutta la capacità del tensore di diffusione D di misurare il processo di diffusione dell’acqua, per stimare quantitativamente l’anisotropia dei tessuti. In particolare, nella sostanza bianca cerebrale la diffusione delle molecole di acqua è direzionata preferenzialmente lungo le fibre, mentre è ostacolata perpendicolarmente ad esse. La trattografia utilizza le informazioni ottenute tramite il DW imaging per fornire una misura della connettività strutturale fra diverse regioni del cervello. Nel lavoro si è concentrata l’attenzione sul fascio corticospinale, che è coinvolto nella motricità volontaria, trasmettendo gli impulsi dalla corteccia motoria ai motoneuroni del midollo spinale. Il lavoro si è articolato in 3 fasi. Nella prima ho sviluppato il pre-processing di immagini DW acquisite con un gradiente di diffusione sia 25 che a 64 direzioni in ognuno dei 25 volontari sani. Si è messo a punto un metodo originale ed innovativo, basato su “Regions of Interest” (ROIs), ottenute attraverso la segmentazione automatizzata della sostanza grigia e ROIs definite manualmente su un template comune a tutti i soggetti in esame. Per ricostruire il fascio si è usato un algoritmo di trattografia probabilistica che stima la direzione più probabile delle fibre e, con un numero elevato di direzioni del gradiente, riesce ad individuare, se presente, più di una direzione dominante (seconda fibra). Nella seconda parte del lavoro, ciascun fascio è stato suddiviso in 100 segmenti (percentili). Sono stati stimati anisotropia frazionaria (FA), diffusività media, probabilità di connettività, volume del fascio e della seconda fibra con un’analisi quantitativa “along-tract”, per ottenere un confronto accurato dei rispettivi percentili dei fasci nei diversi soggetti. Nella terza parte dello studio è stato fatto il confronto dei dati ottenuti a 25 e 64 direzioni del gradiente ed il confronto del fascio fra entrambi i lati. Dall’analisi statistica dei dati inter-subject e intra-subject è emersa un’elevata variabilità tra soggetti, dimostrando l’importanza di parametrizzare il tratto. I risultati ottenuti confermano che il metodo di analisi trattografica del fascio cortico-spinale messo a punto è risultato affidabile e riproducibile. Inoltre, è risultato che un’acquisizione con 25 direzioni di DTI, meglio tollerata dal paziente per la minore durata dello scan, assicura risultati attendibili. La principale applicazione clinica riguarda patologie neurodegenerative con sintomi motori sia acquisite, quali sindromi parkinsoniane sia su base genetica o la valutazione di masse endocraniche, per la definizione del grado di contiguità del fascio. Infine, sono state poste le basi per la standardizzazione dell’analisi quantitativa di altri fasci di interesse in ambito clinico o di studi di ricerca fisiopatogenetica.

Analisi e applicazione dei processi di data mining al flusso informativo di sistemi real-time: Implementazione e analisi di un algoritmo autoadattivo per la ricerca di frequent patterns su macchine automatiche.

Analisi e applicazione dei processi di data mining al flusso informativo di sistemi real-time. Implementazione e analisi di un algoritmo autoadattivo per la ricerca di frequent patterns su macchine automatiche.

Analisi e applicazione dei processi di data mining al flusso informativo di sistemi real-time: Adattamento di un algoritmo di apprendimento automatico per la caratterizzazione e la ricerca di frequent patterns su macchine automatiche

La tesi da me svolta durante questi ultimi sei mesi è stata sviluppata presso i laboratori di ricerca di IMA S.p.a.. IMA (Industria Macchine Automatiche) è una azienda italiana che naque nel 1961 a Bologna ed oggi riveste il ruolo di leader mondiale nella produzione di macchine automatiche per il packaging di medicinali. Vorrei subito mettere in luce che in tale contesto applicativo l’utilizzo di algoritmi di data-mining risulta essere ostico a causa dei due ambienti in cui mi trovo. Il primo è quello delle macchine automatiche che operano con sistemi in tempo reale dato che non presentano a pieno le risorse di cui necessitano tali algoritmi. Il secondo è relativo alla produzione di farmaci in quanto vige una normativa internazionale molto restrittiva che impone il tracciamento di tutti gli eventi trascorsi durante l’impacchettamento ma che non permette la visione al mondo esterno di questi dati sensibili. Emerge immediatamente l’interesse nell’utilizzo di tali informazioni che potrebbero far affiorare degli eventi riconducibili a un problema della macchina o a un qualche tipo di errore al fine di migliorare l’efficacia e l’efficienza dei prodotti IMA. Lo sforzo maggiore per riuscire ad ideare una strategia applicativa è stata nella comprensione ed interpretazione dei messaggi relativi agli aspetti software. Essendo i dati molti, chiusi, e le macchine con scarse risorse per poter applicare a dovere gli algoritmi di data mining ho provveduto ad adottare diversi approcci in diversi contesti applicativi: • Sistema di identificazione automatica di errore al fine di aumentare di diminuire i tempi di correzione di essi. • Modifica di un algoritmo di letteratura per la caratterizzazione della macchina. La trattazione è così strutturata: • Capitolo 1: descrive la macchina automatica IMA Adapta della quale ci sono stati forniti i vari file di log. Essendo lei l’oggetto di analisi per questo lavoro verranno anche riportati quali sono i flussi di informazioni che essa genera. • Capitolo 2: verranno riportati degli screenshoot dei dati in mio possesso al fine di, tramite un’analisi esplorativa, interpretarli e produrre una formulazione di idee/proposte applicabili agli algoritmi di Machine Learning noti in letteratura. • Capitolo 3 (identificazione di errore): in questo capitolo vengono riportati i contesti applicativi da me progettati al fine di implementare una infrastruttura che possa soddisfare il requisito, titolo di questo capitolo. • Capitolo 4 (caratterizzazione della macchina): definirò l’algoritmo utilizzato, FP-Growth, e mostrerò le modifiche effettuate al fine di poterlo impiegare all’interno di macchine automatiche rispettando i limiti stringenti di: tempo di cpu, memoria, operazioni di I/O e soprattutto la non possibilità di aver a disposizione l’intero dataset ma solamente delle sottoporzioni. Inoltre verranno generati dei DataSet per il testing di dell’algoritmo FP-Growth modificato.

Valutazione dell'accuratezza e della precisione di un algoritmo di correlazione digitale di volumi applicato a vertebre naturali e trattate

La Digital Volume Correlation (DVC) è una tecnica di misura a tutto campo, non invasiva, che permette di misurare spostamenti e deformazioni all’interno della struttura ossea in esame. Mediante la comparazione d’immagini con provino scarico e con provino carico, ottenute attraverso sistemi di tomografia computerizzata, si può ottenere la mappa degli spostamenti per ogni direzione e la mappa di deformazione per ogni componente di deformazione. L’obiettivo di questo lavoro di tesi è la validazione della DVC, attraverso la determinazione dell’errore sistematico (accuratezza) e dell’errore casuale (precisione), in modo da poter valutare il livello di affidabilità della strumentazione. La valutazione si effettua su provini di vertebre di maiale, aumentate e non, sia a livello d’organo, sia a livello di tessuto. The Digital Volume Correlation (DVC) is a full field and contact less measurement technique that allowed estimating displacement and strain inside bone specimen. Images of the unloaded and loaded specimen were obtained from micro-CT and compared in order to obtain the displacement map and, differentiating, the strain map. The aim of this work is the validation of the approach, estimating the lack of accuracy (systematic error) and the lack of precision (random error) on different kinds of porcine vertebra, augmented and not, analysing the specimen on tissue level and on organ level.

L'algoritmo bionomico per il Traveling Salesman Problem

In questa tesi viene presentato un nuovo metaeuristico per la risoluzione del Traveling Salesman Problem (TSP) simmetrico. Tale metodo, detto algoritmo bionomico, è una variante dell'algoritmo genetico che usa un metodo innovativo di generazione del parents set. Nella tesi vengono proposti diversi metodi di crossover specifici per il TSP ma che possono essere facilmente estesi per altri problemi di ottimizzazione combinatoria. Tali metodi sono stati sperimentati su un insieme di problemi test, i risultati computazionali mostrano l'efficienza dei metodi proposti. In particolare uno dei metodi domina gli altri sia per la miglior qualità delle soluzioni prodotte che per il minor tempo di calcolo impiegato.