42-505/705 Variational Image Processing

Course Info

• Description :

  This course offers an introduction to variational methods for image processing and analysis. These methods complement traditional spectral and stochastic methods. They permit a systematic treatment of geometric features of images and allow a rich set of numerical techniques for PDEs to be brought to bear on image processing problems. The course will cover four basic tasks in image analysis and processing: registration, enhancement, segmentation, and surface reconstruction. The required mathematical background in numerical methods for PDEs, level sets and dynamic implicit surfaces, and variational methods will be covered, albeit quickly.

  Official prerequisites are senior or graduate standing, a course in partial differential equations, and a course in finite element methods at the level of 12-755 (the latter can be a co-requisite). Students interested in the class but lacking the prerequisites are encouraged to speak to the instructor.

• Units : 12
• Meetings : Mondays and Wednesdays, from 3:30pm to 5:20pm
• Room : Doherty Hall, BME Conference Room
• Instructor : Omar Ghattas, Porter Hall 123J, x8-2949
• Co-Instructor : Alexandre Cunha, Porter Hall 7B, x8-8314 (email Sundance questions)
• WWW : www.cs.cmu.edu/~42-705

News

12/12: A new version of the nonlinear solver has been uploaded. Copy this new version, nlsolver2.cpp, to your working directory. The line search in nlsolver2.cpp has been augmented and now it uses the objective functional as the default merit function. Only the line search part has been modified. We suggest that you build your code on top of nlsolver2.cpp. Email me (Alex) if you have problems.

12/2: The nonlinear solver code nlsolver.cpp is available. Download, compile, link, and run the code to see how it works. Check the comments on assignment #4 below on how to set up your homework solution. Send me (Alex) your questions if you find something is not working properly.

10/13: Variations on the minimum surface code that Omar and Alex demoed in class are available. They include ms.cpp, in which Sundance determines the gradient equation and Newton steps by finding first and second variations; ms-h.cpp in which Sundance determines the Newton step but we hand code the gradient; ms-hh.cpp, in which we hand everything; and ms-hh-picard.cpp, where we code a Picard step (i.e. an approximate Newton step based on modifying the Hessian).

9/22: The minimum surface code we have seen in class is available following this link.

9/15: The code that implements the Galerkin approximation is available. When we run this code with the same beta values used in the energy minimization code (see sep/8 note above) we obtain the same final images. That is, Ritz and Galerkin methods give the same result for this problem. You can visually compare the images obtained by both methods. Email me (Alex) if you have problems.

9/8: The Sundance code shown in class to perform energy minimization is available here. Once you have concluded the setup part, you can download this code to your working directory and experiment with different values of the parameter beta and target images. The set of images obtained for different beta values shown in class is available following this link. In this case, the target image size is 65 x 65 pixels, and it corresponds to a 64 x 64 mesh (remember: a M x N regular mesh has (M+1) x (N+1) vertices, and if the mesh is made up of triangular elements, it has M x N x 2 triangles; each pixel on the image corresponds to a unique vertex of the mesh). Email me (Alex) if you have problems.

Assignments

1. hw1.pdf is now available. Visit the Sundance examples page and check the heat2D.cpp code to find out how to compute the L2 norm of the error. For the energy and H1 norms you will need to call the integral() method for their equivalent expressions.


2. hw2.pdf is now available.


3. hw3.pdf is now available. There are two sets of images you will need. The first case is the four circles image; both the original image circles.png and the noisy image circles-noisy.png can be found here. The second case is the Lena image. You can find the original image lena.png and noisy images corresponding to seven different levels of added noise in image directory (the noisy images are identified as "lenaXX.png", where XX refers to percent added noise). The Lena images are 200x200 pixels, so your finite element mesh size will be 199x199. Note also that if you use the image read/write utilities that Alex wrote, you should read in the .pnm versions of the images (also available in the image directory) rather than the .png versions. Finally, you can grab Alex's image read/write utilities from the top part of the galerkin.cpp code.


4. hw4.pdf is available. The following codes are available to download (send me - Alex - an email if you have problems/questions):
   • nlsolver.cpp: this code shows how to implement a nonlinear solver within the Sundance framework. You can use it as a template to build your code to solve the variational problem of hw #4. The code comes with a function, plotGridValues, to plot the nonlinear iterates at the mesh vertices. The outputs created by plotGridValues are to be used as inputs to the two Matlab routines below.
     IMPORTANT: You will have to submit these iterates as part of your solution (together with your source code).
   
   
   • imgct.m: use this Matlab routine to plot the level sets of your iterates on top of the imaging you are segmenting (see picture at right). For example, imgct('brain.png', 'brain.phi.000.ct.2D.dat') will plot the zero contour (default) of the discretized level set function in file brain.phi.000.ct.2D.dat on top of the image 'brain.png' (use here the PNG version of the image you are segmenting, not PNM). Other arguments exist.
   
   
   • plotct2D.m: use this Matlab routine to visualize the level set function in 3D; this is equivalent to plot2D.m but it uses as input a file generated by plotGridValues. For example, plotct2D('brain.phi.000.ct.2D.dat') will show a surface plot of values from file brain.phi.000.ct.2D.dat.

   You might want to try your segmentation code in a smaller, simpler image before jumping to the brain image. The image balls.pnm, available in the images directory, may be a good candidate.