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

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: Room SIC-201, KReSIT Building (2nd floor)
Lecture Timings: Slot 14, Tuesday and Friday 5:30 to 7:00 pm
Instructor Office Hours (in room SIA-218): Immediately BEFORE class
Teaching Assistants: Jerin Geo James and Pranay Reddy Samala ({jeringeo,pranayr} @ cse DOT iitb DOT ac DOT in)

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.

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 3rd, 4th year B Tech students, 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 10%
Class participation (questions in class, discussions with instructor or on moodle) 5%
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.

Webpages of Previous Offerings

Course project

Project Topics and Instructions

Detailed Schedule

Date
Content of the Lecture
Assignments/Readings/Notes

10th Jan (Fri)

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

Slides (check moodle)

14th Jan (Tue) Compressed Sensing

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
Candes, Romberg, Tao: puzzling experiment; Basic optimization problem for CS involving the total variation (i.e. sum total gradient magnitude of the image)

Slides (check moodle)

Reading: E. Candes and M. Wakin, "Introduction to Compressive sampling", IEEE Signal Processing Magazine, 2008

17th Jan (Fri)

Concept of incoherence between sensing matrix and representation basis
Shannon's sampling theorem and the Whittaker-Shannon Interpolation Formula
Basic CS optimization problem: comments on the uniqueness of its solution
Basic theorem of compressed sensing involving coherence (due to Candes, Romberg, Tao)
Intuition behind role of incoherence in CS
Restricted isometry property

Slides (check moodle)

Reading: E. Candes and M. Wakin, "Introduction to Compressive sampling", IEEE Signal Processing Magazine, 2008

21st Jan (Tue)

Restricted isometry property
Basic theorems of CS: reconstruction of compressible signals
Compressed sensing under noise (theorem 3): choice of regularization parameter under different noise models
The role of randomness
Basis pursuit and its efficiency - Basis pursuit as a linear programming problem
Intuitive explanation: benefits of L1 or L2 penalty for signal sparsity
Toy examples of CS results
Sketch of a conventional camera
Rice single pixel camera

Slides (check moodle)

Reading: E. Candes and M. Wakin, "Introduction to Compressive sampling", IEEE Signal Processing Magazine, 2008

J. Romberg, "Imaging via Compressive sampling", IEEE Signal Processing Magazine, 2008

24th Jan (Fri)

Sketch of a conventional camera
Rice single pixel camera
Video version of the Rice SPC
Video compressive sensing using coded snapshots; concept of space-time tradeoff in video cameras

Slides (check moodle)

Duarte et al, "Single-pixel imaging via Compressive sampling", IEEE Signal processing magazine, 2008
Hitomi et al, "Video from single exposure coded snapshots", ICCV 2011

28th Jan (Tue)

CS algorithms: matching pursuit (MP) and orthogonal matching pursuit (OMP)
CS algorithms: ISTA (iterative shrinkage/thresholding algorithm)

Slides (check moodle)

31st Jan (Fri)

CASSI architecture for compressive hyperspectral image acquisition; multiframe CASSI; role of coded aperture
Concept for color filter arrays (CFA), Comparison of CASSI with color image demosaicing
CS for MRI

Slides (check moodle)

Kittle et al, "Multiframe image estimation for coded aperture snapshot spectral imagers", Applied Optics, 2010

Lustig et al, "Compressed sensing MRI", IEEE Signal Processing Magazine, 2008

4th Feb (Tue)

CS for MRI

Compressed sensing for piecewise constant signals

Concept of mutual coherence, CS theorem using mutual coherence (theorem 5) and its similarity with theorem 3

Relationship between RIC and mutual coherence, Gershgorin's disk theorem, reason why RIC is expensive to compute

Logan's result for band-limited signal recovery under impulse noise

Slides (check moodle)

7th Feb (Fri)

Sketch of proof for Theorem 3: Tube constraint, cone constraint, remaining steps using RIP and other inequalities

CS bounds based on RIC of order s (as opposed to 2s): Theorem 6

Motivation for overcomplete dictionaries

Designing compressed sensing matrices by optimizing on mutual coherence or based on Gram matrix

Slides (check moodle)

The restricted isometry property and its implications for compressed sensing

11th Feb (Tue)

Compressive classification: Generalized Maximum-Likelihood classifier in original and compressed domain; smashed filter
Proof that Basis Pursuit is a Linear Programming problem
Brief discussion on choice of regularization parameter in ISTA

Tomography

Concept of tomography and tompgraphic projection/Radon transform

Concept of backprojection and its limitations

Generations of CT (computed tomography) machines

Fourier slice theorem in tomography

Slides (check moodle)

14th Feb (Fri)

Fourier slice theorem in tomography

Concept of filtered backprojection and its relationship to (unfiltered) backprojection

Tomography as a compressed sensing problem; coupled tomographic reconstruction in a compressed sensing framework

Motivation for the problem of tomography under unknown angles

Slides (check moodle)

18th Feb (Tue)

Motivation for the problem of tomography under unknown angles

Cryo-electron microscopy, concept of micrography, presence of noise in micrograph, concept of particle picking

Moment based approach - Helgason Ludwig consistency conditions (2D images)

Ordering-based algorithm: nearest neighbor algorithm (2D images)

Slides (check moodle)

3rd March (Tue)

Graph-laplacian algorithm for dimensionality reduction (due to Belkin and Niyogi); its application to tomography under unknown angles

PCA-based algorithm for denoising of tomographic projections

Slides (check moodle)

6th March (Tue)

PCA-based algorithm for denoising of tomographic projections; derivation of a Wiener filter in the transform domain

Tomography under unknown angles in 3D (i.e. 2D projection images): the concept of common lines, algorithm for finding common lines in spatial or Fourier domain

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

Orthogonal procrustes algorithm

Slides (check moodle)

13th March (Tue)

Distribution of midsem papers and discussion of solutions

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

Slides (check moodle)

Week of 16th to 21st March Dictionary Learning:PCA (three recorded lectures on CDEEP)

Introduction to overcomplete dictionaries
Concept of overcomplete dictionaries: sinusoids and spikes examples
Issues of uniqueness and sparsity of representation in overcomplete dictionaries, dictionary learning as a generalization of K-means
Principal Components Analysis: Eigenfaces algorithm, complete derivation of PCA algorithm; relationship between DCT and PCA
Dictionary Learning: NMF (one short lecture recorded via zoom)

Non-negative matrix factorization (NMF) and non-negative sparse coding (NNSC)

Multiplicative update rules

Dictionary Learning: Overcomplete dictionaries (four short lecture recorded via zoom)

A basic algorithm for simultaneously obtaining dictionary and sparse code - using projected gradient descent with adaptive step-size
Method of Optimal Directions (MOD)
Union of Orthonormal Bases (two lectures for these two techniques together)
KSVD method: Theory (one lecture)
KSVD applications (one lecture)

Slides (check moodle)

Date	Content of the Lecture	Assignments/Readings/Notes
10th Jan (Fri)	Course overview: intro to compressed sensing, tomography, dictionary and transform learning, low rank matrix recovery	Slides (check moodle)
14th Jan (Tue)	Compressed Sensing 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 Candes, Romberg, Tao: puzzling experiment; Basic optimization problem for CS involving the total variation (i.e. sum total gradient magnitude of the image)	Slides (check moodle) Reading: E. Candes and M. Wakin, "Introduction to Compressive sampling", IEEE Signal Processing Magazine, 2008
17th Jan (Fri)	Concept of incoherence between sensing matrix and representation basis Shannon's sampling theorem and the Whittaker-Shannon Interpolation Formula Basic CS optimization problem: comments on the uniqueness of its solution Basic theorem of compressed sensing involving coherence (due to Candes, Romberg, Tao) Intuition behind role of incoherence in CS Restricted isometry property	Slides (check moodle) Reading: E. Candes and M. Wakin, "Introduction to Compressive sampling", IEEE Signal Processing Magazine, 2008
21st Jan (Tue)	Restricted isometry property Basic theorems of CS: reconstruction of compressible signals Compressed sensing under noise (theorem 3): choice of regularization parameter under different noise models The role of randomness Basis pursuit and its efficiency - Basis pursuit as a linear programming problem Intuitive explanation: benefits of L1 or L2 penalty for signal sparsity Toy examples of CS results Sketch of a conventional camera Rice single pixel camera	Slides (check moodle) Reading: E. Candes and M. Wakin, "Introduction to Compressive sampling", IEEE Signal Processing Magazine, 2008 J. Romberg, "Imaging via Compressive sampling", IEEE Signal Processing Magazine, 2008
24th Jan (Fri)	Sketch of a conventional camera Rice single pixel camera Video version of the Rice SPC Video compressive sensing using coded snapshots; concept of space-time tradeoff in video cameras	Slides (check moodle) Duarte et al, "Single-pixel imaging via Compressive sampling", IEEE Signal processing magazine, 2008 Hitomi et al, "Video from single exposure coded snapshots", ICCV 2011
28th Jan (Tue)	CS algorithms: matching pursuit (MP) and orthogonal matching pursuit (OMP) CS algorithms: ISTA (iterative shrinkage/thresholding algorithm)	Slides (check moodle)
31st Jan (Fri)	CASSI architecture for compressive hyperspectral image acquisition; multiframe CASSI; role of coded aperture Concept for color filter arrays (CFA), Comparison of CASSI with color image demosaicing CS for MRI	Slides (check moodle) Kittle et al, "Multiframe image estimation for coded aperture snapshot spectral imagers", Applied Optics, 2010 Lustig et al, "Compressed sensing MRI", IEEE Signal Processing Magazine, 2008
4th Feb (Tue)	CS for MRI Compressed sensing for piecewise constant signals Concept of mutual coherence, CS theorem using mutual coherence (theorem 5) and its similarity with theorem 3 Relationship between RIC and mutual coherence, Gershgorin's disk theorem, reason why RIC is expensive to compute Logan's result for band-limited signal recovery under impulse noise	Slides (check moodle)
7th Feb (Fri)	Sketch of proof for Theorem 3: Tube constraint, cone constraint, remaining steps using RIP and other inequalities CS bounds based on RIC of order s (as opposed to 2s): Theorem 6 Motivation for overcomplete dictionaries Designing compressed sensing matrices by optimizing on mutual coherence or based on Gram matrix	Slides (check moodle) The restricted isometry property and its implications for compressed sensing
11th Feb (Tue)	Compressive classification: Generalized Maximum-Likelihood classifier in original and compressed domain; smashed filter Proof that Basis Pursuit is a Linear Programming problem Brief discussion on choice of regularization parameter in ISTA Tomography Concept of tomography and tompgraphic projection/Radon transform Concept of backprojection and its limitations Generations of CT (computed tomography) machines Fourier slice theorem in tomography	Slides (check moodle)
14th Feb (Fri)	Fourier slice theorem in tomography Concept of filtered backprojection and its relationship to (unfiltered) backprojection Tomography as a compressed sensing problem; coupled tomographic reconstruction in a compressed sensing framework Motivation for the problem of tomography under unknown angles	Slides (check moodle)
18th Feb (Tue)	Motivation for the problem of tomography under unknown angles Cryo-electron microscopy, concept of micrography, presence of noise in micrograph, concept of particle picking Moment based approach - Helgason Ludwig consistency conditions (2D images) Ordering-based algorithm: nearest neighbor algorithm (2D images)	Slides (check moodle)
3rd March (Tue)	Graph-laplacian algorithm for dimensionality reduction (due to Belkin and Niyogi); its application to tomography under unknown angles PCA-based algorithm for denoising of tomographic projections	Slides (check moodle)
6th March (Tue)	PCA-based algorithm for denoising of tomographic projections; derivation of a Wiener filter in the transform domain Tomography under unknown angles in 3D (i.e. 2D projection images): the concept of common lines, algorithm for finding common lines in spatial or Fourier domain Algorithm for finding unknown angles and underlying 3D structure from 2D projections under unknown angles - case of 3 projections only Orthogonal procrustes algorithm	Slides (check moodle)
13th March (Tue)	Distribution of midsem papers and discussion of solutions 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	Slides (check moodle)
Week of 16th to 21st March	Dictionary Learning:PCA (three recorded lectures on CDEEP) Introduction to overcomplete dictionaries Concept of overcomplete dictionaries: sinusoids and spikes examples Issues of uniqueness and sparsity of representation in overcomplete dictionaries, dictionary learning as a generalization of K-means Principal Components Analysis: Eigenfaces algorithm, complete derivation of PCA algorithm; relationship between DCT and PCA Dictionary Learning: NMF (one short lecture recorded via zoom) Non-negative matrix factorization (NMF) and non-negative sparse coding (NNSC) Multiplicative update rules Dictionary Learning: Overcomplete dictionaries (four short lecture recorded via zoom) A basic algorithm for simultaneously obtaining dictionary and sparse code - using projected gradient descent with adaptive step-size Method of Optimal Directions (MOD) Union of Orthonormal Bases (two lectures for these two techniques together) KSVD method: Theory (one lecture) KSVD applications (one lecture)	Slides (check moodle)