Riassunto analitico
Da molti anni le immagini digitali sono state utilizzate in vari settori della scienza, come astronomia, biologia e medicina, e in tutti i casi queste sono inevitabilmente danneggiate da rumore e sfocatura. In particolare il rumore è principalmente dovuto alla conversione del segnale da analogico a digitale, mentre la sfocatura solitamente è conseguenza della natura delle osservazioni, quali presenza di atmosfera, aberrazione delle lenti o effetti di diffrazione della luce. Una possibile strategia per la ricostruzione di queste immagini prevede un approccio statistico, noto come massima verosimiglianza. Tutti gli algoritmi appartenenti a questo gruppo presuppongono che l'immagine in ingresso sia affetta da rumore, di cui è nota la densità di probabilità, e tentano di trovare l'immagine iniziale più probabile data l'osservazione. Questo porta a risolvere problemi di ottimizzazione le cui funzioni obiettivo dipendono da questa densità di probabilità. Sebbene questi metodi di deconvoluzione diano spesso risultati accettabili, in campi applicativi come microscopia a fluorescenza e astronomia, essi sono computazionalmente intensivi, tipicamente a causa della grande dimensione dei dati. Una possibile soluzione per superare questo problema è la parallelizzazione del calcolo. Le strategie di parallelizzazione più comuni attualmente possono essere divise in due categorie principali. Per prima cosa, esistono algoritmi che sono implementati come applicazioni multi-thread e sviluppati per le architetture SMP (symmetric multiprocessing). Questo modello presuppone che tutte le unità di elaborazione (processori) siano identiche e usino un'unica memoria condivisa. Tali applicazioni parallele possono sfruttare le moderne architetture CPU multi-core, workstaion con diversi processori e memoria globale condivisa, o un diverso tipo di dispositivi multiprocessore ad alte prestazioni come le GPU (schede grafiche). In secondo luogo, gli algoritmi possono essere progettati per architetture a memoria distribuita. In questo caso ogni processore ha la propria memoria privata e i processori possono operare solo su dati locali, dovendo comunicare con altri per accedere ai loro dati. Software sviluppato con questo approccio può sfruttare un cluster di computer (un gruppo di PC collegati in rete) e può anche essere eseguito in modo efficiente su architetture SMP, per velocizzare i calcoli suddividendo il carico di lavoro tra i thread. Tuttavia la deconvoluzione di immagini di grandi dimensioni può essere ancora un problema. I computer general-purpose di solito contengono solo pochi GB di memoria e un processore con due o quattro core. Le workstation multiprocessore sono costose e contengono non più di quattro CPU. Le GPU potrebbero essere una buona soluzione per ottenere una migliore velocità, grazie alla loro architettura massicciamente parallela. In questa tesi sono presentate due versioni parallele del metodo del gradiente scalato proiettato (SGP) per risolvere i problemi di ottimizzazione che sorgono nella deconvoluzione di immagini e modificate per affrontare anche la riduzione dell'effetto di bordo tipicamente introdotto dagli algoritmi di ricostruzione. La prima versione sfrutta l'ambiente Message Passing Interface (MPI) e funziona in modo efficiente su cluster di computer, l'altra sfrutta l'ambiente CUDA per l'utilizzo con GPU NVidia. L'implementazione è stata progettata originalmente per i casi a 2 dimensioni o per immagini multiple in 2D, ma è stata estesa per immagini N-dimensionali. L'efficacia delle implementazioni parallele è stata valutata ricostruendo immagini di piccoli e grandi dimensioni, dando risultati notevoli e accelerazioni molto promettenti rispetto alle versioni scalari. Una sperimentazione numerica intensiva su immagini reali provenienti da astronomia e microscopia ha dimostrato che gli algoritmi proposti sono uno strumento molto promettente per deconvolvere in tempo reale immagini di grandi dimensioni.
|
Abstract
Since many years, digital images have been used in various areas of science, such as astronomy, biology and medicine, and in all cases these are unavoidably corrupted by noise and blur.
In particular the noise is mainly due to the conversion from analogical to digital signal, while the blur usually results from the nature of the observations, such as presence of atmosphere, lenses aberration or light diffraction effects.
A possible strategy for the restoration of this kind of images involves a statistical approach, known as Maximum Likelihood (ML) estimate.
All the algorithms belonging to this group assume that the input image is affected by noise whose probability density is known and attempt to find the most probable source image.
This leads to solve optimization problems whose objective function depend on the assumed noise probability density.
Although these statistical deconvolution methods often give acceptable results in applicative fields as fluorescence microscopy and astronomy, they are computationally intensive due to the typical large size of the data.
A possible solution to overcome this problem is the parallelization of the computation.
The most common parallelization strategies exploited currently may be divided into two main categories.
First, there are algorithms that are implemented as multi-threaded applications and developed for symmetric multiprocessing architectures (SMP).
This model assumes that all processing units (processors) are identical and use single shared main memory.
Such parallel application can use nowadays PC machines which multi-core CPU, workstations with several processors and shared global memory, or a different kind of high-performance multiprocessors devices such as the GPU (Graphical Process Unit).
Secondly, algorithms can be designed for distributed memory architectures. In this case, each processor has its own private memory.
Computational tasks can only operate on local data and must communicate with other tasks to access their data.
Software developed with this approach can use a computer cluster (a group of network-linked PC machines or workstations) and can also efficiently work on SMP architectures.
They can use SMP to speed the computation by splitting the calculation among threads.
However, deconvolution of large images may be still a problem. Standard computers usually contain only a few GBs of memory and one processor with two or four cores.
Multiprocessor workstations are expensive and contain no more than four CPUs.
Some GPU architectures could be a good solution to achieve the best speed, because of their massive parallel structure.
In this thesis we propose two parallel versions of the Scaled Gradient
Projection (SGP) method for solving the optimization problem arising in image deconvolution, including an extension to face also the reduction of the boundary effect typically introduced by the reconstruction algorithms.
The first version exploits the Message Passing Interface (MPI) environment and works efficiently on clusters of computers; the other version exploits the NVidia CUDA framework for GPU devices.
The implementation was designed principally for 2-dimensional cases or multiple 2D images, but it has been extended to work for N-dimensional images.
The effectiveness of the parallel schemes have been evaluated in image
deblurring on small and large scale problems, giving remarkable results and very promising speedups with respect to the scalar versions.
An intensive numerical experimentation on realistic images from applications in astronomy and microscopy showed that the proposed schemes is a very promising tool for achieving real time
deconvolution of very large images.
|