ITALIANO

Programma sintetico

- Processo di formazione delle immagini, rumore e blur. Modelli matematici di immagini degradate. Prodotti di convoluzione discreti, matrici strutturate associate, trasformata discreta di Fourier, algoritmi FFT, filtraggio di immagini nel dominio delle frequenze.
- Mal posizione del problema della ricostruzione di immagini. Soluzioni ai minimi quadrati e decomposizione ai valori singolari (SVD). Tecniche di regolarizzazione.
- La ricostruzione di immagini digitali come problema di ottimizzazione. Metodi numerici di ottimizzazione per la risoluzione di tale problema.

1. P.C. Hansen, J.G. Nagy, D.P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering, SIAM, 2006.
2. M. Bertero, P. Boccacci, Introduction to inverse problems, IOP, 1998.
3. J. Nocedal, S. Wright, Numerical Optimization, Second Edition, Springer, 2006.

Conoscenze e capacità di comprensione: al termine del corso lo studente dovrà aver acquisito la conoscenza di metodi numerici e strumenti software di base per la ricostruzione di immagini digitali affette da rumore e blur.

Applicazione delle conoscenze e della capacità di comprensione: al termine del corso lo studente dovrà essere in grado di utilizzare i metodi e gli strumenti acquisiti per la ricostruzione di immagini digitali.

Abilità comunicative: al termine del corso lo studente dovrà essere in grado di illustrare le metodologie e gli strumenti acquisiti e di esporre i risultati con essi ottenuti, utilizzando un linguaggio tecnico-scientifico appropriato.

L'insegnamento non prevede propedeuticità, ma presuppone la conoscenza di argomenti generalmente trattati in un corso di laurea triennale in matematica, tra i quali gli argomenti di un corso di base di analisi numerica.

Il corso si articola in 48 ore di lezioni frontali, corrispondenti a 6 CFU, e 24 ore di attività in laboratorio, corrispondenti a 2 CFU.

La frequenza non è obbligatoria, ma è fortemente consigliata.

La verifica dell'apprendimento consiste in una discussione orale sugli argomenti del programma. Durante tale discussione allo studente sarà richiesto di utilizzare il calcolatore per illustrare e applicare metodi e strumenti acquisiti durante il corso.

La discussione suddetta è valutata in trentesimi. Il voto minimo per superare l'esame è 18/30; il voto di 30 e lode viene conseguito nel caso di un esame particolarmente brillante.

Per la partecipazione alla prova d'esame è necessario esibire un documento di riconoscimento in corso di validità.

Eventuale materiale didattico aggiuntivo rispetto ai testi di riferimento sarà disponibile sulla piattaforma e-learning di Ateneo (https://elearning.unicampania.it/), in cui sarà attivato il corso "Metodi Numerici per l'Elaborazione di Immagini", a cui gli studenti avranno accesso con le credenziali di Ateneo.

ARGOMENTI

Processo di formazione delle immagini, rumore e blur. Modelli matematici di immagini degradate, Point Spread Function, sistemi di formazione dell'immagine spazio-invarianti e prodotti di convoluzione. Discretizzazione del prodotto di convoluzione e matrici strutturate (di Toeplitz, circolanti, di Hankel e loro versioni a blocchi).

Trasformata Discreta di Fourier (DFT) monodimensionale e bidimensionale. Uso della DFT per il calcolo di prodotti di convoluzione discreti con condizioni al contorno periodiche. Algoritmi di Fast Fourier Transform (FFT). Filtraggio di immagini nel dominio delle frequenze.

Modelli matematici lineari del problema della ricostruzione di immagini. Mal posizione e regolarizzazione. Soluzioni ai minimi quadrati e decomposizione ai valori singolari (SVD). Regolarizzazione mediante filtraggio spettrale. Regolarizzazione di Tikhonov e regolarizzazione L1.

Interpretazione statistica del problema della ricostruzione di immagini: approccio di massima verosimiglianza e approccio Bayesiano, con particolare riferimento al rumore di Gauss e al rumore di Poisson (modello basato sulla divergenza di Kullback-Leibler).


La ricostruzione di immagini come problema di ottimizzazione.

- Generalità sui metodi per l'ottimizzazione non vincolata. Metodi line search: direzioni di ricerca, determinazione del passo mediante ricerca esatta e inesatta, condizioni di Armijo e di curvatura, algoritmi di backtracking per la determinazione del passo, risultati generali di convergenza. Metodi del gradiente: formulazione, convergenza, regole di selezione del passo. Analisi delle proprietà di regolarizzazione di alcuni metodi del gradiente applicati a problemi ai minimi quadrati lineari che modellano problemi di ricostruzione di immagini. Metodi di tipo Newton: metodo di Newton, metodi di Newton con modifiche della matrice Hessiana, metodi di Newton inesatti, metodi quasi-Newton; convergenza e velocità di convergenza di tali metodi.

- Introduzione all'ottimizzazione vincolata: funzione Lagrangiana, condizioni di ottimo del primo e del secondo ordine. Problemi convessi di ottimizzazione vincolata. Specializzazione delle condizioni di ottimo del primo ordine nel caso di vincoli di tipo box. Metodi di proiezione del gradiente: schema generale, proprietà e convergenza. Metodo di proiezione del gradiente scalato per la ricostruzione di immagini corrotte da blur e rumore di Poisson.


ATTIVITA' DI LABORATORIO

Costituiscono parte integrante del programma del corso le attività di laboratorio di seguito elencate, svolte in ambiente MATLAB.

- Introduzione all'Image Processing Toolbox di MATLAB. Lettura, visualizzazione, conversione di formato e scrittura su file di immagini digitali, in bianco e nero e a colori. Costruzione di immagini test affette da rumore gaussiano e da differenti tipi di blur (generando la PSF con la funzione fspecial dell'Image Processing Toolbox e con le funzioni psfDefocus e psfGauss incluse nelle HNO functions disponibili sul sito http://www2.imm.dtu.dk/~pcha/HNO/).

- Calcolo della DFT e della DFT inversa di vettori complessi utilizzando le funzioni fft e ifft di MATLAB. Illustrazione, tramite esempi, di proprietà della DFT (linearità, simmetria/antisimmetria della DFT di un vettore reale/immaginario, DFT di una sequenza p-traslata, etc.). Calcolo di prodotti di convoluzione 2D utilizzando le funzioni fft2, ifft2 e fftshift; costruzione di immagini con blur mediante prodotto di convoluzione 2D.

- Compressione di immagini mediante SVD. Denoising e deblurring di immagini mediante SVD troncata.

- Sviluppo di una funzione che implementa un metodo del gradiente per la minimizzazione di generiche funzioni non lineari, con line search basata sul backtracking. Analisi del comportamento della funzione su differenti problemi test e confronto con i risultati ottenuti con il metodo BFGS implementato nella funzione Matlab fminunc dell'Optimization Toolbox di MATLAB.

- Applicazione del metodo di proiezione del gradiente scalato implementato nel package spg-dec (http://www.unife.it/prin/software) a problemi di ricostruzione di immagini corrotte da blur e rumore di Poisson. Analisi dei risultati al variare del problema test e dei parametri del metodo.

Italian

Summary of contents

- Image formation process, noise and blur. Mathematical models of noisy and blurred images. Discrete convolution products, associated structured matrices, discrete Fourier transform, FFT algorithms, image filtering in the frequency domain.
- Ill-posedness of image restoration problems. Least Squares solutions and Singular Value Decomposition (SVD). Regularization techniques.
- Modelling digital image restoration as an optimization problem. Related numerical optimization methods.

1. P.C. Hansen, J.G. Nagy, D.P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering, SIAM, 2006.
2. M. Bertero, P. Boccacci, Introduction to inverse problems, IOP, 1998.
3. J. Nocedal, S. Wright, Numerical Optimization, Second Edition, Springer, 2006.

Knowledge and understanding: students are expected to know basic numerical methods for restoration of noisy and blurred digital images.

Applying knowledge and understanding: students should be able to use basic methods and tools for restoring digital images.

Communication skills: students should be able to illustrate the methods and tools acquired during the course and to communicate the results obtained with them, using a suitable technical and scientific language.

Knowledge of basic methods and tools of mathematics usually taught in undergraduate programs in mathematics, and in particular of numerical analysis, is assumed.

The course consists of 48 hours of lectures (6 ECTS credits) and 24 hours (2 ECTS credits) of computing laboratory.

Attendance is not mandatory, but it is strongly recommended.

The exam consists in an oral assessment, which includes also a computer-based illustration of methods and tools studied during the course.

Marks are expressed in thirtieths. The minimum passing mark is 18/30; outstanding performance is marked 30/30 cum laude.

In order to be admitted to an exam, students must show a valid id card.

Additional course material will be made available on the university e-learning platform (https://elearning.unicampania.it/) under the course "Metodi Numerici per l'Elaborazione di Immagini", which can be accessed by the students using their credentials for University online services.

TOPICS

Image formation process, noise and blur. Mathematical models of noisy and blurred images, Point Spread Function (PSF), space-invariant imaging systems and convolution products. Discretization of convolution products and structured matrices (Toeplitz, circulant, Hankel, and related block versions).

One-dimensional and two-dimensional Discrete Fourier Transform (DFT). Use of the DFT for computing discrete convolution products with periodic boundary conditions. Fast Fourier Transform (FFT) algorithms. Image filtering in the frequency domain.

Linear mathematical models of image restoration problems. Ill-posedness and regularization. Least Squares solutions and Singular Value Decomposition (SVD). Regularization through spectral filtering. Tikhonov and L1 regularization.

Statistical interpretation of the image restoration problem: maximum likelihood and Bayesian approaches, with focus on Gaussian noise and Poisson noise (model based on the Kullback-Leibler divergence).


Modelling image restoration as an optimization problem.

- Fundamentals of unconstrained optimization. Line-search methods: search directions, exact and inexact line searches, Armijo and curvature conditions, backtracking techniques for step-length selection, general convergence results. Gradient methods: formulation, convergence, step-length selection rules. Analysis of the regularization properties of some gradient methods applied to linear least squares problems modelling image restoration problems. Newton-type methods: Newton method, Newton methods with Hessian modifications, inexact Newton methods, quasi-Newton methods; convergence and rate of convergence of these methods.

- Introduction to constrained optimization: Lagrangian function, first-order and second-order optimality conditions. Convex constrained optimization problems. First-order optimality conditions for bound-constrained problems. Gradient projection methods: general algorithm, main properties and convergence. Scaled gradient projection method for the restoration of images corrupted by Poisson noise.


COMPUTING LABORATORY EXERCISES

The following computing laboratory exercises will be carried out during the course, using the MATLAB environment. All students are required to do the exercises before taking the exam.

- Introduction to the MATLAB Image Processing Toolbox: reading/writing image data from/to files, image visualization and format conversion. Construction of test images corrupted by Gaussian noise and different blurs (building the PSF with the fspecial function from the MATLAB Image Processing Toolbox or with psfDefocus and psfGauss functions available from HNO (http://www2.imm.dtu.dk/~pcha/HNO/).

- Computation of the DFT and the inverse DFT of a complex vector by the fft and ifft MATLAB functions. Illustration, through examples, of the DFT properties (linearity, symmetry/antisymmetry of the DFT of a rea/imaginary-valued sequence, DFT of a shifted sequence, etc.). Computation of 2D convolutions using the fft2, ifft2 and fftshift MATLAB functions; generation of images blurred by using 2D convolutions.

- Image compression through SVD. Denoising and deblurring of images by truncated SVD.

- Development of a function implementing a gradient method for minimizing general nonlinear functions, with line search based on backtracking. Analysis of the behaviour of this function on selected test problems, and comparison of the results obtained with the BFGS method implemented in the fminunc function from the MATLAB Optimization Toolbox.

- Application of the scaled gradient projection method implemented in the spg-dec package (http://www.unife.it/prin/software) to the restoration of blurred images with Poisson noise. Analysis of the results, varying the test problem and the algorithmic parameters.