CS 754: Advanced Image Processing(aka Inverse Problems in Image Processing), Spring 2021

CS 754 - Advanced Image Processing (aka Inverse Problems in Image Processing)

Course Information

Instructor: Ajit Rajwade
Office: SIA-218, KReSIT Building
Email: ajitvr AT cse DOT iitb DOT ac DOT in
Lecture Venue: MSTeams
Lecture Timings: Slot 13, i.e. Monday and Thursday 7:00 to 8:30 pm. (I will share pre-recorded lecture videos.)
Instructor Office Hours: Immediately BEFORE class on MSTeams (Details will be announced later)
Teaching Assistants: TBD

Course Description

Besides being just two- or three-dimensional arrays containing numbers (pixel intensity values), the images that are seen and acquired in everyday life have a number of very interesting properties. For example, small patches from different spatial regions of an image are quite similar to each other. Another example is that these images when transformed by certain kinds of matrix operations (eg: wavelet or discrete cosine transform) produce coefficients that are very sparse (i.e. most of them are zero or close to zero in value). These properties are a key to developing efficient and accurate algorithms for a variety of applications such as image noise removal, blur removal, image separation, compression and even image-based forensics. Not just that, these properties have also inspired the design of new sensors to acquire images much faster (a technology called compressed sensing) which is really crucial in tasks involving video or some types of images in medicine (such as magnetic resonance imaging - MRI). This course will systematically study several such techniques motivated by these interesting properties of natural images. The course will explore some key theory (including the proofs of some truly beautiful theorems), algorithms, as well as many applications. It will expose students to a broad range of modern, state-of-the-art techniques in image processing. A more detailed (tentative) syllabus can be accessed here. Many of the problems we will deal with in this class fall in the category of inverse problems, i.e. problems where the number of unknowns seems to exceed the number of knowns, at superficial glance, and there is also noise or system matrix contamination.

Many of the techniques studied in this course are very relevant in the era of BIG DATA, and they focus on intelligent acquisition of data. Can we acquire data in a compressed format so as to save resources: time, radiation given to a patient in a CT scanner, electrical power? Surprisingly, though we study these techniques in the context of image processing, the techniques are very generic and applicable in a variety of other domains. Last year at the beginning of the pandemic, many students in this course helped me and a colleague in developing techniques for saving resources used in COVID-19 RTPCR testing!

Need for the course

This course will cover some state-of-the-art techniques for several applications in image processing and provide some rigorous theoretical foundation behind those.
It will be of interest to students working in allied areas such as machine learning, statistics or signal processing, as well.
Besides CSE and EE, this course will be of interest to students from various disciplines such as remote sensing (CSRE), earth sciences, computational biology, computational physics, etc.

Image Processing Applications

The course will cover principled techniques that can be applied to some interesting image processing problems:

Denoising with different noise models, deblurring with different models of blur (motion/defocus)
Tomographic reconstruction (in computed tomography machines, as well as in biology/virology)
Reflection removal
Image-based forensics
Image compression
Compressive reconstruction - including reconstruction of video, Magnetic resonance imaging (MRI) and hyperspectral images
Some cutting-edge problems in image processing and machine learning: low rank matrix completion/recovery, phase retrieval, robust principal components analysis (RPCA) and compressive RPCA
Time permitting, we will study the application of different types of convolution neural networks (CNNs) for solving inverse problems -- this is a relatively less explored facet of CNNs. We will also try to explore theoretical aspects of neural networks.

Intended Audience and Pre-requisites

Intended for UG students from the second year onward, DDP students, and all PG students (MTech/PhD) from CSE/EE/EP/CSRE/Earth Sciences. You must have taken CS 663 or EE 610 or CS 725, otherwise you must discuss with me whether you have suitable background for this course.

Textbooks

"Natural Image Statistics", by Aapo Hyvarinen, Jarmo Hurri and Patrick Hoyer, Springer Verlag 2009, freely downloadable online
"A Mathematical Introduction to Compressive Sensing", by Simon Foucart and Holger Rauhut, Birkhauser, 2013
Statistical Learning with Sparsity: The Lasso and Generalizations", by Hastie, Tibshirani and Wainwright, CRC press (freely downloadable online)
Various research papers on key topics will be circulated

Resources

MATLAB at IITB
MATLAB Tutorial: here or here
MATLAB Image Processing Toolbox tutorial: here
Matlab Tutorial
The MathWorks - MATLAB Tutorial
Matlab Primer
On-line Matlab Help
Writing Fast Matlab Code (pdf)
Code Vectorization Guide
Matlab Programmin Style Guidelines (pdf)

Grading scheme (tentative)

Midsem: 10%
Cumulative Endsem: 15%
About 6-7 assignments involving programs, written problems and Google searches (yes you read that right -- but there's some (not so) fine print attached :-)) 50% (individually or in pairs)
Course project with demo and viva 25% (individually or in pairs). You are expected to put in significant effort in the course project (in terms of reading literature as well as implementation and mathematics) and assignments.
100% attendance is expected - the only exception is documented emergencies or participation in conferences. Students with less than 80% attendance may get DX grade.
Audit students must (1) write both exams and submit all assignments + project, and (2) have an aggregate score of at least 50%, for the AU grade.
I will put up optional quizzes online for you to check your understanding. These will not be graded.

Webpages of Previous Offerings

Course project

Project Topics and Instructions

Detailed Schedule

Date
Content of the Lecture
Assignments/Readings/Notes

Lecture 1: 10th Jan (Fri)

Course overview: intro to compressed sensing, tomography, dictionary and transform learning, low rank matrix recovery

Slides (check moodle)

Lecture 2: 11th Jan (Mon)

Compressed sensing (CS): introduction and motivation

Review of DFT and DCT, Review of JPEG, representation of a signal/image as a linear combination of basis vectors

Sparsity of natural images in transform bases

Slides (check moodle)

Lecture 3: 11th Jan (Mon)

Candes, Romberg, Tao: puzzling experiment; Basic optimization problem for CS involving the total variation (i.e. sum total gradient magnitude of the image)

Concept of incoherence between sensing matrix and representation basis

Slides (check moodle)

Lecture 4: 14th Jan (Thurs)

Theorem 1 for reconstruction guarantees

Whittaker-Shannon sampling theorem

Comparison between Theorem 1 and Shannon's sampling theorem.

Slides (check moodle)

Lecture 5: 18th Jan (Mon)

Further comments on theorem 1

Inutuition behind incoherence

Concept of restricted isometry property (RIP)

Slides (check moodle)

Lecture 6: 18th Jan (Mon)

Theorems 2 and 3 and comments on them

Motivation for use of L1 norm instead of L2 norm for compressed sensing

Toy sample experiments in compressed sensing

Slides (check moodle)

Lecture 7: 21st Jan (Thurs)

CS for piecewise constant signals: Theorem 4

Rice single pixel camera: architecture, and difference from conventional camera

Results on a patch-based Rice single pixel camera

Slides (check moodle)

Lecture 8: 21st Jan (Thurs)

Rice single pixel camera in video mode

Concept of tradeoff between spatial and temporal resolution in image acquisition

Video snapshot compressive sensing: concept, hardware description, results

Slides (check moodle)

Lecture 9: 25th Jan (Mon)

Video snapshot compressive sensing: concept, hardware description, results

Hyperspectral images: introduction

CASSI: Hyperspectral compressive sensing

Slides (check moodle)

Lecture 10: 25th Jan (Mon)

CASSI: Hyperspectral compressive sensing

Coded Filter Arrays (CFAs) and color image acquisition, image mosaicing

Importance of coded aperture

Compressed sensing for MRI

Slides (check moodle)

Lecture 11: 28th Jan (Thurs)

Matching pursuit (MP) and orthogonal matching pursuit (OMP)

Slides (check moodle)

Lecture 12: 28th Jan (Thurs)

Iterative Shrinkage and Thresholding Algorithm (ISTA)

Slides (check moodle)

Lecture 13: 1st Feb (Mon)

Compressed sensing for Pooled testing of COVID19 samples

RT-PCR noise model

Compressed sensing algorithms for pooled testing

Use of contact tracing and family information

Slides (check moodle)

Lecture 14: 4th Feb (Thurs)

Concept of mutual coherence and its relation to the RIC

Gershgorin's disc theorem

Sketch of proof of theorem 3, review of various vector inequalities

Slides (check moodle)

Lecture 15: 8th Feb (Mon)

Compressed sensing matrix design

Compressive classification

Slides (check moodle)

Lecture 16: 11th Feb (Thurs) Tomography

Introduction to tomography

Radon transforms, Fourier slice theorem

Backprojection and filtered backprojection

Slides (check moodle)

Lecture 17: 15th Feb (Mon)

Tomography as a compressed sensing (CS) problem

Concept of function handles

Coupled CS reconstruction

Slides (check moodle)

Lecture 18: 15th Feb (Mon)

Cryo-electron microscopy: introduction, concept of micrograph/particle

Tomography under unknown angles (2D images, 1D projections): Helgason Ludwig consistency conditions (HLCC), inherent ambiguity in tomography under unknown angles

Theoretical results in tomography under unknown angles (stated without proof)

Slides (check moodle)

Lecture 19: 18th Feb (Thurs)

Algorithms for tomography under unknown angles: moment-based method, algorithm by Basu and Bresler based on ordering, algorithm based on dimensionality reduction using Laplacian eigenmaps

Correction for unknown shifts in tomography under unknown angles; usage of order statistics for ordering and dimensionality reduction methods

Laplacian eigenmaps algorithm in detail

Slides (check moodle)

Lecture 20: 18th Feb (Thurs)

Algorithms for tomography under unknown angles: algorithm based on dimensionality reduction using Laplacian eigenmaps

Laplacian eigenmaps algorithm in detail

Denoising tomographic projections using spatially varying PCA and Wiener filter

Slides (check moodle)

Lecture 21: 22nd Feb (Mon)

Tomography under unknown angles in 3D: concept of common line, algorithms for determining common lines

Algorithm for finding unknown angles and underlying 3D structure from 2D projections under unknown angles - case of 3 projections only

Algorithm or finding unknown angles (based on semi-definite programming) and underlying 3D structure from 2D projections under unknown angles - case of N projections

Cryo-EM complete pipeline, concept of cryo-electron tomography and its difference from single particle cryo-EM

Handout: orthogonal procrustes algorithm

Slides (check moodle)

Lectures 22 and 23: 4th March (Thurs) Dictionary Learning

Principal components analysis (PCA): basic concept, derivation

Eigenfaces algorithms and its flavours

Concept of overcomplete dictionaries: merits/demerits compared to orthonormal bases

Slides (check moodle)

Lecture 24: 11th March (Mon)

Relation between PCA and DCT for image patches

Relation between dictionary learning and K-means

Dictionary learning: method of OLshausen and Field; Method of optimal directions (MOD); Union of Orthonormal bases with derivation

Slides (check moodle)

Lecture 25: 15th March (Thurs)

KSVD dictionary learning: basic algorithm, use of SVD within KSVD

Applications of KSVD: image compression, denoising, inpainting, video compressive sensing (Hitomi architecture)

Slides (check moodle)

Lecture 26: 18th March (Thurs)

Blind compressive sensing: concept, Compressive KSVD algorithm
Requirement for blind compressed sensing: diversity of measurement matrices
Non-negative matrix factorization, non-negative sparse coding

Slides (check moodle)

Lecture 27 and 28: 22nd March (Mon)

Concept of transform learning
Transform learning: Fisher's linear discriminant
Transform learning: classification using mutual information maximization (between class labels and the projections of the original datapoints)
Compressed sensing using overcomplete dictionaries

Slides (check moodle)

Lecture 29 and 30: 25th March (Thurs)

Ubiquitousness of low rank matrices in image processing and machine learning: recommender systems, image patches assembled to form a matrix, distance matrices, applications in structrue from motion, applications in face recognition
The problem of low rank matrix completion
Informal statement of the basic theorem, concept of coherence of subspaces, sufficient conditions for successful recovery and pathological cases
Formal statement of theorem of low rank matrix completion; extension to the case of noisy matrix completion
Empirical results for low rank matrix completion
Concept of low rank matrix recovery
Basic theorems for low rank matrix recovery, concept of RIP of linear maps/operators, relation between low rank matrix recovery and low rank matrix completion

Slides (check moodle)

Lecture 31 and 32: 1st April (Thurs)

Introduction to Robust Principal Components Analysis (PCA)
Motivating examples for RPCA: background subtraction in videos, specularity and shadow removal from face images
Basic theorem for RPCA; extension to the case when there is noise in observed matrix
Basic theorem for RPCA with incompletely observed entries
Singular Value Thresholding Algorithm (SVT) for matrix completionIntroduction to Robust Principal Components Analysis (PCA)
Motivating examples for RPCA: background subtraction in videos, specularity and shadow removal from face images
Basic theorem for RPCA; extension to the case when there is noise in observed matrix
Basic theorem for RPCA with incompletely observed entries
Singular Value Thresholding Algorithm (SVT) for matrix completion

Slides (check moodle)

Lecture 33: 4th April (Mon)

Introduction to Robust Principal Components Analysis (PCA)
Motivating examples for RPCA: background subtraction in videos, specularity and shadow removal from face images
Basic theorem for RPCA; extension to the case when there is noise in observed matrix
Basic theorem for RPCA with incompletely observed entries
ALM algorithm for RPCA
Compressive RPCA: Greedy Algorithm by Waters et al, applications in video and hyperspectral CS, and RPCA with missing entries
Basic Theorem for Compressive RPCA

Slides (check moodle)

Lecture 34: 8th April (Thurs) Statistics of Natural Images

Power law
Correlation of pixel values in natural images
Statistics of DCT coefficients of natural images: laplacian models and justification for the same
Brief introduction to the Haar wavelet transform
Brief introduction to the Haar wavelet transform
Revision of basic Bayesian statistics, concept of MAP and MMSE, posterior probabilities with gaussian likelihood and Lapalcian and Gaussian priors
Compressed sensing based on statistical priors

Slides (check moodle)

Lectures 35, 36, 37

Statistical properties of power spectra of natural image categories; application to scene categorization
Statistics of wavelet coefficients of natural images, use of dependencies between wavelet coefficients as priors for image denoising and in compression
A semi-automated method for reflection removal using statistics of image gradients: Iteratively reweighted least squares algorithm
Results of the IRLS algorithm for reflection removal, mixture of Laplacian prior for image gradients

Slides (check moodle)

Date	Content of the Lecture	Assignments/Readings/Notes
Lecture 1: 10th Jan (Fri)	Course overview: intro to compressed sensing, tomography, dictionary and transform learning, low rank matrix recovery	Slides (check moodle)
Lecture 2: 11th Jan (Mon)	Compressed sensing (CS): introduction and motivation Review of DFT and DCT, Review of JPEG, representation of a signal/image as a linear combination of basis vectors Sparsity of natural images in transform bases	Slides (check moodle)
Lecture 3: 11th Jan (Mon)	Candes, Romberg, Tao: puzzling experiment; Basic optimization problem for CS involving the total variation (i.e. sum total gradient magnitude of the image) Concept of incoherence between sensing matrix and representation basis	Slides (check moodle)
Lecture 4: 14th Jan (Thurs)	Theorem 1 for reconstruction guarantees Whittaker-Shannon sampling theorem Comparison between Theorem 1 and Shannon's sampling theorem.	Slides (check moodle)
Lecture 5: 18th Jan (Mon)	Further comments on theorem 1 Inutuition behind incoherence Concept of restricted isometry property (RIP)	Slides (check moodle)
Lecture 6: 18th Jan (Mon)	Theorems 2 and 3 and comments on them Motivation for use of L1 norm instead of L2 norm for compressed sensing Toy sample experiments in compressed sensing	Slides (check moodle)
Lecture 7: 21st Jan (Thurs)	CS for piecewise constant signals: Theorem 4 Rice single pixel camera: architecture, and difference from conventional camera Results on a patch-based Rice single pixel camera	Slides (check moodle)
Lecture 8: 21st Jan (Thurs)	Rice single pixel camera in video mode Concept of tradeoff between spatial and temporal resolution in image acquisition Video snapshot compressive sensing: concept, hardware description, results	Slides (check moodle)
Lecture 9: 25th Jan (Mon)	Video snapshot compressive sensing: concept, hardware description, results Hyperspectral images: introduction CASSI: Hyperspectral compressive sensing	Slides (check moodle)
Lecture 10: 25th Jan (Mon)	CASSI: Hyperspectral compressive sensing Coded Filter Arrays (CFAs) and color image acquisition, image mosaicing Importance of coded aperture Compressed sensing for MRI	Slides (check moodle)
Lecture 11: 28th Jan (Thurs)	Matching pursuit (MP) and orthogonal matching pursuit (OMP)	Slides (check moodle)
Lecture 12: 28th Jan (Thurs)	Iterative Shrinkage and Thresholding Algorithm (ISTA)	Slides (check moodle)
Lecture 13: 1st Feb (Mon)	Compressed sensing for Pooled testing of COVID19 samples RT-PCR noise model Compressed sensing algorithms for pooled testing Use of contact tracing and family information	Slides (check moodle)
Lecture 14: 4th Feb (Thurs)	Concept of mutual coherence and its relation to the RIC Gershgorin's disc theorem Sketch of proof of theorem 3, review of various vector inequalities	Slides (check moodle)
Lecture 15: 8th Feb (Mon)	Compressed sensing matrix design Compressive classification	Slides (check moodle)
Lecture 16: 11th Feb (Thurs)	Tomography Introduction to tomography Radon transforms, Fourier slice theorem Backprojection and filtered backprojection	Slides (check moodle)
Lecture 17: 15th Feb (Mon)	Tomography as a compressed sensing (CS) problem Concept of function handles Coupled CS reconstruction	Slides (check moodle)
Lecture 18: 15th Feb (Mon)	Cryo-electron microscopy: introduction, concept of micrograph/particle Tomography under unknown angles (2D images, 1D projections): Helgason Ludwig consistency conditions (HLCC), inherent ambiguity in tomography under unknown angles Theoretical results in tomography under unknown angles (stated without proof)	Slides (check moodle)
Lecture 19: 18th Feb (Thurs)	Algorithms for tomography under unknown angles: moment-based method, algorithm by Basu and Bresler based on ordering, algorithm based on dimensionality reduction using Laplacian eigenmaps Correction for unknown shifts in tomography under unknown angles; usage of order statistics for ordering and dimensionality reduction methods Laplacian eigenmaps algorithm in detail	Slides (check moodle)
Lecture 20: 18th Feb (Thurs)	Algorithms for tomography under unknown angles: algorithm based on dimensionality reduction using Laplacian eigenmaps Laplacian eigenmaps algorithm in detail Denoising tomographic projections using spatially varying PCA and Wiener filter	Slides (check moodle)
Lecture 21: 22nd Feb (Mon)	Tomography under unknown angles in 3D: concept of common line, algorithms for determining common lines Algorithm for finding unknown angles and underlying 3D structure from 2D projections under unknown angles - case of 3 projections only Algorithm or finding unknown angles (based on semi-definite programming) and underlying 3D structure from 2D projections under unknown angles - case of N projections Cryo-EM complete pipeline, concept of cryo-electron tomography and its difference from single particle cryo-EM Handout: orthogonal procrustes algorithm	Slides (check moodle)
Lectures 22 and 23: 4th March (Thurs)	Dictionary Learning Principal components analysis (PCA): basic concept, derivation Eigenfaces algorithms and its flavours Concept of overcomplete dictionaries: merits/demerits compared to orthonormal bases	Slides (check moodle)
Lecture 24: 11th March (Mon)	Relation between PCA and DCT for image patches Relation between dictionary learning and K-means Dictionary learning: method of OLshausen and Field; Method of optimal directions (MOD); Union of Orthonormal bases with derivation	Slides (check moodle)
Lecture 25: 15th March (Thurs)	KSVD dictionary learning: basic algorithm, use of SVD within KSVD Applications of KSVD: image compression, denoising, inpainting, video compressive sensing (Hitomi architecture)	Slides (check moodle)
Lecture 26: 18th March (Thurs)	Blind compressive sensing: concept, Compressive KSVD algorithm Requirement for blind compressed sensing: diversity of measurement matrices Non-negative matrix factorization, non-negative sparse coding	Slides (check moodle)
Lecture 27 and 28: 22nd March (Mon)	Concept of transform learning Transform learning: Fisher's linear discriminant Transform learning: classification using mutual information maximization (between class labels and the projections of the original datapoints) Compressed sensing using overcomplete dictionaries	Slides (check moodle)
Lecture 29 and 30: 25th March (Thurs)	Ubiquitousness of low rank matrices in image processing and machine learning: recommender systems, image patches assembled to form a matrix, distance matrices, applications in structrue from motion, applications in face recognition The problem of low rank matrix completion Informal statement of the basic theorem, concept of coherence of subspaces, sufficient conditions for successful recovery and pathological cases Formal statement of theorem of low rank matrix completion; extension to the case of noisy matrix completion Empirical results for low rank matrix completion Concept of low rank matrix recovery Basic theorems for low rank matrix recovery, concept of RIP of linear maps/operators, relation between low rank matrix recovery and low rank matrix completion	Slides (check moodle)
Lecture 31 and 32: 1st April (Thurs)	Introduction to Robust Principal Components Analysis (PCA) Motivating examples for RPCA: background subtraction in videos, specularity and shadow removal from face images Basic theorem for RPCA; extension to the case when there is noise in observed matrix Basic theorem for RPCA with incompletely observed entries Singular Value Thresholding Algorithm (SVT) for matrix completionIntroduction to Robust Principal Components Analysis (PCA) Motivating examples for RPCA: background subtraction in videos, specularity and shadow removal from face images Basic theorem for RPCA; extension to the case when there is noise in observed matrix Basic theorem for RPCA with incompletely observed entries Singular Value Thresholding Algorithm (SVT) for matrix completion	Slides (check moodle)
Lecture 33: 4th April (Mon)	Introduction to Robust Principal Components Analysis (PCA) Motivating examples for RPCA: background subtraction in videos, specularity and shadow removal from face images Basic theorem for RPCA; extension to the case when there is noise in observed matrix Basic theorem for RPCA with incompletely observed entries ALM algorithm for RPCA Compressive RPCA: Greedy Algorithm by Waters et al, applications in video and hyperspectral CS, and RPCA with missing entries Basic Theorem for Compressive RPCA	Slides (check moodle)
Lecture 34: 8th April (Thurs)	Statistics of Natural Images Power law Correlation of pixel values in natural images Statistics of DCT coefficients of natural images: laplacian models and justification for the same Brief introduction to the Haar wavelet transform Brief introduction to the Haar wavelet transform Revision of basic Bayesian statistics, concept of MAP and MMSE, posterior probabilities with gaussian likelihood and Lapalcian and Gaussian priors Compressed sensing based on statistical priors	Slides (check moodle)
Lectures 35, 36, 37	Statistical properties of power spectra of natural image categories; application to scene categorization Statistics of wavelet coefficients of natural images, use of dependencies between wavelet coefficients as priors for image denoising and in compression A semi-automated method for reflection removal using statistics of image gradients: Iteratively reweighted least squares algorithm Results of the IRLS algorithm for reflection removal, mixture of Laplacian prior for image gradients	Slides (check moodle)