Computer Science in Practice (67864)

Spring 2007

People

Lecturer:
Dani Lischinski (danix@cs.huji.ac.il)
Office: Ross 73
Office hours: Tuesday, 12:00-13:00
Office phone: 02-6585087

TA:
Amit Gruber ( amitg@cs.huji.ac.il)
Office: Ross 57
Office hours: Sunday, 16:00-17:00
Office phone: 02-6584875

Description

The course will provide an introduction to the types of problems and solutions that are common in applied fields of computer science. The goal will not be to cover the fundamentals of each applied field and the course is not a replacement for existing courses in vision, graphics and learning. Rather we will focus on a small number of problems in each field and give the students hands-on experience with algorithms for solving these problems. Among the problems considered will be visual tracking, colorization, dynamic range compression, clustering and regression. We will discuss a wide range of algorithms, unified by the fact that they all make use of basic linear algebra. Specifically, we will discuss numerical methods for solving sparse linear equations, singular value decompositions, recursive matrix inversion and the Kalman and Wiener filters.

Tentative Syllabus

1 Introduction and Google's page rank.

Part I - learning

2 Supervised learning - regression and the pseudoinverse
3 Supervised learning - classification and the Fisher Linear Discriminant
4 Unsupervised learning - dimensionality reduction using PCA

Part II - image processing and vision

5 Unsupervised learning - spectral segmentation.
6 Optical flow - Lucas Kanade
7 SFM - Tomasi Kanade

Part III - graphics

8 High dynamic range compression (Fattal, Lischinski, and Werman)
9 Graphical image manipulation: Colorization (Levin, Lischinski, and Weiss)
10 Methods for solving linear systems with large number of equations - Jacobi, SOR, conjugate gradient

Textbooks

Golub and Van Loan, Matrix Computations, Johns Hopkins, 1996 (3rd Ed.).

Kay S. M., Fundamentals of Statistical Signal Processing , Prentice Hall Signal Processing Series, 1993.

Grimmett and Stirzaker, Probability and Random Processes, Oxford press, 2001 (3rd Ed.) or 1992 (2nd Ed.).

Lecture notes:

Date Subject Files Recommended Reading
February 27 Introduction and Google's page rank algorithm CSIP2007-intro.pdf -
March 6 Linear Regression CSIP2007-regression.pdf -
March 13 Linear Regression (cont.) CSIP2007-regression part2.pdf -
March 20 Classification and Fisher's Linear Discriminant CSIP2007-classification.pdf -
March 27 Unsupervised Learning and PCA CSIP2007-PCA.pdf -
May 15 Spectral Segmentation CSIP2007-segmentation.pdf -
May 29 / June 5 Structure From Motion CSIP2007-sfm.pdf -
June 5 / 12 Gradient-Domain HDR Compression CSIP2007-hdrc.pdf -
June 19 Colorization using Optimization CSIP2007-colorization.pdf -
June 26 Multigrid Methods CSIP2007-MG.pdf -
July 3 Optical Flow CSIP2007-OF.ppt -


Tirgul notes:

Date Subject Files Recommended Reading
February 26 Octave programming Tirgul1.ppt, tirgul1.m, meshgrid_example.m, my_repmat.m.
See Matlab/Octave links below
March 12 The Power Method tirgul2.pdf Matrix Computations (330-332)
March 19 Vector derivatives tirgul3_derivatives.pdf -
May 28 The Multivariate Normal Distribution tirgul34.pdf Grimmett, Kay (chapter 7)
June 4 Rotation Matrices rotation.pdf -
June 11 Structure From Motion sfm.pdf -
June 18 Deriving intrinsic images from image sequences iccv01.pdf (the paper by Yair Weiss) -
June 25 Iterative methods for sparse linear systems iterative.pdf Matrix Computations, pp. 510-513

Homework

There will be homework assignments about once every two weeks. There will be both theoretical exercises and practical exercises (using Octave).
Exercises should be submitted in pairs. If you discuss problems with another student, indicate on your writeup the name of your collaborator(s). In any case you must write up your own solutions.

Exercise Subject Submission date Comments
ex1.ps
ex1.pdf
The Power Method Monday, March 19 2007 Slides and code examples from the first tirgul: Tirgul1.ppt, tirgul1.m, meshgrid_example.m, my_repmat.m, tirgul2.pdf.
ex2.ps
ex2.pdf
Vector derivatives, linear regression, multi variate normal distribution Thursday, April 26 2007 -
ex3.ps
ex3.pdf
Linear Discriminant Analysis Tuesday, June 5 2007 ex3_data_1, ex3_data_2, ex3_data_3
geig.m
ex4.ps
ex4.pdf
3D Reconstruction (Tomasi-Kanade Factorization) Friday, June 22 2006 alignMat.m
ex5.ps
ex5.pdf
Deriving Intrinsic Images from Image Sequences Friday, July 6 2006 iccv01.pdf, demo.m, zeroB.m, getAlbedo.m, reconsEdge3.m, invDel2.m solvePoisson.m show.m

Exams from previous years

Moed A 2006
Moed B 2006

Useful links

Programming

Octave:
Octave for windows
http://www.octave.org/doc/index.html
http://math.iu-bremen.de/oliver/teaching/iub/resources/octave/octave-intro/octave-intro.html

Matlab tutorials:
http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_prog/exampleindex.html
http://alice.nc.huji.ac.il/~hvuag/neuromath/math/Matlab_Tutorial.pdf

Linear algebra and applications

Google's page rank algorithm
Stanford Personalized Page Rank Project
The power method
The power method
Matrix Computations course, taught at McMaster University, Canada
Vector derivatives

Learning

Linear Regression (Wikipedia)
Fisher Linear Discriminant Analysis

Clustering

Normalized Cut (conference version)
Normalized Cut (journal version)

Probability

Multivariate Normal Distribution
Probability review
Maximum Likelihood (from Wikipedia)

Structure From Motion

Tomasi-Kanade factorization method

Register,Grades,Submission

  • Please register to the course
  • Submit Exercises here
  • Get your grades
  • View some statistics