IT 530, Image Representation and Analysis

Course Instructor: Ajit Rajwade (FirstName UNDERSCORE LastName AT daiict DOT ac DOT in)
Term: Autumn 2012
Lecture Location: CEP 104
Lecture Timings: 11:00 to 11:55 am, Tuesday, Wednesday and Friday
Office Location: Faculty Block 1, Room 1201

Syllabus:

The course syllabus (tentative) is described here (.pdf). This is an M-Tech semester 3 elective. It is open to PhD students. Some background in pattern recognition and image processing is expected.

Grading Scheme

In-class presentation (60%)
Final Exam towards the end of the semester (20%)
Two or three assignments involving MATLAB programming (20%)

The in-class presentation will involve discussion of two-three papers assigned to students on first come first served basis. The students may choose other interesting papers related to the course material in consultation with the instructor. Everyone is encouraged to ask questions during the presentation and engage in informal discussion.

General Readings/Reference Books

Book by Hyvarinen, Hurri and Hoyer, "Natural Image Statistics - A probabilistic approach to early computational vision", Springer Verlag 2009 (pre-print can be downloaded for free).
Igor Carron's blog on Compressive Sensing
Compressive Sensing Page from Rice University.

Student Presentations

Click here for a list of papers and general instructions. Student presentation schedule

Lecture Schedule:

Date	Content of the Lecture	Assignments/Exams
24th July (Tue)	Introduction and Overview of Syllabus
25th July (Wed)	Statistics of Natural Images	Huang and Mumford,"Statistics of Natural Images and Models",CVPR 1999 Buccigrossi and Simoncelli, "Image Compression via Joint Statistical Characterization in the Wavelet Domain", IEEE Transactions on Image Processing, 1999 (sections 1 to 3)
27th July (Fri)	Noise Variance Estimation (using statistics of natural images)	Zoran and Weiss, "Scale Invariance and Noise Estimation in Natural Images",ICCV 2011 Pan et al, "Exposing Image Splicing with Inconsistent Local Noise Variances", ICCP 2012 DeStefano et al, "Training methods for image noise level estimation on wavelet components", EURASIP Journal on Applied Signal Procesing, 2004.
31st July (Tue)	Introduction to Wavelet Transform	Stoll et al, "Wavelets for Computer Graphics: A Primer (Part 1)", IEEE Computer Graphics and Applications, 1995 Tutorial for Wavelet Toolbox in MATLAB
1st Aug (Wed)	Denoising using Wavelet Shrinkage	Hyvarinen et al, "Image denoising using sparse code shrinkage", 1999 Simoncelli, "Bayesian denoising of Visual Images", 1999 Sendur and Selesnick, "Bivariate Shrinkage Functions for Wavelet-Based Denoising Exploiting Interscale Dependency", IEEE Transactions on Signal Processing, 2002.
3rd Aug (Fri)	Denoising using Wavelet Shrinkage (continued)	Read (only) section 2 of this paper to see the statement of Donoho and Johnstone's result that we discussed in class (slides 13 and 14 of the lecture ppt)
7th Aug (Tue)	Denoising using Wavelet Shrinkage (continued) Denoising with prior training on multiscale representations	Rajashekhar and Simoncelli, "Multiscale denoising of photographic images", The Essential Guide to Image Processing, 2009.
8th Aug (Wed)	Introduction to Principal Components Analysis (PCA): notes here (pages 115 to 117 from "Pattern Classification" by Duda and Hart - 2nd edition) PCA of natural images (see also section 5.8.2 of this book) Singular Value Decomposition (SVD): Basic Concepts	ASSIGNMENT 1(due August 29th)
14th Aug (Tue)	Singular Value Decomposition (SVD) [continued]: Applications: Eckhart-Young theorem (low-rank matrix approximation), solutions to equations of the form Ax = 0, nearest orthogonal matrix, SVD in the form of weighted sums of outer-products of unit vectors. Basic information theory: discrete(Shannon) entropy, distributions that maximize/minimize entropy, joint entropy, conditional entropy, chain rule	Sections 2.1 and 2.2 of "Elements of Information Theory" by Thomas and Cover. Local copy here.
17th Aug (Fri)	Basic information theory (continued): relative entropy (KL divergence), mutual information, mutual information as a KL divergence, convex and concave functions, Jensen's inequality and proof of Jensen's inequality.	Sections 2.3, 2.4 and 2.6 of "Elements of Information Theory" by Thomas and Cover. Local copy here.
21st Aug (Tue)	Basic information theory (continued): proof of non-negativity of KL-divergence (hence mutual information). Independent Components Analysis: introduction	Sections 2.3, 2.4 and 2.6 of "Elements of Information Theory" by Thomas and Cover. Local copy here. Tutorial on ICA by Hyvarinen and Oja. ICA chapter from "Pattern Classification" by Duda and Hart.
22nd Aug (Wed)	Independent Components Analysis: introduction - continued: ICA and non-Gaussianity, differential entropy, applications of ICA in grayscale and color image denoising. Applications of information theory (joint entropy and mutual information) in image registration	Tutorial on ICA by Hyvarinen and Oja. Hyvarinen et al, "Image denoising using sparse code shrinkage", 1999
24th Aug (Fri)	Applications of information theory (joint entropy and mutual information) in image registration Proofs using calculus of variations: (1) the Gaussian density maximizes the differential entropy amongst all densities with a fixed mean and fixed variance, (2) A KL divergence of zero implies that the two probability densities are equal.	Maes et al, "Multimodality Image Registration by Maximization of Mutual Information", IEEE Transactions on Medical Imaging, 1997.
28th Aug (Tue)	Discussion/recap of assignment 1.
29th Aug (Wed)	Kernel density estimation (Parzen windows), entropy and mutual information estimation using Parzen windows, use of this method in image registration, (Read sections 2.1 to 2.5 of this paper) Concept of stochastic gradient descent/ascent. Neighborhood filters, non-local self-similarity and non-local means. (first 15 slides)	Buades and Morel, "Non-local image and movie denoising", International Journal of Computer Vision, 2008.
4th Sept (Tue)	Neighborhood filters, non-local self-similarity and non-local means.	Awate and Whitaker, "Higher-Order Image Statistics for Unsupervised, Information-Theoretic, Adaptive, Image Filtering", CVPR 2005. Buades and Morel, "Non-local image and movie denoising", International Journal of Computer Vision, 2008. Announcement regarding student presentations.
5th Sept (Wed)	Non-local self-similarity continued: UINTA - an information theoretic and iterated variant of NL-means. Texture synthesis by non-parametric sampling Spatially varying PCA and BM3D (block matching 3D) for denoising	Awate and Whitaker, "Higher-Order Image Statistics for Unsupervised, Information-Theoretic, Adaptive, Image Filtering", CVPR 2005. Efros and Leung,"Texture synthesis by non-parametric sampling", ICCV 1999. Muresan and Parks, "Adaptive principal components for image denoising", ICIP 2003. Dabov, Foi, Katkovnik and Egiazarian,"Image denoising by sparse 3D transform-domain collaborative filtering", IEEE Transactions on Image Processing, 2007.
7th Sept (Fri)	Overcomplete dictionaries: concept and motivation, algorithms for projection onto overcomplete dictionaries, NP-hardness of this problem and approximation methods - basis pursuit (BP), matching pursuit (MP) and orthogonal matching pursuit (OMP).	Lewicki and Sejnowski, "Learning overcomplete representations", Neural Computation, 2000. (Read sections 1, 2 and 3 only)
11th Sept (Tue)	Overcomplete dictionaries: approximation methods continued - basis pursuit (BP), matching pursuit (MP) and orthogonal matching pursuit (OMP); dictionary learning: comparison with K-means, method of Olshausen and Field (using gradient descent) and its applications to natural image statistics, method of optimal directions by Engan et al.	Olshausen and Field, "Natural image statistics and sparse coding", 1996. Aharon et al,"K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation",IEEE Transactions on Signal Processing, 2006 (section 1 and 3 only).
12th Sept (Tue)	Overcomplete dictionaries: KSVD algorithm, applications of KSVD in dictionary learning based (lossy) image compression.	Aharon et al,"K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation",IEEE Transactions on Signal Processing, 2006. ASSIGNMENT 2 (due 3rd October)
14th Sept (Fri)	Overcomplete dictionaries: KSVD algorithm, applications of KSVD in dictionary learning based denoising and inpainting; Learning of overcomplete bases that are represented as a union of orthonormal bases - associated derivation of orthonormal procrustes problem.	Elad and Aharon,"Image denoising using sparse and redundant representations over learned dictionaries",IEEE Transactions on Image Processing, 2006. Aharon et al,"K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation",IEEE Transactions on Signal Processing, 2006.
18th Sept (Tue)	Discussion of assignment 2 and presentations.
19th Sept (Wed)	Applications of overcomplete dictionary representations for (1) texture classification/segmentation, and (2) detection of distinctive (small-sized) patches for object detection in cluttered backgrounds.	Skretting and Husoy,"Texture Classification Using Sparse Frame-Based Representations", EURASIP Journal on Applied Signal Processing 2005. Mairal et al, "Discriminative Learned Dictionaries for Local Image Analysis", CVPR 2008.
25th Sept (Tue)	Compressive Sensing: Shannon's theorem, Whittaker-Shannon interpolation formula and comparison to polynomial interpolation, Compressive sensing: big picture, Main requirements for compressive sensing: signal sparsity and incoherence of measurement matrix, L1 norm based optimization, first theorem for compressive sensing: exact reconstruction with overwhelming probability	Candes and Wakin, "An Introduction to Compressive Sampling", IEEE Signal Processing Magazine, 2008. Romberg, "Imaging via compressive sampling", IEEE Signal Processing Magazine, 2008.
26th Sept (Wed)	Compressive sensing (continued): Discussion of the first theorem and its comparison to Shannon's sampling theorem, Restricted isometry property (RIP), RIP for random matrices, Compressive sensing for signals that are not sparse but compressible (theorem 2), Compressive sensing under noise (theorem 3).	Candes and Wakin, "An Introduction to Compressive Sampling", IEEE Signal Processing Magazine, 2008. Romberg, "Imaging via compressive sampling", IEEE Signal Processing Magazine, 2008. Student presentation schedule
28th Sept (Fri)	Compressive sensing continued: Recap of theorems 1,2 and 3; Benefits of L1-norm optimization as opposed to L2-norm optimization in compressive sensing; toy imaging example: illustration of the superiority of random selection of DCT coefficients over just lower frequency coefficients; Compressive sensing for piecewise flat images (Total variation based optimization) - theorem 4 and its relationship with theorem 1; very brief enumeration of some extensions of basic compressive sensing theory: blind compressive sensing, compressive sensing for overcomplete bases, compressive sensing for systems with errors in measurement matrices.	Candes and Wakin, "An Introduction to Compressive Sampling", IEEE Signal Processing Magazine, 2008. Romberg, "Imaging via compressive sampling", IEEE Signal Processing Magazine, 2008.
3rd Oct (Wed)	Compressive imaging systems: Description of Rice Single Pixel Camera and associated reconstruction algorithm, extension to video acquisition; Compressive hyperspectral imaging system: coded aperture snapshot spectral imager (CASSI) - description of hardware setup.	Duarte et al, "Single Pixel Imaging via Compressive Sampling", IEEE Signal Processing Magazine, 2008. Kittle et al, "Multiframe image estimation for coded aperture snapshot spectral imagers", Applied Optics, 2010.
5th Oct (Fri)	Compressive imaging systems (continued): Compressive hyperspectral imaging system: coded aperture snapshot spectral imager (CASSI) - description of hardware setup; multi-frame version of CASSI; reconstruction algorithm for obtaining hyperspectral datacube from 2D snapshot(s); discussion of results Compressive video acquisition (full-frame mode): discussion of space-time tradeoff in video cameras, acquisition of coded exposure snapshots in a video camera, description of hardware setup for the acquisition.	Kittle et al, "Multiframe image estimation for coded aperture snapshot spectral imagers", Applied Optics, 2010. Hitomi et al, "Video from a single coded-exposure photograph using a learned overcomplete dictionary", ICCV 2011.
9th Oct (Tue)	Compressive video acquisition: discussion of hardware: structure of binary codes, description of dictionary learning procedure and sparse coding method for reconstruction of video from the coded snapshots, difference between the full-frame compresive video acquisition and the Single Pixel Camera based video acquisition; emphasis on the need for random codes (as generated by the LCoS device of the full-frame video-camera or the mask-code in CASSI) for good reconstruction performance. Matrix completion: Motivating problems - customer surveys, the Netflix prize problem, filling in missing pixels in images and videos, incomplete trajectories in structure from motion and multi-frame point correspondences.	Hitomi et al, "Video from a single coded-exposure photograph using a learned overcomplete dictionary", ICCV 2011. Also see video demo here and here.
10th Oct (Wed)	Matrix completion: conditions of low-rank and incoherence with canonical basis for accurate matrix reconstruction starting from a matrix with missing entries, related theorems, matrix completion under noise; singular value thresholding for matrix completion (with and without noise), brief look at some results.	Candes and Recht, "Exact Matrix Completion by Convex Optimization", Foundations of Computational Mathematics, 2008 (read only upto and including section 1.2). Cai et al, "A singular value thresholding algorithm for matrix completion", SIAM Journal on Optimization, 2008 (read upto and including section 1.2, and from section 5.2 on numerical results through to section 6 on conclusions).
12th Oct (Fri)	Matrix Completion: - application of matrix completion to image/video denoising under Gaussian and impulse noise. Robust Principal Components Analysis: applications involving decomposition of a matrix into sparse and low rank components - facial images under varied lighting, tracking of moving foreground in videos with stationary background; key theorem of robust PCA; relation with matrix completion literature; robust PCA under noise; overview of results.	Ji et al, "Robust video denoising using low rank matrix completion", CVPR 2010. Candes et al, "Robust Principal Components Analysis?", Journal of ACM, 2009 (read only section 1).