Italiano

Programma sintetico

- Processo di formazione delle immagini; rumore e "blurring". 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 del restauro di immagini. Soluzioni ai minimi quadrati e decomposizione ai valori singolari (SVD). Tecniche di regolarizzazione.
- Il restauro 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.
4. A. Beck, M. Teboulle, Gradient-Based Algorithms with Applications to Signal Recovery Problems, in D. Palomar, Y. Eldar (Eds.), Convex optimization in signal processing and communications, Cambridge University Press, 2010, pp. 42-88 (https://pdfs.semanticscholar.org/e7a7/5a379a515197e058102d985cd80f4f047c04.pdf, utilizzato in relazione ai metodi proximal gradient).

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 il restauro di immagini digitali affette da rumore e blurring.

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 restaurare 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 degli 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.

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

ARGOMENTI

Processo di formazione delle immagini; rumore e blurring. 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: definizione e proprietà. DFT bidimensionale. Uso della DFT per il calcolo di prodotti di convoluzione discreti con condizioni al contorno periodiche. Algoritmi di Fast Fourier Transform (FFT), formulazione ricorsiva degli algoritmi FFT radix-2. Filtraggio di immagini nel dominio delle frequenze.

Modelli matematici lineari del problema della ricostruzione di immagini. Mal posizione dei modelli e regolarizzazione. Soluzioni ai minimi quadrati e decomposizione ai valori singolari (SVD). Regolarizzazione mediante filtraggio spettrale. Regolarizzazione di Tikhonov, regolarizzazione L1, cenni sulla regolarizzazione mediante il funzionale di Variazione Totale. Cenni sulla scelta del parametro di regolarizzazione.

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: strategie line search e trust region, convergenza locale e globale, velocità di convergenza, criteri di arresto. Metodi line search: direzioni di ricerca, determinazione del passo mediante ricerca esatta e inesatta, condizioni di Armijo e di curvatura, algoritmi di backtracking e di interpolazione quadratica e cubica per la determinazione del passo, risultati generali di convergenza. Metodi del gradiente: formulazione, convergenza, regole di selezione del passo e relazioni con le proprietà spettrali della matrice Hessiana della funzione obiettivo. Analisi delle proprietà di regolarizzazione di alcuni metodi del gradiente applicati a problemi ai minimi quadrati lineari che modellano problemi di restauro di immagini. Metodi di Newton: metodo di Newton "classico", metodi di Newton con modifica 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 ordine (KKT) e del secondo ordine. Problemi convessi di ottimizzazione vincolata. Specializzazione delle condizioni di ottimo del primo ordine nel caso di vincoli di tipo box. Gradiente proiettato e condizioni di ottimo. 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.
- Introduzione ai metodi proximal gradient per la risoluzione di problemi di ottimizzazione con funzione obiettivo che è somma di due funzioni convesse, una differenziabile e l'altra non differenziabile. Applicazione a problemi di ricostruzione di immagini con regolarizzazione L1.

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 della DFT di un vettore reale e antisimmetria della DFT di un vettore 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 monotona basata su backtracking o su interpolazione quadratica e cubica. Analisi del comportamento della funzione su differenti problemi test, al variare del punto iniziale, della tolleranza e di altri parametri algoritmici. Confronto tra i risultati ottenuti con il metodo del gradiente e quelli ottenuti applicando 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.

- Applicazione di metodi proximal gradient implementati nel package FOM (https://sites.google.com/site/fomsolver/) a problemi di ricostruzione di immagini con regolarizzazione L1. Analisi dei risultati al variare del problema test e di parametri algoritmici.

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.
4. A. Beck, M. Teboulle, Gradient-Based Algorithms with Applications to Signal Recovery Problems, in D. Palomar, Y. Eldar (Eds.), Convex optimization in signal processing and communications, Cambridge University Press, 2010, pp. 42-88 (https://pdfs.semanticscholar.org/e7a7/5a379a515197e058102d985cd80f4f047c04.pdf, used for proximal gradient methods).

- 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 numerical analysis, usually taught in undergraduate programs in mathematics, is assumed.

The course consists of 48 hours (6 ECTS credits) of lectures 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.

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 Discrete Fourier Transform (DFT): definition and properties. Two-dimensional DFT. Use of the DFT for computing discrete convolution products with periodic boundary conditions. Fast Fourier Transform (FFT) algorithms, recursive formulation of radix-2 FFT algorithms. Image filtering in the frequency domain.

Linear mathematical models of image restoration problems. Ill-posedness of these models and regularization. Least Squares solutions and Singular Value Decomposition (SVD). Regularization through spectral filtering. Tikhonov and L1 regularization. Introduction to Total Variation regularization. Choice of the regularization parameter.

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 and trust-region techniques, local and global convergence, convergence rate, stop criteria. Line-search methods: search directions, exact and inexact line searches, Armijo and curvature conditions, backtracking and quadratic and cubic interpolation techniques for step-length selection, general convergence results. Gradient methods: formulation, convergence, step-length selection rules and their relationships with spectral properties of the Hessian of the objective function. Analysis the regularization properties of some gradient methods applied to linear least squares problems modelling image restoration problems. Newton methods: “classical” Newton method, Newton methods with Hessian modification, inexact Newton methods, quasi-Newton methods; convergence and rate of convergence of these methods.
- Introduction to constrained optimization: Lagrangian function, first-order (KKT) and second-order optimality conditions. Convex constrained optimization problems. First-order optimality conditions for bound-constrained problems. Projected gradient and optimality conditions. Gradient projection methods: general algorithm, main properties and convergence. Scaled gradient projection method for the restoration of images corrupted by Poisson noise.
- Introduction to proximal gradient methods for optimization problems where the objective function is the sum of a smooth convex function and a nonsmooth convex one. Application of these methods to image restoration problems with L1 regularization.


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 and writing images data from 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 fit and iffy MATLAB functions. Illustration, through examples, of the DFT properties (linearity, symmetry of the DFT of a real-valued sequence, antisymmetry of the DFT of an 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 debarring of images by truncated SVD.

- Development of a function implementing a gradient method for minimizing general nonlinear functions, with monotone line search based on backtracking or quadratic and cubic interpolation. Analysis of the behaviour of this function on selected test problems, varying the starting guess, the Florence in the stop criterion and other algorithmic parameters. Comparison of the results obtained with the gradient method and those 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.

- Application of proximal gradient methods from the FOM package (https://sites.google.com/site/fomsolver/) to image restoration problems with L1 regularization. Analysis of the results varying the test problem and the algorithmic parameters.