Project

There will be two projects in this course. The first one, which counts for 10 % of the final grade, is given in September, and the second part, which counts for 20 %, will be given in the end of October/beginning of November. The project can to be done either individually or in pairs. If you are in search for a project partner, please send me an e-mail as soon as possible.

Project 2

  • The deadline for the first project is Sunday, November 19, 23:59.
  • The second project will count 20% of the final grade of the course.
  • If you don't hand in anything for the second project, you may take the exam, but the project still counts 20% of the grade.
  • You may work on the project either alone or in pairs.
  • The grading of the project will be mostly (80%) based on correctness and extent of the results, and partly (20%) on the form of the report. The quality/style of the code will not be assessed, but its correctness will be.
  • The code should run in reasonable time. A few minutes are ok - one hour is not. This means that you have to find a reasonably efficient method for implementing the Laplace operator and also the red-black Gauss-Seidel method.

Project description

  • Project 2, version 2; the signs in the right hand side of equation (5) were wrong in the original version.
  • Additional files necessary in the project:
    • Test images: frame10.png frame11.png
    • Some matlab code for the generation of simple test images: generate_test_images.m (you have to change the value of testcase in the code in order to switch between the two test images; the argument n of the function determines the size of the output images)
    • Some code for the depiction of vector fields as color encoded images: mycomputecolor.m
    • Computation of a color wheel using the same code: mycolorwheel.m

What to hand in and how

Your work should contain:

  1. A written report of at most ten pages submitted electronically as a PDF file.
    • You may write either in English or in Norwegian.
    • The report has a strict upper limit of ten pages. You may of course use fewer pages than that.
    • Preferably use LaTeX, but you may use any other typesetting program you like if this causes issues.
    • Do not put your names anywhere on the report. Either use your candidate numbers for this course (if they are already available) or your student numbers (if not).
  2. A zip file containing all your relevant code.
    • Make sure that the code actually runs and include enough documentation for me to run it as well.
    • The quality of the code will not be included in the grade; its correctness will be, though. In particular, your implementation should actually coincide with your description of the algorithm in your report.
    • Do not put your names anywhere in the code.

Send both files together by e-mail to Adrian Kirkeby with "TMA4205 - project 2" in the subject heading.

Help sessions

There will be additional help sessions for the duration of the project work, details will be published soon.

  • Both me and Adrian will be present in the exercise sessions from October 25 until November 15.
  • I will have extended office hours from 11-13 on November 8 and November 15 - these will take place in Nullrommet.
  • I will have office hours on Friday, November 17, from 12-15 (in my office).

FAQ

  • How do I test whether my algorithms work?
    If you run the program generate_test_images.m with testcase set to 1, the result will be a Gaussian that moves to the lower right (assuming that the first row of the image is at the top, and the last row at the bottom). More precisely, the Gaussian moves with speed \((0.02,0.04) \cdot n\), where \(n\) is the dimension of the image. If your implementation is correct, the results should reproduce this speed near the center of the image, and drop off to zero at the boundary (because of the Dirichlet boundary conditions).
  • My code runs fine for the Gaussian test images, but if I try to run it on real images, I only obtain uniform "blobs" as result. Why?
    This might be a scaling issue. The parameter \(\lambda \sim 1000\) works fine if the values of the images are in the range [0,255]. Depending on how you import the images to matlab and convert them to doubles, their scale might be different though. If you use for instance the command im2double for converting the imported images, they will rather be in the range [0,1]. In this case, you have to divide the parameter \(\lambda\) by 2552 in order to obtain good results.
  • My results seem mostly ok, but the colors are a bit off.
    This is probably due to the way I have \(x\) and \(y\) derivatives in my code. Try to exchange the \(u\) and \(v\) variables in your call of mycomputecolor.m.
  • My multigrid iteration works, but is much slower than the CG method.
    First of all, the running time of the algorithm depends strongly on the implementation, and in particular the Gauss-Seidel method can be implemented in Matlab in many different ways, some of which will result in a relatively slow algorithm. However, the number of iterations of the multigrid method should be significantly smaller than that of the CG method. You should expect something like 30-50 V-cycle iterations for the real test image (depending on the choice of all the different parameters). If your implementation requires significantly more iterations, this might be due to a wrong implementation of the Laplacian: At the coarsest level, you have a grid size of 1, and therefore you can simply use the unscaled Laplace matrix at that level. However, at the next finer level, the grid size is doubled, and thus the Laplacian matrix has to be divided by 4 (the square of the grid size); similar scalings occur on the even coarser levels. Alternatively, you can simply change the parameter \(\lambda\) in each level and call the solution method for the next coarser level with a parameter \(\lambda/4\) instead of \(\lambda\).

Errors in the project description

  • In the first version of the project description, the signs of the right hand sides of equation (5) were wrong. This error is corrected in the version that is currently online.
  • In line 5 on page 7 (within the matlab code), replace rhsu and rhsv by r2hu and r2hv respectively.

Project 1

General information

  • The deadline for the first project is Sunday, October 1, 23:59.
  • The first project will count 10% of the final grade of the course.
  • If you don't hand in anything for the first project, you may take the exam, but the project still counts 10% of the grade.
  • You may work on the project either alone or in pairs.
  • The grading of the project will be mostly (80%) based on correctness and extent of the results, and partly (20%) on the form of the report. The quality/style of the code will not be assessed, but its correctness will be.
  • You will need this note on the Eigenvalues of tridiagonal Toeplitz matrices for this project.

Project description

What to hand in and how

Your work should contain:

  1. A written report of at most five pages submitted electronically as a PDF file.
    • You may write either in English or in Norwegian.
    • The report has a strict upper limit of five pages. You may of course use fewer pages than that.
    • Preferably use LaTeX, but you may use any other typesetting program you like if this causes issues.
    • Do not put your names anywhere on the report. Either use your candidate numbers for this course (if they are already available) or your student numbers (if not).
  2. A zip file containing all your relevant code.
    • Make sure that the code actually runs and include enough documentation for me to run it as well.
    • The quality of the code will not be included in the grade; its correctness will be, though. In particular, your implementation should actually coincide with your description of the algorithm in your report.
    • Do not put your names anywhere in the code.

Send both files together by e-mail to Adrian Kirkeby with "TMA4205 - project 1" in the subject heading.

Help sessions

There will be additional help sessions for the duration of the project work:

  • Both me and Adrian will be present in the exercise sessions on September 13, September 20, and September 27.
  • I will have extended office hours from 11-13 on September 20 and September 27.
  • If needed, there will be an additional exercise class in the week before the deadline.
2017-11-15, Markus Grasmair